Accelerating Multi-Agent Planning Using Graph Transformers with Bounded Suboptimality
Conflict-Based Search is one of the most popular methods for multi-agent path finding. Though it is complete and optimal, it does not scale well. Recent works have been proposed to accelerate it by introducing various heuristics. However, whether these heuristics can apply to non-grid-based problem settings while maintaining their effectiveness remains an open question. In this work, we find that the answer is prone to be no. To this end, we propose a learning-based component, i.e., the Graph Transformer, as a heuristic function to accelerate the planning. The proposed method is provably complete and bounded-suboptimal with any desired factor. We conduct extensive experiments on two environments with dense graphs. Results show that the proposed Graph Transformer can be trained in problem instances with relatively few agents and generalizes well to a larger number of agents, while achieving better performance than state-of-the-art methods.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Agent Path FindingOpen-Ended Question AnsweringMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Fast and scalable retrosynthetic planning with a transformer neural network and speculative beam search
AI-based computer-aided synthesis planning (CASP) systems are in demand as components of AI-driven drug discovery workflows. However, the high latency of such CASP systems limits their utility for high-throughput synthes…
Single-step retrosynthesisDrug DiscoveryAccelerating Search-Based Planning for Multi-Robot Manipulation by Leveraging Online-Generated Experiences
An exciting frontier in robotic manipulation is the use of multiple arms at once. However, planning concurrent motions is a challenging task using current methods. The high-dimensional composite state space renders many …
Motion PlanningMulti-Agent Path FindingRobot ManipulationAdjust Planning Strategies to Accommodate Reinforcement Learning Agents
In agent control issues, the idea of combining reinforcement learning and planning has attracted much attention. Two methods focus on micro and macro action respectively. Their advantages would show together if there is …
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Graph Based Deep Reinforcement Learning Aided by Transformers for Multi-Agent Cooperation
Mission planning for a fleet of cooperative autonomous drones in applications that involve serving distributed target points, such as disaster response, environmental monitoring, and surveillance, is challenging, especia…
Deep Reinforcement LearningDisaster Responsegraph constructionNeurosymbolic Transformers for Multi-Agent Communication
We study the problem of inferring communication structures that can solve cooperative multi-agent planning problems while minimizing the amount of communication. We quantify the amount of communication as the maximum deg…