ORCARRT*
Back to Pavel Janovsky's website
Paper
Finding Coordinated Paths for Multiple Holonomic Agents in 2d Polygonal Environment
Appears in: Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems AAMAS 2014, May 59, 2014, Paris, France
Authors
Pavel
Janovsky (pavel.janovsky at agents.fel.cvut.cz), Michal Cap
(michal.cap at agents.fel.cvut.cz), Jiri Vokrinek
(jiri.vokrinek at agents.fel.cvut.cz)
Abstract
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 2d environment with polygonal
obstacles. The problem is PSPACEhard, with the state space growing
exponentially in the number of agents. Therefore, the state of the art
methods include mainly reactive techniques and samplingbased iterative
algorithms.
We compare the performance of a widelyused reactive
method ORCA [1] with three variants of a popular planning algorithm RRT* [2]
applied to multiagent path planning and find that an algorithm
combining reactive collision avoidance and RRT* planning, which we call
ORCARRT* 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 multiagent 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.
(a) ORCARRT*
(b) ORCA
Figure 1: Improvement of the reactive technique ORCA 
Figure 2: Example problem instance 
Figure 3: Success Rate of the compared algorithms 
Figure 4: Problem Environments 
References
[1] J. van den Berg, S. J. Guy, M. Lin and D. Manocha. Reciprocal nbody collision avoidance. 2011.
[2] Karaman and Frazzoli. Samplingbased algorithms for optimal motion planning. I. J. Robotic Res., 20(5):846894, 2011. 
