Bhaskara Marthi and Stuart J. Russell and Jason Wolfe

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2009-122

August 22, 2009

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-122.pdf

High-level actions (HLAs) are essential tools for coping with the large search spaces and long decision horizons encountered in real-world decision making. In a recent paper, we proposed an "angelic" semantics for HLAs that supports proofs that a high-level plan will (or will not) achieve a goal, without first reducing the plan to primitive action sequences. This paper extends the angelic semantics with cost information to support proofs that a high-level plan is (or is not) optimal. We describe the Angelic Hierarchical A* algorithm, which generates provably optimal plans, and show its advantages over alternative algorithms. We also present the Angelic Hierarchical Learning Real-Time A* algorithm for situated agents, one of the first algorithms to do hierarchical lookahead in an online setting. Since high-level plans are much shorter, this algorithm can look much farther ahead than previous algorithms (and thus choose much better actions) for a given amount of computational effort. This is a revised, extended version of a paper by the same name appearing in ICAPS '08.

---

BibTeX citation:

@techreport{Marthi:EECS-2009-122,
    Author= {Marthi, Bhaskara and Russell, Stuart J. and Wolfe, Jason},
    Title= {Angelic Hierarchical Planning: Optimal and Online Algorithms (Revised)},
    Year= {2009},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-122.html},
    Number= {UCB/EECS-2009-122},
    Abstract= {High-level actions (HLAs) are essential tools for coping with the large search spaces and long decision horizons encountered in real-world decision making. In a recent  paper, we proposed an "angelic" semantics for HLAs that supports proofs that a high-level plan will (or will not) achieve a goal, without first reducing the plan to primitive action sequences. This paper extends the angelic semantics with cost information to support proofs that a high-level plan is (or is not) optimal. We describe the Angelic Hierarchical A* algorithm, which generates provably optimal plans, and show its advantages over alternative algorithms. We also present the Angelic Hierarchical Learning Real-Time A* algorithm for situated agents, one of the first algorithms to do hierarchical lookahead in an online setting. Since high-level plans are much shorter, this algorithm can look much farther ahead than previous algorithms (and thus choose much better actions) for a given amount of computational effort. This is a revised, extended version of a paper by the same name appearing in ICAPS '08.},
}

EndNote citation:

%0 Report
%A Marthi, Bhaskara 
%A Russell, Stuart J. 
%A Wolfe, Jason 
%T Angelic Hierarchical Planning: Optimal and Online Algorithms (Revised)
%I EECS Department, University of California, Berkeley
%D 2009
%8 August 22
%@ UCB/EECS-2009-122
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-122.html
%F Marthi:EECS-2009-122