Reciprocal n-body Collision Avoidance

1 Reciprocaln-body Collision AvoidanceJur van den Berg, Stephen J. Guy, Ming Lin, and Dinesh ManochaAbstractIn this paper, we present a formal approach toreciprocal n-body collisionavoidance, where multiple mobile robots need to avoid collisions witheach otherwhile moving in a common workspace. In our formulation, eachrobot acts fully in-dependently, and does not communicate with other robots. Based on the definitionof velocity obstacles [5], we derive sufficient conditions for Collision -free motionby reducing the problem to solving a low-dimensional linearprogram. We test ourapproach on several dense and complex simulation scenariosinvolving thousandsof robots and compute Collision -free actions for all of themin only a few millisec-onds. To the best of our knowledge, this method is the first that can guarantee localcollision-free motion for a large number of robots in a cluttered IntroductionCollision Avoidance is a fundamental problem in robotics.

2 The problem can gen-erally be defined in the context of an autonomous mobile robotnavigating in anenvironment with obstacles and/or other moving entities, where the robot employs acontinuous cycle of sensing and acting. In each cycle, an action for the robot must becomputed based on local observations of the environment, such that the robot staysfree of collisions with the obstacles and the other moving entities, while makingprogress towards a authors are with the Department of Computer Science, University of North Carolina at ChapelHill, USA. E-mail:{berg, sjguy, lin, research is supported in part by ARO Contracts W911NF-04-1-0088, NSF award 0636208,DARPA/RDECOM Contracts N61339-04-C-0043 and WR91 CRB-08-C-0137, Intel, and that the problem of (local) Collision - Avoidance differs frommotion planning, where theglobal environment of the robot is considered to be known anda complete path towards a goalconfiguration is planned at once [18], andcollision detection, which simply determines if twogeometric objects intersect or not (see [17]).}

3 12 Jur van den Berg, Stephen J. Guy, Ming Lin, and Dinesh ManochaThe problem of Collision Avoidance has been well studied forone robot avoid-ing static or moving obstacles. In this paper, we address themore involved and lessstudied problem ofreciprocal n-body Collision Avoidance , where collisions need tobe avoided among multiple robots (or any decision-making entities). This problemhas important applications in many areas in robotics, such as multi-robot naviga-tion and coordination among swarms of robots [20]. It is alsoan key component incrowd simulation for computer graphics and VR [11, 21], modeling of non-playercharacters in AI, studying flocks of birds and fish in biology [23], and real-time (air)traffic control [16]. In this paper, we propose a fast and novel method that simulta-neously determines actions for many (possibly thousands of) robots that each mayhave different objectives.

4 The actions are computed for each robot independently,without communication among the robots or central coordination. Yet, we provethat our method guarantees Collision -free motion for each of the use a simplified robot model, where each robot is assumed tohave a sim-ple shape (circular or convex polygon) moving in a two-dimensional , we assume that the robot isholonomic, it can move in any direc-tion, such that the control input of each robot is simply given by a two-dimensionalvelocity vector. Also, we assume that each robot hasperfectsensing, and is ableto infer the exact shape, position and velocity of obstaclesand other robots in results:We present a rigorous approach for reciprocaln-body collisionavoidance that provides asufficientcondition for each robot to be Collision -free forat least a fixed amount of time into the future, only assuming that the other robots usethe same Collision - Avoidance protocol.

5 Our approach isvelocity-based. That impliesthat each robot takes into account the observed velocity of other robots in order toavoid collisions with them, and also that the robot selects its own velocity fromitsvelocity spacein which certain regions are marked as forbidden because of thepresence of other robots. Our formulation, optimal Reciprocal Collision Avoidance ,infers for each other robot a half-plane (in velocity-space) of velocities that areallowed to be selected in order to guarantee Collision Avoidance . The robot thenselects its optimal velocity from the intersection of all permitted half-planes, whichcan be done efficiently usinglinear programming. Under certain conditions withdensely packed robots, the resulting linear program may be infeasible, in which casewe select the safest possible velocity using a three-dimensional linear experimented with our approach on several complex simulation scenarioscontaining thousands of robots.

6 As each robot is independent, we can fullyparal-lellizethe computation of the actions for each robot and report veryfast real-timerunning times. Furthermore, our experiments show that our approach achieves con-vincing motions that are smooth and rest of this paper is organized as follows. We start by discussing previouswork in Section 2. In Section 3, we formally define the problemwe address inthis paper. We derive the half-plane of permitted velocities for optimal reciprocalcollision Avoidance of a robot with respect to another robotin Section 4, and showhow this approach is used to navigate among multiple robots in Section 5. We reportexperimental results in Section 6 and conclude in Section Collision Avoidance32 Previous WorkThe problem of Collision Avoidance has been extensively studied. Many approachesassume the observed obstacles to be static ( non-moving) [2, 4, 6, 7, 13, 14, 24],and compute an immediate action for the robot that would avert collisions with theobstacle, in many cases taking into account the robot s kinematics and dynamics.

7 Ifthe obstacles are also moving, such approaches typically repeatedly replan basedon new readings of the positions of the obstacles. This may work well if the obstaclesmove slower than the robot, but among fast obstacles (such ascrossing a highway),the velocity of the obstacles need to be specifically taken into account. This problemis generally referred to as asteroid Avoidance , and approaches typically extrapolatethe observed velocities in order to estimate the future positions of obstacles [8, 9,12, 19, 22, 28].The problem of Collision Avoidance becomes harder when the obstacles arenot simply moving without considering their environment, but are also intelligentdecision-making entities that try to avoid collisions as well. Simply consideringthem as moving obstacles may lead tooscillationsif the other entity considers allother robots as moving obstacles as well [15, 26].

8 Therefore, the reactive nature ofthe other entities must be specifically taken into account inorder to guarantee thatcollisions are avoided. Yet, the robot may not be able to communicate with otherentities and may not know their intents. We call this problemreciprocal collisionavoidance, and is the focus of this obstacles (VO) [5] have been a successful velocity-based approach toavoid collisions with moving obstacles; they provide asufficientandnecessarycon-dition for a robot to select velocity that avoids collisionswith an obstacle moving ata known velocity. This approach was extended for robot-robot Collision avoidancewith the definition of Reciprocal Velocity Obstacles (RVO) [10, 26], where bothrobots were assumed to select a velocity outside the RVO induced by the other , this formulation only guarantees Collision - Avoidance under specific con-ditions, and does not provide a sufficient condition for Collision - Avoidance in this paper, we present the principle ofoptimal Reciprocal Collision avoid-ance(ORCA) that overcomes this limitation.

9 ORCA provides a sufficient conditionfor multiple robots to avoid collisions among one another, and thus can guaranteecollision-free note that it is possible to provide a sufficient and necessary condition formultiple (sayn) robots to select Collision -avoiding velocities, by defining acom-positevelocity obstacle in the 2n-dimensional space of velocities of allnrobots[1]. However, this is not only computationally impractical, it also requires centralcoordination among robots. This is incompatible with the type of distributed multi-robot navigation we focus on in this paper, in which each robot independently andsimultaneously selects its velocity from its own 2-D velocity fact, both robots selecting a velocityinsideeach other s RVO is a sufficient condition to endup in a van den Berg, Stephen J. Guy, Ming Lin, and Dinesh Manocha3 Problem DefinitionThe problem we discuss in this paper is formally defined as follows.

10 Let there be aset ofnrobots sharing an simplicity we assume therobots are disc-shaped and move in the planeR2(the definitions and algorithms we present in thispaper can easily be extended to translating polygons, and also to higher dimensions).Each robotAhas a current positionpA(the center of its disc), a current velocityvAand a radiusrA. These parameters are part of the robot s external state, weassume that they can be observed by other robots. Furthermore, each robot has amaximum speedvmaxAand a preferred velocityvprefA, which is the velocity the robotwould assume had no other robots been in its way (for instancea velocity directedtowards the robot s goal with a magnitude equal to the robot s preferred speed). Weconsider these parameters part of the internal state of the robot, and can thereforenot be observed by other task is for each robotAtoindependently(and simultaneously) select a newvelocityvnewAfor itself such thatallrobots areguaranteedto be Collision -free for atleast a preset amount of time when they would continue to move at their new ve-locity.