We present a general approach to planning with incomplete information in Answer Set Programming (ASP). More precisely, we consider the problems of conformant and conditional planning with sensing actions and assumptions. We represent planning problems using a simple formalism where logic programs describe the transition function between states, the initial states and the goal states. For solving planning problems, we use Quantified Answer Set Programming (QASP), an extension of ASP with existential and universal quantifiers over atoms that is analogous to Quantified Boolean Formulas (QBFs). We define the language of quantified logic programs and use it to represent the solutions to different variants of conformant and conditional planning. On the practical side, we present a translation-based QASP solver that converts quantified logic programs into QBFs and then executes a QBF solver, and we evaluate experimentally the approach on conformant and conditional planning benchmarks.

We present a generalisation of CPCES, a conformant planner that uses two procedures: candidate plan generation and sampling of the initial belief state. The new CPCES better distinguishes these two procedures and therefore provides a clearer framework for the resolution of conformant planning problems. We study CPCES theoretically by analysing the sampling phase through the lens of tags, width and basis. The benefit of this new interpretation is twofold: firstly it allows us to bound the maximum number of iterations required by CPCES, and second it allows us to individuate sampling strategies that guarantee the discovery of subsets of minimal bases. An experimental analysis reported in the paper shows that the greedy sampling (the original version of CPCES) is the more effective strategy, coverage wise. However, when either the quality of the plans or the size of the resulting samples is important a more sophisticated sampling is more effective.

Epistemic Specifications allow for the correct representation of incomplete information in the presence of multiple belief sets by expanding Answer Set Programming with modal operators $K$ and M. The meaning of M in the existing work does not correspond well to the principle of justifiedness accepted by the community. It is, however, challenging to characterize the justfiedness of each belief, due to the complexity introduced by M. We address this issue by identifying a belief set with a program which uniquely decides the belief set. This idea leads to a novel definition of the semantics of Epistemic Specifications which assures that each belief in any belief set is well justified.  We also show that conformant planning problems can be naturally represented by Epistemic Specification under our semantics.

We consider planning with uncertainty in the initial state as a case study of incremental quantified Boolean formula (QBF) solving. We report on experiments with a workflow to incrementally encode a planning instance into a sequence of QBFs. To solve this sequence of incrementally constructed QBFs, we use our general-purpose incremental QBF solver DepQBF. Since the generated QBFs have many clauses and variables in common, our approach avoids redundancy both in the encoding phase and in the solving phase. Experimental results show that incremental QBF solving outperforms non-incremental QBF solving. Our results are the first empirical study of incremental QBF solving in the context of planning and motivate its use in other application domains.

Many practical planning problems necessitate the generation of a plan under incomplete information about the state of the world. In this paper we propose the notion of Assumption-Based Planning. Unlike conformant planning, which attempts to find a plan under all possible completions of the initial state, an assumption-based plan supports the assertion of additional assumptions about the state of the world, often resulting in high quality plans where no conformant plan exists. We are interested in this paradigm of planning for two reasons: 1) it captures a compelling form of \emph{commonsense planning}, and 2) it is of great utility in the generation of explanations, diagnoses, and counter-examples -- tasks which share a computational core with We formalize the notion of assumption-based planning, establishing a relationship between assumption-based and conformant planning, and prove properties of such plans. We further provide for the scenario where some assumptions are more preferred than others. Exploiting the correspondence with conformant planning, we propose a means of computing assumption-based plans via a translation to classical planning. Our translation is an extension of the popular approach proposed by Palacios and Geffner and realized in their T0 planner. We have implemented our planner, A0, as a variant of T0 and tested it on a number of expository domains drawn from the International Planning Competition. Our results illustrate the utility of this new planning paradigm.

For a given problem, the optimal Markov policy can be considerred as a conditional or contingent plan containing a (potentially large) number of branches. Unfortunately, there are applications where it is desirable to strictly limit the number of decision points and branches in a plan. For example, it may be that plans must later undergo more detailed simulation to verify correctness and safety, or that they must be simple enough to be understood and analyzed by humans. As a result, it may be necessary to limit consideration to plans with only a small number of branches. This raises the question of how one goes about finding optimal plans containing only a limited number of branches. In this paper, we present an any-time algorithm for optimal k-contingency planning (OKP). It is the first optimal algorithm for limited contingency planning that is not an explicit enumeration of possible contingent plans. By modelling the problem as a Partially Observable Markov Decision Process, it implements the Bellman optimality principle and prunes the solution space. We present experimental results of applying this algorithm to some simple test cases.

Many practical planning problems necessitate the generation of a plan under incomplete information about the state of the world. In this paper we propose the notion of Assumption-Based Planning. Unlike conformant planning, which attempts to find a plan under all possible completions of the initial state, an assumption-based plan supports the assertion of additional assumptions about the state of the world, simplifying the planning problem. In many practical settings, such plans can be of higher quality than conformant plans. We formalize the notion of assumption-based planning, establishing a relationship between assumption-based and conformant planning, and prove properties of such plans. We further provide for the scenario where some assumptions are more preferred than others. Exploiting the correspondence with conformant planning, we propose a means of computing assumption-based plans via a translation to classical planning. Our translation is an extension of the popular approach proposed by Palacios and Geffner and realized in their T0 planner. We have implemented our planner, A0, as a variant of T0 and tested it on a number of expository domains drawn from the International Planning Competition. Our results illustrate the utility of this new planning paradigm.

The paper introduces a novel technique for improving the performance and scalability of best-first progression-based conformant planners. The technique is inspired by different well-known techniques from classical planning, such as landmark and stratification. Its most salient feature is that it is relatively cheap to implement yet quite effective when applicable. The effectiveness of the proposed technique is demonstrated by the development of new conformant planners by integrating the technique in various state-of-the-art conformant planners and an extensive experimental evaluation of the new planners using benchmarks collected from various sources. The result shows that the technique can be applied in several benchmarks and helps improve both performance and scalability of conformant planners.

Planning under uncertainty is one of the most general and hardest problems considered in the area of planning. Uncertainty can take the form of incomplete information, wrong information, multiple action outcomes, and varying action durations. My doctoral thesis concentrates on planning with incomplete knowledge and multiple action outcomes, specifically conformant planning and contingent planning. These problems have attracted the attention of many researchers, resulting in numerous sophisticated planners of different approaches. However, those planners cannot scale up well on the size of problems, mostly due to the representation methods employed in the planners. The doctoral research work provides a systematic methodology for dealing with planning under uncertainty, focusing on the representation of belief states that can be used in a forward search paradigm in the belief space for solutions. A good representation should be compact so that a planner implementing it can perform and scale up well as the larger the formulae, the more the computation and the more the memory consumption (i.e., the slower the system and the less the scalability). On the other hand, it should also have properties that allow for definition of an efficient transition function for computing successor belief states, e.g., checking satisfaction in a DNF formula is easy. Defining a direct complete transition function in presence of incomplete information for a general representation, other than the belief state, is particularly hard due to conditional action effects. To address this, I propose a generic abstract algorithm, called GAA, for defining such function given an arbitrary representation. Using the GAA algorithm, my doctoral thesis investigates the properties of different logical formulae and their applicability in planning under uncertainty as a belief state representation. The results obtained so far are very promissing as the research work developed several highly competitive planners which outperform other state-of-the-art planners in most benchmarks available in the literature.

We tackle the problem of planning in nondeterministic domains, by presenting a new approach to conformant planning. Conformant planning is the problem of finding a sequence of actions that is guaranteed to achieve the goal despite the nondeterminism of the domain. Our approach is based on the representation of the planning domain as a finite state automaton. We use Symbolic Model Checking techniques, in particular Binary Decision Diagrams, to compactly represent and efficiently search the automaton. In this paper we make the following contributions. First, we present a general planning algorithm for conformant planning, which applies to fully nondeterministic domains, with uncertainty in the initial condition and in action effects. The algorithm is based on a breadth-first, backward search, and returns conformant plans of minimal length, if a solution to the planning problem exists, otherwise it terminates concluding that the problem admits no conformant solution. Second, we provide a symbolic representation of the search space based on Binary Decision Diagrams (BDDs), which is the basis for search techniques derived from symbolic model checking. The symbolic representation makes it possible to analyze potentially large sets of states and transitions in a single computation step, thus providing for an efficient implementation. Third, we present CMBP (Conformant Model Based Planner), an efficient implementation of the data structures and algorithm described above, directly based on BDD manipulations, which allows for a compact representation of the search layers and an efficient implementation of the search steps. Finally, we present an experimental comparison of our approach with the state-of-the-art conformant planners CGP, QBFPLAN and GPT. Our analysis includes all the planning problems from the distribution packages of these systems, plus other problems defined to stress a number of specific factors. Our approach appears to be the most effective: CMBP is strictly more expressive than QBFPLAN and CGP and, in all the problems where a comparison is possible, CMBP outperforms its competitors, sometimes by orders of magnitude.