Applications of CPS technologies essential for the functioning of a society and economy.
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.
Off
Columbia University
-
National Science Foundation
Maxemchuk, Nicholas
![Nicholas Maxemchuk](/sites/cps-vo.org/files/profile_images/picture-186.jpg)
The objective of this research is to address a fundamental question in cyber-physical systems: What is the ideal structure of systems that detect critical events such as earthquakes by using data from large numbers of sensors held and managed by ordinary people in the community? The approach is to develop theory about widely-distributed sense and respond systems, using dynamic and possibly unreliable networks using sensors and responders installed and managed by ordinary citizens, and to apply the theory to problems important to society, such as responding to earthquakes. Intellectual Merit: This research develops theory and prototype implementations of community-based sense-and-respond systems that enable people help one another in societal crises. The number of participants in such systems may change rapidly; some participants may be unreliable and some may even deliberately attack systems; and the structures of networks change as crises unfold. Such systems must function in rare critical situations; so designs, analyses and tests of these systems must give confidence that they will function when the crisis hits. The proposed research will show how to design systems with organic growth, unreliable components and connections, security against rogue components, and methods of demonstrating reliability. Broader Impact: People want to help one another in a crisis. Cheap sensors, mobile phones, and laptops enable people to use information technology to help. This research empowers ordinary citizens collaborate to overcome crises. The researchers collaborate with the US Geological Service, Southern California Edison, and Microsoft, and will host 3,000 students at a seismic facility
Off
California Institute of Technology
-
National Science Foundation
Robert Clayton
Thomas Heaton
Krause, Andreas
![Andreas Krause](/sites/cps-vo.org/files/profile_images/picture-229.jpg)
The objective of this research is to develop technologies to improve the efficiency and safety of the road transportation infrastructure. The approach is to develop location-based vehicular services combining on-board automotive computers, in-car devices, mobile phones, and roadside monitoring/surveillance systems. The resulting vehicular Cyber Physical Systems (CPS) can reduce travel times with smart routing, save fuel and reduce carbon emissions by determining greener routes and commute times, improve safety by detecting road hazards, change driving behavior using smart tolling, and enable measurement-based insurance plans that incentivize good driving. This research develops distributed algorithms for predictive travel delay modeling, feedback-based routing, and road hazard assessment. It develops privacy-preserving protocols for capturing and analyzing data and using it for tasks such as congestion-aware tolling. It also develops a secure macro-tasking software run-time substrate to ensure that algorithms can be programmed centrally without explicitly programming each node separately, while ensuring that it is safe to run third-party code. The research focuses on re-usable methods that can benefit multiple vehicular services, and investigates which lessons learned from this vehicular CPS effort generalize to other situations. Road transportation is a grand challenge problem for modern society, which this research can help overcome. Automobile vendors, component developers, and municipal authorities have all shown interest in deployment. The education plan includes outreach to local K-12 students and a new undergraduate course on transportation from a CPS perspective, which will involve term projects using the data collected in the project
Off
Massachusetts Institute of Technology
-
National Science Foundation
Samuel Madden
Daniela Rus
Balakrishnan, Hari
![Hari Balakrishnan](/sites/cps-vo.org/files/profile_images/picture-196.jpg)
The objective of this research is the transformation from static sensing into mobile, actuated sensing in dynamic environments, with a focus on sensing in tidally forced rivers. The approach is to develop inverse modeling techniques to sense the environment, coordination algorithms to distribute sensors spatially, and software that uses the sensed environmental data to enable these coordination algorithms to adapt to new sensed conditions. This work relies on the concurrent sensing of the environment and actuation of those sensors based on sensed data. Sensing the environment is approached as a two-layer optimization problem. Since mobile sensors in dynamic environments may move even when not actuated, sensor coordination and actuation algorithms must maintain connectivity for the sensors while ensuring those sensors are appropriately located. The algorithms and software developed consider the time scales of the sensed environment, as well as the motion capabilities of the mobile sensors. This closes the loop from sensing of the environment to actuation of the devices that perform that sensing. This work is addresses a challenging problem: the management of clean water resources. Tidally forced rivers are critical elements in the water supply for millions of Californians. By involving students from underrepresented groups, this research provides a valuable opportunity for students to develop an interest in engineering and to learn first hand about the role of science and engineering in addressing environmental issues.
Off
University of California-Berkeley
-
National Science Foundation
Bayen, Alexandre
![Alexandre Bayen](/sites/cps-vo.org/files/profile_images/picture-232.jpg)
The objective of this research is the transformation from static sensing into mobile, actuated sensing in dynamic environments, with a focus on sensing in tidally forced rivers. The approach is to develop inverse modeling techniques to sense the environment, coordination algorithms to distribute sensors spatially, and software that uses the sensed environmental data to enable these coordination algorithms to adapt to new sensed conditions. This work relies on the concurrent sensing of the environment and actuation of those sensors based on sensed data. Sensing the environment is approached as a two-layer optimization problem. Since mobile sensors in dynamic environments may move even when not actuated, sensor coordination and actuation algorithms must maintain connectivity for the sensors while ensuring those sensors are appropriately located. The algorithms and software developed consider the time scales of the sensed environment, as well as the motion capabilities of the mobile sensors. This closes the loop from sensing of the environment to actuation of the devices that perform that sensing. This work is addresses a challenging problem: the management of clean water resources. Tidally forced rivers are critical elements in the water supply for millions of Californians. By involving students from underrepresented groups, this research provides a valuable opportunity for students to develop an interest in engineering and to learn first hand about the role of science and engineering in addressing environmental issues.
Off
University of California-San Diego
-
National Science Foundation
Martinez, Sonia
![Sonia Martinez](/sites/cps-vo.org/files/profile_images/picture-217.jpg)
The objective of this research is the transformation from static sensing into mobile, actuated sensing in dynamic environments, with a focus on sensing in tidally forced rivers. The approach is to develop inverse modeling techniques to sense the environment, coordination algorithms to distribute sensors spatially, and software that uses the sensed environmental data to enable these coordination algorithms to adapt to new sensed conditions. This work relies on the concurrent sensing of the environment and actuation of those sensors based on sensed data. Sensing the environment is approached as a two-layer optimization problem. Since mobile sensors in dynamic environments may move even when not actuated, sensor coordination and actuation algorithms must maintain connectivity for the sensors while ensuring those sensors are appropriately located. The algorithms and software developed consider the time scales of the sensed environment, as well as the motion capabilities of the mobile sensors. This closes the loop from sensing of the environment to actuation of the devices that perform that sensing. This work is addresses a challenging problem: the management of clean water resources. Tidally forced rivers are critical elements in the water supply for millions of Californians. By involving students from underrepresented groups, this research provides a valuable opportunity for students to develop an interest in engineering and to learn first hand about the role of science and engineering in addressing environmental issues.
Off
University of Arizona
-
National Science Foundation
Sprinkle, Jonathan
![Jonathan Sprinkle](/sites/cps-vo.org/files/pictures/2024-03/sprinkle_2020-ua.jpeg)