Multi-Valued Partial Order Plans in Numeric Planning
This work addresses a foundational problem in AI planning for researchers, providing incremental theoretical insights into decidable fragments of numeric planning.
The paper tackles the undecidability problem in numeric planning formalisms that mix numeric with Boolean effects by analyzing action occurrences and reformulating restricted tasks as search problems, resulting in the identification of an NP-complete fragment using heuristics and the development of multi-valued partial order plans as a compact representation.
Many planning formalisms allow for mixing numeric with Boolean effects. However, most of these formalisms are undecidable. In this paper, we will analyze possible causes for this undecidability by studying the number of different occurrences of actions, an approach that proved useful for metric fluents before. We will start by reformulating a numeric planning problem known as restricted tasks as a search problem. We will then show how an NP-complete fragment of numeric planning can be found by using heuristics. To achieve this, we will develop the idea of multi-valued partial order plans, a least committing compact representation for (sequential and parallel) plans. Finally, we will study optimization techniques for this representation to incorporate soft preconditions.