Wednesday, 20. March 2013 20.03.13 08:54 Age: 5 Jahre

Putting Limits on Infinity
Safe Navigation in Complex Systems

Graph abstraction made vivid: Dominik Steenken and Steffen Ziegert (on the right) planning and avoiding errors

Can navigation networks with an infinite number of system conditions be programmed to be safe? So safe that they always meet all the safety requirements? It's difficult!

New traffic systems are emerging while the traffic density continues to increase – they need to be efficient, cost-effective and safe. The Paderborn RailCab System is one solution. But its development is complex because the reliability and safety of the navigation software must be guaranteed: Not only when the software is being used in traffic systems, but also in general for communication in networked structures. Conventional software tests cannot detect all the potential errors when large, complex systems are involved. Verifications offer more safety. But they are highly complex and cannot be handled by people alone when infinite system conditions are involved.

To state the question again: Can safety-critical systems be programmed to be safe when an infinite variety of conceivable errors is involved? Yes, it can be done! The research group led by Prof. Wehrheim uses technologies that build on model-driven software development (MDSD), a development concept for complex software systems. The goal of MDSD is to use formal techniques to generate functional software directly from abstract models.

Real navigation scenarios involve an extremely high number of possibilities which can result in ineffective behavior and even dangerous situations. Research assistant Dominik Steenken is striving to guarantee that such errors be avoided right from the start and uses shape analysis to do this: To verify the infinitely large number of possible conditions, he mathematically simplifies the structure of the graphs into an abstract model. The abstraction level is flexible and can be adapted to match the current problem. At the same time, the computer must be capable of recognizing meaningful structures: It should not abstract too little because the state space would then be infinite. Nor should it abstract too much because then the important characteristics would not be verifiable. With shape analysis, infinite graphs of real scenarios can be drastically reduced in size and represented by finite structures. Because the results from the abstracted model also apply to the original concrete model, dangerous situations can already be detected and remediated during the development process.

While Steenken ensures that the system does not contain any dangerous situations such as collisions, his colleague Steffen Ziegert optimizes state sequences with regard to economic aspects, examining concrete graphs and system conditions and planning future behaviors. It is a complex undertaking because he must consider various different factors. Which behavior is appropriate for reaching a particular goal as quickly as possible? How can a person drive both energy-efficiently and comfortably at the same time? Under these aspects, how can convoys be formed and conflicts avoided? In contrast to verification, Ziegert plans at runtime: While the system is in operation, the behavior of all the participants must be calculated continuously.

These methods not only significantly improve the navigation of RailCab. Through planning and error prevention, they ensure in general that it is possible to drive in complex systems safely and effectively. Even systems in engineering, the automotive industry and medical technology benefit from these results.

The research is part of the B1 project in "SFB 614 – Self-optimizing Concepts and Structures in Mechanical Engineering".

Contact:
Prof. Dr. Heike Wehrheim
Specification and Modeling of Software Systems
Tel: 05251 60-4331

wehrheim[at]uni-paderborn.de