The approach, developed by University Professor of Computer Science Edmund M. Clarke and Andre Platzer, assistant professor of computer science, already has detected a flaw in aircraft collision avoidance maneuvers —since corrected — that could have caused mid-air collisions.
It also has verified the soundness of the European Train Control System. Ultimately, the method could be used on other cyber-physical systems, such as robotic surgery devices and nano-level manufacturing equipment.
"Engineers increasingly are relying on computers to improve the safety and precision of physical systems that must interact with the real world, whether they be adaptive cruise controls in automobiles or machines that monitor critically ill patients," Clarke said. "With systems becoming more and more complex, mere trial-and-error testing is unlikely to detect subtle problems in system design that can cause disastrous malfunctions. Our method is the first that can prove these complex cyber-physical systems operate as intended, or else generate counterexamples of how they can fail using computer simulation."
In the case of aircraft collision avoidance systems, for instance, Platzer and Clarke used their method to analyze so-called roundabout maneuvers. When two aircraft are on rapidly converging paths, one technique for avoiding collisions is for the system to order each pilot to turn right and then circle to the left until the aircraft can safely turn right again to resume their original paths. It's as if the aircraft are following a large traffic circle, or rotary, in the sky. But analysis by the Carnegie Mellon researchers identified a counterexample: when aircraft approach each other at certain angles, the roundabout maneuver actually creates a new collision course that, in the few seconds remaining before their paths cross, the pilots might not have time to recognize.
Like Model Checking, a method pioneered by Clarke that today is the most widely used technique for detecting and diagnosing errors in complex hardware and software design, the new method analyzes the logic underlying the system design, much as a mathematician uses a proof to determine that a theorem is correct. Clarke shared the 2007 A.M. Turing Award, generally considered the computer science equivalent of the Nobel Prize, for his role in developing Model Checking.
A crucial difference, however, is that Model Checking can examine every possible state of a discrete finite-state system, such as a new circuit design for a computer chip; that's not possible for a CPS that must interact with the infinitely variable real world. Even if the differential equations that govern these systems can be solved — and they often can't — it usually is impossible to use the results to predict the behavior of the system, Platzer said. Instead, he and Clarke have developed algorithms that decompose the systems until they produce differential invariants — mathematical descriptions of parts of the system that always remain the same. These differential invariants, in turn, can be used to prove the global logic of the CPS.
"When the system design is sound, as we found in the case of the European control system for train traffic or the repaired flight controller, our method can provide conclusive proof," Platzer said. Likewise, when flaws exist, the method reliably generates counterexamples. "Finding the counterexamples is actually the easy part," he added. "Proving that they are fixed is hard."
The demand for methods that can prove a CPS or hybrid system operates as intended will only increase as these systems become more numerous and more crucial for everyday life, Platzer said. "Bugs in complex cyber-physical systems like cars, aircraft, chips or medical devices are expensive to fix and may endanger human life," he explained. "In transportation, the percentage of development cost spent on design and testing new control software is already well above 50 percent and is steadily rising."
The National Science Foundation (NSF) has identified the design and verification of CPS as a key area of research. The increasing use of robotic devices, the growth of sensor networks, the proposed creation of a "smart grid" for delivering electrical power, a greater reliance on automated war fighting and growing use of efficient, "zero-net-energy" buildings are all examples of a growing reliance on computer control systems that are tightly coupled to physical systems. This work was sponsored, in part, by the NSF and the German Research Council.
About Carnegie Mellon: Carnegie Mellon is a private research university with a distinctive mix of programs in engineering, computer science, robotics, business, public policy, science and social science, fine arts and the humanities. More than 11,000 undergraduate and graduate students receive an education characterized by its focus on creating and implementing solutions for real problems, interdisciplinary collaboration, and innovation. A small student-to-faculty ratio provides an opportunity for close interaction between students and professors. While technology is pervasive on its 145-acre Pittsburgh campus, Carnegie Mellon is also distinctive among leading research universities for the world-renowned programs in its College of Fine Arts. A global university, Carnegie Mellon has campuses California's Silicon Valley and Qatar, and programs in Asia, Australia and Europe.
Byron Spice | EurekAlert!
Further reports about: > CPS > NSF > Science TV > Silicon Valley > adaptive cruise controls in automobiles > aircraft collision avoidance systems > computer science > computer-controlled devices > cyber-physical systems > disastrous malfunctions > high-speed train controls > mid-air collisions > zero-net-energy
Smarter robot vacuum cleaners for automated office cleaning
15.08.2017 | Fraunhofer-Institut für Arbeitswirtschaft und Organisation IAO
Researchers 3-D print first truly microfluidic 'lab on a chipl devices
15.08.2017 | Brigham Young University
Physicists at the University of Bonn have managed to create optical hollows and more complex patterns into which the light of a Bose-Einstein condensate flows. The creation of such highly low-loss structures for light is a prerequisite for complex light circuits, such as for quantum information processing for a new generation of computers. The researchers are now presenting their results in the journal Nature Photonics.
Light particles (photons) occur as tiny, indivisible portions. Many thousands of these light portions can be merged to form a single super-photon if they are...
For the first time, scientists have shown that circular RNA is linked to brain function. When a RNA molecule called Cdr1as was deleted from the genome of mice, the animals had problems filtering out unnecessary information – like patients suffering from neuropsychiatric disorders.
While hundreds of circular RNAs (circRNAs) are abundant in mammalian brains, one big question has remained unanswered: What are they actually good for? In the...
An experimental small satellite has successfully collected and delivered data on a key measurement for predicting changes in Earth's climate.
The Radiometer Assessment using Vertically Aligned Nanotubes (RAVAN) CubeSat was launched into low-Earth orbit on Nov. 11, 2016, in order to test new...
A study led by scientists of the Max Planck Institute for the Structure and Dynamics of Matter (MPSD) at the Center for Free-Electron Laser Science in Hamburg presents evidence of the coexistence of superconductivity and “charge-density-waves” in compounds of the poorly-studied family of bismuthates. This observation opens up new perspectives for a deeper understanding of the phenomenon of high-temperature superconductivity, a topic which is at the core of condensed matter research since more than 30 years. The paper by Nicoletti et al has been published in the PNAS.
Since the beginning of the 20th century, superconductivity had been observed in some metals at temperatures only a few degrees above the absolute zero (minus...
Researchers from the University of Miami (UM) Rosenstiel School of Marine and Atmospheric Science, the Italian Space Agency (ASI), and the Instituto Geofisico--Escuela Politecnica Nacional (IGEPN) of Ecuador, showed an increasing volcanic danger on Cotopaxi in Ecuador using a powerful technique known as Interferometric Synthetic Aperture Radar (InSAR).
The Andes region in which Cotopaxi volcano is located is known to contain some of the world's most serious volcanic hazard. A mid- to large-size eruption has...
16.08.2017 | Event News
04.08.2017 | Event News
26.07.2017 | Event News
16.08.2017 | Physics and Astronomy
16.08.2017 | Materials Sciences
16.08.2017 | Interdisciplinary Research