K-Swaps: Cooperative Negotiation for Solving Task-Allocation Problems

1 Introduction

We study distributed algorithms for (re-)allocating tasks to cooperative agents, where tasks may have synergies with each other and each task has to be assigned to exactly one agent so that the resulting team cost is small (= team performance is high). Researchers have developed several taskallocation algorithms that do not re-allocate tasks once they have assigned them to agents [Koenig et al., 2007; 2008; Tovey et al., 2005]. In this paper, we develop a re-allocation mechanism that allows the agents to exchange their assigned tasks to reduce their team cost. Centralized task re-allocation is inefficient in terms of both computation and communication since the central controller is the bottleneck of the system. Instead, agents can negotiate with other agents. Such negotiations are usually used in a competitive setting where agents are self-interested and a contract is accepted only if all participants are better off from the contract [Golfarelli et al., 1997; Thomas et al., 2004; Sandholm, 1998;

∗This material is based upon work supported by, or in part by, the U.S. Army Research Laboratory and the U.S. Army Research Office under contract/grant number W911NF-08-1-0468 and by NSF under contract 0413196. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the sponsoring organizations, agencies, companies or the U.S. government.

Sven Koenig

Department of Computer Science University of Southern California Los Angeles, CA 90089-0781 skoenig@usc.edu

Andersson and Sandholm, 1999]. In this paper, agents are cooperative and always collaborate to minimize the team cost. Thus, they consider all task exchanges that reduce their team cost. We use the term negotiation here to describe the interaction of cooperative agents. Many approaches repeatedly execute single task exchanges that each decrease the team cost [Golfarelli et al., 1997; Dias and Stentz, 2000], where single task exchanges (or, synonymously, O-contracts [Sandholm, 1998]) transfer single tasks between two agents at a time. To minimize the team cost, however, it might be necessary to repeatedly execute multiple task exchanges among multiple agents that decrease the team cost [Dias and Stentz, 2002; Sandholm, 1998]. After describing task-allocation problems formally, we therefore propose K-swaps (for a given constant K) as a new type of contract that describes multiple task exchanges among multiple agents at a time. We then present a distributed algorithm that constructs all possible Kswaps that reduce the team cost of a given task allocation. Finally, we demonstrate empirically that K-swaps can reduce the team costs of several existing task-allocation algorithms significantly even if K is small.

2 Task-Allocation Problem

We follow [Koenig et al., 2007] to formalize task-allocation problems: A task-allocation problem consists of a set of agents A = {a1 . . . am} and a set of tasks T = {t1 . . . tn}. If any tuple (Ta1 . . . Tam ) of pairwise disjunct bundles Tai ⊆ T for i = 1 . . .m (= no task is assigned to more than one agent) satisfies ∪mi=1 Tai = T (= each task is assigned to at least one agent), then it is a solution of the task-allocation problem, with the meaning that agent ai performs the tasks Tai . Let ca(T ′) be the agent cost of agent a ∈ A for performing the tasks T ′ ⊆ T . There can be synergies among tasks, that is, ca(T ′ ) + ca(T ′′ ) does not necessarily equal ca(T ′ ∪ T ′′ ) even if T ′ ∩ T ′′ = ∅. We want to find a solution of the task-allocation problemwith a small team cost, given by ∑a∈A ca(Ta).

We study multi-agent routing problems as examples of task-allocation problems, see Figure 1. Multi-agent routing problems are task-allocation problems where the tasks are to visit given targets with exactly one agent each. The terrain, the locations of all agents and the locations of all targets are known. The agent cost of an agent to visit a set of given targets corresponds, for example, to the minimal fuel consumption that the agent needs to visit the targets from its current location. The team cost then corresponds to the fuel consumption of all agents. Multi-agent routing is a standard task for robot teams that needs to be solved, for example, as part of de-mining, search-and-rescue and taking rock probes on the moon [Dias et al., 2006; Koenig et al., 2007]. In multi-agent routing without capacity constraints, every agent can perform an arbitrary number of tasks. In multi-agent routing with capacity constraints, every agent can perform at most a given number of tasks (= its capacity), for example, can take only a given number of rock probes before its drill bit becomes useless due to wear and tear.

3 K-Swaps

We now formalize the concept of task exchanges among agents. Let {Ta}a∈A be the solution before the task exchanges and {T ′a}a∈A be the solution after the task exchanges. We first define partial k-swaps, that describe multiple task exchanges among multiple agents at a time. We then discuss several operations that can be performed on partial kswaps and finally prove several properties of partial k-swaps. Table 1 summarizes our notation.

3.1 Concepts

An out swap of agent a is a task exchange where task t ∈ Ta is transferred from agent a to some other agent, written as (a, -, t, -). An in swap of agent a is a task exchange where task t′ /∈ Ta is transferred from some other agent to agent a, written as (a, -, -, t′). An exchange swap is a task exchange between two different agents a and a′ where task t ∈ Ta is transferred from agent a to agent a′ and task t′ ∈ Ta′ is transferred from agent a′ to agent a, written as (a, a′ , t, t′ ). One (and only one) of the tasks t or t′ in an exchange swap can be empty, written as ∅. Two exchange swaps (a, a′ , t, ∅) and (a, a′ , ∅, t′ ) can be re-written as a single exchange swap

(a, a′ , t, t′ ). A set of exchange swaps is compact iff it does not contain pairs of exchange swaps that can be re-written as single exchange swaps.

A partial k-swap sk describes the task exchanges of a set of agents A(sk ) ⊆ A. It consists of a set of out swaps in which tasks are transferred from agents in A(sk ) to agents not in A(sk ), a set of in swaps in which tasks are transferred from agents not in A(sk ) to agents in A(sk ) and a set of compact exchange swaps in which tasks are transferred between agents that are both in A(sk ). Each agent a ∈ A(sk ) must appear at least once in in, out or exchange swaps of sk . The value k is the number of exchange swaps in sk . We sometimes refer to a partial k-swap as a partial multi-swap if the value of k is unimportant.

A partial k-swap sk is complete iff its sets of out and in swaps are both empty. A complete partial k-swap, called complete k-swap for short, describes exactly k exchange swaps among multiple agents. Complete k-swaps thus generalize single task exchanges, which are complete one-swaps with one empty task in their exchange swap. Complete k-swaps also generalize three contract types introduced in [Sandholm, 1998], namely:

• Swap contracts: A swap contract is a complete one-swap with two non-empty tasks in its exchange swap.
• Cluster contracts: A cluster contract is a complete kswap with only two agents a and a′ whose exchange swaps are of the form (a, a′ , t, ∅) with different tasks t, where k is the size of the cluster.
• Multiagent contracts: A multiagent contract can be represented as a complete k-swap with k + 1 agents for k ≥ 2.

Proposition 1 For any task-allocation problem with n tasks and any solution {Ta}a∈A of the task-allocation problem, there always is a complete n′ -swap sn′ with n′ ≤ n that changes {Ta}a∈A to a solution with the smallest team cost.

The gain of partial k-swap sk is the total decrease of the agent costs of all agents in A(sk ) after executing sk , that is, gain(sk ) = ∑a∈A(sk ) (ca(Ta) - ca(T ′a )). sk is profitable iff its gain is positive. The following proposition shows that the team cost decreases when executing profitable complete k-swaps.

Proposition 2 The team cost of the solution after executing a complete k-swap sk is equal to the team cost of the solution before executing sk minus the gain of sk .

Sometimes a complete k-swap can decrease the team cost of a given solution but no combination of profitable complete k′ -swaps with k′ < k can decrease it. Consider, for example, the multi-agent routing problem without capacity constraints shown in Figure 2. The agents a1 and a2 and targets t1, . . . , tk are located on a graph, and the agents can move only along the edges of the graph. The solution with the smallest team cost is {T ∗ a1 = ∅, T ∗ a2 = {t1, . . . , tk}}. Assume that the given solution is {Ta1 = {t1, . . . , tk}, Ta2 = ∅}. The complete k-swap {(a1, a2, t1, ∅), . . . , (a1, a2, tk, ∅)} is profitable and changes the given solution to the solution with the smallest team cost. However, there is no profitable complete k′ -swap with k′ < k.

A partial k-swap sk is connected iff the graph is connected whose vertices are the agents in A(sk ) and whose edges connect two vertices iff they represent agents that appear in an exchange swap in sk . A disconnected partial k-swap sk can be viewed as a set of two or more connected partial multiswaps. In the following, all partial multi-swaps are assumed to be connected unless mentioned otherwise.

3.2 Operations

An exchange swap (a, a′ , t, t′ ) can be decomposed into an in swap (a,-,-, t′) and an out swap (a,-, t,-) for agent a and an in swap (a′ , -, -, t) and an out swap (a′ , -, t′ , -) for agent a′ . An agent a ∈ A(sk ) can be removed from a partial k-swap sk as follows: First, one decomposes all exchange swaps in sk that contain agent a and then removes all out and in swaps that contain agent a from sk . These out and in swaps form a partial zero-swap that contains only agent a, called the singleton swap ska . After removing agent a from sk , the remaining part of sk is a set of one or more partial multi-swaps, denoted by sk /ska. Conversely, an in swap (a, -, -, t) and an out swap (a′ , -, t, -) can be combined to an exchange swap (a, a′ , t, ∅). Such a pair of out and in swaps form a resolvable pair.

A complete k′ -swap sk′ completes a partial k-swap sk iff it results from adding out and in swaps to sk′ so that all out and in swaps can be grouped into resolvable pairs, combining each resolvable pair into an exchange swap and making all exchange swaps compact. A partial k-swap sk is bounded by K iff there is a complete k′ -swap sk′ with k′ ≤ K that completes it. A partial k-swap is always bounded by the total number of its in, out and exchange swaps although this bound is not necessarily tight.

A partial g-swap sg and a partial h-swap sh are combinable iff they satisfy the following conditions:

• A(sg ) ∩ A(sh ) = ∅.
• For each in swap (a,-,-, t) in sg or sh with t ∈ Ta′ for some agent a′ ∈ A(sg ) ∪ A(sh ), there must be an out swap (a′ ,-, t,-) in sg or sh that forms a resolvable pair with it.
• There must be at least one resolvable pair in sg and sh .

The following operation combine(sg , sh) combines a combinable pair of a partial g-swap sg and a partial h-swap sh to a new partial k-swap sk :

1. Add all exchange swaps in sg and sh to the set of exchange swaps in sk .
2. For each resolvable pair of an in swap (a,-,-, t) and an out swap (a′ ,-, t,-) in sg and sh , add the exchange swap (a, a′ , ∅, t) to the set of exchange swaps in sk .
3. Make the set of exchange swaps in sk compact.
4. Add each in or out swap in sg and sh that is not part of a resolvable pair to the sets of in or out swaps of sk , respectively.

The new partial k-swap sk contains all exchange swaps in sg and sh and one or more additional exchange swaps that result from combining the resolvable pairs of out and in swaps in sg and sh .

Proposition 3 If sk = combine(sg , sh ) for combinable multi-swaps sg and sh , then sk has the following properties: 1) sk is connected, 2) A(sk ) = A(sg ) ∪ A(sh ), 3) gain(sk ) = gain(sg ) + gain(sh ), and 4) k ≥ g + h + 1.

Proposition 4 For any agent a ∈ A(sk ) in a partial k-swap sk , if there are x partial multi-swaps in sk /ska , then agent a can construct sk by using the combine operation x times to combine ska with all partial multi-swaps in sk /ska .

3.3 Properties

We now prove several properties of profitable partial multiswaps.

Theorem 1 For any profitable partial k-swap sk , there is at least one agent a ∈ A(sk ) so that the partial multi-swaps in sk /ska are all profitable.

Proof Sketch: We prove the theorem by induction on the number x of non-profitable singleton swaps ska for all a ∈ A(sk ). It holds trivially for x = 0: Pick any agent a ∈ A(sk ). The partial multi-swaps in sk /ska are all profitable since they are all composed of profitable singleton swaps. Assume that the statement holds for all 0 ≤ x′ < x. It then also holds for x: There is at least one nonprofitable singleton swap. Consider any non-profitable singleton swap ska. If the partial multi-swaps in sk /ska are all profitable, then the theorem holds. Otherwise, there is at least one non-profitable partial g-swap sg ∈ sk /ska. sg contains at most x -1 non-profitable singleton swaps since it does not contain ska. Combine ska with all partial multi-swaps in sk /ska except for sg to a new (connected) partial h-swap sh , that is, sk = combine(sg , sh ). Agent a is the only agent in A(sh) that exchanges tasks with agents in A(sg ). sh is profitable according to Proposition 3 since sg is not profitable but sk is. Transform the partial k-swap sk to a new partial k′ -swap sk′ by contracting sh to a new single agent a′ , as follows: sk′ results from sk by deleting all exchange swaps in sh from sk and changing every agent in A(sh ) that appears in the remaining in, out and exchange swaps to agent a′ . We define the gain of sk′ a′ to be the gain of sh , resulting in sk′ a′ being a profitable singleton swap. Thus, sk′ contains at most x non-profitable singleton swaps, namely the ones in sg , and is profitable since it has the same gain as sk . There is at least one agent a′′ ∈ A(sk′ ) so that the partial multi-swaps in sk′ /sk′ a′′

are all profitable according to the induction assumption. It must be that a′′ ̸= a′ since the non-profitable g-swap sg is the only partial multi-swap in sk′ /sk′ a′ . Transform sk′ back to sk by uncontracting agent a′ to prove the theorem.

Assume that each agent a ∈ A is assigned an index index(a) that orders all agents completely. Then, agent a ∈ A(sk ) is a core of a partial k-swap sk iff the partial multiswaps in sk /ska are all profitable and no agent a′ ∈ A(sk ) with index(a′ ) < index(a) has this property.

Proposition 5 Any profitable partial k-swap sk has exactly one core.

4 Centralized Algorithm

We first present an algorithm for a central planner that constructs all profitable complete k-swaps with 1 ≤ k ≤ K (which we also casually refer to as K-swaps) for a given solution and user-defined constant K ≥ 1:

1. The central planner initializes the following sets to empty: the set R of all profitable complete k-swaps with 1 ≤ k ≤ K and the set Splanner of all partial multiswaps that it has constructed.
2. Each agent a ∈ A constructs all possible partial zeroswaps bounded by K that contain only itself (these partial zero-swaps contain at most K in swaps, at most K out swaps, no exchange swaps and at least one in or out swap) and sends them to the central planner.
3. The central planner adds all partial zero-swaps that it receives from the agents to Splanner and repeats for K rounds:
4. The central planner combines every combinable pair of partial g-swap sg ∈ Splanner and partial hswap sh ∈ Splanner and executes for the resulting partial k-swap sk = combine(sg , sh ):
5. If sk is a profitable complete k-swap bounded by K, then the central planner adds sk to R.
6. If sk is not a complete k-swap but bounded by K, then the central planner adds sk to Splanner.

Each agent sends all partial zero-swaps bounded by K that contain only itself to the central planner in one round, which can result in a communication bottleneck, and the central planner then constructs all partial k-swaps (including all profitable complete k-swaps) bounded by K, which can result in a computation bottleneck.

5 Distributed Algorithm

We therefore now present a distributed (synchronous) algorithm where the agents construct all profitable complete kswaps with 1 ≤ k ≤ K for a given solution by sending only profitable partial multi-swaps to the other agents and thus typically only a small part of their local computation results:

1. Initialize the set R of all profitable complete k-swaps with 1 ≤ k ≤ K to empty, and assign each agent a ∈ A an index index(a) that orders all agents completely.
2. Each agent a ∈ A initializes the following sets to empty: the set S local a of all partial multi-swaps that it has constructed, the set S send a of all profitable partial multiswaps that it will send to all other agents and the set S receive a of all partial multi-swaps that it has received from other agents.
3. Each agent a ∈ A constructs all possible partial zeroswaps bounded by K that contain only itself, adds them to S local a and, if they are profitable, also to S send a . It then sends all partial zero-swaps in S send a to all other agents and sets S send a to empty.
4. Each agent repeats for K rounds:
5. Each agent a adds each partial multi-swap that it receives from the other agents to S receive a .
6. Each agent a combines every combinable pair of partial g-swap sg ∈ S receive a and partial h-swap sh ∈ S local a as long as agent a is part of at least one resolvable pair of sg and sh and executes for the resulting partial k-swap sk = combine(sg , sh ):
7. If sk is a profitable complete k-swap bounded by K and agent a is the core of sk , then agent a adds sk to R.
8. If sk is not a complete k-swap but bounded byK and sk /∈ S local a , then agent a adds sk to S local a and, if sk is profitable and agent a is the core of sk , also to S send a .
9. Each agent a sends all partial multi-swaps in S send a to all other agents and sets S send a to empty.

The following theorem proves that the distributed algorithm constructs all profitable complete k-swaps with 1 ≤ k ≤ K. Each profitable complete k-swap is sent by some agent to all other agents at most once since it can be sent only by its unique core a. The core then stores it in slocal a and does not send it again.

Theorem 2 The core of any profitable partial k-swap bounded by K with 0 ≤ k ≤ K has constructed it by the end of the kth round.

Proof Sketch: We prove the theorem by induction on k. It holds trivially for k = 0 according to Step 3. Assume that the statement holds for all 0 ≤ k′ < k. It then also holds for k: Every profitable partial k-swap sk has a unique core a ∈ A(sk ) according to Proposition 5. Assume that there are x partial multi-swaps in sk /ska. These partial multi-swaps are all profitable according to Theorem 1. Then, the following properties hold: 1) x ≥ 1 since k ≥ 1 and there are thus at least two agents in A(sk ). 2) Each partial multi-swap in sk /ska is bounded by K since sk is bounded by K. 3) h ≤ k-x < k for each partial h-swap sh in sk /ska because sk contains k exchange swaps and one needs to decompose at least one exchange swap for each one of the resulting x partial multi-swaps. Put together, each partial multi-swap in sk /ska has been constructed by its core by the end of the (k - x)th round according to the induction assumption and was then sent to all other agents. Thus, agent a can construct sk by using the combine operation once in each one of the x rounds following the (k - x)th round to combine ska, which it constructed in Step 3, with all partial multi-swaps in sk /ska according to Proposition 4, which proves the theorem.

6 Applications

We have shown how to construct all profitable complete kswaps with 1 ≤ k ≤ K for a given solution and user-defined constant K ≥ 1. We now present several applications, each of which iteratively selects a profitable complete k-swap and executes it on the current solution to reduce the team cost of the current solution, until the team cost of the current solution cannot be reduced any longer:

• GREEDY: During each iteration, Greedy first uses the distributed algorithm described in the previous section to construct all profitable complete k-swaps. It then selects the profitable complete k-swap with the highest gain and executes it on the current solution.
• ROLLOUT: During each iteration, ROLLOUT first uses the distributed algorithm described in the previous section to construct all profitable complete k-swaps. It then evaluates each profitable complete k-swap by hypothetically executing it and then hypothetically using GREEDY on the resulting solution. ROLLOUT then selects the profitable complete k-swap with the smallest team cost for the solution resulting from the hypothetical experiment and executes it on the current solution.

7 Experiments

We now evaluate the benefit of K-swaps for multi-agent routing problems with capacity constraints on known eightneighbor planar grids of size 51 × 51 with square cells that are either blocked or unblocked. The grids resemble office environments with walls and doors, as shown in Figure 1. We set the capacities of all agents to the ratio of the number of targets and agents. We average over 25 instances with randomly closed doors for each number of agents and targets. We consider the following four existing task-allocation algorithms to provide different initial solutions for each instance:

• Randomized Allocation: Randomized allocation randomly assigns each unassigned task to an agent as long as that assignment does not violate the capacity constraint of the agent.
• SSI Auctions: SSI auctions [Tovey et al., 2005] assign tasks to agents in rounds. During each round, they greedily assign an unassigned task to an agent so that the team cost increases the least.
• Auctions with Regret Clearing: Auctions with regret clearing [Koenig et al., 2008] assign tasks to agents in rounds. During each round, they assign the unassigned task with the largest regret to an agent so that the team cost increases the least.
• Sequential Bundle-Bid Auctions: Sequential bundlebid auctions with bundle size two [Koenig et al., 2007] assign tasks to agent in rounds. During each round, they greedily assign two unassigned tasks to one or more agents so that the team cost increases the least.

Each agent needs to solve a version of the Traveling Salesperson Problem (TSP) in order to calculate its agent cost, which is an NP-hard problem. We thus use a combination of the two-opt and cheapest-insertion heuristics to approximate its agent cost quickly. Table 2 tabulates our experimental results. The column "Minimal Cost" shows approximations of the minimal team costs (measured in distance units), which we calculated by solving a Mixed Integer Program with a two hour runtime limit. A value is enclosed in square brackets iff it is only an upper bound on the minimal team cost due to the runtime limit. The runtime to calculate this gold standard quickly increases with the problem size. For example, we are not able to determine the minimal team costs for any of the 25 instances with 10 agents and 40 targets within the runtime limit. The column "Initial Cost" shows the team cost of the initial solution, which we generated via one of Randomized Allocation, SSI Auctions, Auctions with Regret Clearing and Sequential Bundle-Bid Auctions. The columns "Cost" and "Time" show the team cost and runtime (measured in seconds) of the resulting solution after using one of GREEDY and ROLLOUT in conjunction with K-swaps on the initial solution. Team costs that are no larger than the approximations of the minimal team costs are shown in bold.

We make the following observations: First, K-swaps with larger values of K result in smaller team costs but require more runtime (an effort that is more pronounced for ROLLOUT) because the number of all profitable partial k-swaps with 1 ≤ k ≤ K increases with K. Second, K-swaps produce solutions with different team costs if the initial solutions are generated with different task-allocation algorithms, but the difference diminishes as K increases. Third, K-swaps can reduce the team costs of the initial solutions significantly. For example, GREEDY with three-swaps and ROLLOUT with two-swaps produce solutions with team costs that are very close to the approximations of the minimal team costs, no matter how the initial solutions are generated.

8 Conclusions

In this paper, we presented our initial research on improving given task allocations by allowing cooperative agents to exchange their assigned tasks in order to reduce their team cost. We defined a new type of contract, called K-swaps, that describes multiple task exchanges among multiple agents at a time, which generalizes the concept of single task exchanges. We designed a distributed algorithm that constructs all possible k-swaps with 1 ≤ k ≤ K for a given solution and user-defined constant K ≥ 1 that reduce the team cost of a given task allocation and showed that each agent typically only needs to communicate a small part of its local computation results to the other agents. We then demonstrated empirically that K-swaps can reduce the team costs of several existing task-allocation algorithms significantly even if K is small.