AAAI Publications, Twenty-Ninth AAAI Conference on Artificial Intelligence

Font Size: 
Strong Temporal Planning with Uncontrollable Durations: A State-Space Approach
Alessandro Cimatti, Andrea Micheli, Marco Roveri

Last modified: 2015-03-04

Abstract


In many practical domains, planning systems are required to reason about durative actions. A common assumption in the literature is that the executor is allowed to decide the duration of each action. However, this assumption may be too restrictive for applications. In this paper, we tackle the problem of temporal planning with uncontrollable action durations. We show how to generate robust plans,that guarantee goal achievement despite the uncontrollability of the actual duration of the actions. We extend the state-space temporalplanning framework, integrating recent techniques for solving temporalproblems under uncertainty. We discuss different ways of lifting the total order plans generated by the heuristic search to partial orderplans, showing (in)completeness results for each of them. We implemented our approach on top of COLIN, a state-of-the-art planner. An experimental evaluation over several benchmark problems shows the practical feasibility of the proposed approach.

Keywords


Temporal Planning with Uncontrollable Durations; Temporal uncertainty; Temporal Planning; Temporal Problems

Full Text: PDF