A Native Qualitative Numeric Planning Solver Based on AND/OR Graph Search

Hemeng Zeng, Yikun Liang, Yongmei LiuIJCAI 2022 · DOI

TL;DR

This paper introduces DSET, a novel solver for Qualitative Numeric Planning (QNP) problems that directly searches an AND/OR graph representation of the problem. DSET significantly outperforms existing compilation-based methods in terms of speed and memory usage, especially for unsolvable problems, by avoiding the exponential blow-up in problem size.

What Problem Does This Paper Address?

Classical AI planning deals with finding sequences of actions to achieve goals. Qualitative Numeric Planning (QNP) extends this by introducing non-negative real-valued variables that can be arbitrarily increased or decreased by actions. This allows modeling problems with loops where actions might need to be repeated an unknown number of times. Existing QNP solvers primarily rely on compiling QNP problems into other planning formalisms like Fully Observable Non-deterministic Planning (FOND) or FOND+. However, these compilation approaches often lead to a massive increase in the problem size (variables and actions), making them computationally expensive and inefficient. This paper aims to address this inefficiency by developing a "native" solver that tackles QNP problems directly without relying on such compilations.

Methods

The core of this paper is the development of a native QNP solver called DSET. Instead of compiling QNP problems, DSET works by:

  • AND/OR Graph Representation: It models the state space of a QNP problem as an AND/OR graph. Nodes in this graph represent "qualitative states" (assignments of literals to variables), and connectors represent actions.
  • Direct Subgraph Search: DSET searches for a specific type of subgraph within this AND/OR graph. This subgraph must be "closed" (every non-goal node has exactly one outgoing connector) and "terminating" (all paths starting from any node eventually reach a goal node). This characterization of a solution is simpler than previous approaches.
  • Pruning Strategy: A key innovation is the use of a termination test (based on the SIEVE algorithm) to prune non-terminating subgraphs early. The paper leverages the observation that any extension of a non-terminating policy is also non-terminating. This prevents the solver from exploring large branches of the search space that are guaranteed not to lead to a solution.
  • Backtracking: When a path is found to be non-terminating or leads to a dead end (no goal node reachable), the algorithm backtracks to explore alternative paths.

Datasets

The paper evaluates DSET on several benchmark domains commonly used in QNP research:

  • ChoppingTree, Nest2, Nest3, ShovelingSnow (from Srivastava et al., 2011)
  • BlocksOn, Delivery1, Delivery2, Delivery3, Gripper1, Nest2, Nest3, Nest10 (from Bonet et al., 2019 and Bonet and Geffner, 2020)
  • Logistics1, Logistics2 (newly designed domains to test scalability)
  • Unsolvable versions of some domains (Nest3u, Nest10u, Gripper1u) were created to test the solver's ability to identify unsolvable problems.
  • Additionally, 500 randomly generated QNP problems were used to evaluate the impact of the pruning strategy.

Key Insights and Ideas

  • Simpler Solution Characterization: The paper proposes a more straightforward definition of a QNP solution: a closed and terminating policy (represented as a subgraph) that contains a goal node. This simplifies the search objective.
  • The Power of Pruning: The observation that extending a non-terminating policy always results in a non-terminating policy is crucial. This insight enables an effective pruning strategy, significantly reducing the search space compared to methods that only verify termination at the end.
  • Native Solver Advantage: Directly searching the QNP problem's state space (AND/OR graph) avoids the exponential overhead introduced by compiling to FOND problems, leading to substantial performance gains.

Key Results

  • Speedup: DSET is significantly faster than compilation-based approaches (FOND-SAT and PRP) on solvable QNP problems, achieving speedups of "one order of magnitude" or more.
  • Unsolvable Problems: For unsolvable QNP problems, DSET returns "Unsolvable" in seconds, whereas compilation-based solvers often time out or take extremely long.
  • Policy Size: DSET generally returns policies with a smaller size (fewer qstate-action pairs), indicating more succinct solutions.
  • Comparability: DSET's performance is comparable to the FOND+ solver FOND-ASP, which also works with a similar state space.

Limitations and Future Work

  • Scalability: While DSET outperforms compilation methods, it is described as a "naive enumeration method" and suffers from scalability issues on very large or complex domains (e.g., the Logistic2 domain).
  • Heuristic Search: The authors plan to improve DSET's scalability by incorporating heuristic search techniques.
  • Restricted Numeric Changes: Future work also includes extending the approach to handle QNP problems where numeric variables are increased or decreased by restricted amounts, which could serve as better abstraction models for generalized planning.

Summary updated

BibTeX
@inproceedings{zeng2022native,
  author = {Hemeng Zeng and Yikun Liang and Yongmei Liu},
  title = {{A Native Qualitative Numeric Planning Solver Based on AND/OR Graph Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/651},
}
Figure