Optimal Path Planning in Hostile Environments
Authors
Kaczmarczyk, A.; Schierreich, Š.; Tanujaya, N.A.; Xu, H.
Year
2026
Published
Proceedings of the 36th International Conference on Automated Planning and Scheduling. Menlo Park, California: AAAI Press, 2026. p. 123-132. vol. 36. ISSN 2334-0835. ISBN 978-1-57735-910-4.
Type
Proceedings paper
Departments
Annotation
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.
Project Submission Games in Participatory Budgeting
Authors
Faliszewski, P.; Janeczko, Ł.; Kaczmarczyk, A.; Lisowki, G.; Pierczyński, G.
Year
2026
Published
Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems. County of Richland: IFAAMAS, 2026. p. 1229-1237. ISBN 979-8-4007-2317-9.
Type
Proceedings paper
Departments
Annotation
We introduce the framework of project submission games, capturing the behavior of project proposers in participatory budgeting (and multiwinner elections). Here, each proposer submits a subset of project proposals, aiming at maximizing the total cost of those that get funded. We focus on finding conditions under which pure Nash equilibria exist in our games, and on the complexity of checking whether they exist. We also seek algorithms for computing best responses for the proposers. Finally, we check the existence of equilibria, as well as their properties, in real-life data.