Multi-Agent Planning

In order to attain their goals, agents are sometimes required to coordinate them­selves to cooperate or compete with each other, and dispatch tasks using inter­action protocols. In some cases, agents may be required to plan their actions before executing them. Actions can include rounds of interactions that must happen in a given order, for example if their outcomes are interdependent. As shown in Fig. 15.21, planning enables advanced agent cooperation, whereas negotiations are used for managing competing agents.

Similarly to interactions, planning involves action selection, sequencing, and resources handling. The established plans can be action sequences or action trees resulting from policies and strategies defined by the designer or by other agents. Figure 15.7 provides a simple example: to be able to provide the required power during the demand peak, the storage unit needs to charge before the peak occurs.

Three main elements differentiate multi-agent planning techniques: where the plans are created, when coordination occurs, and how plans are coordinated. As for MAS architectures, planning can be centralized, or partially or fully distributed. In centralized planning, one agent plans for the others. It is potentially optimal and requires communication only before and after planning. On the other hand, in distributed planning, computation time is reduced, privacy is easier to ensure, the

Fig. 15.21 Agents can coordinate themselves in two different manners: by cooperating, and planning is then required, or by competing, requiring negotiation

system is scalable and distributed control and execution are enabled. For partially distributed planning, only parts of agents’ plans are shared. Regarding when coordination occurs, three main approaches exist: before, during and after planning (Fig. 15.22). Coordination can also happen during plan execution, especially when communication is unreliable.

Existing planning techniques include STRIPS, ACT, partial plans, plan space refinement, HTN, or Petri nets [54]. Choosing a planning and coordination tech­nique depends on the behavior of the agents and of the technical environment. Similarly to what was detailed in the previous sections, agents for planning can:

• Be strongly related or independent.

• Be cooperative or self-interested.

• Try to resolve conflicts or to exploit efficiency.

• Have no communication or reliable communication available.

• Have to bear with a low or high incident rate.

The interested reader may refer to [31, 59–61] for more information on this topic.