Use of Falsification to Find Rare Failure Modes of a Ship Collision Avoidance Algorithm

Existing collision avoidance algorithms for autonomous ships use techniques ranging from model predictive control to rule-based decision methods. However, verification of these algorithms requires exploring the entire space of ship trajectories, which is difficult due to the prohibitively large number of potential encounter scenarios even in cases involving a few ships. While simulating thousands of encounter scenarios is required for an accurate assessment of the algorithm's efficacy in preventing collisions, such a process is computationally expensive and time-consuming. Alternatively, one can reduce the total number of simulations used for algorithm assessment by strategically searching the input space for undesirable behavior from the collision avoidance algorithm. We address this challenge by using optimization-based falsification techniques to efficiently discover failure modes of a ship collision avoidance algorithm. We examine different methods for falsification and show that the cross-entropy approach using a Gaussian mixture distribution for sampling has potential advantages over competing methods for the collision avoidance application. Namely, the Gaussian mixture distribution can identify correlated inputs due to our assumption of nonindependent inputs and is more likely to discover multiple failure regions in the input space.