Safe Collaborating Intelligent Vehicles: Synchronized Clocks

Abstract:

Our objective is to engineer vehicles that can collaborate on the use of a roadway. The protocols that define the collaboration must be provably safe, and the implementations of the protocols by different manufacturers must be guaranteed to inter-operate. As an example we are using a collaborative merge protocol, that assists a driver merging between two vehicles in an adjacent lane. We are using a probabilistic verification technique to test the most likely sequences of interactions between the vehicles until the unexplored sequences occur at an acceptably infrequent level. Considering that the ignition key problem in GM vehicles caused fatalities less than once every 107 hours of operation this level of guarantee cannot be achieved using test tracks or conventional simulations, but can be reached with our technique. We are using a black box testing procedure, called conformance testing, to guarantee that different implementations of the protocols will interoperate. We generate test sequences that can be applied to the input of the implementation, and observe the outputs. Initially we developed an architecture to break the problem into more manageable pieces. The architecture has a stack for each interaction between the intelligent system and the physical world. The modules in each stack are interconnected to provide the intelligent function. By designing the interconnections without loops, we can modify and test the modules separately.This year we concentrated on using synchronized clocks. Accurate, synchronized clocks are available from conventional GPS units. When GPS isn't available, crystal oscillators and standardized, precision time protocols maintain the clocks. We use the clocks to simplify verification and conformance testing, and to invent communications protocols with guarantees that are difficult or impossible to obtain without synchronization. We have a lock protocol that guarantees that none of the collaborating vehicles leave a collaboration before any of the others and release the lock even after communication is disrupted. We use the lock to guarantee that the vehicles can only participate in one maneuver at a time. We have a fault tolerant broadcast protocol, with a message type that cannot be lost, even when the communications channel is lost. We use this message to return the vehicles to a safe operating state whenever a disruptive situations occur. Synchronized clocks simplify probabilistic verification by reducing the number of sequences that can occur when collaboration occurs over unreliable communications channels that can require message retransmissions or lost messages. We use synchronized clocks to extract time from most of the intelligent modules. Instead of setting timers within a protocol, events that occur according to a time plan are inputs to the modules. As a result, we can use the postman package to generate test sequences for many time dependent protocols which did not have test sequences.