Paul H. Morris, Nicola Muscettola
An important issue for temporal planners is the ability to handle temporal uncertainty. We revisit the question of how to determine whether a given set of temporal requirements are feasible in the light of uncertain durations of some processes. In particular, we consider how best to determine whether a network is Dynamically Controllable, i.e., whether a dynamic strategy exists for executing the network that is guaranteed to satisfy the requirements. Previous work has shown the existence of a pseudo-polynomial algorithm for testing Dynamic Controllability. Here, we simplify the previous framework, and present a strongly polynomial algorithm with a termination criterion based on the structure of the network.
Content Area: 16. Planning and Scheduling
Subjects: 3.6 Temporal Reasoning; 15.2 Constraint Satisfaction
Submitted: May 10, 2005