Generalized Reaction Functions for Solving Complex-Task Allocation Problems
Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 478-482.
https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-087
© 2011 International Joint Conferences on Artificial Intelligence
Abstract
We study distributed task-allocation problems wherecooperative agents need to perform some tasks simultaneously. Examples are multi-agent routing problems where several agents need to visit some targets simultaneously, for example, to move obstacles out of the way cooperatively. In this paper, we first generalize the concept of reaction functions proposed in the literature to characterize the agent costs of performing multiple complex tasks. Second, we show how agents can construct and approximate reaction functions in a distributed way. Third, we show how reaction functions can be used by an auction-like algorithm to allocate tasks to agents. Finally, we show empirically that the team costs of our algorithms are substantially smaller than those of an existing state-of-the-art allocation algorithm for complex tasks.
- [Desrosiers et al., 1995] J. Desrosiers, Y. Dumas, M. Solomon, and F. Soumis. Time constrained routing and scheduling. In Network Routing, volume 8 of Handbooks in Operations Research and Management Science, chapter 2, pages 35-139. 1995.
- [Dias et al., 2006] M. Dias, R. Zlot, N. Kalra, and A. Stentz. Market-based multirobot coordination: a survey and analysis. Proceedings of the IEEE, Special Issue on Multirobot Coordi- nation, 94(7):1257 -1270, 2006.
- [Koenig et al., 2007] S. Koenig, C. Tovey, X. Zheng, and I. Sungur. Sequential bundle-bid single-sale auction algorithms for decen- tralized control. In Proceedings of the International Joint Con- ference on Artificial Intelligence, pages 1359-1365, 2007. IJCAI
- [Or, 1976] I. Or. Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. PhD thesis, Northwestern University, Evanston, Illinois, 1976.
- [Zheng and Koenig, 2008] X. Zheng and S. Koenig. Reaction func- tions for task allocation to cooperative agents. In Proceedings of the International Joint Conference on Autonomous Agents and MultiAgent Systems, pages 559-566, 2008.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
We study complex-task allocation problems in a cooperative setting where agents collaborate to minimize the team cost (that is, maximize the team performance) and some tasks need to be performed simultaneously. Our motivating problem is multi-agent routing where the tasks are to visit given targets in the plane. The terrain, the locations of the agents and the locations of the targets are known. Multi-agent routing is a standard problem for robot teams [Koenig et al., 2007; Dias et al., 2006], for example, as part of de-mining, searchand-rescue and taking rock probes on the moon. In this paper, we are interested in the version of multi-agent routing where some targets, called complex targets, need to be visited simultaneously by more than one agent. For example, large fires can only be extinguished with several fire engines, and heavy objects can only be moved with several robots. Thus, allocation algorithms for complex tasks have to solve the following two interrelated subproblems:
∗This material is based upon work supported by NSF (while serving at NSF). It is also based upon work supported by ARL/ARO under contract/grant number W911NF-08-1-0468 and ONR in form of a MURI under contract/grant number N00014-09-1-1031. 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 or the U.S. government.
Sven Koenig
University of Southern California Los Angeles, CA 90089-0781 skoenig@usc.edu
- Subproblem 1: Each complex target has to be visited by more than one agent. Thus, one has to determine which group of agents should visit a given complex target.
- Subproblem 2: Each complex target has to be visited by the group of agents at the same time. Thus, one has to determine when a given group of agents should visit a given complex target.
Solving Subproblem 2 is non-trivial since a group of agents needs to agree on a common visit time. Zheng and Koenig [Zheng and Koenig, 2008] proposed an approach that makes use of reaction functions to allocate complex targets to agents. Reaction functions characterize the costs of agents for visiting a single complex target at any given visit time and thus can be used by a central planner to determine the optimal visit time of a group of agents for visiting an additional complex target. The main drawback of this approach is that the visit times of complex targets cannot be changed once they have been assigned, which results in highly suboptimal task allocations. In this paper, we first generalize the concept of reaction functions to characterize the costs of an agent for visiting multiple complex targets at any given visit times. Then, we show how agents can construct and approximate generalized reaction functions in a distributed way. Third, we show how an auction-like algorithm can use generalized reaction functions to allocate targets to agents. Finally, we show empirically that the team costs of our algorithms can be substantially smaller than those of the allocation algorithm developed in [Zheng and Koenig, 2008].
2 Multi-Agent Routing
We follow [Zheng and Koenig, 2008] to formalize multiagent routing problems. A multi-agent routing problem consists of a set of agents A and a set of targets X. The number of different agents that need to visit target x ∈ X simultaneously, called its coalition size, is d(x). We call a target x simple if d(x) = 1 and complex otherwise. The set of simple targets X s and the set of complex targets X c partition the set of all targets. The group of d(x) different agents that need to visit complex target x at some visit time t is called the coalition of the complex target. Each agent in the coalition thus has a commitment to visit the complex target x at visit time t, written as x ← t. Each agent a ∈ A is characterized by a simple target capacity qsa and a complex target capacity qca with the meaning that agent a can visit at most qsa simple targets and at most qca complex targets.
An allocation of agent a is a triple (X s a , X c a ,Ca), where X s a is the set of simple targets assigned to it, X c a is the set of complex targets assigned to it, and Ca is the set of its commitments for the complex targets in X c a . The agent cost cagent a (X s a , X c a ,Ca) is the smallest sum of travel and wait times needed for agent a to visit all targets assigned to it from its initial location, where it can freely determine when to visit each simple target in X s a subject to the restriction that it has to visit all complex targets (if any) at the visit times recorded in its commitment set Ca. (The agent cost is defined to be infinity if agent a cannot satisfy this restriction, |X s a | > qsa or |X c a| > qca.)
Our objective is to find a solution with a small team cost, where a solution requires each target x ∈ X to be assigned to exactly d(x) different agents. All agents in the coalition must have the same commitment for a complex target. The team cost of a set of agents A is ∑a∈A cagent a (X s a, X c a, Ca) (roughly proportional to the energy needed by the agents for traveling and waiting) for the MiniSum team objective and maxa∈A cagent a (X s a, X c a,Ca) (the task-completion time) for the MiniMax team objective. We use cteam as a special operator for either the sum or max operator, depending on the team objective, and write cteam a∈A cagent a (X s a , X c a ,Ca) to make our notation independent of the team objective.
3 Generalized Reaction Functions
In this section, we introduce the concept of (generalized) reaction functions, explain how to construct and use them, and finally describe how to approximate them.
3.1 Concepts
As discussed in the introduction, solving a complex-task allocation problem consists of two parts: which targets should be assigned to which agents (Subproblem 1) and when should the agents visit their assigned targets (Subproblem 2). In order to evaluate a given target assignment, the agents have to determine the visit times of their assigned targets that minimize the team cost (optimal visit times). The reason for introducing reaction functions is to facilitate the determination of the optimal visit times for the complex targets.
Assume that each agent a ∈ A has been assigned a set of simple targets X s a ⊆ X s and a set of complex targets X c a ⊆ X c , let xa = (x1a, . . . , xna a ) be the vector of the complex targets X c a (in an arbitrary order), ta = (t1a , . . . , tna a ) be the vector of the corresponding visit times of these complex targets, and let xa ← ta be the set of commitments {x1a ← t1a , . . . , xna a ← tna a }. Then, the agent cost of agent a for visiting the complex targets xa at visit times ta is cagent a (X s a, X c a, xa ← ta). Let x = (x1, . . . , xn) be the vector of all complex targets ∪a∈AX c a (in an arbitrary order) and t = (t1, . . . , tn) be the vector of the corresponding visit times of these complex targets. We define a projection function fa(v) to project any vector v of complex targets onto the complex targets assigned to agent a ∈ A in order (t1a, . . . , tna a , for example, xa = fa(x) and ta = fa(t). Thus, the optimal visit times of all complex targets can be determined as

| permutations (π ∈ Πa1 ) | visit orders (p ∈ Pa1,π) | vectors of visit times (tp) | agent cost (cp) |
|---|---|---|---|
| (x1, x2) | a1 ⇝ x1 ⇝ x2 ⇝ xs a1 ⇝ x1 ⇝ xs ⇝ x2 a1 ⇝ xs ⇝ x1 ⇝ x2 | (3, 7) (3, 11) (13, 17) | 10 11 17 |
| (x2, x1) | a1 ⇝ x2 ⇝ x1 ⇝ xs a1 ⇝ x2 ⇝ xs ⇝ x1 a1 ⇝ xs ⇝ x2 ⇝ x1 | (5, 9) (5, 13) (11, 15) | 14 13 15 |
where R+ is the set of all non-negative numbers.
For the given target assignment {(X s a, X c a)}a∈A, we can construct a bipartite graph of agents A and complex targets X c where an edge connects an agent a and a complex target x iff x is assigned to a. Two agents are related iff they are connected in the graph. This relationship partitions the set of agents A into a set of bundles B = {b1, . . . , bl} where each bundle b ∈ B consists of agents that are related with each other. Since agents in different bundles can determine the visit times of their assigned targets independently, we have mint∈Rn+ cteam a∈A cagent a (X s a , X c a, xa ← fa(t)) = cteam b∈B (mintb∈Rnb + cteam a∈b cagent a (X s a , X c a , xa ← fa(tb))), where nb is the number of complex targets assigned to bundle b and tb is the vector of the visit times of these complex targets. In other words, we can solve the minimization problem mintb∈Rnb + cteam a∈b cagent a (X s a , X c a , xa ← fa(tb)) independently for each bundle b ∈ B.
We now introduce a reaction function F Xca a (ta) for each agent a in a bundle b ∈ B that characterizes its agent cost (= the smallest sum of travel and wait times) of visiting its assigned complex targets X c a at any given visit times ta:
which generalizes the concept of reaction functions proposed in [Zheng and Koenig, 2008]. The optimal visit times t∗b for the complex targets assigned to bundle b can thus be determined as follows:
3.2 Constructing Reaction Functions
Given a target assignment {(X s a, X c a)}a∈A, agent a ∈ A constructs its reaction function F Xca a (ta) as follows:
- Agent a constructs all possible visit orders of its assigned targets in X s a ∪X c a . Let Pa be the set of all these visit orders.
- Agent a constructs all possible permutations of its assigned complex targets in X c a = {x1a, . . . , xna a }. Let Πa be the set of all these permutations. For each permutation π = (xπ(1) a , . . . , xπ(na) a ) in Πa, let Pa,π be the set of the visit orders in Pa in which complex targets are visited in the order given by permutation π.
Consider the multi-agent routing problemwith the given target assignment shown in Figure 1, where the agents and targets are located on a graph and the agents can only move along the edges of the graph. The coalition sizes of all three complex targets are 2. Table 1 tabulates the permutations of complex targets and the visit orders of targets that are assigned to agent a1.
- For each permutation π ∈ Πa and each visit order p ∈ Pa,π, agent a finds the vector of visit times tp = (tπ(1) p , . . . , tπ(na) p ) of the complex targets in π and calculates the resulting agent cost cp if it visits its assigned targets in visit order p without waiting at any target. For example, Table 1 tabulates the vectors of visit times and the corresponding agent costs for each possible visit order of agent a1.
- For each permutation π ∈ Πa and each visit order p ∈ Pa,π, agent a constructs a meta-function F π a,p(tπa ), which characterizes the agent cost of agent a if it visits its assigned targets in visit order p, as follows:
Domain: The domain of this meta-function is the set of all possible visit times tπa = (tπ(1) a , . . . , tπ(na) a ) of the complex targets in π = (xπ(1) a , . . . , xπ(na) a ) if agent a visits its assigned targets in visit order p and waits only at complex targets. Consider any pair of adjacent complex targets xπ(i-1) a ∈ π and xπ(i) a ∈ π. Their visit times tπ(i-1) a and tπ(i) a must satisfy tπ(i) a - tπ(i-1) a ≥ tπ(i) p - tπ(i-1) p since tπ(i) p - tπ(i-1) p is the travel time of agent a from complex target xπ(i-1) a to xπ(i) a in visit order p. This constraint can be re-written as tπ(i) a - tπ(i) p ≥ tπ(i-1) a - tπ(i-1) p . Thus, the domain of the meta-function is the set of vectors of visit times tπa = (tπ(1) a , . . . , tπ(na) a ) that satisfy tπ(na) a - tπ(na) p ≥ . . . ≥ tπ(1) a - tπ(1) p ≥ 0. We define a boolean function B(ta) = true iff tna a ≥ . . . ≥ t1a ≥ 0 for any vector ta so that the domain constraint of the meta-function can be simply written as B(tπa - tp) = true.
Value: The value of this meta-function is the agent cost of agent a if agent a visits its assigned targets in visit order p and waits only at complex targets, which can be calculated as:
F π a,p(tπa) = cp + tπ(na) a - tπ(na) p iff B(tπa - tp) = true where cp is the travel time of agent a to visit its assigned targets in the order p and tπ(na) a -tπ(na) p is the total wait time of agent a at complex targets for the given visit times tπa. For the sake of convenience, we define F π a,p (tπa ) :=∞ if B(tπa - tp) = false.

(a) Reaction Function of a
(b) Reaction Function of a
(c) Reaction Function of a
Figure 2: Domains of Reaction Functions
- For each permutation π ∈ Πa, agent a constructs a permutation function F π a (tπa) whose domain consists of the vectors of visit times tπa of complex targets in π that satisfy the domain constraint B(tπa) = true and whose value is determined as the minimum of meta-functions F π a,p (tπa ) for all visit orders p ∈ Pa,π:
- Finally, the reaction function F Xca a (ta) of agent a is the collection of all permutation functions F π a (tπa ) for each permutation π ∈ Πa.
Consider again the multi-agent routing problem shown in Figure 1. Figure 2 shows the domains of the reaction functions of agents a1, a2 and a3 for the given target assignments, where a meta-function corresponds to a visit order of an agent.
The correctness of our approach is given by the following lemma and theorem.
Lemma 1 For each permutation π ∈ Πa of the complex targets assigned to agent a, the agent cost (= the smallest sum of travel and wait times) of agent a for visiting its complex targets in the order given by permutation π at any given visit times tπa is the value of the permutation function F π a (tπa ), namely, minp∈Pa,π F π a,p(tπa ).
Proof: Let c∗ be the agent cost of agent a. If c∗ =∞, then there does not exist any visit order so that agent a can visit its complex targets in the order given by permutation π at visit times tπa , that is, B(tπa - tp) = false for each visit order p ∈ Pa,π. Thus, c∗ = minp∈Pa,π F π a,p(ta). If c∗ ̸= ∞, then let p∗ be a visit order of agent a that results in agent cost c∗ . We let wa = (wπ(1) a , . . . ,wπ(na) a ) be the vector of total wait times of agent a at complex targets, where wπ(i) a is the total wait time of agent a at all complex targets xπ(j) a with 1 ≤ j ≤ i. Consider the meta-function F π a,p∗(tπa) of agent a for visit order p∗ . We have tπ(na) a = tπ(na) p∗ + wπ(na) a and F π a,p∗(tπa ) = cp∗ + tπ(na) a - tπ(na) p∗ = cp∗ +wπ(na) a = c∗ . Since p∗ ∈ Pa,π, we have c∗ = F π a,p∗(tπa) ≥ minp∈Pa,π F π a,p(tπa ). Given that c∗ is the smallest sum of travel and wait times of agent a, by definition minp∈Pa,π F π a,p(tπa) cannot be less than c∗ . Thus, c∗ = minp∈Pa,π F π a,p(tπa ).
Theorem 1 The agent cost of agent a for visiting its complex targets X c a = {x1a , . . . , xna a } at any given visit times ta = (t1a, . . . , tna a ) can be calculated from its reaction function F Xca a (ta).
| permutations | scenarios |
|---|---|
| (x1, x2, x3) (x1, x3, x2) (x2, x1, x3) (x2, x3, x1) (x3, x1, x2) (x3, x2, x1) | a1 does not wait at x1, a1 does not wait at x2, a2 does not wait at x3 a1 does not wait at x1, a1 does not wait at x2, a3 does not wait at x3 a1 does not wait at x1, a3 does not wait at x2, a2 does not wait at x3 a1 does not wait at x1, a3 does not wait at x2, a3 does not wait at x3 a2 does not wait at x1, a1 does not wait at x2, a2 does not wait at x3 a2 does not wait at x1, a1 does not wait at x2, a3 does not wait at x3 a2 does not wait at x1, a3 does not wait at x2, a2 does not wait at x3 a2 does not wait at x1, a3 does not wait at x2, a3 does not wait at x3 |
Proof: Sort the visit times ta = (t1a, . . . , tna a ) in increasing order to yield tπa = (tπ(1) a , . . . , tπ(na) a ), which results in permutation π = (xπ(1) a , . . . , xπ(na) a ). Lemma 1 states that the agent cost of agent a for visiting its complex targets (xπ(1) a , . . . , xπ(na) a ) at visit times tπa = (tπ(1) a , . . . , tπ(na) a ) can be calculated as the value of the permutation function F π a (tπa), which is also the agent cost of agent a for visiting its complex targets (x1a, . . . , xna a ) at visit times ta = (t1a, . . . , tna a ).
3.3 Determining Optimal Visit Times
Given the reaction function F Xca a (ta) of each agent a in the bundle b of related agents, the optimal visit times of complex targets xb = (x1b , . . . , xnb b ) that are assigned to bundle b can be determined as arg mintb∈Rnb + cteam a∈b F Xca a (fa(tb)). The minimization is over Rnb + (= all possible visit times of the nb complex targets). The following theorem, however, shows that this is unnecessary.
Theorem 2 Let T be the set of vectors of visit times tb at which the agents in bundle b are able to visit the complex targets xb without waiting at any simple target and for each complex target in xb there exists at least one agent in its coalition that does not wait at it. Then,
Proof: Let t∗b be the optimal visit times of complex targets xb. If there exists any simple target at which its assigned agent waits or any complex target at which all agents in its coalition wait, run the following procedure on this target x: First, find the smallest wait time sx > 0 of all agents at target x. Then, let each agent visit target x sx time units earlier. The resulting team cost does not increase since all agents visit their targets no later than before. Repeat this procedure until agents do not wait at any simple target and for each complex target there exists at least one agent in its coalition that does not wait at it. The resulting visit times belong to set T , and the resulting team cost is no larger than that of the optimal visit times t∗b .
Now we describe how a central planner can construct the set T based on the reaction functions of agents:
- The central planner constructs all possible permutations πb of the complex targets in xb.
- The central planner constructs all possible scenarios so that, for each complex target in xb, there is at least one agent in its coalition that does not wait at it.
For example, Table 2 tabulates all possible permutations and scenarios for the multi-agent routing problem from Figure 1.
- For each combination of a scenario and a permutation πb = (xπb(1) b , . . . , xπb(nb) b ), the central planner generates a search tree for constructing the visit times tπb b = (tπb(1) b , . . . , tπb(nb) b ) that belong to set T , starting with the root node (tπb(1) b ≥ 0, . . . , tπb(nb) b ≥ tπb(nb-1) b ) at depth 0. The depth of the search tree is nb. Each node at any depth i with 1 ≤ i ≤ nb has the form (tπb(1) b , . . . , tπb(i) b , tπb(i+1) b ≥ tπb(i) b , . . . , tπb(nb) b ≥ tπb(nb-1) b ), where the visit times (tπb(1) b , . . . , tπb(i) b ) have been determined from the previous depths. Consider any node (tπb(1) b , . . . , tπb(i) b , tπb(i+1) b ≥ tπb(i) b , . . . , tπb(nb) b ≥ tπb(nb-1) b ) at depth i. We now show how the central planner determines the visit time tπb(i+1) b at depth i + 1: Assume that agent a does not wait at complex target xπb (i+1) b in the given scenario. First, the central planner constructs the permutation πa = fa(πb) of the complex targets assigned to agent a and finds the complex target xπa(j) a ∈ πa that is identical to xπb(i+1) b ∈ πb. Then, for each visit order p ∈ Pa,πa of agent a, it determines the visit time tπa(j) a of complex target xπa(j) a to be tπa(j-1) a + tπa(j) p - tπa(j-1) p , where tπa(j-1) a is the visit time of complex target xπa(j-1) a and tπa(j) p -tπa(j-1) p is the travel time of agent a from complex target xπa(j-1) a to xπa(j) a in visit order p. Finally, it generates one child node in which tπb(i+1) b = tπa(j) a and labels the edge from the node in question to the child node with the domain constraint B(tπa a - tp) = true of meta-function F πa a,p (tπa a ). If the determined visit times in the child node are inconsistent with any domain constraint labeling the edges from the root to the child node, the central planner removes the child node from the search tree. This completes the construction of the search tree. The central planner then adds the vectors of visit times in the leaf
nodes of the search tree to set T .
Consider again the multi-agent routing problem from Figure 1. Assume that the permutation of complex targets is (x1, x2, x3) and the scenario is that a2 does not wait at x1, a1 does not wait at x2 and a3 does not wait at x3. Figure 3 shows the search tree constructed by the central planner, and Figure 4 shows the corresponding meta-functions of agents used to determine the visit times.
3.4 Approximating Reaction Functions
The number of meta-functions in the reaction function of agent a usually depends on the number of visit orders of agent a for visiting its assigned targets, which is usually exponential in the number of its assigned targets. Thus, the computation of the reaction function is time-intensive. Now we show how to approximate reaction functions by considering only a constant number of visit orders, similar to the approach used in [Zheng and Koenig, 2008]:
- Agent a finds a sufficiently large visit time e so that it can visit all assigned (both simple and complex) tar-


gets in any visit order before time e. For example, ∑x∈Xs a∪Xca 2 · d(a, x) + ϵ could be a simple choice of e, where d(a, x) is the travel time of agent a from its initial location to target x ∈ X s a ∪ X c a and ϵ is a small positive constant. Then, agent a divides the time interval [0, e) evenly into G time intervals [sj, ej) for a given discretization granularity G. Lastly, agent a constructs all possible vectors of na time intervals ([s1 , e1 ), . . . , [sna , ena )), where the value of each [si , ei ) in the vector can be [sj , ej) for any 1 ≤ j ≤ G.
- Agent a solves the following optimization problem for each vector of time intervals ([s1 , e1), . . . , [sna , ena )), namely, to find the visit order p of its targets X s a ∪ X c a with the minimal agent cost that satisfies the following two constraints: 1) it visits complex target xia at time tip ∈ [si , ei ) and 2) it does not wait at any target. 1 (Such visit order may not always exist for any given vector of time intervals.) Let the set P ′a be the set of the resulting visit orders p found for all possible vectors of time intervals ([s1 , e1 ), . . . , [sna , ena )).
- The remaining steps of constructing the approximate reaction function are identical to Steps 2-6 of constructing the reaction function as described in Section "Constructing Reaction Functions" if one replaces Pa with P ′a everywhere.
Approximate reaction functions are identical to the ideal ones if agent a uses an infinite number of time intervals (G = ∞). In general, however, approximate reaction functions may not be identical to the ideal reaction functions. For example, Figure 5 shows two approximate reaction functions obtained with e = 24 and different discretization granularities.
1 This optimization problem is a special case of the NP-hard traveling salesperson problem with time windows [Desrosiers et al., 1995]. We use the Or-opt heuristic [Or, 1976] to solve it approximately.

4 Auctions with Reaction Functions
Now, we describe a greedy auction-like algorithm that makes use of reaction functions to allocate targets to distributed agents in a hill-climbing fashion, similar to [Koenig et al., 2007; Zheng and Koenig, 2008]. The agents are the bidders, and a central planner is the auctioneer. The algorithm consists of multiple rounds to allocate all targets to agents. Initially, all targets are unassigned. During each round, all agents bid on all unassigned targets (bidding phase) and the auctioneer assigns one additional target to a coalition of agents (winner determination phase) so that the team cost increases least (= hill-climbing principle). Consider any round of the algorithm. Assume that the current allocation of agent a ∈ A is (X s a , X c a , Ca) and the set of unassigned targets is U. We now explain how the agents bid and how the auctioneer determines the winning bid:
- Bidding Phase For each unassigned simple target xs ∈ U, agent a constructs and bids the following reaction function: (Case 1) If X c a ̸= ∅, then it constructs a reaction function F Xca a,xs (ta) = cagent a (X s a ∪ {xs }, X c a, xa ← ta), where xa is the vector of complex targets in X c a and ta is the corresponding vector of visit times; (Case 2) If X c a = ∅, then it constructs a (trivial) reaction function F ∅ a,xs(·) = cagent a (X s a ∪ {xs}, ∅, ∅).
For each unassigned complex target xc ∈ U, agent a constructs and bids a reaction function F Xca a,xc(ta) = cagent a (X s a , X c a ∪ {xc }, xa ← ta), where xa is the vector of complex targets in X c a ∪ {xc } and ta is the corresponding vector of visit times.
- Winner Determination Phase The auctioneer needs to keep records of the following information for each agent a ∈ A: 1) its current allocation (X s a, X c a,Ca); 2) its current agent cost cagent a (X s a, X c a, Ca); and 3) its current reaction function F Xca a (ta) if X c a ̸= ∅. Remember that allocation algorithms for complex tasks need to solve two subproblems as described in the introduction:
Solution of Subproblem 1: First, the auctioneer constructs the set O(d(x)) that contains all coalitions of d(x) different agent(s) for visiting each unassigned target x ∈ U. Second, for each coalition o ∈ O(d(x)), the auctioneer constructs the bundle b(x, o) ⊆ A of agents that are related to agents in o after allocating target x to coalition o. Let xb(x,o) be the vector of all complex targets assigned to bundle b(x, o) and tb(x,o) be the corresponding vector of visit times. Third, the auctioneer determines the evaluation cost ceval x,o of allocating each target x ∈ U to each coalition o ∈ O(d(x)) and the optimal visit times t∗b(x,o) for complex targets in xb(x,o) as explained below in the solution of Subproblem 2. Fourth, the auctioneer determines (x∗ , o∗ ) = arg minx∈U,o∈O(d(x)) ceval x,o . Finally, the auctioneer allocates the target x∗ to all agent(s) in o∗ and sets the visit times of all complex targets xb(x∗ ,o∗ ) to t∗b(x∗ ,o∗ ) .
Solution of Subproblem 2: For each agent a ∈ b(x, o), the auctioneer constructs the following evaluation function:
where the reaction function F Xca a (ta) is either the reaction function F Xca a,x(ta) submitted by agent a in the bidding phase if agent a ∈ o, or the reaction function F Xca a (ta) recorded by the auctioneer if agent a /∈ o. Let nb(o,x) be the number of complex targets in xb(o,x). Then, the auctioneer determines the evaluation cost ceval
o,x to be mintb(o,x)∈Rnb(o,x) + cteam a∈b(o,x)V Xca a (fa(tb(o,x))) and t∗b(o,x) to be the corresponding optimal visit times.
Variants: All simple targets are assigned to agents before any complex target in [Zheng and Koenig, 2008]. However, this is not necessary for our approach with generalized reaction functions since the agents are able to update the visit times of complex targets that have already been assigned to them when a new target is assigned. In order to better evaluate our approach, we use the following three variants of the auction-like algorithm: V.1 (Mixed) There is no restriction on the auction-like algorithm. V.2 (Simple-First): All simple targets are assigned before any complex target. V.3 (Complex-First): All complex targets are assigned before any simple target.
5 Experimental Results
We now evaluate the benefits of generalized reaction functions. Since the algorithm ARF introduced in [Zheng and Koenig, 2008] is the only existing allocation algorithm in the literature for multi-agent routing with complex targets, we compare all three variants of the auction-like algorithm introduced in the previous section against it. We use multi-agent routing problems on a known four-neighbor planar grid of size 51 × 51 with square cells that are either blocked or unblocked. The grid resembles an office environment with walls and doors [Koenig et al., 2007]. Table 3 tabulates the team costs and runtimes of allocation algorithms for solving multiagent routing problems with 10 agents, 40 simple targets and 5 complex targets. The coalition size of each complex target is 2. Each agent can be assigned at most four simple targets and three complex targets. We report data that has been averaged over 25 instances with randomly generated locations of agents and targets. We make the following observations: First, the team costs of the auction-like algorithms are significantly smaller than those of ARF for both the MiniSum and MiniMax team objectives since agents can update the visit times of their assigned complex targets when a new target is assigned. Second, the runtimes of the auction-like algorithms are still small, although they increase significantly as the discretization granularity G increases. Third, the team costs and runtimes of the "Mixed" variant are very similar to those of the "Simple-First" variant for the MiniSum team objective. The reason is that simple targets tend to be allocated before complex targets in the "Mixed" variant for the MiniSum team objective since the team cost typically increases less when allocating an additional simple target to some agent than allocating an additional complex target to a coalition of agents.
| Allocation Algorithm | MiniSum | MiniMax | |||
|---|---|---|---|---|---|
| TeamCost | Runtime | TeamCost | Runtime | ||
| ARF [Zheng and Koenig, 2008] | 824.16 | 0.04 | 162.12 | 0.03 | |
| Ideal | 717.64 | 0.38 | 150.26 | 0.25 | |
| Mixed G = 30 | 718.44 | 0.20 | 150.39 | 0.19 | |
| G = 15 | 719.12 | 0.09 | 152.60 | 0.07 | |
| Ideal | 717.06 | 0.37 | 137.18 | 0.28 | |
| Simple-First G = 30 | 717.41 | 0.24 | 137.24 | 0.20 | |
| G = 15 | 718.16 | 0.11 | 137.44 | 0.12 | |
| Ideal | 726.48 | 0.52 | 151.39 | 0.43 | |
| Complex-First G = 30 | 727.84 | 0.38 | 154.40 | 0.22 | |
| G = 15 | 733.92 | 0.20 | 155.32 | 0.15 | |
6 Conclusions
We studied how to improve the team performance of allocation algorithms for complex tasks. We first generalized the concept of reaction functions proposed in the literature to characterize the agent costs of performing multiple complex tasks at given times. Second, we showed how agents can construct and approximate reaction functions in a distributed way. Third, we showed how an auction-like algorithm can use reaction functions to allocate tasks to agents. Finally, we showed empirically that the team performance of our algorithm is substantially better than those of an existing state-ofthe-art allocation algorithm for complex tasks.
@inproceedings{ijcai2011p87,
title = {Generalized Reaction Functions for Solving Complex-Task Allocation Problems},
author = {Zheng, Xiaoming and Koenig, Sven},
booktitle = {Proceedings of the Twenty-Second International Joint Conference on
Artificial Intelligence, {IJCAI-11}},
publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
editor = {Toby Walsh},
pages = {478--482},
year = {2011},
month = {7},
doi = {10.5591/978-1-57735-516-8/IJCAI11-087},
url = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-087},
}
TY - CPAPER TI - Generalized Reaction Functions for Solving Complex-Task Allocation Problems AU - Zheng, Xiaoming AU - Koenig, Sven T2 - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11 PB - AAAI Press/International Joint Conferences on Artificial Intelligence PY - 2011 SP - 478 EP - 482 DO - 10.5591/978-1-57735-516-8/IJCAI11-087 UR - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-087 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: