next up previous
Next: Complexity analyses and Up: 1 Introduction Previous: Sound and complete

Search techniques and heuristics, including choose-fewest-threats-first (CFTF) and expand-most-threats-first (EMTF), that take advantage of summary information to prune the search space.

When interdependencies run more deeply in agents' plans, resolving them at abstract levels, if possible at all, can lead to unacceptable losses in parallel activity. Fortunately, even when agents need to delve into the details of their plans to tease out interdependencies, summary information can still enable exponential speedups by guiding decomposition and by pruning refinement choices. The search efficiency of using summary information comes from ignoring irrelevant information, which in a distributed planning system also reduces communication overhead exponentially.

Bradley Clement 2006-12-29