Cooperative Pathfinding

TLDR

Cooperative Pathfinding is a multi‑agent path planning problem requiring agents to find non‑colliding routes to separate destinations with full knowledge of others, and it is often addressed by decoupled approaches that break the problem into single‑agent searches. The paper introduces three new algorithms for efficiently solving Cooperative Pathfinding, targeting Real‑Time Strategy games and other real‑time settings. The authors propose Cooperative A*, Hierarchical Cooperative A*, and Windowed Hierarchical Cooperative A*, which search space‑time, use an abstract heuristic, and limit search depth to a dynamic window, respectively, and evaluate them on challenging maze‑like environments against the industry standard A* with Local Repair. The results show that the new algorithms, especially WHCA*, are robust and efficient solutions to the Cooperative Pathfinding problem, finding more successful routes and following better paths than Local Repair A*.

Abstract

Cooperative Pathfinding is a multi-agent path planning problem where agents must find non-colliding routes to separate destinations, given full information about the routes of other agents. This paper presents three new algorithms for efficiently solving this problem, suitable for use in Real-Time Strategy games and other real-time environments. The algorithms are decoupled approaches that break down the problem into a series of single-agent searches. Cooperative A* (CA*) searches space-time for a non-colliding route. Hierarchical Cooperative A* (HCA*) uses an abstract heuristic to boost performance. Finally, Windowed Hierarchical Cooperative A* (WHCA*) limits the space-time search depth to a dynamic window, spreading computation over the duration of the route. The algorithms are applied to a series of challenging, maze-like environments, and compared to A* with Local Repair (the current video-games industry standard). The results show that the new algorithms, especially WHCA*, are robust and efficient solutions to the Cooperative Pathfinding problem, finding more successful routes and following better paths than Local Repair A*