Qualitative Numeric Planning

We consider a new class of planning problems involving a set of non-negative real variables, and a set of non-deterministic actions that increase or decrease the values of these variables by some arbitrary amount. The formulas specifying the initial state, goal state, or action preconditions can only assert whether certain variables are equal to zero or not. Assuming that the state of the variables is fully observable, we obtain two results. First, the solution to the problem can be expressed as a policy mapping qualitative states into actions, where a qualitative state includes a Boolean variable for each original variable, indicating whether its value is zero or not. Second, testing whether any such policy, that may express nested loops of actions, is a solution to the problem, can be determined in time that is polynomial in the qualitative state space, which is much smaller than the original infinite state space. We also report experimental results using a simple generateand-test planner to illustrate these findings.

Authors

• Siddharth Srivastava Arizona State University
• Shlomo Zilberstein University of Massachusetts Amherst
• Neil Immerman University of Massachusetts, Amherst
• Hector Geffner Rheinisch Westfälische Technische Hochschule Aachen

Keywords

No keywords are indexed for this paper.