EUVIMEDEUVIMED entdecken
Crossref

Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning

Alexey Skrynnik, Anton Andreychuk, Maria Nesterova, Konstantin Yakovlev, Aleksandr Panov

Proceedings of the AAAI Conference on Artificial Intelligence · 24.03.2024 · 38 (16) · 17541-17549

DOI: 10.1609/aaai.v38i16.29704 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 24.03.2024. Verfasst von Alexey Skrynnik und 4 weiteren Autor:innen. Die Arbeit wurde bisher 41-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Multi-agent Pathfinding (MAPF) problem generally asks to find a set of conflict-free paths for a set of agents confined to a graph and is typically solved in a centralized fashion. Conversely, in this work, we investigate the decentralized MAPF setting, when the central controller that possesses all the information on the agents' locations and goals is absent and the agents have to sequentially decide the actions on their own without having access to the full state of the environment. We focus on the practically important lifelong variant of MAPF, which involves continuously assigning new goals to the agents upon arrival to the previous ones. To address this complex problem, we propose a method that integrates two complementary approaches: planning with heuristic search and reinforcement learning through policy optimization. Planning is utilized to construct and re-plan individual paths. We enhance our planning algorithm with a dedicated technique tailored to avoid congestion and increase the throughput of the system. We employ reinforcement learning to discover the collision avoidance policies that effectively guide the agents along the paths. The policy is implemented as a neural network and is effectively trained without any reward-shaping or external guidance. We evaluate our method on a wide range of setups comparing it to the state-of-the-art solvers. The results show that our method consistently outperforms the learnable competitors, showing higher throughput and better ability to generalize to the maps that were unseen at the training stage. Moreover our solver outperforms a rule-based one in terms of throughput and is an order of magnitude faster than a state-of-the-art search-based solver. The code is available at https://github.com/AIRI-Institute/learn-to-follow.

Zitieren

APA

Skrynnik, A., Andreychuk, A., Nesterova, M., Yakovlev, K., & Panov, A. (2024). Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 38(16), 17541-17549. https://doi.org/10.1609/aaai.v38i16.29704

Vancouver

Skrynnik A, Andreychuk A, Nesterova M, Yakovlev K, Panov A. Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning. Proceedings of the AAAI Conference on Artificial Intelligence. 2024;38(16):17541-17549. doi:10.1609/aaai.v38i16.29704

BibTeX
@article{Skrynnik2024,
  author = {Skrynnik, Alexey and Andreychuk, Anton and Nesterova, Maria and Yakovlev, Konstantin and Panov, Aleksandr},
  title = {Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2024},
  volume = {38},
  number = {16},
  pages = {17541--17549},
  doi = {10.1609/aaai.v38i16.29704}
}
Kostenlos starten →