A Scalable Approach to Chasing Multiple Moving Targets with Multiple Agents

1 Introduction

In moving target search (MTS), introduced in the AI literature by Ishida and Korf [1991], a mobile agent chases a mobile target on a map. As a target's location changes constantly, an agent needs to be able to adapt its strategy very fast, making this a challenging real-time search problem.

We address the problem where multiple agents chase multiple mobile targets. We call this the multiple agents and targets variant of MTS, or, shortly, the MAT problem. The problem has multiple practical applications, such as pursuing suspect vehicles with police cars, and controlling non-player characters in video games. The task is to plan the moves of the agents so that they catch the mobile targets.

Addressing MAT efficiently is challenging. Existing approaches rely on minimax searches 1 either on the combined state space of all agents and all targets [Vieira et al., 2008], or on sub-spaces with one target and one team of agents each [Vieira et al., 2009]. Performing minimax search in the MAT

∗ Part of this work has been performed when the first author was a visitor to IBMResearch, Ireland.

1 In this work, we call a minimax search a search in the combined space of two or more units, where hunter agents minimize the duration of a chase, and targets maximize it.

Akihiro Kishimoto

IBMResearch, Ireland akihirok@ie.ibm.com

problem can provide optimal policies [Vieira et al., 2008]. However, minimax search introduces a major performance bottleneck. Moldenhauer and Sturtevant [2009b] have shown that, even in the simpler case of one agent and one target, minimax search is computationally expensive, reaching millions of node expansions on small gridmaps with up to 1600 nodes, much smaller than modern game gridmaps used in our experiments. The search effort grows sharply with the map size and the number of agents.

We introduce a sub-optimal but scalable approach to the MAT problem. Our method assigns individual agents to individual targets. The assignment can change dynamically. The computation of each assignment considers the current positions of agents and targets, and ignores future possible movements of the targets. This allows to avoid running minimax searches, greatly reducing the computational costs. Given an assignment, our method runs a series of independent single-agent, single-target chases. In each independent chase an agent uses optimal moves towards the current target position. The moves are retrieved from a compressed path database [Botea, 2011], following a state-of-the-art approach in single-agent, single-target MTS [Botea et al., 2013].

We formally show that our algorithm terminates, with all targets captured, and provide upper bounds for the time steps required to complete a chase. We formally analyse the impact of the re-assignment frequency on the solution quality. We provide upper bounds for the suboptimality stemming from the decision of not recomputing a new assignment at one or several iterations in a row.

We perform a detailed empirical analysis on a collection of gridmaps from Sturtevant's repository [Sturtevant, 2012]. Our approach shows a strong scalability performance. It can solve instances with up to 200 agents and 200 targets, on a map with nearly 100,000 nodes, within the order of one second, or even a fraction of a second. On the other hand, previous approaches do not scale beyond small instances with a few agents and much smaller graphs. On small instances, where a comparison to an optimal minimax policy is possible, our system is shown to produce solutions of a good quality, as their sub-optimality is no larger than 12.84 % on average.

2 RelatedWork

The "standard" MTS assumes a single agent, a single target, and full knowledge about the environment and the target's position. Recent successful approaches to standard MTS include incremental search, reusing part of the results computed in a previous search round [Sun et al., 2012], using compressed path databases [Botea et al., 2013], and searching in subgoal graphs [Nussbaum and Y¨or¨ukc¸ ¨u, 2015].

Moving target search has been investigated in partially known and dynamic environments [Koenig et al., 2007; Sun et al., 2010; Baier et al., 2014]. Other research has focused on multiple agents chasing one target [Goldenberg et al., 2003; Isaza et al., 2008]. Goldenberg et al. [2003] assume that the target position is not fully known to the agents. Replaning paths for multiple agents after each target movement could be slow. In addressing this, Isaza et al. [2008] use cover sets, regions that an agent can reach faster than the target. Cover sets are used to coordinate multiple agents chasing one target.

Among the contributions focusing on multi-agent, multitarget scenarios, Hahn and MacGillivray [2006] discuss the problem from a theoretical angle, focusing on the existence of a winning strategy for the agents (the "cops"). Vidal et al. [2002] take a probabilistic approach in scenarios with heterogeneous agents, such as helicopters, that can only observe, but not capture, and ground vehicles.

Vieira et al.'s work [2008; 2009] is the most closely related to our research, and a summary is necessary to better motivate our work. Vieira et al. [2008] describe a minimax strategy for computing optimal agent policies. This approach runs a minimax search in the combined state space of all agents and all targets, which does not scale beyond small problems, with small maps and a few agents.

Vieira et al. [2009] take a step towards improving scalability, with a suboptimal decomposition approach. Assuming that c(G) agents are sufficient to eventually capture a target, there are r targets and p ≥ c(G) × r agents, this work enumerates teams of c(G) agents each. For each combination of a target and a team of agents, a minimax search returns a cost such as the max time to capture that target. Teams of agents are statically assigned to targets in such a way that the max capture time, across all team-target pairs considered in the assignment, is minimized. As such, this boils down to a linear bottleneck assignment problem. Vieira et al.'s work [2009] requires enumerating potentially many teams of agents. Then, for each combination of a team and a target, an expensive minimax search is employed. Even in the base case when c(G) = 1, where only trivial one-agent "teams" are considered, p×r expensive minimax searches are needed. Furthermore, these have to be performed upfront, potentially causing large first-move lags, before agents start moving.

3 ProblemDescription

Agents and targets share an environment represented as a connected graph. The time is discretized. A transition from one time step to the next is called an iteration. At an iteration, agents take an action each, after which targets take an action each. Actions include moving to an adjacent node, or staying put. An agent can capture a target when they share the same location. Due to space limitations, we focus on the case when agents capture only their currently assigned target. An instance is solved when all targets are captured.

Head-to-head collisions between two agents are easier to address than in standard multi-agent path finding, as agents are free to swap their targets in our problem. Swapping the targets of the two agents results in swapping their travel direction. The result is equivalent to allowing the agents to pass by each other. In this work we assume that agents can pass by each other. We further assume that multiple agents can share a given location, a typical assumption in multi-agent moving target search [Goldenberg et al., 2003; Isaza et al., 2008; Vieira et al., 2008; 2009]. More generally, any instance can be solved while restricting the number of agents per location (e.g., at most 1), thanks to the freedom of assigning any target to any agent, but this is beyond the focus of this short paper.

The graph is static and unweighted. The positions of the agents and targets are known. Agents move slightly faster than targets, to ensure that a chase eventually finishes. For a given target, this is implemented by requiring that, once in l iterations, where l is a parameter (the stay-put parameter), the only action available to the target at that iteration is staying put. We set l = 10, as previously done in the literature (e.g., [Sun et al., 2012; Botea et al., 2013]).

4 Our Approach Overview

Algorithm 1 Generate Agent Moves

Input Agent positions pa, target positions pt, map (graph) g, (possibly empty) assignment a

Output Agent moves

• 1: if new assignment desired at this iteration then
• 2: d ←ComputeDistance(pa, pt, g)
• 3: a ←ComputeAssignment(d)
• 4: m←GenerateMoves(a, pa, pt, g)
• 5: return m

Algorithm 1 outlines how agent moves are generated. This is invoked at each iteration, until all targets are captured. We compute d as an exact distance matrix, using compressed distance databases [Xie et al., 2015] as a distance oracle.

Method ComputeAssignment(d) assigns one target to each agent. When a new assignment is computed, it becomes the active assignment. We discuss our assignment strategies in more detail in the next section. The frequency of computing a new active assignment (i.e., lines 1 to 3) is analysed theoretically in Section 6 and evaluated empirically in the experiments section.

As soon as an active assignment is available (step 4), we reduce the problem to a collection of independent singleagent, single-target moving target search instances (i.e., standard MTS instances). This is implemented in method GenerateMoves, which returns a move for each agent. We address each standard MTS instance with a state-of-the-art approach from the literature [Botea et al., 2013]. As such, an optimal move from the current location of an agent to the current location of its assigned target is fetched fast, by querying an oracle such as a compressed path database [Botea, 2011]. No effort is wasted in computing a longer path fragment than just one move at a time.

Our approach is modular, decomposing the original problem into subproblems. This allows to address part of the subproblems involved with state-of-the-art approaches to those subproblems from the literature. For example, we leverage existing solutions to the assignment problem and to the single agent, single target MTS problem.

Given m agents and n targets, in the rest of this paper we focus on scenarios with m = n. However, our approach easily allows addressing more general scenarios. For instance, when m < n, focus on m targets at a time. When a target is captured, another target is assigned to an agent. When m > n, assign at least one agent per target. In experiments we include a brief evaluation on cases with m ̸= n.

5 Assigning Agents to Targets

Computing an active assignment considers the current positions of agents and targets, but not their potential future positions. This allows to reduce the task of assigning agents to targets to classical assignment problems [Munkres, 1957; Burkard et al., 2009], as shown later in this section. The exact assignment problem formulation depends on the solution quality criterion at hand. We consider three such criteria: the sum of the distances between each agent and its target (summation cost), the max distance (makespan), and a combination with the makespan as the main component. Strategies presented in this section are optimal with respect to the current positions of targets but, as mentioned earlier, not necessarily optimal with respect to future target positions. For this reason, we call them statically optimal assignments.

Summation Cost Criterion. This criterion is relevant in problems where reducing the total traveled distance matters (e.g., to reduce fuel consumption). In this case, we obtain a linear assignment problem. It consists of finding an assignment that minimizes the sum of distances between each agent and its assigned target at the current time. The problem is solved exactly in an O(n3 ) time [Edmonds and Karp, 1972]. We say an assignment computed this way is statically optimal with respect to summation cost. In Figure 1, the assignment (A1, T1), (A2, T2) is statically optimal with respect to the summation cost. Its cost is 1+7 = 8, whereas the cost of the assignment (A1, T2), (A2, T1) is 5 + 5 = 10.

Theorem 1. With the summation cost in use, a chase terminates (with all targets captured) in at most S0 × l iterations, where S0 is the summation cost of the initial assignment and l is the stay-put parameter.

Proof. Let S be the summation cost, initialized to S0. S never increases from an iteration to the next, as each agent chases its assigned target. S never increases when a reassignment is performed, as every new assignment minimizes S. S strictly decreases when a target stays put. It follows that S converges to 0 after at most S0 × l iterations.

Makespan Criterion. Reducing the makespan is important when a chase should finish as soon as possible (e.g., when police are chasing suspect cars). We obtain the known linear bottleneck assignment problem, which consists of finding an assignment that minimizes the maximum distance between an agent and its assigned target. In Figure 1, the assignment (A1, T2), (A2, T1) is statically optimal with respect to the makespan. Its makespan is max(5, 5) = 5, whereas the makespan of the other assignment is max(1, 7) = 7.

We solve the linear bottleneck assignment problem as a modified bipartite match problem as follows. We find a minimal edge weight w with the property that after removing all edges with larger weights than w there still exists at least one one-to-one match. Our algorithm has the following steps: 1) Sort all edge weights in ascending order, and store them in a list L; 2) Binary search L to find the minimal value w such that, after removing all edges with larger weight than w, there still exists at least one assignment; 3) Return such an assignment. Step 2 dominates the time complexity. Testing whether a perfect bipartite match exists is done with the Kopcroft-Karp algorithm [Hopcroft and Karp, 1973], with a time complexity of O(n2.5 ). After factoring in the binary search part, the complexity becomes O(n2.5 logn). We say that an assignment computed as shown above is statically optimal with respect to the makespan cost.

Let M0 be the makespan of the initial assignment.

Theorem 2. Assume re-assignments give priority to the old assignment, when this remains optimal. With the makespan in use, a chase terminates (with all targets captured).

Proof. Let M be the makespan, initialized to M0. M cannot increase from one iteration to another, as each agent follows its target. M cannot increase during a re-assignment, as the re-assignment minimizes M.

We show that M decreases (by at least 1) after a finite number of steps. Assume by contradiction that M never decreases. It follows that M does not decrease during a reassignment, which further implies that the current assignment is preserved forever. However, after a finite number of steps, all targets have stayed put at least once, and therefore the distance between each agent and its target decreases by at least 1. This implies that M decreases by at least 1, which is a contradiction with our assumption.

Thus, M never increases and it decreases by at least 1 after a finite number of iterations. Applying this recursively, it follows that M eventually converges to 0, which is equivalent to saying that all targets have been captured.

Corollary 1. If all targets stay put at the same iterations, a chase finishes in at most M0 × l iterations.

Proof. In the previous proof, M decreases for sure at an iteration where all targets stay put. It follows that M converges to 0 after at most M0 × l iterations.

Mixed-Cost Criterion. Minimizing the makespan alone can sometimes lead to a large solution summation cost. This can be alleviated with a mixed-cost criterion, where the makespan is the main component, and ties are broken on the summation cost. The following assignment algorithm handles such a case: 1) Find the minimum weight w such that, after removing all edges with a larger weight than w, there still exists one perfect match; 2) Find the minimum weight bipartite match in the map after removing all edges with a larger weight than w.

The time complexity for step 1 is O(n2.5 logn), as discussed in the case of the makespan cost. For step 2, the complexity is the same as for the summation cost. Thus, step 2 dominates the complexity, and the overall complexity is the same as for the summation cost.

Theorem 3. With the mixed cost in use, a chase terminates, reaching a state where all targets are captured.

Proof. Given P1 = (M1, S1) and P2 = (M2, S2), we say that P1 < P2 if M1 < M2 or (M1 = M2 and S1 < S2). Let P = (M, S) be the initial mixed cost, with M being the makespan and S the summation cost. P never increases from an iteration to the next, as each agent chases its assigned target. P never increases at a re-assignment, as every new assignment minimizes P . P strictly decreases every time when a target stays put, as at least S decreases. Hence P converges to (0, 0) after a finite number of iterations.

Corollary 1 applies to the mixed-cost case as well, providing an M0 × l upper bound to the number of iterations. We omit the proof due to space limitations.

6 Static Assignment Error

If new assignments are computed at every iteration, the active assignment will always be statically optimal. However, if an assignment is kept active for a number of iterations, for computational time savings, an error might accumulate as compared to a statically optimal assignment. We analyse this formally, deriving upper bounds for such errors.

Recall that the time is discretized into iterations. We assume that t = 0 is the time at the beginning of the first iteration. Given a time t, let dt (i, j) be the distance on the map from agent i to target j.

In the rest of this section we focus on the static error for the summation cost, and the static error for the makespan cost.

Definition 1. At a given time t, the summation static error of an assignment f is Es(f) = ∑a∈A(dt (a, f(a)) - dt (a, f ∗ (a))), where f ∗ is a statically optimal assignment for the summation cost at time t.

Theorem 4. Within a given iteration, if ℓ out of |A| targets move, the summation static error of the active assignment f cannot increase by more than 2ℓ.

We omit the proofs to Theorems 4 and 5 to save space.

Corollary 2. Consider a statically optimal assignment f at a starting time 0. If f remains active in the next p iterations, Es(f) ≤ 2p|A| after p iterations.

Figure 2 shows an example. At iteration k, the active assignment (A1, T1), (A2, T2) is statically optimal with respect to the summation cost. However, at iteration k + 1, its summation cost is 4 + 4 = 8, whereas the the assignment (A1, T2), (A2, T1) has a summation cost of 2 + 2 = 4.

The static error of the initial assignment is 8 - 4 = 4. According to Theorem 4, the maximum error at one iteration is 2ℓ = 2 × 2 = 4. Thus, our example shows a worst-case scenario in terms of the static error for the summation cost.

Definition 2. At a given time t, the makespan static error of an assignment f is Em(f) = maxa∈A dt (a, f(a)) - maxa∈A dt (a, f ∗ (a)), where f ∗ is a statically optimal assignment for the makespan cost at time t.

Theorem 5. The makespan static error of an active assignment f cannot increase at one iteration by more than 2.

Corollary 3. With the makespan cost in use, consider a statically optimal assignment f at a starting time 0. If f remains active in the next p iterations, the makespan static error Em(f) after p iterations is bounded by 2p.

Consider again the example in Figure 2. At iteration k, the active assignment (A1, T1), (A2, T2) is statically optimal makespan-wise. However, at iteration k + 1, its makespan is max(4, 4) = 4, whereas the assignment (A1, T2), (A2, T1) has a makespan of max(2, 2) = 2. The static error of the initial assignment is 4 - 2 = 2. According to Theorem 5, the maximum error at one iteration is 2. Thus, our example shows a worst-case static error for the makespan.

7 Experimental Results

We evaluate four agent strategies. The DIS strategy performs assignments based on the summation cost. MKS and MIX are based on the makespan cost and the mixed-cost criterion, respectively. The fourth strategy, GDY, is a baseline, greedy approach that iterates through the set of agents and assigns to an agent the closest target not yet assigned.

We implemented three target strategies. TrailMax [Moldenhauer and Sturtevant, 2009a] aims at planning a path for the target that will provably not intersect with a given agent's path for k time steps, where k is a parameter. We use k = 50. The Escape strategy maximizes the minimum distance to any agent. Naive is a baseline, random walking strategy.

Experiments use maps from Sturtevant's [2012] repository: AR0603SR, from Baldur's Gate (BG), with 13,764 nodes; AR0703SR (BG, 51,585 nodes); orz100d (Dragon Age: Origins - DAO, 99,626 nodes); orz900d (DAO, 96,603 nodes); deadwaterdrop (Warcraft III - WC3, 76,028 nodes); and darkforest (WC3, 99,758 nodes).

Besides the agent strategies, target strategies and maps described earlier, we have implemented an optimal agent strategy and an optimal target strategy, which we evaluate on 2 small maps where such optimal strategies are practical.

Following the approach of Sun et al. [2012], maps are considered to be 4-connected. Unless said otherwise, numbers shown in figures and tables are averages over 100 instances with initial agent and target locations picked at random.

Evaluating the Agent and the Target Strategies. Figure 3 compares the 4 agent strategies in combination with the three target strategies. To save room, we show results for a representative subset of data, with three maps and with assignments computed at every iteration.

The main conclusions, shown next, are consistent across all maps. MIX combines strengths from both DIS and MKS, and this helps MIX be the best strategy in terms of iterations (Figure 3, bottom). In terms of number of steps, MIX and DIS have a good performance, being close to each other and significantly better than MKS and GDY (Figure 3, top).

We conclude that MIX is overall the best, which is why our subsequent analysis focuses more on MIX. DIS has a good performance as well, whereas MKS is weaker. In terms of number of agent steps, MKS is even outperformed by GDY.

Figure 3 shows that, among the target strategies, TrailMax performs the best, resulting in more iterations and agent steps as compared to Escape (2nd place) and Naive (3rd place). To our knowledge, TrailMax has not been tested in multi-agent scenarios before. Our results confirm that TrailMax is a stateof-the-art target strategy in multi-agent chases too.

Sensitivity to the Re-assignment Gap. By definition, the re-assignment gap is the number g with the property that a new assignment is re-computed at every g-th iteration. E.g., when g = 1 an assignment is computed at every iteration. We have varied g in the range R = {1, 2, 4, 8, 16, 32, 64, 128,∞}. For ∞, no assignment is computed except for the initial one.

Table 1 summarizes the results for MIX. The number-ofsteps values are computed as 100 × (M - m)/M, where M = maxg∈R S(g), m = ming∈R S(g), and S(g) is the number of steps with the re-assignment gap g in use. The number-of-iterations numbers are computed similarly.

The results show that, when using MIX, the quality of solutions is stable when varying g. The number-of-steps values range from as little as 0.34% to 11.69%. The number-ofiterations values range from 2.64% to 12.48%. A majority of the numbers shown in the table are smaller than 5%.

In the next section we present an additional comparison of a few gap values on a range of numbers of agents and targets.

Scalability to Large Instances. For a scalability analysis, we vary the number of agents and the number of targets from 10 to 200 in increments of 10. We measure the CPU time to compute agent moves, the number of steps in a solution (summation cost) and the number of iterations (makespan).

We focus on MIX, the best agent strategy, and TrailMax, the best target strategy and thus the most difficult opponent of MIX. We considered three gaps g: 1, 10 and ∞. MIX with gap 1 is up to 8.94 times slower than with gap 10. It has no benefits in terms of number of iterations, and the benefits on the number of steps are small, ranging from -1% to 7.92%. Thus, gap 10 works well in comparison to gap 1, and we skip gap 1 from this analysis, to save room and avoid clutter.

Figure 4 shows the performance on darkforest, the largest map used. Other maps show a similar behavior. Instances are solved very fast. For the largest instances (200x200), the average solving time ranges from 0.08 seconds (map deadwaterdrop) to 0.13 seconds (maps orz100d and orz900d) when g = ∞; and from 0.57 seconds (map darkforest) to 1.08 seconds (map orz900d) when g = 10.

On the other hand, previous work does not scale beyond small instances. Even Vieira et al.'s work [2009], which is suboptimal and somewhat more scalable than optimal centralized minimax, needs to perform n × n one-chase-one minimax searches before it starts performing any action. However, even one single one-chase-one minimax search is impractical on maps of a reasonable size, such as our benchmark maps. Their reported tests have up to 9 units (6 agents, 3 targets) on graphs with up to 16 nodes. Furthermore, Moldenhauer and Sturtevant [2009b] showed that a state-of-the-art minimax search for the basic 1-chase-1 case requires in the order of 1 million to over 10 million node expansions on a map as small as 1600 nodes.

In contrast, our maps are much larger, with up to nearly 100,000 nodes, and we have many more agents. Yet, our method solves such large problems within the order of 1 second or less. These results show an substantial boost in speed and scalability in comparison to previous work. To achieve such a scalability, we give away solution optimality. See an analysis of solution quality later in this section.

Figure 4 illustrates the trade-off between the computational time (left) and the solution quality (number of steps at the center and number of iterations at the right). Performing no re-assignments is faster, and it has a very small impact on the number of steps. The variation in the number of iterations is also reasonably small, not exceeding 14.74% in Figure 4 (right). Thus, if speed is more important and a moderate increase in the number of iterations is acceptable, use no reassignments. Otherwise, perform re-assignments, which still allows to solve problems within the order of 1 second or less.

Comparison to a Minimax Solver. We have compared MIX to an optimal minimax solver on small instances where minimax search is feasible. The purpose of this experiment is evaluating the quality of solutions computed with MIX. We used 2 × 2 chases on two maps, one with 10 nodes, with a topology inspired from Vieira et al. [2009], and one with 28 nodes (called the "ijcai" map), which to our knowledge is created by Sturtevant. On each map, we solve 50 randomlygenerated instances. On such small maps, MIX results are identical for g = 1, 10,∞.

In a minimax search, agents minimize the number of iterations, and targets maximize it. A minimax search provides the number of iterations when both agents and targets play optimally. In addition, we use minimax search to build an optimal target policy in response to MIX agent moves.

Table 2 shows that MIX produces good-quality solutions, only about 2 iterations longer than optimal in average.

Beyond n × n Scenarios. To show that the system can handle "uneven" cases with m ̸= n, we considered cases with n0 = 2m, where m is the number of agents, n0 is the initial number of targets, and m varies from 10 to 100 in increments of 10. At any given point in time, an agent is assigned to exactly one target, unless the remaining number of targets n is smaller than m. In the latter case, each remaining target is assigned one agent. Initially, half of the targets (selected at random) are assigned to agents and the other half remain unassigned. When a target is captured, one unassigned target (selected at random), if any is left, changes its status into assigned, and a re-assignment is performed. An instance finishes when all targets are captured. As shown in Table 3, the system scales well in uneven scenarios as well.

8 Conclusion and FutureWork

We have introduced a fast and scalable approach to moving target search with multiple agents and multiple targets. We have presented a thorough empirical evaluation and a theoretical analysis. Trading optimality for scalability, our system shows a strong speed and scalability performance. While previous techniques are impractical even for moderate-size problems, our method solves large instances on real game maps with hundreds of agents within the order of 1 second or less. On small instances, where a comparison to minimax search is possible, we find that our system produces solutions of a good quality. In future work, we plan to address problems with physical constraints such as velocity and size constraints.