The setting is Multi-Agent Path Finding (MAPF), where multiple agents must move collision-free through a shared graph from given starts to given goals. A conventional MAPF solution assigns paths whose execution requires each agent to be at particular locations at particular timesteps. That requirement is unrealistic for physical robots because hardware, communication, kinematic constraints, and wheel slippage can cause delays. A Temporal Plan Graph converts the time-dependent solution into precedence dependencies, while a Bidirectional Temporal Plan Graph relaxes some inter-agent precedence constraints into bidirectional pairs, allowing either agent to pass first when doing so is safe.
The central contribution is BTPG-max, which addresses non-deadlock cycle types that the earlier BTPG-o method can miss. The paper develops a characterization of possible non-deadlock cycles in a BTPG and uses it to distinguish cycles that can actually cause a reachable deadlock from cycles that cannot. Based on this analysis, BTPG-max adds bidirectional pairs whenever the additional reverse dependency does not introduce a reachable deadlock cycle. The resulting construction is locally maximal: after the algorithm finishes, no further bidirectional pair can be added under its construction criterion. Empirically, the method finds substantially more pairs and offers better anytime behavior, although pair count does not always translate directly into the largest execution-time improvement.
The input is a collision-free MAPF solution, which is first converted into a TPG. The algorithm then examines type-2 edges one at a time and tests whether an edge can be converted into a bidirectional pair by adding the opposite direction. As in BTPG-o, a conversion is accepted only if it does not create a deadlock. The key difference is the deadlock test: BTPG-max performs a depth-first search rooted at the edge under consideration and checks only reachable deadlock cycles, using the paper’s reachability analysis and cycle conditions rather than a limited set of hand-crafted exclusions. A vertex is considered unreachable not only when it lies after a deadlock, but also when it depends through type-1 or type-2 edges on another unreachable vertex. The experiments also compare processing with and without grouping because grouping changes the efficiency and outcome of the construction.
The authors use the optimal MAPF solver CBSH2-RTC to produce a solution for each instance, convert that solution into a TPG, and then compare BTPG-o with BTPG-max both with and without grouping. All BTPG construction methods have a ten-minute cutoff. The evaluation covers six benchmark maps, with five to eight agent-count settings per map and ten random instances for each setting. The execution study contains 3,900 simulations, with each instance run using ten random seeds. The delay model is the same as in the cited BTPG-o study: at each non-delayed timestep, 10% of the agents have a 30% chance of being delayed by five timesteps. The reported measures include discovered bidirectional pairs, average and median execution-time improvement, anytime behavior during construction, and pairs actually used in reverse during simulation; the excerpt does not provide every per-map value or the complete improvement formula.
Without grouping, BTPG-max finds more bidirectional pairs than BTPG-o on every reported map and has higher mean improvement. Grouping substantially improves both methods, increasing the number of pairs found and the overall improvement. However, the total number of pairs and execution improvement are not equivalent objectives: with grouping, BTPG-max finds more pairs than BTPG-o on the warehouse map, while BTPG-o has the larger mean improvement there. The paper attributes this discrepancy to edge order and pair utilization. Consequently, a construction may contain more pairs but use fewer of them in simulated execution, so grouping, edge order, and the distinction between discovered and used pairs are important trade-offs. The authors identify online use during execution, better anytime behavior, parallelization, more sophisticated grouping, and incorporation of prior delay knowledge as future directions.
TPG was introduced as a post-processing representation of a MAPF solution for delay-aware execution. Its type-1 edges express within-agent precedence, while type-2 edges express an inter-agent ordering at a conflict location where both paths need to pass. A conventional TPG preserves the original order even when a delay makes that order inconvenient. BTPG relaxes selected type-2 constraints into bidirectional pairs, so the other agent may pass first when the resulting choice is safe. This approach is orthogonal to methods that plan delay-robust MAPF solutions directly, including methods that assume explicit delay bounds or delay probabilities, and to approaches that reduce waiting or type-2 edges during planning.
A MAPF path set alone does not specify a safe and useful response when agents deviate from their planned timings. If agents keep following fixed temporal orders despite delays, they may wait unnecessarily, collide, or enter deadlock. Adding reverse dependencies indiscriminately is also unsafe because combinations of dependencies can create cycles that lead to deadlock. The problem is therefore to maximize execution flexibility by finding as many safe bidirectional pairs as possible while preserving deadlock avoidance. BTPG-o improves on a basic BTPG construction but still misses some cycle types that are not deadlocking.
The algorithm’s safety test is based on reachable deadlock cycles rather than on every syntactic cycle in the graph. Its depth-first search traverses normal type-2 edges and existing bidirectional pairs under conditions intended to preserve the state required for a reachable deadlock. Reachability is propagated through dependency edges, so vertices that depend on an already unreachable vertex are also excluded from future execution. This analysis supports the local-maximality claim: each candidate is tested against the relevant deadlock conditions, and accepted candidates remain in the constructed BTPG.
The study uses CBSH2-RTC with a two-minute limit to determine the maximum agent count tested on each map, then applies BTPG construction with a ten-minute cutoff. It compares BTPG-o, BTPG-max without grouping, and BTPG-max with grouping, and also reports comparisons involving grouping for BTPG-o. The execution simulator uses the specified stochastic five-timestep delays and records both construction-time and execution-time outcomes. The supplied excerpt names the six-map evaluation and its sampling structure but does not list all map names or all raw measurements.
With grouping, BTPG-max consistently finds three to five times as many bidirectional pairs as BTPG-o across all six maps. It has better median improvement on four of the six maps, not all six, showing that pair count is not a sufficient performance metric. Without grouping, it is reported to be strictly better than BTPG-o in pairs found, mean improvement, and anytime performance. The anytime comparison indicates that BTPG-max finds more pairs faster and reaches a higher final count, with most of its pairs found during the first pass over type-2 edges and relatively few added later.
BTPG-max provides a locally maximal construction procedure for bidirectional temporal plan graphs. Its theoretical basis is the identification of non-deadlock cycles and the corresponding test for reachable deadlock cycles. The reported experiments support the claim that it exposes more bidirectional execution choices than BTPG-o and can improve delay-aware execution, especially when combined with grouping. The evidence supports these conclusions for the stated benchmark maps, solver, cutoff settings, and delay model.
Local maximality does not mean global optimality for execution time, nor does it guarantee the greatest possible improvement under every delay pattern. The usefulness of a discovered pair depends on whether it is actually reversed during execution, and the result depends on edge order and grouping. The evaluation uses six benchmark maps and one specified stochastic delay model; the excerpt does not establish generalization to other map families, robot dynamics, communication regimes, or real hardware. The method is described as a pre-execution post-processing technique, while online operation remains future work. The supplied text also omits the complete proof details, full pseudocode context, complete numerical tables, and some implementation specifics.
The work targets a practical gap between idealized MAPF timing and the irregular execution of real multi-robot systems. It shows that additional flexibility can be obtained by post-processing an existing MAPF solution rather than replacing the planner, while still checking for deadlock. Because the method is described as orthogonal to several delay-robust planning approaches, it could be layered on top of solutions that already account for delay bounds, probabilities, waiting, or type-2 structure. Its distinction between the number of available pairs and the number actually used also highlights an important evaluation issue for flexible execution policies.
This paper is recommended for researchers working on MAPF execution, TPG or BTPG representations, delay-aware coordination, deadlock analysis, and anytime planning or post-processing. It is especially relevant to readers interested in converting fixed passage orders into safe bidirectional choices. Readers seeking exact reproduction should consult the complete paper because the supplied excerpt does not establish every theorem detail, formula, map identity, raw measurement, or implementation condition.