Tech Report CS-94-44

Predicting Real-Time Planner Preformance by Domain Characterization

Jak Kirman

October 1994

Abstract:

There is a large class of problems that involve real-time planning and execution in stochastic domains. Classical solutions either ignore the random element while planning and then modify the plan to deal with failures, or compute the best action to perform in any circumstance. These solutions are often either too brittle or too expensive computationally. I present an approach that interleaves planning and execution and reduces the set of circumstances that need to be considered at a given time. In previous work with other researchers I have shown that this approach is practical for some stochastic problems, but left open the question of which problems the approach can be applied to effectively. I present a classification of real-time stochastic decision problems that allows the prediction of the performance of this planning system (and others) without resorting to exhaustive empirical performance estimation. For a number of such planning problems, I present results showing the correlation between the predicted performance and the actual performance as estimated empirically.

(complete text in pdf or gzipped postscript)