Finding Coordinated Paths for Multiple Holonomic Agents in 2-d Polygonal Environment
Avoiding collisions is one of the vital tasks for systems of autonomous mobile agents. We focus on the problem of finding continuous coordinated paths for multiple mobile disc agents in a 2-d environment with polygonal obstacles. The problem is PSPACE-hard, with the state space growing exponentially in the number of agents. Therefore, the state of the art methods include mainly reactive techniques and sampling-based iterative algorithms. We compare the performance of a widely-used reactive method ORCA with three variants of a popular planning algorithm RRT* applied to multi-agent path planning and find that an algorithm combining reactive collision avoidance and RRT* planning, which we call ORCA-RRT* can be used to solve instances that are out of the reach of either of the techniques. We experimentally show that: 1) the reactive part of the algorithm can efficiently solve many multi-agent path finding problems involving large number of agents, for which RRT* algorithm is often unable to find a solution in limited time and 2) the planning component of the algorithm is able to solve many instances containing local minima, where reactive techniques typically fail.
Code (0)
등록된 구현이 없습니다.
Tasks
Collision AvoidanceMulti-Agent Path FindingSimilar Papers 제목 키워드 기반
Hybrid Control Barrier Functions for Nonholonomic Multi-Agent Systems
This paper addresses the problem of guaranteeing safety of multiple coordinated agents moving in dynamic environments. It has recently been shown that this problem can be efficiently solved through the notion of Control …
Whole-Body Control on Non-holonomic Mobile Manipulation for Grapevine Winter Pruning Automation
Mobile manipulators that combine mobility and manipulability, are increasingly being used for various unstructured application scenarios in the field, e.g. vineyards. Therefore, the coordinated motion of the mobile base …
Cooperative constrained motion coordination of networked heterogeneous vehicles
We consider the problem of cooperative motion coordination for multiple heterogeneous mobile vehicles subject to various constraints. These include nonholonomic motion constraints, constant speed constraints, holonomic c…
Motion GenerationSymmetry Breaking for k-Robust Multi-Agent Path Finding
During Multi-Agent Path Finding (MAPF) problems, agents can be delayed by unexpected events. To address such situations recent work describes k-Robust Conflict-BasedSearch (k-CBS): an algorithm that produces coordinated …
Multi-Agent Path FindingGraph-Based Multi-Robot Path Finding and Planning
Purpose of Review Planning collision-free paths for multiple robots is important for real-world multi-robot systems and has been studied as an optimization problem on graphs, called Multi-Agent Path Finding (MAPF). This …
Multi-Agent Path FindingScheduling