Plan Reuse in Distributed Planning

Revised on Nov. 18, 2001


In cooperative distributed problem solving, distributed planning is important to generate cooperative activities. It is, however, a sophisticated task because of not only the computational cost of the fundamental planning algorithm but also costs of communications among agents, detections of task relations and generations of coordinated actions. This often results in difficulty in developing practical systems. ``More efficient distributed planning'' is a very important research issue.

In single-agent planning, plan reuse has been proposed by Kambhampati [1] to achieve efficient planning by avoiding repetitive planning activities. When a new problem is given, the system retrieves the plan that was created for a past identical or similar problem then modifies it so that it can be applied to the new one. This research addresses the issue of whether or not, in hierarchical distributed planning, an agent can reuse past plans for new incoming problems in an environment where a number of identical or similar problems recur. There are a number of issues in realizing plan reuse in distributed planning for multiple agent actions.

The first issue is the similarity of new and old problems. Even if an agent thinks that the new problem is similar to a past one, other agents may have quite different goals. Is the plan created for the past problem useful for planning for the new one? Another important issue is performance, that is, can plan reuse really achieve efficient planning? Especially, it is important to reduce the costs of communication, conflict detection, and conflict resolution (negotiation) because they are relatively costly. The underlying ideas to these issues are that it is possible in such an environment that

(1) other agents' goals may affect the process of specialization of a high-level plan such as how to minimize and resolve conflicts, but the high level plan is usually similar or identical.
(2) even if there is a conflict, it can be detected in an earlier stage of planning and can be resolved by one of the methods used in the past.
(3) planning activities of a peer agent that does not reuse a past plan may also become simple by sharing a common subgoal.

We propose the plan-reuse framework that is applicable to the new problem regardless of other agents' goals. In this framework, a generated plan is stored as a plan template. A template has a number of plans to achieve the goal or subgoals (intermediary goals). Possible conflicts and resolution methods that were actually detected and used in the past planning activities are also stored. Unlike plan reuse in single-agent planning, a template is incrementally generated because a planning result highly depends on the other agents' goals; in some problems, all agent goals may be independent thus no coordination can be made from the plan derived from this type of problem.

Note: We think that plan reuse is a kind of case-based reasoning/planning. The reason that we do not use the word 'CASE' here is that we have much attention to, not the case idenfitications but, the reusability of plans. We beleive that case identifications in multiagent systems is not easy task becase all co-operating agents matches their sub-cases then they gather all infomation to generate the whole case for identifying the past similar cases. In this research, agents do not have a subjective nor complete global view; they are only interested in whther or not there are reuable plans. Other agents may have different goals, but if their plans causes the same conflict (or contain the task identical to the one used in the past that causes the conflict), the past local plan may be reusable.

References

[1] S. Kambhampati, ``Supporting Flexible Plan Reuse,'' Machine Learning Methods for Planning Ed. by S. Minton, 397-434, 1993

Related Papers


© Toshiharu Sugawara