Analytic Velocity Obstacle for Efficient Collision Avoidance Computation and a Comparison Study With Sampling and Optimization-Based Approaches

Abstract

Velocity obstacle (VO) is one of the popular reactive navigation algorithms for the path planning of autonomous agents. The collision-free property can be guaranteed if the agent is able to choose a velocity outside the VO region under the assumption that obstacles maintain a constant velocity within the control cycle time of the agent. To date, the selection of the optimal velocity relies on either sampling or optimization approaches. The sampling approach can maintain the same amount of computation cost but may miss feasible solutions under collision risks with an insufficient number of samples. The optimization approach such as the linear programming demands convexity of the constraints in the velocity space which may not be satisfied considering non-holonomic agents. In addition, the algorithm has varying computation demands depending on the navigation situation. This paper proposes an analytic approach for choosing a candidate velocity rather than relying on sampling or optimization approaches. The analytic approach can significantly reduce computation costs without sacrificing performance. Agents with both holonomic and non-holonomic constraints are considered to demonstrate the performance and efficiency of the proposed approach. Extensive comparison studies with static, non-reactive, and reactive moving obstacles demonstrate that the analytical VO is computationally much more efficient than the optimization-based approach and performs better than the sampling-based approach. Major video results of this paper can be accessed online.