The current generation of automobiles uses sensors and computers to assist the driver to avoid accidents. The next step is to use communications between automobiles to improve the accuracy of sensor measurements and negotiate maneuvers between vehicles. The objective is to improve safety and increase the capacity of roadways.
As the systems evolve, different vehicles will have different capabilities. The communications between vehicles is unreliable. And, the algorithms are complex and failures can be fatal. This year there have been massive recalls of vehicles with faulty control systems.
In this project, we are:
1) Investigating a variety of roles that communications can play in vehicle control, and the limitations that communications imposes on control.
2) Establishing metrics to quantify the performance of cyber-physical systems in several dimensions, including performance, fairness and safety.
3) Testing strategies to guarantee that the systems can be operated safely.
We are testing our techniques by analyzing and simulating a system that controls multiple lane merges that occur when highways merge, following tolls, and at construction or accident sites. For instance, at the lower level of the New York bound George Washington Bridge, 10 lanes merge to 3. The delays during the morning rush range from 20 to 90 minutes, and there are accidents most days. Assisted lane merging can reduce accidents and delays at these dangerous locations. These systems are the most technically challenging of the collaborative driving applications. They require cooperation and planning between vehicles in addition to controlling the speed, braking and maneuvers of the individual vehicles.
Our objective is to engineer collaborative vehicles that are safe. We have: 1) Developed a probabilistic verification technique that can achieve the levels of safety that are required in automobiles. The procedure operates by validating each sequence of operations that can occur with different combinations of failures. It may not be possible to validate all of the sequences, but the most likely sequences are validated first, until the remaining sequences occur so infrequently that they can be disregarded. Consider GM’s ignition switch problem. There was less than one fatality every 10 million hours of operation, and this was not considered adequate. This level of failure cannot be reliably detected by operating a small number of vehicles on a test track or even on public roads, but can be detected using probabilistic verification. 2) Developed a multi-layered architecture, shown in the attached figure, that partitions the engineering and verification of intelligent vehicles, into more manageable pieces. The connecting lines in the figure represent a protocol to merge a vehicle between two vehicles in an adjacent lane. They show which modules depend upon other modules to provide a service. To the extent that we can avoid loops in the architecture, we can design and verify the modules independently. The architecture also shows which physical failures can affect the intelligent system. This strategy is similar to that in the Internet, which uses a single stack, communications architecture. The intelligent vehicle problem is more complicated than the communications problem, interacts with the physical world in more ways, and is time critical. 3) Pioneered the use of synchronized clocks in cyber-physical systems. GPS, crystal oscillators, and standardized precision time protocols have made inexpensive, synchronized clocks readily available. We are using synchronized clocks to: 1) Reduce the complexity of verifying time dependent protocols. Coordinating the maneuvers of multiple vehicles by sending messages over an unreliable communications channel results in ambiguous sequences of operations because messages to the vehicles may require multiple transmissions, or may not be delivered at all. If instead of setting timers when a message is received, we schedule an event at a specified time, in the future, there will only be one possible sequence of operations. The operations can be scheduled to occur simultaneously in all of the vehicles, or can be scheduled in a specified sequence in each of the vehicles. We are using scheduled events to separate the plan of operation, which is time dependent, from the control portion of the protocol, which controls the operation of the protocol when messages are received or when there are inputs from the external sensors or the mechanical systems in a vehicle. The control portion of the protocol is verified using probabilistic verification, but verifying the time plan must be proven safe by other means, and usually requires knowledge of the physics of mobility. We use a synchronized protocol to guarantee that we only schedule events in the future. 2) Create a new class of communications protocols that use synchronized clocks to obtain unique guarantees that are difficult or impossible to obtain without synchronization. The first two synchronized protocols are: 1) A lock protocol that guarantees that: The protocol only proceeds when all of the parties are locked. That the locks are always released at some time in the future, independent of which parties are locked. And, that all of the locks that have been obtained are released simultaneously, no matter what combination of messages is lost. The lock protocol is used by our merge protocol. The merge can only proceed when the three cars participating in the merge are committed to this merge and no others. The merging car is the master and requests a lock, until a specified time, from the two adjacent cars. The request is retransmitted k times, or until acknowledged. The acknowledgement is transmitted each time the request is received. The master is locked as soon as it transmits the request and the other vehicles are locked when they receive the request, if they are not already locked. The merge proceeds if the master receives both acknowledgements. All parties release the lock at the specified time. 2) A fail safe broadcast protocol that guarantees that messages to abort the protocol are never lost, even if the communications channel is lost. Each party in the protocol transmits messages at a scheduled time. The other parties request retransmissions if a scheduled message is not received. The protocol is aborted by not transmitting in a scheduled slot. When any party cannot recover a scheduled transmission, it aborts and does not transmit in its scheduled slot. Therefore, the protocol is aborted if any party aborts the protocol or if any party is unable to communicate with any other party.
