Using a Classical Forward Search to Solve Temporal Planning Problems under Uncertainty

Planning with action concurrency under time and resources constraints and uncertainty is a challenging problem. Current approaches which rely on Markov Decision Processes and a discrete model for time and resources are limited by a blow-up of the search state-space. This paper presents a planner which is based on a classical forward search for solving this kind a problems. A continuous model is used for time and resources. The uncertainty on time is represented by continuous random variables which are organized in a dynamically generated Bayesian network. Two versions of the ActuPlan planner are presented. As a first step, ActuPlan_nc performs a forward-search in an augmented state-space to generate epsilon-optimal nonconditional plans which are robust to uncertainty (threshold on the probability of success). ActuPlan_nc is then adapted to generate a set of nonconditional plans which are characterized by different trade-offs between their probability of success and their expected cost. ActuPlan, the second version, builds a conditional plan with a lower expected cost by merging previously generated nonconditional plans. The branches are built by conditioning on the time. Empirical experimentation on standard benchmarks demonstrates the effectiveness of the approach.