Another approach to obstacle avoidance is based on the concept of velocity obstacles [1]}. Velocity obstacles are geometric regions in velocity space that describe the set of velocities an agent A is not permitted to use, otherwise it will eventually collide with agent B, if both agents continue to travel with the same velocity. Assuming two or more agents are using the same control principle and choose a velocity for the next time step outside of their respective velocity obstacles in a reciprocal fashion [2]}, a simple linear program can be used to guarantee collision-free motion for n-bodies [3]} as long as the modeling assumptions hold. Acceleration-velocity obstacles [4]} and nonholonomic control [5]} have also been investigated. Velocity obstacles assume circular or convex polygonal obstacles that travel at constant velocity and use the same controller. Our concept can deal with nonconvex polygons of arbitrary size and does not make the assumption of a certain type of controller being used by the other agents. Furthermore, as it is possible to enter and leave a velocity obstacle before the collision actually occurs, our A* approach provides for more precise collision checking than the velocity obstacle concept is able to. We also predict the state of other agents based on the assumption that their observed velocities remain constant for a short time, but we predict the state of the controlled agent using the planned controls and perform precise polygon vs polygon collision checking with the predicted states.
