CPS: Small: The Roles of Communications in Lane Merging Systems

Abstract: Vehicle automation has progressed from systems that monitor the operation of a vehicle, such as antilock brakes and cruise control, to systems that sense adjacent vehicles, such as emergency braking and intelligent cruise control. The next generation of systems will share sensor readings and collaborate to control braking operations by looking several cars ahead or by creating safe gaps for merging vehicles. Before we allow collaborative systems on public highways we must prove that they will do no harm, even when multiple rare events occur. The events will include loss of communications, failures or inaccuracies of sensors, mechanical failures in the automobile, aggressive drivers who are not participating in the system, and unusual obstacles or events on the roadways. The rules that control the interaction between vehicles is a protocol. There is a large body of work to verify the correctness of communications protocols and test that different implementations of the protocol will interact properly. However, it is difficult to apply these techniques to the protocols for collaborative driving systems because they are much more complex: 1) They interact with the physical world in more ways, through a network of sensors and the physical operation of the automobile as well as the communications channel; 2) They perform time critical operations that use multiple timers; And, 3) they may have more parties participating. In [1] we have verified that a three party protocol that assists a driver who wants to merge between two cars in an adjacent lane will not cause an accident for combinations of rare events. The verification uses a probabilistic sequence testing technique [2] that was developed for communications protocols. We were only able to use the communications technique after designing and specifying the collaborative driving protocol in a particular way. We have generalized the techniques used in the earlier work so that we can design collaborative driving protocols that can be verified. We have 1) a non-layered architecture, 2) a new class of protocols based upon time synchronized participants, and 3) a data management rule. 1) Communications protocols use a layered architecture. Protocol complexity is reduced by using the services provided by a lower layer. The layered architecture is not sufficient for collaborative driving protocols because they operate over multiple physical platforms. Instead, we define a smoke stack architecture that is interconnected. 2) The operation of protocols with multiple timers is more difficult to analyze because there are different sequences of operations depending on the relative times when the timers are initiated. Instead of using timers, we design protocols that use absolute time. This is reasonable because of the accurate time acquired from GPS and the accuracy of current clocks while GPS is not available. 3) Finally, in order for programs in different vehicles to make the same decisions they must use the same data. Our design merges the readings of sensors in different vehicles and uses a communications protocol that guarantees that all vehicles have the same sequence of messages and only use the messages that all vehicles have acquired. 1. Bohyun Kim, N. F. Maxemchuk, "A Safe Driver Assisted Merge Protocol," IEEE Systems Conference 2012, 19-22 Mar. 2012, Vancouver, BC, Canada, pp. 1-4. 2. N. F. Maxemchuk, K. K. Sabnani, "Probabilistic Verification of Communication Protocols," Distributed Computing Journal, Springer Verlag, no. 3, Sept. 1989, pp. 118-129.