Capturing Velocity Function Plateaus for Efficient Marine Vehicle Collision Avoidance Calculations

摘要

Closest Point of Approach (CPA) calculations are fundamental calculations for determining the utility and safety of a candidate maneuver of a marine vessel with respect to another vessel, i.e., contact. In certain kinds of path planning, a set of CPA calculations is made for thousands of candidate maneuvers, perhaps several times per second. Furthermore, with multiple contacts, multiple sets need to be calculated. This workload can overwhelm the computational resources of the on-board computer, especially on a low-power computer commonly found on marine platforms. We present here a method for representing and forming collision avoidance utility functions called velocity functions. These utility functions are defined over all possible maneuver decisions and are piecewise linearly defined with each piece providing a linear approximation of utilities for a subset of possible decisions. The piecewise defined functions contribute to a multi-objective optimization problem where the optimal decision represents a collision free maneuver. The piecewise defined functions need not be uniformly sized. If utility function plateaus can be rapidly identified, then a handful of large pieces may replace thousands of pieces without a loss in accuracy. In this paper a set of algorithms is provided for rapid identification or capture of plateaus to greatly improve the efficiency and speed of collision avoidance multi-objective optimizations problems.