Coordinating agents through hazardous environments, such as aid-delivering drones navigating conflict zones or field robots traversing deployment areas filled with obstacles, poses fundamental planning challenges. We introduce and analyze the computational complexity of a new multi-agent path planning problem that captures this setting. A group of identical agents begins at a common start location and must navigate a graph-based environment to reach a common target. The graph contains hazards that eliminate agents upon contact but then enter a known cooldown period before reactivating. In this discrete-time, fully-observable, deterministic setting, the planning task is to compute a movement schedule that maximizes the number of agents reaching the target. We first prove that, despite the exponentially large space of feasible plans, optimal plans require only polynomially-many steps, establishing membership in NP. We then show that the problem is NP-hard even when the environment graph is a tree. On the positive side, we present a polynomial-time algorithm for graphs consisting of vertex-disjoint paths from start to target. Our results establish a rich computational landscape for this problem, identifying both intractable and tractable fragments.
Figures & tables
Figure 1: An illustration of our problem showing timesteps 0 to 5 , as indicated by . There are two assets, red and blue . The reload time of the single trap r ( ) is c(r)=1 . If the trap is depicted in light gray ( ), then it is inactive in this round.
Figure 2: Illustration of the construction from Theorem 4 . The dark labels by the traps ( ) depict the respective reload times.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 3: Construction of the reduction on trees
Figure 4: Variable Gadget for APX-hardness reduction.
Figure 5: Clause Gadget for APX-hardness reduction.
Figure 6: Construction for showing APX -hardness. The formula for this construction is (X1∨¬X3)∧(X1∨X3)∧(¬X1∨¬X3) . The blue and red lines are used to differentiate positive and negative literals respectively.