Reciprocal n-body Collision Avoidance

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.

be avoided among multiple robots (or any decision-making entities). This problem has important applications in many areas in robotics, such as multi-robot naviga-tion and coordinationamong swarms of robots [20]. It is also an key component in crowd simulation for computer graphics and VR [11, 21], modeling of non-player

Loading..

Tags:

  Applications, Robot

Information

Related search queries