Qualitative Numeric Planning

Siddharth Srivastava, Shlomo Zilberstein, Neil Immerman, and Hector Geffner. Qualitative Numeric Planning. Proceedings of the Twenty-Fifth Conference on Artificial Intelligence (AAAI), 1010-1016, San Francisco, California, 2011.

Abstract

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 generate-and-test planner to illustrate these findings.

Bibtex entry:

@inproceedings{SZIGaaai11,
  author        = {Siddharth Srivastava and Shlomo Zilberstein and Neil Immerman 
                   and Hector Geffner},
  title		= {Qualitative Numeric Planning},
  booktitle     = {Proceedings of the Twenty-Fifth Conference on
		   Artificial Intelligence},
  year		= {2011},
  pages		= {1010-1016},
  address       = {San Francisco, California},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/SZIGaaai11.html}
}

shlomo@cs.umass.edu