A new approach for coordinating generated agents’ plans dynamically

Abstract

In this work, we propose a new approach for coordinating generated agents’ plans dynamically. The purpose is to take into consideration new conflicts introduced in new versions of agents’ plans. The approach consists in finding the best combination which contains one plan for each agent among its set of possible plans whose execution does not entail any conflict. This combination of plans is reconstructed dynamically, each time agents decide to change their plans to take into account unpredictable changes in the environment. This not only ensures that new conflicts are likely to be introduced in the new plans that are taken into account but also it allows agents to deal, solely, with the execution of their actions and not with the resolution of conflicts. For this, we use genetic algorithms where the proposed fitness function is defined based on the number of conflicts that agents can experience in each combination of plans. As part of our work, we used a concrete case to illustrate and show the usefulness of our approach.

Keywords

Multi-agent systems distributed dynamic planning coordination genetic algorithms

1. Introduction

Distributed planning [1, 2] consists of distributing the generation and/or execution of action plans over a set of agents. These agents can be cooperative in the sense that they have a common global objective and complementary capacities to achieve it or, individualistic in the sense that they have individual objectives which they can ensure the achievement without external help. In both cases, the agents must be able to generate plans which allow the achievement of either of the sub – objectives necessary for an overall objective or individual objectives. Distributed planning has enriched the automated planning field as a result of exploiting multi – agent paradigm advantages. Indeed, it has made it possible to go beyond the use of classical representation languages which have exploded a great complexity in plan generation algorithms, the resolution of which has become a major problem for the artificial intelligence community. In the literature, work on distributed planning are available. We cite, among others [3, 4, 5, 6].

The fact that multi-agent planning is distributed over a set of agents that have a strong dependence on their tasks and share the same resources, forces us to give more importance to coordination [24, 25]. The aim is to avoid conflicts that appear when several agents need the same resources simultaneously for the execution of their plans. Coordination includes a set of devices, regulations, and additional actions that it is necessary to accomplish so that the actions of the different agents are possible. The latter can be achieved either by conflict anticipation techniques before the execution of the agents’ plans [7, 8, 9, 10, 12, 13, 14] or by conflict resolution techniques during execution of agent plans [15, 16, 17, 18, 19, 20, 21, 22, 23].

When it comes to dynamic distributed planning, coordination activity becomes more difficult. In fact, in distributed dynamic planning, each agent can make changes in its set of actions to be planned, in order to take into account, the unpredictable changes in its environment. This puts the agents in front of a new planning problem and obsoletes the plans they were performing because they do not take new actions into account. Agents must, therefore, generate new plans dynamically as they change considering new actions. Nevertheless, a big problem arises concerning the coordination of these newly generated plans since new conflicts can be introduced during the execution of the new actions that are inserted in the new plans.

However, two scenarios arise depending on the coordination applied to the initial plans:

In the case where the coordination of the initial plans was based on conflict anticipation techniques before the execution of these plans, the new conflicts introduced are not taken into account, which reduces the initial coordination effort to nothing. In the case where the coordination of the initial plans was based on conflict resolution techniques during the execution of these plans, new conflicts, the number of which increases with each change in plans, force agents to make efforts to resolve them, which delays or even prevents them from achieving their goals.

To overcome these constraints, we propose a new approach for coordinating generated agents’ plans dynamically, able to take into account the evolution of many conflicts caused by the change of agents’ plans. The remainder of this paper is organized as follows. In Section 2, we give a brief overview of major-related work. We describe, in Section 3, the proposed approach. Section 4 illustrates the proposed approach using a concrete case study. Finally, some conclusions and future work directions are given in Section 5.

2. Literature review

Several work in the literature have been proposed for the coordination of the plans. We will focus on the proposed work for coordination prior to the execution of the plans and those proposed for coordination during the plan’s execution.

2.1 Coordination prior to the execution of the plans

Coordination prior to the execution of the plans can be: (i) after planning using plan merging methods and (ii) before planning using social laws.

Among the works proposed for coordination after planning, Georgeff [7, 8] proposes a process model to formalize the actions open to an agent. Parts of such a process model are the correctness conditions, which are defined by the state of the world and must be valid before the execution of the plan may succeed. Two agents can help each other by changing the state of the world in such a way that the correctness conditions of the other agent become satisfied.

Stuart [9] uses a propositional temporal logic to specify constraints on plans, which guaranteed that only feasible states of the environment can be reached. These constraints are given to a theorem prover to generate sequences of communication actions (in fact, these implement semaphores) that guarantee that no event will fail. To both improve efficiency and resolve conflicts, one can introduce restrictions on individual plans to ensure efficient merging.

The work [10] proposes a distributed plan synchronization algorithm. It is based on a representation of the world by states similar to the formalism strips [11]. The production of the plans is carried out by the agents according to their local goals. Each agent is then responsible for synchronizing its plans with the other agents. The construction of a structured plan is broken down into two phases. First, the agent develops a plan independently without considering the plans produced by other agents. Then, it tries to synchronize its plan by broadcasting it to the other agents.

Among the works proposed for coordination before planning, the work of Yang et al. [12] and Foulser et al. [13] proposed some social laws that each agent has to follow in its plans. Thereafter Briggs [14] proposed more flexible laws, where agents first try to plan using the strictest laws, but when a solution cannot be found, agents are allowed to relax these laws somewhat.

Although this work has contributed significantly to the field by proposing new strategies for plan coordination, it does not adapt to dynamic planning in which agents can change their plans at any time to take into account unpredictable changes in the environment. Indeed, with the changes in the plans, new conflicts are not taken into consideration during the coordination of the initial plans, it can be introduced which reduces the effort of the initial coordination to nothing. Contrary to these approaches, our approach makes it possible to consider the new conflicts that can be introduced with the changes in plans.

2.2 Coordination during the execution of plans

The work of the coordination during the execution of the plans focuses a lot more on (i) negotiation protocol (case of a cooperative negotiation). These protocols allow agents in conflict to enter into a series of exchanges and compromises in order to reach an agreement, that is, a solution that satisfies all the parties. Among these protocols we find: Contract-Net protocol [15, 16], Cammarata protocol [17] and multi-stage protocol [18, 19]. (ii) game theory [20], heuristics [21], auctioning [22] or on argumentation [23] (case of a competitive negotiation).

Coordination during the execution of plans can be adapted to dynamic planning since the appearance of a new conflict caused by the change of plans; the agents solve it and continue the execution of their plans. However, with the evolution of the number of conflicts, the agents find themselves more in the process of resolving conflicts than executing their plans, which delays them or even prevents them from completing the execution of their plans. Contrary to these approaches, our approach makes it possible to find, among the sets of possible plans of the agents, the set of plans whose execution does not involve any conflict. This is dynamic whenever there is a change in the sets of plans caused by unpredictable changes in the environment. As a result, agents find themselves only executing their plans and unsolicited in resolving conflicts.

3. The proposed approach for coordinating generated agents’ plans dynamically

Our approach consists in coordinating, dynamically, the plans of the agents that are likely to undergo changes following the unpredictable changes in the environment. This approach is based on the following principle:

To achieve its goal, the agent can generate several plans consisting of a sequence of actions whose execution order differs from one plan to another. However, the execution of one of these plans (the plan X, for example) can put the agent in several conflict situations with the other agents if several actions in the plan X are executed on the same resource, simultaneously with the actions of the other agent’ plans. While the execution of another plan (the plan Y, for example) may create no conflict between this agent and the other agents if no action in the plan Y is executed on the same resource, simultaneously, as the actions of other agent plans. This implies that the number of conflicts that agents can encounter depends on their choice of plans to execute in parallel.

In this regard, we propose a new centralized dynamic coordination approach in which a coordinating agent is tasked with selecting the best combination which contains one plan for each agent among its set of possible plans. The identified combination must guarantee that executing the actions of the plans it contains will not cause any conflict due to the fact that they do not use the same resource simultaneously. This combination is reconstructed dynamically, each time the agents are faced with a new planning problem, with new sets of actions to plan, with respect to which the agents will decide to change their sets of possible plans. For each new combination, the coordinating agent takes into consideration the new conflicts that may be introduced following the execution of the new actions, inserted in the new plans.

According to our approach, each agent $A_{i}$ must generate, based on its set of actions $\alpha_{it}$ , the set of possible plans $P_{it}$ to be executed at time $t$ to solve the planning problem $\Pi_{t}$ where each plan is a sequence of actions to be executed, in a different order from the other plans. The sets of plans $P_{it}$ thus generated will be brought together in a set $P_{t}$ from which the coordinating agent will find the best combination, between the plans generated by the agents, which the execution does not lead to any conflict.

For this, we use genetic algorithms where the proposed fitness function (F) is defined based on the number of potential conflicts that agents can experience in each combination of plans. We set: F $=$ 1/Nbr_Conflicts where the number of conflicts for any combination equals the number of resources used simultaneously (in the same time interval [x, y]) by at least two actions of two different plans that it comprises. The time intervals [x, y] to perform an action on a resource in a given plan depend on the order of this action in this plan and the estimated period for the execution of this latter. Therefore, the most satisfactory combination for the fitness function (F), which the coordinating agent must find, is the one that contains plans whose order of actions ensures that the intersection between its time intervals of the utilisation of a given resource is empty.

Initially, at time t, each agent generates its set of possible plans $P_{i0}$ (the set of possible plans for agent i at time t) to solve the planning problem $\Pi$ . From the sets of plans generated by the agents, the coordinating agent generates the initial population. The individuals of this population are combinations of planes in the form of vector V, where each element of these vectors is a plane $P_{ij}$ (the plane j of agent $A_{i}$ ) (one of the possible planes for agent $A_{i}$ ).

The coordinating agent, through the use of genetic algorithms, generates subpopulations with which it gets closer, as the fitness function is satisfied. This repeats until we get the best combination of plans to execute. During the execution of this combination, if one of the agents $A_{i}$ finds itself, at a given instant $t$ , in front of a new planning problem $\Pi_{t}$ with a new set of actions to plan, another set of plans $P_{it}$ , will be generated dynamically to consider these actions. In this new set $P_{it}$ , the agent $A_{i}$ must generate all possible plans based on its new set of actions ( $\alpha_{it}$ ) which contains the old unexecuted actions of the old plan and the new actions generated by the changes. The coordinating agent, in this case, receives, from the agents having changed their sets of plans, the new sets of $P_{it}$ plans generated, and from the rest of the agents, it receives the set of possible plans generated based on the set of actions not yet executed at time $t$ of the change. The new set of $P_{t}$ plans formed, thus, will serve as a basis for the coordinating agent for a new combination of plans whose execution will not suffer from any conflict. According to our approach, the coordination problem at time $t$ is defined by the planning problem $\Pi_{t}$ , the set of possible plans $P_{t}$ to be executed by the agents to solve this planning problem, the set of resources $R_{t}$ to be used by the agents.

The planning problem at time $t\Pi_{t}$ is defined by the set of agents (N), the current state of the system at time $t(S_{t})$ , and the final system state ( $S_{f}$ ).

Each agent is defined by 4 parts as follows:

(i)
The set of actions $\alpha_{it}$ to be executed at time $t$ . Each action $\alpha_{ik}$ is characterized by a state $e_{k}$ which indicates whether this action is executed or not at the time $t$ , the resource to be used by this action $R_{k}$ and the period necessary for the execution of this action.
(ii)
The current state of the agent.
(iii)
An action revision function Rev_ $\alpha_{i}$ that allows the agent’s action set to be updated when it changes.
(iv)
A plan revision function Rev_ $P_{it}$ that allows the update of the agent’s set of plans according to the change in its set of actions.

3.1 The formal definition of the distributed planning problem

According to our approach, the coordination problem can be defined as follows

$\displaystyle C_{t}=(\Pi_{t},P_{t},R_{t}).$ (1)

where $\Pi_{t}$ represents the planning problem at instant $t$ ,

$\displaystyle\Pi_{t}=(N,S_{t},S_{f}),$ (2)

where $N$ represents a set of agents

$\displaystyle N={\{}A_{1},A_{2},\ldots,A_{n}{\}},$ (3)

$S_{t}$ represents the state of the system at time $t$ , which changes as the actions are executed by the set of $N$ agents, and $S_{f}$ represents the final state of the system.

$P_{t}$ represents the possible solutions to the problem $\Pi_{t}$ . It contains the set of all possible plans of agents at time $t$ .

$\displaystyle P_{t}={\{}P_{1t},P_{2t}\ldots P_{nt}{\}}.$ (4)

Based on this set, the coordinating agent generates the best possible combination.

$R_{t}$ represents the set of resources to be used by the actions of the agents at time $t$ .

Each agent $A_{i}$ is defined as

$\displaystyle A_{i}=(\alpha_{it},P_{it},S_{it},S_{if},\textit{Rev}{\_}\alpha_{% i},\textit{Rev}{\_}P_{it}),$ (5)

where $\alpha_{it}$ represents $A_{i}$ agent’s set of actions at instant $t$

$\displaystyle\alpha_{it}={\{}\alpha_{i1},\alpha_{i2},\ldots,\alpha_{il}{\}}$ (6)

Each action $\alpha_{ik}$ (the action k of agent $A_{i}$ ) is defined as

$\displaystyle\alpha_{ik}=(e_{k},Pr_{k},R_{k}),$ (7)

where $e_{k}$ represents the state that indicates that the action $\alpha_{ik}$ is performed or not at instant $t$ , $R_{k}$ represents the resource that will be used by action $\alpha_{ik}$ , and $Pr_{k}$ , represents the estimated necessary period to execute action $\alpha_{ik}$ (action k of agent Ai) on the resource $R_{k}$ .

$P_{it}$ represents the set of possible plans of agent Ai at time $t$ .

$\displaystyle P_{it}={\{}P_{i1},P_{i2}\ldots,P_{ij},\ldots,P_{im}{\}}$ (8)

where $P_{ij}$ represents plan $j$ , among m possible plans, of agent Ai at instant $t$ .

$\displaystyle P_{ij}=\left\{\begin{array}[]{l}(\alpha_{ik1},\alpha_{ik2},% \ldots,\alpha_{\textit{ikl}})\\ ((x_{\alpha ik1},y_{\alpha ik1}),(x_{\alpha ik2},y_{\alpha ik2}),\ldots,((x_{% \alpha\textit{ikl}},y_{\alpha\textit{ikl}}))\\ \end{array}\right.$ (9)

where $\alpha_{\textit{ikq}}$ represents the action $k$ of the agent Ai placed in the order $q$ in the plane $j$ , and ( $x_{\alpha\textit{ikq}}$ , $y_{\alpha\textit{ikq}}$ ) represents the time intervals [x, y] to perform the actions $\alpha_{ik}$ on the resource $R_{k}$ . These intervals are calculated by the period $Pr_{k}$ and the order $q$ of the action in $P_{ij}$ .

Figure 1.

Diagrammatic representation of the formal framework.

$S_{it}$ represents the state of agent $A_{i}$ at time $t$ , which changes as the actions are executed; $S_{if}$ represents the final state of the agent $A_{i}$ ; Rev_ $\alpha_{i}$ represents agent’s set of actions revision function which can change the set of the action of the agent $A_{i}$ in order to take into account, the unpredictable changes in its environment; Rev_ $P_{it}$ represents agent’s plans revision function which can change plans of the agent $A_{i}$ in order to take into account new actions.

Figure 1 shows a diagrammatic representation of the formal framework.

3.2 Coordination of initial plans

P_{0}

Each agent $A_{i}$ starts by generating its initial possible plan set $P_{i0}$ for solving the initial planning problem $\Pi$ based on its initial action set $\alpha_{i0}$ .

Based on the sets of plans $P_{i0}$ of the agents, the coordinating agent first generates an initial population Pop ${}_{0}$ , in which it builds a large number of individuals (vectors). The generation of the initial population is done randomly. In order to find a more efficient population Pop ${}_{1}$ that will better satisfy the fitness function, the coordinating agent applies the following steps to the population Pop ${}_{{0}}$ .

First, each individual $V_{k}$ (a combination of agent plans) of the population Pop ${}_{0}$ is evaluated. For this, the value of the fitness function F is calculated.

Then, a selection step is applied. This step makes it possible to eliminate the least relevant individuals (combinations) from Pop ${}_{0}$ and to keep only the best ones according to their evaluation.

The next step is to cross the previously selected individuals to obtain the new Pop1 population. It consists in applying for every two individuals (parents) a crossing operator in order to obtain a new individual (descendant). The latter is composed of a part of parent 1 and a part of parent 2.

To diversify the solutions over generations, a mutation step is used. This mutation consists of modifying a small part of a character in certain individuals of the new generation randomly.

From the Pop ${}_{1}$ population obtained, the steps described above will be reapplied, within the limit of the number of possible generations “n” specified by the program. The aim is to obtain a population in which there is an individual (a combination) that fully satisfies the fitness function. The plans of this individual will be considered as initial plans $p_{i0}$ for the agents $A_{i}$ . If this individual is not obtained within the limit of the possible generations, the best individual obtained in the last generation (Pop ${}_{n}$ ) will be taken.

3.3 Dynamic coordination of plans

In the event of the appearance of a new planning problem $\Pi_{t}$ , the coordinating agent, must find a new combination $V_{t}$ , between the new sets of possible plans generated by the agents based on their new sets of actions, whose execution will not suffer any conflict. To do this, it follows the same steps as those applied for the generation of the initial combination $V_{0}$ , knowing that

(a)
The set of plans $P_{t}$ will be built by the new sets of plans $P_{it}$ generated by the agents having changed their sets of actions and by the set of possible plans generated based on the set of actions not yet executed at the instant $t$ of the change generated by the rest of the agents;
(b)
The initial population Pop ${}_{0}$ will be generated based on this new set of plans $P_{t}$ ;
(c)
The set of resources will be increased by the new resources to be used by the new actions.

The algorithm of our approach is presented in Algorithm 1. The function $\textit{Generation}{\_}V_{t}$ is executed by the coordinating agent CA while the function $\textit{Revision}(\Pi_{t},R_{t})$ is executed by the agents $A_{i}$ .

Algorithm 1: Coordinating generated agents’ plans dynamically

1. Input: coordination problem at $t_{0}$ $C_{t}=(\Pi_{t},P_{t},R_{t})$

2. output: $V_{t}$

3. Function: Generation_ $V_{t}$ ( $P_{t}$ , $R_{t}$ ) /* Executed by the coordinating agent CA

4. Begin

5. Generate randomly the initial population Pop ${}_{0}$ on the basis of the set $P_{t}$ /* Each vector is a combination which

contains one plan for each agent among its set of possible plans

6. $n:=$ 0;

7. While $n<=N$ and F is not satisfied do

8. Begin

9. Evaluate each $V_{k}$ of the population according to F

10. Select the most satisfactory vectors in the population

11. Produce new vectors (children) from selected plans by crossing

12. Mutation of the Vectors

13. $n:=n+1$ ;

14. End;

15. Return $V_{t}$ /* The best combination (Vector) found at time t

16. End;

17. Function: Revision ( $\Pi_{t}$ , $R_{t}$ ) /* Executed by the agents $A_{i}$

18. Begin

19. Rev_ $\alpha i$ /* actions revision function which can change the set of the action of the agent $A_{i}$ in order to take into account,

the unpredictable changes in its environment. $\alpha_{it}:=\alpha_{ij}$ (not executed actions where $\alpha_{ij}.e_{k}=\textit{false}$ ) U New actions

20. Rev_Pi /* plans revision function which can change plans of the agent $A_{i}$ in order to take into account new actions.

21. $S_{it}:=$ The agent state at instant t of change;

22. End;

23. Begin

24. $t:=t_{0}$

25. For $i:=$ 1 to N do

26. Begin

27. $P_{it}:=$ All possible plans generated from the action set $\alpha_{it}$

28. $P_{t}:=P_{t}U(P_{it})$

29. End For;

30. Repeat

31. $V_{t}:=$ CA. Generation_ $V_{t}$ ( $P_{t}$ , $R_{t}$ );

32. Execute the plans of $V_{t}$

33. If there is a change in the actions set $\alpha_{it}$ during the execution of the plans of $V_{t}$ do

34. $t:=$ Instant of change

35. $Rt:=$ The available resources in the system at instant of change $t$

36. $S_{st}$ : the system state at instant t of change;

37. For $i:=$ 1 to N do

38. Begin

39. $A_{i}$ . Revision ( $\Pi_{t}$ , $R_{t}$ )

40. End For;

41. End if

42. Until $S_{it}=S_{if}$ or $S_{st}=S_{sf}$ /* The generation of new plans is stopped when: (i) agents arrive at their final states.

This is if the agents having deferent objectives. (ii) agents arrive at the final state of the system. This is if the agents

have the same objective.

43. End.

4. Case study

Algorithm 1: Coordinating generated agents’ plans dynamically
1. Input: coordination problem at $t_{0}$ $C_{t}=(\Pi_{t},P_{t},R_{t})$
2. output: $V_{t}$
3. Function: Generation_ $V_{t}$ ( $P_{t}$ , $R_{t}$ ) /* Executed by the coordinating agent CA
4. Begin
5. Generate randomly the initial population Pop ${}_{0}$ on the basis of the set $P_{t}$ /* Each vector is a combination which
contains one plan for each agent among its set of possible plans
6. $n:=$ 0;
7. While $n<=N$ and F is not satisfied do
8. Begin
9. Evaluate each $V_{k}$ of the population according to F
10. Select the most satisfactory vectors in the population
11. Produce new vectors (children) from selected plans by crossing
12. Mutation of the Vectors
13. $n:=n+1$ ;
14. End;
15. Return $V_{t}$ /* The best combination (Vector) found at time t
16. End;
17. Function: Revision ( $\Pi_{t}$ , $R_{t}$ ) /* Executed by the agents $A_{i}$
18. Begin
19. Rev_ $\alpha i$ /* actions revision function which can change the set of the action of the agent $A_{i}$ in order to take into account,
the unpredictable changes in its environment. $\alpha_{it}:=\alpha_{ij}$ (not executed actions where $\alpha_{ij}.e_{k}=\textit{false}$ ) U New actions
20. Rev_Pi /* plans revision function which can change plans of the agent $A_{i}$ in order to take into account new actions.
21. $S_{it}:=$ The agent state at instant t of change;
22. End;
23. Begin
24. $t:=t_{0}$
25. For $i:=$ 1 to N do
26. Begin
27. $P_{it}:=$ All possible plans generated from the action set $\alpha_{it}$
28. $P_{t}:=P_{t}U(P_{it})$
29. End For;
30. Repeat
31. $V_{t}:=$ CA. Generation_ $V_{t}$ ( $P_{t}$ , $R_{t}$ );
32. Execute the plans of $V_{t}$
33. If there is a change in the actions set $\alpha_{it}$ during the execution of the plans of $V_{t}$ do
34. $t:=$ Instant of change
35. $Rt:=$ The available resources in the system at instant of change $t$
36. $S_{st}$ : the system state at instant t of change;
37. For $i:=$ 1 to N do
38. Begin
39. $A_{i}$ . Revision ( $\Pi_{t}$ , $R_{t}$ )
40. End For;
41. End if
42. Until $S_{it}=S_{if}$ or $S_{st}=S_{sf}$ /* The generation of new plans is stopped when: (i) agents arrive at their final states.
This is if the agents having deferent objectives. (ii) agents arrive at the final state of the system. This is if the agents
have the same objective.
43. End.

To validate our approach, we apply it to a concrete case study: A merchandise distribution system. The objective of this system is to distribute articles Art ${}_{tj}$ stored in distribution points $S_{j}$ to a set of customers installed in points $T_{k}$ . The points $S_{j}$ , and $T_{k}$ represent all the resources, which can be the source of conflicts if the distributors access them simultaneously. The system receives each time requests defined by: the requesting client $T_{k}$ , the requested article Art ${}_{j}$ , the point in which the article is stored $S_{j}$ , the quantity of the requested article as well as the agent $A_{i}$ concerned by this request. For each request

$\displaystyle\textit{Req}_{m}=((S_{j},\textit{Art}_{j},T_{k}),\textit{quantity% },A_{i})$ (10)

the agent $A_{i}$ must perform the following actions:

$\displaystyle(\textit{Drive}(S_{j}),\textit{False}),(\textit{Load}(S_{j},% \textit{Art}_{j},\textit{quantity}),\textit{False}),$ (11) $\displaystyle(\textit{Drive}(T_{k}),\textit{False}),(\textit{Distribute}(T_{k}% ,\textit{Art}_{j},\textit{quantity}),\textit{False}).$

In what follows, we will first apply the approach to a given system state for which the agents have generated their sets of possible plans and the coordinating agent has created the best combination between the possible generated plans. In a second step, we will propose a change that will be applied during the execution of the plans of the combination found by the coordinating agent to show the dynamism of the approach. In this case study, for the genetic algorithm, we adopted a real coding and we chose the following values: maximum number of generations $=$ 30; mutation probability $=$ 2%, selection percentage $=$ 80%; the fitness function F $=$ 1/Nbr_conf (when the number of conflicts is equal to 0 divided by 0.0001). For the implementation, we used the JADE platform and for plans generation, we used the list structure.

4.1 The coordination problem at time

t_{0}

Suppose that at time $t_{0}$ we have 7 customers T ${}_{1}$ , T ${}_{2}$ … T ${}_{7}$ and 4 distribution points S ${}_{1}$ , S ${}_{2}$ … S ${}_{4}$ (Fig. 2).

Figure 2.

System state at instant $t_{0}$ .

Suppose that the requests at this time are:

$\displaystyle\text{Req}_{1}=((\text{S}_{1},\text{Art}_{1},\text{T}_{3}),100,% \text{A}_{1}),$ $\displaystyle\text{Req}_{2}=((\text{S}_{3},\text{Art}_{3},\text{T}_{4}),50,% \text{A}_{1}),$ $\displaystyle\text{Req}_{3}=((\text{S}_{2},\text{Art}_{2},\text{T}_{1}),150,% \text{A}_{1}),$ $\displaystyle\text{Req}_{4}=((\text{S}_{3},\text{Art}_{3},\text{T}_{2}),150,% \text{A}_{2}),$ $\displaystyle\text{Req}_{5}=((\text{S}_{4},\text{Art}_{4},\text{T}_{5}),50,% \text{A}_{2}),$ $\displaystyle\text{Req}_{6}=((\text{S}_{2},\text{Art}_{2},\text{T}_{7}),300,% \text{A}_{2}),$ $\displaystyle\text{Req}_{7}=((\text{S}_{1},\text{Art}_{1},\text{T}_{6}),200,% \text{A}_{2}),$ $\displaystyle\text{Req}_{8}=((\text{S}_{2},\text{Art}_{2},\text{T}_{3}),150,% \text{A}_{3}),$ $\displaystyle\text{Req}_{9}=((\text{S}_{1},\text{Art}_{1},\text{T}_{2}),150,% \text{A}_{3}),$ $\displaystyle\text{Req}_{10}=((\text{S}_{4},\text{Art}_{4},\text{T}_{1}),200,% \text{A}_{3}).$

At instant t0, the set of actions of each agent $A_{i}$ :

$\displaystyle\alpha_{10}={\{}(\text{Drive}(\text{S}_{1}),\text{False}),(\text{% Load}(\text{S}_{1},\text{Art}_{1},100),\text{False}),(\text{Drive}(\text{T}_{3% }),\text{False}),(\text{Distribute}(\text{T}_{3},\text{Art}_{1},100),\text{% False}),(\text{Drive}(\text{S}_{3}),\text{False}),(\text{Load}(\text{S}_{3},% \text{Art}_{3},50),\text{False}),(\text{Drive}(\text{T}_{4}),\text{False}),(% \text{Distribute}(\text{T}_{4},\text{Art}_{3},50),\text{False}),(\text{Drive}(% \text{S}_{2}),\text{False}),(\text{Load}(\text{S}_{2},\text{Art}_{2},150),% \text{False}),(\text{Drive}(\text{T}_{1}),\text{False}),(\text{Distribute}(% \text{T}_{1},\text{Art}_{2},150),\text{False}){\}}$ $\displaystyle\alpha_{20}={\{}(\text{Drive}(\text{S}_{3}),\text{False}),(\text{% Load}(\text{S}_{3},\text{Art}_{3},150),\text{False}),(\text{Drive}(\text{T}_{2% }),\text{False}),(\text{Distribute}(\text{T}_{2},\text{Art}_{3},150),\text{% False}),(\text{Drive}(\text{S}_{4}),\text{False}),(\text{Load}(\text{S}_{4},% \text{Art}_{4},50),\text{False}),(\text{Drive}(\text{T}_{5}),\text{False}),(% \text{Distribute}(\text{T}_{5},\text{Art}_{4},50),\text{False}),(\text{Drive}(% \text{S}_{2}),\text{False}),(\text{Load}(\text{S}_{2},\text{Art}_{2},300),% \text{False}),(\text{Drive}(\text{T}_{7}),\text{False}),(\text{Distribute}(% \text{T}_{7},\text{Art}_{2},300),\text{False}),(\text{Drive}(\text{S}_{1}),% \text{False}),(\text{Load}(\text{S}_{1},\text{Art}_{1},200),\text{False}),(% \text{Drive}(\text{T}_{6}),\text{False}),(\text{Distribute}(\text{T}_{6},\text% {Art}_{1},200),\text{False}){\}}$ $\displaystyle\alpha_{30}={\{}(\text{Drive}(\text{S}2),\text{False}),(\text{% Load}(\text{S}2,\text{Art}2,150),\text{False}),(\text{Drive}(\text{T}3),\text{% False}),(\text{Distribute}(\text{T}3,\text{Art}2,150),\text{False}),(\text{% Drive}(\text{S}1),\text{False}),(\text{Load}(\text{S}1,\text{Art}1,150),\text{% False}),(\text{Drive}(\text{T}2),\text{False}),(\text{Distribute}(\text{T}2,% \text{Art}1,150),\text{False}),(\text{Drive}(\text{S}4),\text{False}),(\text{% Load}(\text{S}4,\text{Art}4,200),\text{False}),(\text{Drive}(\text{T}1),\text{% False}),(\text{Distribute}(\text{T}1,\text{Art}4,200),\text{False}){\}}$

The set $R_{0}$ of resources used by these actions are:

$\displaystyle R_{0}={\{}T1,T2,T3,T4,T5,T6,T7,S1,S2,S3,S4{\}}$ (12)

The set of possible initial plans to accomplish the requests of the initial planning problem $\Pi_{0}$ for each agent $A_{{i}}$ is given in Table 1 (this table represents five possible initial plans for each agent A ${}_{1}$ , A ${}_{2}$ , and A ${}_{3}$ ).

Table 1

Five possible initial plans for each agent A ${}_{1}$ , A ${}_{2}$ , and A ${}_{3}$

P ${}_{\text{i0}}$		Five possible initial plans for A ${}_{\text{i}}$
P ${}_{10}$	P11	(Drive S1, false) (Load S1, Article1, 100, false) (Drive S2, false) (Load S2, Article2, 150, false) (Drive T3, false) (Distribute T3, Article1, 100, false) (Drive S3, false) (Load S3, Article3, 50, false) (Drive T4, false) (Distribute T4, Article3, 50, false) (Drive T1, false) (Distribute T1, Article2, 150, false) ((0, 2) (2, 5) (5, 7) (7, 11) (11, 13) (13, 15) (15, 18) (18, 22) (22, 25) (25, 30) (30, 34) (34, 36))
	P12	(Drive S2, false) (Load S2, Article2, 150, false) (Drive S3, false) (Load S3, Article3, 50, false) (Drive S1, false) (Load S1, Article1, 100, false) (Drive T3, false) (Distribute T3, Article1, 100, false) (Drive T4, false) (Distribute T4, Article3, 50, false) (Drive T1, false) (Distribute T1, Article2, 150, false) ((0, 4) (4, 7) (7, 6) (6, 10) (10, 14) (14, 16) (16, 18) (18, 22) (22, 27) (27, 32) (32, 37) (37, 39))
	P13	(Drive S2, false) (Load S2, Article2, 150, false) (Drive S1, false) (Load S1, Article1, 100, false) (Drive S3, false) (Load S3, Article3, 50, false) (Drive T3, false) (Distribute T3, Article1, 100, false) (Drive T1, false) (Distribute T1, Article2, 150, false) (Drive T4, false) (Distribute T4, Article3, 50, false) ((0, 3) (3, 6) (6, 8) (8, 12) (12, 14) (14, 16) (16, 19) (19, 23) (23, 25) (25, 30) (30, 35) (35, 38))
	P14	(Drive S2, false) (Load S2, Article2, 150, false) (Drive T1, false) (Distribute T1, Article2, 150, false) (Drive S3, false) (Load S3, Article3, 50, false) (Drive S1, false) (Load S1, Article1, 100, false) (Drive T4, false) (Distribute T4, Article3, 50, false) (Drive T3, false) (Distribute T3, Article1, 100, false) ((0, 2) (2, 5) (5, 8) (8, 12) (12, 15) (15, 17) (17, 19) (19, 24) (24, 28) (28, 33) (33, 37) (37, 40))
	P15	(Drive S2, false) (Load S2, Article2, 150, false) (Drive T1, false) (Distribute T1, Article2, 150, false) (Drive S3, false) (Load S3, Article3, 50, false) (Drive S1, false) (Load S1, Article1, 100, false) (Drive T3, false) (Distribute T3, Article1, 100, false) (Drive T4, false) (Distribute T4, Article3, 50, false) (Distribute T1, Article2, 150, false) (Drive T4, false) (Distribute T4, Article3, 50, false) ((0, 5) (5, 10) (10, 12) (12, 16) (16, 18) (18, 20) (20, 23) (23, 27) (27, 30) (30, 35) (35, 32) (32, 35))
P ${}_{20}$	P21	(Drive S1, false) (Load S1, Article1, 200, false) (Drive T6, false) (Distribute T6, Article1, 200, false) (Drive S3, false) (Load S3, Article3, 150, false) (Drive S4, false) (Load S4, Article4, 50, false) (Drive T2, false) (Distribute T2, Article3, 150, false) (Drive S2, false) (Load S2, Article2, 300, false) (Drive T5, false) (Distribute T5, Article4, 50, false) (Drive T7, false) (Distribute T7, Article2, 300, false) ((0, 4) (4, 7) (7, 8) (8, 11) (11, 14) (14, 16) (16, 19) (19, 22) (22, 24) (24, 27) (27, 30) (30, 36) (36, 40) (40, 43) (43, 45) (45, 49))
	P22	(Drive S3, false) (Load S3, Article3, 150, false) (Drive S2, false) (Load S2, Article2, 300, false) (Drive S1, false) (Load S1, Article1, 200, false) (Drive S4, false) (Load S4, Article4, 50, false) (Drive T2, false) (Distribute T2, Article3, 150, false) (Drive T5, false) (Distribute T5, Article4, 50, false) (Drive T6, false) (Distribute T6, Article1, 200, false)

Table 1, continued
P ${}_{\text{i0}}$		Five possible initial plans for A ${}_{\text{i}}$
		(Drive T7, false) (Distribute T7, Article2, 300, false)((0, 3) (3, 8) (9, 12) (12, 14) (14, 16) (16, 17) (17, 19) (19, 22) (22, 24) (24, 28) (28, 30) (30, 33) (33, 37) (37, 40) (40, 43) (43, 45))
	P23	(Drive S1, false) (Load S1, Article1, 200, false) (Drive S3, false) (Load S3, Article3, 150, false) (Drive T2, false) (Distribute T2, Article3, 150, false) (Drive S2, false) (Load S2, Article2, 300, false) (Drive T6, false) (Distribute T6, Article1, 200, false) (Drive T7, false) (Distribute T7, Article2, 300, false) (Drive S4, false) (Load S4, Article4, 50, false) (Drive T5, false) (Distribute T5, Article4, 50, false) ((0, 5) (5, 8) (8, 10) (10, 12) (12, 14) (14, 16) (16, 19) (19, 22) (22, 25) (25, 27) (27, 30) (30, 34) (34, 37) (37, 40) (40, 43) (43, 45))
	P24	(Drive S3, false) (Load S3, Article3, 150, false) (Drive S1, false) (Load S1, Article1, 200, false) (Drive T6, false) (Distribute T6, Article1, 200, false) (Drive S4, false) (Load S4, Article4, 50, false) (Drive T5, false) (Distribute T5, Article4, 50, false) (Drive S2, false) (Load S2, Article2, 300, false) (Drive T7, false) (Distribute T7, Article2, 300, false) (Drive T2, false) (Distribute T2, Article3, 150, false) ((0, 2) (2, 5) (5, 8) (8, 11) (11, 14) (14, 16) (16, 20) (20, 24) (24, 26) (26, 28) (28, 32) (32, 36) (36, 40) (40, 43) (43, 47) (47, 50))
	P25	(Drive S3, false) (Load S3, Article3, 150, false) (Drive S1, false) (Load S1, Article1, 200, false) (Drive T6, false) (Distribute T6, Article1, 200, false) (Drive S4, false) (Load S4, Article4, 50, false) (Drive T5, false) (Distribute T5, Article4, 50, false) (Drive T2, false) (Distribute T2, Article3, 150, false) (Drive S2, false) (Load S2, Article2, 300, false) (Drive T7, false) (Distribute T7, Article2, 300, false) ((0, 3) (3, 7) (7, 8) (8, 12) (12, 14) (14, 16) (16, 19) (19, 22) (22, 25) (25, 27) (27, 30) (30, 34) (34, 37) (37, 40) (40, 42) (42, 46))
P ${}_{30}$	P31	(Drive S2, false) (Load S2, Article2, 150, false) (Drive S1, false) (Load S1, Article1, 150, false) (Drive T2, false) (Distribute T2, Article1, 150, false) (Drive S4, false) (Load S4, Article4, 200, false) (Drive T1, false) (Distribute T1, Article4, 200, false) (Drive T3, false) (Distribute T3, Article2, 150, false) ((0, 3) (3, 7) (7, 9) (9, 12) (12, 15) (15, 18) (18, 21) (21, 24) (24, 28) (28, 31) (31, 35) (35, 38))
	P32	(Drive S2, false) (Load S2, Article2, 150, false) (Drive S1, false) (Load S1, Article1, 150, false) (Drive S4, false) (Load S4, Article4, 200, false) (Drive T2, false) (Distribute T2, Article1, 150, false) (Drive T3, false) (Distribute T3, Article2, 150, false) (Drive T1, false) (Distribute T1, Article4, 200, false) ((0, 2) (2, 6) (6, 9) (9, 12) (12, 15) (15, 19) (19, 21) (21, 24) (24, 27) (27, 31) (31, 36) (36, 40))
	P33	(Drive S4, false) (Load S4, Article4, 200, false) (Drive S1, false) (Load S1, Article1, 150, false) (Drive S2, false) (Load S2, Article2, 150, false) (Drive T2, false) (Distribute T2, Article1, 150, false) (Drive T3, false) (Distribute T3, Article2, 150, false) (Drive T1, false) (Distribute T1, Article4, 200, false) ((0, 4) (4, 7) (7, 10) (10, 13) (13, 15) (15, 18) (18, 21) (21, 25) (25, 28) (28, 31) (31, 35) (35, 39))

Table 1, continued
P ${}_{\text{i0}}$		Five possible initial plans for A ${}_{\text{i}}$
	P34	(Drive S1, false) (Load S1, Article1, 150, false) (Drive S2, false) (Load S2, Article2, 150, false) (Drive S4, false) (Load S4, Article4, 200, false) (Drive T2, false) (Distribute T2, Article1, 150, false) (Drive T3, false) (Distribute T3, Article2, 150, false) (Drive T1, false) (Distribute T1, Article4, 200, false) ((0, 3) (3, 8) (8, 11) (11, 13) (13, 15) (15, 18) (18, 23) (23, 26) (26, 28) (28, 31) (31, 33) (33, 36))
	P35	(Drive S4, false) (Load S4, Article4, 200, false) (Drive S2, false) (Load S2, Article2, 150, false) (Drive T3, false) (Distribute T3, Article2, 150, false) (Drive S1, false) (Load S1, Article1, 150, false) (Drive T1, false) (Distribute T1, Article4, 200, false) (Drive T2, false) (Distribute T2, Article1, 150, false) ((0, 5) (5, 9) (9, 11) (11, 14) (14, 16) (16, 18) (18, 21) (21, 24) (24, 28) (28, 32) (32, 35) (35, 38))

4.2 Coordination of agents’ initial plans

To coordinate the initial plans, the coordinating agent must find the best combination, between the sets of possible plans generated by the agents, whose execution does not lead to any conflict. It starts by generating the initial population Pop ${}_{0}$ from the set of initial plans P ${}_{0}$ . Table 2 represents ten vectors (possible combinations) of the initial population Pop ${}_{0}$ as well as the value of the fitness function obtained for each one.

Table 2
Ten vectors (possible combinations) of initial population Pop ${}_{0}$

Vector	Plans of the vector	$F$ -value
V1	(P11, P25, P38)	F $=$ 0.125
V2	(P15, P28, P39)	F $=$ 0.16666667
V3	(P12, P27, P310)	F $=$ 0.14285714
V4	(P14, P21, P37)	F $=$ 0.2
V5	(P18, P26, P31)	F $=$ 0.25
V6	(P13, P23, P37)	F $=$ 0.5
V7	(P110, P28, P33)	F $=$ 0.33333333
V8	(P19, P23, P35)	F $=$ 1
V9	(P14, P23, P39)	F $=$ 0.2
V10	(P16, P29, P34)	F $=$ 0.14285714

Figure 3 demonstrates the evaluations of the initial population Pop ${}_{0}$ .

Figure 3.

Evaluation of the population Pop ${}_{0}$ .

After 30 generations here is the best-obtained vector (Fig. 4).

The plans of the best-obtained vector V ${}_{0}$ are presented in Table 3.

Table 3

The plans of the best-obtained vector V ${}_{0}$

Best-obtained vector V ${}_{0}$
V0 $=$ (P19, P23, P35)/
P10	(Drive S1, false) (Load S1, Article1, 100, false) (Drive S2, false) (Load S2, Article2, 150, false) (Drive T1, false) (Distribute T1, Article2, 150, false) (Drive T3, false) (Distribute T3, Article1, 100, false) (Drive S3, false) (Load S3, Article3, 50, false) (Drive T4, false) (Distribute T4, Article3, 50, false) ((0, 2) (2, 5) (5, 8) (8, 12) (12, 15) (15, 17) (17, 19) (19, 24) (24, 28) (28, 33) (33, 37) (37, 40))
P20	(Drive S4, false) (Load S4, Article4, 50, false) (Drive S1, false) (Load S1, Article1, 200, false) (Drive S3, false) (Load S3, Article3, 150, false) (Drive T5, false) (Distribute T5, Article4, 50, false) (Drive T2, false) (Distribute T2, Article3, 150, false) (Drive S2, false) (Load S2, Article2, 300, false) (Drive T6, false) (Distribute T6, Article1, 200, false) (Drive T7, false) (Distribute T7, Article2, 300, false) ((0, 2) (2, 4) (4, 8) (8, 11) (11, 14) (14, 16) (16, 19) (19, 22) (22, 24) (24, 27) (27, 30) (30, 36) (36, 40) (40, 43) (43, 45) (45, 49))
P30	(Drive S4, false) (Load S4, Article4, 200, false) (Drive S2, false) (Load S2, Article2, 150, false) (Drive T3, false) (Distribute T3, Article2, 150, false) (Drive S1, false) (Load S1, Article1, 150, false) (Drive T1, false) (Distribute T1, Article4, 200, false) (Drive T2, false) (Distribute T2, Article1, 150, false) ((0, 4) (4, 8) (8, 12) (12, 13) (13, 15) (15, 18) (18, 23) (23, 26) (26, 28) (28, 31) (31, 33) (33, 36))

Figure 4.

The best vector $V_{0}$ obtained by the coordinating agent.

The plans of the $V_{0}$ vector obtained don’t use the same resource simultaneously, which ensures that the execution of these plans doesn’t lead to any conflict. Figure 5 represents the plans of the vector $V_{0}$ obtained that the agents $A_{1}$ , $A_{2}$ , and $A_{3}$ must execute as well as the estimated periods for the execution of the actions on the resources (A1 plan in red, A2 plan in blue and A3 plan in green).

Figure 5.

Representation of plans $P_{{i0}}$ of combination $V_{0}$ obtained by the coordinating agent at instant $t_{0}$ .

Figure 6.

The best vector $V_{{t}}$ obtained by coordinating agent.

Table 4

Five new possible plans for each agent A ${}_{1}$ , A ${}_{2}$ , and A ${}_{3}$

P ${}_{\text{it}}$		Five possible new plans for A ${}_{\text{i}}$
P ${}_{\text{1t}}$	P11	(Drive S3, false) (Load S3, Article3, 50, false) (Drive T1, false) (Distribute T1, Article5, 400, false) /* new actions (Drive T4, false) (Distribute T4, Article3, 50, false) (Drive S5, false) (Load S5, Article5, 400, false) /* new actions ((22, 25) (25, 30) (30, 34) (34, 36) (36, 37) (37, 40) (40, 45) (45, 48))
	P12	(Drive S5, false) (Load S5, Article5, 400, false) /* new actions (Drive S3, false) (Load S3, Article3, 50, false) (Drive T1, false) (Distribute T1, Article5, 400, false) /* new actions (Drive T4, false) (Distribute T4, Article3, 50, false) ((22, 24) (24, 28) (28, 34) (34, 36) (36, 38) (38, 41) (41, 43) (43, 46))
	P13	(Drive S3, false) (Load S3, Article3, 50, false) (Drive T4, false) (Distribute T4, Article3, 50, false) (Drive S5, false) (Load S5, Article5, 400, false) /* new actions (Drive T1, false) (Distribute T1, Article5, 400, false) /* new actions ((22, 25) (25, 27) (27, 33) (33, 37) (37, 39) (39, 42) (42, 45) (45, 48))
	P14	(Drive T1, false) (Distribute T1, Article5, 400, false) /* new actions (Drive S3, false) (Load S3, Article3, 50, false) (Drive T4, false) (Distribute T4, Article3, 50, false) (Drive S5, false) (Load S5, Article5, 400, false) /* new actions ((22, 26) (26, 30) (30, 34) (34, 36) (36, 38) (38, 40) (40, 45) (45, 48))
	P15	(Drive S5, false) (Load S5, Article5, 400, false) /* new actions (Drive T1, false) (Distribute T1, Article5, 400, false) /* new actions (Drive S3, false) (Load S3, Article3, 50, false) (Drive T4, false) (Distribute T4, Article3, 50, false) ((22, 25) (25, 31) (31, 34) (34, 35) (35, 37) (37, 41) (41, 45) (45, 47))
P ${}_{\text{2t}}$	P21	(Drive S5, false) (Load S5, Article5, 100, false) /* new actions (Drive T5, false) (Distribute T5, Article4, 50, false) (Drive T9, false) (Distribute T9, Article5, 100, false) /* new actions (Drive S4, false) (Load S4, Article4, 50, false) ((22, 24) (24, 29) (29, 34) (34, 36) (36, 38) (38, 41) (41, 43) (43, 46))
	P22	(Drive S4, false) (Load S4, Article4, 50, false) (Load S5, Article5, 100, false) /* new actions (Drive T9, false) (Distribute T9, Article5, 100, false) /* new actions (Drive T5, false) (Distribute T5, Article4, 50, false) (Drive S5, false) ((22, 25) (25, 31) (31, 34) (34, 35) (35, 37) (37, 41) (41, 45) (45, 47))
	P23	(Drive S4, false) (Load S4, Article4, 50, false) (Drive T5, false) (Distribute T5, Article4, 50, false) /* new actions (Drive S5, false) (Load S5, Article5, 100, false) (Drive T9, false) (Distribute T9, Article5, 100, false) /* new actions ((22, 27) (27, 29) (29, 33) (33, 37) (37, 39) (39, 42) (42, 45) (45, 48))
	P24	(Drive S5, false) (Load S5, Article5, 100, false) (Drive T9, false) (Distribute T9, Article5, 100, false) (Drive T5, false) (Drive S4, false) (Load S4, Article4, 50, false) (Distribute T5, Article4, 50, false) ((22, 25) (25, 28) (28, 32) (32, 36) (36, 37) (37, 40) (40, 45) (45, 48))
	P25	(Drive S4, false) (Load S4, Article4, 50, false) (Drive S5, false) (Load S5, Article5, 100, false) /* new actions (Drive T9, false) (Distribute T9, Article5, 100, false) /* new actions (Drive T5, false) (Distribute T5, Article4, 50, false) ((22, 26) (26, 30) (30, 34) (34, 36) (36, 38) (38, 40) (40, 45) (45, 48))
P ${}_{\text{3t}}$	P31	(Drive S1, false) (Load S1, Article1, 150, false) (Drive T1, false) (Distribute T1, Article4, 200, false)

Table 4, continued
P ${}_{\text{it}}$		Five possible new plans for A ${}_{\text{i}}$
		(Drive T2, false) (Distribute T2, Article1, 150, false)(Drive S5, false) (Load S5, Article5, 100, false) /* new actions (Drive T8, false) (Distribute T8, Article5, 100, false) /* new actions ((22, 25) (25, 31) (31, 34) (34, 35) (35, 37) (37, 41) (41, 45) (45, 47) (47, 52) (52, 57))
	P32	(Drive S1, false) (Load S1, Article1, 150, false) (Drive T2, false) (Distribute T2, Article1, 150, false) (Drive S5, false) (Load S5, Article5, 100, false) /* new actions (Drive T8, false) (Distribute T8, Article5, 100, false) /* new actions (Drive T1, false) (Distribute T1, Article4, 200, false) ((22, 25) (25, 30) (30, 34) (34, 36) (36, 37) (37, 40) (40, 45) (45, 48) (48, 51) (51, 56))
	P33	(Drive S5, false) (Load S5, Article5, 100, false) /* new actions (Drive T1, false) (Distribute T1, Article4, 200, false) (Drive S1, false) (Load S1, Article1, 150, false) (Drive T2, false) (Distribute T2, Article1, 150, false) (Drive T8, false) (Distribute T8, Article5, 100, false) /* new actions ((22, 26) (26, 30) (30, 34) (34, 36) (36, 38) (38, 40) (40, 45) (45, 48) (48, 53) (53, 56))
	P34	(Drive S1, false) (Load S1, Article1, 150, false) (Drive T2, false) (Distribute T2, Article1, 150, false) (Drive S5, false) (Load S5, Article5, 100, false) /* new actions (Drive T8, false) (Distribute T8, Article5, 100, false) /* new actions (Drive T1, false) (Distribute T1, Article4, 200, false) ((22, 24) (24, 28) (28, 34) (34, 36) (36, 38) (38, 41) (41, 43) (43, 46) (46, 49) (49, 55))
	P35	(Drive S5, false) (Load S5, Article5, 100, false) /* new actions (Drive T1, false) (Distribute T1, Article4, 200, false) (Drive S1, false) (Load S1, Article1, 150, false) (Drive T2, false) (Distribute T2, Article1, 150, false) (Drive T8, false) (Distribute T8, Article5, 100, false) /* new actions ((22, 25) (25, 27) (27, 33) (33, 37) (37, 39) (39, 42) (42, 45) (45, 48) (48, 52) (52, 56))

4.3 Dynamic coordination of plans after a change

Suppose that during the execution of the initial plans $P_{{i0}}$ , which is in the initial combination $V_{0}$ rendered by the coordinating agent, a new article is introduced, at time $t$ , into a new stock point $S_{5}$ and that following the introduction of this new article, the following requests were proposed:

Req ${}_{11}=$ (S ${}_{5}$ , Art ${}_{5}$ , T1), 400, A ${}_{1}$ , False), Req ${}_{12}=$ (S ${}_{5}$ , Art ${}_{5}$ , T ${}_{9}$ ), 100, A ${}_{2}$ , False), Req ${}_{13}=$ (S ${}_{3}$ , Art ${}_{5}$ , T ${}_{8}$ ), 100, A ${}_{3}$ , False).

At the instant $t$ of the change, the new set of actions of each agent $A_{{i}}$ :

$\displaystyle\alpha_{\text{1t}}=\@setsize{\scriptsize}{9.5pt}{\viiipt}{% \@viiipt}\begin{array}[]{ll}\begin{array}[]{l}{\{}(\text{Drive}(\text{S}_{1}),% \text{True}),(\text{Load}(\text{S}_{1},\text{Art}_{1},100),\text{True}),\\ (\text{Drive}(\text{T}_{3}),\text{True}),(\text{Distribute}(\text{T}_{3},\text% {Art}_{1},100),\text{True}),\end{array}&\begin{array}[]{l}\text{/* The actions% carried out in the previous plan; they will not be}\\ \text{taken into account when generating new plans.}\end{array}\\ \begin{array}[]{l}(\text{Drive}(\text{S}_{3}),\text{False}),(\text{Load}(\text% {S}_{3},\text{Art}_{3},50),\text{False}),\\ (\text{Drive}(\text{T}_{4}),\text{False}),(\text{Distribute}(\text{T}_{4},% \text{Art}_{3},50),\text{False}),\end{array}&\begin{array}[]{l}\text{/* % Actions not carried out in the previous plan}\end{array}\\ \begin{array}[]{l}(\text{Drive}(\text{S}_{2}),\text{True}),(\text{Load}(\text{% S}_{2},\text{Art}_{2},150),\text{True}),\\ (\text{Drive}(\text{T}_{1}),\text{True}),(\text{Distribute}(\text{T}_{1},\text% {Art}_{2},150),\text{True}),\end{array}&\begin{array}[]{l}\text{/* The actions% carried out in the previous plan}\end{array}\\ \begin{array}[]{l}(\text{Drive}(\text{S}_{5}),\text{False}),(\text{Load}(\text% {S}_{5},\text{Art}_{5},400),\text{False}),\\ (\text{Drive}(\text{T}_{1}),\text{False}),(\text{Distribute}(\text{T}_{1},% \text{Art}_{5},400),\text{False}){\}}\end{array}&\begin{array}[]{l}\text{/* % The new actions generated by the changes}\end{array}\\ \end{array}$ $\displaystyle\alpha_{\text{2t}}=\@setsize{\scriptsize}{9.5pt}{\viiipt}{% \@viiipt}\begin{array}[]{ll}\begin{array}[]{l}{\{}(\text{Drive}(\text{S}_{3}),% \text{True}),(\text{Load}(\text{S}_{3},\text{Art}_{3},150),\text{True}),\\ (\text{Drive}(\text{T}_{2}),\text{True}),(\text{Distribute}(\text{T}_{2},\text% {Art}_{3},150),\text{True}),\end{array}&\begin{array}[]{l}\text{/* The actions% carried out in the previous plan; they will not be}\\ \text{taken into account when generating new plans.}\end{array}\\ \begin{array}[]{l}(\text{Drive}(\text{S}_{4}),\text{False}),(\text{Load}(\text% {S}_{4},\text{Art}_{4},50),\text{False}),\\ (\text{Drive}(\text{T}_{5}),\text{False}),(\text{Distribute}(\text{T}_{5},% \text{Art}_{4},50),\text{False}),\end{array}&\begin{array}[]{l}\text{/* % Actions not carried out in the previous plan}\end{array}\\ \begin{array}[]{l}(\text{Drive}(\text{S}_{2}),\text{True}),(\text{Load}(\text{% S}_{2},\text{Art}_{2},300),\text{True}),\\ (\text{Drive}(\text{T}_{7}),\text{True}),(\text{Distribute}(\text{T}_{7},\text% {Art}_{2},300),\text{True}),\\ (\text{Drive}(\text{S}_{1}),\text{True}),(\text{Load}(\text{S}_{1},\text{Art}_% {1},200),\text{True}),\\ (\text{Drive}(\text{T}_{6}),\text{True}),(\text{Distribute}(\text{T}_{6},\text% {Art}_{1},\text{200}),\text{True}),\end{array}&\begin{array}[]{l}\text{/* The % actions carried out in the previous plan}\end{array}\\ \begin{array}[]{l}(\text{Drive}(\text{S}_{5}),\text{False}),(\text{Load}(\text% {S}_{5},\text{Art}_{5},100),\text{False}),\\ (\text{Drive}(\text{T}_{9}),\text{False}),(\text{Distribute}(\text{T}_{9},% \text{Art}_{5},100),\text{False}){\}}\end{array}&\begin{array}[]{l}\text{/* % The new actions generated by the changes}\end{array}\\ \end{array}$ $\displaystyle\alpha_{\text{3t}}=\@setsize{\scriptsize}{9.5pt}{\viiipt}{% \@viiipt}\begin{array}[]{ll}\begin{array}[]{l}{\{}(\text{Drive}(\text{S}_{2}),% \text{True}),(\text{Load}(\text{S}_{2},\text{Art}_{2},150),\text{True}),\\ (\text{Drive}(\text{T}_{3}),\text{True}),(\text{Distribute}(\text{T}_{3},\text% {Art}_{2},150),\text{True}),\end{array}&\begin{array}[]{l}\text{/* The actions% carried out in the previous plan; they will not be}\\ \text{taken into account when generating new plans.}\end{array}\\ \begin{array}[]{l}(\text{Drive}(\text{S}_{1}),\text{False}),(\text{Load}(\text% {S}_{1},\text{Art}_{1},150),\text{False}),\\ (\text{Drive}(\text{T}_{2}),\text{False}),(\text{Distribute}(\text{T}_{2},% \text{Art}_{1},150),\text{False}),\end{array}&\begin{array}[]{l}\text{/* % Actions not carried out in the previous plan}\end{array}\\ \begin{array}[]{l}(\text{Drive}(\text{S}_{4}),\text{True}),(\text{Load}(\text{% S}_{4},\text{Art}_{4},200),\text{True}),\end{array}&\text{/* The actions % carried out in the previous plan}\\ \begin{array}[]{l}(\text{Drive}(\text{T}_{1}),\text{False}),(\text{Distribute}% (\text{T}_{1},\text{Art}_{4},200),\text{False}),\end{array}&\begin{array}[]{l}% \text{/* The new actions generated by the changes}\end{array}\\ \begin{array}[]{l}(\text{Drive}(\text{S}_{5}),\text{False}),(\text{Load}(\text% {S}_{5},\text{Art}_{5},100),\text{False}),\\ (\text{Drive}(\text{T}_{8}),\text{False}),(\text{Distribute}(\text{T}_{8},% \text{Art}_{5},100),\text{False}){\}}\end{array}&\begin{array}[]{l}\text{/* % The actions carried out in the previous plan; they will not be}\\ \text{taken into account when generating new plans.}\end{array}\\ \end{array}$

Table 5
The plans of the best-obtained vector V ${}_{\text{t}}$

	Best-obtained vector Vt
	Vt $=$ (P11, P27, P34)/
P1t	(Drive S3, false) (Load S3, Article3, 50, false) (Drive S5, false) (Load S5, Article5, 400, false) (Drive T1, false) (Distribute T1, Article5, 400, false) (Drive T4, false) (Distribute T4, Article3, 50, false) ((22, 24) (24, 28) (28, 34) (34, 36) (36, 38) (38, 41) (41, 43) (43, 46))
P2t	(Drive S4, false) (Load S4, Article4, 50, false) (Drive T5, false) (Distribute T5, Article4, 50, false) (Drive S5, false) (Load S5, Article5, 100, false) (Drive T9, false) (Distribute T9, Article5, 100, false) ((22, 25) (25, 28) (28, 32) (32, 36) (36, 37) (37, 40) (40, 45) (45, 48))
P3t	(Drive T1, false) (Distribute T1, Article4, 200, false) (Drive S1, false) (Load S1, Article1, 150, false) (Drive T2, false) (Distribute T2, Article1, 150, false) (Drive S5, false) (Load S5, Article5, 100, false) (Drive T8, false) (Distribute T8, Article5, 100, false) ((22, 25) (25, 27) (27, 33) (33, 37) (37, 39) (39, 42) (42, 45) (45, 48) (48, 52) (52, 56))

Figure 7.

Representation of the new plans of the new combination $V_{{t}}$ obtained by the coordinating agent at instant $t$ .

The new set of resources used by these actions are:

$\displaystyle R_{t}={\{}T_{1},T_{2},T_{3},T_{4},T_{5},T_{6},T_{7},T_{8},T_{9},% S_{1},S_{2},S_{3},S_{4},S_{5}{\}}$

The new set of possible plans for solving the new planning problem $\Pi_{t}$ for each agent $A_{{i}}$ : the $A_{{i}}$ agents affected by the change must generate their new set of $P_{{it}}$ plans in which they Load into consideration the new actions necessary to accomplish the new requests. For the generation of these new sets of $P_{{it}}$ plans, each agent is based on its new set of actions $\alpha_{{it}}$ which contains the set of old actions that are not executed from the old plan plus the new actions generated by the changes. Table 4 represents five possible new plans for each agent $A_{1}$ , $A_{2}$ , and $A_{3}$ .

The coordinating agent, in this case, must find a new combination, between the new sets of possible plans generated by the agents based on their new sets of actions, the execution of which will not suffer any conflict. To do this, it follows the same steps applied for the generation of the initial $V_{0}$ combination, knowing that:

(a)

The set of plans $P_{{t}}$ will be built by the new sets of plans $P_{{it}}$ generated by the agents having changed their sets of actions and by the set of possible plans generated based on the set of actions not yet executed at the instant $t$ of the change generated by the rest of the agents;

(b)

The initial population Pop0 will be generated based on this new set of plans $P_{{t}}$ ;

(c)

The resource set will be the new $R_{{t}}$ resource set.

Applying the approach with these new conditions gives the following vector (Fig. 6).

The plans of the best-obtained vector $V_{{t}}$ are presented in Table 5.

The plans of the obtained vector $V_{{t}}$ do not use the same resource simultaneously, which ensures that the execution of these plans does not lead to any conflict. This is valid despite the dynamic change of plans caused by unpredictable changes in the environment. Figure 7 represents the plans of the vector $V_{{t}}$ obtained that the agents $A_{1}$ , $A_{2}$ , and $A_{3}$ must execute as well as the estimated periods for the execution of the actions on the resources (plan $A_{1}$ in red, plan $A_{2}$ in blue, plan $A_{3}$ in green).

5. Conclusion

Distributed planning has enriched the field of planning as a result of exploiting the advantages of the multi-agent paradigm. However, the use of the latter introduced new challenges that are not present in the classic version of planning. Indeed, in distributed planning, each agent can make changes in its set of actions to be planned, in order to take into account the unpredictable changes in its environment. However, another problem arises concerning the coordination of these newly generated plans since new conflicts can be introduced during the execution of the new actions inserted in the new plans. These new conflicts are not taken into consideration in the coordination approaches before the execution of the plans, which explains the uselessness of these approaches with dynamic planning. As for the coordination approaches during the execution of the plans, even if in the latter, the agents can resolve the new conflicts each time they appear, this will, however, have the consequence of delaying them in the execution of their plans. In this work, we have proposed a new adaptive dynamic coordination approach with dynamic distributed planning, capable of considering the evolution of many of the conflicts caused by the change of agents’ plans. In this approach, a coordinating agent is in charge of finding the best combination, between the sets of possible plans generated by the agents, the execution of which does not lead to any conflict. This combination is reconstructed in a dynamic way, each time the agents decide to change their sets of possible plans to take into account the unpredictable changes in the environment. For each new combination, the coordinating agent takes into consideration the new conflicts that may be introduced following the execution of the new actions, inserted in the new plans. The proposed approach was applied to a concrete case study of a merchandise distribution system in order to show its effectiveness by taking into account the evolution of many conflicts caused by the change in agents’ plans. According to the obtained results, it would be interesting to incorporate the proposed approach into the JADE platform for supporting the coordination of generated agents’ plans dynamically.

Footnotes

Author’s Bios

	Nour El Houda Dehimi is Assistant professor of Computer Science at the Department of Computer Science and Mathematics at the university of Larbi Ben Mhidi of Oum El Bouaghi. Her areas of interest include mutli agent systems, software engineering, test multi agent systems, machine learning and Deep learning, security and cryptanalysis.
	Tahar Guerram is Assistant professor of Computer Science and Mathematics at the Department of Computer Science and Mathematics at the university of Larbi Ben Mhidi of Oum El Bouaghi. His areas of interest include mutli agent systems, machine learning. and complex systems.
	Zakaria Tolba is Ph.D. student at the Department of Computer Science and Mathematics at Larbi Tebessi University, Algeria. His areas of interest include machine learning applications in cryptography, security, privacy, cryptanalysis and mutli agent systems.

References

Ghallab

Nau

and Traverso

, Automated Planning Theory and Practice, Morgan Kaufmann Publishers, 2004.

Durfee

E.H.

, Distributed problem solving and planning, Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, MIT Press, 1999, 121–164.

Canu

and Mouaddib

A.I.

, Dynamic local interaction model: framework and algorithms, in: 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’11), 2011.

Beynier

Charpillet

Szer

and Mouaddib

A.I.

, Markov Decision Processes and Artificial Intelligence, chapter DEC-MDP/POMDP, Wiley, 2010, 321–359.

Shoham

and Leyton-Brown

, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge University Press, New York, 2009.

Dehimi

N.E.H.

Guerram

Zakaria

and Farid

, A novel distributed dynamic planning approach based on constraints satisfaction, Multiagent and Grid Systems – An International Journal 14 (2018), 243–261.

Georgeff

M.P.

, Communication and interaction in multi-agent planning, in: Proceedings of the Third National Conference on Artificial Intelligence (AAAI-83), August 1983, pp. 125–129.

Georgeff

M.P.

, Communication and interaction in multi-agent planning, Readings in Distributed Artificial Intelligence, A. Bond and L. Gasser, eds, Morgan Kaufmann Publishers, San Mateo, CA, 1988, pp. 200–204.

Stuart

C.J.

, An implementation of a multi-agent plan synchronizer, in: Proceedings of the Ninth International Joint Conference on Artificial Intelligence (IJCAI-85), Morgan Kaufmann Publishers, August 1985, pp. 1031–1033.

10.

DeLoach

Wood

F.M.

and Sparkman

H.C.

, Multiagent systems engineering, The International Journal of Software Engineering and Knowledge Engineering, June 2001.

11.

Bäckström

and Nebel

, Complexity results for SAS+ planning, Computational Intelligence 11 (1996), 625–655.

12.

Yang

Nau

D.S.

and Hendler

, Merging separately generated plans with restricted interactions, Computational Intelligence 8(4) (November 1992), 648–676. URL http://www.cs.sfu.ca/isa/pubs/index.html.

13.

Foulser

D.E.

and Yang

, Theory and algorithms for plan merging, Artificial Intelligence Journal 57(2–3) (1992), 143–182. URL http://www.cs.sfu.ca/isa/pubs.

14.

Briggs

, Modularity and Communication in Multi-Agent Planning, PhD thesis, University of Texas at Arlington, 1996. URL http://citeseer.nj.nec.com/briggs96modularity.html.

15.

Smith

R.G.

and Davis

, Frameworks for cooperation in distributed problem solving, IEEE Transactions on Systems, Man, and Cybernetics 11(1) (1980).

16.

Ciancarini

and Wooldridge

, Representing Agent Interaction Protocols in UML, in: Agent-Oriented Software Engineering, Springer, Berlin, 2001, pp. 121–140. http://www.fipa.org/docs/input/f-in-00077.

17.

Cammarata

McArthur

and Steeb

, Strategies of cooperation in distributed problem solving, in: Proceedings of the 8th International Joint Conference on Artificial Intelligence, 1983, pp. 767–770.

18.

Conry

S.E.

Kuwabara

Lesser

V.R.

and Meyer

R.A.

, Multistage negotiation in distributed constraint satisfaction, IEEE Transactions on Systems, Man, and Cybernetics, December 1991.

19.

Conry

S.E.

Meyer

R.A.

and Pope

R.P.

, Mechanisms for assessing the nonlocal impact of local decisions in distributed planning, Distributed Artificial Intelligence, Pitman Publishing: London and Morgan Kaufmann: San Mateo, CA, Volume II, 1989, 245–258.

20.

Pereau

J.C.

, Negotiation and game theory: The “underside” of an acceptable agreement, Negotiations 12(2) (2009), 37–51.

21.

Paletta

and Herrero

, A mas-based negotiation mechanism to deal with saturated conditions in distributed environments, in: International Conference on Agents and Artificial Intelligence (ICAART), 2010, pp. 1–7.

22.

Lavendelis

and Grundspenkis

, Multi-agent auction based simulation tool for an insurance policy market, Applied Computer Systems 15(1) (2014), 5–13.

23.

Rahwan

and Dignum

, Formal analysis of interest-based negotiation, Annals of Mathematics and Artificial Intelligence 55(3) (2009), 253–276.

24.

Bergenti

and Ricci

, Three approaches to the coordination of multiagent systems, in: 2002 ACM Symposium on Applied Computing (SAC), New York, NY, USA, ACM, 2002, pp. 367–372.

25.

Subagdja

and Tan

A.-H.

, On coordinating pervasive persuasive agents, in: International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2014, pp. 1467–1468.