Optimal Path Planning in Hostile Environments
This addresses a fundamental planning challenge for coordinating agents like drones or robots in hostile settings, though it is incremental as it builds on existing path planning frameworks.
The paper tackles the problem of multi-agent path planning in hazardous environments where agents can be eliminated by hazards with cooldown periods, aiming to maximize the number of agents reaching a target. It proves the problem is NP-hard even on trees but provides a polynomial-time algorithm for vertex-disjoint paths, establishing a computational landscape with both intractable and tractable fragments.
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.