Angelic Semantics for High-Level Actions

High-level actions (HLAs) lie at the heart of hierarchical planning. Typically, an HLA admits multiple refinements into primitive action sequences. Correct descriptions of the effects of HLAs may be essential to their effective use, yet the literature is mostly silent. We propose an angelic seman-tics for HLAs, the key concept of which is the set of states reachable by some refinement of a high-level plan, represent-ing uncertainty that will ultimately be resolved in the plan-ning agent’s own best interest. We describe upper and lower approximations to these reachable sets, and show that the re-sulting definition of a high-level solution automatically sat-isfies the upward and downward refinement properties. We define a STRIPS-like notation for such descriptions. A sound and complete hierarchical planning algorithm is given and its computational benefits are demonstrated