The Study of Highway for Lifelong Multi-Agent Path Finding

MAPF is an NP-hard problem [16, 17] and is typically solved in one-shot and offline, where each agent has exactly one goal known beforehand and paths of agents are found at once, respectively. The solution of one-shot MAPF solvers is typically evaluated by sum-of-costs (the sum of the arrival times of each agent) or makespan (the time span for all agents to reach their goals).

There are various one-shot MAPF methods [18], including compilation-based solvers [19, 20], rule-based solvers [21, 22], A*-based solvers [23, 24], and prioritized planning [25], etc. Especially, the search-based solvers [26, 6] and their variants are common. Most of the search-based solvers are two-level MAPF solvers. The low-level solver plans the paths for each agent and the high-level solver handles the conflicts of these paths to guarantee no collisions. A* [27] is a typical algorithm as the low-level solver of search-based solvers. As for the high-level solvers, Conflict-Based Search (CBS) [5] is a popular MAPF solver that is complete and optimal, and its variants [6, 28] sacrifice the optimality for faster computation time. Besides, Priority-Based Search (PBS) [29], which solves the conflicts by priority orderings, shows prominent computational efficiency but is incomplete and not optimal.

In contrast to one-shot MAPF, lifelong MAPF solves problems that an agent may be assigned more than one task, which is always accompanied by the online scenario. In online MAPF, the tasks will be generated on the fly during execution [3]. Therefore, the solution can not be planned in advance and should be evaluated by throughput (the number of tasks finished per timestep) because the execution time and the tasks assigned to agents can be endless. For instance, endless tasks come at any time in warehouses, and agents are assigned new tasks after they finished the previous ones. Therefore, the path solver needs to consider the solution constantly in real-time and the problems should be solved as lifelong MAPF. In addition, we should consider not only the throughput but also the runtime (computing time of planning) that makes sure the planning of paths can be completed on time to effectively utilize agents.

Firstly, if all the tasks are known in advance, a lifelong MAPF problem can be solved as a one-shot MAPF problem [10]. Otherwise, the second type of methods [9, 11] replans paths for all the agents at each timestep to handle new tasks on the fly. Nonetheless, these two types of methods are really time-consuming in solving the whole problem offline or constantly replan at each timestep, respectively. Therefore, the third type of method [8] can be followed in that new paths are replanned for the agents which get new goals only, but it still encounters poor throughput without cooperative planning among all agents.

To retain the efficiency of runtime while maximizing the throughput, RHCR [12] incorporated windowed MAPF [4] into lifelong MAPF. The idea is to plan the entire paths to goals and solve conflicts only for the first $w$ timesteps and the $w$ represents the time horizon. In addition to the time horizon $w$, RHCR has another user-specified parameter $h$ that specifies the replanning period. Every $h$ timesteps as an episode, the new goals are assigned to the agents which have reached their goals, and the conflict-free paths in subsequent $w$ timesteps are planned for the future when the agents are following the planning results from the previous episode. After $h$ timesteps pass, agents follow these new conflict-free paths, and the paths for the next episode should be planned. However, due to the incompleteness and the lack of guarantee in the optimality, the windowed MAPF solver encounters deadlocks (i.e., agents idle at their current locations waiting for each other to pass first), which rely on a potential function to evaluate the progress of the agents and $w$ will be increased to address deadlocks [12]. Besides, because windowed MAPF [4] only solves conflicts in the first few timesteps and replans paths constantly, it causes agents to revise their path direction or revisit locations that they had previously visited, which also happens in RHCR [12].

In one-shot MAPF, the highway is an add-on setting on the map to speed up the runtime, which builds a global rule of the moving direction to encourage or enforce MAPF solvers to search paths in a consistent direction. Forbidding agents to move against the highway direction is a simple strategy to reduce computational complexity and avoid collisions. For instance, a one-shot solution [14] used directed maps to reduce the complexity of MAPF for faster computational efficiency. Additionally, another one-shot solution [15] increases the cost on the paths against the highway direction when calculating the heuristic values, which implicitly encourages solvers to explore the path along the highway direction. However, these methods are proposed for one-shot MAPF where undesirable phenomena in lifelong MAPF such as deadlocks and rerouting do not occur. Even if RHCR [12] (a lifelong solution) used directed maps in its experimental section to reduce the planning complexity, it still lacked further discussions and experiments on how highway affects the planning results in lifelong scenarios.

In one-shot MAPF with highways [15], highway was represented as a subgraph $G_{H}=(L_{H},E_{H})$ of the given graph of the map $G=(L,E)$, where $L_{H}$ contained locations involved in the highway and $E_{H}$ represented the edges following the highway direction.

In this work, we focus on warehouse-like maps [30], the highway settings can be defined by specifying the direction of movement for each corridor. A sequence of locations $K=\{l_{0},...,l_{n}\}\subseteq L$ is called a corridor with length $n$ iff $l_{i}$ is connected to exact two locations $l_{i-1}$ and $l_{i+1}$ according to $E$ for $i=1\rightarrow i-1$ (i.e., only one way in and one way out at each location). The $l_{0}$ and $l_{n}$ can be the same location as a loop-corridor. For each corridor, there exists a direction $d\in D$, which is a bool-value representing the direction of the corridor, shown in Fig. 2. Besides, any location as an intersection, which connects two or more corridors, will not belong to any corridors. Finally, given a set of directions $D=\{d_{0},...,d_{m}\}$ (m is the number of corridors), the highway can be represented as a subgraph $G_{H}=(L_{H},E_{H})\subseteq G$ and the edges that against the highway direction $E_{H^{\prime}}=\{(l_{b},l_{a})|(l_{a},l_{b})\in E_{H}\}$.

We follow RHCR [12] as our lifelong MAPF framework. Given user-specified time horizon $w$ and replanning period $h$ ($h\leq w$), the conflict-free paths in the first $w$ timesteps will be planned for agents every $h$ timesteps, and the new goals will be assigned to the agents which have reached their goals. As for the high-level solver, we use PBS [1], which shows prominent computational efficiency with RHCR.

In our method, we use A* as the low-level solver with the true shortest distance heuristic. The shortest-path heuristic values, which ignore dynamic constraints (i.e., moving agents), can be calculated by shortest-path algorithms in advance. In this way, the precise values of the distances between nodes can guide the low-level solver to traverse fewer locations to the goal than the heuristic values of Manhattan distance. Besides, given a highway setting, the calculated heuristic can influence the low-level solver to find paths following the direction of highway, thereby resulting in fewer conflicts, and the complexity of low-level planning is also relaxed because choices to move against the highway direction are trimmed away.

There are two methods to set up the highway for the low-level solver. Firstly, the movement across edges is allowed for only one direction [14], which we call strict-limit highway in this work. The second one is to increase heuristic values only except following the direction of the highway [15] that encourages low-level solvers to search paths along the edges of the highway, which we call soft-limit highway here.

Under the soft-limit highway, the low-level solver is planning with the highway heuristic. Because the path against the highway direction has higher heuristic values, the neighboring locations along the highway direction have higher priority to be taken out from the open-set of A* for the lower expected costs. Hence, the direction of paths found by the low-level solver shows consistency in the direction. The consistency of paths for agents causes fewer face-to-face collisions, which decreases the nodes the high-level solver should generate to solve conflicts. When $c$ is small, the results are close to the ones without the highway. As $c$ increases, the planning results are gradually close to the ones using the shortest paths of the highway as the heuristic values. However, even if $c$ is set to infinity, the movement against the highway direction happens when the locations along the shortest path are blocked by the dynamic obstacle, which shows the flexibility for agents to choose the direction of their movement but may cause conflicts that take time to solve. Using the strict-limit highway, the consistent direction of paths of agents can be guaranteed by blocking the edges to neighboring locations during planning, as shown in Fig. 4.

The purpose of utilizing highway is to ensure the paths of agents can share a collaborative rule locally, which relieves the congestion by solving conflicts as well as keeps the consistency of the planning results in neighboring time horizons. Benefiting from the consistent direction of paths, the strict-limit highway has the following properties addressing the issues of deadlocks and rerouting. Additionally, we show that the soft-limit highway can exploit these properties depending on the given $c$ in our experimental section.

Deadlock is a phenomenon caused by the windowed MAPF without considering the entire time horizon [12]. A deadlock happens when two agents move face-to-face with their goals on opposite sides. With a small $w$, neither they can go directly because of the swapping conflict nor go along the reverse direction because the high-level solver prefers the agents waiting at the original location for less  sum-of-costs instead of taking a longer path. For example, if time horizon ${w=2}$, replanning period ${h=2}$ and CBS is used as the high-level solver, the windowed MAPF solver returns the paths in Fig. 5-(a), which lets agents stay at the location without moving for $w$ timesteps and start to move after that to the goal location. This situation causes by the limited cooperative planning of the windowed MAPF solvers, which only solves the conflicts in the first $w$ timesteps and ignores the conflicts behind that. Hence, the low-level solver is not able to consider the further locations because the sum-of-costs is smaller while waiting at the original location. To make one agent move along the top side and the other move along the bottom side, $w$ should be set to $3$ at least to let the solver consider the further path instead of a cheating solution that waiting across the time horizon to avoid conflicts like in Fig. 5-(b). Worse yet, the bigger value of $w$ should be checked to find the solution if the corridor is longer or the goals are further, which increases the runtime.

Generally, a deadlock happens when the MAPF solver can not find feasible moving paths for agents with lower sum-of-costs compared with paths of waiting. That is, the MAPF solver can not find the new locations for agents in the next $w$ timesteps that have a lower sum of distances to their goals. Given $A_{d}\subseteq A$ represents a subset of agents which may cause a deadlock. An agent $a_{i}\in A_{d}$ asks for $p_{i}=[l^{i}_{c},...,l^{i}_{n}]$ ($|p_{i}|-1=w$, where $w$ is the time horizon), which is a feasible path from its current location $l^{c}_{i}$ to the next location $l^{i}_{n}$ in the next $w$ timesteps without collisions. With the shortest path heuristic values that represent the distances to the goal locations in the strict-limit highway, a situation that a deadlock may happen can be simplified as:

where $l_{g}^{i}$ is the goal location of $a_{i}$.

In strict-limit highway, if an agent $a_{i}$ moves from any location $l^{i}_{a}$ to its neighboring location $l^{i}_{b}$ and $(l^{i}_{a},l^{i}_{b})\in E_{H}$ always, then $H_{S}(l^{i}_{b},l^{i}_{g})=H_{S}(l^{i}_{a},l^{i}_{g})-1$ if $l^{i}_{a}\neq l^{i}_{g}$, where $l^{i}_{g}$ is its goal location. Thus, Eq. (3) can be rewritten as:

where $\bar{p}_{i}$ is the set of unique locations in $p_{i}$, and $|\bar{p}_{i}|$ reflects the number of unique locations in $p_{i}$.

Eq. (4) is not held when $\exists a_{i}\in A_{d},|\bar{p}_{i}|>1$. Namely, in the strict-limit highway, if all agents move along the edges $\in E_{H}$, deadlocks will not happen unless every agent has no available neighboring locations to move to.

Rerouting is a phenomenon that results from the lack of long-term consideration of windowed MAPF [4], which causes agents to revise their path direction or revisit locations that they had previously visited. The idea of the windowed MAPF used in RHCR is to separate the lifelong MAPF problem into a sequence of subproblems by time, which is referred to as episode. In each episode, the low-level solver plans the entire path for each agent, and then the high-level solver solves the conflicts of the paths for the finite time horizon $w$. After planning, each agent follows the path of the first $h$ (smaller than or equal to $w$) timesteps. However, although planning the entire path to the goal, only the partial path in the first $h$ timesteps is followed by each agent. Therefore, each agent may stop at a location whose heuristic value is higher than the original location, namely waiting is a wiser choice rather than moving. Besides, in most search-based MAPF solvers, special mechanisms are followed to determine the priority orderings in high-level planning to decide which agent should go first when a conflict happens (e.g. CBS [5] adds the constraint to the certain agent as a CT-node, and PBS [29] maintains priority ordering pairs). However, the consistency of the priority orderings of agents is not guaranteed in the subsequent high-level planning, and changes in the priority orderings may lead to an obvious difference in the planning results. These cases may ask agents to reroute or even move backward, resulting in longer distances for agents to reach their goals.

We formally defined that an agent $a_{i}$ is rerouting when it is assigned a path $p_{i}=[l_{c}^{i},...,l_{n}^{i}]$ by the MAPF solver that makes $a_{i}$ move away from its goal $l_{g}^{i}$, which can be represented by the shortest path heuristic:

where $l_{c}^{i}$ is the current location of $a_{i}$ and $l_{n}^{i}$ represents the location where $a_{i}$ will arrive after $h$ timesteps ($h$ is the replanning period smaller than or equal to the time horizon $w$). In strict-limit highway, given an agent $a_{i}$ and its goal location $l^{i}_{g}$, $\forall(l_{a},l_{b})\in E_{H}$, $H_{S}(l_{a},l^{i}_{g})=H_{S}(l_{b},l^{i}_{g})+1$ if $l_{a}\neq l^{i}_{g}$. Therefore, when $a_{i}$ moves along the edges $\in E_{H}$, Eq. (5) is not held because $H_{S}(l_{c}^{i},l_{g}^{i})\geq H_{S}(l_{n}^{i},l_{g}^{i})$. In summary, using strict-limit highway, these properties guarantee that there are no deadlocks and rerouting as agents move across the edges that are parts of the highway.

We implement RHCR with $w=5$, $h=5$ using PBS as the lifelong MAPF solver with a standard location-time A* as the low-level solver in Python and ran all experiments on Intel Core i9-9980XE with 16 GB memory. Before each round of experiments, the start locations and goal locations of agents are selected randomly from the different empty locations on the map. When an agent arrives at its goal location, a location that is not the goal location of any other agents will be assigned. Besides, we randomly initialize 100 episodes for each experiment and simulate 100 iterations of planning in each episode. Each iteration has its time limit of 60 seconds, and the episode will be labeled as a fail case if any iteration times out. All metrics shown are calculated as averages which exclude the fail cases.

Generally, throughput and runtime are the two main metrics for lifelong MAPF. For evaluating that highway can effectively deal with existing phenomena of deadlocks and rerouting, moving timesteps, idle timesteps, and rerouting rate are recorded during the experiments. Rerouting rate is the percentage of the agents who reroute in an iteration. Besides, moving timesteps reflects the number of timesteps that an agent moves during a task and idle timesteps is the number of timesteps that an agent stays at the same location without moving during a task. For observing how increasing c influences agents, highway avoidance rate shows the chance that an agent moves against the highway direction. Similar to [5] and [15], generated nodes is used to explain the reason why our method has lower runtime, which is the number of high-level nodes generated by the MAPF solver before finding the solution during one planning.

Given that the heuristic values are calculated from the shortest paths (e.g. strict-limit highway and soft-limit highway with $c=1$ or $\infty$), a trick mentioned in the previous work [4] can be applied to simplify planning. Namely, in windowed MAPF, instead of planning the entire path to the goal, we can directly ignore the planning after $w$ timesteps, which yields the same result but saves the time to plan entire paths. We include this trick in Table II for comparison.

In autonomous warehouses, a set of inventory pods are placed closely into a rectangle block, and the blocks with corridors in between are placed into a grid, like in Fig. 7. In our experiments, we follow the settings of the warehouse map in Fig. 7-(a) [30]: (1) each block contains 10$\times$2 pods, and (2) the corridors are single-rowed. For simplicity, we test maps with N$\times$N blocks, where N is an odd number (i.e., 3, 5, 7, etc.), and inventory pods are considered obstacles for the agents. For instance, the smallest 3$\times$3 version of the maps is shown in Fig. 7-(b). In addition, the percentage of obstacles over the entire map indicates how crowded the map is. Our smallest map (Fig. 7-(b)) has more than 50% of obstacles, and the percentage of obstacles gradually increases as the map grows with the larger N. The high obstacle density and neighboring corridors are suitable for testing highway.

The parameter $c$ in soft-limit highway determines how much the map is influenced by the highway directions. Therefore, we evaluate the influence of highway through the map in Fig. 7-(b) with the increasing $c$ and fixed 5% density of agents (i.e., the ratio of agents to empty locations of the map). Fig. 6 shows the relative throughput, runtime, and generated nodes with the $c\in\{1,1.2,1.5,2,5,10,50,\infty\}$, which are compared to the result of $c=1$.

When the map is small, the value of throughput drops when the value of $c$ rises in Fig. 6-(a), though the runtime decreases slightly in Fig. 6-(b). However, in the case of the larger map, the drop in throughput is much slower, and the drop in runtime is significant as $c$ increases. Surprisingly, the relative throughput when $c=1.5$ even surpasses the throughput without highway. Furthermore, a trend shows that the gap in the throughput between no-highway ($c=1$) and highway ($c=\infty$) narrows as the map size grows larger.

The speedup on the runtime mainly benefits from the more efficient planning under highway, because the global rule of the direction should be followed, and thus planning results are more consistent, which causes fewer conflicts before the solution is found. Referring to Fig. 6, if a higher $c$ is used, fewer nodes should be generated to find a solution, and the benefit is even more pronounced in larger maps.

In Table I, the results verified that using highway resulted in fewer average idle timesteps (timesteps that an agent stays at the same point during a task), which reflects the consistent direction of paths and fewer deadlocks, and the average idle timesteps reduce more when a larger map. Also, through c increases, the chance that an agent moves against the highway direction and the rerouting problem decreases, shown as the highway avoidance rate (the chance of an agent moving against the highway direction) and the rerouting rate (the percentage of the rerouting agents in an iteration of planning) in Table I. Besides, following the highway causes agents to have more moving timesteps (timesteps that an agent needs to arrive at its goal). Nevertheless, using highway in a larger map causes fewer extra moving timesteps, which explains another reason that a larger map can benefit more while using highway. For instance, in Table I, using highway ($c=50$) in the 3x3 map causes 69.1% extra moving timesteps while using highway ($c=50$) in the 7x7 map only causes 23.9% extra moving timesteps.

To ensure the runtime is efficient enough to assign the paths on time without idling the agents, the question is whether the advantages of highway are kept after the map of a warehouse scales up. Referring to the results mentioned previously, the answer is clearly yes. Subsequently, we discuss and quantify the benefits of highway as the map size scales up and the agent density grows larger.