Motion safety properties of relative velocity-based reciprocal collision avoidance methods

This paper is concerned with the development of motion safety criteria and associated proofs of safe operation for the class of reciprocal collision avoidance methods based on the relative velocity paradigm; including Velocity Obstacles (VO), Reciprocal Velocity Obstacles (ORCA), and Continuous Control Obstacles (CCO) - thus covering both holonomic and non-holonomic configurations. In the first part of this paper various notions of safety are reviewed and formalized, beginning with the most stringent of definitions which are then gradually relaxed while retaining practical applicability. In the second part of the paper, the developed safety notions are applied to the specified class of relative velocity-based reciprocal collision avoidance methods for which no guarantees for safe operation were known before. We develop a set of partial results, which, when together incorporated into the individual collision avoidance routines, provably lead to safe and collision-free overall operation.