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

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

Hemeng Zeng, Yikun Liang, Yongmei Liu

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 4693-4700. https://doi.org/10.24963/ijcai.2022/651

Qualitative numeric planning (QNP) is classical planning extended with non-negative real variables that can be increased or decreased by some arbitrary amount. Existing approaches for solving QNP problems are exclusively based on compilation to fully observable nondeterministic planning (FOND) problems or FOND+ problems, i.e., FOND problems with explicit fairness assumptions. However, the FOND-compilation approaches suffer from some limitations, such as difficulties to generate all strong cyclic solutions for FOND problems or introducing a great many extra variables and actions. In this paper, we propose a simpler characterization of QNP solutions and a new approach to solve QNP problems based on directly searching for a solution, which is a closed and terminating subgraph that contains a goal node, in the AND/OR graphs induced by QNP problems. Moreover, we introduce a pruning strategy based on termination tests on subgraphs. We implemented a native solver DSET based on the proposed approach and compared the performance of it with that of the two compilation-based approaches. Experimental results show that DSET is faster than the FOND-compilation approach by one order of magnitude, and comparable with the FOND+-compilation approach.
Keywords:
Planning and Scheduling: Planning Algorithms
Planning and Scheduling: Planning under Uncertainty