Forum for Science, Industry and Business

Sponsored by:     3M 
Search our Site:

 

Carnegie Mellon methods keep bugs out of software for self-driving cars

22.06.2011
Analysis verifies safety of distributed car control system

Driver assistance technologies, such as adaptive cruise control and automatic braking, promise to someday ease traffic on crowded routes and prevent accidents. Proving that these automated systems will work as intended is a daunting task, but computer scientists at Carnegie Mellon University have now demonstrated it is possible to verify the safety of these highly complex systems.

To do so, the researchers first developed a model of a distributed car control system in which computers and sensors in each car combine to control acceleration, braking and lane changes, as well as entering and exiting the highway. They then used mathematical methods to formally verify that the system design would keep cars from crashing into each other.

"The system we created is in many ways one of the most complicated cyber-physical systems that has ever been fully verified formally," said Andre Platzer, an assistant professor of computer science. He and his collaborators, Ph.D. students Sarah M. Loos and Ligia Nistor, will present their findings at the International Symposium on Formal Methods, June 22 at the University of Limerick, Ireland.

"Auto accidents cost society billions of dollars and too many lives, so automated systems that could increase both the safety and efficiency of our roads only make sense," Platzer said. "It would be foolish to move to such a system, however, unless we can be certain that it won't create problems of its own. The dynamics of these systems have been beyond the scope of previous formal verification techniques, but we've had success with a modular approach to detecting design errors in them."

Formal verification methods are routinely used to find bugs in computer circuitry and software; Platzer is a leader in developing new techniques to verify complex computer-controlled devices such as aircraft collision avoidance systems and robotic surgery devices, known collectively as cyber-physical systems, or hybrid systems. He also is a member of the Computational Modeling and Analysis of Complex Systems (CMACS) center, a CMU-based initiative sponsored by the National Science Foundation to apply verification techniques to a variety of complex biological or physical systems.

Using these formal methods to either find errors in automated vehicle control or prove they are safe is particularly challenging, Platzer said. Like other cyber-physical systems, they must take into account both physical laws and the capabilities of the system's hardware and software. But vehicle control systems add another layer of complexity because they are distributed systems — that is, no single computer is ultimately in control, but rather each vehicle makes decisions in concert with other vehicles sharing the same road.

Platzer, Loos and Nistor showed that they could verify the safety of their adaptive cruise control system by breaking the problem into modular pieces and organizing the pieces in a hierarchy. The smallest piece consists of just two cars in a single lane. Building on that, they were able to prove that the system is safe for a single lane with an arbitrary number of cars, and ultimately for a highway with an arbitrary number of lanes. Likewise, they were able to show that cars could safely merge in and out of a single lane and then extended it to prove that cars could safely merge across a multi-lane highway.

Platzer cautioned that this proof has a major limitation — it only applies to straight highway. Addressing the problem of curved lanes, sensory inaccuracy and time synchronization are among the issues that will be a focus of future work. The methods the Carnegie Mellon researchers developed can, however, be generalized to other system designs or to variations in car dynamics.

"Any implementation of a distributed car control system would be more complicated than the model we developed," Platzer said. "But now at least we know that these future systems aren't so complex that we can't verify their safety."

This research was supported by the National Science Foundation and the Office of Naval Research. Follow the Carnegie Mellon School of Computer Science on Twitter @SCSatCMU.

About Carnegie Mellon University: Carnegie Mellon (www.cmu.edu) is a private, internationally ranked research university with programs in areas ranging from science, technology and business, to public policy, the humanities and the arts. More than 11,000 students in the university's seven schools and colleges benefit from a small student-to-faculty ratio and an education characterized by its focus on creating and implementing solutions for real problems, interdisciplinary collaboration and innovation. A global university, Carnegie Mellon's main campus in the United States is in Pittsburgh, Pa. It has campuses in California's Silicon Valley and Qatar, and programs in Asia, Australia, Europe and Mexico. The university is in the midst of a $1 billion fundraising campaign, titled "Inspire Innovation: The Campaign for Carnegie Mellon University," which aims to build its endowment, support faculty, students and innovative research, and enhance the physical campus with equipment and facility improvements.

Byron Spice | EurekAlert!
Further information:
http://www.cmu.edu

More articles from Automotive Engineering:

nachricht When your car knows how you feel
20.12.2017 | FZI Forschungszentrum Informatik am Karlsruher Institut für Technologie

nachricht Did you know how many parts of your car require infrared heat?
23.10.2017 | Heraeus Noblelight GmbH

All articles from Automotive Engineering >>>

The most recent press releases about innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: Attoseconds break into atomic interior

A newly developed laser technology has enabled physicists in the Laboratory for Attosecond Physics (jointly run by LMU Munich and the Max Planck Institute of Quantum Optics) to generate attosecond bursts of high-energy photons of unprecedented intensity. This has made it possible to observe the interaction of multiple photons in a single such pulse with electrons in the inner orbital shell of an atom.

In order to observe the ultrafast electron motion in the inner shells of atoms with short light pulses, the pulses must not only be ultrashort, but very...

Im Focus: Good vibrations feel the force

A group of researchers led by Andrea Cavalleri at the Max Planck Institute for Structure and Dynamics of Matter (MPSD) in Hamburg has demonstrated a new method enabling precise measurements of the interatomic forces that hold crystalline solids together. The paper Probing the Interatomic Potential of Solids by Strong-Field Nonlinear Phononics, published online in Nature, explains how a terahertz-frequency laser pulse can drive very large deformations of the crystal.

By measuring the highly unusual atomic trajectories under extreme electromagnetic transients, the MPSD group could reconstruct how rigid the atomic bonds are...

Im Focus: Developing reliable quantum computers

International research team makes important step on the path to solving certification problems

Quantum computers may one day solve algorithmic problems which even the biggest supercomputers today can’t manage. But how do you test a quantum computer to...

Im Focus: In best circles: First integrated circuit from self-assembled polymer

For the first time, a team of researchers at the Max-Planck Institute (MPI) for Polymer Research in Mainz, Germany, has succeeded in making an integrated circuit (IC) from just a monolayer of a semiconducting polymer via a bottom-up, self-assembly approach.

In the self-assembly process, the semiconducting polymer arranges itself into an ordered monolayer in a transistor. The transistors are binary switches used...

Im Focus: Demonstration of a single molecule piezoelectric effect

Breakthrough provides a new concept of the design of molecular motors, sensors and electricity generators at nanoscale

Researchers from the Institute of Organic Chemistry and Biochemistry of the CAS (IOCB Prague), Institute of Physics of the CAS (IP CAS) and Palacký University...

All Focus news of the innovation-report >>>

Anzeige

Anzeige

VideoLinks
Industry & Economy
Event News

2nd International Conference on High Temperature Shape Memory Alloys (HTSMAs)

15.02.2018 | Event News

Aachen DC Grid Summit 2018

13.02.2018 | Event News

How Global Climate Policy Can Learn from the Energy Transition

12.02.2018 | Event News

 
Latest News

Basque researchers turn light upside down

23.02.2018 | Physics and Astronomy

Finnish research group discovers a new immune system regulator

23.02.2018 | Health and Medicine

Attoseconds break into atomic interior

23.02.2018 | Physics and Astronomy

VideoLinks
Science & Research
Overview of more VideoLinks >>>