Angelic Hierarchical Planning: Optimal and Online Algorithms (Revised). Marthi, Russell, Wolfe. Tech Report 2009 (revision of earlier ICAPS paper)

<Not reading super carefully because of limited time>

  1. Deals with “angelic” high level actions that can be used to develop a plan and figure out if it will succeed without transforming into low-level actions
  2. Here the concept is expanded to be able to figure out if such a plan is optimal or not
    1. Algorithm based on A* <at least thats what it seems like based on the name>
  3. “Humans somehow manage to choose quite intelligently the twenty trillion primitive motor commands that constitute a life, despite the large state space. It has long been thought that hierarchical structure in behavior is essential in managing this complexity. Structure exists at many levels, ranging from small (hundred-step?) motor programs for typing characters and saying phonemes up to large (billion-step?) actions such as writing an ICAPS paper, getting a good faculty position, and so on. The key to reducing complexity is that one can choose (correctly) to write an ICAPS paper without first considering all the character sequences one might type.”
  4. “…downward refinement property: every plan that claims to achieve some condition does in fact have a primitive refinement that achieves it. This property would enable the derivation of provably correct abstract plans without refining all the way to primitive actions, providing potentially exponential speedups. This requires, however, that HLAs have clear precondition–effect semantics, … we defined an “angelic semantics” for HLAs, specifying for each HLA the set of states reachable by some refinement into a primitive action sequence. The angelic approach captures the fact that the agent will choose a refinement and can thereby choose which element of an HLA’s reachable set is actually reached. This semantics guarantees the downward refinement property and yields a sound and complete hierarchical planning algorithm that derives significant speedups from its ability to generate and commit to provably correct abstract plans.”
  5. Their previous paper was concerned only with correctness, not efficiency, so here the ability to use heuristics is added, and they want optimality as well: “the exact cost of executing a high-level action to get from state s to state s” is the least cost among all primitive refinements that reach s^’ “
  6. Getting an exact cost estimate is difficult though so they start with trying to get accurate upper and lower bounds
  7. “we derive the first algorithm capable of generating provably optimal abstract plans… We also provide a satisficing algorithm that sacrifices optimality for computational efficiency and may be more useful in practice. Preliminary experimental results show that these algorithms outperform both “flat” and our previous hierarchical approaches”
  8. Also considers online planning where there is planning is done by repeated limited lookahead
    1. Do a version of LRTA* for online hierarchical angelic planning
  9. Consider finite deterministic domains, with at least one finite-cost solution (cost minimization)
  10. A refinement of a plan is basically a way of making a plan less abstract and more concrete, although it doesn’t necessarily ground the plan out in primitives; it may simply decompose it into more high-level actions that are executed in certain conditions
  11. High-level actions are basically defined in terms of what states they are allowed to start in, and what states they may finish in (although again remember the domain is deterministic)
  12. But these high level actions also have costs associated with them, and if we are doing optimal planning these costs must also be optimal
  13. Can describe the formalism with NCSTRIPS with costs added (Nondeterministic Conditional STRIPS) <wait I thought we are in deterministic land, maybe the high level actions can have stochasticity?>
  14. Offline and online methods of planning
  15. Offline search done by branch-and-bound search
  16. <Ok skipping the rest – think I get the idea>

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: