Bhaskara Marthi and Stuart J. Russell and Jason Wolfe

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2007-89

July 10, 2007

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-89.pdf

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 semantics for HLAs, the key concept of which is the set of states reachable by some refinement of a high-level plan, representing uncertainty that will ultimately be resolved in the planning agent's own best interest. We describe upper and lower approximations to these reachable sets, and show that the resulting definition of a high-level solution automatically satisfies 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. This is an extended version of a paper by the same name appearing in ICAPS '07.

---

BibTeX citation:

@techreport{Marthi:EECS-2007-89,
    Author= {Marthi, Bhaskara and Russell, Stuart J. and Wolfe, Jason},
    Title= {Angelic Semantics for High-Level Actions},
    Year= {2007},
    Month= {Jul},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-89.html},
    Number= {UCB/EECS-2007-89},
    Abstract= {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 semantics for HLAs, the key concept of which is the set of states reachable by some refinement of a high-level plan, representing uncertainty that will ultimately be resolved in the planning agent's own best interest.  We describe upper and lower approximations to these reachable sets, and show that the resulting definition of a high-level solution automatically satisfies 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.  This is an extended version of a paper by the same name appearing in ICAPS '07.},
}

EndNote citation:

%0 Report
%A Marthi, Bhaskara 
%A Russell, Stuart J. 
%A Wolfe, Jason 
%T Angelic Semantics for High-Level Actions
%I EECS Department, University of California, Berkeley
%D 2007
%8 July 10
%@ UCB/EECS-2007-89
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-89.html
%F Marthi:EECS-2007-89