Angelic Hierarchical Planning: Optimal and Online Algorithms
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 06, 2008
- Accession Number
- ADA518658
Entities
People
- Bhaskara Marthi
- Jason Wolfe
- Stuart J. Russell
Organizations
- University of California, Berkeley