Abstraction is a powerful tool for solving large-scale planning and scheduling problems. By abstracting away less critical details when looking at a large problem, an agent can find an overall solution to the problem more easily. Then, with the skeleton of the overall solution in place, the agent can work additional details into the solution [Sacerdoti, 1974, Tsuneto, Hendler, Nau, 1998]. Further, when interdependencies are fully resolved at abstract levels, then one or more agents can flesh out sub-pieces of the abstract solution into their full details independently (even in parallel) in a ``divide-and-conquer'' approach [Korf, 1987, Lansky, 1990, Knoblock, 1991].
Unfortunately, it is not always obvious how best to abstract large, complex problems to achieve these efficiency improvements. An agent solving a complicated, many-step planning problem, for example, might not be able to identify which of the details in earlier parts will be critical for later ones until after it has tried to generate plans or schedules and seen what interdependencies end up arising. Even worse, if multiple agents are trying to plan or schedule their activities in a shared environment, then unless they have a lot of prior knowledge about each other, it can be extremely difficult for one agent to anticipate which aspects of its own planned activities are likely to affect, and be affected by, other agents.
In this paper, we describe a strategy that balances the benefits and risks of abstraction in large-scale single-agent and multi-agent planning problems. Our approach avoids the danger of ignoring important details that can lead to incorrect plans (whose execution will fail due to overlooked interdependencies) or to substantial backtracking when abstract decisions cannot be consistently refined. Meanwhile, our approach still achieves many of the computational benefits of abstraction so long as one or more of a number of reasonable conditions (listed later) holds.
The key idea behind our strategy is to annotate each abstract operator in a plan hierarchy with summary information about all of its potential needs and effects under all of its potential refinements. While this might sound contrary to the purpose of abstraction as reducing the number of details, in fact we show that it strikes a good balance. Specifically, because all of the possibly relevant conditions and effects are modeled, the agent or agents that are reasoning with abstract operators can be absolutely sure that important details cannot be overlooked. However, because the summary information abstracts away details about under which refinement choices conditions and effects will or will not be manifested, and information about the relative timing of when conditions are needed and effects achieved, it still often results in an exponential reduction in information compared to a flat representation.
Based on the concept of summary information, this paper extends the prior work summarized below and in Section 8 to make the following contributions: