GREYC-CNRS, Bd Marechal Juin, Campus II, BP5186, 14032 Caen Cedex, France abeynier,mouaddib@info.unicaen.fr Summary. We consider in this paper a multi-robot planning system where robots realize a common mission with the following characteristics : the mission is an acyclic graph of tasks with dependencies and temporal window validity. Tasks are distributed among robots which have uncertain durations and resource consumptions to achieve tasks. This class of problems can be solved by using decision-theoretic planning techniques that are able to handle local temporal constraints and dependencies between robots allowing them to synchronize their processing. A specific decision model and a value function allow robots to coordinate their actions at runtime to maximize the overall value of the mission realization. For that, we design in this paper a cooperative multi-robot planning system using distributed Markov Decision Processes (MDPs) without communicating. Robots take uncertainty on temporal intervals and dependencies into consideration and use a distributed value function to coordinate the actions of robots.

Introduction

Although a substantial progress with formal models for decision process of individual robots using Markov Decision Process (MDP), extensions of MDP to multiple robots is lacking. Recent attempts identify different classes of multi-robot decision process that include Multi-Agent Markov Decision Process (MMDP) proposed by Boutilier [START_REF] Boutilier | Sequential optimality and coordination in multiagents systems[END_REF], the Partial Observable Identical Payoff Stochastic Game (POIPSG) proposed by Peshkin et al. [START_REF] Peshkin | Learning to cooperate via policy search[END_REF], the multi-agent decision process by Xuan and Lesser [START_REF] Xuan | Communication decisions in multiagent cooperation[END_REF], the Communicative Multiagent Team Decision Problem (COM-MTDP) proposed by Pynadath and Tambe [NPY + 03], the Decentralized Markov Decision Process (DEC-POMDP and DEC-MDP) by Bernstein et al. [START_REF] Bernstein | The complexity of decentralized control of mdps[END_REF], DEC-MDP with a central coordination proposed by Hanna and Mouaddib [START_REF] Hanna | Task selection as decision making in multiagent system[END_REF], the DEC-POMDP with communication proposed by Goldman and Zilberstein [START_REF] Goldman | Optimizing information exchange in cooperative multiagent systems[END_REF] and Transition Independent DEC-MDP proposed by Becker et al. [START_REF] Becker | Transitionindependent decentralized markov decision processes[END_REF]. Bererton et al. [START_REF] Bererton | Auction mechanism design for multi-robot coordination[END_REF] present an extension of MDPs and apply auction mechanisms to coordinate multiple robots. Therefore, they reduce communication. Nevertheless, agents communicate during the executing.

Our approach is a specific structured DEC-MDPs to control multiple robots realizing a common mission with temporal and dependency constraints. Indeed, the formal model we use can be seen as an extension of the structured DEC-MDP, proposed by Becker et al. [START_REF] Becker | Transitionindependent decentralized markov decision processes[END_REF], to increase the expressiveness of the model to handle temporal constraints. The formal model we develop is based on an augmented MDP per robot using an augmented reward function that represents the reward a robot gains when it achieves a task and the opportunity cost of violating temporal constraints. As described in [NPY + 03], our system builds the policy in a centralized way but the execution is decentralized. Nonetheless, in our approach, the robots don't have to communicate during their execution. This model is motivated by a more general scenario than the one introduced in [START_REF] Cardon | Adaptive control of acyclic progressive processing task structures[END_REF] to control the operations of a rover. The extended scenario, considered, is a multiple robot scenario in which each robot has a mission to achieve (a set of tasks) similar to the planetary rovers [BDM + 02] where each one has to visit sites and to take pictures, conduct experiments and collect data (see the example in [START_REF] Cardon | Adaptive control of acyclic progressive processing task structures[END_REF]).

These scenarios are mainly characterized by 1. Single rover activities have an associated temporal window : the examples involve measurements of the environment -a "gravity wave" experiment that needs to be done "preferably in the morning", and atmospheric measurements at sunrise, sunset, and noon (look at the sun through the atmosphere). 2. There is uncertainty on time realization tasks and the temporal interval activity of rovers. 3. The temporal constraints are, in general, soft. 4. Precedence dependencies among tasks exist. 5. Interacting tasks could not be assigned to the same rover because of its limited resource : one popular scenario is preparing a site with a set of robotic bulldozers (pushing dirt and small stones). In this paper, we don't take into account tasks achieved by more than one robot.

We present in the next sections the multi-robot decision process system and how the decision process is distributed and coordinated among rovers.

A Formal Description of Decentralized MDP

One approach to this problem is to represent the system as a large Markov Decision Process (MDP) [START_REF] Sutton | Reinforcement learning : An introduction[END_REF] where the "macro-action" is a joint action of all of the robots and the reward is the total reward of all of the robots. The problem is the large action space that is for n robots and m actions for each one, we have m n macro-actions [START_REF] Guestrin | Multiagent planning with factored mdps[END_REF]. Some approaches use Factored MDPs while other approaches are designed in such a way that most of them are based on distributed robots with partial information. Such approaches are known to be intractable [START_REF] Bernstein | The complexity of decentralized control of mdps[END_REF]. In our approach, we view the entire multi-robot system as distributed Markov Decision Process robots without communication but some information on the effect of the local robot's actions, on the plans of the other robots are assumed to be available. Differently speaking, the system is composed on robots each of which constructs a local MDP and derives a local policy, taking into account the temporal dependencies. Indeed, in the local MDP we introduce an opportunity cost due to the current activity of the robot which delays the successor activities of the other robots. It measures the loss in value when starting the activity with a delay δt. This cost is the difference between the value when we start at time and the value when we start with a delay δt. Consequently, each robot develops a local MDP independently of the local policies of the other robots but, introducing in its expected value the opportunity cost due to the possible delay of his activity. The construction of the local MDP is based, first, on the construction of the state space, second, on the computation of the opportunity cost at each state and then, the computation of the value of each state to construct the local optimal policy. To define the state space, we need to define what is the state for the decision process. To do that, let us recall the characteristics of the problem.

The mission of the robot, as described previously, is a graph of tasks where each task is characterized by the execution time window, and the uncertainty on the execution time and resource consumption. In the rest of the paper, we assume that the mission graph is given and each task has a set of possible execution times and their probabilities, and a set of possible amounts of resource and their probabilities. It means that the representation of execution time and resource consumption are discrete. Given these information, the problem is to choose the best decision about which task to execute and when to execute it. This decision is based on the available resources and the temporal constraints. The respect of the temporal constraints requires to know the interval of time during which the current task has been executed. From that, the decision process constructs its decision given the current state of the last executed task, the remaining resources and the interval during which this task has been executed. The state of this decision process is then, [l i , r, I] that corresponds to the last executed task l i , the remaining resource r and the interval of time. Given the uncertainty on the execution time, there exist many possible intervals of time during which a task could be executed. In order to develop the state space of the decision process, we need to know for each task in the graph the set of its possible execution intervals of time.

To do that, we develop an algorithm that computes for each task in the graph all the possible intervals of time by propagating different execution times.

The algorithm of developing a local MDP is divided into 5 major steps :

• Propagating the temporal constraints and computing the set of execution intervals of time for each task (node in the graph) among the graph (section 1.4). • Computing the probability for each interval of time (section 1.5).

• Constructing the state space of the Markov Decision Process using the transition model (section 1.6). • Computing the opportunity cost at each state (section 1.6).

• Using the value iteration algorithm to solve the MDP.

In the rest of the paper, we describe each step of the algorithm and we give the formal description of the local MDP and their interactions.

Preliminaries

In the previous section, we describe the overall basis of the model we develop and give its main lines. For that we consider a distribution probability on execution time and resource, and probabilities on start and end time of tasks.

Uncertain computation time

The uncertainty on execution time has been considered in several approaches developed in [START_REF] Cardon | Adaptive control of acyclic progressive processing task structures[END_REF]. All those approaches ignore the uncertainty on the start time. We show in this paper how extensions can be considered in those approaches taking different temporal constraints into account.

Definition 1 A probabilistic execution time distribution, P r(δ c = t c ) = P c (t c ) is the probability that the activity takes t c time units for its execution.

The representation adopted of this distribution is discrete. We use a set of couples (t c ,p) where each couple means that there is a probability p that the execution will take t c time units.

Uncertain resource consumption

The consumptions of resources (energy, memory, etc ...) are uncertain. We assume a probability distribution on the resource consumptions of a rover when performing an activity.

Definition 2 A probabilistic resource consumption is a probability distribution, P r(∆r) of resource consumption measuring the probability that an activity consumes ∆r units of resources.

The representation adopted of this distribution is discrete. We use a set of couples (r,p) where each couple means that there is a probability p that the execution will consume r units.

Temporal window of Tasks

Each task is assigned a temporal window [EST,LET] during which is should be executed. EST is the earliest start time and LET is the latest end time. The temporal execution interval of the activity (start time and the end time) should be included in this interval.

Rewards

Each robot, i, receives a reward R presumably based on the quality of the solution and the remaining resources. For all states [l i , r, I], the reward function is assumed given R([[l i , r, I]). However, we assume that all failure states have a zero reward.

Temporal interval propagation

A simple temporal interval propagation algorithm

Given the possible transition times of different tasks, we determine the set of temporal intervals during which a task can be realized. Firstly, the possible start times is a one of instants EST, EST + 1, . . . , LET -min δ i (Last start time that we node LST). However, a robot needs to know when its predecessor terminates its processing to validate some of those start times. For that, we compute off-line all the possible end times of all its predecessors and compute its possible start times consequently. The possible intervals I of a robot are determined with a simple temporal propagation constraints in the graph. This propagation organizes the graph into levels such that : l 0 is the root of the graph, l 1 contains all the successors of the root (successors(root)), . . ., l i contains the successors of all nodes at level l i-1 . For each node in given level l, we compute all its possible intervals of time from its predecessors.

• level 0 : the start time and the end times of the root node (the first task of the mission) are computed as follows : st(root) = EST (root) and

ET (root) = {st(root) + δ root c , ∀δ root c } where δ root c
is the execution time of the first activity (task) of the mission.

• level i : for each node in level i, it starts its execution when all its predecessors end their own activities. The set of the possible end times of the node is then given thanks to the start times and the task's durations :

ET (node) = ∀δ node c ,st {st + δ node c } where δ node c
is the execution time of the activity (task) at node node and st ∈ ST (node). We recall also here that there is a probability that some end times can violate the deadline LET node .

A Probability propagation algorithm

After computing off-line all the possible execution intervals of each activity (or node), we describe, in this section, how we can weight each of those intervals with a probability. This probabilistic weight allows us to know the probability that an activity can be executed during an interval of time. For that, a probability propagation algorithm among the graph of activities is described using the execution time probability and the temporal constraints EST, LST, and LET. This algorithm has to take the precedence-constraint that affects the start time of each node, and the uncertainty of execution time that affects the end time of the node. In the following, we describe how the conditional start time probability (DP) is computed and the probability of an execution interval P w using DP and the probability of execution time P c .

Conditional probability on start time

The computation of conditional start time has to consider the precedenceconstraint that expresses the fact that an activity cannot start before its predecessors finish. The start time probability of an activity should express the uncertainty on the precedence-constraint dependency. This constraint expresses the fact that the activity starts its execution when all activities of its predecessors have been finished. Consequently, the probability DP (t) that a robot starts an activity at t is the product of the probability that all predecessor robots terminate their activities before time t and there is, at least, one of them that finish at time t. More formally speaking :

•for the root :

DP s (i) = 1, i ∈ [EST root , LET root ]
•for the other nodes : DP s (δ s = t) = Π a∈predecessors(c) P r a (δ e ≤ t) -

t <t DP (t )
Where a is an activity of a predecessor robot of the robot performing the considered activity c and P r a (δ e ≤ t) is the probability that predecessor a finishes before time t. This probability is the sum of probabilities that the predecessor a executes its task in an interval I with an end time et(I) less than t. More formally speaking, P r a (δ e < t) = ti+tj =t DP s (t i ).P c (t j ) such that [t i , t] is one of intervals interval(a) computed for the activity of robot a. This probability can be rewritten as follows :

P r a (δ e < t) = I∈intervals(a),et(I)<t P r(I)

In the following, we show how we compute the probability that an execution occurs in an interval I.

Probability on a temporal interval of an activity

Given the probability on start time and end time, we can compute the probability that the execution of an activity occurs during the interval I where st(I) is the start time and et(I) is the end time.

Definition 3 A probabilistic execution interval I is the probability P w (I) of the interval during which an activity can be executed. This probability measures the probability that an activity starts at st(I) and it ends at et(I) .

P w (I) = DP s (st(I)).P c (et(I)st(I))

An activity l i+1 of an agent is executed during an interval I when the agent finishes its activity l i and that all predecessor agents finish their activities. To compute the probability of the interval I , we need to add the fact that we know the end time of activity l i . For that, we compute the probability P w (I |et li (I)) such that : This equation expresses the fact that we know activity l i has finished at et(I), and allows us to consider only the probability that the other predecessor activities finish.

A Decision Model for Multi-robot Planning system with temporal dependencies

As mentioned above, we formalize this problem with Markov Decision Processes. To do that, we need to define what is the state space, the transition model and the value function for each robot. Each rover develops its local policy using the off-line temporal interval propagation. Robots don't need to communicate since all information needed for each to make a decision are available. The consequence of representing all the intervals and all the remaining resources, is that the state space becomes fully observable and the decision process can start its maximization action selection using the modified Bellman equation defined bellow. However, the maximization action selection uses an uncertain start time that is computed from an uncertain end time of the predecessors.

The start time selected by the policy can be earlier or later than the end time of the predecessors. When the start time is later than the end time of the predecessors, we need to handle the situation where the start time is later than LET -min δ i . The other case is when the policy selects a start time earlier than the end time of the predecessors, in such case, the action selected won't succeed since the precedence constraint is not respected. In such case, we assume that the new state is a partial failure and a penalty should be paid. For example, rover A assumes that at time t 1 , rover B (bulldozer) finishes its processing and it can moves toward its destination. When rover B finishes later than t 1 , the moving action of rover A fails. In the rest of this section we formalize this decision process.

State Representation, Transition model and Values

Each robot, i, observes its resource levels and the progress made in achieving its tasks which represent the state of the robot. The state is then a triplet [l, r, I] where l is the last task, r is the available resource and I is the interval during which the task has been executed.

We assume that the actions of one robot is enough to achieve a task. The robot should make a decision on which task to execute and when to start its execution. However, the actions to perform consist of Execute the next task l i at time st (E(st)) that is the action to achieve task i at time st when the task i -1 has been executed . This action is probabilistic since the processing time of the task is uncertain. This action allows the Decision process to move from state [l i , r, I] to state [l i+1 , r , I ]. When a robot starts before its predecessors terminate, this transition leads to a failure state that we recover by a state [l i , r -∆r, [st, unknown]] where ∆r is the consumed resources. This recovery allows us to represent the situation where the robot acts with no results, except the fact that further resource has been consumed. Finally, the execution can lead to a failure state that we represent with [f ailure, 0, [st, +∞]] when the remaining resources are not enough to realize a task. It can also lead to another failure state when the execution starts too late (st > LET -min δ i ). We use ∞ or unknown in order to indicate to the policy that those states needs a special consideration by considering a special value that we explain in the next section. Let us just give a meaning to +∞ : +∞ means that the robot is never be able to achieve the task while unknown means that the robot tries and fails but there is a chance to succeed another time by starting later. The transitions are formalized as follows :

• Successful transition : The action allows the policy to transition to a state [l i+1 , r , I ] where task l i+1 has been achieved during the interval I respecting the EST and LET time of this task and that r is the remaining resource for the rest of the plan. The expected value to move to the state [l i+1 , r , I ] is : • Deadline met Transition : The action starts an execution at time st but the duration δ is so long that the deadline is met. Given these different transitions, we adapt our former to Bellman equation as follows :

V 1 =
V [l i , r, I] = immediat gain R([l i , r, I]) - Opportunity Cost k∈sucessors OC k (et(I) -et(I f irst )) + Expected value max E(li+1,st),st>current time (V 1 + V 2 + V 3 + V 4 + V 5)
This equation means that robot rewards R([l i , r, I]) are reduced by an opportunity cost due to the delay caused in the successor robots.

Opportunity cost is the lost in value when a robot starts with a delay. This means it is a difference between V 0 when we start with no delay and V ∆t when we start with a delay ∆t :

OC k (∆t) = V 0 -V ∆t with : i) ∀t ≤ 0, OC(t) = 0, ii) OC(unknown) = 0, iii) ∀t > LET -min i δ i OC([failure(l i ), r, [+∞, +∞]]) = R(l i ) + a∈AllSucc(li)

R(a)

The opportunity cost has to be computed off-line for all the delays from 0 to latest start time (LET -min δ i ) and for each task. We store all these costs in library that allows to each robot to know the opportunity cost of its delay in the values of its successors. Each robot has, for each successor i, the corresponding opportunity cost OC i function for each task.

Implementation

This multi-robot decision system has been implemented and run on a scenario involving two robots : R1 and R2. Each one must exit a warehouse, move to an object, and catch it. Then, it must bring back the object to another warehouse. This problem implies constraints :

• Temporal constraints : warehouses have opening and closing hours. They open from 1 to 4 and from 25 to 32. • Precedence constraints : the object O1 must be moved in order R2 to bring O2 back to warehouse 1.

The robots' mission can be represented by the graph shown in the figure 1.1. A fictitious task is added at the begin of the mission in order to have only one root. The intervals stand for the temporal constraints. For each task, the graph specifies the robot that must complete it. We have tested our decision system on this scenario. The results are promising. The robots perform the whole mission and act in an optimal way : for each step, each robot chooses the action that leads to the highest expected value. More complex scenarios, involving 3 or 4 robots, are under development. They deal with planetary rovers or crisis scenario. For instance, a set of rovers must operate on the surface of Mars, they must complete different observations or experiments : take pictures, complete atmospheric measurements,... Another scenario deal with crisis control : an earth-quake arises and the firemen, the policemen and the ambulance men have several tasks to complete in order to rescue the inhabitants.

Currently, we are developing different experiments by modifying three parameters : number of tasks, number of constraints and number of robots. The first results show the robustness of our approach and its ability to support a large problem (200 tasks, 3 robots and 50 constraints) where the state space is almost 300000 states. Furthermore, given a mission, it can be shown that when we increase the number of agents, the state space size of each local MDP decreases. Indeed, each agent has less tasks to complete and the number of triplet [l i , r, I] decreases. If we increase the number of tasks, the state space size increases. When we increase the number of precedence constraints or we tighten the temporal constraints (smaller temporal windows [EST, LET ]), the number of possible execution intervals goes down. Thus, the state space size diminishes. Also, the initial resource rate has effects on the space state size. Formalization of these fluctuations is under development.

Conclusion

In this paper we have deal with a multi-robot system under temporal and complex constraints. In this multi-robot system, robots are with limited and uncertain resources. This problem can be seen as a multi-robot planning under uncertainty with temporal and complex dependencies and limited resources. To address this problem, we proposed a decentralized MDPs framework. In this framework, MDPs are with no communication and they don't have a complete observation about the states of the other robots. This framework is based on the notion of opportunity cost to derive an optimal joint policy. Each robot constructs its optimal policy to achieve all its tasks taking for each one the dependency with the other tasks of the other robots. This policy respects the local temporal constraints (EST, LST and LET) and the temporal dependency between robots (precedence constraint).

Future work will concerns many techniques for computing exact or approximate opportunity cost.

1

  Decentralized Markov Decision Processes for Handling Temporal and Resource constraints in a Multiple Robot SystemAurélie Beynier 1 , Abdel-Illah Mouaddib 1

P

  w (I |et li (I)) = DP s (st(I )|et li (I)).P c (et(I ) li+1st(I) li+1 ) And the probability DP s (st(I )|et li (I)) is computed as follows : DP s (st(I )|et li (I)) = a∈predecessors(li+1)-li P a r (δ e ≤ st(I )|et li (I))-t1<st(I ) DP s (t 1 |et li (I)) P a r (δ e ≤ t|et(I) li ) = I1∈,et(I1)=et(I) l i ,et(I1)≤t P w (I 1 )

  ∆r≤r et(I )≤LET P r (∆ r ).P w (I |et(I)).V ([l i+1 , r , I ] • Too late start time Transition : The action starts too late and the execution meets the deadline LET. In such case, the action allows the policy to move to a [f ailure, r, [st, +∞]]. The expected value to move to this state is : V 2 = P r(st > LETminδ i ).V ([f ailure, r, [st, +∞]]) = a∈pred(li+1)-{li} Ia P w (I a )-a∈pred(li+1)-li Ia:et(Ia)≤LET -minδi P w (I a ).V ([f ailure, r, [st, +∞]])

  Fig. 1.1. Graph of the mission

  This transition moves to the state [f ailure, r, [st, +∞]]. The expected value to move to this state is : V 3 = ∆r≤r st+tc>LET P r (∆r).DP (st|et(I) li ).P c (t c ).V ([f ailure, r, [st, +∞]]) • Insufficient resource Transition : The execution action requires more resources than available. This transition moves to the state [f ailure, 0, [st, +∞]]. The expected value to move to this state is : V 4 = ∆r >r P r (∆ r ).V ([f ailure, 0, [st, +∞]]) • Too early start time Transition : The action starts too early before one of the predecessor robots has finished its tasks. In such case, the action allows the policy to move to [f ailure, r, [st, st + 1]]. Conceptually, we proposed that the end time should be unknown, but in our model we formalize it by the fact that when a robot starts before its predecessor robots finish, it realizes it immediately. This means that the robot, at st + 1, realizes that it fails. This state is a non-permanent failure because the robot can retry later. The robot should pay a penalty k visiting such states. The expected value to move to this state is :

	V 5 =		P w (I a )
	∆r≤r	a∈predecessors(li+1)-{li} Ia:et(Ia)>LET -minδi
	-	DP (s|et(I) li ) .P r (∆r).V ([f ailure, r, [st, st + 1]])
	s≤st

DEC-MDPs for Handling Temporal and Resource constraints


Aurélie Beynier
email: aurelie.beynier@lip6.fr

Abdel-Illah Mouaddib

Applications of DEC-MDPs in multi-robot systems

Optimizing the operation of cooperative multi-robot systems that can cooperatively act in large and complex environments has become an important focal area of research. This issue is motivated by many applications involving a set of cooperative robots that have to decide in a decentralized way how to execute a large set of tasks in partially observable and uncertain environments. Such decision problems are encountered while developing exploration rovers, team of patrolling robots, rescue-robot colonies, mine-clearance robots, etc.

. All these applications share common characteristics: they are composed of a set of robots that must autonomously and cooperatively act in uncertain and partially observable environments. Thus, each robot must be able to decide on its own, how to act so as to maximize the global performance of the system. In order these robots to be able to optimize their behaviors, decision making approaches that take into account characteristics of real-world applications (large systems, constraints on task execution, uncertainty and partial observability) have then to be developed.

. They allow for modeling cooperative and distributed decision problems under uncertainty and partial observability. This chapter will describe how DEC-MDP approaches can contribute to solve multi-robot decision problems.

The chapter will be divided into three main parts. The first part will describe multirobot real-world applications and we will introduce problematics related to the decentralized control of robot teams. The second part will introduce the DEC-MDP framework and the last part of the chapter will present existing DEC-MDP approaches that are concerned with solving multi-robot decision problems.

Decentralized control in multi-robot systems

This section introduces problematics related to the decentralized control of multi-robot systems. Optimizing the operation of cooperative multi-robot systems that can cooperatively act in large and complex environments has become an important focal area of research. This issue is motivated by many applications involving a set of cooperative robots that have to decide in a decentralized way how to execute a large set of tasks in partially observable and uncertain environments.

Mars exploration scenario

The first problem we consider consists in controlling task execution of a cooperative team of Mars exploration rovers. Once a day, the team receives, from a ground center, a set of tasks to execute (observations, measurements, moves) which is intended to increase science knowledge. As the amount of useful scientific data returned to the ground measures the success of the mission, rovers aim at maximizing science return. This performance measure can be represented by an expected value function. In order to optimize this function, several kinds of constraints must be respected while executing the tasks [

Introduction

Recent robotic researches have demonstrated the feasibility of projects such as space exploration by mobile robots, mine clearance of risky area, search and rescue of civilians in urban disaster environments, etc. In order to increase the performance and abilities of these robots, researchers aim at developing multi-robot systems where the robots could interact. As explained by [START_REF] Estlin | An integrated system for multi-rover scientific exploration[END_REF] about multi-rover exploration of Mars, such teams of robots will be able to collect more data by dividing tasks among the robots. More complex tasks that require several robots to cooperate, could also be executed. Moreover, abilities of the team could be improved by enabling each rover to have special skills. Finally, if one robot fails (robot breakdown or failure of task execution), another robot will be able to repair the damage to the first robot or will complete the unexecuted tasks. Teams of robots can also be used to increase the must be taken at sunset or sunrise. On the other hand, some operations must be performed at night (atmospheric measurements).

• preconditions: some tasks have setup conditions that must hold before they can be performed. For instance, instruments must be turned on and calibrated in order an agent to perform measurements. If these preconditions do not hold, the agent will fail to perform its task. Preconditions lead to precedence constraints between the tasks and to dependencies between the agents. Let us consider that a robot must take a sample of the ground in order for another robot to analyse it: the second robot cannot start analysis before the first robot has finished to take the sample. The success of the second robot relies therefore on the first robot.

• resource constraints: executing a task requires power, storage (storing pictures or measurements) or bandwidth (data communication). These resources must be available to complete a task.

Moreover, robots must handle uncertainty on task execution and partial observability of the environment. Since accuracy and capacity of sensors are limited, each rover partially senses its environment. Because the environment is unknown and the issue of a task may depend on environment parameters (temperature, slope and roughness of the terrain, etc.), durations and resource consumptions of tasks are uncertain. Thus, each task takes differing amounts of time and consumes differing amounts of resources.

Furthermore, robots must deal with limited communications. Mars rovers communicate with operators via a satellite which is often unavailable due to its orbital rotation. Moreover, communications take time and consume resources. Consequently, communications with operators are limited to once a day. During this communication window, the robots send the data they have collected and they receive a new set of tasks to execute. During the rest of the day, the robots cannot communicate with the operators and they must act in an autonomous way. If there is no obstacle between the robots and they are close enough to each other, direct communication is possible. Nonetheless, as rovers cover large area with many obstacles, such direct communication is often impossible. They must therefore be able to perform their tasks without direct information exchange. Then, each rover must be able to autonomously decide how it will act and decision processes have to be decentralized. Finally, space robots have limited computation resources and data storage. Thus, in order to maximize collected data, each rover must be able to efficiently decide (with little computing power and data storage) which task to execute.

Rescue missions

There has been a growing interest in the recent years in disaster management crisis [Morimoto, 2000, RoboCup, 2000]. The RoboCup Rescue Competition has been organized since 2001 to promote research and development in this domain. The scenarios that are considered involve a team of rescue robots that must rescue civilians and prevent buildings from burning, after an earthquake occurs. A team is composed of three kinds of robots: fire brigade robots that must extinguish fires, ambulance robots that must rescue injured people and drive them to hospital, and police robots that can unblock roads. Such skills lead to dependencies between the robots. For instance, ambulance robots and fire robots cannot pass a blockade. Thus, police robots must unblock roads before the other robots can pass.

Rescue robots share many characteristics with planetary rovers. Rescue robots must face uncertainty and partial observability of the environment. Task durations and resource consumptions are uncertain. For instance, extinguishing a fire can take different amounts of time and consumes different amounts of water. Since communication installations often breakdown in such scenarios, it is assumed that communications between the agents are impossible. Moreover, resources are limited: an ambulance can load only one civilian at a time, a fire brigade robot has a limited amount of water, etc. Finally, temporal constraints must be considered. First, a crisis deadline is set. Next, temporal constraints can be deduced from scenarios' characteristics. For instance, a fire robots must have extinguished a fire before the building is entirely destroyed.

Multi-robot exploration and rescue rover missions are closely related to the problem of Decentralized Simultaneous Localization and Mapping (DSLAM) [Kleiner andSun, 2007, Nettleton et al., 2003]. Decentralized SLAM addresses the problem of cooperatively building a map of an envrionment: a set of agents navigate in an unknown environment and jointly build a map of this environment while simultaneously localising themselves relatively to the map. DSLAM approaches have been applied to the problem of fire searching in an unknown environment [START_REF] Marjovi | Multi-robot fire searching in unknown environment[END_REF].

Multi-robot flocking and platooning

The purpose of robot platooning [START_REF] Michaud | Coordinated maneuvering of automated vehicles in platoons[END_REF] is to build and to maintain a formation for a group of mobile robots from a starting point to a goal. Because the environments are unknown and the robots have imperfect sensing of the environment, environments are assumed to have unpredictable properties so actions have nondeterministic effects (for example, an agent can skid on a wet ground).Those kind of problems have been studied with flocking approach, where the agents have to maintain a global shape thanks to few simple local basic rules. Flocking rules [Reynolds, 1987] 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.

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.

The platooning can be seen 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: The multi-robot teams presented in this section can be easily considered as cooperative multiagent systems. These consist of a set of agents that have to autonomously execute a set of tasks in the same environment so as to maximize a common performance measure1 . The problems that are considered involve large sets of tasks and agents. For instance, regarding Mars exploration, the set of tasks to execute is sent once a day and may involve about ten robots that have to complete hundreds of tasks. Different kinds of constraints must be considered in order to achieve good performance. These include temporal constraints, precedence constraints, resource constraints, limited or impossible communication, limited computation capacities.

Decentralized Markov Decision Processes

The above mentioned multi-robot applications require a decentralized control approach that enables each robot to decide how to act in a partially observable environments and in a coordinated way with the other robots. Classical multiagent planning approaches are not suitable to handle such decision problems since they are not able to consider uncertainty and partial observability [START_REF] Shoham | On social laws for artifical agent sociaties: off-line design[END_REF], Weld, 1994a, Decker and Lesser, 1993a, Decker and Lesser, 1992, Clement and Barrett, 2003]. Some classical planning approaches, such as STRIPS, GRAPHPLAN or PGRAPHPLAN, have been adapted for planning under uncertainty [Blythe, 1999a, Blum and Furst, 1997, Blum and Langford, 1999]. Most of these approaches search for a plan that meets a threshold probability of success or that exceeds a minimum expected utility. During task execution, if the agent deviates from the computed plan, a new plan has to be re-computed. To limit re-planning, some approaches compute a contingent plan that encodes a tree of possible courses of actions. Nonetheless, a contingent plan may not consider all possible courses of actions so, re-planning remains and optimality is not guaranteed.

Markov Decision Processes (MDP) provide a stochastic planning approach that allows for computing optimal policies (see Chapter 3). As a policy maps each possible state of the agent to an action, there is no need for on-line re-planning. The agent's objectives are expressed as a utility function and efficient algorithms have been developed to efficiently compute a policy that maximizes the utility [Puterman, 2005, Howard, 1960]. MDPs have been successfully applied to many domains such as mobile robots [START_REF] Bernstein | Planetary rover control as a markov decision process[END_REF], spoken dialog managers [START_REF] Roy | Spoken dialogue management using probabilistic reasoning[END_REF] or inventory management [Puterman, 2005]. Then, MDPs have been extended to deal with multiagent settings and Decentralized Markov Decision Processes (DEC-MDPs) [START_REF] Bernstein | The complexity of decentralized control of mdps[END_REF] have been defined.

Model description

DEC-MDPs provide a mathematical framework to model and solve problems of decentralized control in stochastic environments. So as to modelize partial observability and uncertainty, the DEC-MDP model is composed of a set of observations, a probabilistic observation function and a probabilistic transition function. A reward function to maximize formalizes the objectives of the system.

Definition 1 A Decentralized Markov Decision Process (DEC-MDP) for n agents is defined by a tuple < S, A, P, Ω, O, R > where :

• S is a finite set of system states. The state of the system is assumed to be jointly observable2 .

• A = A 1 , • • • , A n is a set of joint actions, A i is the set of actions a i that can be executed by the agent Ag i .

• P = S × A × S → [0, 1] is a transition function. P(s, a, s ) is the probability of the outcome state s when the agents execute the joint action a in s.

•

Ω = Ω 1 × Ω 2 × • • • × Ω n is a finite state of observations where Ω i is agent Ag i 's set of observations. • O = S × A × S × Ω → [0, 1] is the observation function. O(s, a, s , o = o 1 , • • • , o n )
is the probability that each agent Ag i observes o i when the agents execute the joint action a from state s and the system moves to state s .

• R is a reward function. R(s, a, s ) is the reward the system obtains when the agents execute joint action a from state s and the system moves to state s .

Problem solving

Optimally solving a DEC-MDP consists in finding a joint policy which maximizes the expected reward of the system.

Definition 2 A joint policy π in an n-agent DEC-MDP is a set of individual policies π 1 , . . . , π n where π i is the individual policy of the agent Ag i . The individual policy π i of an agent Ag i is a mapping from each possible state of the agent's information (its state, its observations or its belief state) to an action a i ∈ A i .

Note that an individual policy π i takes into account every possible information state of the agent while methods based on classical planners find a sequence of actions based on a set of possible initial states [START_REF] Blythe | Planning under uncertainty in Dynamic domains[END_REF].

Recent works have focused on developing off-line planning algorithms to solve problems formalized by DEC-MDPs. They consist in computing a set of individual policies, one per agent, describing the agents' behaviors. Each individual policy maps the agent's information (its state, its observations or its belief state) to an action. Since solving optimally a DEC-MDP is a very hard problem (NEXP-hard) [START_REF] Bernstein | The complexity of decentralized control of mdps[END_REF], most approaches search for methods that reduce the complexity of the problem.

Two kinds of approaches can be identified to overcome the high complexity of DEC-MDPs. The first set of approaches aims at identifying properties of DEC-MDPs that reduce their complexity. Thus, Goldman and Zilberstein [START_REF] Goldman | Decentralized control of cooperative systems: Categorization and complexity analysis[END_REF] have introduced transition independence and observation independence. These properties enable identifying classes of problems that are easier to solve [START_REF] Goldman | Decentralized control of cooperative systems: Categorization and complexity analysis[END_REF]. For instance, it has been proved that a DEC-MDP with independent transitions and observations is NP-complete. Based on this study, an optimal algorithm, the Coverage Set Algorithm (CSA), has been developed to solve DEC-MDPs with independent observations and transitions [START_REF] Becker | Transition-independent decentralized markov decision processes[END_REF].

Other attempts to solve DEC-MDPs have focused on finding approximate solutions instead of computing the optimum. [START_REF] Nair | Taming decentralized pomdps: Towards efficient policy computation for multiagent settings[END_REF] describe an approach, the Joint Equilibrium Based Search for Policies (JESP), to solve transition and observation independent DEC-MDPs. JESP relies on co-alternative improvement of policies: the policies of a set of agents are fixed and the policies of the remaining agents are improved. Policy improvement is executed in a centralized way and only a part of the agents' policies is improved at each step. Finally, the algorithm converges to a Nash equilibrium. Chadès et al. describe a similar approach based on the definition of subjective MDPs and the use of empathy [START_REF] Chadès | A heuristic approach for solving decentralized-POMDP: Assessment on the pursuit problem[END_REF]. Improvements of JESP have also been proposed: DP-JESP [START_REF] Nair | Taming decentralized pomdps: Towards efficient policy computation for multiagent settings[END_REF] speeds up JESP algorithm using dynamic programming and LID-JESP [START_REF] Nair | Networked distributed POMDPs: A synthesis of distributed constraint optimization and POMDPs[END_REF] combines JESP and distributed constraints optimization algorithms. Thus, LID-JESP exploits the locality of interactions to improve the efficiency of JESP. SPIDER [START_REF] Varakantham | Letting loose a SPIDER on a network of POMDPs: Generating quality guaranteed policies[END_REF]] also exploits the locality of interactions to compute an approximate solution. Moreover, SPI-DER uses branch and bound search and abstraction to speed up policy computation. [START_REF] Peshkin | Learning to cooperate via policy search[END_REF] propose a distributed learning approach based on gradient descent method that also allows finding a Nash equilibrium. [START_REF] Emery-Montemerlo | Approximate solutions for partially observable stochastic games with common payoffs[END_REF] approximate DEC-MDP solutions using one-step Bayesian games that are solved by a heuristic method. Alternatives to Hansen's exact dynamic programming algorithm [START_REF] Hansen | Dynamic programming for partially observable stochastic games[END_REF] have also been proposed by [START_REF] Bernstein | Bounded policy iteration for decentralized pomdps[END_REF] and Amato et al. [START_REF] Amato | Optimizing memory-bounded controllers for decentralized pomdps[END_REF]. They use memory bounded controllers to limit the required amount of space to solve the problem. Recently, Wu et al. [START_REF] Wu | Point-based policy generation for decentralized pomdps[END_REF] have improved the scalability of Amato et al.'s approach [START_REF] Amato | Optimizing memory-bounded controllers for decentralized pomdps[END_REF] by avoiding the full backup performed at each step of the policy computation.

Finally, some approaches introduce direct communication so as to increase each agent observability [START_REF] Goldman | Optimizing information exchange in cooperative multiagent systems[END_REF], Xuan et al., 2001, Pynadath and Tambe, 2002]. The agents communicate to inform the other agents of their local state or observation. If communication is free and instantaneous and the system state is jointly observable, the problem is reduced to a Multiagent Markov Decision Process (MMDP) [START_REF] Boutilier | Decisiontheoretic planning: Structural asumptions and computational leverage[END_REF] that is easier to solve. Otherwise, the problem complexity remains unchanged and heuristic methods are described to find near optimal policies.

DEC-MDP approaches for multi-robot systems

Even if DEC-MDP approaches describe a powerful framework to formalize and solve multiagent decision problems, several issues arise while considering problems of decentralized control in real-world multi-robot systems. [START_REF] Bresina | Planning under continuous time and resource uncertainty: A challenge for ai[END_REF] point out some difficulties in formalizing robotic planning problems using markovian models. Indeed, this framework considers a simple model of time and actions. All actions are assumed to have the same duration (one time unit) so the agents are assumed to be fully synchronized. Moreover, DEC-MDPs do not take into account temporal and precedence constraints on action execution. The high complexity of optimally solving DEC-MDPs also reduced their applicability since it is difficult to solve problems involving more than two agents.

In this section we introduce two approaches based on DEC-MDPs that have been proposed to reduce the gap between the kinds of problems DEC-MDPs can solve and real world multi-robot applications. These models improve time and action representations and propose efficient approximate algorithms that can solve large problems considering constraints on task execution.

OC-DEC-MDP

The Opportunity Cost Decentralized Markov Decision Process (OC-DEC-MDP) framework [Beynier and[START_REF] Beynier | [END_REF][START_REF] Beynier | [END_REF] has been proposed to modelize and solve problems of decentralized control in multi-robot systems such as the ones presented at the beginning of the chapter. Because of communication limitations and unreliability of information exchange, communication between the agents (i.e. the robots) is assumed to be impossible during task execution. In order for a task to be successfully executed, temporal, precedence and resource constraints must be respected. Temporal constraints define, for each task t i , a temporal window during which the task should be executed. Precedence constraints partially order the tasks by representing preconditions on task execution such as "task t j must be finished before t i can start". Finally, resource constraints guarantee that an agent has enough resources to execute a task.

Mission Definition

Problems of decentralized control in multi-agent systems that are considered in the OC-DEC-MDP framework, are defined as a mission X which stands for a couple < Ag, T > where:

• Ag = {Ag 1 , • • • , Ag n } is a set of n agents Ag i ∈ Ag. • T = {t 1 , • • • , t p } is the set of tasks to execute.
The problem is for the agents Ag i ∈ Ag to execute the set of tasks T . The problem of task allocation is out of the scope of this chapter and tasks are supposed to be divided among the agents. Note that task allocation must take into account each agent's skills and must result in a feasible mission. Thus, there must be at least one interval of execution per task which respects temporal and precedence constraints. [START_REF] Hanna | Task selection as decision making in multiagent system[END_REF], and more recently Abdallah and Lesser [START_REF] Abdallah | Modeling Task Allocation Using a Decision Theoretic Model[END_REF], have developed MDP based algorithms that can perform such an allocation. Allocation of tasks among physical robots have also been studied by Gerkey et al. [START_REF] Gerkey | Sold!: Auction methods for multi-robot coordination[END_REF] and Esben et al. [START_REF] Esben | Multi-robot task allocation in the light of uncertainty[END_REF] using auction principles.

As shown on Figure 2, a mission can be represented by an acyclic graph. This example describes a mission involving three planetary rovers. Edges stand for precedence constraints and nodes represent the tasks. • an agent Ag i that has to execute the task.

• different possible durations δ i . P t (δ i ) is the probability the execution of t i takes δ i time units.

• different possible resource consumptions ∆ i r . P r (∆ i r ) is the probability the execution of t i consumes ∆ i r resources. • temporal constraints: each task t i is assigned a temporal window

T C i = [EST i , LET i ]
during which it should be executed. EST i is the Earliest Start Time of the task and LET i is its Latest End Time.

• precedence constraints: each task t i has a set of predecessors P red i which defines the tasks to be executed before t i can start.

∀t i ∈ T , t i ∈ root ⇔ ∃t j ∈ T : t j ∈ P red(t i )
where root refers to the first tasks to be executed, i.e. the tasks without predecessors. Coordination constraints similar to our precedence constraints are described in frameworks such as TAEMS (Task Analysis, Environment Modeling and Simulation) [START_REF] Decker | Quantitative modeling of complex environments[END_REF] which is used to describe task structures of multiagent systems.

• a reward R i which is the reward the agents obtain when t i is successfully executed (respecting temporal, precedence and resource constraints).

Given a mission X , the agents' aim consists in maximizing the sum of the cumulative reward they obtain during task execution. Because of the decentralized nature of the decision process and communication limitations, each agent must be able to decide, in a cooperative way, which task to execute and when, without communicating (during task execution) and with respect to constraints.

OC-DEC-MDP model

In order to model large problems, the OC-DEC-MDP model represents the multiagent decision problem as a set of MDPs where each MDP stands for a single agent decision problem. The policy of an agent Ag i will therefore be deduced from Ag i 's MDP. Since each agent observe all the information it needs to make a local decision, MDPs are defined (not POMDPs) and the framework is referred as OC-DEC-MDPs.

Definition 3 An n-agent OC-DEC-MDP is a set of n MDPs, one for each agent. The MDP of an agent Ag i is defined as a tuple < S i , T i , P i , R i > where:

• S i is the finite set of states of the agent Ag i ,

• T i is the finite set of tasks of the agent Ag i ,

• P i is the transition function of the agent Ag i , • R i : T i → R is the reward function of the agent Ag i .
Because of interactions between the agents, local MDPs are not independent of each others. Moreover, the components of the MDPs must be defined so as to represent constraints on task execution. The remaining of this section details each component of a local MDP.

States The state space of an agent (i.e. of its MDP) is composed of three kinds of states: success states, partial failure states and failure states.

• Success states: Let us consider an agent Ag i which has just successfully executed a task t i during an interval I and let r be the agent's remaining resources. At the end of t i 's execution, the agent Ag i moves to a success state and must decide its next action. This action depends on the last successfully executed task t i , its interval I and the remaining resources r. Thus, a success state of Ag i is defined as a triplet [t i , I, r].

• Partial failure states: When an agent Ag i starts to execute a task t i+1 at st but fails because the predecessors of t i+1 are not finished, it moves to a partial failure state [t i , [st, st + 1], et(I ), r] where t i stands for Ag i last successfully executed task, et(I ) is the end time of t i and r is Ag i 's remaining resources after it partially fails.

When an agent starts to execute a task t i+1 before the predecessors of t i+1 have finished their execution, the agent immediately realizes that the execution of the task partially fails. This means that the agent Ag i , at st + 1, realizes that it fails. As the agent could retry to execute the task later, this state is called a partial failure state. Thus, if precedence constraints are respected when the agent retries to execute t i+1 , the task could be successfully executed.

• Failure states: When an agent Ag i starts to execute a task t i+1 and it lacks resources or it violates temporal constraints, it moves to the failure state [f ailure ti+1 , * , * ] associated to t i+1 .

Tasks -Actions At each decision step, the agent must decide when to start its next task. The actions to perform thus consist of "Executing the next task t i+1 at time st: E(t i+1 , st)", that is the action to start executing task t i+1 at time st where st respects temporal constraints. Actions are probabilistic since the processing time and the resource consumption of the task are uncertain. Precedence and temporal constraints restrict the possible start times of each task. Consequently, there is a finite set of start times for each task and a finite action set.

Transition Function

The transition function of an agent Ag i gives the probability that Ag i moves from a state s i to a state s i when it starts to execute a task t i+1 at st. Since the execution of t i+1 can lead to three different kinds of states, three kinds of transitions have to be considered: successful transitions, partial failure transitions and failure transitions. Transition probability computation differs for each kind of transition. Let us assume that an agent Ag i tries to execute a task t i+1 at st.

• Successful transitions: The probability that Ag i successfully executes t i+1 relies on: the probability the predecessors of t i+1 have finished at st (given by the probabilities on the end times of the predecessors), the probability Ag i has enough resources to execute the task (given by the probabilities on resource consumptions of t i+1 ), and the probability Ag i finishes the execution of the task before its deadline (given by probabilities on the durations of t i+1 ).

• Partial failure transitions: The probability that Ag i moves to a partial failure state is the probability that the predecessors of t i+1 have not finished at st and Ag i has enough resources to be aware of its partial failure. The probability that the predecessors have not finished at st is the probability that they will finish later or they will never finish.

• Failure transitions: An agent fails to execute its task if it lacks resources or temporal constraints are violated. The probability that Ag i lacks of resources is given by the probability the execution of t i+1 consumes more resources than available or the agent partially fails and the necessary resources to be aware of it are not sufficient.

If st > LET i+1 -min(δ i+1 ), the agent starts the execution of t i+1 before the latest end time of t i+1 (LET i+1 -min(δ i+1 )). Temporal constraints are therefore violated and the agent fails.

When st ≤ LET i+1 -min(δ i+1 ), the agent may also violate temporal constraints. Indeed, if the duration δ i+1 is so long that the deadline is met (st + δ i+1 > LET i+1 ), the agent fails. The probability of violating the deadline therefore relies on duration probabilities.

In order to define transition functions, probabilities on start times and end times of the tasks must be known. The probability an agent starts to execute a task t i+1 at st relies on the agent's policy, on its available resources and on the ends times of the predecessors of t i+1 . Moreover, the predecessors' end times depend on the policies of their agents. Thus, the agents' policies have to be known to compute probabilities on start times and end times. Assuming an initial set of policies for the agents (one policy per agent), a propagation algorithms has been developed [START_REF] Beynier | A polynomial algorithm for decentralized markov decision processes with temporal constraints[END_REF] to compute such probabilities. This algorithm propagates constraints through the mission graph from the roots to the leaves. Each time a node (i.e. a task) t i is considered, its temporal probabilities (probabilities on start times and end times) and resource probabilities are computed using temporal and resource probabilities of the predecessors of t i and using the policy of t i . Once all the nodes have been considered, transition probabilities can be deduced from temporal probabilities and probabilities on resource consumptions.

Reward function When it successfully executes a task t i+1 , the agent Ag i moves to a success state and obtains the reward associated with t i+1 . If the agent partially fails, no reward is obtained. Finally, if the agent permanently fails the execution of t i+1 , it is penalized for all the tasks it will not be able to execute due to the failure of t i+1 .

Complexity Analysis A joint policy for the agents in an OC-DEC-MDP is a set of individual policies π 1 • • • π n where π i is a local policy for an agent Ag i in the OC-DEC-MDP.

Theorem 1 Optimally solving an OC-DEC-MDP requires an exponential amount of computation time.

Proof: Optimally solving an OC-DEC-MDP consists in finding a joint policy that maximizes the global performance [START_REF] Bernstein | The complexity of decentralized control of mdps[END_REF]. From the definition of a joint policy for an n-agent OC-DEC-MDP, we can deduce that the number of possible joint policies is exponential in the number of joint states. Evaluating a joint policy can be done in polynomial time through the use of dynamic programming [START_REF] Goldman | Decentralized control of cooperative systems: Categorization and complexity analysis[END_REF].

In fact, we use standard policy evaluation algorithms for MDPs since the policy to evaluate is a mapping from joint states to joint actions: the states of the MDPs are the joint states s = s 1 • • • s n where s i is a local state of Ag i in the OC-DEC-MDP and the actions of the MDP are the joint actions a = a 1 , • • • a n where a i is an action of Ag i in the OC-DEC-MDP. Finding an optimal policy for an n-agent OC-DEC-MDP consists in evaluating all the possible local policies and therefore requires an exponential amount of computation time.

Constraints affect the policy space but have no effect on the worst case complexity. They reduce the state space and the action space. Thus, the policy space can be reduced. Nonetheless, the number of policies remains exponential. Consequently, dealing with constraints does not result in lower complexity.

Due to the high complexity of OC-DEC-MDPs, it is untractable to optimally solve large size of problems. It is thus better to turn towards an approximate planning approach that can solve large size of problems and computes a solution that is closed to the optimum. Indeed, developing an optimal algorithm would limit the size of problems that can be solved in practice and real-world multi-rover applications could not be considered.

Decision Problem

During task execution, each agent has a local view of the system and does not know the other agents' states nor actions. If the execution of a task t i starts before its predecessors finish, it partially fails. Partial failures consume restricted resources and can lead to insufficient resources. If an agent lacks resources it will be unable to execute its remaining tasks. Consequently, the agents tend to avoid partial failures. One way to restrict partial failures consists in delaying the execution of the tasks. As a result, the likelihood that the predecessors have finished when an agent starts to execute a task increases and less resources are "wasted" by partial failures. Nonetheless, the more the execution of a task is delayed, the more the successors are delayed and the higher the probability of violating temporal constraints. In fact, the probability the deadline is met and the agent fails permanently executing the task increases.

The problem is to find a local policy for each agent that maximizes the sum of the rewards of all the agents. Thus, the agents must trade off the probability of partially failing and consuming resources to no avail against the consequences of delaying the execution of a task. Indeed, to maximize the sum of the expected rewards, each agent must consider the consequences of a delay on itself and on its successors.

Opportunity Cost and Expected Value For purposes of coordinating the agents, the notion of Opportunity Cost has been introduced by Beynier and Mouaddib [Beynier and[START_REF] Beynier | [END_REF][START_REF] Beynier | [END_REF]. It is borrowed from economics and refers to hidden indirect costs associated with a decision. In the OC-DEC-MDP framework, Opportunity Cost measures the indirect effect of an agent's decision on the other agents. More specifically, the Opportunity Cost is the loss of expected value resulting from delaying the execution of the other agents' tasks. Taking this cost into account leads to better coordination among the agents: it allows each agent to consider how its decisions influence the other agents.

Consequently, the policy of an agent Ag i in a state s i is computed using two equations. The first one is a standard Bellman equation that computes the expected utility of an agent Ag i and considers the tasks Ag i still has to execute:

V (s i ) = Immediate Gain R(s i ) + Expected Utility max E(ti+1,sti+1),sti+1≥t (V (E(t i+1 , st i+1 ), s i )) (1)
where

s i =< t i , [st i , et i ], r ti > (and et i = t) or s i =< t i , [t -1, t], et i , r ti >. If s i is a success state ( s i =< t i , [st i , et i ], r ti >)
, the agent obtains a reward for successfully executing task t i and R(s i ) = R(t i ). Otherwise, R(s i ) = 0.

V (E(t i+1 , st i+1 ), s i )) denotes the expected utility of the agent while executing E(t i+1 , st i+1 ) from state s i . Since the execution of the action can lead to different types of transitions, V (E(t i+1 , st i+1 ), s i )) is defined as:

V (E(t i+1 , st i+1 ), s i ) =V suc (E(t i+1 , st i+1 ), s i ) + V P CV (E(t i+1 , st i+1 ), s i ) + V f ail (E(t i+1 , st i+1 ), s i )
where V suc (E(t i+1 , st i+1 ), s i ) is the expected value of the agent when t i+1 is successfully executed at st i+1 , V P CV is the expected value of the agent when the execution of t i+1 starts at st i+1 and partially fails, and V f ail is the expected value if the agent start executing t i+1 at st i+1 and it lacks resources or temporal constraints are violated.

The second equation computes the best foregone action using a modified Bellman equation in which an Expected Opportunity Cost (EOC) is introduced. It allows the agent to select the best action to execute in a state s i , considering its expected utility and the EOC induced on the other agents:

π i (s i ) = argmax E(ti+1,sti+1),sti+1≥eti Expected Utility V (E(t i+1 , st i+1 ), s i ) - Expected Opportunity Cost EOC(t i+1 , st i+1 )
(2) where:

• argmax denotes the operator which returns the action E(t i+1 , st i+1 ) which maximizes the trade-off between the expected utility V of the agent and the expected opportunity cost provoked on the other agents.

• EOC(t i+1 , st i+1 ) is the expected opportunity cost the execution of t i+1 will induce if it starts at st i+1 .

Thus, the most valuable foregone action is selected by considering:

• The expected value, computed using a standard Bellman equation (Equation 1). It takes into account the expected value of executing the agent's remaining task.

• The expected opportunity cost provoked on the other agents.

The EOC induced on the other agents when t i+1 starts at st is defined as follows:

EOC(t i+1 , st) = P suc • Agj ∈Ag,j =i EOC Agj ,ti+1 (et i+1 ) (3)
+P f ail Agj ∈Ag,j =i EOC Agj ,ti+1 (f ail)

+ P P CV • EOC(t i+1 , st )
where et i+1 is a possible end time of t i+1 , EOC Agj ,ti+1 (et i+1 ) is the EOC induced on the agent Ag j when t i+1 ends at et i+1 . It is computed using Equation 4. EOC(t i+1 , st ) is the OC when the execution of t i+1 partially fails and the agents re-tries to execute the task at st (the next start time of the task). P suc stands for the probability to successfully execute the task, P P CV is the probability to fail partially because the predecessors have not finished. P f ail is the probability to fail permanently.

EOC values can be deduced by considering the delay provoked on the successors. The Expected Opportunity Cost described in Equation 3 is given by :

EOC Agj ,ti+1 (et ti+1 ) = rt j P tj ra (r tj ) • OC tj (∆t, r tj ) (4)
where t j is the nearest task that will be executed by Ag j (the distance between two tasks t i and t j is given by the number of nodes that belongs to the shortest path between t i and t j in the mission graph). P tj ra (r tj ) is the probability that Ag j has r tj resources when it starts to execute t j . ∆t is the delay induced on t j when t i+1 ends at et ti+1 . This delay is computed by propagating temporal constraints between t i+1 and t j . OC tj (∆t, r tj ) is the Opportunity Cost provoked on t j when it is delayed by ∆t. It stands for a difference in expected value computed as follows:

OC tj (∆t, r tj ) = V 0,rt j tj -V ∆t,rt j tj (5)
where V 0,rt j tj is the expected value of Ag j if the execution of t j is not delayed and the agent has r tj resources when it starts to execute t j . V ∆t,rt j tj is the expected value of the agent Ag j when the execution of t j is delayed by ∆t and the agent has r tj resources when it starts to execute t j .

If the execution of t i+1 fails, t j could not be executed because of violation of precedence constraints. Then, EOC Agj ,ti+1 (f ail) is given by:

EOC Agj ,ti+1 (f ail) = OC tj (f ail) = rt j P tj ra (r tj ) V 0 tj ,rt j -V ([f ailure tj , * , * ])
Policy computation Given a state s i of an agent Ag i , Equation 2 allows for the agent to decide its policy from s i . Beynier and Mouaddib [START_REF] Beynier | An iterative algorithm for solving constrained decentralized markov decision processes[END_REF] have proposed an iterative revision algorithm which applies this decision method to each state of each agent and computes an approximate solution to the multiagent decision problem. The algorithm consists in iteratively improving an initial policy set. At each iteration step, the agents improve their initial local policy at the same time. Given the initial policies that have been used to compute temporal and resource probabilities, each agent tries to improve its own policy. At each iteration step, each agent Ag i traverses the task graph in the reverse topological order and, revises the execution policy of each task (node), using Equation 2. While revising the policy of t i , Ag i considers all the states s i from which t i can be executed (states associated to the previous task t i-1 of Ag i ). The expected value of s i is then computed and its policy is deduced. This process is repeated until no changes are made. An equilibrium is then reached.

Experiments

Experiments have been developed to prove the scalability, the efficency and the applicability of OC-DEC-MDPs. Experiments show that large problems can be solved using the OC-DEC-MDP framework. Indeed, missions of hundreds of tasks and more than twenty agents can be considered. The performances obtained at each iteration step have also been studied by running mission executions. Experiments illustrate that the performance of the agents increases with the number of iterations. By iterating the process, the likelihood the agents fail because of partial failure resource consumption and because of lack of resources, decreases. The resulting policy is safer than policies of previous iterations and the gain of the agents is steady over executions. A near optimal policy is obtained at the end of the first iteration. Second iteration leads to small improvements but it diminishes the number of partial failures. Finally, the OC-DEC-MDP framework has been applied to real-world scenarios using Koala robots. Scenarios derived from Mars rover missions were considered. Figure 3 represents a scenario involving two robots that have to explore a set of 8 interesting places. The first robot (robot Ag 1 ) can take pictures and the second one (robot Ag 2 ) can take and analyse ground samples. Robot Ag 1 must take picture of sites A, B, D, E, F , H and J, and robot Ag 2 must analyse sites C, D, F , H and I. Sites are ordered so as to minimize travelling resource consumptions. Furthermore, precedence constraints have to be taken into account. As taking samples of the ground may change the topology of the site, pictures of a site must be taken before the other robot starts to analyse it. Moreover, robot Ag 1 must have left a site before robot Ag 2 can start to analyse it. Thus, robot Ag 1 must have taken a picture of site D before robot Ag 1 enters this site. Temporal constraints have also to be considered: visiting earliest start times and latest end times are associated with each site.

The mission was represented using a mission graph (Figure 4). Then, the corresponding OC-DEC-MDP was automatically built and solved by the iterative algorithm. Finally, resulting policies were implemented on Koala robots. During task execution, robots only have to execute their policies which map each state to an action. Thus, initial ambitions about the limitation of computational resources needed to make a decision have been fulfilled. Coordination performs well even if robots cannot communicate. Temporal and precedence constraints are respected. As shown on Figure 5 for the crossing point D, while deciding when to start its action, the first robot takes into account the fact that the other robot waits for him (thanks to the OC). The decision of the second robot is based on the probability that robot Ag 1 has left the site, the cost of a partial failure, and the robot's own expected value. Thus, robot 1 enters site D, completes its task (Picture 2) and leaves the site (Picture 3). Then, robot Ag 2 tries to enter the site (Picture 4). As robot 1 does not know the other robot actions, it may try to enter the site and fails because the other robot has not finished to take the picture. The second robot realizes that it fails when it tries to enter the site. If precedence constraints are not respected the robot returns to its last position. If temporal constraints are respected, the robot enters the site (Picture 4). These experiments show that the OC-DEC-MDP approach can be used by physical robots which are thus able to successfully and cooperatively complete their mission.

2V-DEC-MDP for flocking and platooning

In [START_REF] Mouaddib | Towards multiobjective 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. It is based on MDP with an online coordination part. Assuming without loss of generality that all agents are identical, a 2V-DEC-MDP is a set of 2V-MDP, one per agent. A 2V-MDP is composed by an off-line part, an MDP, and an on-line part to adapt its actions with the other agents. The MDP is a tuple S, A, P, R , with:

• S a set of states,

• A a set of action,

• P : 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, an expected reward is defined on a finite horizon T . The optimal value function V * of a state is defined by:

V * (s) = max a∈A (R(s, a) + s ∈S P (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 P (s, a, s ) • V * (s )), ∀s ∈ S
The neighborhood for an agent i is defined as the set of states of (detected) agents who can interact with i. Until now, it is assumed that all the agents near enough (according to a fixed maximum distance d) could be detected and their states could be known. Taking into account partial observability will be the subject of some future works. If the neighborhood is too big, it can be restricted to a subset (more the neighborhood will be big and more the policy will be good but more the computation of this policy will take time).

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 impact on the group are:

• ER for the individual reward (the value of the optimal policy of the MDP),

• JER for the group interest,

• JEP for the negative impact on the group.

Using those functions, the agents will use a LexDif f operator to choose the policy (i.e. the best action) to apply.

LexDif f builds a vector v = (ER(π i ), JER(π i ), JEP (π i )) for every π 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 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 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. Thanks to this design, the DEC-MDP is expressed as a set of 2V-MDP, allowing the coordination problem to be tractable. In [START_REF] Boussard | Vector valued markov decision process for robot platooning[END_REF], ER JER and JEP have been defined for platoon emergence, but this work does not try to keep the shape of the platoon.

2V-DEC-MDP-Based approach for flocking

2V-DEC-MDP has been used to formalize the problem, by translating the three criteria into three formulae (each formula having one or more equations) which will parameterize each 2V-MDP. Three functions have been defined: ER as the alignment criterion, JER as the cohesion criterion and JEP as the separation criterion.

Notations

• s j i is the state j of agent i (the environment being reduced to a discrete set of possible positions, a state is one position of this set and one orientation),

• -→ s = (s 1 , . . . , s N ) is the joint state vector,

• f ace(s) gives all the agents the are closer to the objective than s,

• distance(s 1 , s 2 ) gives the number of actions needed to go from s 1 to s 2 ,

• angle(s 1 , s 2 ) gives the angle between the orientation of s 1 and the one of s 2 : angle(s 1 , s 2 ) = orientation s 1 -orientation s 2 angle max

• back(s) gives the next place available behind s (if s 1 , the location just behind s according to the orientation of s, is available, s 1 is returned. If it is not available, back(s 1 )) is returned.

So now, using those definitions, the formulae for ER, JER and JEP can be written in the platooning context: sense for it and, typically, w ER to 0.49 and w JER to 0.51. For a non-leader, w JEP = 0.35, w ER = 0.32 and w JER = 0.33 (except if a leader is detected behind the agent, in which case w JER = w JEP = 0, and w ER = 1). Finally, for any agent, w JER = 0 as soon as it is near to the objective of the platoon. Experimentations proved that values of those weights do not change anything on the behavior of the agents. The only important thing is the order of those weights: the most important criteria has to have the biggest weight, the second criteria has to have the second weight, etc., so values for those weights could be chosen arbitrary.

Experiments with real robots

After testing the approach on a simulator, tests on real robots (Koalas) have been developped. Those robots know the "map" of the environment they are evolving in and have local visibility, so they know the position and orientation of the agents around them. A 2V-DEC-MDP, parameterized as described before, is running on them. An example with 3 robots is shown on Figure 6. Robots are placed on a same line, and an objective in front of them is given (the door on the right side). Figure 7, Figure 8 and Figure 9 are captions of those tests. When the test starts, the closest robot to the objective chooses the ER1 function and goes toward its objective. Because of the JER function, it waits for the other agents. In the same time, the two other agents follow the first one: according to the ER2 function, one of them chooses to follow the first agent, while the other one chooses to take the third place.

The platoon then emerges from those interactions: we can see the robots in their initial position in Figure 7, and their position after a few moves in Figure 8. Then, in Figure 9, we can see the fully shaped platoon.

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

Conclusion

Decentralized decision making is an appropriate approach for multi-robot applications since they are able to support uncertainty, partial observability and decentralized control. Even if Decentralized Markov Decision Processes suffer from a high complexity, the structure of multi-robot decision problems such as constraints on task execution (exploration mission) or locality of interactions (platooning) can be exploited to reduce the complexity. This chapter presented two approaches based on DEC-MDPs that have been proved to solve efficiently multi-robot cooperative problems. These approaches allow us to derive individual cooperative policies for the robots such that a global utility is maximized. The coordination in those approaches is considered during the computation of the policies by evaluating the effect of a local decision on the other robots. In the opposite to that, classical multiagent planning techniques address the problem of coordination in two steps: computing plans and then coordinating them. The second step requires in general a costly communication between the robots that limits their applicability in real-world applications (communication not always available, costly and time consuming). Another drawback of classical approaches is when the execution deviates from the expected behavior and thus re-planification and re-coordination are required that can reduce the performance of the system during the execution. Another contribution of decentralized decision models is to better formalize the flocking techniques by improving their robustness, supporting the uncertainty and assessing the quality of the global behavior.

Markov Decision Processes have also been successfully used to solve decentralized decision problems in non Artificial Intelligence domains. For instance, decision problems of search and storage in peer-to-peer server networks have been solved using a set of Interactive Markov Decision Processes [START_REF] Beynier | Decentralized decision making process for document server networks[END_REF].

Future works in multi-robot domain should concern the extension of the DEC-MDPs to deal with problems involving human and robot interactions such as mixed initiative techniques [START_REF] Weld | Robots that work in collaboration with people[END_REF], Sidner and Lee, 2005, Freedy et al., 2008]. These systems can operate mostly autonomously, but may need supervision or help in particular situations. Examples include mobile robots or intelligent vehicles navigating in a narrow corridor or heavy traffic, or avoiding risky areas that could cause costly failures. Similarly, robots performing complex surgical operations may require supervision and intervention of the specialist. In these applications, a supervision unit, often a human operator, can take over control when the situation is too complex for the autonomous system [START_REF] Crandall | Validating human-robot interaction schemes in multitasking environments[END_REF]. While the supervision unit (e.g., a driver, a surgeon, or a control center operator) may be able to perform each task by manually controlling the system, this would normally result in a time-consuming, costly operation. The problem is therefore to develop a general framework for supervision unit -autonomous unit teaming, to optimize performance and reduce the supervision unit work-load, costs, fatigue-driven errors and risks [START_REF] Green | Human-robot collaboration: A literature review and augmented reality approach in design[END_REF].

Figure 1 :

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

Figure 2 :

 2 Figure 2: Mission graph

Figure 3 :

 3 Figure 3: Two-robot exploration scenario

Figure 5 :

 5 Figure 5: Execution of the mission (crossing point of site D)

Figure 6 :

 6 Figure 6: Scenario of multi-robot platooning

Figure 7 :

 7 Figure 7: Initial situation Figure 8: After few moves Figure 9: Platoon is formed

The Robocup rescue competition defines a score based on the number of rescued civilians, the rate of burned buildings, etc.

Decentralized Partially Observable Markov Decision Processes (DEC-POMDPs) generalize DEC-MDPs to formalize problems where the state of the system is partially observable[START_REF] Bernstein | The complexity of decentralized control of mdps[END_REF].

Alignment

ER(s, a) = s ∈S p(s, a, s )ER i , i = 1, 2, 3 Depending on the situation, ER i are defined by:

where s b1 = back(s j ), s b2 = back(leader) and V * (s) a function of the expected distance between s and the objective of the platoon. distance(s 1 , s 2 ) gives the cost of going from a state s 1 to a state s 2 and angle(s 1 , s 2 ) gives the cost of rotating from the orientation of s 1 to the one of s 2 . Thus, it has been added to those equations two costs: the cost of going from a state s 1 to a state s 2 , wich means the cost of reaching the position of s 2 AND rotating to the good orientation. The angle is divided by the maximum angle to be sure that the cost of the distance will always be bigger than the cost of the angle, so the agent will not choose to stay on a distant place for saving the cost of a rotation. In ER 2 and ER 3 , back(target) is used instead of target, because the agent wants to go behind its target.

An agent does not have the same objectives whether it is on a leader position or inside a platoon. Indeed, a leader will move in the direction of its objective, while a non-leader agent will follow the one in front of it. Hence, an agent have to choose which equation to follow before resolving its 2V-MDP.

So, 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 . Finally, if it is inside a platoon and have no leader behind it, it chooses ER 2 .

Separation

Where D is the set of states of detected agents in neighborhood and C a constant equal to the cost of a collision between two agents.

Cohesion

Where K(s) is the function which estimate the gain of a given situation for the group. K(s) gives a reward if at least one agent is behind s.

After choosing an equation for the ER criteria, the agent has to fix the weight of ER, JER and JEP . For a leader, it is set w JEP to 0 since the criterion is with no