Eithan Ephrati, Martha E. Pollack, and Jeffrey S. Rosenschein
In this paper, we suggest an approach to multi-agent planning that contains elements from decision theory. Our method makes use of subgoals, and derived sub-plans, to construct a global plan. Agents solve their individual sub-plans, which are then merged into a global plan. The suggested approach reduces overall planning time and derives a plan that approximates the optimal global plan that would have been derived by a central planner, given those original subgoals. We consider three different situations (and their possible combinations). The first involves a group of agents with a common goal. The second considers how agents can interleave planning and execution when planning towards a common, though dynamic, goal. The third examines the case where agents, each with his private own goal, plan together to reach a state in consensus for the group. Finally, we consider how these approaches can be adapted to handle rational agents.