Conformant Planning via Symbolic Model Checking

By William W. Cohen, Robert E. Schapire, Yoram Singer. Journal of Artificial Intelligence Research, 2000

952 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/ccb8ee05179cbefd047f48e766cf1bf1188351ab

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Bipartite Ranking through Minimization of Univariate Loss (2011, methodology): “We start by reducing the ranking problem to a classification problem in a typical way (Cohen et al., 1999; Balcan et al., 2008; Ailon & Mohri, 2008; Herbrich et al., 1999).”
RADAR - A Proactive Decision Support System for Human-in-the-Loop Planning (2017, background): “Once the ﬁre chief selects a goal, RADAR generates the problem ﬁle and displays the landmarks (Hoffmann, Porteous, and Sebastia 2004) to help the user be on track to achieve the goal.”
Large Margin Methods for Structured and Interdependent Output Variables (2005, background): “The same is true also for other ranking algorithms (Cohen et al., 1999; Herbrich et al., 2000; Schapire and Singer, 2000; Crammer and Singer, 2002; Joachims, 2002).”
Post Classification Label Refinement Using Implicit Ordering Constraint Among Data Instances (2015, methodology): “The performance of BC and PB is very similar because in PB the difference of weights of incoming and outgoing edges in a location [8] are loosely related to the amount of water in the location.”
Learning Bayesian networks: approaches and issues (2011, background): “Some of the newest work is by Cheng and Druzdzel (2000, 2001) with their AIS-BN system, which has good performance characteristics across a wide range of classes, guaranteed bounds on inferred probabilities and a simple stopping rule.”
Bayesian Artificial Intelligence (2004, methodology): “0 provides more recent stateof-the-art sampling algorithms, AIS-BN [43] and EPIS-BN [304].”
Bayesian network modeling of correlated random variables drawn from a Gaussian random field (2011, neutral): “[14,15].”
A review of generalized planning (2019, background): “With this regard, planning landmarks can be an interesting research direction [40].”
A Universal Marginalizer for Amortized Inference in Generative Models (2017, methodology): “We therefore must resort to approximate methods such as variational inference [Wainwright et al., 2008] and Monte Carlo methods, e.g., importance sampling [Cheng and Druzdzel, 2000, Neal, 2001].”
A comparative study of artificial intelligence and human doctors for the purpose of triage and diagnosis (2018, background): “Given a set of userentered presenting symptoms and risk-factors, the model infers the most likely conditions and generates follow-up questions [4, 5, 6, 7].”
Noncompensatory/nonlinear composite indicators for ranking countries: a defensible setting (2009, methodology): “…have been proposed in the literature; are mainly heuristics based on artificial intelligence, branch and bound approaches and multi-stage techniques (see e.g., Barthelemy et al., 1989; Charon et al., 1997; Cohen et al., 1999; Davenport and Kalagnanam, 2004; Dwork et al., 2001; Truchon, 1998b).”
Learning, planning, and control for quadruped locomotion over challenging terrain (2011, background): “This corresponds to the widely studied rank learning or preference learning problem in the machine learning literature (Cohen et al. 1999).”
Plan Recognition as Planning (2009, background): “The Landmark problem is known to be Pspace–complete (Hoffmann et al., 2004) even when formulas are restricted to size 1, e.”