Solving Temporally-Cyclic Planning Problems

In order to correctly model certain real-world planning problems, it is essential to take into account time. This is the case for problems requiring the concurrent execution of actions (known as temporally-expressive problems). However, we show in this paper that certain existing planners which solve this type of problem are, in fact, incomplete. They cannot guarantee to find a solution to a problem involving sets of cyclically-dependent actions (which we call temporally-cyclic problems). We characterize those temporal planning languages which can express temporally-cyclic problems. We also present a polynomial-time algorithm which transforms a temporally-cyclic problem into an equivalent acyclic problem. Applying our transformation restores the completeness of these temporal planners.

Authors

• Martin C. Cooper
• Frederic Maris
• Pierre Régnier

Keywords

• Planning
• Transforms
• Search problems
• Taxonomy
• Concurrent computing
• Production
• Cognition
• Planning Problem
• Types Of Problems
• Action Execution
• Duration Of Action
• Simple Example
• Temporal Gap
• Temporal Constraints
• Set Of Propositions
• Action Instances
• Problem Transformation
• Causal Graph
• Instantaneous Activity
• time
• temporally-cyclic