[ CogSci Summaries home | UP | email ]
http://www.jimdavies.org/summaries/

B. Bonet, G. Loerincs and H. Geffner (1997). A Robust and Fast Action Selection Mechanism for Planning, Proceedings of the 14th National Conference on Artificial Intelligence and 9th Innovative Applications of Artificial Intelligence Conference (AAAI-97/IAAI-97)

@InProceedings{AAAI97_IAAI97*714,
  author =       "Blai Bonet and G{\'a}bor Loerincs and H{\'e}ctor Geffner",
  title =        "A Robust and Fast Action Selection Mechanism for Planning",
  pages =        "714--719",
  ISBN =         "0-262-51095-2",
  booktitle =    "Proceedings of the 14th National Conference on
                 Artificial Intelligence and 9th Innovative Applications
                 of Artificial Intelligence Conference
                 ({AAAI}-97/{IAAI}-97)",
  month =        jul # "~27--31",
  publisher =    "AAAI Press",
  address =      "Menlo Park",
  year =         "1997",
}

Author of the summary: David Furcy, 1999, dfurcy@cc.gatech.edu

Cite this paper for:

System: ASP or Action Selection for Planning (later renamed HSP or Heuristic Search for Planning).
Planning as real-time search using a domain-independent heuristic.
Interleaving planning and plan execution.
Knowledge representation: compactness of functional encodings for planning problems.

Summary

This paper introduces a new paradigm for planning, namely planning as real-time search. ASP, the proposed algorithm, is a variation on LRTA*. Because it performs heuristic search, it is not optimal. However, ASP is fast (faster than SATplan in certain domains) and robust in the presence of noise in action executions.

Detailed outline

Motivation

Going back to the early days, planning was viewed as search in the state-space. But this idea was rejected because:

no good heuristic existed, and
the structured description of planning problems naturally led to the idea of goal decomposition.

The problem is that traditional planners don't scale up very well.

Planning heuristic

Let G be the (abstract) description of the goal state where G = p1 AND p2 AND ... AND pn where each pi is a ground atom.

For every state s and literal p, let d(p,s) denote the actual length of the derivation (or plan) of p from s.

The planning heuristic h(s) is the sum of d(pi,s) over all literals pi in G.

This heuristic captures the traditional idea of goal decomposition as well as the assumption of independence between subgoals. It is a heuristic because it neglects additive (resp. cancellation) interactions and may, as a result, overestimate (resp. underestimate) the length of the optimal plan to G.

In addition to the idea of goal decomposition, this heuristic provides an estimate of the relative difficulty of establishing each subgoal.

Note that this heuristic is neither domain- nor representation-dependent.

Algorithm

LRTA* with look-ahead of 1 interleaves fine-grained planning and plan execution. It always moves to the successor with the smallest heuristic value (local, greedy search) and updates the heuristic value of each visited node (to avoid cycles). Over repeated trials, it learns the optimal goal distances of the states on an optimal path. However, LRTA*:

is unstable from one trial to the next as it favors exploration, and
is slow to converge.

ASP is a variant of LRTA*. It only executes one trial of LRTA* but more work is done before each decision is made. More precisely, ASP uses a look-ahead of 2 over a sample of the search space (because the branching factor is often large).

Functional representation

Based on a standard STRIPS representation, ASP represents actions explicitly (as opposed to SATplan's state-based encodings) but replaces relational fluents with functional fluents of the form t = t'. It also uses a trick to reduce the number of ground instantiations.

Results

Both LRTA* and ASP scale better than SATplan but the quality of the solutions found is not as good.

Advantages

ASP is fast. It allows for real-time action.

ASP is robust in the presence of noise. It seems to handle non-deterministic actions rather smoothly.

Summary author's notes:

none

Back to the Cognitive Science Summaries homepage
Cognitive Science Summaries Webmaster:

JimDavies ( jim@jimdavies.org )

Last modified: Thu Mar 14 10:07:04 EST 2002