Proactive and Reactive Coordination of Non-dedicated Agent Teams Operating in Uncertain Environments

1 Introduction

In delivery of services or goods [Dantzig and Ramser, 1959; Dolgov and Durfee, 2006], task allocations to individual vehicles are based on uncertain travel times to delivery locations. Also, in disaster rescue scenarios [Varakantham et al., 2014; Velagapudi et al., 2011; Varakantham et al., 2009], victims have to be allocated to robots while considering the uncertainty in travelling through disaster prone areas. Furthermore, in large warehouses [Hazard et al., 2006; Wurman et al., 2007] of online portals such as Amazon, movement of automated robots fetching goods based on online orders (uncertainty) have to be coordinated in the usage of pathways (resources). Finally, in problems associated with safety and security, recent research [Brown et al., 2014; Shieh et al., 2014; Varakantham et al., 2013] has considered patrolling problems where a team of defenders coordinate to secure a set of targets against an observing adversary (e.g., traffic police coordination for patrolling roads in order to reduce violations).

These domains have the following common characteristics: (a) A team of agents (e.g., ambulances/fire trucks) coordinate plans to achieve a goal or to optimize a certain criterion (e.g., save victims); (b) There is transition uncertainty in planning problems of individual agents, either due to travelling on roads (due to traffic) or due to uncertain demand (online orders) or physical constraints (e.g., robots); (c) Actions of agents either require the availability of resources (roads, paths, tools, etc.) or completion of tasks allocated (target surveillance, delivery of items, etc.). Furthermore, there is usually a hard constraint on the number of tasks/resources available and this causes agent plans to be dependent on each other; and most importantly (d) The individual agents have a chance of leaving the team at any time step due to either a breakdown (e.g., in the case of large warehouses, individual robots leave the system either to get charged or because of malfunction) or to address a higher priority task (e.g., in case of traffic patrolling problems, traffic police have to attend to incidents/accidents in addition to patrolling roads).

We are interested in application problems with above mentioned characteristics. Due to the non-dedicated nature of the team members (as agents can leave the team at any time), we refer to these teams as non-dedicated agent teams. The notion of non-dedicated teams was introduced and studied extensively in the context of Belief Desire Intention (BDI) frameworks [Cohen and Levesque, 1991; Grosz and Kraus, 1996; Tambe, 1997] for multi-agent planning. However, those works relied on existence of plan libraries and considered primarily deterministic outcomes to actions. In this work, we generate plans automatically and focus on domains with probabilistic outcomes to actions.

Another closely related thread of research is on adhoc teams [Barrett et al., 2017], which focuses on a newly added team member that cooperates with a variety of teammates, without directly altering the behavior of teammates. We focus on non-dedicated teams where the configuration of the team is altered to accommodate the leaving team member. More recently, Shieh et al. [Shieh et al., 2014] re-introduced the notion of non-dedicated teams in the context of defender teams patrolling against an observing adversary. While Shieh et al.'s work considered non-deterministic outcomes to actions, their exhaustive offline approach is not scalable.

To that end, we first provide a general model for the study of non-dedicated agent teams operating in uncertain environments. We then provide multiple proactive and reactive approaches to generate policies for individual agents in nondedicated agent teams. One of our main contributions is a proactive approach that relies on sampling and decomposition to efficiently generate policies for individual agents. Another major contribution involves the formulation of a two stage approach where the state of the team (i.e., agent exits) at the end of first stage is input for the second stage to provide a two stage policy for the agents. Finally, our exhaustive evaluation on benchmark problems illustrate the improved performance of our proactive and reactive approaches.

2 Model: ND-TasC-MDP

We build on the TasC-MDP model introduced by Dolgov et al. [Dolgov and Durfee, 2006] and extended by Agrawal et al. [Agrawal et al., 2016] to represent the problems with nondedicated teams operating in uncertain environments. We refer to this model as Non Dedicated TasC-MDP (ND-TasCMDP) and is characterised by the tuple:

• Ag is the set of agents.
• Γ is the different types of tasks.
• C = ⋃τ∈Γ C(τ) corresponds to the set of all tasks, where C(τ) is the set of tasks of type τ. |C(τ)| is the capacity bound for tasks of type τ.
• D = {τ1 ≺ τ2, τ1 ‖ τ2, . . .} represent the set of allocation constraining dependencies and temporal dependencies (refer [Agrawal et al., 2016] for more details). For purposes of easy exposition, we focus on problems with independent tasks, however, all our approaches are easily extendable to cases with dependencies.
• Mi = 〈Si, Ai, Pi, Ri, ρi, α0 i 〉 is the MDP model for agent i along with the task associations of actions.
• Si, Ai,Pi, Ri are the standard MDP elements. - ρi : Ai × Γ → R{0,1} is a function that specifies the binary task association of all actions. In states where tasks can be accomplished, there are task specific actions. - α0 i is the starting probability distribution for agent i.
• ∆i: Vector of probabilities for agent i leaving the system at different times. Specifically, ∆ti represents the probability of agent i leaving the team at time t and ∑t ∆ti = 1.
• H is the time horizon for the decision problem.

The key distinction in ND-TasC-MDP is the presence of a probability distribution for each agent, ∆i that represents the non-dedication of each agent. The goal is to compute a joint policy π∗ that has the highest expected reward among all joint policies given that agents can leave the team according to probability distribution ∆:

Variables: ∀si, σi ∈ Si; ∀ai ∈ Ai; ∀τ ∈ Γ; ∀i ∈ Ag; ∀t ∈ H

Subject to:

Table 1: Optimal MILP for Dedicated Team

where πi is the individual policy of agent i in the joint policy π, δi is the set of tasks allocated to agent i with δi(τ) indicating the number of tasks of type τ . Vi(πi, α0 i ) is the expected value for the individual policy, πi on model Mi. The task-based interactions are explicitly modelled in Equation 1, which ensures that number of tasks executed is less than the total number of tasks. The individual task accomplishments are modelled using the constraints (2). The function f is used to compute the number of tasks type τ completed by using a policy πi for agent i given the non-dedication parameter, ∆.

2.1 Formulation for a Dedicated Team

For the case where no agent leaves the system (represented as ∆Hi = 1 for all agents), previous work [Dolgov and Durfee, 2006; Agrawal et al., 2016] has provided mixed integer formulations to address different types of resource and task interactions. We provide this mixed integer linear program (MILP) for a dedicated agent team in table 1. Objective maximizes the sum of expected rewards over all agents [Puterman, 1994] where xti (si, ai) represents the occupation measure of agent i for state action pair (s, a). Equation 4 ensures outgoing flow from a state σi by taking any action is equal to the incoming flow into that state from other states. For the initial state, Equation 5 ensures the flow at the beginning for an agent is equal to its starting distribution. Equation 6 constrains the number of executed tasks for any given type, τ to be less than the number of tasks of that type. A task can be executed only if there is a positive flow associated with the right state and action. This is enforced in Equation 7.

3 Approaches

We provide both reactive (online) and proactive (offline) approaches to facilitate coordination among the remaining agents over the tasks left undone by the agents leaving the team. In addition, we also provide heuristics that benchmark the performance of our approaches.

3.1 Benchmarking Heuristics

We first outline two benchmarking heuristics that will be employed to benchmark the performance of our approaches in-

troduced in later sections.

Ignore the leaving agent, ILA: In this heuristic, we solve the MILP of Table 1 and obtain solution assuming agents will not leave the system. When some agents leave the system, other agents ignore their departure and execute the policies computed by solving the MILP. This provides a good lower bound on solution quality that has to be achieved by any new proposed approach.

Online Revamp, O-Rev: In this heuristic, the agents execute their policies obtained from solving the MILP of Table 1 until one or more agents leave the system. At the decision epoch t where at least one of the agents leaves, the problem is solved again for the remaining agents and time steps. The information of leaving agents and the starting probability distribution over states for agents at the leaving time is input to the MILP. The new policy obtained from re-solving is executed by the agents until there is a change in the system (i.e. some agent leaves the system). Even though this approach is not feasible for online decision making (due to the computational complexity of solving the MILP), this revamp approach provides a good upper bound on the desired performance for our proposed approaches.

3.2 Proactive Expected FlowOptimization

Expected flow optimization (EFO) is a proactive approach that given the probability distribution for agents leaving the system, i.e., ∆, we update the formulation of Table 1. Specifically, we replace the actual flow with expected flow given "probability of staying back" in the flow preservation constraint of Equation 4. That is to say,

All other constraints in the optimization problem of Table 1 remain exactly the same. As will be noted in our experiments, such an approach though easy to implement performs poorly in comparison with other approaches.

3.3 Reactive Assignment of Tasks

We now describe Reactive Assignment of Tasks (ReacT) that performs reactive updates to the current solution as agents leave the system. Initially, we start with the joint policy obtained by solving the MILP of Table 1. When one or more agents leave the team, the tasks of leaving agents must be assigned to the remaining agents. Each remaining agent evaluates the value of changing the current allocation (i.e., taking on some of the newly available tasks and discarding some of the currently assigned tasks) given the newly available tasks. The agent which obtains the highest value by changing its allocation is first assigned tasks from the newly available list and tasks discarded by that agent are added to the newly available task list. This process is repeated with the remaining agents who evaluate the value of changing their current allocation until the new task list is exhausted or all agents have changed their allocation once. Evaluating value of taking on additional tasks at the cost of discarding some of the current tasks is performed by solving an MDP over the remaining horizon. The starting distribution of the agents are updated to consider the distribution of states at the current time step. Algorithm 1 provides the pseudocode for ReacT where inputs

Algorithm 1 REACTIVE TASK ASSIGNMENT( F, ˜ δ, t)

• 1: repeat
• 2: 〈i∗ , Vi∗〉 ←maxi∈Ag\F Vi(π∗ i , αt i , δi ∪ ˜ δ)
• 3: δ+ i∗ ← GETNEWLYALLOCATEDTASKS(πi∗ , δi)
• 4: δi∗ ← GETDISCARDEDTASKS(πi∗ , δi)
• 5: ˜ δ ← (˜ δ \ δ+ i∗ ) ∪ δi∗
• 6: F ←F ∪ {i∗ }
• 7: until ˜ δ = ∅ OR Vi∗ = 0

to the algorithm are the set of agents leaving the system, F, the newly available tasks, ˜ δ and the current time step, t. The algorithm finds the agent with largest expected reward (line 2) where each of the remaining agents are allowed to consider all tasks from the list ˜ δ ∪ δi. The newly available tasks assigned to the agent with highest reward are determined in line 3 and the discarded tasks are determined in line 4. The list of newly available tasks ˜ δ is then updated to remove the assigned tasks and add the tasks discarded by agent i∗ on line 5. F is updated to include i∗ . This process is continued until either of the termination conditions are met.

3.4 Proactive Planning through SAA+LR

We now describe a sample average approximation based Lagrangian relaxation (SAA+LR) approach that computes a policy for each of the agents for multiple scenarios of agent availability over the entire time horizon. Since it is impossible to consider all the samples of agent availability on larger problems, this is primarily an approximate approach that optimizes the expected value given the probability distributions of agents leaving.

A sample of agent availability is generated by sampling from a biased coin with probability pi independently for every agent i. At every time step t, the coin is tossed to decide if the agent i either leaves or stays in the team depending on the value of associated probability in ∆i. Therefore, in every sample of agent availability ξ k , we know the availability horizon ξ k (i) of every agent i. The MILP in table 2 (referred to as OPT-ND-TasC) provides an optimal offline solution for the optimization problem of a non dedicated team over K samples with a different solution (allocation of tasks and policy) for each sample.

For transition function, we have P t,k i instead of just Pi. Similarly, for reward, Rt,k i instead of Ri. They are defined as:

Intuitively, these indicate that once the agent leaves the system (at ξ k (i)) reward and transitions are set to 0. To ensure conciseness in expressions, we will use the following short form for the objective employed in Table 2:

Table 2: Optimal MILP for Non Dedicated Team

The MILP for non dedicated team (OPT-ND-TasC) is separable over the number of samples. However, it can provide a usable solution only if the agent availability sample is known beforehand. But due to the dynamic nature of the problem, agent availability information is not available offline. Therefore, we modify the optimization problem in table 2 to provide an offline allocation of tasks that works well across all K samples using global task allocation variables, d :

That is to say, task allocations for all samples should agree on the same solution. This constraint links the optimization of allocations across all samples. Lagrangian dual for the optimization problem of Table 2 while considering the common allocation constraint of Equation 15 is given by:

where λ is the dual vector associated with constraints in Equation 15. A solution with respect to a given vector λ is given by G(λ) = minx,δ L(x, δ, d). The variable dti (τ) is unconstrained, which may lead to an unbounded dual. Therefore, to avoid unboundedness, the price variables must satisfy the following constraints:

The above condition further simplifies the dual G(λ), as the last term in Equation 16 vanishes leading to the below dual which is separable over K samples:

Maximizing the Dual Function

We now address the master problem of maximizing the Lagrangian lower bound over the price variables λ, which can be solved by using projected sub-gradient ascent[Bertsekas, 1999]. The gradient w.r.t. a variable λki (τ) is given by ∇G(λt,k i (τ)) = δt,k i (τ) where δt,k i (τ) denotes the solution of inner minimization problem of Eq.(18) for sample k which is used to update the price variables as follows:

Here, n and n∗ represent the current and next iteration, respectively. The second term is the projection into the feasible that ensures that ∑k λt,k i (τ) = 0 as indicated in Eq.(17).

Extraction of Feasible Primal Solution

The dual solution obtained by solving the individual samples may be inconsistent due to violation of the common allocation constraint of Eq.(15) among different copies of the task allocation variable δ, resulting in δt,k i (τ) ̸= δt,k′ i (τ) for any two samples k and k′ . To obtain a consistent task allocation to agents over K samples, we find the best-agent i∗ for every task τ ∈ Γ. The best-agent is nominated by choosing the agent with highest number of assignments of task τ over all samples. We obtain the best-agent for all tasks and formulate a reduced version of the OPT-ND-TasC MILP (table 2) by using the unique task allocation obtained over all samples. This reduced MILP is easy to solve and provides a consistent policy assignment for every agent of the non dedicated team irrespective of the sample. The solution obtained is the primal solution Primaln which is employed in the updation of step parameter γn∗ = Primaln-Dualn ||∇gk ||2 in Eq.(19) where Dualn is the dual value for iteration n.

3.5 Two Stage MILP for Non-Dedicated Team

The SAA+LR computes one allocation of tasks for the entire duration. In this section, we extend the underlying MILP formulation of SAA+LR to compute an initial allocation and then change the allocation once before the time horizon based on the current state of the system (agents available). Since, we consider the state before changing the allocation, this formulation improves team utility when compared to a single stage allocation. It should be noted that the dual decomposition approach described in the previous section is also directly applicable for this extended formulation. Due to the similarity, we do not describe the dual decomposition approach here and furthermore, we refer to two-stage MILP and Lagrangian relaxation of two-stage MILP synonymously.

State of the system (of relevance to task allocation) is the set of agents leaving the system. In this extended MILP, we compute an initial allocation and then at an observation time, t′ compute a new allocation based on the observation, o ∈ O of the state of the system. The samples of agent availability < ξ 1 , ξ 2 , ..., ξ k > provide the set of possible observations at t′ that marks the beginning of second stage. An observation belief < b1 , b2 , ..., bk > is maintained over the sample set ξ for every observation o at the observation time t′ . It must be

Table 3: Two-Stage MILP for Non Dedicated Team

noted that any sample ξ k , k ∈ K will have a non-zero belief for at most one observation and zero for the remaining set of observations. This reduces the number of samples to be solved at observation level, thereby, reducing the complexity of the problem at second stage to solving maximum K samples instead of K × |O|.

The objective is to maximize the total value over all samples ξ where the first and second term denote the objectives for the two stages, respectively. The variables xt,k i,1 (si, ai) and xt,k i,2 (si, ai, o) denote the visitation frequency for agent i at time t for sample k with observation o in stages 1 and 2 respectively. dti,n and yt i,n represent the common task allocation and policy assignment variables for the two stages n ∈ {1, 2} over all samples.

The constraints 22 to 26 are the constraints for stage 1 where equations 22 and 23 are the flow constraints and equation 24 is the task assignment/execution constraint. The equations 25 and 26 are required to provide a unique policy and task allocation over all samples in the first stage. Similarly, constraints 27 to 31 are the second stage constraints. For every observation o ∈ O, equations 27 and 28 are the flow constraints. The initial flow for every observation in the second stage at t′ + 1 is the outflow from the last time-step t′ of the first stage as shown in 27. Equation 29 provides the task assignment constraint. Equations 30 and 31 provide a unique policy and unique task allocation over all samples for an observation. For every sample, equation 21 is the task assignment constraint that ensures that a task can be done only in either of the stages.

4 Experiments

We evaluate 1 the performance of our reactive and proactive approaches. While there are no benchmark problems to study performance of non-dedicated teams, we rely on the benchmark problems available for multi-agent coordination in uncertain domains and augment them with probability distributions that represent the non-dedicative nature of agents.

4.1 Experimental Setup

We employ a generic setting that can be easily adapted to the domains described in introduction. Specifically, we employ the Urban Consolidation Center problems that deal with allocation of tasks and have to consider transitional uncertainty [Handoko et al., 2014]. We evaluate the performance of all the approaches on various metrics: (a) solution quality; (b) runtime; (c) quality of bounds provided by dual solution; and (d) percentage of optimality with increasing training samples and varying observation time.

Experimental results are averaged over 15 randomly generated grid maps that randomly place the delivery locations (tasks) and walls. Grids are described using a single parameter m that represents number of rows and columns (i.e., m x m grid). The actions are classified into movement actions (stay, left, right, up and down) and task actions. Rewards are generated only for task actions using a pseudo-random function dependent on the task location and task id. We generate 1500 samples of agent availability and divide it into training and testing sets of 1000 and 500 samples, respectively. To obtain a fair comparison over all online and offline approaches, we compare the solution quality and runtime on the same test set for the following approaches.

1. Ignore the leaving agent, ILA - Section 3.1.
2. Online revamp, O-Rev - Section 3.1.
3. Expected Flow Optimization, EFO - Section 3.2.
4. Reactive assignment of tasks (ReacT) - Section 3.3.

(5) Sample Average Approximation based Lagrangian Relaxation (SAA + LR) - Section 3.4. Due to repetition of samples, we assign frequency-specific weights to distinct training samples and select the 10 best samples for computing the joint policy with SAA+LR. The number of training samples is fixed to 10 best samples unless mentioned specifically.

(6) OPT-ND-TasC - This corresponds to solving all the chosen test samples offline. This is not really an approach that can be employed, but serves as a benchmark on the best pos-

sible performance achievable.

1 All our optimization problems are run on CPLEX v12.5

(7) Two Stage MILP for Non-Dedicated Team (MILP-2S) - Section 3.5. The training set, obtained similar to SAA+LR, is used to find the set of possible observations O beforehand for the second stage in MILP-2S. For any observation outside O in the testing set, we employ ReacT to obtain the solution of second stage for the samples. The observation time is fixed to t′ = 6 for a horizon H = 10 unless specifically mentioned.

4.2 Results

We compare the different approaches with respect to average team utility in Figure 1(a) as the number of agents |Ag| is increased. Specifically, we consider grids with m = 5, tasks C(τ) = 20 and horizon H = 10. Similarly, in Figure 1(b), we compare for different grid-size m for a fixed number of agents |Ag| = 6, tasks C(τ) = 20 and horizon H = 10. The key observations are summarized as following:

(1) EFO provides low team utility solutions. In the best case, EFO performs similar to ReacT but in the worst case, the performance is even lower than ILA.

(2) Since ILA ignores the leaving agents which impacts the scope of improvement in the rewards, ReacT performs better. Moreover, ReacT allocates high valued tasks of leaving agents to improve its utility.

(3) SAA+LR typically provides better performance than ReacT, but in some cases (e.g., 6 agents in Figure 1(a)), ReacT performs slightly better. O-Rev provides better utility than ReacT, ILA and SAA+LR but requires a lot of "online" cycles to solve the MILP at every stage of leaving agents.

(4) Finally, we observe that OPT-ND-TasC provides the best utility but it requires the knowledge of samples before-hand. MILP-2S provides comparable or better performance than ORev. O-Rev does not provide the optimal solution, because it does not reason about future scenarios of agents leaving while planning at a time step. Overall, amongst all the relevant and reasonable approaches, MILP-2S provides the best performance with respect to solution quality.

With respect to runtime, there are offline and online runtimes. Since EFO, ILA, SAA+LR and MILP-2S are offline approaches, online runtime is minimal (milliseconds). ReacT is an online approach and takes less than 30 seconds to generate a new allocation. O-Rev is an online approach but takes a long time (10-30 minutes) to generate results and hence is not applicable. For all offline approaches, we provide a maximum of three hours for training.

Figure 2 shows the convergence graph for the training samples of SAA+LR where the primal and dual evolve with increasing iterations and the number of training samples. A key observation is that SAA+LR provides near optimal solution very early and converges quickly even with increasing samples. The solution quality of the primal (calculated as Primal ∗ 100/Dual) is atleast 90% of the optimal.

Figure 3 shows the comparison of optimality (calculated as U(approach)∗100/U(OPT-ND-TasC) where U(approach) represents the utility obtained using specified approach) on the test set with different training samples and observation times in the training phase. Figure 3(a) shows the comparison of MILP-2S, SAA+LR and O-Rev with increasing training samples for MILP-2S and SAA+LR. Notice that O-Rev requires no training being online and it's performance remains unchanged. We observe that the performance of MILP-2S and SAA+LR improves to a certain extent with increasing training samples after which the performance becomes approximately constant. This is because for higher sample sizes (ordered in decreasing frequency weights), few samples with lower weights would be given preference in training which may not even occur in the test set at all, thereby impacting the performance. Similarly, in Figure 3(b), we vary the observation time for MILP-2S to obtain a two-stage offline policy for the different observation times and simulate the policies on the same test set. We observe that MILP-2S performs approximately as good as O-Rev (benchmark heuristic not dependent on observation time) with different observation times, but performs extremely well towards the centre.

5 Conclusion

In this work, we focussed on the problem of task allocation for a non-dedicated agent team. We provided both proactive (SAA+LR, MILP-2S) and reactive (ReacT) approaches for handling agents leaving the team in an effective manner. Our extensive experiments on benchmark problems demonstrate that the offline approach, MILP-2S provides the best solutions that are on par with benchmarks that compute upper bound on performance. Furthermore, our two stage approach (MILP-2S) can be easily extended to multiple stages to handle both leaving and returning agents simultaneously given the distribution of leaving/returning of agents.