October 2010 Theme: Mathematics Chasing Complexity

October 2010 Theme:
Mathematics Chasing Complexity

Guest Editor's Introduction by Michael Shafto

In commenting on Computer‘s September 2009 issue in his article “Really Rethinking Formal Methods,” (login required for full text) David Parnas challenges some of the core claims and assumptions underlying mathematical approaches to software modeling, model-checking, and related formal methods. He notes that there is a significant gap between formal methods and the practical world of software engineering. Not surprisingly, there is also a gap between software engineering and other engineering disciplines. Mathematics, which is supposed to be the common language that unites different science and engineering disciplines, seems to have failed in the case of computer science and software development.

The purpose of this month’s theme on Computing Now is to point out some new directions that might lead from formal methods into the traditional science and engineering disciplines and back again to computer science. These same lines of work seem also to be linking discrete mathematics to continuous mathematics, and perhaps to some degree reducing the gap between theoretical computer science and classical mathematics. These new directions have to do, in general, with modeling.

These new directions in modeling arise in part from the inescapable challenges of dealing with increasingly complex systems. These challenges are driving requirements for exceptionally high-fidelity modeling and reliable simulation of hybrid systems, as illustrated by three articles in this theme: “Getting Diagnostic Reasoning off the Ground: Maturing Technology with Tacsat-3” (login required for full text) by Ryan Mackey and colleagues, “Policy-Based Design of Human-Machine Collaboration in Manned Space Missions” (login required for full text) by Jurriaan van Diggelen and colleagues, and “Measuring Performance in Real Time during Remote Human-Robot Operations with Adjustable Autonomy” (login required for full text) by Debra Schreckenghost, Tod Milam, and Terrence Fong. These research efforts illustrate the use of high-fidelity simulation, agent-based architectures, and empirical analog-environment studies to increase understanding of and confidence in complex aerospace systems. All these methods, however, have limitations—limitations that are well-known in the world of formal methods. They all depend on searching a tiny subset of the space of possible system states.

Researchers in computer science, hybrid control theory, system health management, and human-system interaction have become quite familiar with the state-space explosion problem, and they have begun to do something about it. One line of work that seems promising involves sophisticated physical modeling. In their article “Classification of Physical Interactions between Two Subjects,” (login required for full text) Ruzena Bajcsy and colleagues, for example, are trying to solve theoretical and practical problems of interacting systems with complex nonlinear dynamics. This work primarily concerns complex physical interactions. Mirco Tribastone and Stephen Gilmore in “Automatic Translation of UML Sequence Diagrams into PEPA Models,” (login required for full text) on the other hand, are interested in complex communication and control interactions as represented by UML diagrams.

For our thematic purposes, however, these two efforts represent an emerging direction that could help reduce the gaps Parnas has described. The methods that Bajcsy and colleagues use for physical modeling are not far removed from methods that are equally applicable to hybrid control systems. The Performance Evaluation Process Algebra methodology of Tribastone and Gilmore, while firmly rooted in formal methods, has recently been extended to biology, chemistry, and other areas of science and engineering. Both of these efforts illustrate the current trend toward integrating discrete and continuous mathematics, providing a more flexible tool-kit for analyzing, designing, and controlling complex systems. For more information on this topic, please take a look at these Related Resources below.