A novel distributed dynamic planning approach based on constraint satisfaction

Abstract

In this work, we propose a new distributed dynamic planning approach based on constraint satisfaction, able to take into account the satisfaction of the constraints in all new versions of generated plans. Our approach is to generate, a new plan by each agent, whenever there is a change in its set of actions to plan caused by the unpredictable changes of the environment. This does not alter the satisfaction of the constraints taken into account during the generation of the initial plan. Our approach allows the integration of all the new actions, generated by the changes, in the new plan at the right place, which preserves the satisfaction of the constraints. For this, the approach uses genetic algorithm where the fitness function is defined on the basis of the constraints to be satisfied. The proposed approach is supported by a formal framework and applied on a concrete case study to illustrate and show its usefulness.

Keywords

Agent multi-agent system constraint satisfaction genetic algorithm planning dynamic planning

1. Introduction

Planning is a central issue in Artificial Intelligence, which the aim is to generate an action plan at a symbolic level from an initial state to a previously defined goal [1]. In its classical version, planning has been developed considerably because of the richness of the modeling languages and the efficiency of the systems of generation of the plans. Nevertheless, classical planning suffered from a weakness caused by the fact that it was based on two strong simplifying assumptions: the provision of perfect knowledge at all times of the state of the system and the effects of actions and The certainty that the changes in the state of the system arise solely from the execution of the actions of the plan. To overcome this weakness, the field of planning in the uncertain [2] has developed, proposing to integrate probabilistic actions and additive utility functions on the goals, leading to a family of approaches for planning based on decision theory [3] and using representational languages traditionally known in artificial intelligence: logic, constraints, or Bayesian networks. The use of these representational languages has caused a great deal of complexity in the algorithms for generating plans, the resolution of which has become a challenge for artificial intelligence community.

The extension of planning in multi-agent systems has resulted in distributed planning [4, 5] where the planning domain is distributed over a set of agents. These agents may be cooperative in the sense that they have a common overall objective and complementary capacities to achieve it or individualistic in the sense that they have individual objectives which they are able to achieve without external help. In both cases, the agents must be able to generate plans that allow the realization either of the sub-objectives necessary for a global objective or of the individual objectives. In the literature, there is some work on distributed planning. We cite, among others [6, 7, 8, 9].

Unlike object paradigm, the agent has a behavior characterized mainly by four properties [10]: autonomy, sensitivity, locality and flexibility. Indeed, the agent is not limited to reacting to the invocations of specific methods, as is often the case in the object paradigm, but also to any other observable change in its environment. Taking these changes into account automatically translates into a set of new actions that the agent must perform. The determination of these actions depends on the nature of the agent [11]. Indeed if, for example, the agent is rational, the actions to be determined must not be in opposition to the utility function of the agent, if the agent is with purpose, these actions must not be in opposition with the purpose of the agent, if the agent is reactive with model, these actions are predetermined by a set of rules. The behavior of the agent therefore has advantages, however, the new actions, introduced by the unpredictable change of its environment, can create a problem in distributed planning. This is especially noticeable when distributed planning is based on satisfying the constraints imposed by the system, by the agents or by the agents’ coordination.

Indeed, in classical planning, the set of actions to be planned is defined beforehand and does not undergo any change thus ensuring, a reliability of the generated plan regarding the constraints to consider when generating the latter, until the end of its execution. In distributed planning, however, each agent may have changes in the set of actions to be planned, as a result of unpredictable changes in the environment. Indeed, because of the changes, the plan that the agent was executing becomes obsolete because it does not take into account the new actions. The agent is therefore forced to generate a new plan in which it integrates the new actions. However, a problem arises with respect to the constraints to be satisfied. Indeed, the agent must integrate the new actions in the new plan without altering the satisfaction of the constraints taken into account during the generation of the initial plan.

This represents the focal point of our work, in which we propose a new distributed dynamic planning approach, able to take into account changes that may occur on the set of actions to plan and ensure the satisfaction of the constraints in the new generated plans. Our approach fits into the context of distributed planning for distributed plans (several planners, several executors) where each agent can produce and execute its own plan independently of other agents. In this type of planning, there is no overall plan. To ensure coordination between these plans, agents must satisfy, in addition to the constraints that they have, the necessary constraints to avoid conflict situations in all versions of generated plans. In the case of non-determination of constraints to avoid conflict situations, agents execute their plans (without prior coordination) and in the event of a conflict situation, they resolve it either by negotiation [12] or by arbitration (iterative coordination).

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 works in the literature have been proposed for distributed planning. We will focus on proposed work for dynamic distributed planning and proposed work for distributed planning based on constraint satisfaction. Distributed dynamic planning approach was proposed in paper [13, 15]. In paper [13], the authors proposed an approach of multi-agent (MA) plan repair (MA-REPAIR), based on multi-agent planning (MASTRIPS) as introduced in [14]. MA-STRIPS is an approach to planning for teamwork and coordination extending the classical STRIPS-based planning techniques. According to the MA-REPAIR approach, the multi-agent team computes a team plan using a fully decentralized MA-STRIPS planning algorithm, and subsequently executes the plan, while at the same time monitoring of possible failures of plan execution. Upon an occurrence of such a failure, the team stops execution and invokes a plan repair algorithm and fixes the failed joint plan in order to reach a joint goal state from the state in which the failure occurred.

In paper [15], the authors proposed prefix and suffix-based approaches to MA plan repair. Their work showed that these repairing approaches save communication in contrast to replanting from scratch in tightly coupled problems with action failures; however a research question which plan repairing techniques are more appropriate for which planning domains and problems remained unanswered. In this work, we generalize the prefix and suffix-based approaches from their work and present a study on how particular multi-agent plan repair techniques and particular parameterizations perform in different planning domains.

Although these works have considerably forwarded the domain by proposing novel strategies for distributed dynamic planning, they did not discuss the satisfaction of the constraints in the dynamic generation of new plans. Unlike these approaches, our approach is able to take into account unpredictable changes in the environment by generating new plans. This does not alter the satisfaction of the constraints taken into account during the generation of the initial plan.

Other constraint satisfaction based approaches for multi-agents planning systems were proposed [16, 17, 18, 19]. Here agents search cooperatively an optimal plan satisfying a predefined set of constraints distributed over them. Although this approach gives good results in the case of a small size problem and a static environment, the performance of these systems falls in the case of a large distributed problem with a dynamic environment. This is explained by the fact that, when searching for a global optimal plan, each agent maintaining a certain number of constraints has to share their values (values of constraints) every time with other agents of the system until reaching a global optimal plan satisfying all the constraints and generated cost verifies a predefined objective function. These interactions between agents generates a huge number of communications which negatively influences system’s performance, namely when the environment’s dynamicity is high. Unlike these approaches, our approach works even if the agents’ environment is dynamic. In addition, in our approach each agent generates its own plan independently of the other agents which minimizes the interactions between agents, attenuates the complexity of the distributed planning problem and hence improves the performance of the searched solution.

3. Proposed approach to distributed dynamic planning based on constraint satisfaction

According to our approach, each agent must generate the most appropriate plan, based on its set of actions that it has at a given moment, to satisfy all the set of constraints imposed by the system, by the agent or by the coordination between the agents. Each agent must regenerate a new plan, dynamically, whenever the its set of actions to plan changes. For each generated new plan, the agent integrates the new actions in the new plan while respecting the constraints to be satisfied. This approach is based on the following principle:

To achieve its goal, each agent can generate multiple plans with the same set of actions in a different order from one plan to another. Depending on the order of the actions, the agent may be very close to or far from satisfying the constraints. In this case, the satisfaction of all constraints allows establishing the best order of actions to be planned by the agent, whatever the changes occurring on the set of actions. The question that arises is: how can the agent recognize the best order that can enable him to meet the constraints? For this, we use genetic algorithm where the proposed fitness function is defined on the set of constraints that the agent must satisfy in the plan it must generate.

Initially at time $t_{0}$ , each agent, based on its set of actions it has at this moment, generates a set of randomly generated first plans (initial population) where each plan is a sequence of actions to be executed in a different order from the other plans. From the initial population, each agent, through the use of genetic algorithm, generates sub-populations with which it gets better scoring using the fitness function. This is repeated until the best plan is found. During the execution of this latter, if the agent is faced with a change, with respect to which new actions are to be executed, another plan will be dynamically generated to take these actions into consideration. In this new plan, the agent must establish the best order between the old unexecuted actions of the old plan and the new actions generated by the changes in order to satisfy all the constraints. The generation of the plans is repeated in a recursive manner, taking, each time, as a new initial state; the state in which the set of actions of the agent undergoes a change. The coordination between these plans is ensured by the satisfaction of the necessary constraints to avoid conflict situations in all of the generated plans versions. In case of non-determination of these constraints, agents must follow one of the iterative coordination mechanisms that can be either negotiation or arbitration. The generation of new plans is stopped when: (i) agents arrive at their final states. This is if the agents having different objectives; and (ii) Agents arrive at the final state of the system. This is if the agents have the same objective.

According to our approach, the planning problem at time $t$ is defined by a set of agents, the current state of the system and the coordination mechanism to be adopted in the case of non-determination of constraints to avoid conflict situations.

Each agent is defined by:

(iii) (i)
A set of actions to be executed at time $t$ . Each action is characterized by a state that indicates that this action is performed or not at time $t$ .
(ii)
A set of constraints to be satisfied during the generation of the plan at instant $t$ . Each constraint is defined by a set of variables, a fitness function and a coefficient that indicates the weight of the constraint.
(iii)
A fitness function to be optimized, by the agent, during the generation of its plan. It is defined on the basis of the constraint fitness functions.
(iv)
The current state of the agent.
(v)
An action review function that updates the agent’s actions at any time.

3.1 Formal framework of planning problem

According to our approach, the distributed planning problem could be defined as follows:

$\displaystyle\prod\nolimits_{t}=(N,S_{st},S_{sf},\text{Coordination})$

where

(iii) (i)
$N$ represents a set of $n$ agents $N=\{A_{1},A_{2},\ldots{},A_{n}\}$ ; each agent $A_{i}$ is defined by:

$\displaystyle A_{i}=\{\alpha_{it},C_{it},f\_A_{i},S_{it},S_{if},\text{Rev}\_% \alpha_{i}\}$

–
$\alpha_{it}$ represents the set of actions of agent $A_{i}$ at the instant $t$ , such that $\alpha_{it}=\{(\alpha_{ij},e)\}$ , $\alpha_{ij}$ represents the action $j$ of the agent $I$ , and $e$ represents a state showing if an action is executed or not at the instant $t$ .
–
$C_{it}$ represents the set of constraints to satisfy by agent $A_{i}$ . $C_{it}=\{(\textit{Var}\_C_{ij},f\_C_{ij},\textit{Coef}\_C_{ij})\}$ , $C_{ij}$ represents the constraint $j$ of agent $i$ , Var_ represents the set of variables defining the constraint $C_{ij}$ , $f\_C_{ij}$ represents the fitness function corresponding to the constraint $C_{ij}$ , $\textit{Coef}\_C_{ij}$ represents a coefficient defined on the constraint $C_{ij}$ , it indicates the importance of this constraint.
–
$f\_A_{i}$ represents the fitness function must be optimized by agent $A_{i}$ .

$\displaystyle f\_A_{i}=\sum_{j=1}^{n}(f\_C_{ij}*\textit{Coef}\_C_{ij})\bigg{/}% \sum_{j=1}^{n}\textit{Coef}\_C_{ij}$
–
$\text{Rev}\_\alpha_{i}$ : represents actions revision function that can determines the new action must be executed by the agent, according to its nature, to take into account the unpredictable changes of the environment.
–
$S_{it}$ : represents the current state of agent $i$ . This state changes, as and when, with the execution of the actions.
–
$S_{if}$ : represents the final state of agent $i$ .

(ii)
$S_{st}$ : represents the current state of the system. This state changes, as and when, with the execution of the actions, by the set of $N$ agents.
(iii)
$S_{sf}$ : represents the final state of the system.
(iv)
Coordination: represents the chosen coordination process to be used in the case of non-determination of constraints to avoid conflict situations.

Figure 1 shows a diagrammatic representation of the formal framework.

The solution to this distributed planning problem, at instant $t$ , is the plan $P_{t}$ defined by:

$\displaystyle P_{t}=\{P_{1t},P_{2t},\ldots,P_{nt}\}$

where $P_{it}$ represents the best plan of agent $A_{i}$ defined by the set of actions $\alpha_{it}$

Figure 1.
Diagrammatic representation of the formal framework.

3.2 Generation of initial plans $P_{i0}$

Each agent $A_{i}$ begins with the generation of an initial plan $P_{i0}$ in which it must establish the best order between its initial set of actions $\alpha_{i0}$ so as to satisfy all the constraints.

Agent $A_{i}$ , initially, generates an initial population $\textit{Pop}_{i0}$ , in which it constructs a large number of individuals. Each individual corresponds to a plan $P_{ij}$ (plan $j$ of agent $i$ ) which contains all the actions of the initial set of actions $\alpha_{i0}$ in a different order from the other plans. The initial population is generated in a random manner. In order to find a more efficient population $\textit{Pop}_{i1}$ which will better satisfy all the constraints, agent $A_{i}$ applies the following steps on the $\textit{Pop}_{i0}$ :

Firstly, each $P_{ij}$ of the $\textit{Pop}_{i0}$ population is evaluated. To do this, the value of the fitness function $f\_A_{i}$ is calculated.

Secondly, a selection step is applied. This step eliminates the worst plans of the $\textit{Pop}_{i0}$ and keeps only the best ones, according to their evaluation.

Thirdly, this step is to cross the previously selected plans to obtain the new $\textit{Pop}_{i1}$ population. Two plans (parents) are thus chosen to apply a crossing operator in order to obtain a new (descending) plan. There are many techniques of crossing, in our approach; we will use the “one point crossover”. This operator consists of recopying a part of parent 1 and a part of parent 2 to obtain a new individual. The parental separation point is called the crossing point. However, we must be careful not to repeat the same action (we do not recopy the actions already included in the plan), and not to forget actions (we add at the end the actions not taken into account).

Finally, to diversify the solutions over the generations, a mutation step is used. This mutation consists in randomly modifying a small part of a character in certain individuals of the new generation. This step is carried out with a very low probability, and consists, for example, in exchanging two consecutive actions in a plan.

From the population $\textit{Pop}_{i1}$ obtained, the steps described above will be reapplied, within the limit of the number of possible generations.

3.3 Dynamic generation of plans

Each agent $A_{i}$ begins the execution of its initial plan $P_{i0}$ . If during the execution of this plan, a change occurs in the agent’s environment at instant $t$ , in respect of which new actions are to be executed, another $P_{it}$ plan will be generated by this agent in a way to take these new actions into account. For the generation of this new $P_{it}$ plan, the agent applies the same steps applied for the generation of the initial plan $P_{i0}$ , knowing that:

(iii) (i)
The set of actions to be planned $\alpha_{it}$ will be equal to all the old actions not executed of the old plan plus the new actions generated by the changes. In the new plan $P_{it}$ the agent must establish the best order between the actions of the set $\alpha_{it}$ so as to satisfy all the constraints.
(ii)
The initial population $\textit{Pop}_{i0}$ will be generated on the basis of this new action set $\alpha_{it}$ .
(iii)
The initial state of the agent for this plan will be the state of the agent at time $t$ , $S_{it}$ .
(iv)
The initial system’s state for this plan will be the system’s state at time $t$ , $S_{st}$ .

Our approach is presented in Algorithm 1. The part that allows the generation of plans using genetic algorithm is realized by the function: $\text{Generation}\_P_{it}$ ( $\alpha_{it},n,F\_A_{i}$ ).

InputinputOutputoutput Generation $\text{Generation\_}P_{it}$ FnFunction: endDynamic generation of plansPlanning problem at $t_{0},\prod_{0}=(N,S_{0t},S_{sf}$ , Coordination) The possible number of generation $n$ ; Function: Generation_ $P_{it}(\alpha_{it}$ , $n$ , $F\_A_{i}$ ) Generate randomly the initial population $\textit{Pop}_{i0}$ on the basis of the set $\alpha_{it}$ $k:=$ 0; $k\leqslant n$ and $F\_A_{i}$ is not satisfied Evaluate each plan of the population according to $F\_A_{i}$ Select the most satisfactory plans in the population Produce new plans (children) from selected plans by crossing Mutation of the plans $k:=k+1$ ; $P_{it}$ // the best plan found at time $t$ $t:=t_{0}$ $S_{it}=S_{if}$ or $S_{st}=S_{sf}$ $P_{it}:=$ Generation_ $P_{it}(\alpha_{it},n,F\_A_{i})$ ; Execute the actions of $P_{it}$ // for each executed action $\alpha_{ij}$ , $\alpha_{ij}\rightarrow e=$ true; // $S_{it}$ and $S_{St}$ changes with the execution of the actions. // In case of non-determination of constraints, to avoid conflict situations, the agent $A_{i}$ must represents the chosen coordination process during the execution of the plans $P_{it}$ , endIfElseIfElseifdoelse ifelseend there is a change in the actions set $\alpha_{it}$ during the execution of the plan $P_{it}$ $t:=$ instant of change Rev_ $\alpha_{i}$ // actions revision function that can determines the new action must be executed by the agent, according to its nature, to take into account the unpredictable changes of the environment. $\alpha_{it}:=\alpha_{ij}$ (not executed actions where $\alpha_{ij}.e=$ false) U New actions; $S_{it}:=$ the agent state at instant $t$ of change; $S_{st}:=$ the system state at instant $t$ of change; // 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.
4. Case study

To validate our approach, we apply it to a well-known problem: The Dynamic Pick and Delivery Problem (DPDP) where the objective is to distribute articles (or items) $\textit{Art}_{j}$ stored in distribution points $S_{j}$ to a set of clients positioned at points $T_{k}$ . In each case, the system receives requests that agents must carry out through the execution of a set of actions. Each request is defined by the requesting client $T_{k}$ , the requested article $\textit{Art}_{j}$ , the point in which the article is stored $S_{j}$ , the quantity of the requested article as well as agent $A_{i}$ concerned by this request.

The choice of the case study was based on the fact that it allows the illustration of different stages of the proposed approach in a simple and clear way. In the following, we will at first time $t_{0}$ , show the generation of initial plans based on the initial action sets of the agents. In a second time $t$ , we will propose a change that will be applied during the execution of the generated plans for which new actions must be executed. In this second time, we will show how the agents generate new plans in which they integrate new actions while respecting the satisfaction of the constraints taken into account during the generation of the initial plan.

In this case study we have adopted three (3) reactive agents with model whose determination of actions to perform is predefined by a set of rules. In our case study, agents use two rules:

Rule 1:
for each request $R_{m}=((S_{j},\textit{Art}_{j},T_{k}),\textit{quantity},A_{i},\textit{False})$ , agent $A_{i}$ has to execute the following actions: (Move ( $S_{j}$ ), False), (Take ( $S_{j}$ , Art ${}_{j}$ , quantity), False), (Move ( $T_{k}$ ), False), (Delivery ( $T_{k}$ , Art ${}_{j}$ , quantity), False).
Rule 2:
When the battery of an agent $A_{i}$ is equal to 1/10 of its maximum load, the agent must execute the following action: Charg_batterie((Position Chargeur), False), which will load the agent’s battery.

We suppose that the three agents must satisfy the same constraints. The first constraint is to minimize distance the second constraint is to reduce number of obstacles in distribution.

The finesse function of each constraint is:

$\displaystyle f\_C_{1}=1\bigg{/}\sum\nolimits_{\begin{matrix}j=1\\ i=1\\ \end{matrix}}^{n}\textit{Dis}(\text{Point }i,\text{Point }j),$ $\displaystyle f\_C_{1}=1\bigg{/}\sum\nolimits_{\begin{matrix}j=1\\ i=1\\ \end{matrix}}^{n}\textit{Nbr\_Obs}(\text{Point }i,\text{Point }j)$

where Point $i$ , Point $j$ : may be a distribution point ( $S_{j}$ ) or a client point ( $T_{j}$ ).

The fitness functions must be optimized by each agent $A_{i}$

$\displaystyle f\_A_{i}=(f\_C_{1}\textit{Coef}\_C_{1})+(f\_C_{2}\textit{Coef}% \_C_{12})/(\textit{Coef}\_C_{1}+C\textit{Coef}\_C_{2})$

The system state is defined each time by the position of the clients $T_{k}$ , and the position of the distribution points $S_{i}$ and by the set of requests to be performed. The state of each agent is defined at each time by the agent’s position, the level of the battery and the rate of its actions performed. The final state of the system is

$\displaystyle S_{sf}=\{\text{Requests not satisfied}=\phi\}$

and the final state of each agent is

$\displaystyle S_{if}=\{\text{Actions not achieved}=\phi\}$

The coordination process chosen in the case of conflict events is the process of coordination by arbitration where the arbitrator or mediator has the various possible points of conflict and how to resolve them.

For the genetic algorithm, we chose the following values: Initial population size $=$ 20; Maximum number of generations $=$ 30; Mutation probability $=$ 2%, selection rate $=$ 80%.

The case study is developed using JADE platform [20].
4.1 The planning problem at the instant $t_{0}$

Suppose that at the instant $t_{0}$ we have seven (7) clients $T_{1},T_{2},\ldots,T_{7}$ and four (4) distribution points $S_{1},S_{2},\ldots,S_{4}$ (see Fig. 2).

Figure 2.

The system state at the instant $t_{0}$ .

At the instant $t_{0}$ the set of actions of each agent $A_{i}$ is:

$\alpha_{10}=$ {(Move ( $S_{1}$ ), False), (Take ( $S_{1}$ , Art ${}_{1}$ , 100), False), (Move ( $T_{3}$ ), False), (Delivery ( $T_{3}$ , Art ${}_{1}$ , 100), False), (Move ( $S_{3}$ ), False), (Take ( $S_{3}$ , Art ${}_{3}$ , 50), False), (Move ( $T_{4}$ ), False), (Delivery ( $T_{4}$ , Art ${}_{3}$ , 50), False), (Move ( $S_{2}$ ), False), (Take ( $S_{2}$ , Art ${}_{2}$ , 150), False), (Move ( $T_{1}$ ), False), (Delivery ( $T_{1}$ , Art ${}_{2}$ , 150), False)}

$\alpha_{20}=$ {(Move ( $S_{3}$ ), False), (Take ( $S_{3}$ , Art ${}_{3}$ , 150), False), (Move ( $T_{2}$ ), False), (Delivery ( $T_{2}$ , Art ${}_{3}$ , 150), False), (Move ( $S_{4}$ ), False), (Take ( $S_{4}$ , Art ${}_{4}$ , 50), False), (Move ( $T_{5}$ ), False), (Delivery ( $T_{5}$ , Art ${}_{4}$ , 50), False), (Move ( $S_{2}$ ), False), (Take ( $S_{2}$ , Art ${}_{2}$ , 300), False), (Move ( $T_{7}$ ), False), (Delivery ( $T_{7}$ , Art ${}_{2}$ , 300), False), (Move ( $S_{1}$ ), False), (Take ( $S_{1}$ , Art ${}_{1}$ , 200), False), (Move ( $T_{6}$ ), False), (Delivery ( $T_{6}$ , Art ${}_{1}$ , 200), False)}

$\alpha_{30}=$ {(Move ( $S_{2}$ ), False), (Take ( $S_{2}$ , Art ${}_{2}$ , 150), False), (Move ( $T_{3}$ ), False), (Delivery ( $T_{3}$ , Art ${}_{2}$ , 150), False), (Move ( $S_{1}$ ), False), (Take ( $S_{1}$ , Art ${}_{1}$ , 150), False), (Move ( $T_{2}$ ), False), (Delivery ( $T_{2}$ , Art ${}_{1}$ , 150), False), (Move ( $S_{4}$ ), False), (Take ( $S_{4}$ , Art ${}_{4}$ , 200), False), (Move ( $T_{1}$ ), False), (Delivery ( $T_{1}$ , Art ${}_{4}$ , 200), False)}

To generate an initial plan, each agent $A_{i}$ begins with the generation of an initial population Pop ${}_{i0}$ from its set of initial actions $\alpha_{i0}$ . Snippets 1–3 represent ten plans of the initial population of agents $A_{1},A_{2},A_{3}$ , respectively.

Plan 0

(Move S1, false)(Take S1, Article 1, 100, false)(Move S2, false)(Take S2, Article 2, 150, false)

(Move T3, false)(Delevry T3, Article 1, 100, false)(Move S3, false)

(Take S3, Article 3, 50, false)(Move T4, false)(Delevry T4, Article 3, 50, false)

(Move T1, false)(Delevry T1, Article 2, 150, false)

Plan 1

(Move S2, false)(Take S2, Article 2, 150, false)(Move S3, false)(Take S3, Article 3, 50, false)(Move S1, false)(Take S1, Article 1, 100, false)(Move T3, false)(Delevry T3, Article 1, 100, false)(Move T4, false)(Delevry T4, Article 3, 50, false)

(Move T1, false)(Delevry T1, Article 2, 150, false)

Plan 2

(Move S2, false)(Take S2, Article 2, 150, false)(Move S1, false)

(Take S1, Article 1, 100, false)(Move S3, false)(Take S3, Article 3, 50, false)

(Move T3, false)(Delevry T3, Article 1, 100, false)(Move T1, false)

(Delevry T1, Article 2, 150, false)(Move T4, false)(Delevry T4, Article 3, 50, false)

Plan 3

(Move S2, false)(Take S2, Article 2, 150, false)(Move T1, false)

(Delevry T1, Article 2, 150, false)(Move S3, false)(Take S3, Article 3, 50, false)

(Move S1, false)(Take S1, Article 1, 100, false)(Move T4, false)

(Delevry T4, Article 3, 50, false)(Move T3, false)(Delevry T3, Article 1, 100, false)

Snippet 1: Initial population of ten plans of agent

A_{1}

Plan 4

(Move S2, false)(Take S2, Article 2, 150, false)(Move T1, false)(Delevry T1, Article 2, 150, false)(Move S3, false) (Take S3, Article 3, 50, false)(Move S1, false)(Take S1, Article 1, 100, false)(Move T3, false)

(Delevry T3, Article 1, 100, false)(Move T4, false)(Delevry T4, Article 3, 50, false)

Plan 5

(Move S3, false)(Take S3, Article 3, 50, false)(Move S1, false)

(Take S1, Article 1, 100, false)(Move T3, false)(Delevry T3, Article 1, 100, false)

(Move T4, false)(Delevry T4, Article 3, 50, false)(Move S2, false)

(Take S2, Article 2, 150, false)(Move T1, false)(Delevry T1, Article 2, 150, false)

Plan 6

(Move S2, false)(Take S2, Article 2, 150, false)(Move S3, false)

(Take S3, Article 3, 50, false)(Move T4, false)(Delevry T4, Article 3, 50, false)

(Move S1, false)(Take S1, Article 1, 100, false)(Move T3, false)

(Delevry T3, Article 1, 100, false)(Move T1, false)(Delevry T1, Article 2, 150, false)

Plan 7

(Move S1, false)(Take S1, Article 1, 100, false)(Move S3, false)

(Take S3, Article 3, 50, false)(Move S2, false)(Take S2, Article 2, 150, false)

(Move T4, false)(Delevry T4, Article 3, 50, false)(Move T3, false)

(Delevry T3, Article 1, 100, false)(Move T1, false)(Delevry T1, Article 2, 150, false)

Plan 8

(Move S3, false)(Take S3, Article 3, 50, false)(Move T4, false)

(Delevry T4, Article 3, 50, false)(Move S1, false)(Take S1, Article 1, 100, false)

(Move T3, false)(Delevry T3, Article 1, 100, false)(Move S2, false)

(Take S2, Article 2, 150, false)(Move T1, false)(Delevry T1, Article 2, 150, false)

Plan 9

(Move S2, false)(Take S2, Article 2, 150, false)(Move S3, false)

(Take S3, Article 3, 50, false)(Move S1, false)(Take S1, Article 1, 100, false)

(Move T3, false)(Delevry T3, Article 1, 100, false)(Move T1, false)

(Delevry T1, Article 2, 150, false)(Move T4, false)(Delevry T4, Article 3, 50, false)

Snippet 1: continued.

Plan 0

(Move S1, false)(Take S1, Article 1, 200, false)(Move T6, false)

(Delevry T6, Article 1, 200, false)(Move S3, false)(Take S3, Article 3, 150, false)

(Move S4, false)(Take S4, Article 4, 50, false)(Move T2, false)

(Delevry T2, Article 3, 150, false)(Move S2, false)(Take S2, Article 2, 300, false)

(Move T5, false)(Delevry T5, Article 4, 50, false)(Move T7, false)

(Delevry T7, Article 2, 300, false)

Plan 1

(Move S3, false)(Take S3, Article 3, 150, false)(Move S2, false)

(Take S2, Article 2, 300, false)(Move S1, false)(Take S1, Article 1, 200, false)

(Move S4, false)(Take S4, Article 4, 50, false)(Move T2, false)

(Delevry T2, Article 3, 150, false)(Move T5, false)(Delevry T5, Article 4, 50, false)

(Move T6, false)(Delevry T6, Article 1, 200, false)(Move T7, false)

(Delevry T7, Article 2, 300, false)

Plan 2

(Move S2, false)(Take S2, Article 2, 300, false)(Move S3, false)(Take S3, Article 3, 150, false)

(Move T7, false)(Delevry T7, Article 2, 300, false)(Move T2, false)(Delevry T2, Article 3, 150, false)(Move S4, false)(Take S4, Article 4, 50, false)(Move S1, false)(Take S1, Article 1, 200, false)(Move T6, false)(Delevry T6, Article 1, 200, false)(Move T5, false)(Delevry T5, Article 4, 50, false)

Plan 3

(Move S3, false)(Take S3, Article 3, 150, false)(Move S1, false)

(Take S1, Article 1, 200, false)(Move T6, false)(Delevry T6, Article 1, 200, false)

(Move S4, false)(Take S4, Article 4, 50, false)(Move T5, false)

Snippet 2: Initial population of ten plans of agent

A_{2}

(Delevry T5, Article 4, 50, false)(Move S2, false)(Take S2, Article 2, 300, false)

(Move T7, false)(Delevry T7, Article 2, 300, false)(Move T2, false)

(Delevry T2, Article 3, 150, false)

Plan 4

(Move S3, false)(Take S3, Article 3, 150, false)(Move S1, false)

(Take S1, Article 1, 200, false)(Move T6, false)(Delevry T6, Article 1, 200, false)(Move S4, false)(Take S4, Article 4, 50, false)(Move T5, false)(Delevry T5, Article 4, 50, false)(Move T2, false)(Delevry T2, Article 3, 150, false)(Move S2, false)(Take S2, Article 2, 300, false)(Move T7, false)(Delevry T7, Article 2, 300, false)

Plan 5

(Move S3, false)(Take S3, Article 3, 150, false)(Move T2, false)(Delevry T2, Article 3, 150, false)(Move S4, false)(Take S4, Article 4, 50, false)(Move S1, false)

(Take S1, Article 1, 200, false)(Move S2, false)(Take S2, Article 2, 300, false)

(Move T6, false)(Delevry T6, Article 1, 200, false)(Move T7, false)

(Delevry T7, Article 2, 300, false)(Move T5, false)(Delevry T5, Article 4, 50, false)

Plan 6

(Move S3, false)(Take S3, Article 3, 150, false)(Move S2, false)(Take S2, Article 2, 300, false)(Move S1, false)(Take S1, Article 1, 200, false)

(Move S4, false)(Take S4, Article 4, 50, false)(Move T2, false)

(Delevry T2, Article 3, 150, false)(Move T5, false)(Delevry T5, Article 4, 50, false)

(Move T6, false)(Delevry T6, Article 1, 200, false)(Move T7, false)

(Delevry T7, Article 2, 300, false)

Plan 7

(Move S1, false)(Take S1, Article 1, 200, false)(Move S2, false)(Take S2, Article 2, 300, false)(Move S3, false)(Take S3, Article 3, 150, false)

(Move S4, false)(Take S4, Article 4, 50, false)(Move T7, false)

(Delevry T7, Article 2, 300, false)(Move T6, false)(Delevry T6, Article 1, 200, false)

(Move T2, false)(Delevry T2, Article 3, 150, false)(Move T5, false)(Delevry T5, Article 4, 50, false)

Plan 8

(Move S1, false)(Take S1, Article 1, 200, false)(Move S4, false)(Take S4, Article 4, 50, false)(Move S2, false)(Take S2, Article 2, 300, false)

(Move T7, false)(Delevry T7, Article 2, 300, false)(Move T5, false)

(Delevry T5, Article 4, 50, false)(Move S3, false)(Take S3, Article 3, 150, false)

(Move T6, false)(Delevry T6, Article 1, 200, false)(Move T2, false)

(Delevry T2, Article 3, 150, false)

Plan 9

(Move S1, false)(Take S1, Article 1, 200, false)(Move S2, false)

(Take S2, Article 2, 300, false)(Move S3, false)(Take S3, Article 3, 150, false)

(Move T2, false)(Delevry T2, Article 3, 150, false)(Move S4, false)

(Take S4, Article 4, 50, false)(Move T5, false)(Delevry T5, Article 4, 50, false)

(Move T6, false)(Delevry T6, Article 1, 200, false)(Move T7, false)

(Delevry T7, Article 2, 300, false)

Snippet 2: continued.

Plan 0

(Move S2, false)(Take S2, Article 2, 150, false)(Move S1, false)

(Take S1, Article 1, 150, false)(Move T2, false)(Delevry T2, Article 1, 150, false)

(Move S4, false)(Take S4, Article 4, 200, false)(Move T1, false)

(Delevry T1, Article 4, 200, false)(Move T3, false)(Delevry T3, Article 2, 150, false)

Plan 1

(Move S2, false)(Take S2, Article 2, 150, false)(Move S1, false)

(Take S1, Article 1, 150, false)(Move S4, false)(Take S4, Article 4, 200, false)

(Move T2, false)(Delevry T2, Article 1, 150, false)(Move T3, false)

(Delevry T3, Article 2, 150, false)(Move T1, false)(Delevry T1, Article 4, 200, false)

Plan 2

(Move S4, false)(Take S4, Article 4, 200, false)(Move S1, false)

(Take S1, Article 1, 150, false)(Move S2, false)(Take S2, Article 2, 150, false)

(Move T2, false)(Delevry T2, Article 1, 150, false)(Move T3, false)

(Delevry T3, Article 2, 150, false)(Move T1, false)(Delevry T1, Article 4, 200, false)

Plan 3

(Move S1, false)(Take S1, Article 1, 150, false)(Move S2, false)

(Take S2, Article 2, 150, false)(Move S4, false)(Take S4, Article 4, 200, false)

(Move T2, false)(Delevry T2, Article 1, 150, false)(Move T3, false)

(Delevry T3, Article 2, 150, false)(Move T1, false)(Delevry T1, Article 4, 200, false)

Plan 4

(Move S1, false)(Take S1, Article 1, 150, false)(Move S2, false)

(Take S2, Article 2, 150, false)(Move T3, false)(Delevry T3, Article 2, 150, false)

(Move S4, false)(Take S4, Article 4, 200, false)(Move T2, false)

(Delevry T2, Article 1, 150, false)(Move T1, false)(Delevry T1, Article 4, 200, false)

Plan 5

(Move S2, false)(Take S2, Article 2, 150, false)(Move S4, false)

(Take S4, Article 4, 200, false)(Move S1, false)(Take S1, Article 1, 150, false)

(Move T1, false)(Delevry T1, Article 4, 200, false)(Move T2, false)

(Delevry T2, Article 1, 150, false)(Move T3, false)(Delevry T3, Article 2, 150, false)

Plan 6

(Move S2, false)(Take S2, Article 2, 150, false)(Move T3, false)(Delevry T3, Article 2, 150, false)(Move S1, false)(Take S1, Article 1, 150, false)

(Move S4, false)(Take S4, Article 4, 200, false)(Move T1, false)

(Delevry T1, Article 4, 200, false)(Move T2, false)(Delevry T2, Article 1, 150, false)

Plan 7

(Move S2, false)(Take S2, Article 2, 150, false)(Move S4, false)

(Take S4, Article 4, 200, false)(Move T1, false)(Delevry T1, Article 4, 200, false)

(Move S1, false)(Take S1, Article 1, 150, false)(Move T3, false)

(Delevry T3, Article 2, 150, false)(Move T2, false)(Delevry T2, Article 1, 150, false)

Plan 8

(Move S4, false)(Take S4, Article 4, 200, false)(Move T1, false)

(Delevry T1, Article 4, 200, false)(Move S2, false)(Take S2, Article 2, 150, false)

(Move T3, false)(Delevry T3, Article 2, 150, false)(Move S1, false)

(Take S1, Article 1, 150, false)(Move T2, false)(Delevry T2, Article 1, 150, false)

Plan 9

(Move S4, false)(Take S4, Article 4, 200, false)(Move T1, false)

(Delevry T1, Article 4, 200, false)(Move S2, false)(Take S2, Article 2, 150, false)

(Move T3, false)(Delevry T3, Article 2, 150, false)(Move S1, false)

(Take S1, Article 1, 150, false)(Move T2, false)(Delevry T2, Article 1, 150, false)

Snippet 3: Initial population of ten plans of agent

A_{3}

In order to find a better $\textit{Pop}_{i1}$ population that will better satisfy all the constraints, agent $A_{i}$ applies the following steps on the population $\textit{Pop}_{i0}$ :

(iii) (i)

Evaluation: this step consists in calculating the fitness function $f\_A_{i}$ of each plan $P_{ij}$ of the initial population $\textit{Pop}_{i0}$ . Snippets 4–6 represent the evaluation of ten plans of the initial population of agents $A_{1}$ , $A_{2}$ , $A_{3}$ respectively.

(ii)

Selection: this step is to eliminate the worst plans of the $\textit{Pop}_{i0}$ and to keep only the best ones according to their evaluation.

(iii)

Crossing: this step consists of crossing the previously selected plans to obtain the new $\textit{Pop}_{i1}$ population.

Snippet 4: Evaluation of ten plans of the initial population of agent $A_{1}$ .
Plan 0	$F\_C_{1}=$ 3.6583253244223507E $-$ 4	$F\_C_{2}=$ 0.01	$F\_A=$ 4.531462743252149E $-$ 5
Plan 1	$F\_C_{1}=$ 6.323401357583406E $-$ 4	$F\_C_{2}=$ 0.01	$F\_A=$ 7.781241907869489E $-$ 5
Plan 2	$F\_C_{1}=$ 5.897754111634356E $-$ 4	$F\_C_{2}=$ 0.01	$F\_A=$ 7.265073595371868E $-$ 5
Plan 3	$F\_C_{1}=$ 6.323401357583406E $-$ 4	$F\_C_{2}=$ 0.01	$F\_A=$ 7.781241907869489E $-$ 5
Plan 4	$F\_C_{1}=$ 5.77533185332251E $-$ 4	$F\_C_{2}=$ 0.027777777777777776	$F\_A=$ 7.181835083820729E $-$ 5
Plan 5	$F\_C_{1}=$ 3.9932094414700796E $-$ 4	$F\_C_{2}=$ 0.011363636363636364	$F\_A=$ 4.9480429438769634E $-$ 5
Plan 6	$F\_C_{1}=$ 4.143145586936494E $-$ 4	$F\_C_{2}=$ 0.01	$F\_A=$ 5.1258392381236724E $-$ 5
Plan 7	$F\_C_{1}=$ 4.143145586936494E $-$ 4	$F\_C_{2}=$ 0.01	$F\_A=$ 5.1258392381236724E $-$ 5
Plan 8	$F\_C_{1}=$ 3.7730500878527685E $-$ 4	$F\_C_{2}=$ 0.00980392156862745	$F\_A=$ 4.6713680801655446E $-$ 5
Plan 9	$F\_C_{1}=$ 3.689321454479055E $-$ 4	$F\_C_{2}=$ 0.011111111111111112	$F\_A=$ 4.573685774725651E $-$ 5

Snippet 5: Evaluation of ten plans of the initial population of agent $A_{2}$ .
Plan 0	$F\_C_{1}=$ 2.1472768420252827E $-$ 4	$F\_C_{2}=$ 0.00641025641025641	$F\_A=$ 2.6618050860961023E $-$ 5
Plan 1	$F\_C_{1}=$ 2.6595279043151345E $-$ 4	$F\_C_{2}=$ 0.00641025641025641	$F\_A=$ 3.290282547228916E $-$ 5
Plan 2	$F\_C_{1}=$ 3.116105495296216E $-$ 4	$F\_C_{2}=$ 0.00641025641025641	$F\_A=$ 3.8483634339865544E $-$ 5
Plan 3	$F\_C_{1}=$ 2.705071325893138E $-$ 4	$F\_C_{2}=$ 0.00641025641025641	$F\_A=$ 3.346039186200589E $-$ 5
Plan 4	$F\_C_{1}=$ 3.8486730545899116E $-$ 4	$F\_C_{2}=$ 0.006756756756756757	$F\_A=$ 4.743296349885949E $-$ 5
Plan 5	$F\_C_{1}=$ 3.385426476167838E $-$ 4	$F\_C_{2}=$ 0.006535947712418301	$F\_A=$ 4.177685179203307E $-$ 5
Plan 6	$F\_C_{1}=$ 2.6005714273620996E $-$ 4	$F\_C_{2}=$ 0.008264462809917356	$F\_A=$ 3.2253413988792484E $-$ 5
Plan 7	$F\_C_{1}=$ 2.2290002356262293E $-$ 4	$F\_C_{2}=$ 0.006024096385542169	$F\_A=$ 2.7607127328053214E $-$ 5
Plan 8	$F\_C_{1}=$ 4.1487733971837395E $-$ 4	$F\_C_{2}=$ 0.011111111111111112	$F\_A=$ 5.138004806751753E $-$ 5
Plan 9	$F\_C_{1}=$ 3.0030781367048617E $-$ 4	$F\_C_{2}=$ 0.008333333333333333	$F\_A=$ 3.7203303427402686E $-$ 5

Snippet 6: Evaluation of ten plans of the initial population of agent $A_{3}$ .
Plan 0	$F\_C_{1}=$ 6.186662433765832E $-$ 4	$F\_C_{2}=$ 0.020833333333333332	$F\_A=$ 7.676338940901854E $-$ 5
Plan 1	$F\_C_{1}=$ 5.678571076814047E $-$ 4	$F\_C_{2}=$ 0.020833333333333332	$F\_A=$ 7.050171962903428E $-$ 5
Plan 2	$F\_C_{1}=$ 6.662723350575081E $-$ 4	$F\_C_{2}=$ 0.020833333333333332	$F\_A=$ 8.262344529228388E $-$ 5
Plan 3	$F\_C_{1}=$ 6.186662433765832E $-$ 4	$F\_C_{2}=$ 0.020833333333333332	$F\_A=$ 7.676338940901854E $-$ 5
Plan 4	$F\_C_{1}=$ 6.662723350575081E $-$ 4	$F\_C_{2}=$ 0.020833333333333332	$F\_A=$ 8.262344529228388E $-$ 5
Plan 5	$F\_C_{1}=$ 4.727751919925607E $-$ 4	$F\_C_{2}=$ 0.020833333333333332	$F\_A=$ 5.876351580944249E $-$ 5
Plan 6	$F\_C_{1}=$ 6.662723350575081E $-$ 4	$F\_C_{2}=$ 0.020833333333333332	$F\_A=$ 8.262344529228388E $-$ 5
Plan 7	$F\_C_{1}=$ 6.662723350575081E $-$ 4	$F\_C_{2}=$ 0.020833333333333332	$F\_A=$ 8.262344529228388E $-$ 5
Plan 8	$F\_C_{1}=$ 4.290402414243473E $-$ 4	$F\_C_{2}=$ 0.020833333333333332	$F\_A=$ 5.335533116805599E $-$ 5
Plan 9	$F\_C_{1}=$ 6.967986411053363E $-$ 4	$F\_C_{2}=$ 0.02	$F\_A=$ 8.6347742765399E $-$ 5

The steps described above will be reapplied on the obtained population $\textit{Pop}_{i1}$ , within the limit of the number of possible generations specified by the program (in our case $k=$ 30). This, in order to obtain a population in which there is a plan that completely satisfies all the constraints. This plan will be considered as the initial plan $p_{i0}$ that agent $A_{i}$ must execute. If this plan is not obtained within the limits of possible generations, the best plan obtained in the last generation ( $\textit{Pop}_{ik}$ ) will be taken as the initial plan. After 30 generations the best plans are obtained (see Snippet 7).

P_{10}=

(Move S2, false)(Take S2, Article 2, 150, false)(Move T1, false)

(Delevry T1, Article 2, 150, false)(Move S1, false)(Take S1, Article 1, 100, false)

(Move T3, false)(Delevry T3, Article 1, 100, false)(Move S3, false)(Take S3, Article 3, 50, false)

(Move T4, false)(Delevry T4, Article 3, 50, false)

F\_C_{1}=

6.323401357583406E

-

F\_C_{2}=

0.01

F\_A=

7.781241907869489E

-

P_{20}=

(Move S1, false)(Take S1, Article 1, 200, false)(Move S3, false)

(Take S3, Article 3, 150, false)(Move T2, false)(Delevry T2, Article 3, 150, false)

(Move S2, false)(Take S2, Article 2, 300, false)(Move T6, false)

(Delevry T6, Article 1, 200, false)(Move T7, false)(Delevry T7, Article 2, 300, false)

(Move S4, false)(Take S4, Article 4, 50, false)(Move T5, false)(Delevry T5, Article 4, 50, false)

F\_C_{1}=

3.116105495296216E

-

F\_C_{2}=

0.00641025641025641

F\_A=

3.8483634339865544E

-

P_{30}=

(Move S4, false)(Take S4, Article 4, 200, false) (Move S2, false)(Take S2, Article 2, 150, false)(Move T3, false)(Delevry T3, Article 2, 150, false) (Move S1, false)(Take S1, Article 1, 150, false)(Move T1, false)(Delevry T1, Article 4, 200, false)

(Move T2, false)(Delevry T2, Article 1, 150, false)

F\_C_{1}=

6.662723350575081E

-

F\_C_{2}=

0.020833333333333332

F\_A=

8.262344529228388E

-

Snippet 7: The best plans obtained by agents

A_{1}

A_{2}

A_{3}

Figure 3 shows the best plans obtained by agents $A_{1}$ , $A_{2}$ $A_{3}$ (plan of $A_{1}$ in red, plan of $A_{2}$ in blue, and plan of $A_{3}$ in green).

Figure 3.

Representation of the best plans obtained by agents $A_{1}$ , $A_{2}$ , $A_{3}$ .

4.2 The planning problem at the instant

t

of the change

Let us suppose that during the execution of the initial plans by each agent, at instant $t$ , a new article is introduced into a new distribution point $S_{5}$ and that following the introduction of this new article the following requests have been made:

$\displaystyle R_{11}=(S_{5},Art_{5},T_{1}),400,A_{1},\textit{False})$ $\displaystyle R_{12}=(S_{5},Art_{5},T_{9}),100,A_{2},\textit{False})$ $\displaystyle R_{13}=(S_{5},Art_{5},T_{8}),100,A_{3},\textit{False})$

The agents concerned by this change must generate a new plan in which they take into account the new actions necessary to fulfill the new requests. For the generation of this new $P_{it}$ plan, the agent applies the same applied steps for the generation of the initial plan $P_{i0}$ , knowing that:

The action set of each agent $\alpha_{it}$ will be equal to the set of old actions not executed of the old plan plus the new actions generated by the changes. The actions carried out in the previous plan are marked in blue. They will not be taken into account when generating new plans. The actions not carried out in the previous plan are marked in black. The new actions generated by the changes are marked in red:

$\alpha_{1t}=$ {[rgb]0.00,0.00,1.00(Move ( $S_{1}$ ), True), (Take ( $S_{1}$ , Art ${}_{1}$ , 100), True), (Move ( $T_{3}$ ), True), (Delivery ( $T_{3}$ , Art ${}_{1}$ , 100), True), (Move ( $S_{3}$ ), False), (Take ( $S_{3}$ , Art ${}_{3}$ , 50), False), (Move ( $T_{4}$ ), False), (Delivery ( $T_{4}$ , Art ${}_{3}$ , 50), False), [rgb]0.00,0.00,1.00(Move ( $S_{2}$ ), True), (Take ( $S_{2}$ , Art ${}_{2}$ , 150), True), (Move ( $T_{1}$ ), True), (Delivery ( $T_{1}$ , Art ${}_{2}$ , 150), True), [rgb]1.00,0.00,0.00(Move ( $S_{5}$ ), False), (Take ( $S_{5}$ , Art ${}_{5}$ , 400), False), (Move ( $T_{1}$ ), False), (Delivery ( $T_{1}$ , Art ${}_{5}$ , 400), False)}

$\alpha_{2t}=$ {[rgb]0.00,0.00,1.00(Move ( $S_{3}$ ), True), (Take ( $S_{3}$ , Art ${}_{3}$ , 150), True), (Move ( $T_{2}$ ), True), (Delivery ( $T_{2}$ , Art ${}_{3}$ , 150), True), (Move ( $S_{4}$ ), False), (Take ( $S_{4}$ , Art ${}_{4}$ , 50), False), (Move ( $T_{5}$ ), False), (Delivery ( $T_{5}$ , Art ${}_{4}$ , 50), False), [rgb]0.00,0.00,1.00(Move ( $S_{2}$ ), True), (Take ( $S_{2}$ , Art ${}_{2}$ , 300), True), (Move ( $T_{7}$ ), True), (Delivery ( $T_{7}$ , Art ${}_{2}$ , 300), True), (Move ( $S_{1}$ ), True), (Take ( $S_{1}$ , Art ${}_{1}$ , 200), True), (Move ( $T_{6}$ ), True), (Delivery ( $T_{6}$ , Art ${}_{1}$ , 200), True), [rgb]1.00,0.00,0.00(Move ( $S_{5}$ ), False), (Take ( $S_{5}$ , Art ${}_{5}$ , 100), False), (Move ( $T_{9}$ ), False), (Delivery ( $T_{9}$ , Art ${}_{5}$ , 100), False)}

$\alpha_{3t}=$ {[rgb]0.00,0.00,1.00(Move ( $S_{2}$ ), True), (Take ( $S_{2}$ , Art ${}_{2}$ , 150), True), (Move ( $T_{3}$ ), True), (Delivery ( $T_{3}$ , Art ${}_{2}$ , 150), True), (Move ( $S_{1}$ ), False), (Take ( $S_{1}$ , Art ${}_{1}$ , 150), False), (Move ( $T_{2}$ ), False), (Delivery ( $T_{2}$ , Art ${}_{1}$ ,150), False), [rgb]0.00,0.00,1.00(Move ( $S_{4}$ ), True), (Take ( $S_{4}$ , Art ${}_{4}$ , 200), True), (Move ( $T_{1}$ ), False), (Delivery ( $T_{1}$ , Art ${}_{4}$ , 200), False), [rgb]1.00,0.00,0.00(Move ( $S_{5}$ ), False), (Take ( $S_{5}$ , Art ${}_{5}$ , 100), False), (Move ( $T_{8}$ ), False), (Delivery ( $T_{8}$ , Art ${}_{5}$ , 100), False)}

The initial population, $\textit{Pop}_{i0}$ of plans of each agent $A_{i}$ will be generated based on its set of actions $\alpha_{it}$ The initial state of each agent for this plan will be the agent state at the instant $t$ , $S_{it}$ . The initial state of the system for this plan will be the system state at the instant $t$ , $S_{it}$ .

Applying of our approach providing these new conditions gives the following plans (see Snippet 8). In these new plans, the new actions (marked in red) have been integrated in the right place to respect the satisfaction of the constraints taken into account during the generation of the initial plan.

P_{1t}=

(Move S3, false)(Take S3, Article 3, 50, false) (Move S5, false)

(Take S5, Article 5, 400, false)(Move T1, false)(Delevry T1, Article 5, 400, false)

(Move T4, false)(Delevry T4, Article 3, 50, false)

F\_C_{1}=

7.323401357583406E

-

F\_C_{2}=

0.01

F\_A=

6.381241907869489E

-

P_{2t}=

(Move S4, false)(Take S4, Article 4, 50, false) (Move T5, false) (Delevry T5, Article 4, 50, false)(Move S5, false)(Take S5, Article 5, 100, false) (Move T9, false) (Delevry T9, Article 5, 100, false)

F\_C_{1}=

4.165105495296216E

-

F\_C_{2}=

0.00961025641025641

F\_A=

2.8483634339865544E

-

P_{3t}=

(Move T1, false)(Delevry T1, Article 4, 200, false)(Move S1, false)

(Take S1, Article 1, 150, false) (Move T2, false)(Delevry T2, Article 1, 150, false)

(Move S5, false)(Take S5, Article 5, 100, false)(Move T8, false)(Delevry T8, Article 5, 100, false)

F\_C_{1}=

8.092723350575081E

-

F\_C_{2}=

0.020833333333333332

F\_A=

5.295344529228388E

-

Snippet 8: The best new plans obtained by agents

A_{1}

A_{2}

and

A_{3}

Figure 4 shows the best new plans obtained by agents $A_{1}$ , $A_{2}$ and $A_{3}$ (plan of $A_{1}$ in red, plan of $A_{2}$ in blue, and plan of $A_{3}$ in green).

Figure 4.

Representation of the best new plans obtained by agents $A_{1}$ , $A_{2}$ , $A_{3}$ .

4.3 Discussion of the results

The obtained results show that the proposed approach offers several advantages, namely taking into account of changes that may occur on all the actions to be planned by each agent following the taking into account of the changes observable in its environment. The second advantage is that the constraints are respected in every version of the generated plan. Indeed, the proposed approach allows the integration of the new actions in the correct order so as not to alter the satisfaction of the constraints taken into account during the generation of the initial plan. Another interesting advantage of the proposed approach is it avoids returning to the zero point for the generation of a new plan since each agent takes into consideration only the old actions not executed of the old plan to which it adds new actions generated by the changes. Also, the use of genetic algorithm allows ensuring that generated plans are the best ones and computed in reasonable time. Moreover and besides that the proposed approach is independent of agents’ architecture, each agent generates its own plans independently of the other agents, which minimizes the interactions between agents, attenuates the complexity of the distributed planning problem and hence improves the performance of the searched solution.

5. Conclusion

Agent-oriented technology has become a full-fledged paradigm of software engineering with its own methodological elements in terms of design and programming. The success of this paradigm, in relation to other paradigms, rests on its own functional and behavioral characteristics such as autonomy, pro-activity, sensitivity, flexibility, etc. The extension of planning in multi-agent systems has resulted in distributed planning. This extension has enriched the field of planning following the exploitation of the advantages of the multi-agent paradigm. However, the use of the latter has introduced new non-existent challenges in the classic version of planning. This is especially noticeable when distributed planning is based on satisfying of the constraints imposed by the system, by the agents or by the agents’ coordination.

Indeed, in distributed planning, each agent can make changes in its set of actions to plan, in order to take into account the unpredictable changes in its environment. The agent is therefore forced to generate a new plan in which it integrates the new actions. However, a problem arises with respect to the constraints to be satisfied. Indeed, the agent must integrate the new actions in the new plan without altering the satisfaction of the constraints taken into account during the generation of the initial plan. In this paper, a new distributed dynamic planning approach is proposed, able to take into account the changes that can occur on the set of actions to plan and ensure the satisfaction of the constraints in the new generated plans.

According to our approach, each agent starts by generating its initial plan, in which it establishes the best order, of the set of initial actions it must execute in order to satisfy the set of constraints in the most satisfactory way. During the execution of the generated plan, if the agent is faced with a change, against which new actions must be executed, another plan will be generated dynamically to take these actions into account. In this new plan, the agent must establish the best order between the old non-executed actions of the old plan and the new actions generated by the changes in order to satisfy all the constraints. The generation of the plans is repeated in a recursive manner, taking, each time, as a new initial state; the state in which the set of actions of the agent undergoes a change. The proposed approach is validated on a concrete case study: DPDP. According to the obtained results, it would be interesting to integrate our approach into the agent development platforms as a separate library to support the planning process.

As future work, we plan in the short term to study the computation time of the generated plans in the objective to optimize it. One way to attain this aim is to consider soft and hard constraints which allow obtaining approximate solutions with less response time.

Footnotes

Authors’ Bios

	Nour El Houda Dehimi studies Doctor of Computer Science at the Department of Computer Science and Mathematics at the university of Larbi Ben Mhidi of Oum El Bouaghi. She is a member of DISE (Distributed and Intelligent Systems Engineering) team at RelacCS(2) research Laboratory at the same university. Her areas of interest include multi-agent systems and software engineering.
	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 and head of the same department. He is a member of DISE (Distributed and Intelligent Systems Engineering) team at RelacCS(2) research Laboratory at the same university. His areas of interest include multi-agent systems, machine learning. and complex systems.
	Zakaria Tolba studies Master degree in distributed software architectures at the Department of Computer Science and Mathematics at the university of Larbi Ben Mhidi of Oum El Bouaghi. His areas of interest include multi-agent systems and Java programming.
	Farid Mokhati is Professor of computer sciences at the Department of Computer Science and Mathematics at the university of Larbi Ben Mhidi of Oum El Bouaghi. His is the head of DISE (Distributed and Intelligent Systems Engineering) team at RelacCS(2) research Laboratory at the same university. His areas of interest include multi-agent systems, formal methods and agent based software engineering.

References

Kautz

and Selman

, Pushing the envelope: Planning, propositional logic, and stochastic search, in: Proceedings of the Thirteenth National Conference on Artificial Intelligence, Portland, OR, 1996, pp. 1194–1201.

Nielsen

T.D.

and Jensen

F.V.

, Belief updating in bayesian networks, in: Bayesian Networks and Decision Graphs Book, Chapter 3, Springer Science and Business Media, 2007, pp. 109–166.

Givan

R.T.

Dean

and Greig

, Equivalence notions and model minimization in Markov decision processes, Artificial Intelligence, Elsevier 147 (2003), 163–223.

Ghallab

Malik

Dana

and Paolo

, Planning in robotics, in: Automated Planning: Theory and Practice Book, Chapter 20, Elsevier, 2004, pp. 469–490.

Durfee

E.H.

, Distributed problem solving and planning in multiagent systems: A modern approach to distributed Artificial intelligence, MIT press, 1999, pp. 121–164.

Canu

and Mouaddib

A.I.

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

Beynier

F.A.

Charpillet

Szer

and Mouaddib

A.I.

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

Vlassis

, Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan and Claypool Publishers, 2009, pp. 223–246.

Shoham

and Brown

K.L.

, Distributed optimization, in: Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations Book, Chapter 2, Cambridge University Press, 2009, pp. 19–46.

10.

Ferber

and Müller

J.P.

, Influences and reaction: A model of situated multiagent systems, in: Second International Conference on Multi-Agent Systems, ICMAS’96, Kyoto, Japan, 1996, pp. 72–80.

11.

Wooldridge

, Intelligent agent, in: An Introduction to Multiagent Systems Book, Chapter 2, John Wiley and Sons, 2009, pp. 15–42.

12.

Sycara

K.P.

, Multi-agent compromise via negotiation, in: Distributed Artificial Intelligence Volume II Gasser

and Huhns

, eds, Pitman Publishing: London and Morgan Kaufmann, San Mateo, CA, USA, 1989, pp. 119–138.

13.

Komenda

Novák

and Pechoucek

, Decentralized multi-agent plan repair in dynamic environments (Extended Abstract), in: Proceedings of AAMAS, 2012, pp. 1239–1240.

14.

Brafman

R.I.

and Domshlak

, From one to many: Planning for loosely coupled multi-agent systems, in: Proceedings of ICAPS, 2008, pp. 28–35.

15.

Komenda

Novák

and Pechoucek

, Domain-independent multi-agent plan repair, Journal of Network and Computer Applications 76–88.

16.

Anderson

S.J.

et al., Constraint-based planning and control for safe, semi-autonomous operation of vehicles, in: Intelligent Vehicles Symposium, 2012, pp. 383–388.

17.

Muscalagiu

et al., Enhancing DisCSP-Netlogo from simulation to real-execution of agents in distributed constraints, Procedia Computer Science 35 (2014), 261–270.

18.

Castejon

et al., Multi-agent planning by distributed constraint satisfaction, in: Proceedings of CAEPIA, 2015, pp. 41–50.

19.

Amanatiadis

A.A.

et al., A multi-objective exploration strategy for mobile robots under operational constraints, IEEE Access Journal 1 (2013), 691–702.

20.

Bellifemine

F.L.

Caire

and Greenwood

, Developing Multi-agent Systems with JADE, Wiley and Sons, 2007, ISBN 0470057475.