Optimal Path Planning in Hostile Environments
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918398208770048 |
|---|---|
| author | Kaczmarczyk, Andrzej Schierreich, Šimon Tanujaya, Nicholas Axel Xu, Haifeng |
| author_facet | Kaczmarczyk, Andrzej Schierreich, Šimon Tanujaya, Nicholas Axel Xu, Haifeng |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_18958 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal Path Planning in Hostile Environments Kaczmarczyk, Andrzej Schierreich, Šimon Tanujaya, Nicholas Axel Xu, Haifeng Computer Science and Game Theory Multiagent Systems 68Q25 (Primary) 90B35 (Secondary) F.2.2; G.2.2 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. |
| title | Optimal Path Planning in Hostile Environments |
| topic | Computer Science and Game Theory Multiagent Systems 68Q25 (Primary) 90B35 (Secondary) F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2603.18958 |