Cooperative heuristic multi-agent planning
Mathijs M. De Weerdt, J.F.M. Tonino, Cees Witteveen · 2001
In a previous BNAIC paper [10] we introduced a resource-based framework for representing plans. Using this framework we developed a polynomial algorithm for plan merging, a process in which agents combine their plans to save actions and resources. In this paper we will use the framework to study cooperative heuristic multi-agent planning. During the construction of their plans, the agents use a heuristic function inspired by the FF planner ([3]). At any time in the process of planning the agents may exchange available resources, or they may request an agent to produce a missing resource. The latter feature is enabled by an advertising mechanism: Any agent communicates to the other agents which resources it can, in principle, produce using a plan scheme stored in its knowledge base. The planning algorithm presented in this paper is sound but not complete: It might fail to find a plan in cases a valid plan does exist.