Monitoring the Execution of Partial Order Plans via Regression
Christian Muise, Sheila McIlraith and Chris Beck
Partial-order plans (POPs) have an inherent form of robustness due to the number of linearizations a POP can represent. This robustness can be exploited to maximal advantage through effective execution monitoring. Here we address the problem of POP execution monitoring for precisely this purpose. Building on the classical notion of goal regression, we characterize the conditions under which a POP remains viable by relating these conditions to a notion of regression extended to deal with POPs. Exploiting this characterization, we develop a method for POP execution monitoring via a structured policy, expressed as an ordered algebraic decision diagram. When used for execution monitoring, the policy enables an agent to seamlessly switch between POP linearizations to accommodate unexpected changes in system state. We demonstrate the effectiveness of our approach by comparing it, both empirically and analytically, with a standard technique for execution monitoring of sequential plans. On POPs that have few ordering constraints among actions, robustness gains (as measured by the number of states for which the plan is viable) can be exponentially large. On IPC domains, where there are numerous ordering constraints, our approach is still 2 to 17 times faster and up to 2.5 times more robust.