Temporally and spatially flexible plan execution for dynamic hybrid systems

Planners developed in the Artificial Intelligence community assume that tasks in the task plans they generate will be executed predictably and reliably. This assumption provides a useful abstraction in that it lets the task planners focus on what tasks should be done, while lower-level motion planners and controllers take care of the details of how the task should be performed. While this assumption is useful in many domains, it becomes problematic when controlling physically embedded systems, where there are often delays, disturbances, and failures. The task plans do not provide enough information about allowed flexibility in task duration and hybrid state evolution. Such flexibility could be useful when deciding how to react to disturbances. An important domain where this gap has caused problems is robotics, particularly, the operation of robots in unstructured, uncertain environments. Due to the complexity of this domain, the demands of tasks to be performed, and the actuation limits of robots, knowledge about permitted flexibility in execution of a task is crucial. We address this gap through two key innovations. First, we specify a Qualitative State Plan (QSP), which supports representation of spatial and temporal flexibility with respect to tasks. Second, we extend compilation approaches developed for temporally flexible execution of discrete activity plans to work with hybrid discrete/continuous systems using a recently developed Linear Quadratic Regulator synthesis algorithm, which performs a state reachability analysis to prune infeasible trajectories, and which determines optimal control policies for feasible state regions. The resulting Model-based Executive is able to take advantage of spatial and temporal flexibility in a QSP to improve handling of disturbances. Note that in this work, we focus on execution of QSPs, and defer the problem of how they are generated. We believe the latter could be accomplished through extensions to existing task planners.