We present the Traffic Signal Plans Explorer, a framework for visualising and exploring traffic signal plans generated via PDDL+ planning. Designed to support both traffic experts and non-specialists, the tool offers a web-based interface for high-level network analysis and a SUMO-based adapter for detailed simulation. Users can inspect junction settings and link dynamics, and simulate plan execution step by step. The system bridges planning technology with practical traffic control, enhancing the transparency and usability of automatically generated solutions.

Optimising traffic signals is crucial for mitigating urban congestion, and automated planning, particularly with PDDL+, has shown promise for real-world deployment due to its flexibility and centralised perspective. While existing PDDL+ models guarantee deployability on current infrastructure, they face significant limitations: reliance on domain-independent heuristics restricts their applicability and scalability, leading to slow solution generation and unclear plan quality. To overcome these challenges and unlock the widespread adoption of planning-based traffic control, we introduce hCAFE, a domain-specific heuristic for PDDL+-based traffic signal optimisation. Unlike prior approaches, hCAFE is designed to work effectively across multiple problem encodings, addressing a key limitation of traditional domain-specific heuristics. We demonstrate its capabilities on real-world data from a region of the UK, showing significant improvements in solution generation time and search space exploration. Our evaluation also compares the strategies generated by hCAFE against historical data from existing traffic control systems and a non-deployable benchmark, confirming the high quality of the resulting plans.

Stable models of logic programs have been studied and characterized in relation with other formalisms by many researchers. As already argued in previous papers, such characterizations are interesting for diverse reasons, including theoretical investigations and the possibility of leading to new algorithms for computing stable models of logic programs. At the theoretical level, complexity and expressiveness comparisons have brought about fundamental insights. Beyond that, practical implementations of the developed reductions enable the use of existing solvers for other logical formalisms to compute stable models. In this paper, we first provide a simple characterization of stable models that can be viewed as a proof-theoretic counterpart of the standard model-theoretic definition. We further show how it can be naturally encoded in difference logic. Such an encoding, compared to the existing reductions to classical logics, does not require Boolean variables. Then, we implement our novel translation to a Satisfiability Modulo Theories (SMT) formula. We finally compare our approach, employing the SMT solver yices, to the translation-based ASP solver lp2diff and to clingo on domains from the “Basic Decision” track of the 2017 Answer Set Programming competition. The results show that our approach is competitive to and often better than lp2diff, and that it can also be faster than clingo on non-tight domains.

In this paper, we propose a novel approach for solving automated planning problems, called Symbolic Pattern Planning. Given a deterministic planning problem Π, we propose to compute a plan by first fixing a pattern –defined as an arbitrary sequence of actions– and then define a formula encoding the state resulting from the sequential execution of the actions in the pattern, starting from an arbitrary initial state. By allowing each action in the pattern to be executed consecutively zero, one or possibly more times, and by imposing the conditions on the initial and goal states, we can check whether the pattern allows determining a valid plan or whether the pattern needs to be extended and the procedure iterated. We ground our proposal in the numeric planning setting, we prove the correctness and also the completeness of the procedure (provided at each iteration the pattern is extended with a complete sequence of actions), and we define procedures for the pattern selection and for computing quality plans. When exploiting the planning as satisfiability approach, we show that our encoding allows to determine a valid plan in a number of iterations which is never higher than the one needed by the state-of-the-art rolled-up or relaxed-relaxed-∃ symbolic encodings. On the experimental side, we run an extensive analysis which included the problems and systems involved in the numeric track of the 2023 International Planning Competition, showing that the results validate the theoretical findings and that our planner Patty has remarkably good comparative performances.

Abstract The Nuclear Medicine Scheduling (NMS) problem consists of assigning patients to a day, on which the patient will undergo the medical check, the preparation and the actual image detection process. The schedule should consider the different requirements of the patients and the available resources, e.g. varying time required for different diseases and radiopharmaceuticals used, number of injection chairs and tomographs available. In this paper, we present two solutions to the NMS problem based on Answer Set Programming (ASP). The first solution is a direct ASP encoding, which is then processed by an ASP solver, while the second solution employs a Logic-based Bender Decomposition (LBBD) approach implemented through the usage of multi-shot solving. Experiments employing real data show that the direct encoding provides overall satisfying results in terms of solutions quality in a relatively short time, and that the LBBD approach also helps in improving scalability.

Real-world applications of planning techniques often deal with dynamic and noisy environments, where sensor readings are often inaccurate, and the world's states can evolve in unexpected ways. This is particularly challenging for hybrid discrete-continuous planning approaches, where processes and events can be strongly affected by even slightly different initial conditions of the world, and planning tasks are notoriously difficult to cope with. In this paper, we introduce the Initial Condition Retrieving (ICR) problem to foster hybrid planning in real-world applications. Given a knowledge model of a planning task and a trace, solving the ICR problem allows identifying the space of all the initial conditions from which the provided plan is guaranteed to reach a goal state. We define three tasks: (i) retrieving any valid initial condition, (ii) fixing only some desired initial values and retrieving a complete initial condition that fills in the unassigned values, or (iii) retrieving the closest achievable initial condition to a fully specified one from which the goal cannot be reached. Experiments on well-known hybrid planning domains demonstrate the efficacy of our approach in solving such tasks. Moreover, given that our approach can be applied to numeric planning without any change, we extend our analysis to numeric domains, where we obtain positive results.

Languages for Knowledge Representation and Reasoning, such as ASP, CP, and SMT, excel at solving some complex problems, but encoding them into a higher-level language may be more profitable, leaving these formalisms as targets for solving. Recent studies aim to convert controlled natural languages into formal representations, yet these solutions are often tailored to specific languages and require significant effort. This paper introduces a general framework that generates grammars for target representation languages, enabling the translation of problems stated in CNL into formal representations. The related system, CNLWizard, offers a flexible, high-level approach to defining desired grammars, significantly reducing the time and effort needed to create custom grammars. Finally, we demonstrate the system's effectiveness through an experimental analysis.

Stable models of logic programs have been studied and characterized in relation with other formalisms by many researchers. As already argued in previous papers, such characterizations are interesting for diverse reasons, including theoretical investigations and the possibility of leading to new algorithms for computing stable models of logic programs. At the theoretical level, complexity and expressiveness comparisons have brought about fundamental insights. Beyond that, practical implementations of the developed reductions enable the use of existing solvers for other logical formalisms to compute stable models. In this paper, we first provide a simple characterization of stable models that can be viewed as a proof-theoretic counterpart of the standard model-theoretic definition. We further show how it can be naturally encoded in difference logic. Such an encoding, compared to the existing reductions to classical logics, does not require Boolean variables. Then, we implement our novel translation to a Satisfiability Modulo Theories (SMT) formula. We finally compare our approach, employing the SMT solver yices , to the translation-based ASP solver lp2diff and to clingo on domains from the “Basic Decision” track of the 2017 Answer Set Programming competition. The results show that our approach is competitive to and often better than lp2diff , and that it can also be faster than clingo on non-tight domains.

Abstract The operating room scheduling (ORS) problem deals with the optimization of daily operating room surgery schedules. It is a challenging problem subject to many constraints, like to determine the starting time of different surgeries and allocating the required resources, including the availability of beds in different department units. Recently, solutions to this problem based on answer set programming (ASP) have been delivered. Such solutions are overall satisfying but, when applied to real data, they can currently only verify whether the encoding aligns with the actual data and, at most, suggest alternative schedules that could have been computed. As a consequence, it is not currently possible to generate provisional schedules. Furthermore, the resulting schedules are not always robust. In this paper, we integrate inductive and deductive techniques for solving these issues. We first employ machine learning algorithms to predict the surgery duration, from historical data, to compute provisional schedules. Then, we consider the confidence of such predictions as an additional input to our problem and update the encoding correspondingly in order to compute more robust schedules. Results on historical data from the ASL1 Liguria in Italy confirm the viability of our integration.

Abstract In the context of urban traffic control, traffic signal optimisation is the problem of determining the optimal green length for each signal in a set of traffic signals. The literature has effectively tackled such a problem, mostly with automated planning techniques leveraging the PDDL + language and solvers. However, such language has limitations when it comes to specifying optimisation statements and computing optimal plans. In this paper, we provide an alternative solution to the traffic signal optimisation problem based on Constraint Answer Set Programming (CASP). We devise an encoding in a CASP language, which is then solved by means of clingcon 3 , a system extending the well-known ASP solver clingo . We performed experiments on real historical data from the town of Huddersfield in the UK, comparing our approach to the PDDL+ model that obtained the best results for the considered benchmark. The results showed the potential of our approach for tackling the traffic signal optimisation problem and improving the solution quality of the PDDL + plans.

In this paper, we propose a novel approach for solving linear numeric planning problems, called Symbolic Pattern Planning. Given a planning problem Pi, a bound n and a pattern --defined as an arbitrary sequence of actions-- we encode the problem of finding a plan for Pi with bound n as a formula with fewer variables and/or clauses than the state-of-the-art rolled-up and relaxed-relaxed-exists encodings. More importantly, we prove that for any given bound, it is never the case that the latter two encodings allow finding a valid plan while ours does not. On the experimental side, we consider 6 other planning systems --including the ones which participated in this year's International Planning Competition (IPC)-- and we show that our planner Patty has remarkably good comparative performances on this year's IPC problems.

The PDDL+ formalism allows the use of planning techniques in applications that require the ability to perform hybrid discrete-continuous reasoning. PDDL+ problems are notoriously challenging to tackle, and to reason upon them a well-established approach is discretisation. Existing systems rely on a single discretisation delta or, at most, two: a simulation delta to model the dynamics of the environment, and a planning delta, that is used to specify when decisions can be taken. However, there exist cases where this rigid schema is not ideal, for instance when agents with very different speeds need to cooperate or interact in a shared environment, and a more flexible approach that can accommodate more deltas is necessary. To address the needs of this class of hybrid planning problems, in this paper we introduce a reformulation approach that allows the encapsulation of different levels of discretisation in PDDL+ models, hence allowing any domain-independent planning engine to reap the benefits. Further, we provide the community with a new set of benchmarks that highlights the limits of fixed discretisation.

The PDDL+ formalism allows the use of planning techniques in applications that require the ability to perform hybrid discrete-continuous reasoning. PDDL+ problems are notoriously challenging to tackle, and to reason upon them a well-established approach is discretisation. Existing systems rely on a single discretisation delta or, at most, two: a simulation delta to model the dynamics of the environment, and a planning delta, that is used to specify when decisions can be taken. However, there exist cases where this rigid schema is not ideal, for instance when agents with very different speeds need to cooperate or interact in a shared environment, and a more flexible approach that can accommodate more deltas is necessary. To address the needs of this class of hybrid planning problems, in this paper we introduce a reformulation approach that allows the encapsulation of different levels of discretisation in PDDL+ models, hence allowing any domain-independent planning engine to reap the benefits. Further, we provide the community with a new set of benchmarks that highlights the limits of fixed discretisation.

Abstract The problem of scheduling pre-operative assessment clinic (PAC) consists of assigning patients to a day for the exams needed before a surgical procedure, taking into account patients with different priority levels, due dates and operators availability. Realizing a satisfying schedule is of upmost importance for a hospital, since delay in PAC can cause delay in the subsequent phases, thus lowering patients’ satisfaction. In this paper, we propose a two-phase solution to the PAC problem: in the first phase, patients are assigned to a day taking into account a default list of exams; then, in the second phase, having the actual list of exams needed by each patient, we use the results of the first phase to assign a starting time to each exam. We first present a mathematical formulation for both problems. Further, we present a solution where modeling and solving are done via answer set programming. We then introduce a rescheduling solution that may come into play when the scheduling solution cannot be applied fully. Experiments employing synthetic benchmarks on both scheduling and rescheduling show that both solutions provide satisfying results in short time. We finally show the implementation and usage of a web application that allows to run our scheduling solution and analyze the results graphically in a transparent way.

Abstract The Operating Room Scheduling (ORS) problem deals with the optimization of daily operating room surgery schedules. It is a challenging problem subject to many constraints, like to determine the starting time of different surgeries and allocating the required resources, including the availability of beds in different units. In the past years, Answer Set Programming (ASP) has been successfully employed for addressing and solving the ORS problem. Despite its importance, due to the inherent difficulty of retrieving real data, all the analyses on ORS ASP encodings have been performed on synthetic data so far. In this paper, first we present a new, improved ASP encoding for the ORS problem. Then, we deal with the real case of ASL1 Liguria, an Italian health authority operating through three hospitals, and present adaptations of the ASP encodings to deal with the real-world data. Further, we analyse the resulting encodings on hospital scheduling data by ASL1 Liguria. Results on some scenarios show that the ASP solutions produce satisfying schedules also when applied to such challenging, real data.1

Abstract Answer set programming (ASP) has demonstrated its potential as an effective tool for concisely representing and reasoning about real-world problems. In this paper, we present an application in which ASP has been successfully used in the context of dynamic traffic distribution for urban networks, within a more general framework devised for solving such a real-world problem. In particular, ASP has been employed for the computation of the “optimal” routes for all the vehicles in the network. We also provide an empirical analysis of the performance of the whole framework, and of its part in which ASP is employed, on two European urban areas, which shows the viability of the framework and the contribution ASP can give.

Abstract A core part of the rehabilitation scheduling process consists of planning rehabilitation physiotherapy sessions for patients, by assigning proper operators to them in a certain time slot of a given day, taking into account several legal, medical, and ethical requirements and optimizations, for example, patient’s preferences and operator’s work balancing. Being able to efficiently solve such problem is of upmost importance, in particular after the COVID-19 pandemic that significantly increased rehabilitation’s needs. In this paper, we present a two-phase solution to rehabilitation scheduling based on Answer Set Programming, which proved to be an effective tool for solving practical scheduling problems. We first present a general encoding and then add domain-specific optimizations. Results of experiments performed on both synthetic and real benchmarks, the latter provided by ICS Maugeri, show the effectiveness of our solution as well as the impact of our domain-specific optimizations.

Abstract Answer set programming (ASP) is a popular declarative programming language for solving hard combinatorial problems. Although ASP has gained widespread acceptance in academic and industrial contexts, there are certain user groups who may find it more advantageous to employ a higher-level language that closely resembles natural language when specifying ASP programs. In this paper, we propose a novel tool, called CNL2ASP, for translating English sentences expressed in a controlled natural language (CNL) form into ASP. In particular, we first provide a definition of the type of sentences allowed by our CNL and their translation as ASP rules and then exemplify the usage of the CNL for the specification of both synthetic and real-world combinatorial problems. Finally, we report the results of an experimental analysis conducted on the real-world problems to compare the performance of automatically generated encodings with the ones written by ASP practitioners, showing that our tool can obtain satisfactory performance on these benchmarks.

Abstract The rehabilitation scheduling process consists of planning rehabilitation physiotherapy sessions for patients, by assigning proper operators to them in a certain time slot of a given day, taking into account several requirements and optimizations, e.g. patient’s preferences and operator’s work balancing. Being able to efficiently solve such problem is of upmost importance, in particular as a consequence of the COVID-19 pandemic that significantly increased rehabilitation’s needs. The problem has been recently successfully solved via a two-phase solution based on answer set programming (ASP). In this paper, we focus on the problem of rescheduling the rehabilitation sessions, which comes into play when the original schedule cannot be implemented, for reasons that involve the unavailability of operators and/or the absence of patients. We provide rescheduling solutions based on ASP for both phases, considering different scenarios. Results of experiments performed on real benchmarks, provided by ICS Maugeri, show that also the rescheduling problem can be solved in a satisfactory way. Finally, we present a web application that supports the usage of our solution.

Abstract The problem of finding a Master Surgical Schedule (MSS) consists of scheduling different specialties to the operating rooms (ORs) of a hospital clinic. To produce a proper MSS, each specialty must be assigned to some ORs, where the number of assignments is different for each specialty and can also vary during the considered planning horizon. The problem is enriched by considering resource availability such as beds, surgical teams and nurses. Realizing a satisfying schedule is of upmost importance for a hospital clinic, since a poorly scheduled MSS may lead to unbalanced specialties availability and increase patients’ waiting list, thus negatively affecting both the administrative costs of the hospital and the patient satisfaction. In this paper, we present compact solutions based on Answer Set Programming (ASP) to the MSS problem. We tested our solutions on different scenarios: experiments show that our ASP solutions provide satisfying results in short time, also when compared to other logic-based formalisms. Finally, we describe a web application we have developed for easy usage of our solution.

Abstract The decoupling between the representation of a certain problem, that is, its knowledge model, and the reasoning side is one of main strong points of model-based artificial intelligence (AI). This allows, for example, to focus on improving the reasoning side by having advantages on the whole solving process. Further, it is also well known that many solvers are very sensitive to even syntactic changes in the input. In this paper, we focus on improving the reasoning side by taking advantages of such sensitivity. We consider two well-known model-based AI methodologies, SAT and ASP, define a number of syntactic features that may characterise their inputs, and use automated configuration tools to reformulate the input formula or program. Results of a wide experimental analysis involving SAT and ASP domains, taken from respective competitions, show the different advantages that can be obtained by using input reformulation and configuration.

Abstract dialectical frameworks (ADFs) constitute one of the most powerful formalisms in abstract argumentation. Their high computational complexity poses, however, certain challenges when designing efficient systems. In this paper, we tackle this issue by (i) analyzing the complexity of ADFs under structural restrictions, (ii) presenting novel algorithms which make use of these insights, and (iii) implementing these algorithms via (multiple) calls to SAT solvers. An empirical evaluation of the resulting implementation on ADF benchmarks generated from ICCMA competitions shows that our solver is able to outperform state-of-the-art ADF systems.

Abstract The Operating Room Scheduling (ORS) problem is the task of assigning patients to operating rooms (ORs), taking into account different specialties, lengths, and priority scores of each planned surgery, OR session durations, and the availability of beds for the entire length of stay (LOS) both in the Intensive Care Unit (ICU) and in the wards. A proper solution to the ORS problem is of primary importance for the healthcare service quality and the satisfaction of patients in hospital environments. In this paper we first present a solution to the problem based on Answer Set Programming (ASP). The solution is tested on benchmarks with realistic sizes and parameters, on three scenarios for the target length on 5-day scheduling, common in small–medium-sized hospitals, and results show that ASP is a suitable solving methodology for the ORS problem in such setting. Then, we also performed a scalability analysis on the schedule length up to 15 days, which still shows the suitability of our solution also on longer plan horizons. Moreover, we also present an ASP solution for the rescheduling problem, that is, when the offline schedule cannot be completed for some reason. Finally, we introduce a web framework for managing ORS problems via ASP that allows a user to insert the main parameters of the problem, solve a specific instance, and show results graphically in real time.

Public railway transport systems play a crucial role in servicing the global society and are the transport backbone of a sustainable economy.While a significant effort has been devoted to predict inter-station trains movements to support stakeholders (i.e., infrastructure managers, train operators, and travellers) decisions, the problem of predicting instation movements, while being crucial to improve train dispatching (i.e., empowering human or automatic dispatchers), has been far more less investigated.In fact, stations are the most critical points in a railway network: even small improvements in the estimation of the duration of trains movements can remarkably enhance the dispatching efficiency in coping with the increase in capacity demand and with delays.In this work we will first leverage on state of the art shallow models, fed by domain experts with domain specific features, to improve the current predictive systems.Then, we will leverage on a customised deep multi scale model able to automatically learn the representation and improve the accuracy of the shallow models.Results on real-world data coming from the Italian railway network will support our proposal.* This work has been partially

In-station train dispatching is the problem of optimising the effective utilisation of available railway infrastructures for mitigating incidents and delays. In this paper, we describe an approach for dealing with the in-station dispatching problem by means of automated planning techniques.

Abstract The manipulation of articulated objects is of primary importance in Robotics and can be considered as one of the most complex manipulation tasks. Traditionally, this problem has been tackled by developing ad hoc approaches, which lack flexibility and portability. In this paper, we present a framework based on answer set programming (ASP) for the automated manipulation of articulated objects in a robot control architecture. In particular, ASP is employed for representing the configuration of the articulated object for checking the consistency of such representation in the knowledge base and for generating the sequence of manipulation actions. The framework is exemplified and validated on the Baxter dual-arm manipulator in the first, simple scenario. Then, we extend such scenario to improve the overall setup accuracy and to introduce a few constraints in robot actions execution to enforce their feasibility. The extended scenario entails a high number of possible actions that can be fruitfully combined together. Therefore, we exploit macro actions from automated planning in order to provide more effective plans. We validate the overall framework in the extended scenario, thereby confirming the applicability of ASP also in more realistic Robotics settings and showing the usefulness of macro actions for the robot-based manipulation of articulated objects.

Abstract The problem of scheduling chemotherapy treatments in oncology clinics is a complex problem, given that the solution has to satisfy (as much as possible) several requirements such as the cyclic nature of chemotherapy treatment plans, maintaining a constant number of patients, and the availability of resources, for example, treatment time, nurses, and drugs. At the same time, realizing a satisfying schedule is of upmost importance for obtaining the best health outcomes. In this paper we first consider a specific instance of the problem which is employed in the San Martino Hospital in Genova, Italy, and present a solution to the problem based on Answer Set Programming (ASP). Then, we enrich the problem and the related ASP encoding considering further features often employed in other hospitals, desirable also in S. Martino, and/or considered in related papers. Results of an experimental analysis, conducted on the real data provided by the San Martino Hospital, show that ASP is an effective solving methodology also for this important scheduling problem.

This paper addresses two intertwined needs for collaborative robots operating in shop-floor environments. The first is the ability to perform complex manipulation operations, such as those on articulated or even flexible objects, in a way robust to a high degree of variability in the actions possibly carried out by human operators during collaborative tasks. The second is encoding in such operations a basic knowledge about physical laws (e.g., gravity), and their effects on the models used by the robot to plan its actions, to generate more robust plans. We adopt the manipulation in three-dimensional space of articulated objects as an effective use case to ground both needs, and we use a variant of the Planning Domain Definition Language to integrate the planning process with a notion of gravity. Different complexity levels in modelling gravity are evaluated, which tradeoff model faithfulness and performance. A thorough validation of the framework is done in simulation using a dual-arm Baxter manipulator.

The issue of describing in a formal way solving algorithms in various fields such as Propositional Satisfiability (SAT), Quantified SAT, Satisfiability Modulo Theories, Answer Set Programming (ASP), and Constraint ASP, has been relatively recently solved employing abstract solvers. In this paper we deal with cautious reasoning tasks in ASP, and design, implement and test novel abstract solutions, borrowed from backbone computation in SAT. By employing abstract solvers, we also formally show that the algorithms for solving cautious reasoning tasks in ASP are strongly related to those for computing backbones of Boolean formulas. Some of the new solutions have been implemented in the ASP solver WASP, and tested.

This special issue of Fundamenta Informaticae publishes extended and revised versions of the best papers presented at RCRA 2018, the 25th Workshop of the RCRA working group (Rappresentazione della conoscenza e Ragionamento Automatico, Knowledge representation and automated reasoning) of the Italian Association for Artificial Intelligence (AI*IA).1 This event continues the series of the RCRA annual meetings held since 1994 and becoming international in 2007.

The Answer Set Programming (ASP) logic programming paradigm was introduced in the late 1990s, based on the answer set semantics of logic programs proposed by Gelfond and Lifschitz a decade earlier. To date, ASP has been applied to a variety of domains and demonstrated its suitability for solving knowledge-intensive tasks and combinatorial search problems, in particular. One direction of ASP research focuses on the development of efficient methods for computing answer sets. Novel techniques were initially adapted from SAT, which led to the introduction of satisfiability modulo theories. More recently, ideas have been derived from the study of the relationship between ASP and other computing paradigms, such as constraint satisfaction, quantified boolean formulas, first-order logic, pseudo-boolean solvers, theorem provers. A second line of work in the ASP community investigates multi-paradigm problem-solving for practical applications, which has resulted so far in the integration of ASP with description logics, constraint satisfaction and external means of computation.

Abstract Standardization of solver input languages has been a main driver for the growth of several areas within knowledge representation and reasoning, fostering the exploitation in actual applications. In this document, we present the ASP-CORE-2 standard input language for Answer Set Programming, which has been adopted in ASP Competition events since 2013.

Abstract Answer Set Programming (ASP) is a prominent knowledge representation language with roots in logic programming and non-monotonic reasoning. Biennial ASP competitions are organized in order to furnish challenging benchmark collections and assess the advancement of the state of the art in ASP solving. In this paper, we report on the design and results of the Seventh ASP Competition, jointly organized by the University of Calabria (Italy), the University of Genova (Italy), and the University of Potsdam (Germany), in affiliation with the 14th International Conference on Logic Programming and Non-Monotonic Reasoning (LPNMR 2017).

This special issue of Fundamenta Informaticae publishes extended and revised versions of the best papers presented at the 24th RCRA International Workshop (RCRA 2017). 1 This event follows the series of the RCRA (the working group of the AI*IA association on Knowledge Representation and Automated Reasoning) annual meetings, held since 1994, and that since 2007 became an international workshop.RCRA 2017 was held in Bari, Italy, on 14th November 2017 as a satellite workshop of the 16th International Conference of the Italian Association for Artificial Intelligence (AI*IA 2017).The success of all these events shows that RCRA is nowadays established as a major forum for exchanging ideas and proposing experimentation methodologies for algorithms in Artificial Intelligence.vi iii possibility and for his support throughout the whole process.Finally, we are very grateful to the Program Committee members and to the external anonymous reviewers of RCRA 2017 for their work, as well as to the authors and the participants that took part in the workshop.

Abstract Abstract solvers are a method to formally analyze algorithms that have been profitably used for describing, comparing and composing solving techniques in various fields such as Propositional Satisfiability (SAT), Quantified SAT, Satisfiability Modulo Theories, Answer Set Programming (ASP), and Constraint ASP. In this paper, we design, implement and test novel abstract solutions for cautious reasoning tasks in ASP. We show how to improve the current abstract solvers for cautious reasoning in ASP with new techniques borrowed from backbone computation in SAT, in order to design new solving algorithms. By doing so, we also formally show that the algorithms for solving cautious reasoning tasks in ASP are strongly related to those for computing backbones of Boolean formulas. We implement some of the new solutions in the ASP solver wasp and show that their performance are comparable to state-of-the-art solutions on the benchmark problems from the past ASP Competitions.

Answer set programming (ASP) is a prominent knowledge representation and reasoning paradigm that found both industrial and scientific applications. The success of ASP is due to the combination of two factors: a rich modeling language and the availability of efficient ASP implementations. In this paper we trace the history of ASP systems, describing the key evaluation techniques and their implementation in actual tools.

Abstract dialectical frameworks (ADFs) constitute one of the most powerful formalisms in abstract argumentation. Their high computational complexity poses, however, certain challenges when designing efficient systems. In this paper, we tackle this issue by (i) analyzing the complexity of ADFs under structural restrictions, (ii) presenting novel algorithms which make use of these insights, and (iii) empirically evaluating a resulting implementation which relies on calls to SAT solvers.

"23rd RCRA International workshop on “Experimental evaluation of algorithms for solving problems with combinatorial explosion”." Journal of Experimental & Theoretical Artificial Intelligence, 30(4), pp. 479–480

Abstract Answer Set Programming (ASP) is a logic-based knowledge representation framework, supporting—among other reasoning modes—the central task of query answering. In the propositional case, query answering amounts to computing cautious consequences of the input program among the atoms in a given set of candidates, where a cautious consequence is an atom belonging to all stable models. Currently, the most efficient algorithms either iteratively verify the existence of a stable model of the input program extended with the complement of one candidate, where the candidate is heuristically selected, or introduce a clause enforcing the falsity of at least one candidate, so that the solver is free to choose which candidate to falsify at any time during the computation of a stable model. This paper introduces new algorithms for the computation of cautious consequences, with the aim of driving the solver to search for stable models discarding more candidates. Specifically, one of such algorithms enforces minimality on the set of true candidates, where different notions of minimality can be used, and another takes advantage of unsatisfiable cores computation. The algorithms are implemented inwasp, and experiments on benchmarks from the latest ASP competitions show that the new algorithms perform better than the state of the art.

Abstract Aggregates are among the most frequently used linguistic extensions of answer set programming. The result of an aggregation may introduce new constants during the instantiation of the input program, a feature known as value invention. When the aggregation involves literals whose truth value is undefined at instantiation time, modern grounders introduce several instances of the aggregate, one for each possible interpretation of the undefined literals. This paper introduces new data structures and techniques to handle such cases, and more in general aggregations on the same aggregate set identified in the ground program in input. The proposed solution reduces the memory footprint of the solver without sacrificing efficiency. On the contrary, the performance of the solver may improve thanks to the addition of some simple entailed clauses which are not easily discovered otherwise, and since redundant computation is avoided during propagation. Empirical evidence of the potential impact of the proposed solution is given.

Answer Set Programming (ASP) is a well-known paradigm of declarative programming with roots in logic programming and non-monotonic reasoning. Similar to other closely related problem-solving technologies, such as SAT/SMT, QBF, Planning and Scheduling, advancements in ASP solving are assessed in competition events. In this paper, we report about the design and results of the Sixth ASP Competition, which was jointly organized by the University of Calabria (Italy), Aalto University (Finland), and the University of Genoa (Italy), in affiliation with the 13th International Conference on Logic Programming and Non-Monotonic Reasoning. This edition maintained some of the design decisions introduced in 2014, e.g., the conception of sub-tracks, the scoring scheme, and the adherence to a fixed modeling language in order to push the adoption of the ASP-Core-2 standard. On the other hand, it featured also some novelties, like a benchmark selection stage classifying instances according to their empirical hardness, and a "Marathon" track where the top-performing systems are given more time for solving hard benchmarks.

Abstract Constraint answer set programming (CASP) is an extension of answer set programming that allows for numerical constraints to be added in the rules. PDDL+ is an extension of the PDDL standard language of automated planning for modeling mixed discrete-continuous dynamics. In this paper, we present CASP solutions for dealing with PDDL+ problems, i.e., encoding from PDDL+ to CASP, and extensions to the algorithm of theezcspCASP solver in order to solve CASP programs arising from PDDL+ domains. An experimental analysis, performed on well-known linear and non-linear variants of PDDL+ domains, involving various configurations of theezcspsolver, other CASP solvers, and PDDL+ planners, shows the viability of our solution.

Answer Set Programming (ASP) is a declarative programming paradigm with roots in logic programming, knowledge representation, and non-monotonic reasoning. The ASP competition series aims at assessing and promoting the evolution of ASP systems and applications. Its growing range of challenging application-oriented benchmarks inspires and showcases continuous advancements of the state of the art in ASP.

This special issue of Fundamenta Informaticae publishes extended and revised versions of the best papers orally presented at the 22nd RCRA International Workshop (RCRA 2015). 1 This event follows the series of the RCRA (the working group of the AI*IA association on Knowledge Representation and Automated Reasoning) annual meetings, held since 1994, and that from 2007 became an international workshop.RCRA 2015 was held in Ferrara, Italy, on 22 September 2015 as a satellite workshop of the 14th Conference of the Italian Association for Artificial Intelligence (AI*IA 2015).The success of all these events shows that RCRA is nowadays established as a major forum for exchanging ideas and proposing experimentation methodologies for algorithms in Artificial Intelligence.

Answer Set Programming (ASP) is a logic programming, declarative, paradigm that was introduced in the late 1990s, based on the answer set semantics of logic programs proposed by Gelfond and Lifschitz a decade earlier.To date, ASP has been applied to a variety of domains and demonstrated its suitability for solving reasoning tasks such as knowledge-intensive tasks and combinatorial search problems.One direction of ASP research focuses on the development of efficient methods for computing answer sets.Novel techniques were initially adapted from SAT, then designed on purpose for ASP, e.g. to deal with specific ASP constructs, like aggregates, or to solve different reasoning tasks, such as cautious reasoning.More recently, ideas have been derived from the study of the relationship between ASP and other computing paradigms, such as constraint satisfaction, quantified Boolean formulas, first-order logic, pseudo-Boolean solvers, theorem provers, description logics, and external means of computation.The goal of this direction is to be able to cope more efficiently with practical problems, and to extend the domains that can be modeled and solved via ASP and its extensions.A recent, successful direction is CASP, which integrates ASP and constraint programming to solve problems with mixed discrete-continuous dynamics.The Answer Set Programming and Other Computing Paradigms (ASPOCP) series of workshops aims at fostering the cross-fertilization between ASP and other approaches by providing a venue for discussing advances in theory, solving techniques, and applications.Furthermore, the workshop encourages research that crosses the boundaries of ASP in other original directions, including action languages, probabilistic reasoning and machine learning, multi-agent and multi-context systems, argumentation frameworks and modularity.The ASPOCP workshop series has been held annually since its first edition in 2008 as a co-located event with the International Conference on Logic Programming (ICLP).The workshop has become an established event, as demonstrated by the considerable number of submissions and participants at each edition.The eighth edition of the workshop (ASPOCP 2015 1 ) was held in Cork, Ireland, on August 31st, 2015, as an affiliated event of the 31st ICLP meeting, which was part of "The Year of George Boole."Eleven papers were presented and the authors were invited to submit extended versions to be con-

Abstract Answer set programming is a declarative programming paradigm oriented towards difficult combinatorial search problems. A fundamental task in answer set programming is to compute stable models, i.e., solutions of logic programs. Answer set solvers are the programs that perform this task. The problem of deciding whether a disjunctive program has a stable model is ΣP2-complete. The high complexity of reasoning within disjunctive logic programming is responsible for few solvers capable of dealing with such programs, namely dlv, gnt, cmodels, clasp and wasp. In this paper, we show that transition systems introduced by Nieuwenhuis, Oliveras, and Tinelli to model and analyze satisfiability solvers can be adapted for disjunctive answer set solvers. Transition systems give a unifying perspective and bring clarity in the description and comparison of solvers. They can be effectively used for analyzing, comparing and proving correctness of search algorithms as well as inspiring new ideas in the design of disjunctive answer set solvers. In this light, we introduce a general template, which accounts for major techniques implemented in disjunctive solvers. We then illustrate how this general template captures solvers dlv, gnt, and cmodels. We also show how this framework provides a convenient tool for designing new solving algorithms by means of combinations of techniques employed in different solvers.

Problems arising in several areas of computer science have combinatorial nature. Solving these problems with reasonable performance is often both a challenging and crucial task, because feasible or...

The recent application of Machine Learning techniques to the Answer Set Programming (ASP) field proved to be effective. In particular, the multi-engine ASP solver me-asp is efficient: it is able to solve more instances than any other ASP system that participated to the 3rd ASP Competition on the ‘System Track’ benchmarks. In the me-asp approach, classification methods inductively learn offline algorithm selection policies starting from both a set of features of instances in a training set, and the solvers performance on such instances. In this article we present an improvement to the multi-engine framework of me-asp, in which we add the capability of updating the learned policies when the original approach fails to give good predictions. An experimental analysis, conducted on training and test sets of ground instances obtained from the ones submitted to the ‘System Track’ of the 3rd ASP Competition, shows that the policy adaptation improves the performance of me-asp when applied to test sets containing domains of instances that were not considered for training.

A fundamental task in answer set programming is to compute answer sets of logic programs. Answer set solvers are the programs that perform this task. The problem of deciding whether a disjunctive program has an answer set is ΣP2

Abstract Answer-set programming (ASP) is a truly declarative programming paradigm proposed in the area of non-monotonic reasoning and logic programming, which has been recently employed in many applications. The development of efficient ASP systems is, thus, crucial. Having in mind the task of improving the solving methods for ASP, there are two usual ways to reach this goal: (i) extending state-of-the-art techniques and ASP solvers or (ii) designing a new ASP solver from scratch. An alternative to these trends is to build on top of state-of-the-art solvers, and to apply machine learning techniques for choosing automatically the “best” available solver on a per-instance basis. In this paper, we pursue this latter direction. We first define a set of cheap-to-compute syntactic features that characterize several aspects of ASP programs. Then, we apply classification methods that, given the features of the instances in atrainingset and the solvers' performance on these instances, inductively learn algorithm selection strategies to be applied to atestset. We report the results of a number of experiments considering solvers and different training and test sets of instances taken from the ones submitted to the “System Track” of the Third ASP Competition. Our analysis shows that by applying machine learning techniques to ASP solving, it is possible to obtain very robust performance: our approach can solve more instances compared with any solver that entered the Third ASP Competition.

The introduction of aggregates has been one of the most relevant language extensions to Answer Set Programming (ASP). Aggregates are very expressive, they allow to represent many problems in a more succinct and elegant way compared to aggregate-free programs. A significant amount of research work has been devoted to aggregates in the ASP community in the last years, and relevant research results on ASP with aggregates have been published, on both theoretical and practical sides. The high expressiveness of aggregates (eliminating aggregates often causes a quadratic blow-up in program size) requires suitable evaluation methods and optimization techniques for an efficient implementation. Nevertheless, in spite of the above-mentioned research developments, aggregates are treated in a quite straightforward way in most ASP systems. In this paper, we explore the exploitation of look-back techniques for an efficient implementation of aggregates. We define a reason calculus for backjumping in ASP programs with aggregates. Furthermore, we describe how these reasons can be used in order to guide look-back heuristics for programs with aggregates. We have implemented both the new reason calculus and the proposed heuristics in the DLV system, and have carried out an experimental analysis on publicly available benchmarks which shows significant performance benefits.

Planning as Satisfiability is one of the most well-known and effective techniques for classical planning: satplan has been the winning system in the deterministic track for optimal planners in the 4th International Planning Competition (IPC) and a cowinner in the 5th IPC. Given a planning problem П and a makespan n, the approach based on satisfiability (a.k.a. SAT-based) simply works by (i) constructing a SAT formula П n and (ii) checking Ðn for satisfiability: if there is a model for П n then we have found a plan, otherwise n is increased. The approach guarantees that the makespan is optimal, i.e. minimum. In this article we extend the Planning as Satisfiability approach in order to handle preferences and satplan in order to solve problems with simple preferences. This allows, e.g. to take into consideration ‘plan quality’ issues other than makespan, like number of actions and ‘soft’ goals. The basic idea is to explore the search space of possible plans in accordance with the given partially ordered preferences.We first prove that, at fixed makespan, our approach returns an ‘optimal’ plan, if any. Then, considering both classical planning problems and problems coming from IPC-5, we show that satplan extended in order to deal with preferences: (i) returns optimal plans that are often of considerable better quality, i.e. with fewer actions or with a better plan metric on soft goals, than satplan; and (ii) is overall competitive, in terms of plan quality, with sgplan, the winning system in the ‘SimplePreferences’ category of the IPC-5. Notably, such results are often obtained without sacrificing efficiency.

The problem of expressing and solving satisfiability problems (SAT) with qualitative preferences is central in many areas of Computer Science and Artificial Intelligence. In previous papers, it has been shown that qualitative preferences on literals allow for capturing qualitative/quantitative preferences on literals/formulas; and that an optimal model for a satisfiability problems with qualitative preferences on literals can be computed via a simple modification of the Davis-Logemann-Loveland procedure (DLL): Given a SAT formula, an optimal solution is computed by simply imposing that DLL branches according to the partial order on the preferences. Unfortunately, it is well known that introducing an ordering on the branching heuristic of DLL may cause an exponential degradation in its performances. The experimental analysis reported in these papers hightlights that such degradation can indeed show up in the presence of a significant number of preferences.

Abstract. Answer Set Programming (ASP) and propositional satisfiability (SAT) are closely related. In some recent work we have shown that, on a wide set of logic programs called “tight”, the main search procedures used by ASP and SAT systems are equivalent, i.e., that they explore search trees with the same branching nodes. In this paper, we focus on the experimental evaluation of different search strategies, heuristics and their combinations that have been shown to be effective in the SAT community, in ASP systems. Our results show that, despite the strong link between ASP and SAT, it is not always the case that search strategies, heuristics and/or their combinations that currently dominate in SAT are also bound to dominate in ASP. We provide a detailed experimental evaluation for this phenomenon and we shed light on future development of efficient Answer Set solvers. 1