Angelic Hierarchical Planning




This is the homepage for several of our papers on hierarchical decision making. Information is provided for each set of papers, most-recent first.

Angelic Hierarchical Planning: Optimal and Online Algorithms

Bhaskara Marthi, Stuart Russell, and Jason Wolfe.


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.

Paper Versions

A preprint of the published version of the paper:

Angelic Hierarchical Planning: Optimal and Online Algorithms
B. Marthi, S. Russell, and J. Wolfe.
In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 2008.
(bibtex)


An expanded technical report version, which includes proofs:

Angelic Hierarchical Planning: Optimal and Online Algorithms
B. Marthi, S. J. Russell, and J. Wolfe,
EECS Department, University of California, Berkeley,
Tech. Rep. UCB/EECS-2008-150, Dec 2008.
(bibtex)


Update (8/26/09): A revised version of the tech report, which includes some additional content, and corrected empirical results. Results reported in the original paper and previous tech report were erroneous, due to a programming error.

Angelic Hierarchical Planning: Optimal and Online Algorithms (Revised)
B. Marthi, S. J. Russell, and J. Wolfe,
EECS Department, University of California, Berkeley,
Tech. Rep. UCB/EECS-2009-122, Aug 2009.
(bibtex)


Code Download

A Lisp implementation of the algorithm and test domains described in the paper, along with scripts used to produce the empirical results, is available here.
Update (8/26/09): The pruning code in this release is incorrect, which is reflected in the results reported in the two 2008 papers above.
  1. Download and unzip the code
  2. Start up Allegro Lisp or SBCL, and change to the lisp/ directory created in step 1.
  3. Load the asdf system lookahead-sys
  4. Follow the instructions in lisp/lookahead/exps/icaps08/README to run the experiments


Angelic Semantics for High-Level Actions

Bhaskara Marthi, Stuart Russell, and Jason Wolfe.


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 an abstract 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 an abstract 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.

Paper Versions

An expanded technical report version, which includes an appendix with proofs:

Angelic Semantics for High-Level Actions
B. Marthi, S. J. Russell, and J. Wolfe,
EECS Department, University of California, Berkeley,
Tech. Rep. UCB/EECS-2007-89, July 2007.
(bibtex) (endnote)


A preprint of the published version of the paper:

Angelic Semantics for High-Level Actions
B. Marthi, S. Russell, and J. Wolfe.
In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 2007.

Code Download

A Lisp implementation of the algorithm and test domain described in the paper, along with scripts used to produce the empirical results, is available here. Instructions for building and testing are as follows (also here):
  1. Download the file angelic.tar.gz
  2. gunzip and untar the file. This will create a directory tree containing the code, whose root directory is called code/
  3. Start up Lisp
  4. Change to the code root directory
  5. Type '(load "angelic.lisp")'
  6. Type '(make-all)'. This has been tested to compile and load the code without warnings or errors on Allegro Lisp and SBCL, and should work, possibly with minor modifications, on any Ansi Common Lisp.
  7. Type '(load "lookahead/test-lookahead")'. This should run without warnings or errors in under a minute.
  8. Next, to see what the planner is actually doing, switch to the test-lookahead package. Type '(setf *debug-level* 2) and'(hierarchical-forward-search q2). This will make the planner print a trace as it goes.
  9. Type '(load "lookahead/exps/submission")'. This will run the scripts used to produce the results in the paper. Warning: this will probably take days to run. You might want to go into the file and comment out some of the experiments, or change the *num-trials* parameter.
Navigating the code: Our algorithms are in lookahead/. The lookahead/ directory contains representation-independent algorithms, and lookahead/prop contains code related to logical representations and NCSTRIPS. The warehouse world definition, hierarchies and HLA descriptions can be found in envs/blocks.

General tip: you can type (help SYMBOL-NAME) to get help on most operations, types, and packages. E.g., try (help hierarchical-forward-search)

Acknowledgments

Bhaskara Marthi thanks Leslie Kaelbling and Tomas Lozano-Perez for their support during the latter part of this research. This research was also supported by DARPA IPTO, contracts FA8750-05-2-0249 and 03-000219.