Two-Dimensional Distributed Velocity Collision Avoidance

May 1, 2016

Naval Air Warfare Center Weapons Division, China Lake, California

As the number of autonomous vehicles continues to increase for both commercial and military applications, collision avoidance algorithms are of the utmost importance to successfully execute missions in dynamic environments.

One approach is the two-dimensional (2D) version of the Automated Velocity Obstacle Collision Avoidance (AVOCA) system, a collection of velocity obstacle (VO)-based collision avoidance algorithms. The primary goal of the AVOCA system is to achieve cooperative collision avoidance by dynamic entities in the problem space (agents), performed in a distributed fashion with minimal communication requirements. The algorithms used in AVOCA achieve implicit cooperation through their application and require only basic information (i.e., position and velocity) information on other agents for their calculations.

The AVOCA system uses basic VOs, truncated VOs, reciprocal velocity obstacles (RVOs), hybrid reciprocal velocity obstacles (HRVOs), and Clearpath. Generally, a VO is a geometric region (typically an infinite triangle) that is calculated using two agents in the problem space, a source agent (Asrc) (i.e., the agent that is being guided by the algorithm), and another agent (Aoth). The VO region defines the set of all points that, if used for the endpoint for Asrc’s velocity vector, will result in a collision between the two agents at some point in the future.

To perform its avoidance calculations, AVOCA builds basic VOs, RVOs, and HRVOs for all other agents in the problem space. The constructs are built using the velocity and position of each agent, so these data items are required by AVOCA. Basic VOs assume no interagent cooperation. When used unmodified, this means that Asrc assumes full responsibility for performing the collision avoidance between the two agents. The AVOCA system uses bound Euclidean vectors (i.e., vectors in which both the base and end point are used), rather than the more commonly used free vectors (i.e., vectors in which just the magnitude and angle are relevant).

This work was done by Josh L. Wilkerson, Jim Bobinchak, Michael Culp, Josh Clark, Tyler Halpin-Chan, Katia Estabridis, and Gary Hewer of the Naval Air Warfare Center Weapons Division. NAWC-0001