Aurélie Beynier

Abdel-Illah Mouaddib

An Iterative Algorithm for Solving Constrained Decentralized Markov Decision Processes

Despite the significant progress to extend Markov Decision Processes (MDP) to cooperative multi-agent systems, developing approaches that can deal with realistic problems remains a serious challenge. Existing approaches that solve Decentralized Markov Decision Processes (DEC-MDPs) suffer from the fact that they can only solve relatively small problems without complex constraints on task execution. OC-DEC-MDP has been introduced to deal with large DEC-MDPs under resource and temporal constraints. However, the proposed algorithm to solve this class of DEC-MDPs has some limits: it suffers from overestimation of opportunity cost and restricts policy improvement to one sweep (or iteration). In this paper, we propose to overcome these limits by first introducing the notion of Expected Opportunity Cost to better assess the influence of a local decision of an agent on the others. We then describe an iterative version of the algorithm to incrementally improve the policies of agents leading to higher quality solutions in some settings. Experimental results are shown to support our claims.

Introduction

Solving optimally Decentralized Markov Decision Processes (DEC-MDPs) is known to be NEXP [START_REF] Bernstein | The complexity of decentralized control of mdps[END_REF]. One way to overcome this complexity barrier consists in identifying specific classes of DEC-MDPs that can be solved more easily thanks to characteristics such as transition or observation independence [START_REF] Goldman | Decentralized control of cooperative systems: Categorization and complexity analysis[END_REF][START_REF] Becker | Decentralized markov decision processes with event-driven interactions[END_REF][START_REF] Becker | Transition-independent decentralized markov decision processes[END_REF]. Other approaches develop approximate solution algorithms [START_REF] Nair | Taming decentralized pomdps: Towards efficient policy computation for multiagent settings[END_REF][START_REF] Pynadath | The communicative multiagent team decision problem: Analyzing teamwork theories and models[END_REF][START_REF] Peshkin | Learning to cooperate via policy search[END_REF].

Nevertheless, solving large problems remains a serious challenge even for approximating approaches, that can solve relatively small problems. Moreover few approaches consider temporal or resource constraints on task execution. To address this shortcoming, OC-DEC-MDP has been introduced [START_REF] Beynier | A polynomial algorithm for decentralized markov decision processes with temporal constraints[END_REF]. This formalism can be used to represent large decision problems with temporal, precedence and resource constraints. Furthermore, a polynomial algorithm efficiently computes an approximation of the optimal solution considering these constraints.

This framework proposes to solve local MDPs in a decentralized way. Coordination is guaranteed thanks to Opportunity Cost (OC) which allows the agents to consider the consequences of their decisions on the other agents. Experiments proved that good quality policies are obtained even for large problems. Nonetheless, the algorithm for solving OC-DEC-MDP suffers from limitations. First of all, OC overestimates the influence of a decision on the other agents. Then, it may lead to fallacies or bad decisions. Moreover, this algorithm improves the initial policy of each task only once, the improvement process is not repeated. We suggest that reiterating the policy improvement should lead to better performance in some settings. In this paper, we propose to overcome these limits by first introducing the notion of Expected Opportunity Cost to better assess the influence of a decision on the other agents. Then we develop an iterative version of the algorithm. Higher quality policies could therefore be obtained in some settings.

We begin by formalizing the problem we are considering and by giving an overview of the approach described in [START_REF] Beynier | A polynomial algorithm for decentralized markov decision processes with temporal constraints[END_REF]. Next, we describe two directions to improve the existing algorithm for solving OC-DEC-MDP. We start with the description of the Expected Opportunity Cost and we present its benefits. We then describe an iterative version of the algorithm that allows policy improvement to be repeated. Finally, we give some experimental results on the scalability and the performance of our approach and conclude by discussing possible future issues.

Problem Statement

We consider a set of agents, for instance a fleet of robots, that have to execute a set of tasks respecting temporal, precedence and resource constraints. The problems X we deal with (introduced by Beynier and Mouaddib [START_REF] Beynier | A polynomial algorithm for decentralized markov decision processes with temporal constraints[END_REF]) can be described by a tuple < T, A, T C, P red, P c , P r , R, R ini >. T is a set of tasks t i to execute. A is a set of agents A i that have to execute T . T i denotes the set of tasks A i must execute. T C are temporal constraints among the tasks. Each task t i is assigned a temporal window T C(t i ) = [EST i , LET i ] during which it should be executed. EST i is the earliest start time of t i and LET i is its latest end time. P red are precedence constraints between the tasks. Each task t i has predecessors: the tasks to be executed before t i can start. The execution time of each Figure 1: A mission graph for planetary rovers task is uncertain. P c (δ c ) i is the probability that the activity t i takes δ c time units for its execution. Each task t i has several resource consumptions. P r (∆r) i is the probability that t i consumes ∆r units of resources. R is a reward function. R i is the reward an agent obtains when it has accomplished the task t i . R ini is the initial resource rate available for each agent before the mission starts.

During task execution, each agent has a local view of the system and do not know the other agents' states nor actions. The agents must be able to coordinate without communicating during the execution. This class of problems can be met in NASA scenarios dealing with rovers operating on Mars. In order to increase the scientific feedback, researchers plan to send fleets of robots that could operate autonomously and cooperatively. Since the environment is unknown, robots must deal with uncertainty regarding the duration of actions and consumption of resources. Once a day, a daily mission of a hundred tasks is sent to the robots via satellite. It allows the agents to communicate during a fixed amount of time. The agents can then plan their actions and communication is possible. For the rest of the day, the rovers must complete their tasks and cannot communicate via satellite due to orbital rotation. In addition, because of bandwidth limitations, the distance between the agents and obstacles, the agents are unable to communicate directly. To guarantee scientific feedback, temporal and precedence constraints must be respected. Pictures, for example, must be taken at sunset or sunrise because of illumination constraints. The tasks of an agent are ordered by precedence, temporal and resource constraints. Precedence constraints give a partial order which can be reduced to a total order while considering temporal constraints (possible execution intervals) and space constraints (we aim to minimize distance because of resource consumptions).

As shown on Figure 1, a problem X can be represented using a graph of tasks. This example describes a mission involving three planetary rovers. Edges stand for precedence constraints. Each task is assigned an agent. The problem of task allocation is out of the scope of this paper.

Temporal constraints restrict the possible intervals of execution and precedence constraints partially order the tasks. If the execution of a task t i starts before its predecessors finish, it fails. Because the agent could retry to execute t i later, this kind of failure is called a partial failure. 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 increases. If temporal constraints are violated during task execution, the agent fails permanently executing the task. This assumption can be easily relaxed without modifications of our approach.

The problem is to find a local policy for each agent that maximizes the sum of the rewards of all the agents. 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. To maximize the sum of the expected rewards, each agent must consider the consequences of a delay on itself and on its successors.

Existing OC-DEC-MDP Such problems have been formalized byg OC-DEC-MDPs [START_REF] Beynier | A polynomial algorithm for decentralized markov decision processes with temporal constraints[END_REF].

Definition 1 An OC-DEC-MDP for n agents is a set of n local MDPs. A local MDP for an agent A i is defined by a tuple < S i , T i , P i , R i > where: S i is the finite set of states of the agent A i , T i is the finite set of tasks of the agent A i , P i is the transition function and R i is the reward function.

Each component of a local MDP is defined by considering and representing precedence, temporal and resource constraints. The actions consist of Execute the next task t i at time st: E(t i , st). Precedence 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. Decisions rely on the last executed task, the end time of its execution, the current time and the available resources.

At each decision step, two kinds of states are considered: safe states and partial failure states. Safe states [t i , I, r] describe cases where the agent has just finished executing task t i during an interval of time I and its has r remaining resources. Partial failures [t i , I, et(I ), r] are also taken into account when the agent has just tried to execute task t i+1 duringq interval I but failed because execution of the predecessors was not finished. t i is the last task the agent has safely finished to execute at et(I ).

Theorem 1 An OC-DEC-MDP has a complexity exponential in the number of states.

Proof: Each agent's state is supposed to be locally fully observable. A joint policy is a mapping from world states

S = S 1 , • • • , S n to joint actions A = A 1 , • • • , A n
and the number of joint policies is exponential in the number of states |S|. Evaluating a joint policy can be done in polynomial time through the use of dynamic programming. The OC-DEC-MDP is therefore exponential in the number of states |S|. 2

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 a lower complexity.

Expected Opportunity Cost

As explained in [START_REF] Beynier | A polynomial algorithm for decentralized markov decision processes with temporal constraints[END_REF], each agent computes its own local policy by improving an initial policy. The probabilities on the end times of the other agents can therefore be deduced from this initial policy and each agent's transition function can be computed. If an agent modifies its own local policy without taking into account the influence of such changes on the other agents, the agents will not coordinate. When an agent decides when to start the execution of a task t i , its decision influences all the tasks that can be reached from t i in the mission graph. In order to coordinate, the agents must consider the consequences of their decisions on the other agents. The notion of Opportunity Cost is used in order to obtain coordinated policies. It allows each agent to measure the consequences of its decision on the other agents. While deciding when to start the execution of a task t i , each agent must trade off its expected utility against the OC it will provoke on the other agents. More specifically, the OC is the loss of expected value by the other agents resulting from delaying the execution of a task.

Previous work has demonstrated the usefulness of OC to predict the influence of a decision on the other agents. Nonetheless, the OC described previously does not compute exactly the loss in expected value due to a delay ∆t. First, resources available by the other agents are not taken into account. It has been assumed that resources do not influence the OC. Next, it has been assumed that the delay provoked by a task t i cannot be increased or decreased by other tasks. As these assumptions may lead to overestimation of the OC provoked on an agent, the influence of a decision may then be approximately computed leading the agents to fallacies.

Opportunity Cost and resources

Each agent's policy is influenced by the available resource rate. Expected utility depends on resources and the OC represents a loss in expected utility. It can be deduced that resources must be taken into account while computing the OC. For instance, if resources are very tight, the probability the agent will fail because of lack of resources is very high. Delaying a task has a low cost because whatever its start time, the likelihood its execution will fail is very high.

For each start time st t j of t j , bounded by [LB t j , U B t j ], and each resource rate r, OC is given by : OC tj (∆t, r) = V * 0,r

t j -V * ∆t,r t j where V * 0,r t j is the expected value if t j can start in [LB j , U B j ] with r resources, and V * ∆t,r t j is the ex- pected value if t j can start in the interval [LB j + ∆t, U B j ] with r resources.

Policy Computation and EOC

Revising the policy of a task t i consists in revising the policy for each state associated with t i . Previous work introduced an equation to compute a new policy for each task. Nonetheless, it considers the OC provoked on the successors. Such computation may lead to overestimation of OC because the delay provoked on an agent can be considered more than once. If there are several paths from a successor k to a task t j+1 , then the OC on t j+1 is considered several times. To overcome this issue, we propose to compute the EOC provoked on the other agents. The tasks that are influenced by the end time of t i+1 are the nearest tasks of the other agents. The nearest task of t i+1 executed by A j is the nearest task executed by A j that can be reached from t i+1 in the mission graph (in Figure 1, "agent 3: test the sample" is the nearest task of "agent 2: move to site A"). Assume that an agent A i ends a task t i+1 at et i+1 and t j is the nearest task executed by another agent A j . t i+1 induces an EOC on t j . If t i+1 ends at et i+1 this does not imply that t j can start at et i+1 . If t j is not a successor of t i+1 , there may be tasks between t i+1 and t j that can increase or decrease the delay. One solution to tackle this issue consists in computing the probability to provoke a delay ∆t j on t j when t i+1 ends at et i+1 . This explains why we consider EOC instead of OC.

New equations are therefore defined. The first one is a standard Bellman equation:

V (s) = immediate gain Ri(ti) + Expected value max E(t i+1 ,st),st≥et(I) (V ) (1)
where

s = [t i , I, r] or s = [t i , [st, st + 1], et(I ), r]. If s is a permanent failure state, V (s) = -R t i -suiv R suiv
where suiv is the set of tasks A i should execute after t i .

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

Π * (s) = arg max E(t i+1 ,st),st≥et(I)
Expected utility

V - EOC EOC(t i+1 , st) (2)
where EOC(t i+1 , st) is the EOC induced on the other agents when t i+1 starts at st. Since actions are not deterministic, we do not know exactly when the task t i+1 will end and the EOC it will induce. Different kinds of transitions must be taken into account so as to consider the possible end times of the task. The EOC induced on the other agents when t i+1 starts at st can be rewritten as follows:

EOC(ti+1, st) = Psuc • ag∈other agents EOCag,t i+1 (eti+1) (3)
+P f ail ag∈other agents EOCag,t i+1 (f ail)

+ P P CV • EOC(ti+1, st )
where other agents are the agents that do not execute t i+1 , et i+1 is a possible end time of t i+1 , EOC ag,t i (et i+1 ) is the EOC induced on the agent ag when t i+1 ends at et i+1 . It is computed using Equation 3. EOC(t i+1 , st ) is the OC when the execution of t i+1 partially fails and the agents retries to execute the task at st (the next start time given by the EOC-policy). The execution of t i+1 can lead to different transitions, therefore all these transitions must be considered in EOC(t i+1 , st). 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.

Revision algorithm

The previous work algorithm has been adapted to deal with EOC computation leading to a new revision algorithm (Algorithm 1). Both algorithms allow the agents to evaluate at the same time their own local MDP and to derive a new local policy from the initial policy. While computing its policy, an agent first considers the last level of its graph which consists of the last task it must execute. It then passes through its graph of tasks from the leaves to the root and evaluates its policy level by level.

Algorithm 1 Revision Algorithm 1: for level L n from the leaves to the root do 2: for all task t i in level L n do 3:

7:

for all start time st from U B t i to LB t i do

8:

for all resource rate r t i of a partial failure do

9:

Compute V and Π * for partial failure states: Using equation 3 we need to know the EOC provoked on the other agents when t i+1 ends at et i+1 . The delay provoked on the nearest tasks t k must therefore be known. This delay depends on the policies of the tasks between t i+1 and t j . Nonetheless, the algorithm passes through the graph from the leaves to the node. The policies of the tasks t i+1 and t j have been revised when t i+1 is considered. If the initial policy is used to compute these probabilities, it may lead to inaccurate results because of policy changes. Accurate probabilities can be deduced from the revised policies but A i does not know them unless all policy modifications are communicated to all agents.

[t i-1 , [st, st + 1], et(I ),
To overcome this difficulty, an update method has been developed. When an agent A j has finished revising the policy of a task t j , it computes the OC values of t j for each delay ∆t t j and each resource rate r t j of t j (line 19 of algorithm 1). These OC values are sent (line 20) to t j 's predecessor agents. These agents now revise the policy of t j 's predecessor tasks. They also update the received OC of t j following their revised policy (line 22) and send them to their predecessors. Finally, A i is going to receive the updated OC values of t j from its successors. Consequently, even if t j is not a direct successor of t i , when t i delays the execution of t k , the exact OC provoked on t j is known.

Thanks to our update method, EOC values can be deduced by considering the delay provoked on the successors. The OC described in Equation 3 is given by :

EOCag,t i (ett i ) = r t j P t j ra (rt j ) • OCt j (∆tsucc, rt j )
where t j is the nearest task that will be executed by ag and OC t j (∆t succ , r t j ) is the OC provoked on t j when the successors of t i are delayed by ∆t succ . This OC value is known since the agent received it from its successors. P t j ra (r t j ) is the probability that ag has r t j resources when it starts to execute t j . If t i has several successors and several delays are provoked, ∆t succ represents the maximum of these delays.

This method allows each agent to know the exact EOC provoked on the other agents without communicating revised policies. The agents only need to communicate OC values. When an agent evaluates the states associated with a task t i , it needs to know the EOC it will provoke on the other agents. Therefore, it must have received OC values from its successors. If these values have not been received yet, the agent waits until delivery. We assume that there is no loss of messages. As soon as OC values are known, the agent can compute its expected value and the policy of each state related to t i . Notice that even if decentralized execution of the algorithm requires off-line communication, the agents never communicate during the execution of the mission.

Theorem 2 The complexity of the revision algorithm is polynomial time in |S|.

Proof: In the worst case, none of the states can be evaluated at the same time and the algorithm has the same time complexity as a centralized algorithm which evaluates all the agents' states one by one. Therefore only one state is evaluated at a time. The time needed to pass trough the state space of each local MDP and to value each state is |S|. States have a form of [task, (end time), interval, resources], so |S| includes the number of tasks. We will assume that communication requires one time unit. There is #n OC values of OC to communicate. Then, the overall complexity of the algorithm is O(#n OC + |S|). As #n OC < |S|, the complexity can be re-written as O(|S|).2

Experiments

Experiments have been developed to test the influence of OC computation on performance. We have compared three kinds of OC : Opportunity Cost without resources (OC), OC with resources (OCr) and Expected Opportunity Cost (EOC). Our experiments have been achieved with a benchmark composed of different mission sizes.These experiments show the benefits of considering resources and EOC. We present results obtained on a scenario involving 2 agents and about 20 tasks. Figure 2 plots the reward the agents obtain over 1000 executions for different resource rates. When the agents have very few resources, OC computation has no influence on the performance. In fact, whatever their policy, the agents do not have enough resources to execute their tasks, the gain is near zero and delaying a task does not decrease the expected value. With large or unlimited resources, resources have no influence on the expected utility nor the OC. OCr and OC lead to the same performance. Unless, there are tight temporal constraints, delaying a task does not reduce the expected value, EOC and OCr are quite the same when resources are large.

Improvements are much larger when resources are tight. In this case, the agents have just enough resources to execute their tasks and partial failures may lead to permanent failures through lack of resources. Taking into account resources while computing the OC increases performance. Moreover, delaying a task can lead the other agents to fail partially and waste resources to no avail. Consequently, the agents accurately measure the consequences of their decisions on the other agents. EOC therefore achieves best improvement under tight resources (R ini ∈ [20, 30]).

Iterative Algorithm

The algorithm presented so far consists in improving an initial policy. When the revision algorithm stops, each task has been considered once and a new local policy is available for each agent. In order to obtain better solutions, we re-execute the revision algorithm considering that the initial policy is the policy we have just computed.

Iterative Process

At each iteration step, the agents improve their initial local policy at the same time. The outcome policies of iteration N -1 are the initial policies of iteration N . Obviously, the transition function depends upon the initial policy of the current iteration and must be updated for each iteration step. Once the new transition function is known, each agent can execute the revision algorithm to obtain new local policies. This process is repeated until no changes are made. A local optimum is then reached. Since each policy is considered once and there is a finite set of policies, we assure convergence.

Algorithm 2 Iterative Algorithm 1: nbChanges = 1 2: while nbChanges > 0 do 3: Compute the new transition function 4: nbChanges = 0 5: for all Agents Ai do 6:

Revise local policies πi 7:

nbChanges += number of local policy changes 8: end for 9: end while By iterating the algorithm each task is considered several times. We will consider a task t i and its predecessor task t j . At first iteration step t j is supposed to follow the initial policy. t i 's policy is revised assuming t j 's initial policy. Once the policy of t i is revised, t j will be considered and its policy may change. t j 's new policy is computed assuming the new policy of t i (thanks to EOC). Nonetheless, given the new policy of t j , t i may find a better policy. Using the iteration process, revision of t i 's policy is possible. Theorem 3 The complexity of the iterative is polynomial time in (N + 1) • |S| where N is the number of iterations. Proof: At each iteration step, the transition function is computed and the revision algorithm is executed. The complexity of the revision algorithm is polynomial time in |S|. The transition function is updated before each iteration step by propagating temporal constraints through the mission graph whose complexity is less than O(|S|). Then, the overall complexity of the algorithm is O((N + 1) • |S|). 2

Experiments

So that our iterative algorithm can be used to solve realistic decision problems, it must be able to consider large problems and to find good approximate solutions. The following experiments first test the scalability of our approach and then describe its performance.

Scalability The same space is required to iterate once or several times. We have proved that large problems can be solved by the revision algorithm. This assertion remains true while considering the iterative process.As in OC-DEC-MDP, this new approach can deal with large problems, for instance we can consider missions of 200 taks and 15 agents.

The running time of the iterative algorithm relies on the state space size of each agent, the branching factor of the mission graph and the number of iterations. The branching factor of the mission graph defines the number of tasks per graph level. The iterative algorithm revises all the tasks of a same level at the same time. The higher the branching factor is, the more tasks are revised at the same time. Running time is also influenced by the number of iterations. Most of the time, the final solution is reached within four iterations. Moreover, a solution is always available even if the algorithm has not finished its execution. Indeed, the initial policy of the last ended iteration can stand for a temporary solution. Experimental results show that for a mission graph of 20 tasks and 2 agents, the final solution is obtained within 25 seconds. For larger graphs, for instance 60 tasks and 2 agents, the final solution is returned within one minute. Graphs composed of hundreds of tasks can also be considered. Our approach can therefore deal with large problems that cannot be solved by other existing approaches.

Performance Other experiments have been developed to test the performance and convergence of the iterative algorithm. The number of iteration steps to converge has been studied. The performances obtained at each iteration step have been compared by running mission executions. The benchmark is the same as the one used for OC comparisons. EST-policy (select the Earliest Possible Start Time) is supposed to be the initial policy of the first iteration.

First, the number of iteration steps needed to converge has been studied. Experiments show that the algorithm always converges. Most of the time, it takes less than four iterations to converge. Figure 3 relates the number of iteration steps to the initial resource rate. With large or unlimited resources, only one iteration step is needed to converge. As the initial resource rate decreases, the number of iteration steps increases since it reaches a maximum which corresponds to a critical resource rate. If the agents initially have less resources than this critical rate, they will not be able to execute all the tasks. Whatever their policy, the latest tasks cannot be executed because of a lack of resources. Then, all the possible policies of these tasks are equivalent and there is no strictly better policy than the initial EST-policy.

Figure 4 describes the relationship between the initial re- Indeed, it can be proved that the initial policy is an optimal policy. As the initial resource rate decreases, more and more changes are needed to obtain the solution. If initial resources are low, the policy of the latest task remains unchanged and few changes are necessary. The number of policy changes per iteration has also been studied. Experiments demonstrate that the number of policy changes decreases at each iteration step. Most changes are made during the earliest iteration. The number of policy changes per iteration diminishes until it becomes null and convergence is reached.

Experiments demonstrate that the performance of the agents increases with the number of iterations. Moreover, it can be shown that first iteration achieves largest improvements. Subsequent iterations reduce the number of partial failures and lead to maximum gain. By iterating the process, the likelihood the agents fail 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: it does not fall when partial failures arise. Figure 5 plots the number of partial failures of the agents over 1000 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. When resources are tight, more iterations are needed to obtain a near optimal policy. Now, more benefits are gained from reiterating. As soon as the solution produces the maximum gain, re-iterating reduces the number of partial failures.

Related work

It is difficult to compare the performance of our approach with other works. We have in fact developed the first approach that can deal with large problems and several kinds of constraints. Other existing approaches can only solve small problems so, we were unable to compare our performance on large problems. Despite this lack of comparison, experiments show that most of the time, the iterative algorithm allows the agents to obtain the maximum reward. We may assume that our solutions are closed to the optimal.

Our results have been compared on smaller problems which can be solved by other approaches. The Coverage Set Algorithm (CSA) [START_REF] Becker | Transition-independent decentralized markov decision processes[END_REF] is the only algorithm that is able to deal with complex constraints and solve these problems. Despite the wide variety of problems formalized by CSA, it suffers from exponential complexity. In practice, only small problems with restricted constraints can be solved which have been proved to be solved optimally by our algorithm. We deduce that our approach performs as well as CSA, on the problems CSA can solve. Other existing approaches do not consider temporal and precedence constraints. We were therefore unable to compare our performance with algorithms such as JESP [START_REF] Nair | Taming decentralized pomdps: Towards efficient policy computation for multiagent settings[END_REF].

Nonetheless, it can be mentioned that JESP improves only one local policy at a time while our algorithm allows the agents' policies to be improved at the same time.

Conclusion

Most recent multiagent applications such as rescue teams of robots or planetary rovers demonstrate the need for cooperative decision making systems that can deal with large problems and complex constraints. Previous work provided a framework for solving large decision problems with temporal, precedence and resource constraints. Introduction of EOC in Bellman Equation improves the coordination of local policies. With EOC, each agent can accurately compute the consequences of its decision on the other agents. We proposed an iterative version of the previous algorithm for solving such problems in a decentralized way. This polynomial algorithm consists in improving each agent's local policy at the same time. This new algorithm does not reduce the size of the problems that can be solved. Moreover, higher quality policies are obtained and best improvements are obtained with tight resources and tight temporal constraints. It has been shown that the quality of the policies increases at each iteration step. Experiments show that our algorithm has anytime properties. Future work will explore this issue.

  while the agent doesn't have the OC values it needs do the failure state: [f ailure(t i ), * , * ]

  Figure 2: Influence of OC

FigureFigure 5 :

 5 Figure 4: Influence of resources

  r t i ]Compute V and Π * for the safe states:[t i , [st, st + ∆t 1 ], r t i ]

	10:	end for
	11: 12:	for all resource rate r t i of t i 's safe execution do for all duration ∆t 1 of t i do
	13:
	14: 15: 16:	end for Compute V end for	* ∆t,r t i k	where ∆t = st -LB t i
	17: 18: 19: 20: 21:	end for for all V k * ∆t,r t i Compute OC(∆t, r t i ) = V computed previously do * 0,r t i k -V Send OC(∆t, r t i ) to the predecessors for all task t j executed by another agent and for which OC values has * ∆t,r t i k
		been received do
	22:	Update the OC values and Send to predecessors
	23:	end for
	24:	end for
	25: end for
	26: end for


Élie Aur

Abdel-Illah Beynier

Mouaddib

A Polynomial Algorithm for Decentralized Markov Decision Processes with Temporal Constraints

Keywords: I.2.11 [Artificial Intelligence]: Distributed Artificial Intelligence-Multiagent systems; G.3 [ Mathematics of Computing]: Probability and Statistics-Markov processes Multi-agent systems, Markov decision Processes, Planning, Uncertainty

One of the difficulties to adapt MDPs for the control of cooperative multi-agent systems, is the complexity issued from Decentralized MDPs. Moreover, existing approaches can not be used for real applications because they do not take into account complex constraints about the execution. In this paper, we present a class of DEC-MDPs, OC-DEC-MDP, that can handle temporal and precedence constraints. This model allows several autonomous agents to cooperate so as to complete a set of tasks without communication. In order to allow the agents to coordinate, we introduce an opportunity cost. Each agent builds its own local MDP independently of the other agents but, it takes into account the lost in value provoked, by its local decision, on the other agents. Existing approaches solving DEC-MDP are NEXP complete or exponential, while our OC-DEC-MDP can be solved by a polynomial algorithm with good approximation.

INTRODUCTION

Markov decision processes (MDPs) and partially observable Markov Decision processes (POMDPs) have proved to be efficient tools for solving problems of mono-agent control in stochastic environments. That's why extensions of these models to cooperative multiagent systems, have become an important point of interest. Nonetheless, decentralization of the control and knowledge among the agents Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. AAMAS'05, July 25-29, 2005, Utrecht, Netherlands. . increases significantly the problem complexity, and effective methods to solve optimally decentralized MDPs are lacking. It has been proved that solving optimally DEC-MDP and DEC-POMDP is NEXP complete [START_REF] Bernstein | The complexity of decentralized control of mdps[END_REF]. Boutilier [START_REF] Boutilier | Sequential optimality and coordination in multiagents systems[END_REF] has proposed an extension of MDPs : the multi-agent Markov decision processes which is polynomial but, it is based on full observability of the global state by each agent. Other attempts allow the agents to communicate in order to exchange local knowledge : the DEC-POMDP with communication (DEC-POMDP-Com) proposed by Goldman and Zilberstein [START_REF] Goldman | Optimizing information exchange in cooperative multiagent systems[END_REF], the Communicative Multi-agent Team Decision Problem (COM-MTDP) described by Pynadath and Tambe [START_REF] Pynadath | The communicative multiagent team decision problem: Analyzing teamwork theories and models[END_REF], the multiagent decision process by Xuan and Lesser [START_REF] Xuan | Communication decisions in multiagent cooperation[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]. Becker et al. has identified two classes of decentralized MDPs that can be solved optimally : the Decentralized Decision Process with Event Driven Interaction (ED-DEC-MDP) [START_REF] Becker | Decentralized Markov Decision Processes with Event-Driven Interactions[END_REF] and the Transition-Independent Decentralized MDPs (TI-DEC-MDP) [START_REF] Becker | Transition-Independent Decentralized Markov Decision Processes[END_REF]. They are both exponential in the number of states, but they only deal with very small problems. Figure 1 sums up the complexity of existing approaches to solve decentralized MDPs. In this paper, we present a class of DEC-MDPs, Opportunity Cost DEC-MDP (OC-DEC-MDP), that can handle temporal and precedence constraints. This class of DEC-MDPs allows several autonomous agents to cooperate in order to complete a set of tasks (a mission) without communication. This OC-DEC-MDP can be solved by a polynomial algorithm and can deal with large mission graphs.

The mission of the agents we consider is an acyclic graph of tasks. Each task is assigned a temporal window [EST,LET] during which it should be executed. EST is the earliest start time and LET is the latest end time. The temporal execution interval of the activity should be included in this window. Each task ti has predecessors : the tasks that must be executed before ti can start, and a reward : the reward the agent obtains when it has accomplished the task. The execution times and the resource consumptions of the tasks are uncertain, each task has a set of possible execution times and their probabilities, and a set of possible resource consumptions and their probabilities. Their representation is discrete. Then, Pc(δc) is the probability that the activity takes δc time units for its execution, and P r(∆r) is the probability that an activity con-sumes ∆r units of resources. We assume that resource consumption and execution time are independent. But, this assumption does not affect the genericity of the model (we can use a probability distribution of (∆r, δc) such that P ((∆r, δc)) is the probability that the activity takes δc time units and consumes ∆r resources). Each node of the graph is a task and edges stand for precedence constraints. Figure 2 gives a mission example involving three agents (robots) that have to explore a radioactive land. Agent 1 has to complete radioactivity measurements and then compress the collected data. Agent 2 must snap target 2 , complete radioactivity measurements and analyze data. Agent 3 has to move to the target 1, and snap it. Edges stand for precedence constraints : the agents must have snapped the targets before agent 1 completes its radioactivity measurements. Temporal constraints are given thanks to temporal windows [EST, LET], mentioned by intervals : the radioactivity measurements on target 2 can't start before 5 and must be finished at 7. Our model can deal with more important and complex missions, and with others applications such as rescue teams of robots, satellites, ... Given these information, the problem is to choose, in an autonomous way, the best decision about which task to execute and when to execute it. This decision is based on the executed tasks and on the temporal constraints. Our approach consists of solving the multi-agent decision problem thanks to a Decentralized Markov Decision Process. The system is composed on agents 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 (OC) provoked by the current activity of the agent by delaying the activities of the other agents related to this activity. It measures the loss in value when starting the activity with a delay ∆t. This cost is the difference between the value when we can start on time and the value when our execution is delayed by ∆t. Each agent develops a local MDP independently of the local policies of the other agents but, it introduces in its expected value the opportunity cost of the possible delay provoked by his activity.

Goldman and Zilberstein [START_REF] Goldman | Decentralized control of cooperative systems : Categorization and complexity analysis[END_REF] have identified properties of the DEC-MDP and DEC-POMDP that influence the complexity of the problem. Our OC-DEC-MDP is locally fully observable : each agent fully observes its local state. Moreover, it is observation independent : the probability an agent observes O is independent of the other agents' observations. But, because of the precedence constraints, our OC-DEC-MDP is not transition independent : the transition probability of an agent to move from a state s to s ′ relies on its predecessor agents. The opportunity cost allows to assess the effect of the decision of an agent on the expected value of the other agents. Therefore, the agents do not have to build belief-state MDPs that consider the agent's belief about the other agents, nor to communicate during the execution. All the information an agent needs is the OC and its observation of its local state, thus the complexity of the problem is reduced. Moreover communication is not necessary during the execution.

The construction of OC-DEC-MDP (and of the local MDPs) is based, first, on the construction of the state spaces, second, on the computation of the opportunity cost for each task and the computation of the value of each state to construct the local policy. Section 2 describes some pre-computing algorithm, used to build the OC-DEC-MDP. Section 3 provides a definition of the OC-DEC-MDP and describes how to build the local MDPs. Section 4 presents the value equation and the algorithm used to solve the problem. We also present the complexity of our algorithm. Section 5 illustrates how the algorithm performs. The contribution of this work and remarks for future research direction are given in section 6.

PRELIMINARIES

In order to build the local MDPs, we need further information that can be computed off-line thanks to propagation algorithms which compute each task's possible intervals of execution and their probabilities.

Temporal Propagation

Given the temporal and precedence constraints, and the execution durations for each task, we determine the set of temporal intervals during which a task can be executed, by propagating the temporal constraints through the mission graph. The graph is organized into levels such that : L0 is the root of the graph, L1 contains all the successors of the root (successors(root)), . . ., Li contains the successors of all nodes in level Li-1. For each node (task) ti in a given level Li, we compute all its possible intervals of time. The start times are in [EST, LST ] where LST = LETmin(δc) and δc are the possible durations of the task. However an agent can start the execution of ti if all the predecessors of ti have finished their execution. Thanks to the end times of the predecessors, we can validate the possible start times in [EST, LST ]. In the following, LBi stands for the first valid start time of ti (Lower Bound), and U Bi is the last valid start time (Upper Bound). For each node, the intervals are computed by :

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

st(root) = max{EST (root), start time}

= LBroot = U Broot ET (root) = {st(root) + δ root c ≤ LET, ∀δ root c } where δ root c
is the computation time of the first activity (task) of the mission and start time is the system "wake up" time. Consequently, intervals of activities of the root are given by I = [st(root), et(root)], where et(root) ∈ ET (root).

• level Li : Each node in level Li starts its execution when all its predecessors end their own activities. Since each predecessor has different possible end times, the possible start times for nodes in level Li are also numerous. Firstly, we compute the first possible start time of the considered node.

To do that, we compute the set of first end times (FET) of the predecessors :

F ET (node) = pred∈parents(node) ( min et∈ET (pred) (et))
and then the maximum of these first end times represents the first possible start time for the node.

F ET AP (node) = max{EST, max et∈F ET (node) (et)} LB node = F ET AP (node)
Secondly, we compute the other possible start times of the node. To do that we consider all the other possible end times of the predecessors. Indeed, any predecessor pred finishing after FETAP (at end time) is a possible start time of the node because it represents a situation where all the other predecessors have finished before FETAP and predecessor pred has finished after FETAP at end time. Consequently, the other possible start times are defined as follows :

OST (node) = {et ∈ ET (pred), et > F ET AP } U B node = max{OST (node)}
The set of the possible start times of a node are :

ST (node) = {st ∈ F ET AP (node) OST (node)} such that EST node ≤ st ≤ LST node
The set of the possible end times of the node is then given by : ∀node ∈ leveli,

[ET (node) = ∀δ node c ,st {st + δ node c < LET node }] where δ node c
is the computation time of the activity (task) at node node and st ∈ ST (node).

Probability Propagation

We describe, in this section, how we can weight each of these computed intervals with a probability. This probabilistic weight allows us to know the probability that an activity can be executed during an interval of time with success. For that, a probability propagation algorithm among the graph of activities is described using the execution time probability. This algorithm has to use the precedence constraints that affect the start time of each node, and the uncertainty of execution time that affects the end time of the node.

Probability on start time

The computation of conditional start time has to consider the precedence constraints. Indeed, they express the that an activity cannot start before its predecessors finish.

Let's consider that the initial policy of an agent starts the activities as soon as the predecessors finish. Consequently, the probability DP (t) that an agent starts an activity at t is the product of the probability that all predecessor agents terminate their activities before time t and there is, at least, one of them that finishes at time t. More formally speaking :

•for the root :

DP (t) = 1, t = U Broot = LBroot
•for the other nodes :

DP (t) = a∈predecessors(c) P a end (δe ≤ t) - t 1 ≤t DP (t1)
Where a is an activity of a predecessor agent of the agent performing the considered activity c and P end (δe ≤ t) is the probability that predecessor a finishes before or at time t. DP (t) is called "absolute probability" because it is not relative to any decision on the start time of the other agents, the agent starts as soon as possible.

On the other hand, let's suppose that the agent decides to start an activity at time t even if it can have started before t. The probability that this situation occurs is t ′ ≤t DP (t ′ ) : the probability that the predecessors have finished at t or before. This probability is called " relative probability" because it is relative to the decision of starting the execution at t.

In the following, P abs w (I) is the probability that the execution occurs in the interval I if the agent follows its initial policy (start as soon as possible). P rel w (I) stands for the relative probability that the execution occurs in the interval I if the policy dictates to the agent to start the activity at st.

Then, P a end (δe ≤ t) can be given as follows :

P a end (δe ≤ t) = I 1 ∈intervalles(a),et(I 1 )≤t P abs w (I1)
This probability is the sum of probabilities that each predecessor a executes its task in an interval I1 with an end time et(I1) less than t. Now we are able to show how we can compute the probability that an execution occurs in an interval I.

Probability on a temporal interval of an activity

The probability that the execution duration of an activity ti+1 occurs during I = [st, et] is the probability that ti+1 starts at st and it takes ∆t = etst to finish. Furthermore, an agent starts ti+1 when it finishes ti. Consequently, it knows the end time, let it be et(I ′ ), of ti. That's why we need to compute the probability that ti+1 occurs in I when the agent knows that ti finishes at et(I ′ ). To do that, we compute the probability P abs w (I|et(I ′ )t i ) and P rel w (I|et(I ′ )t i ) such that :

P abs w (I|et(I ′ )t i ) = DP (st(I)|et(I ′ )t i ).Pc(et(I) -st(I)) P rel w (I|et(I ′ )t i ) = t ′ ≤st(I) DP (t ′ |et(I ′ )t i ).Pc(et(I) -st(I))
Now, the probability DP (st(I)|ett i (I ′ )) used below means that we know activity ti has finished at et(I ′ ), and only the probability that the other predecessor activities have been finished, should be considered.

DP (st(I)|et(I ′ )t i ) = a∈predecessors(t i+1 )-t i P a end (δe ≤ st(I)|et(I ′ )t i ) - t 1 <st(I ′ ) DP (t1|et(I ′ )t i ) P a end (δe ≤ t|et(I ′ )t i ) = I 1 ∈intervalles(a),et(I 1 )≤t P abs w (I1|et(I ′ )t i )
3. FORMAL FRAMEWORK DESCRIPTION

The OC-DEC-MDP model

From the graph of tasks (mission) that the agent should accomplish, we isolate for each agent the tasks it has to execute, named agent's graph in figure 3. This agent's graph is then used to build the local MDP of the agent taking into account the precedence constraints. We name the set of local MDPs, OC-DEC-MDP.

DEFINITION 1. An OC-DEC-MDP for n agents is a set of n local MDPs.

A local MDP for an agent Ai is defined by a tuple < Si, Ti, Pi, Ri > where :

• Si is the finite set of states of the agent Ai As we will explain later, dependencies between local MDPs (due to temporal and precedence constraints) are taken into account thanks to the Opportunity Cost. In the rest of the section, we give more details about each component of the local MDPs.

OC-DEC-MDP Agents' Graphs

States

At each decision step, Ai has executed a task ti during an interval I and it has r resources. The decision process constructs its decision given these three parameters. The states are then triplets [ti, I, r] where ti is the last executed task and I is the interval during which the task ti has been executed and r is the rate of available resources.

Figure 3 shows that a fictitious initial task is added in each local MDP. Each box gathers the states associated to a task ti. Each node stands for a state [ti, I, r].

Tasks -Actions

At each decision step, the agent must decide when to start the next task. The actions to perform consist of"Executing the next task ti at time st : E(ti, st)", that is the action to start executing task ti at time st when the task ti-1 has been executed. Actions are probabilistic since the processing time and the resource consumption of the task are uncertain.

Transitions

We assume that the actions of one agent is enough to achieve a task. The action of an agent allows the decision process to move from state [ti, I, r] to a success state [ti+1, I ′ , r ′ ] or to a failure state. The transitions are formalized as follows :

• Successful transition: The action allows the process to change to a state [ti+1, I ′ , r ′ ] where task ti+1 has been achieved during the interval I ′ respecting the EST and LET time of this task. r ′ = r -∆r is the remaining resources for the rest of the plan. The probability to move to the state [ti+1, I ′ , r ′ ] is :

P1 = r≥∆r et(I ′ )≤LET
Pr(∆r).P rel w (I ′ |et(I)t i )

• Too early start time Transition : The agent starts too early before all the predecessor agents have finished their tasks. We consider that when an agent starts before its predecessor agents finish, it realizes it immediately. This means that the agent, at st + 1, realizes that it fails. This state is a non-permanent failure because the agent can retry later. We represent this state by [ti, [st, st + 1], r ′ ] where r ′ = r -∆r ′ f ailure such that ∆r ′ f ailure is a penalty in resource when an agent fails. The probability to move to this state is the probability that the predecessors have not finished and the agent has enough resources to be aware of it. The probability P not end (st) that the agent's predecessors have not finished at st is the probability that the predecessors will finish later or will never finish.

P not end (st) = ( a∈predecessors(t i+1 )-t i Ia :et(Ia)>LET -minδ i Pw(Ia|et(I)t i ) - t ′ ≤st DP (t ′ |et(I)t i ))+ (1 - a∈predecessors(t i+1 )-t i Ia Pw(Ia|et(I)t i ))
The probability to move to a state [ti, [st, st + 1], r ′ ] is : P2 = P not end (st) where r ′ ≥ 0 and st ≤ U B.

(δc)

It is straightforward that P1 + P2 + P3 + P4 + P5 = 1 and the transition system is complete.

Rewards

Each agent, Ai, receives a reward Ri presumably based on the executed task. The reward function is assumed given Ri(ti) and Ri([f ailuret i , * , * ]) = 0.

Once the local MDPs have been built, each agent's policy can be computed. The next section describes how to solve the OC-DEC-MDP.

PROBLEM RESOLUTION

A policy is computed for each agent, thanks to a modified Bellman equation and a polynomial dynamic programming algorithm. The use of OC in the Bellman equation allows each agent to take into account the other agents, and therefore to coordinate without communication. This section presents the modified Bellman equation we use and introduces the notion of OC. It also gives some results about the valuation algorithm we have developed.

Value Function

Bellman Equation

Given the different transitions described previously, we can adapt our former to Bellman equation as follows :

V [ti, I, r] = immediate gain Ri(ti) - Opportunity Cost k∈succ OC k (et(I) -LB k ) + Expected value max E(t i+1 ,st),st>current time (V ′ )
where succ are the successors of ti executed by an other agent, et(I) is the end time of the interval I and LB k is the first possible start time of the task t k . OC k (et(I) -LB k ) is the opportunity cost provoked on t k when its possible start times are reduced to

[LB k + ∆t, U B k ].
This equation means that the agents' rewards Ri(ti) are reduced by an opportunity cost due to the delay provoked in the successor agents.

The best action to execute in state [ti, I, r] is given by :

Expected value argmax E(t i+1 ,st),st>current time (V ′ )
V ′ is such that :

V ′ = V 1 + V 2 + V 3 + V 4.
Each part of V ′ stands for a type of transitions :

• Successful transition : V 1 = P1.V ([ti+1, I ′ , r ′ ])
• Too early start time Transition :

V 2 = P2.V ([ti, [st, st + 1], r ′ ])
• Insufficient resource Transition :

V 3 = P3.V ([f ailuret i+1 , [st, +∞], 0])
• Too late start time or Deadline met Transitions :

V 4 = (P4 + P5).V ([f ailuret i+1 , [st, +∞], * ])
The value of the failure state associated to ti is given by :

V * f ail(t i ) = -Rt i - suc / ∈agent(t i ) OC(f ail)succ - suiv∈agent(t i )

Rsuiv

where -Rt i is the immediate penalty due to the failure of ti, suc / ∈agent(t i ) OC(f ail)suc is the Opportunity Cost on the successors of ti (succ are the successors of ti executed by other agents), and -suiv∈agent(t i ) Rsuiv is the lost in value due to the failure of all the remaining tasks executed by the same agent as ti.

Approximation of Opportunity Cost

Opportunity cost comes from economics. We use it to measure the effect of the decision of an agent Ai, about the start time of ti, on a successor agent Aj. Let tj be the successor task of ti executed by Aj. Agent Ai can select a start time sti of ti in [LBi, U Bi] while agent Aj selects the start time stj of tj in [LBj , U Bj ]. The fact that Ai decides to start at sti and it finishes at eti, can reduce the possible start times of tj to [LBj +∆t, U Bj ] where ∆t = eti-LBj (tj can start after ti finishes). Let V * 0 j be the expected value of Aj when stj can be selected from [LBj , U Bj ], and V * ∆t j the expected value when stj can be selected from [LBj + ∆t, U Bj ].

OCt j (∆t) = V * 0 t j -V * ∆t t j (1)
This cost is computed for all ∆t from 0 to U Bj -LBj .

V * ∆t t j = ∆t t j c
Pc(δ

t j c ).V [tj, [stj, stj + δ t j c ], r max t j ] [tj, [stj, stj +δ t j c ], r max t j
] describes the states that can be reached when the execution of the task tj starts at stj. stj is the best start time of tj in [LB + ∆t, U B] which is the set of possible start times when the task is delayed by ∆t. [stj, stj + δ t j c ] describes the possible execution intervals. When stj + δ t j c > LET , we have :

V [tj , [stj, stj + δ t j c ], r max t j ] = V (f ailure(tj))
When ∆t > U Bt j -LBt j the execution starts before the last possible start time U Bt j , temporal constraints are violated and

V * ∆t t j = -R(tj) + a∈AllSucc(t j ) R(a) .
The expected values V * 0 t j and V ∆t t j have been computed for states [tj , [stj, stj + δ

t j c ], r max t j
] where stj ∈ [LB + ∆t, U B] . We assume (assumption) that agent Aj has its maximum resources r max t j because there is no effect of the decision of the agent Ai on the resources of agent Aj. Also, we need to assess the effect of agent Ai's decision on failing agent Aj when this failure is not due to the lack of resources of agent Aj. That's why, we assume that Aj has all its maximum resources :

r max t j = rini -t k ∈P red(t j ) mint k (∆r)
where P red(tj) is the set of tasks executed by the agent before tj, and mint k (∆r) is the minimal resource consumption of t k .

Our modified Bellman equation is used in a valuation algorithm which computes the values of all the agents' states and thus determines a policy for each agent.

Resolution of the OC-DEC-MDP

Valuation algorithm

In order to evaluate each state in the local MDPs and to compute each agent's policy, a dynamic programming algorithm is used. Because of dependencies between the graphs of the agents, the algorithm evaluates the local MDPs in parallel. In figure 3, if we want to compute the values of the states associated to "snap target 1", we need the value of the opportunity cost for "radioactivity measurements by agent 1". To compute the opportunity cost for "radioactivity measurements by agent 1", we must have valued the states associated to this task, and consequently we need the OC for "analyze data". Therefore the local MDPs of agents 1, 2 and 3 must be valued at the same time. The states of the OC-DEC-MDP (union of the states of the local MDPs), are organized into levels. The first level contains the root of the mission graph. The level Ln contains all the successors, in the mission graph, of the tasks in Ln-1. For each level, from the last level to the root, the valuation algorithm evaluates the states associated to each task in the current level. Thus, states from different local MDPs are valued at the same time. The "pseudo-code" of the valuation algorithm is :

The computation of a value V ([ti, I, r]) for a state [ti, I, r] is done thanks to the previous Bellman Equation. It allows to determine the policy for this state.

Each agent knows the mission graph and then computes its policy. This algorithm can be executed by each agent in a centralized way if the agents can not communicate before the execution. If the agents can communicate before the execution, the algorithm can be executed in a decentralized way : each agent computes the values of its own states and sends the OC values of each of its task ti to the predecessors of ti. The mission is always executed in a distributed way and the agents do not communicate.

Problem Complexity

An upper bound on the complexity of OC-DEC-MDP can be computed. It takes into account the state space size of the OC-DEC-MDP which relies on : #n tasks the number of tasks of the agent, #nMax Interv the maximum of intervals per task, #nMax Res the maximum of resource levels per task and #nMax Start the maximum of start time per task.

These parameters (intervals per task, range of available resources) affect the complexity of the problem. In the worst case, the state space size, for each agent (local MDP state space size), is given by the following equation : Given equation 2, the complexity is O(|S|) and the algorithm is polynomial in |S| where S is the set of states. ✷

To sum up, our valuation algorithm of OC-DEC-MDP is polynomial in |S| whereas other approaches are in best case exponential in |S|. The states do not include observations about the other agents, so the number of states is quite fair. Moreover, most of existing approaches do not consider temporal and precedence constraints even if such constraints are often encounter in MAS.

THEOREM 2. Adding communication during the execution of the agents with unlimited resources, does not improve the performance of the OC-DEC-MDP.

Proof : Let us assume that agents send messages to interested agents when they finish a task. And, an agent α does not start the execution of a task ti until it receives a notification from all agents executing tasks tj preceding task ti. Does this communication between agents improve the performance of the OC-DEC-MDP ?

Let i be the time at which all the messages from agents achieving tasks tj preceding the task ti and [LB, U B] be the lower and upper bounds of start time of task ti. Three cases are possible in which we compare respectively the cost K1 of OC-DEC-MDP and the cost K2 of OC-DEC-MDP-COM (OC-DEC-MDP augmented with a mechanism of communication). We assume in our case that the cost of partial failure is 1 time unit and that the communication, in best case, costs (cheapest) also 1 time unit. In such situation, we have :K2 = (i -LB) + pred(α) and K1 = (i -LB)

We can see that in this case OC-DEC-MDP outperforms OC-DEC-MDP-COM.

• i < LB : in this case, as soon as the OC-DEC-MDP tries to start it successes. Then the cost is 0. However, the cost of communication in OC-DEC-MDP-COM is at least 1 time unit. Consequently, the OC-DEC-MDP outperforms OC-DEC-MDP-COM.

• i > U B : in OC-DEC-MDP, agent α will temporary fail U B -LB times before failing definitively while in OC-DEC-MDP-COM, it will wait up to UB before failing definitively. In addition to that, messages are sent but they won't be used. Consequently, OC-DEC-MDP outperforms OC-DEC-MDP-COM.

K2 = k∈pred(α) cost of Com k + cost wait(U B -LB) K1 = (U B -LB).Cost P artial F ailure = U B -LB✷

EXPERIMENTS

Experiments have been developed in order to test the scalability and performance of our approach. As mentioned previously, the state space size relies on several parameters. For instance, changes in the temporal constraints influence the number of intervals per task. In the worst case, the number of intervals for a task is given by equation 3. If the temporal constraints are tight, the interval [LB , UB] is reduced. We then compute few intervals and the number of states decreases. When we increase the size of the temporal windows, the state space size grows. Indeed, temporal constraints are less tight, and new execution plans (involving new states) can be considered.

When we increase the number of agents that execute the mission, the state space size decreases : each agent has less tasks to execute, the number of triplets [ti, I, r] is smaller. For a mission of 200 tasks and 3 agents, the number of states per local MDP is about 250 000. If we increase the number of agents to 15, then the state space size of each local MDPs is about 75 000 states. A peak in the number of states can be observed when starting to increase the number of agents. It is due to an augmentation in the number of available resources for each task. In our experiments, initial resources are tight. Moreover, we don't consider the possible rates less than zero. When we increase the number of agents, each one has less tasks to execute and the initial resources become wider. The lack of resources (r ≤ 0) becomes scarce and the number of possible resource rates, greater than zero that have to be considered, increase. Figure 4 shows the changes in the state space size through the mission's size and the number of agents. If we increase the initial resource rate, resources become wider and agents don't lack of them, all the resource combinations are positive. The augmentation in the number of agents, don't increase the number of possible resource rates greater than zero. If resources are unlimited there is no peak. When we increase the number of precedence constraints per task, the number of states decreases. The constraints reduce the number of possible intervals of execution per task, and therefore the number of states diminishes. For instance, given 3 agents and 200 tasks to execute, the state space size is about 500 000 states for 25 constraints and 300 000 states for 45 constraints. Figure 5 shows these changes for missions of 100, 150 or 200 tasks executed by 3 agents (worst case in figure 4). Experiments have shown that our approach can deal with large mission graphs. Experiments with larger graphs are under development, even if first experiments have proved that our approach is suitable for the applications we deal with. Different scenari have also been implemented on simulators, they involve several robots that have to explore a planetary site or deal with a crisis situation. First experiments have shown that our approach allows the agents to accomplish their tasks with weak number of partial failures. Although, this approach is not optimal. The current experimental results show that it's a good approximation.

CONCLUSION

The framework of decentralized MDPs has been proposed to solve decision problem in cooperative multi-agent systems. Nevertheless, most of DEC-MDP are NEXP-Complete. In this paper we have identified the OC-DEC-MDP class which has a polynomial complexity. Moreover, OC-DEC-MDP model can handle temporal and precedence constraints that are often encountered in real world applications, but not considered in most of existing models. Each agent builds its own local MDP, taking into account its own tasks. Each local MDP is a standard MDP valued off-line thanks to our algorithm that uses a modified Bellman equation and computes the OC values. Thanks to the opportunity cost no communication is needed during the execution, the agents can work even if communications are not possible or too expensive. Moreover, the agents do not have to complete observations about the others, so the complexity of the problem is reduced and a polynomial algorithm has been proposed to solve such OC-DEC-MDP.

Future work will concern the improvement of the performance of this approach by better estimating OC. In the current approach, OC is over-estimated and the agents assume that for each decision there is a cost. In fact, there is a likelihood that this cost can happen. That's why, a new approach should be considered with an expected opportunity cost.

Figure 1 :

 1 Figure 1: Classes of complexities of DEC-MDPs

Figure 2 :

 2 Figure 2: A mission graph

•

  Ti is the finite set of tasks of the agent Ai • Pi is the transition function where P (s ′ i |si, ti) is the probability of the outcome state s ′ i for agent Ai when it executes the task ti in state si

Figure 3 :

 3 Figure 3: Relationship between the graphs of tasks and the OC-DEC-MDP

  |S| = #n tasks .(#nMax Interv + nMax Start).#nM ax Res (2) In the worst case, each value in [LB, UB] is a possible start time and each duration is possible. Then, #nMax Interv = (U B -LB) × #nMax Dur (3) and #nMax Start = U B -LB where #nMax Dur is the maximum number of durations for a task. THEOREM 1. An OC-DEC-MDP with temporal and precedence constraints is polynomial in the number of states. Proof : The algorithm described previously solves the OC-DEC-MDP. It passes through the state space of each local MDP and values each state. The valuation of a state "Compute V" has a complexity of O(1). Lines 4-10 value all the states associated to a task ti. The complexity of this phase is O((#nMax Interv + #Max Start).#nM ax Res). Lines 11-15 compute the OC value for each delay of ti. In the worst case, the number of delays is equal to the number of possible start times. That's why, the complexity is O(U B -LB). Lines 4-15 are executed for each task. Moreover, O(U B -LB) << O(#nMax Interv ). The overall complexity of the algorithm is then O(#n tasks .(#nMax Interv + #nMax Start).#nM ax Res).

•

  i ∈ [LB, U B] : OC-DEC-MDP-COM has a a cost : K2 = k∈pred(α) cost of Com k + cost wait(i -LB) OC-DEC-MDP without communication has as a cost : K1 = (i -LB).Cost P artial f ailure

Figure 4 :

 4 Figure 4: Changes in the state space size

Figure 5 :

 5 Figure 5: Changes in the state space size

•

  Insufficient resource Transition :The execution requires more resources than available or the predecessors have not finished and the necessary resources to be aware of it are not sufficient (r

		t i+1 c	is so long that the deadline is
	met. This transition moves to the state [f ailuret i+1 , [st, +∞], r].
	The probability to move to this state is :
	P5 =	Pr(∆r).DP (st|et(I)t i ).P c t i+1
	r≥∆r st+δ c >LET t i1

′ < 0). This transition moves to the state [f ailuret i+1 , [st, +∞], 0]. The probability to move to this state is :

P3 = t ′ ≤st DP (t ′ |et(I)t i )

r<∆r Pr(∆r) + P not end • Too late start time Transition : The task starts too late and the execution meets the deadline LET. The agent moves to the state [f ailuret i+1 , [st, +∞], r] . This case arises when st > LST . Otherwise (st ≤ U B), P4 = 0. The probability to move to this state is : P4 = P not end (st > U B) • Deadline met Transition : The action starts an execution at time st but the duration δ

  Algorithm 1 Evaluation Algorithm 1: for level Ln from the leaves to the root do 2: for all task ti in level Ln do 3: Compute V for the failure state: [f ailure(ti), * , * ] 4: for all start time st from U Bt i to LBt i do 5: for all resource rate rt i of a partial failure do 6: Compute V for non-permanent failure state : [ti, [st, st + 1], rt i ]

	7:	end for
	8:	for all duration ∆t1 of ti do
	9:	for all resource rate rt i of ti's safe execution do
	10:	Compute V for the safe states : [ti, [st, st +
		∆t1], rt i ]
	11:	end for
	12:	end for
	13:	Compute V * ∆t k	where ∆t = st -LBt i
	14:	end for
	15: 16:	for all V * ∆t k Compute OC(∆t) = V * 0 computed previously do k -V * ∆t k
	17:	end for
	18:	end for
	19: end for

ACKNOWLEDGEMENTS

The authors would like to thank Shlomo Zilberstein for his helpful comments. This project was supported by the national robotic program Robea and "Plan Etat-Région".