A Fast Incremental Algorithm for Maintaining Dispatchability of Partially Controllable Plans

TitleA Fast Incremental Algorithm for Maintaining Dispatchability of Partially Controllable Plans
Publication TypeConference Proceedings
Year of Conference2007
AuthorsShah, J. A., J. Stedl, B. Williams, and P. Robertson
Conference NameProceedings of the International Conference on Automated Planning and Scheduling (32% acceptance rate)
Date Published09/2007
Abstract

Autonomous systems operating in real-world environments
must be able to plan, schedule, and execute missions while
robustly adapting to uncertainty and disturbances. Previous
work on dispatchable execution increases the efficiency of
plan execution under uncertainty by introducing a temporal
plan dispatcher that schedules events dynamically in
response to disturbances, and a compiler that reduces a plan
to a dispatchable form that enables real-time scheduling.
However, this work does not address the situation where
response requires modifying the plan in real-time. In these
situations, after the autonomous system replans, compilation
to dispatchable form must occur in near real-time.

The key contribution of this paper is a fast Incremental
Dynamic Control algorithm (IDC) for maintaining the
dispatchability of a partially controllable plan, in response
to incremental plan modifications by an online planner.
IDC is developed as a set of incremental update rules that
exploit the structure of the plan in order to efficiently
propagate the effects of constraint loosening and tightening
throughout the plan. IDC exhibits an order of magnitude
improvement in compile time over the state of the art nonincremental
algorithm applied to randomly generated
problems. Its practicality is demonstrated on plans for
coordinating rovers within the authors’ hardware test-bed.