EUVIMEDEUVIMED entdecken
Crossref

Optimal Path Planning in Hostile Environments

Andrzej Kaczmarczyk, Šimon Schierreich, Nicholas Axel Tanujaya, Haifeng Xu

Proceedings of the International Conference on Automated Planning and Scheduling · 08.06.2026 · 36 (1) · 123-132

DOI: 10.1609/icaps.v36i1.42821 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 08.06.2026. Verfasst von Andrzej Kaczmarczyk und 3 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Kaczmarczyk, A., Schierreich, Š., Tanujaya, N. A., & Xu, H. (2026). Optimal Path Planning in Hostile Environments. Proceedings of the International Conference on Automated Planning and Scheduling, 36(1), 123-132. https://doi.org/10.1609/icaps.v36i1.42821

Vancouver

Kaczmarczyk A, Schierreich Š, Tanujaya NA, Xu H. Optimal Path Planning in Hostile Environments. Proceedings of the International Conference on Automated Planning and Scheduling. 2026;36(1):123-132. doi:10.1609/icaps.v36i1.42821

BibTeX
@article{Kaczmarczyk2026,
  author = {Kaczmarczyk, Andrzej and Schierreich, Šimon and Tanujaya, Nicholas Axel and Xu, Haifeng},
  title = {Optimal Path Planning in Hostile Environments},
  journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
  year = {2026},
  volume = {36},
  number = {1},
  pages = {123--132},
  doi = {10.1609/icaps.v36i1.42821}
}
Kostenlos starten →