MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding
In multi-agent applications such as surveillance and logistics, fleets of mobile agents are often expected to coordinate and safely visit a large number of goal locations as efficiently as possible. The multi-agent planning problem in these applications involves allocating and sequencing goals for each agent while simultaneously producing conflict-free paths for the agents. In this article, we introduce a new algorithm called MS* which computes an optimal solution for this multi-agent problem by fusing and advancing state of the art solvers for multi-agent path finding (MAPF) and multiple travelling salesman problem (mTSP). MS* leverages our prior subdimensional expansion approach for MAPF and embeds the mTSP solvers to optimally allocate and sequence goals for agents. Numerical results show that our new algorithm can solve the multi-agent problem with 20 agents and 50 goals in a minute of CPU time on a standard laptop.
Code (0)
등록된 구현이 없습니다.
Tasks
CPUMulti-Agent Path FindingSimilar Papers 제목 키워드 기반
Multi-Agent Filtering with Infinitely Nested Beliefs
In partially observable worlds with many agents, nested beliefs are formed when agents simultaneously reason about the unknown state of the world and the beliefs of the other agents. The multi-agent filtering problem is …
DNQ: Deep Nash Q-Network for Partially Observable n-Player Games
Many real-world competitive systems require multiple decision-makers to act simultaneously under shared constraints, limited information, and repeated interaction, as in auctions, resource allocation, and security compet…
Exact Learning of Arithmetic with Differentiable Agents
We explore the possibility of exact algorithmic learning with gradient-based methods and introduce a differentiable framework capable of strong length generalization on arithmetic tasks. Our approach centers on Different…
Structured Cooperative Multi-Agent Reinforcement Learning: a Bayesian Network Perspective
The empirical success of multi-agent reinforcement learning (MARL) has motivated the search for more efficient and scalable algorithms for large scale multi-agent systems. However, existing state-of-the-art algorithms do…
Multi-agent Reinforcement LearningExact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures
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 …