The MG-MAPF problem places multiple agents on an undirected graph with unit-length edges. Each agent may wait or move to an adjacent vertex at every time step, and must visit all of its pre-assigned goals at least once in any order. Agents may not occupy the same vertex at the same time or move along the same edge at the same time, and after completing all visits an agent remains at one of its goal vertices. The objective is to minimize the sum of the individual path costs, where an agent’s cost is the number of time steps needed to complete its goal visits.
The paper first demonstrates that DVS methods, which decouple goal-vertex visiting-order search from single-agent path finding, cannot always guarantee an optimal MG-MAPF solution. It then introduces Multi-Goal Conflict-Based Search, or MGCBS, based on decoupling goal safe-interval visiting-order search from single-agent path finding. A safe interval is used to represent time-dependent availability of a goal under the relevant constraints. The paper also proposes the Time-Interval-Space Forest, which reuses shortest-path information from arbitrary start vertices and start times to goal safe intervals, and presents theoretical arguments for MGCBS optimality and completeness.
MGCBS is a two-level solver. Its high-level component extends Conflict-Based Search by maintaining a constraint tree, selecting a lowest-cost node, detecting conflicts, and generating child nodes by adding constraints for the conflicting agents. Its low-level component uses an A*-based search to find the best safe-interval visiting order and a corresponding path for one agent under the node’s constraints. For each agent, a TIS Forest consists of several Time-Interval-Space Trees, with one tree associated with a particular goal safe interval. These trees provide the shortest path and length from a start vertex at a start time to the associated safe interval, reducing repeated shortest-path queries.
The evaluation uses four-neighbor grid maps and randomly samples starts and goals, while ensuring that different agents have distinct start vertices. The reported efficiency study selects three maps from the MAPF benchmark, ranging from small to large, and generates 100 instances for each tested agent count. It compares HCBS, the current DVS-based state-of-the-art method, MGCBS without the TIS Forest, and full MGCBS; CBS plus A* is used as an optimal reference in the solution-quality evaluation. Efficiency is measured using average runtime and success rate, with a 60-second cutoff, while solution quality is assessed by differing costs and maximum and average relative error against the optimal reference. The supplied excerpt does not provide every experimental parameter, every runtime value, or the complete instance-level data.
The case study and experiments show that separating goal-vertex ordering from single-agent path finding cannot guarantee optimality for MG-MAPF. DSS addresses this limitation by ordering goal safe intervals rather than only vertices, thereby including time-dependent availability in the low-level search. The TIS Forest trades data-structure construction and reconstruction for reuse across many shortest-path queries; related trees must be reconstructed when constraints change. The experiments support the claimed benefit on the tested grid benchmarks, but the excerpt does not establish performance in physical robot deployments, non-grid environments, alternative objectives, different collision models, or memory-limited settings. It also does not specify a concrete future-work agenda in enough detail to infer one.
Multi-agent path finding asks for collision-free paths from agent starts to goals and is relevant to applications such as aircraft towing, video games, and traffic management. MG-MAPF extends this setting by assigning multiple goals to each agent. The paper distinguishes MG-MAPF from related multi-goal settings such as multi-agent pickup and delivery, MAPF with precedence constraints, and simultaneous multi-goal sequencing and path finding, because those problems impose different requirements. Earlier MG-MAPF approaches include HCBS and SMT-HCBS; the paper characterizes HCBS as typically faster because of its heuristic search, while leaving room for improvements in both optimality and efficiency.
The input consists of an undirected unit-edge graph, a set of agents, one start vertex for each agent, and multiple assigned goal vertices for each agent. Agents can wait or move at each time step, and they must visit every assigned goal at least once in an arbitrary order. A vertex conflict occurs when two agents occupy one vertex simultaneously; an edge conflict occurs when they move along the same edge at the same time. The objective is the sum of the completion times of all agents. The need to choose visit orders while respecting time-dependent interactions is the central difficulty addressed by the paper.
A TIS Forest is maintained per agent and contains multiple TIS Trees, each associated with a particular goal safe interval. The structure records shortest paths from time-space states toward a safe interval and can answer queries for different start vertices and start times. The theoretical discussion characterizes the tree construction as a backward version of Dijkstra’s algorithm and explains that states within a TIS state can be expanded together along reverse edges. Because the exact time at which a goal will be reached is unknown beforehand, the structure cannot simply be built using a mechanism analogous to SIPP. The excerpt does not provide implementation-level memory bounds or a complete asymptotic complexity analysis.
The efficiency experiment uses the benchmark maps named maze-32-32-4, lak303d, and orz900d, described in the supplied material as small, medium, and large grid maps. For each tested number of agents, 100 random instances are generated, and a run exceeding 60 seconds is counted as unsuccessful and assigned a runtime of 60 seconds. HCBS, MGCBS without the TIS Forest, and full MGCBS are compared using average runtime and success rate. The solution-quality experiment compares against CBS plus A*, described as an optimal algorithm, and counts differing costs while computing maximum and average relative error. The excerpt omits the full tested agent range and does not reproduce all detailed measurements.
The paper reports that full MGCBS consistently obtains optimal solutions on the successfully solved instances in its evaluation. HCBS produces non-optimal paths on some instances, with a maximum relative error exceeding 17 percent, whereas MGCBS matches the optimal results in the reported comparisons. MGCBS also achieves a maximum speedup of up to seven times over the state-of-the-art DVS-based method. The supplied excerpt contains selected success-rate information but does not establish every average runtime or every result for all map and agent-count combinations.
The study concludes that separating goal-vertex ordering from single-agent path finding is insufficient for optimal MG-MAPF. MGCBS instead searches over goal safe-interval orders while using CBS-style conflict resolution and an A*-based low-level solver. The TIS Forest makes this approach more efficient by reusing shortest paths to safe intervals from many time-space starting states. Within the reported four-neighbor grid evaluation, the method combines the claimed optimality with substantially better runtime than the DVS-based state-of-the-art method.
The evidence provided is concentrated on four-neighbor grid maps, unit-edge graphs, and the sum-of-costs objective, so it does not establish generality to other environments or objectives. The excerpt does not quantify the memory cost of TIS Forest construction, the cost of rebuilding trees after constraints change, or the scaling boundary as the number of agents and goals grows. Randomly generated starts and goals may not represent structured industrial workloads, and the supplied material does not evaluate physical execution, uncertainty, or communication constraints. Although the paper presents optimality and completeness proofs, the excerpt does not give enough detail to independently reconstruct every proof step or to identify a specific future-work program.
The work is important because it identifies a fundamental limitation in a natural decomposition for multi-goal planning: a vertex order can fail to be optimal when temporal availability and inter-agent conflicts are considered. By making safe intervals part of the ordering problem, MGCBS connects goal sequencing with time-dependent feasibility while retaining a CBS architecture. The TIS Forest further shows how an exact solver can reuse repeated shortest-path computations rather than abandoning optimality for speed. This makes the approach relevant to researchers studying exact coordination for fleets with multiple assigned tasks.
This paper is recommended for MAPF and MAPD researchers interested in exact planning for agents that must visit several assigned locations. It is particularly useful for readers studying CBS, safe-interval reasoning, A*-based multi-goal planning, and reuse of single-agent shortest-path queries. Readers focused on real-robot deployment, continuous motion, non-grid graphs, stochastic execution, or strict memory limits should treat the claims cautiously because those settings are not established by the supplied excerpt.