TL;DR
This paper introduces a novel, scalable approach to the complex problem of multiple agents chasing multiple moving targets. By dynamically assigning agents to targets and leveraging pre-computed path information, their method significantly outperforms previous computationally expensive minimax approaches, achieving near real-time performance on large-scale scenarios.
What Problem Does This Paper Address?
Imagine a scenario like a video game where multiple player-controlled characters (agents) need to simultaneously track and capture several non-player characters (targets) that are also moving. This is the "multiple agents, multiple targets" (MAMTS) problem, a challenging variant of the classic Moving Target Search (MTS). Existing solutions often rely on "minimax searches," which are powerful for finding optimal strategies but become computationally infeasible very quickly as the number of agents, targets, or the size of the environment increases. This limitation makes them impractical for real-world applications like complex games or even robotic coordination in large spaces. The paper aims to bridge this gap by developing a method that is both scalable to large numbers of agents and targets and still provides good quality solutions.
Methods
The core of the paper's contribution lies in its sub-optimal but scalable approach. Instead of attempting a full, computationally intensive minimax search over the entire state space, their method breaks down the problem:
- Dynamic Agent-Target Assignment: The algorithm assigns individual agents to individual targets. Crucially, this assignment isn't fixed; it can be re-computed dynamically throughout the chase. This allows agents to adapt to changing target positions and potentially re-assign to different targets if it leads to a better outcome.
- Statically Optimal Assignments: When an assignment is computed, it's based on the current positions of agents and targets, not their future predicted movements. This simplification avoids complex lookahead and allows the use of classical assignment algorithms (like those for minimizing summation cost or makespan). The paper explores three assignment criteria:
- Summation Cost: Minimizing the total distance traveled by all agents.
- Makespan: Minimizing the time it takes for the last target to be captured.
- Mixed-Cost: A combination, prioritizing makespan and using summation cost to break ties.
- Leveraging Pre-computed Paths: For the actual movement of each agent towards its assigned target, the system uses a state-of-the-art technique involving compressed path databases. This allows agents to fetch their next optimal move very quickly without re-computing paths from scratch at each step.
The key innovation is the trade-off: sacrificing perfect optimality for massive gains in computational speed and scalability. The frequency of re-assigning agents to targets is also analyzed as a parameter affecting this trade-off.
Datasets
The paper evaluates its approach on a collection of grid maps from Sturtevant's repository [Sturtevant, 2012]. These maps are derived from popular video games like Baldur's Gate, Dragon Age: Origins, and Warcraft III, offering realistic and challenging environments. The maps vary in size, with the largest having nearly 100,000 nodes. The experiments also involve randomly generated initial positions for agents and targets on these maps.
Key Insights and Ideas
- Decomposition is Key: Breaking down the complex MAMTS problem into independent single-agent, single-target chases, guided by a dynamic assignment strategy, is the fundamental enabler of scalability.
- Assignment Strategy Matters: The choice of assignment criterion (summation cost, makespan, or mixed) significantly impacts the solution quality and the nature of the chase. Makespan is crucial for time-sensitive applications, while summation cost is relevant for resource efficiency.
- Re-assignment Frequency is a Tunable Parameter: The trade-off between computational cost and solution quality can be managed by adjusting how often agent-target assignments are re-computed. Performing assignments less frequently saves computation but might lead to slightly longer chases.
- Pre-computation Pays Off: Utilizing compressed path databases for individual chases dramatically speeds up the agent movement phase, making the overall system efficient.
Key Results
- Scalability: The proposed approach scales remarkably well, capable of solving instances with up to 200 agents and 200 targets on maps with nearly 100,000 nodes in under a second. This is a stark contrast to previous methods that struggle with much smaller problem sizes.
- Speed: The algorithm achieves near real-time performance, solving large instances in the order of one second or even fractions of a second.
- Solution Quality: While sub-optimal compared to theoretical minimax solutions, the quality is good. On small instances where comparison was possible, the sub-optimality was no larger than 12.84% on average. The MIX agent strategy (combining makespan and summation cost) was found to be the best overall.
- Target Strategy Performance: The "TrailMax" target strategy proved to be the most challenging opponent, leading to more iterations and agent steps, confirming its effectiveness.
Limitations and Future Work
- Sub-optimality: The primary limitation is that the approach is sub-optimal by design, trading perfect solutions for speed. The paper quantifies this sub-optimality in terms of static errors and solution quality metrics.
- Static Environments: The current approach assumes static environments (maps). Future work could extend this to dynamic environments where the map itself changes.
- Physical Constraints: The authors explicitly mention future work involving problems with physical constraints such as agent/target velocity and size, which would add further complexity.
- Agent Collisions: While the paper assumes agents can pass through each other, handling strict collision avoidance would be a valuable extension.
Summary updated