Counter-Example Based Planning Under Uncertainty

Abstract

Planning under uncertainty broadly involves finding a plan for an agent acting in an uncertain environment. Conformant Planning (CP) and Probabilistic Conformant Planning (PCP) are two specific and related planning problems that involve uncertainty. In CP, an agent that is unable to observe the environment must find a plan that achieves its goal under a qualitatively uncertain initial state. CP can involve uncertainty either in the initial state alone or in both the initial state and the action effects. PCP features quantitative uncertainty, extending CP by introducing a probability distribution over the initial state, requiring the goal to be reached with at least a given probability threshold.

A key milestone in the development of CP algorithms was by Grastien and Scala (2020). This thesis first explores three methods to improve the runtime performance of the CPCES algorithm. The first identifies certain facts, whose values remain known with certainty during the plan execution. Certain facts are represented explicitly in the classical abstraction. Merging certain facts substantially reduces the size of the classical abstraction, thereby lowering the cost of reasoning over it. The second, warm-starting CPCES, identifies "important initial states" before commencement of iterative refinement, enabling CPCES to sometimes find a valid plan immediately, or converge in fewer iterations. The third integrates the Fast Downward System (Helmert 2006) into CPCES, developing a bespoke stratified compilation approach for synthesizing successive classical abstractions. Experimental results show that all three methods significantly improve CPCES efficiency.

Moving our attention to quantitative uncertainty, we reimagine CPCES to develop a counter-example driven algorithm to solve PCP. Like CPCES, our approach iteratively searches for candidate plans via a classical abstraction, and then counter-examples for such plans. Instead of using a single initial state as a counter-example, we introduce counter-tags, a concept that enables the algorithm to reason over succinct representations of sets of initial states. Our algorithm searches over counter-tags, computing their probabilities efficiently by using a d-DNNF representation of discrete probability distributions. We call our algorithm p-CPCES. To address the challenge of disjunctive goals posed by classical abstractions encountered using p-CPCES, we further develop a hitting set approach to eliminate disjunctive goals from classical abstractions, thereby removing the need for classical planners capable of handling such goals. This enhanced version of the algorithm is called p-CPCES-hit. Experiments show p-CPCES-hit outperforms the state-of-the-art PCP planner Probabilistic-FF (Domshlak and Hoffmann 2006, 2007). The good performance of p-CPCES-hit is particularly pronounced on complex problems, where it is faster than the incumbent algorithms.

Work performed by p-CPCES is amenable to acceleration by exploiting parallel computation. We introduce parallel-CPCES, a multi-core approach to solving PCP. The p-CPCES-hit algorithm involves three sequential steps per iteration: (1) solving counter-tags, (2) computing their probabilities, and (3) solving for a candidate plan using a classical abstraction. Any step can become a bottleneck if it takes too long, and parallel execution mitigates this issue. We implement a framework combining p-CPCES-hit, a database, and a file system, where results from any stage are stored in a database, and tasks communicate efficiently via the file system. Each stage is executed on multiple CPUs to improve efficiency. Additionally, we introduce a new hitting set strategy highly suited to our parallel setting to further enhance planning performance. Experimental results confirm that parallel-CPCES finds solutions faster than p-CPCES-hit, with speed improving as more workers (i.e., CPUs) are added. Show more