AAAI Publications, Fourth Annual Symposium on Combinatorial Search

Font Size: 
Planning in Domains with Cost Function Dependent Actions
Mike Phillips, Maxim Likhachev

Last modified: 2011-07-05


In a number of graph search-based planning problems, the value of the cost function that is being minimized also affects the set of possible actions at some or all the states in the graph. In such planning problems, the cost function typically becomes one of the state variables thereby increasing the dimensionality of the planning problem, and consequently the size of the graph that represents the problem. In this paper, we show how to avoid this increase in the dimensionality for weighted search (with bounded suboptimality) whenever the availability of the actions is monotonically non-increasing with the increase in the cost function.


weighted search; bounded sub-optimality; cost function dependent actions

Full Text: PDF