Integrating Planning and Execution in Stochastic Domains

We investigate planning in time-critical domains represented as Markov Decision Processes. To reduce the computational cost of the algorithm we execute actions as we construct the plan, and sacrifice optimality by searching to a fixed depth and using a heuristic function to estimate the value of states. Although this paper concentrates on the search procedure, we also discuss ways of constructing heuristic functions that are suitable for this approach.