A fast incremental algorithm for maintaining dispatchability of partially controllable plans

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.