Arnaud Canu

Abdel-Illah Mouaddib

Matthieu Boussard

Collective Decision-Theoretic Planning for Robot Platoon Formation ⋆

Keywords: Multiagent Planning, Markov Decisions Processes, Game Theory, Multi-Robot Systems

The robot platooning problem has been studied extensively by the robotics community under some assumptions such as communication existance and global full observability. In this paper, we consider the platooning problem where the previous assumptions are not valid. In such a context, platooning can be considered as a specific flocking which is a collective decision model. This model can, thus, be seen as a decentralized multi-criteria decision making process. Vector-Valued Decentralized Markov Decision Process (2V-DEC-MDP) is an interesting framework for multi-criteria collective decision. It has been shown that 2V-DEC-MDP does not consider communication, local interactions and use local full observability which is a sub-class of partial observability. In this paper, we adapt this framework to consider the notion of leader and the relationship with the stochastic games. The theoretic concept of optimality used in such contexts is the Stackelberg Equilibrium (SE). We give the assumptions under which the leader follows the SE when using 2V-DEC-MDP. We present, then, the adaptation of the initial value functions of the 2V-DEC-MDP, in order to reach an SE. Experiments shown us that using the initial 2V-DEC-MDP leads to a near SE with a weak complexity while the adapted 2V-DEC-MDP leads to a SE with a very high complexity and thus a limited scalability which limits its applicability in real-life robotic applications.

Introduction

Robot platooning [START_REF] Michaud | Coordinated maneuvering of automated vehicles in platoons[END_REF] is a concrete problem where the goal is to build and to maintain a formation for a group of mobile robots. Robotics community addressed this problem with different techniques where the most popular are the bio-inspired, evolutionist and explicit cooperative approches. Most of these techniques are based on some strong assumptions such as communication, full observability and deterministic actions, or assuming the global desired behavior using top-down technique as ant algorithms [START_REF] Berman | Bio-inspired group behaviors for the deployment of a swarm of robots to multiple destinations[END_REF]. Our approach relax most of the assumptions and we address these problems where there is no communication, no full and complete observability, actions are stochastic and it is a bottom-up technique where the global behavior is emerged from local behaviors. We will look at the particular problem of agents trying to organize themselves according to a line shape but other shapes could be considered. Those kinds of problems have been studied with flocking approaches, where agents have to maintain a global shape thanks to few local basic rules. In this context, the platooning is a specific flocking and so, a collective decision making process where each agent has to respect its individual interest and the collective interest. Satisfying these criteria leads us to collective multi-criteria decision making problem. Moreover, actions are stochastic and thus the decision making problem is under uncertainty.

For those problems, and for a single agent, Markov Decision process (MDP) [START_REF] Puterman | Markov decision processes: Discrete stochastic dynamic programming[END_REF] framework allows the agent to compute an optimal policy. DEC-POMDP framework [START_REF] Bernstein | The complexity of decentralized control of markov decision processes[END_REF] has been designed for the same purpose in multiagent settings. Although DEC-POMDPs can find optimal policies, their complexity generally is so high that it is hard to apply on real applications. Moreover, the objective function is considered to be mono-criterion.

⋆ This work is supported by the DGA (Direction Générale de l'Armement).

2V-DEC-MDPs have been introduced to coordinate a large number of agents in multi-criteria problems, extending the MDP framework, by considering local interactions with local full observability (which is a specific Partial Observability) [START_REF] Mouaddib | Towards a framework for multi-objective multiagent planning[END_REF]. We consider 2V-DEC-MDPs as stochastic games to provide a mathematical foundation to improve results presented in [START_REF] Boussard | Vector valued markov decision process for robot platooning[END_REF]. Game theory [START_REF] Shapley | Stochastic games[END_REF] is a formalism for situations where agent's reward does not only depends on its actions but on the actions of all the agents. In stochastics games, Stackelberg Equilibrium (SE) is the theoretic concept of optimality to use with a leader.

In this paper, we adapt flocking rules to platooning, we express them as criteria in a 2V-DEC-MDP and prove the conditions under which the leader follows the SE. Finally, we demonstrate that our 2V-DEC-MDP leads to a near SE with weak complexity while reaching SE requires a very high complexity.

Background

Flocking

Flocking rules [START_REF] Reynolds | Flocks, herds, and schools: A distributed behavioral model[END_REF] Despite the simplicity of those rules, agents manage to maintain the shape of the group. The main advantage of this approach is that it is fully decentralized, with no communication at all.

In this approach, we describe platooning as a particular form of flocking, where agents try to maintain a line shape and to move toward the platoon's objective (in this line, each agent has the same orientation as the previous agent if it is possible, and the leader heads to the objective. The global shape will then be a straight line or, if agents do not have enough space, a broken straight line). This can be done by giving particular flocking rules to each agent, based on agents "perceived" so as we keep the locality property.

Those rules are the following:

1. Cohesion : steer to wait for agents behind it, 2. Separation : steer to avoid collisions with agents in front of it, 3. Alignment : steer to move toward the near agent in front of it, or toward the objective if no one is in front of it.

In the following, we show how we formalize these rules with an extended 2V-MDP [START_REF] White | Multi-objective infinite-horizon discounted markov decision processes[END_REF] to multiagent settings using 2V-DEC-MDP [START_REF] Mouaddib | Towards a framework for multi-objective multiagent planning[END_REF].

Stochastic games

2V-DEC-MDPs are a sub-class of DEC-MDPs, which are equivalent to stochastic games [START_REF] Shapley | Stochastic games[END_REF][START_REF]Processus Décisionnels de Markov en Intelligence Artificielle[END_REF], so we can use stochastic games to estimate the quality of the 2V-DEC-MDP's behaviour.

A stochastic game is defined by a tuple N, S, A, T, R . We describe this tuple as follows:

• N is the number of agents (or players) taking part in the game,

• S is the set of states in which the game can be (a state describes the world and every player/agent),

• A = {A 1 , A 2 , . . . , A N } is the set of possible actions for every agent i with ] is the transitions model between states, according to the joint actions.

A i = a 1 i , . . . , a |Ai| i , • R = {R 1 , R 2 , . . . , R N } is the set of reward functions of every agent with R i : S × A 1 × . . . × A N → R, • P : S × A 1 × . . . × A N × S → [0, 1
At each step, each player chooses an action based on its actual state and its policy. The game then moves to a new state s ′ . The i-agent's policy is noted π i and the joint policy for every agent in the game is π = (π 1 , . . . , π N ). To estimate a strategy's value, it is necessary to know the utility for a given player to follow a given strategy. Let π 1 (s) be the chosen action by applying the π 1 policy on the state s. We can then write π(s) = (π 1 (s), . . . , π N (s)) as the joint policy for this state. In this game, every agent i has (by definition) an immediate reward R i (s, π(s)). We will be able to calculate U π(s) i

(s) the expected utility for an agent i if, in a state s, every agents apply π (with β ≤ 1):

U π i (s) = R i (s, π(s)) + β s ′ ∈S P (s, π(s), s ′ ) • U π i (s ′ )
In a game, a Stackelberg Equilibrium [START_REF] Stackelberg | The theory of the market economy[END_REF] (SE) is a situation where the leader of a group knows that it is the leader. It makes decisions, and its followers apply BR the best response (the best decision) according to this decision. The leader can then estimate the reactions of the other agents, and makes the decision which will bring it the best reward (or the best group reward), according to those reactions. SE is the theoretic concept of optimality to be used in such a situation.

Let us define the SE for a stochastic game. First, we define:

BR(π * i ) = {(π 1 , ..., π n )|∀j = i, π j ∈ BR(π 1 , ..., π * i , ..., π n )}
Let BR(π * i ) be the set of best joint policies (π 1 , ..., π n ) for players 1 to n, knowing that the leader i apply the optimal policy π * i . If, for every state s ∈ S, the leader's policy π * i respects Eq.1, then we have SE.

π * i = Argmax πi ( min π∈BR(πi) U π i (s)) (1)

2V-DEC-MDP

In [START_REF] Mouaddib | Towards a framework for multi-objective multiagent planning[END_REF], the Vector-Valued Decentralized Markov Decision Process (2V-DEC-MDP) framework has been proposed to coordinate locally the actions of a group of agents. Assuming without loss of generality that all agents are identical, a 2V-DEC-MDP is a set of 2V-MDPs, one per agent. A 2V-MDP is composed by an off-line part (an MDP [START_REF] Puterman | Markov decision processes: Discrete stochastic dynamic programming[END_REF]) and an on-line part to adapt its actions with the other agents (in the neighborhood).

The MDP is a tuple S, A, T, R , with:

• S a set of states,

• A a set of action,

• T : S × A × S → [0; 1], the transition function,

• R : S × A × S → R, the reward function which expresses both positive reward for goal states and negative reward for hazardous states.

For the optimality criteria, we use an expected reward on an infinite horizon. With γ ≤ 1, the optimal value function V * of a state s is defined by:

V * (s) = max a∈A (R(s, a) + γ s ′ ∈S T (s, a, s ′ ) • V * (s ′ )), ∀s ∈ S
A policy is a function π : S → A, the optimal policy is a policy π * , such that:

π * (s) = Argmax a (R(s, a) + γ s ′ ∈S T (s, a, s ′ ) • V * (s ′ )), ∀s ∈ S
This MDP represents the behaviour of an agent ignoring its neighbors (we will consider the other agents during the on-line part).

The on-line part of a 2V-MDP is built with the computation of local social impact, according to local observations. The functions for computing the value of the social impact are:

• ER for the individual reward (using the previous MDP),

• JER for the group interest,

• JEP for the negative impact on the group. The on-line part is a sequence of small DEC-MDPs with a special transition model. During this part, an agent builds a new DEC-MDP after each decision it takes (only considering agents in its neighborhood and planning on a short horizon, less than 3). In this DEC-MDP, the probability for an agent i to go from a joint state s to a joint state s ′ only depends on a i .

Deriving a policy for this DEC-MDP consists of solving a multi-criteria Bellman equation based on an Augmented Reward AR = (ER, JER, JEP ). To solve this equation, a regret based value iteration using LexDif f operator [START_REF] Mouaddib | Towards a framework for multi-objective multiagent planning[END_REF] has been designed.

For each possible policy π i , LexDif f builds a vector v = (ER(π i ), JER(π i ), JEP (π i )) and normalize each values vector

v i = (v 1 i , v 2 i , v 3 i ) to a utilities vector v u = (v 1 u , v 2 u , v 3 u ).
LexDif f then uses a leximin operator to find the best vector (it permutes those utilities vectors so that each vector (v 1 , v 2 , v 3 ) be such that v 1 ≥ v 2 ≥ v 3 . The best vector (and so the best policy) is then founded by a lexicographic order: for two vectors

v a = (v 1 a , v 2 a , v 3 a ) and v b = (v 1 b , v 2 b , v 3 b ), we choose v a if v 1 a > v 1 b and v b if v 1 a < v 1 b . If v 1 a = v 1 b , we compare v 2
a and v 2 b , and so on). To use flocking rules in a 2V-DEC-MDP, we translate the three rules into three formulae to parameterize each 2V-MDP. We consider ER as the alignment criterion, JER as the cohesion criterion and JEP as the separation criterion.

Platooning as a 2V-DEC-MDP

We use notations from sec.2.2, with s = (s 1 , ..., s n ), s i being the part of s relative to the i th agent and s 1 , ..., s i-1 , s i+1 , ..., s n the states of the neighbors of i (we define the neighborhood for an agent i as the set of (detected) agents who can interact with i). In the platooning problem, s i is the location of i (so we can say a state is "near" an other state, for exemple).

The ER function will represent the "alignment" into the group, JER will represent the "cohesion" and JEP will represent the "separation". We assume in those functions that an agent i is solving the 2V-MDP. Moreover, we only consider a i the action of i in the transition function (and P (s, a i , s ′ ) only changes s i to s ′ i and leaves the s j unchanged).

Alignment

An agent does not have the same objectives whether it is a leader or a follower. Indeed, a leader will move in the direction of its objective, while a follower will follow the agent in front of it, so an agent have to choose which equation to follow before resolving its 2V-MDP. If the agent is a leader, or if it is out of range of any platoon, it chooses ER 1 . If it is inside a platoon but it knows that the leader is behind it, it chooses

ER 3 . Otherwise, it chooses ER 2 . ER(s, a i ) = s ′ ∈S P (s, a i , s ′ )ER k (s ′ ) k = 1, 2, 3 (2)
Depending on the situation, ER k are defined by:

ER 1 (s) = V * (s i ) ER 2 (s) = -min sj ∈f acei(s) distance(s i , back i (s j )) ER 3 (s) = -distance(s i , back i (s leader ))
with f ace i (s) = {s j ∈ s|distance(s j , objective) ≤ distance(s i , objective)}, back i (s j ) the next state s i behind s j reachable for agent i and V * (s) the function computed during the off-line part. In ER 2 and ER 3 , we use back(target) instead of target, because the agent wants to go behind its target.

Separation

JEP (s, a i ) = s ′ ∈S     P (s, a i , s ′ ) • N j=1     aj P (s, a j , s ′′ ) • c(s ′ i , s ′′ j ) |A j |         (3)
With c(s i , s j ) = {C if s i = s j , 0 otherwise} and C a constant equal to the cost of a collision between two agents.

Cohesion

JER(s, a i ) = s ′ ∈S (P (s, a i , s ′ ) • K i (s ′ )) (4)
Where K i (s ′ ) is the function which estimates the group gain at a state s ′ and gives a reward if at least one agent is behind s i :

K i (s ′ ) = r > 0 if ∃s j ∈ s ′ , j = i such as isBack(s j , s ′ i ) = true 0 otherwise
and where isBack(s 1 , s 2 ) is a function which returns true if s 1 is behind s 2 .

JFPDA 2008

Computation of a policy

Solving the platooning problem consists in deriving a policy from a 2V-DEC-MDP. Our approach is mainly based on local interactions allowing us to compute ER, JER, JEP . Thus we use the near-optimisation operator LexDif f to solve the modified Bellman equation and thus to derive a policy.

Stackelberg equilibrium in 2V-DEC-MDPs

In order to compare our formalism to the SE optimality concept, we aim to find when a 2V-DEC-MDP leads the leader to follow such an equilibrium.

Detecting Stackelberg equilibrium

Theorem 1 An agent using a 2V-MDP is following an SE if and only if each criterion leads to an SE.

Proof. We aim to show that each criterion leads to an SE if and only if applying LexDif f on those criteria leads to an SE.

Here, the agent's policy is built on the fly by LexDif f : for each state, it chooses an action to apply. Because the SE definition says that a leader is in equilibrium if and only if it follows Eq.1 for each state s, we just have to show that the LexDif f equation is equivalent to Eq.1 for every state.

Let c be a criterion and Q π c (s, π i (s)) be the utility for an agent i for applying its policy π i when the system is in the state s and the joint policy is π, according to c. If we assume that each criterion c leads to an SE, we have:

min π * ∈BR(π * L ) Q π * c (s, π * L (s)) (5) = max π L ( min π∈BR(π L ) Q π c (s, π L (s)))∀Q c ∈ -→ Q criteria (6) ↔ min π * ∈BR(π * L ) min Qc∈ - → Q criteria Q π * c (s, π * L (s)) (7) = max π L min π∈BR(π L ) ( min Qc∈ - → Q criteria Q π c (s, π L (s))) (8)
And, we know that LexDif f seeks the action which minimizes the biggest regret. Minimizing regret relative to a criterion is equivalent to maximizing utility relative to this criterion. So LexDif f seeks the lowest utility maximizing action. In other words, because it is a local SE, we have:

U π L (s) = LexDif f π L ( -→ Q criteria ) = max π L min Qc∈ - → Q criteria Q π c (s, π L (s))
We can also deduce the following equality:

U π * L (s) = min Qc∈ - → Q criteria Q π * c (s, π * L (s))
So, Eq.7=Eq.8 is equivalent to:

min π * ∈BR(π * L ) U π * L (s) (9) = max π L ( min π∈BR(π L ) U π L (s)) (10)
So the LexDif f operator leads to an SE.

Adapting the 2V-DEC-MDP to reach a Stackelberg equilibrium

Theorem 2

The criteria of the 2V-DEC-MDP described in Eq.2,Eq.3,Eq.4 don't necessarily lead to a Stackelberg equilibrium.

Proof. According to theorem.1 We aim to show that ER, JER or JEP are not an SE. Using Eq.1, showing that ER, JER of JEP are not SE means to show one of the following:

min π * ∈BR(π * L ) ER π * (s, π * L (s)) = max π L ( min π∈BR(π L ) ER π (s, π L (s))) (11) min π * ∈BR(π * L ) JER π * (s, π * L (s)) = max π L ( min π∈BR(π L ) JER π (s, π L (s))) (12) min π * ∈BR(π * L ) JEP π * (s, π * L (s)) = max π L ( min π∈BR(π L ) JEP π (s, π L (s))) (13)
We will show 11. An agent only following ER will try to maximize the ER value so we have, with π * L the leader's policy resulting from the ER criterion:

ER(s, π * L (s)) = max π L ER(s, π L (s))
However, the equation:

ER(s, π * L (s)) = s ′ ∈S (P (s, π * L (s), s ′ ) • V * (s ′ ))
supposes that no joint policy π is assumed for agents in the neighborhood when computing the value of ER. Indeed, V * (s ′ ) is the reward of the leader when it gets closer to its objective (ie. when s ′ L is closer to the objective than s L ). However, even if an agent gets closer to a point according to a pure geographic point of view, it can in reality move away from this point because of the other agents: if they go between the leader and its objective, it will have to avoid them, what will imply additional movements. Another decision could make the leader to get closer to its objective without being constrained by the other agents. So we have:

ER 2V M DP = ER(s, π * L (s)) = max π L ER(s, π L (s))
while the equation for an SE will be:

ER SE = max π L (min π ER π (s, π L (s)))
We then have ER 2V M DP ≥ ER SE and thus :

min π * ∈BR(π * L ) ER π * (s, π * L (s)) ≥ max π L ( min π∈BR(π L ) ER π (s, π L (s)))
So, ER does not necessarily lead to an SE, nor a 2V-DEC-MDP parametrized by ER, JER and JEP.

Rewriting criteria

According to theorem 1 and 2, the leader does not necessarily follow an SE. We show how to adapt the criteria and its effects on the complexity in order to reach an SE.

ER criterion (Eq.11):

With d(s, g) the distance between s and the goal g if we don't know what the other agents do, and d π (s, g) the distance between s and g knowing the 1 to N agents' policies, we have:

ER(s, π L (s)) = s ′ ∈S P (s, π L (s), s ′ ) • V * (s ′ )
In our problem, their is only one reward, placed on the platoon's objective, so V * (s ′ ) only depends on the distance to the objective, so we can write (with α > 0):

ER(s, π L (s)) = s ′ ∈S P (s, π L (s), s ′ ) • (-αd(s ′ L , g))
Because a i only changes s i to s ′ i but leaves the s j unchanged, we can use P (s i , a i , s ′ i ). So, taking the other agents' decisions into account, we can write:

ER π (s, π L (s)) = s ′ ∈S (P (s, π L (s), s ′ ) • (-αd π (s ′ L , g)))
With

d π (s ′ L , g) = s ′     N j=1 P (s j , π j (s j ), s ′ j )   • d s ′ (s ′ L , g)  
Where d s ′ 1 ,...,s ′ N (s, g) is the distance from s to g without crossing s ′ 1 , nor s ′ 2 , nor . . . , nor s ′ N . Because we want to maximize this criterion, we assume the worst answer from the other agents and write:

π * L = Argmax π L ( min π∈BR(π L ) ER π (s, π L (s)))
5.1.2 JER criterion (Eq.12):

We said that JER was the following, with K i (s) as defined in section 3.3:

JER(s, π L (s)) = s ′ ∈S [P (s, π L (s), s ′ ) • K L (s ′ )]
Taking the other agents' policies into account, we write:

JER π (s, π L (s)) = s ′ ∈S (P (s, π L (s), s ′ ) • K π L (s ′ ))
Where K π i (s) estimates the probability that at least one agent stays behind s i (the objective being not to break the platoon). K is defined by: let

s b (s i ) = {s ′ ∈ S|∃s j ∈ s ′ with isBack(s j , s i ) = true} in K π i (s) = s ′ ∈s b (s)   N j=1 P (s j , π j (s j ), s ′ j )  
To maximize the criterion, we will have:

π * L = Argmax π L ( min π∈BR(π L ) JER π (s, π L (s)))
5.1.3 JEP criterion (Eq.13):

The JEP criterion is the following, with c(s i , s j ) the function which represents the cost of a collision between two agents:

JEP (s, π L (s)) = s ′ ∈S     P (s, π L (s), s ′ ) • N j=1     aj P (s, a j , s ′′ ) • c(s ′ L , s ′′ j ) |A j |        
We can rewrite JEP to consider the other agents' policies:

JEP π (s, π L (s)) = s ′ ∈S   P (s L , π * L (s L ), s ′ L ) • N j=1 P (s j , π j (s j ), s ′ j ) • c(s ′ L , s ′ j )  
Because we aim to maximize the criterion, we will have:

π * L = Argmax π L ( min π∈BR(π L ) JEP π (s, π L (s)))
So, we rewrote the 3 criteria so that they all lead, independently of each other, to an SE. Thus, if the leader follows those criteria, it will be in an SE.

Complexity

We will now compare the complexity of our initial formalism to the one with an SE. We will make this comparison on the JEP criterion (those results are in the same level of complexity for ER and JER).

Initial criteria

Complexity for computing JEP (s, a) is O(S • N • A), with N the number of agents, S the number of states and A the number of actions an agent can do. Moreover, to find the best action, we will have to compute A times JEP . The complexity for this criterion will then be O(S

• N • A 2 ).
So, complexity for finding the best action according to JEP is polynomial in S, N and A which is easy to compute.

Stackelberg adapted criteria

For a fixed joint policy, a leader will have to compute one value. The complexity for computing this value is O(S • N ). The joint policy being not known, the leader will have to compute X values (each one in O(S • N )) to estimate the value of its own policy, X being the size of BR(π L ).

In the worst case, the value of X is P I N , P I being the number of possible policies for one agent. Because a policy is a mapping from S to A, we have P I = A S but once reduced to the actual state we have P I = A, so X = A N . The complexity for computing the value of one π L is then O(A N • S • N ). In order to find its optimal policy, the leader will have to compute this cost Y times, Y being the number of its possible policies.

Finally, in a given state, the global complexity for finding

π * L is O(A N +1 • S • N ),
which is an exponential complexity. Thus, according to this criterion, complexity is much higher in the Stackelberg case.

Similary, complexity for ER and JER are polynomial with the initial criteria and exponential with the Stackelberg adapted criteria.

Experimental results and real robots tests 7.1 Experimental results: with and without SE

We made a simulator in order to test our formalism, where agents' behavior is directed by a 2V-DEC-MDP parametrized as follow:

• we use no communication at all,

• agents know the initial "map" of their environnement,

• agents can perceive neighbors in a short range,

• agents have full observation inside their neighborhood, and null observation outside it (but they do not know their neighbors' policies),

• a state contains position and orientation of the agent and its neighbors,

• actions are "go forward", "go backward", "turn left", "turn right" and "do nothing",

• actions "go forward" and "go backward" can lead with a small probability to slip on a side, while actions "turn" and "do nothing" have probability 1 to be a success,

• DEC-MDPs generated during the on-line part are solved at horizon 1,

• moving cost a little, being on the objective bring a big reward.

Because nearly all the planning task is done on-line, we made some tests in dynamic environnements, by replanning the off-line part AND the on-line part every time a change is perceived in the environnement (for exemple: a new obstacle appear). Results were good but sometimes agents fell into a deadlock: some agents perceived the change while some other didn't perceived it, so their objectives became conflicting. Those results won't be dicussed here but will probably be subject of futur works.

We made some tests on non-dynamic environnement. Fig. 2 represents the situation on which we made our tests: circles are agents (with a black point indicating the agent's direction), polygons are locations where an agent can go and dark patches are obstacles. We made several tests:

• with 7 agents, running the simulator 10 times with and without SE, to compare complexity and quality,

• with a chosen leader, running 5 simulations with 1, 2, . . . , 7 agents in its neighborhood, to analyze complexity. We summarize results of our tests in the following figures. They show results from the environment presented before, as an example, but we did some tests with other initial configurations and other environments. 3 shows platoon's distance (according to its objective) evolution over time. Distance is a good mean to estimate the platoon's behavior quality, because it shows how fast the group is able to move. We can see that a platoon which considers a SE moves exactly at the same speed as a platoon which does not consider it. Thus, quality of the behavior following SE or not are almost the same.

There is an interesting point here: at the end of its evolution, the platoon moves a little faster without SE than with it. Why this difference ? With SE, the platoon's leader is more prudent: it chooses to move slowly, to be sure not to break the platoon. Although, this difference is not representative of the global platoon behavior: during most of the time, there is no difference at all. So, it seems that a platoon using our formalism acts as well as a platoon using a SE. Now, what about the complexity ?

Figure 4: Computation time Fig. 4 shows the complexity according to the number of agents in the neighborhood. When we don't use an SE, the complexity seems to be proportional to the number of agents. This is trivial according to the equations of ER, JER and JEP : they depend on the agents in the neighborhood. Time needed grows slowly with the number of agents. We made some tests with agents starting scattered in the environment: computation time then stay under 0.01 second even with 50 agents.

Complexity is exponential with an SE. When more than 7 agents are in the neighborhood of the leader, time for computing an action becomes too high to be tractable by our simulation. Complexity is then much better with our formalism which can deal with problems up to 50 agents.

During tests on other situations, with other environments, results were the same than the ones depicted in Fig. 3 and Fig. 4. Thus, a platoon using our formalism acts as well as a platoon following SE, with a clearly better complexity.

Algorithms performance

The tests we made show that an agent which uses our formalism has a good behavior, but what about efficiency in time? In 2V-DEC-MDPs, policies are computed online, so computation times have to be good or the agents will have to stop between every action during computation of the next new policy. Several tests have been developped to show the average computation time of one joint action (a 1 , . . . , a N ). Fig. 5 shows computation time according to how many agents are present (average results, on several simulations).

When agents begin scattered, complexity is nearly constant (from 0 to 0,01 seconds for 1 to 50 agents). With a lot of agents, environment is nearly full, so the probability for an agent to have interactions with other agents is high and complexity grows slowly. When agents start grouped, complexity grows slowly with the number of agents: with 50 agents, computation time of one action is less than 0,05 seconds. We made tests on 3 robots running a 2V-DEC-MDP. We parametrized them exactly like we parametrized our simulation. Local full observabilty has been artificialy made by using a central controler which observes the situation and give to every agent the informations it is supposed to know. We placed our robots on a line and put an objective in front of them. In Fig. 6 are captions from a video of those tests. When the test starts, every robot chooses the ER1 function and go toward its objective. After a few seconds (caption 2), one robot chooses the ER2 function and start to follow a robot which is nearest to the objective than it. The two others continue tu use ER1 but, because of the JER function, they move slowly enough to let the third agent follow them. In caption 3, we can see only one agent is still using ER1 while the two others use ER2.

At this point, the platoon starts to emerge from those interactions, and the simulation only started 37s ago. The leader moves slowly because of JER and the two other agents follow it. In caption 4, the platoon is fully made and the leader reached the objective. Because of JEP , the two followers move very slowly to not take any risk and stop just near the leader.

Many other initial configurations were considered and we can see that, for each configuration, robots fully form a platoon after some moves.

Conclusion

In this paper we addressed the platoon formation problem with no cummunication, partial observability and stochastic actions. We shown how to transform this problem into a flocking problem and we formalized it using 2V-DEC-MDP which is the most suitable decision model in this context. To evaluate the performance of our approach, we related 2V-DEC-MDP to stochatic game and we used SE as a theoretic concept for optimality. We shown that the initial 2V-DEC-MDP leads to a near SE with a weak complexity while its adapted version can lead to SE with a very high compelxity.

In future work, we will study the impact of adding human controlled agents into the platoon or impredictible events. We will add a learning layer to avoid deadlocks.

  are a set of three very simple rules describing the behaviour of the agents. Those rules are : 1. Cohesion : steer to move toward the average position of local flockmates, 2. Separation : steer to avoid crowding local flockmates, 3. Alignment : steer towards the average heading of local flockmates.

Figure 1 :

 1 Figure 1: Flocking rules: (1) cohesion, (2) separation, (3) alignment

Figure 2 :

 2 Figure 2: Test environment (start → end)

Figure 3 :

 3 Figure 3: Distance to the objective Fig.3shows platoon's distance (according to its objective) evolution over time. Distance is a good mean to estimate the platoon's behavior quality, because it shows how fast the group is able to move. We can see that a platoon which considers a SE moves exactly at the same speed as a platoon which does not consider it. Thus, quality of the behavior following SE or not are almost the same.

Figure 5 :

 5 Figure 5: Complexity according to the number of agents

Figure 6 :

 6 Figure 6: Platoon formation