Solving Multiagent Path Finding on Highly Centralized Networks

2024-12-12 · Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan, Nikolaos Melissinos, Michal Opler, Tung Anh Vu

The Mutliagent Path Finding (MAPF) problem consists of identifying the trajectories that a set of agents should follow inside a given network in order to reach their desired destinations as soon as possible, but without colliding with each other. We aim to minimize the maximum time any agent takes to reach their goal, ensuring optimal path length. In this work, we complement a recent thread of results that aim to systematically study the algorithmic behavior of this problem, through the parameterized complexity point of view. First, we show that MAPF is NP-hard when the given network has a star-like topology (bounded vertex cover number) or is a tree with $11$ leaves. Both of these results fill important gaps in our understanding of the tractability of this problem that were left untreated in the recent work of [Fioravantes et al. Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology. AAAI'24]. Nevertheless, our main contribution is an exact algorithm that scales well as the input grows (FPT) when the topology of the given network is highly centralized (bounded distance to clique). This parameter is significant as it mirrors real-world networks. In such environments, a bunch of central hubs (e.g., processing areas) are connected to only few peripheral nodes.

📄 PDF Abstract BibTeX arXiv:2412.09433

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

SET Dynamic Sparse Training method where weight mask is updated randomly periodically

Applying MAPP Algorithm for Cooperative Path Finding in Urban Environments

2017-07-20 · Anton Andreychuk, Konstantin Yakovlev

The paper considers the problem of planning a set of non-conflict trajectories for the coalition of intelligent agents (mobile robots). Two divergent approaches, e.g. centralized and decentralized, are surveyed and analy…

Combining Propositional Logic Based Decision Diagrams with Decision Making in Urban Systems

2020-11-09 · Jiajing Ling, Kushagra Chandak, Akshat Kumar

Solving multiagent problems can be an uphill task due to uncertainty in the environment, partial observability, and scalability of the problem at hand. Especially in an urban setting, there are more challenges since we a…

Decision Making reinforcement-learning Reinforcement Learning (RL)

Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures

2024-12-11 · Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan, Nikolaos Melissinos 외

Consider the scenario where multiple agents have to move in an optimal way through a network, each one towards their ending position while avoiding collisions. By optimal, we mean as fast as possible, which is evaluated …

Combining Planning and Reinforcement Learning for Solving Relational Multiagent Domains

2025-02-26 · Nikhilesh Prabhakar, Ranveer Singh, Harsha Kokel, Sriraam Natarajan 외

Multiagent Reinforcement Learning (MARL) poses significant challenges due to the exponential growth of state and action spaces and the non-stationary nature of multiagent environments. This results in notable sample inef…

reinforcement-learning Reinforcement Learning

Multiagent Cooperation and Competition with Deep Reinforcement Learning

2015-11-27 · Ardi Tampuu, Tambet Matiisen, Dorian Kodelja, Ilya Kuzovkin 외

Multiagent systems appear in most social, economical, and political situations. In the present work we extend the Deep Q-Learning Network architecture proposed by Google DeepMind to multiagent environments and investigat…

Deep Reinforcement Learning Q-Learning reinforcement-learning Reinforcement Learning+1