Rules of the Road: Towards Safety and Liveness Guarantees for Autonomous Vehicles

The ability to guarantee safety and progress for all vehicles is vital to the success of the autonomous vehicle industry. We present a framework for the distributed control of autonomous vehicles that is safe and guarantees progress for all agents. In this paper, we first introduce a new game paradigm which we term the quasi-simultaneous discrete-time game. We then define an Agent Protocol agents must use to make decisions in this quasi-simultaneous discrete-time game setting. According to the protocol, agents first select an intended action and then each agent determines whether it can take its intended action or not, given its proposed intention and the intentions of nearby agents. The protocol so defined will ensure safety under all traffic conditions and liveness for all agents under "sparse" traffic conditions. These guarantees, however, are predicated on the premise that all agents are operating with the aforementioned protocol. We provide proofs of correctness of the protocol and validate our results in simulation.