A* search is used to find the shortest path for each agent to reach its destination, but this search ignores the presence of other agents or may treat them as fixed obstacles. During the movement, if the agent detects that a collision is about to occur, the relevant agent will search again and select a new path. Cooperative pathfinding attempts to allow agents to understand each other's intentions. In cooperative pathfinding, A* search is still used, but the movement of other agents is taken into consideration.
This article assumes that you are familiar with the basic ideas and terminology of the A* search algorithm.
01 Add the third dimension
In order to solve cooperative pathfinding problems, search algorithms need to fully understand the obstacles and agents. When the agent moves around, it is impossible to represent the agent's route over time on a two-dimensional map. To overcome this problem, David Silver expanded the third dimension of the map: time, and called the new expanded map a space-time map. The space-time diagram consists of a three-dimensional grid of cells: Cell(x, y, t). In the space-time diagram, assuming that the time cost of executing a single action is 1, the upward movement is equivalent to moving an agent from Cell(x, y, t) to Cell(x, y + 1, t + 1). Similarly, the action of waiting moves an agent from Cell(x, y, t) to Cell(x, y, t + 1). The action is feasible if the target location is free of obstacles and not occupied by other agents. Now continue to use A* search on the space-time graph, using the number of actions required to reach the goal position as the cost of the path. The goal is to find the minimum cost path for the agent from the current point to its goal position. David Silver calls this search process space-time A* (space-time A*) to distinguish it from general A* search.
02 Construct a reservation table
After an agent selects a path, it needs to ensure that other agents can avoid the cells on its path when searching for a path. This constraint can be satisfied by constructing a reservation table that reveals whether each cell is available. The reservation table is a simple data structure that contains an entry for each cell in the spatiotemporal diagram, which specifies whether the corresponding cell is available or reserved. The number of cells in a spatio-temporal diagram is usually large, but the number of reserved entries at each time step should be roughly equal to the number of agents in the diagram. Many cells are unoccupied at most time steps. Directly storing the status of each cell (available/occupied) will cause a lot of waste of space. In order to optimize space usage, occupied space-time cells can be stored in a hash table: use (x, y, t) as the key of the hash table to represent the state of a specific cell at a certain moment. If a cell is not occupied at a particular time step, then it does not need to be recorded in the hash table. Once a cell is reserved, no other agent can move into that cell. The agent uses A* to search for a path in the spatio-temporal diagram. After finding the path to the target location, the path is marked in the reservation table. When subsequent path finding, the agent will avoid all cells that have been reserved, thus ensuring that conflicts between multiple agents occupying the same cell at the same time will not occur (as shown in Figure 1).
In addition, possible edge conflicts need to be avoided. For example, if an agent's path reserves Cell(x, y, t) and Cell(x + 1, y, t + 1), other agents need to be prevented from reserving Cell(x + 1, y, t) and Cell(x, y, t + 1) when planning the path. The first solution is to reserve two time steps for each position involved in the action, one at time t and one at time t+1; the second solution is to clearly identify edge conflicts and mark them as infeasible actions when planning the path.
03 Select heuristic function
The performance of A* search depends on the choice of the heuristic function. When the estimated distance of the heuristic function is less than or equal to the true distance from the point to the target location, A* search is guaranteed to find the shortest path. The closer the estimated distance of the heuristic function is to the true distance, the faster the search speed. In space-time A*, as the search space expands an additional dimension, the choice of heuristic function becomes more important. Grid-based maps often use the Manhattan distance as a heuristic function, which is the sum of the Δx and Δy distances to the target location. If the shortest path to the target location is circuitous, then the Manhattan distance is a poor estimate of the true distance. When Manhattan distance is chosen as the heuristic function, the value of f at many locations on the space-time graph may be smaller than the true distance to the target location. The smaller the value estimated by the heuristic function, the more cells the algorithm will traverse, resulting in a slower search speed. Therefore, a more accurate heuristic function needs to be selected.
During the A* search process, once a node is placed in the close list, the shortest distance from the starting point to the node is known, and this distance is g. In order to more effectively estimate the true distance from a certain point in space-time A* to the target position, a backward search method can be used: with the target position as the starting point and the source position as the end point, only static obstacles in the map are considered, and A* is used to search for the shortest path from the target position to the source position in the two-dimensional map. After the search is completed, for those points added to the close list, the shortest distance from the target position to the position to avoid static obstacles is known. In other words, the g value of each node in the close list is exactly the true distance from that point to the target location on the two-dimensional map. After a backward search is completed, it may not be possible to obtain the true distance from all points on the map to the target location. If necessary, you can continue to use A* to search backward until the required points are searched. The distance obtained using backward search is closer to the real distance to the target position on the space-time diagram. We use this distance as the h value of A* search to improve search efficiency.
Based on the above, two searches are run in parallel in space-time A*. The main search is the search process of space-time A* to find the shortest path from the agent's current position to the target position, and the auxiliary search is the backward search process of A* from the agent's target position to the current position. The primary search requires a heuristic estimate of the true distance when exploring each location, and a secondary search is used to obtain this estimate. If the current position explored by the main search is in the close list of the auxiliary search, its g value is returned immediately; if it is not in the close list, the search continues backward until the requested position is placed in the close list and its g value is returned.
04 Agents that handle different mobile behaviors
So far, we have assumed that each agent moves at the same speed: in one time step it can perform an action - move one cell left, right, up or down, or wait at the current cell. There is a one-to-one correspondence between the cells contained in the spatiotemporal A* search path and the entries in the reservation table. However, each agent can search space-time in a way that best suits itself. For example, an agent moving at a slow speed needs two time steps to move one cell around, then this agent needs a space-time grid with a longer time step (as shown in Figure 5A); similarly, an agent moving at a faster speed has a shorter time step (as shown in Figure 5B). We can build spatio-temporal grids of different sizes for different agents, but the reservation table has a fixed structure. Each cell corresponding to each entry in the reservation table has a fixed size and is shared among all agents (as shown in Figure 5C).
The footprint of the agent's action determines the set of entries that need to be reserved in the reservation table. For example, a diagonally moving footprint might include a cube of eight cells (as shown in Figure 6A). Large agents will have a wider footprint at each time step (shown in Figure 6B). Slower movements will produce footprints that last for more time steps (shown in Figure 5A). A curved movement will occupy all space-time cells traversed by the movement (as shown in Figure 6C). The granularity of the reservation table can be initialized to any value, depending on routing requirements.
Summary
In the spatiotemporal A* algorithm, by planning time and space in advance, agents can avoid each other's paths and avoid conflicting routes. Many ideas for improving the A* search algorithm can also be applied to spatiotemporal A*, and the added time dimension provides more exploration opportunities for the pathfinding algorithm. It is worth mentioning that the space-time A* algorithm already has a Python-based library. You can use it in Python projects by running "pip install space-time-astar" to install this library.
References
[1] Silver, “Cooperative Pathfinding,” AIIDE, vol. 1, no. 1, pp. 117–122, Sep. 2021, doi: 10.1609/aiide.v1i1.18726.
[2] Space-Time A* algorithm Python library website: https://pypi.org/project/space-time-astar/
Machine-translated from the Chinese original Space-time A* 算法介绍 (published 2024-10-20). WeChat original ↗