text: In this paper, we present "IVO: Inverse Velocity Obstacles" an ego-centric framework that improves the real time implementation. The proposed method stems from the concept of velocity obstacle and can be applied for both single agent and multi-agent system. It focuses on computing collision free maneuvers without any knowledge or assumption on the pose and the velocity of the robot. This is primarily achieved by reformulating the velocity obstacle to adapt to an ego-centric framework. This is a significant step towards improving real time implementations of collision avoidance in dynamic environments as there is no dependency on state estimation techniques to infer the robot pose and velocity. We evaluate IVO for both single agent and multi-agent in different scenarios and show it's efficacy over the existing formulations. We also show the real time scalability of the proposed methodology.
  @cite_14: This approach, designed for mobile robots equipped with synchro-drives, is derived directly from the motion dynamics of the robot. In experiments, the dynamic window approach safely controlled the mobile robot RHINO at speeds of up to 95 cm sec, in populated and dynamic environments.
  @cite_4: A real-time obstacle avoidance method for mobile robots which has been developed and implemented is described. This method, named the vector field histogram (VFH), permits the detection of unknown obstacles and avoids collisions while simultaneously steering the mobile robot toward the target. The VFH method uses a two-dimensional Cartesian histogram grid as a world model. This world model is updated continuously with range data sampled by onboard range sensors. The VFH method subsequently uses a two-stage data-reduction process to compute the desired control commands for the vehicle. Experimental results from a mobile robot traversing densely cluttered obstacle courses in smooth and continuous motion and at an average speed of 0.6-0.7 m s are shown. A comparison of the VFN method to earlier methods is given. >
  @cite_8: 
  @cite_1: This paper introduces a framework for real-time simulation and rendering of crowds navigating in a virtual environment. The solution first consists in a specific environment preprocessing technique giving rise to navigation graphs, which are then used by the navigation and simulation tasks. Second, navigation planning interactively provides various solutions to the user queries, allowing to spread a crowd by individualizing trajectories. A scalable simulation model enables the management of large crowds, while saving computation time for rendering tasks. Pedestrian graphical models are divided into three rendering fidelities ranging from billboards to dynamic meshes, allowing close-up views of detailed digital actors with a large variety of locomotion animations. Examples illustrate our method in several environments with crowds of up to 35000 pedestrians with real-time performance. Copyright © 2006 John Wiley and Sons, Ltd.
  @cite_3: We present a novel approach for real-time path planning of multiple virtual agents in complex dynamic scenes. We introduce a new data structure, Multi-agent Navigation Graph (MaNG), which is constructed from the first- and second-order Voronoi diagrams. The MaNG is used to perform route planning and proximity computations for each agent in real time. We compute the MaNG using graphics hardware and present culling techniques to accelerate the computation. We also address undersampling issues for accurate computation. Our algorithm is used for real-time multi-agent planning in pursuit-evasion and crowd simulation scenarios consisting of hundreds of moving agents, each with a distinct goal.
  @cite_0: Most of present work for autonomous navigation in dynamic environment doesn't take into account the dynamics of the obstacles or the limits of the perception system. To face these problems we applied the probabilistic velocity obstacle (PVO) approach (Kluge and Prassler, 2004) to a dynamic occupancy grid. The paper presents a method to estimate the probability of collision where uncertainty in position, shape and velocity of the obstacles, occlusions and limited sensor range contribute directly to the computation. A simple navigation algorithm is then presented in order to apply the method to collision avoidance and goal driven control. Simulation results show that the robot is able to adapt its behaviour to the level of available knowledge and navigate safely among obstacles with a constant linear velocity. Extensions to non-linear, non-constant velocities are proposed.
  @cite_19: We present a novel algorithm for motion planning of multiple robots amongst dynamic obstacles. Our approach is based on a new roadmap representation that uses deformable links and dynamically retracts to capture the connectivity of the free space. We use Newtonian physics and Hooke's Law to update the position of the milestones and deform the links in response to the motion of other robots and the obstacles. Based on this roadmap representation, we describe our planning algorithms that can compute collision-free paths for tens of robots in complex dynamic environments.
  @cite_2: This paper presents an alternative to the Potential Field Method of computing local collision-free motions for general manipulators. The main distinction is that we separate the description of the task from constraints of anti-collision. This enables to control accurately all relevant measures of the problem. A task is expressed by the minimization of a function plus eventually some geometric constraints, whereas anti-collision is translated into very simple linear constraints through the methods of the velocity dampers and the tangent separating planes. This approach is applied to the control of manipulators with a high number of degrees of freedom, using hierarchical descriptions of the environment and the robots. This is illustrated by two realizations, path planning for a ten link manipulator in the cluttered environment of a nuclear plant reactor, and cooperative tasks between two six degree of freedom robots. In the end we discuss how to incorporate the action of a global planner in this general framework.
  @cite_5: 
  @cite_16: 
  @cite_10: This paper presents ICS-AVOID, a collision avoidance scheme based upon the concept of Inevitable Collision State (ICS), ie a state for which, no matter what the future trajectory of the robotic system is, a collision eventually occurs. By design, ICS-AVOID can handle dynamic environments since ICS do take into account the future behaviour of moving objects. ICS-AVOID is designed to keep the system away from ICS. By doing so, motion safety is guaranteed (by definition a robotic system in a non-ICS state has at least one collision-free trajectory that it can use). To demonstrate the efficiency of ICS-AVOID, it has been extensively compared with two state-of-the-art collision avoidance schemes: the first one is built upon the Dynamic Window approach and the second one on the Velocity Obstacle concept. The results obtained show that, when provided with the same amount of information about the future evolution of the environment, ICS-AVOID outperforms the other two schemes. The first reason for this has to do with the extent to which each collision avoidance scheme reasons about the future. The second reason has to do with the ability of each collision avoidance scheme to find a safe control if one exists. ICS-AVOID is the only one which is complete in this respect thanks to the concept of Safe Control Kernel.
  @cite_20: This paper presents a novel randomized motion planner for robots that must achieve a specified goal under kinematic and or dynamic motion constraints while avoiding collision with moving obstacles with known trajectories. The planner encodes the motion constraints on the robot with a control system and samples the robot's state × time space by picking control inputs at random and integrating its equations of motion. The result is a probabilistic roadmap of sampled state ×time points, called milestones, connected by short admissible trajectories. The planner does not precompute the roadmap; instead, for each planning query, it generates a new roadmap to connect an initial and a goal state×time point. The paper presents a detailed analysis of the planner's convergence rate. It shows that, if the state×time space satisfies a geometric property called expansiveness, then a slightly idealized version of our implemented planner is guaranteed to find a trajectory when one exists, with probability quickly converg...
summary: In this section, we present an overview of the approaches on collision avoidance and navigation in dynamic environment. Quite a few approaches @cite_4 , @cite_2 , @cite_14 , @cite_8 assume that the obstacles are static and plan for the control to avoid the collision. In case of moving obstacles these replan based on the updated positions of the obstacles. But these fail to generate the safe trajectories around the fast moving obstacles. In @cite_0 , @cite_16 , @cite_20 , @cite_10 the future position of obstacles are computed by extrapolating with the current velocity to handle high velocities. But these approaches cannot handle the reactive nature of the other agents. Many works like @cite_1 , @cite_5 , @cite_3 , @cite_19 have focused on crowd simulation in which each agent considers the other agents as obstacles and navigates independently.