Enabling fast flexible planning through incremental temporal reasoning

In order for an autonomous agent to successfully complete its mission, the agent must be able to quickly re-plan on the fly, as unforeseen events arise in the environment. This is enabled through the use of temporally flexible plans, which allow the agent to adapt to execution uncertainties, by not over committing to timing constraints, and through continuous planners, which are able to replan at any point when the current plan fails. To achieve both of these requirements, planners must have the ability to reason quickly about timing constraints. We enable continuous, temporally flexible planning through a temporal consistency algorithm (ITC), which supports incremental consistency testing on a new type of disjunctive temporal constraint network, the Temporal Plan Network (TPN), and supports focused search through incremental conflict extraction. The ITC algorithm combines the speed of shortest-path algorithms known to network optimization with the spirit of incremental algorithms such as Incremental A * and those used within truth maintenance systems (TMS). Empirical studies of ITC applied to the Kirk temporal planner demonstrate an order of magnitude speed increase on cooperative air vehicle scenarios and on randomly generated plans