Angelic Hierarchical Planning: Optimal and Online Algorithms
Bhaskara Marthi, Stuart J. Russell and Jason Wolfe
EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2008-150
December 6, 2008
http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-150.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 an extended version of a paper by the same name appearing in ICAPS '08.
BibTeX citation:
@techreport{Marthi:EECS-2008-150,
Author = {Marthi, Bhaskara and Russell, Stuart J. and Wolfe, Jason},
Title = {Angelic Hierarchical Planning: Optimal and Online Algorithms},
Institution = {EECS Department, University of California, Berkeley},
Year = {2008},
Month = {Dec},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-150.html},
Number = {UCB/EECS-2008-150},
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 an 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 %I EECS Department, University of California, Berkeley %D 2008 %8 December 6 %@ UCB/EECS-2008-150 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-150.html %F Marthi:EECS-2008-150