ABSTRACT
Much of the popularity of velocity obstacle (VO) methods can be traced to the ease of understanding them as prohibited shapes in velocity space. Reciprocal velocity obstacle (RVO) in particular is seductively elegant in sharing the burden of collision avoidance between agents. Velocity obstacle methods, at least for the moment, are the deserving rulers of the kingdom of collision avoidance. The goal of any gradient method is to converge to a locally optimal state, where no further improvements can be made. For collision avoidance, that generally looks like agents on trajectories which just squeeze past each other. The optimal reciprocal collision avoidance (ORCA) algorithm, which succeeded the original RVO algorithm had the sidedness concept as its central insight. ORCA was less concerned with stability, though, and more concerned with optimality. Understanding both the nuances of the problem space and the complexity of the solution space is the key to developing a system.
