This paper proposes a mechanism to automatically assess the safety of autonomous robots and a POMDP-based method to generate colliding trajectories for the purpose of safety assessment. The proposed mechanism and method can be applied to any type of robot, but in this paper, we focus on autonomous cars. Given a range of autonomous robots with the same hardware capability but different software, our safety assessment mechanism outputs a ranking of the robots in terms of their safety. Many safety assessment mechanisms rely solely on accident data, which is rare. In contrast, to provide the safety ranking fast, we rely on the observation that in general, the smaller the distance between adversaries’ safe trajectories and their closest colliding trajectories, the less safe the autonomous car being assessed is, because there is less margin for errors. To compute colliding adversarial trajectories that are close to the adversaries’ safe trajectories, we take into account that the driving strategy of the vehicle being assessed is not fully known, and therefore propose a Multi-Objective Partially Observable Markov Decision Process (MOPOMDP) framing of the problem. To solve this MOPOMDP problem fast, we propose an on-line planning method, called Constraint-Aware Tree (CAT). Evaluations of CAT on the nuScenes dataset indicate that for the purpose of generating collision trajectories, CAT outperforms STRIVE, which is a state-of-the-art learning-based method that was also designed to alleviate the data-scarcity problem. Moreover, evaluations of four autonomous driving software on pedestrian crossing and lane merging scenarios, derived from the National Highway Traffic Safety Administration (NHTSA), indicate the viability of the proposed safety assessment mechanism.