Below are the first 10 and last 10 pages of uncorrected machine-read text (when available) of this chapter, followed by the top 30 algorithmically extracted key phrases from the chapter as a whole.
Intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text on the opening pages of each chapter. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.
Do not use for reproduction, copying, pasting, or reading; exclusively for search engines.
OCR for page 116
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force B Virtual Engineering: Toward a Theory for Modeling and Simulation of Complex Systems John Doyle, California Institute of Technology INTRODUCTION This paper is a primer surveying a wide range of issues tied together loosely in a problem domain tentatively referred to as “virtual engineering ” (VE). This domain is concerned with modeling and simulation of uncertain, heterogeneous, complex, dynamical systems—the very kind of M&S on which much of the vision discussed in this study depends. Although the discussion is wide ranging and concerned primarily with topics distant from those usually discussed by the Department of the Navy and DOD modeling communities, understanding how those topics relate to one another is essential for appreciating both the potential and the enormous intellectual challenges associated with advanced modeling and simulation in the decades ahead. BACKGROUND Perhaps the most generic trend in technology is the creation of increasingly complex systems together with a greater reliance on simulation for their design and analysis. Large networks of computers with shared databases and high-speed communication are used in the design and manufacture of everything from microchips to vehicles such as the Boeing 777. Advances in technology NOTE: This appendix benefited from material obtained from many people and sources: Gabriel Robins on software, VLSI, and the philosophy of modeling, Will O'Neil on CFD, and many colleagues and students.
OCR for page 117
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force have put us in the interesting position of being limited less by our inability to sense and actuate, to compute and communicate, and to fabricate and manufacture new materials, than by how well we understand, design, and control their interconnection and the resulting complexity. While component-level problems will continue to be important, systems-level problems will be even more so. Further, “components” (e.g., sensors) increasingly need to be viewed as complex systems in their own right. This “system of systems” view is coming to dominate technology at every level. It is, for example, a basic element of DOD's thinking in contexts involving the search for dominant battlefield awareness (DBA), dominant battlefield knowledge (DBK), and long-range precision strike. At the same time, virtual reality (VR) interfaces, integrated databases, paperless and simulation-based design, virtual prototyping, distributed interactive simulation, synthetic environments, and simultaneous process/product design promise to take complex systems from concept to design. The potential of this still-nascent approach is well appreciated in the engineering and science communities, but what “it” is is not. For want of a better phrase, we refer to the general approach here as “virtual engineering” (VE). VE focuses on the role of M&S in uncertain, heterogeneous, complex, dynamical systems—as distinct from the more conventional applications of M&S. But VE, like M&S, should be viewed as a problem domain, not a solution method. In this paper, we argue that the enormous potential of the VE vision will not be achieved without a sound theoretical and scientific basis that does not now exist. In considering how to construct such a base, we observe a unifying theme in VE: Complexity is a by-product of designing for reliable predictability in the presence of uncertainty and subject to resource limitations. A familiar example is smart weapons, where sensors, actuators, and computers are added to counter uncertainties in atmospheric conditions, release conditions, and target movement. Thus, we add complexity (more components, each with increasing sophistication) to reduce uncertainties. But because the components must be built, tested, and then connected, we are introducing not only the potential for great benefits, but also the potential for catastrophic failures in programs and systems. Evaluating these complexity versus controllability tradeoffs is therefore very important, but also can become conceptually and computationally overwhelming. Because of the critical role VE will play, this technology should be robust, and its strengths and limitations must be clearly understood. The goal of this paper is to discuss the basic technical issues underlying VE in a way accessible to diverse communities—ranging from scientists to policy makers and military commanders. The challenges in doing so are intrinsically difficult issues, intensely mathematical concepts, an incoherent theoretical base, and misleading popular expositions about “complexity.”
OCR for page 118
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force APPROACH In this primer on VE, we concentrate on “physics-based” complex systems, but most of the issues apply to other M&S areas as well, including those involving “intelligent agents.” Our focus keeps us on a firmer theoretical and empirical basis and makes it easier to distinguish the effects of complexity and uncertainty from those of simple lack of knowledge. Our discussion also departs from the common tendency to discuss VE as though it were a mere extension of software engineering. Indeed, we argue that uncertainty management in the presence of resource limitations is the dominant technical issue in VE, that conventional methods for M&S and analysis will be inadequate for large complex systems, and that VE requires new mathematical and computational methods (VE theory, or VET). We need a more integrated and coherent theory of modeling, analysis, simulation, testing, and model identification from data, and we must address nonlinear, interconnected, heterogeneous systems with hierarchical, multi-resolution, variable-granularity models—both theoretically and with suitable software architectures and engineering environments. Although the foundations of any VE theory will be intensely mathematical, we rely here on concrete examples to convey key ideas. We start with simple physical experiments that can be done easily with coins and paper to illustrate dynamical systems concepts such as sensitivity to initial conditions, bifurcation, and chaos. We also use these examples to introduce uncertainty modeling and management. Having introduced key ideas, we then review major success stories of what could be called “proto-VE” in the computer-aided design (CAD) of the Boeing 777, computational fluid dynamics (CFD), and very large scale integrated circuits (VLSI). While these success stories are certainly encouraging, great caution should be used in extrapolating to more general situations. Indeed, we should all be sobered by the number of major failures that have already occurred in complex engineering systems such as the Titanic, Tacoma-Narrows bridge, Denver baggage-handling system, and Ariane booster. We argue that uncertainty management together with dynamics and interconnection is the key to understanding both these successes and failures and the future challenges. We then discuss briefly significant lessons from software engineering and computational complexity theory. There are important generalizable lessons, but—as we point out repeatedly—software engineering is not a prototype for VE. Indeed, the emphasis on software engineering to the exclusion of other subjects has left us in a virtual “pre-Copernican” stage in important areas having more to do with the content of M&S for complex systems. Against this background, we draw implications for VE. We go on to relate these implications to famous failures of complex engineering systems, thereby demonstrating that the issues we raise are not mere abstractions, and that achieving the potential of VE (and M&S) will be enormously challenging. We touch
OCR for page 119
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force briefly on current examples of complex systems (smart weapons and airbags) to relate discussion to the present. We then discuss what can be learned from control theory and its evolution as we move toward a theory of VE. At that point, we return briefly to the case studies to view them from the perspective of that emerging theory. Finally, we include a section on what we call “soft computing,” a domain that includes “complex-adaptive-systems research, ” fuzzy logic, and a number of other topics on which there has been considerable semi-popular exposition. Our purpose is to relate these topics to the broader subject of VE and to provide readers with some sense of what can be accomplished with “soft computing” and where other approaches will prove essential. In summary before getting into our primer, we note that several trends in M&S of complex systems are widely appreciated, if not well understood. There is an increasing emphasis on moving problems and models from linear to nonlinear; from static to dynamic; and from isolated and homogeneous to heterogeneous, interconnected, hierarchical, and multi-resolution (or variable granularity and fidelity). What is poorly understood is the role of uncertainty, which we claim is actually the origin of all the other trends. Model uncertainty arises from the differences between the idealized behavior of conventional models and the reality they are intended to represent. The need to produce models that give reliable predictability of complex phenomena, and thus have limited uncertainty, leads to the explicit introduction of dynamics, nonlinearity, and hierarchical interconnections of heterogeneous components. Thus the focus of this paper is that uncertainty is the key to understanding complex systems. INTRODUCTION TO CENTRAL CONCEPTS Dynamical Systems A few simple thought experiments can illustrate the issues of uncertainty and predictability—as well as of nonlinearity, dynamics, heterogeneity, and ultimately complexity. Most of the experiments we discuss here can also be done with ordinary items like coins and paper. Consider a coin-tossing mechanism that imparts a certain linear and angular velocity on a coin, which is then allowed to bounce on a large flat floor, as depicted in Figure B.1 . Without knowing much about the mechanism, we can reliably predict that the coin will come to rest on the floor. For most mechanisms, it will be impossible to predict whether it will be heads or tails. Indeed, heads or tails will be equally likely, and any sequence of heads or tails will be equally likely. Such specific predictions are as reliably unpredictable as the eventual stopping of the coin is predictable. The reliable unpredictability of heads or tails is a simple consequence of the sensitivity to initial conditions that is almost inevitable in such a mechanism. The coin will bounce around on the floor in an apparently random and erratic manner
OCR for page 120
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force FIGURE B.1 Coin tossing experiment. before eventually coming to rest on the floor. The coin's trajectory will be different in detail for each different toss, in spite of efforts to make the experiment repeatable. Extraordinary measures would be needed to ensure predictability (e.g., dropping the coin heads up a short distance onto a soft and sticky surface, so as always to produce heads). Sensitivity to initial conditions (STIC) can occur even in simple settings such as a rigid coin in a vacuum with no external forces, not even gravity. With zero initial velocity, the coin will remain stationary, but the smallest initial non-zero velocity will cause the coin to drift away with distance proportional to time. The dynamics are linear and trivial. This points out that—in contrast with what is often asserted—sensitivity to initial conditions is very much a linear phenomenon. Moreover, even in nonlinear systems, the standard definition of sensitivity involves examining infinitesimal variations about a given trajectory and examining the resulting linear system. Thus even in nonlinear systems, sensitivity to initial conditions boils down to the behavior of linear systems. What nonlinearity contributes is making it more difficult to completely characterize the consequences of sensitivity to initial conditions. Sensitivity to initial conditions is also a matter of degree; the coin-in-free-space example being on the boundary of systems that are sensitive to initial conditions. Errors in initial conditions of the coin lead to a drifting of the trajectories that grows linearly with time. In general, the growth can be exponential, which is more dramatic. If we add atmosphere, but no other external force, the coin will eventually come to rest no matter what the initial velocities, so this
OCR for page 121
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force is clearly less sensitive to initial conditions than the case with no atmosphere. A coin in a thick, sticky fluid like molasses is even less sensitive. Not all features of our experiment are sensitive to initial conditions. The final vertical position is reliably predictable, the time at which the coin will come to rest is less so, the horizontal resting location even less so, and so on, with the heads or tails outcome perfectly unpredictable. It follows that any notion of complexity cannot be attributed to the system, but must include the property of it that is in question. EXPONENTIAL GROWTH, CHAOS, AND BIFURCATION We can get a better understanding of sensitivity to initial conditions with some elementary mathematics. Suppose we have a model of the form x(t+1) = f(x(t)). This tells us what the state variable x is at time t+1 as a function of the state x at time t. This is called a difference equation, which is one way to describe a dynamical system—i.e., one that evolves with time. If we specify x(t) at some time, say t = 0, then the formula x(t+1) = f(x(t)) can be applied recursively to determine x(t) for all future times t = 1,2,3, . . . . This determines an orbit or trajectory of the dynamical system. This only gives x at discrete times, and x is undefined elsewhere. It is perhaps more natural to model the coin and other physical systems with differential equations that specify the state at all times, but difference equations are simpler to understand. For the coin, the state would include at least the positions and velocities of the coin, and possibly some variables to describe the time evolution of the air around the coin. If the coin were flexible, the state might include some description of the bending and its rate. And so on. A scalar linear difference equation is of the form x(t+1) = ax(t), where a is a constant (the vector case is x(t+1) = Ax(t), where A is a matrix). If x(0) is given, the solution for all time is x(t) = atx(0). Thus, if a>1, nonzero solutions grow exponentially and the system is called unstable. Since the system is linear, any difference in initial conditions will also grow exponentially. (If a<1, then solutions decay exponentially to zero and the origin is a stable fixed point.) Exponential growth appears in so many circumstances that it is worth dramatizing its consequences. If a = 10, then in each second x gets 10 times larger, and after 100 seconds it is 10100 larger. With this type of exponential growth, an error smaller than the nucleus of a hydrogen atom would be larger than the diameter of the known universe in less than 100 seconds. Of course, no physical system could have this as a reasonable model for long time periods. The point is that linear systems can exhibit very extreme sensitivity to initial conditions because of exponential growth. Of course, STIC is a matter of degree. The quantity ln(a) is one measure of the degree of STIC and is called the Lyapunov exponent. Suppose we modify our scalar linear system slightly to make it the nonlinear system x(t+1) = 10x(t) mod10 and restrict the state to the interval [0,10]. This system can be thought of as taking the decimal expansion of x(t) and shifting the
OCR for page 122
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force decimal point to the right and then truncating the digit to the left of the units place. For example, if x(0) = p = 3.141592 ..., then x(1) = 1.41592 ... and x(2) = 4.1592 ... and so on. This still has, in the small, the same exponential growth as the linear system, but its orbits stay bounded. If x(0) is rational, then the x(t) will be periodic, and thus there are a countable number of periodic orbits (arbitrarily long periods). If x(0) is irrational, then the orbit will stay irrational and not be periodic, but it will appear exactly as random and irregular as the irrational initial condition. As is well-known, this system exhibits deterministic chaos. The Lyapunov exponent can also be generalized to nonlinear systems, and in this case would still be ln(a). The several alternative mathematical definitions of chaos are all beyond the scope of this paper, but the essential features of chaotic systems are sensitivity to initial conditions (STIC), periodic orbits with arbitrarily long periods, and an uncountable set of bounded nonperiodic (and apparently random) orbits. The STIC property and the large number of periodic orbits can occur in linear systems. But the “arbitrarily long periods” and “bounded, nonperiodic, apparently random ” features require some nonlinearity. Chaos has received much attention in the popular press, which often confuses nonlinearity and sensitivity to initial conditions in suggesting that the former in some way causes the latter, when in fact both are independent and necessary but not sufficient to create chaos. The formal mathematical definitions of chaos involve infinite time horizon orbits, so none of our examples so far would be, strictly speaking, chaotic. A simple way to get a system that is closer in spirit to chaos would be to put our coin in a box and then shake the box with some periodic motion. Even though the box had regular motion, under many circumstances the coin's motion in bouncing around the box would appear random and irregular. A simple model with linear dynamics between collisions and a linear model for the collisions with the box would almost certainly be chaotic, although even this simple system is too complicated to prove the existence of chaos rigorously and it must be suggested via simulation. Very few dynamical systems have been proved chaotic, and most models of physical systems that appear to exhibit chaos are only suggested to be so by simulation. One-degree-of-freedom models of a ball in a cylinder with a closed top and a periodically moving piston have been proved chaotic. The ball typically bounces between the piston and the other end wall of the cylinder with the impact times being random, even though the dynamics are purely deterministic, and even piecewise linear. To get a sense of the notion of bifurcation in dynamical systems, consider the following experiment. Drop a quarter in as close to a horizontal position and with as little initial velocity as possible. It will drop nearly straight down, and the air will have little effect at the speeds the coin will attain while it bounces around the floor. Now take a quarter-size piece of paper and repeat the experiment. The paper will begin fluttering rapidly and fall toward the floor at a large angle, landing far away from where a real quarter would have first hit the floor. This is
OCR for page 123
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force an example of a bifurcation, where a seemingly small change in properties creates a dramatic change in behavior. The heavy coin will reliably and predictably hit the floor beneath where it is dropped (at which point subsequent collisions may make what follows it quite unpredictable), whereas the paper coin will spin off in any direction and land far away, but then quickly settle down without bouncing. Thus one exhibits STIC, while the other does not. A simple variant on this experiment illustrates a bifurcation more directly. Make two photocopies of the diagram in Figure B.2 (or just fold pieces of paper as follows), and cut out the squares along the solid line. The unfolded paper will flutter erratically when dropped, exhibiting STIC. Next, take one of the papers and fold it along one of the dashed lines to create a rectangularly shaped object. Turn the object so that the long side is vertical. Then make two triangular folds from the top left and bottom left corners along the dotted lines to produce a small funnel-shaped object. If this is dropped it will quickly settle into a nice steady fall at a terminal velocity with the point down. This is known as a relative equilibrium in that all the state variables are constant, except the vertical position, which is decreasing linearly. It is locally stable since small perturbations keep the trajectories close, and is also globally attracting in the sense that all initial conditions eventually lead to this steady falling. If the folds are then smoothed out by flattening the paper more back to its prefolded shape, then only when the paper is dropped very carefully will it fail to flutter. This nearly flat paper has a relative equilibrium consisting of flat steady falling, but the basin of attraction of this equilibrium is very small. That is, the more folded the paper is, the larger the set of initial conditions that will lead to steady falling. If the folds are sharp enough and the distance to the floor great enough, then no matter how the paper is dropped it will eventually orient itself so the point is down, and then fall steadily. This large change in qualitative behavior as a parameter of the system is changed (in this case, the degree of folding) is the subject of bifurcation analysis FIGURE B.2 Proper folding diagram for bifurcation experiment.
OCR for page 124
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force within the theory of dynamical systems theory. In these examples, bifurcation analysis could be used to explore why a regular coin shows STIC only after the first collision, while the paper coin shows it only up to hitting the floor, as well as why the dynamics of the folded paper change with the degree of folding. Of course, bifurcation analysis applies to mathematical models, and developing such models for these examples is not trivial. To develop models that reproduce the qualitative behavior we see in these simple experiments requires advanced undergraduate level aerodynamics. These models will necessarily be nonlinear if they are to reproduce the fluttering motion, as this requires a nontrivial nonlinear model for the fluids. Bifurcation is related to chaos in that bifurcation analysis has often been an effective tool to study how complex systems transition from regular behavior to chaotic behavior. While chaos per se may be overrated, the underlying concepts of sensitivity to initial conditions and bifurcation, and more generally the role of nonlinear phenomena, are critical to the understanding of complex systems. The bottom line is as follows: We can make models from components that are simple, predictable, deterministic, symmetric, and homogeneous, and yet produce behavior that is complex, unpredictable, chaotic, asymmetric, and heterogeneous. Of course, in engineering design we want to take components that may be complex, unpredictable, chaotic, asymmetric, and heterogeneous and interconnect them to produce simple, reliable, predictable behavior. We believe that the deeper ideas of dynamical systems will be important ingredients in this effort. Complexity It is tempting to view complexity in this context as something that arises in a mystical way between complete order (that the coin will come to rest) and complete randomness (heads or tails) and to settle on chaotic systems as prototypically complex. We prefer to view complexity in a different way. To make reliable predictions about, say, the final horizontal resting place, the distribution of horizontal resting positions, or the distribution of trajectories, we would need elaborate models about the experiment and measurements of properties of the mechanism, the coin, and the floor. We might also improve our prediction of, say, the horizontal resting location if we had a measurement of the positions and velocities of the coin at some instant after being tossed. This is because our suspicion would be that the greatest source of uncertainty is due to the tossing mechanism, and the uncertainty created by the air and the collisions with the floor will be less critical, but this would also have to be checked. The quality of the measurement would obviously greatly affect the quality of any resulting prediction, of course.
OCR for page 125
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force To produce a model that reliably predicted, say, the distribution of the trajectories could be an enormous undertaking, even for such a simple experiment. We would need to figure out the distributions of initial conditions imparted on the coin by the tossing mechanism, the dynamics of the trajectories of the coin in flight, and the dynamics of the collisions. The dynamics of the coin in the air is linear if the fluid/coin interaction is ignored or if a naive model of the fluid is assumed. If the coin is light, and perhaps flexible, then such assumptions may allow for too much uncertainty, and a nonlinear model with dynamics of the coin/ fluid interaction may be necessary (imagine a “coin” made from thin paper, or replace air by water as the fluid). If the coin flexibility interacts with the fluid sufficiently, we could quickly challenge the state of the art in computational fluid dynamics. The collisions with the floor are also tricky, as they involve not only the elastic properties of the coin and floor, but the friction as well. This now takes us into the domain of friction modeling, and we could again soon be challenging the state of the art. Even for this simple experiment, if we want to describe detailed behavior we end up with nonlinear models with complex dynamics and the physics of the underlying phenomena is studied in separate domains. It will be difficult to connect the models of the various phenomena, such as fluid/coin interaction, and the interacting of elasticity of the floor and coin with frictional forces. It is the latter feature that we refer to as heterogeneity. Heterogeneity is mild in this example since the system is purely mechanical, and the collisions with the floor are relatively simple. Our view of complexity, then, is that it arises as a direct consequence of the introduction of dynamics, nonlinearities, heterogeneity, and interconnectedness intended to reduce the uncertainty in our models so that reliable predictions can be made about some specific behavior of our system (or its unpredictability can be reliably confirmed in some specific sense, which amounts to the same thing). Complexity is not an intrinsic property of the system, or even of the question we are asking, but in addition is a function of the models we choose to use. We can see this in the coin tossing example, but a more thorough understanding of complexity will require the richer examples studied in the rest of this paper. While this view of complexity has the seemingly unappealing feature of being entirely in the eye of the beholder, we believe this to be unavoidable and indeed desirable: Complexity cannot be separated from our viewpoint. Uncertainty Modeling and Management Up to this point, we have been rather vague about just what is meant by uncertainty, predictability, and complexity, but we can now give some more details. For our coin toss experiment, we would expect that repeated tosses would produce rather different trajectories, even when we set up the tossing mechanism identically each time to the extent we can measure. There would
OCR for page 126
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force presumably be factors beyond our control and beyond our measurement capability. Thus any model of the system that used only the knowledge available to us from what we could measure would be intrinsically limited in its ability to predict the exact trajectory by the inherent nonrepeatability of the experiment. The best we could hope for in a model would be to reliably predict the possible trajectories in some way, either as a set of possible trajectories or in terms of some probability distribution. Thus we ideally would like to explicitly represent this uncertainty in our model. Note that the uncertainty is in our model (and the data that goes with it). It is we—not nature—who are uncertain about each trajectory. 1 We now describe informally the mechanisms by which we would introduce uncertainty into our models. Parametric Uncertainty A special and important form of uncertainty is parametric uncertainty, which arises in even the simplest models such as attempting to predict the detailed trajectory of a coin. Here the “parameters” include the coin's initial conditions and moments of inertia, and the floor's elasticity and friction. Parameters are associated with mechanisms that are modeled in detail but have highly structured uncertainty. Roughly speaking, all of the “inputs” to a simulation model are parameters in the sense we use the term here. 2 How do we deal with parametric uncertainty (see also Appendix D )? Average case. If only average or typical behavior is of interest, this can be easily evaluated with a modest number of repeated Monte Carlo simulations with random initial conditions. In this case the presence of parametric uncertainty adds little difficulty beyond the cost of a single simulation. Also, in the average case the number of parameters does not make much difference, as estimates of probability distributions of outcomes do not depend on the number of parameters. Linear models. If the parameters enter linearly in the model, the resulting uncertainty is often easy to analyze. To be sure, we can have extreme sensitivity to initial conditions, but the consequences are easily understood. Consider the linear dependence of the velocity and position of the first floor collision as a function of the initial velocities and positions of the coin. A set in the initial 1 Except in our discussion of VLSI later in this appendix, we ignore quantum mechanics and the intrinsically probabilistic behaviors associated with it. Quantum effects are only very rarely significant for the systems of interest here. 2 Some workers distinguish between “parameters” that can be changed interactively at run time, or in the course of a run, and “fixed data,” that can be changed only by recompiling the database. Both are parameters for the purposes of this paper.
OCR for page 160
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force Smart Weapons and Airbags In smart weapons, sensors, actuators, and computers are added to counter uncertainties in atmospheric conditions, release conditions, and target movement. This yields reduced sensitivity to uncertainties in the environment, but at the price of increased sensitivity to a large number of new components. If a sensor or actuator component fails, the weapon may actually have much worse accuracy than a dumb weapon. If we are careful in our design, we can use this shift in vulnerability from uncertainty in the environment to uncertainty in our components to our great advantage by making sure that our critical components are sufficiently reliable. Interestingly, it could be argued that the most successful smart weapons so far have been the simplest, for example, Sidewinder and laserguided bombs. Automobile airbags also reduce vulnerability to uncertainties in the environment. With an airbag you are safer in a high-speed collision with, say, a drunk driver who has crossed into your lane. Since you have no direct control of the other driver's behavior, an airbag is one of the most cost-effective control strategies you can take. Unfortunately, there is again increased vulnerability to component failures. Even without component failures, airbags can make certain circumstances more dangerous. For example, a low-speed collision may cause the air bag to deploy even though without the airbag there would be no danger of injury. Thus one could be injured by the airbag itself under normal operation even when the system functions properly. This is particularly serious with small passengers, who may be in more danger with an airbag than without. Overall there is a substantial net reduction in fatalities, but increased danger of injury and death in certain circumstances for all people, and possibly a net increase in danger to smaller people. The awareness of the danger of airbags to children and small adults has provoked a flurry of research to make more advanced and more complex airbags. Proposed schemes include making the airbag deployment more adaptable to individual differences in size and body position by using infrared and ultrasonic sensors, together with weight sensors and capacitance sensors, which detect water in human bodies. Unfortunately, it is possible to fool these sensors as bags of groceries with a hot pizza sitting on a wet towel could presumably be mistaken for a person. Lower-technology solutions include simply setting the threshold for airbag deployment higher so they go off less frequently in slower-speed collisions. All these solutions again highlight that the design is driven by uncertainty management, and complexity is introduced as a by-product. What these two examples illustrate is a kind of conservation principle that is at work in complex systems. Indeed, as we will discuss later, control theory has several such conservation principles that are critical to understanding complex
OCR for page 161
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force systems. Informally, when we introduce new components to reduce the effects of uncertainty in the environment, we inevitably create increased vulnerability either to these new components, or to other uncertainties in the environment. Since we control the design, if we are careful we can use this tradeoff to our advantage and shift our vulnerability from things that are more uncertain to things that are less, but explicit models of uncertainty are critical in achieving this. Unfortunately, with increasing complexity, evaluating these tradeoffs can be conceptually and computationally overwhelming. The earlier section on software engineering discussed how large software development projects require a highly structured approach throughout, since interconnection management dominates component design. While this is now and always will be a challenging domain, it is still relatively homogeneous domain with limited uncertainty. Complex systems engineering has all of the challenges of software engineering plus heterogeneity (hardware and software plus chemical, electrical, mechanical, fluid, communications, and so on) and greater uncertainty (in environment and in system components). Complex systems remain even more poorly understood than large software systems. Complex systems are poorly understood in part simply because nonlinear, heterogeneous, interconnected, complex dynamical systems are intrinsically difficult to model and understand. But more importantly, the role of uncertainty is critical, but very poorly understood. Furthermore, scaling of problem size can make the interaction of these issues overwhelming. As we will see, control theory addresses uncertainty management explicitly, but from a very narrow perspective. A deeper understanding of complex systems is emerging, but in separate and fragmented technical disciplines. Finally, there is the “referee effect.” The referee effect comes from the observation that we notice referees only when they do a bad job. Similarly, we notice the details of our watches, televisions, phone systems, cars, planes, networks, and nuclear reactors only when they fail to provide reliable operation and shield us from the world's uncertainties. Basically, the product of a superior design process makes itself virtually invisible. Even when the design is flawed, it may appear to the user that the failure was due to some component, rather than an underlying design process. This is true in all the examples of failures above. Success or failure of components, including computer hardware and software, is relatively easily understood. The role of the system design process itself, deciding which components to use and how to interconnect them, remains a mystery outside of a narrow technical community. Thus complexity in engineering systems is very much in the eye of the beholder. A design engineer may deliberately introduce great complexity specifically for the purpose of providing the end user with an apparently simple and reliable system. The apparent complexity depends on the viewpoint, and traditionally the only global viewpoint is that of the control engineer.
OCR for page 162
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force LESSONS FROM CONTROLS Increasingly complex systems rely on advanced control systems, from cheap, fast computer disk drives to fly-by-wire aircraft to automobiles, integrated chemical production complexes, semiconductor manufacturing systems, and manned and unmanned space systems. Yet, ironically, control engineering and theory remain poorly understood outside of a narrow technical community. Traditionally, control engineers have been responsible for system integration because the control engineer adds the last component to a complex system, and does systemwide uncertainty management. Generally speaking, however, control theoreticians generally do not support this process. The situation is changing dramatically, and the trend is to more integration of system design and control design, but we need to accelerate this trend, and control theorists must expand their vision and make greater contact with other disciplines. Although control theory by itself offers only a piece of a potential foundation for a theory of VE, it provides a very important complement to dynamical systems and computer science because uncertainty management is the central issue in automatic control systems. The experience and successes and failures of control theory provide important technical foundation and additional insight into the potential role of theory in complex systems. Ironically, until the last 10 years, control theory and practical control engineering have had a very distant relationship. The old story was that since controls were the most mathematical part of engineering it should not be surprising that it simply took decades for theory to get from academia to practice. While this certainly has some truth, another view is that much of the theory was basically irrelevant, and the reason for this irrelevance was inadequate treatment of uncertainty. Tremendous progress has occurred in just the last decade in developing a mathematical theory of analysis of uncertain systems in the subfield of robust control. The new tools of structured uncertainty, integral quadratic constraints, linear matrix inequalities, operator theoretic methods, and so on, are well beyond the scope of this appendix, but a few observations can be made. The rate of transition from theory to practice has increased dramatically, and ironically, control theorists are doing theory that is both more mathematical and more relevant. Another important factor is that they are using modern software tools to get their theory into CAD design packages that are commercially available. Thus theory is now routinely used in industry before it has had time to get through the review and journal publication process. The former can take months, while the latter still takes years. One of the most important messages from control theory is that there are fundamental conservation laws associated with uncertainty management in complex, interconnected systems. The informal notion suggested by the smart weapon and airbag examples that vulnerability to uncertainty could not be absolutely reduced but could only be moved around has theoretical expression in the math-
OCR for page 163
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force ematics of control theory. There are conservation laws where the “conserved quantities” are related to net system-level robustness with respect to component and environmental uncertainty. Interestingly, some of these conservation laws (e.g., Bode's integral formula) are based on results that are up to 50 years old, although they are getting modern extensions. They do require upper division undergraduate mathematics to express, however, and are beyond the scope of this review. Like energy conservation, they limit the performance of interconnected systems, but with proper understanding can be manipulated to our advantage. Also, like energy conservation, attempts to violate them are constantly being attempted, often with catastrophic results. While control theory must play a central role in a theory of VE, current control theory has many inadequacies that must be addressed in this broader context. The first and most obvious is that control theorists take a very limited view of system interconnection, assuming that there is a fixed “plant” with a well-defined performance objective and a controller with adequate sensors, actuators, and computation to achieve the performance. The control design then amounts to solving for the “control laws” that yield the desired performance. This view of control is no longer relevant to even today's design environment where the systemwide control engineer's view of performance is needed at the earliest design stages. As cost-effective uncertainty management correctly takes its place as the dominant design issue, control engineers are forced to play a broader role, and control theory must catch up just to address the current needs, let alone the expanded needs of future VE. Another weakness of control theory is that it tends to treat uncertainty and nonlinearity completely separately. This has traditionally been a remarkably effective strategy. To illustrate this, consider the problem of reentry of the Shuttle orbiter. Viewed as a whole, the dynamics are extremely nonlinear, and there are substantial uncertainties. The strategy has traditionally been to use a simplified nonlinear model with no uncertainty to develop an idealized global trajectory for reentry, and then use a local linearized model to design a feedback controller to keep the vehicle close to the trajectory in the presence of uncertainty. The sources of uncertainty included atmospheric disturbances, unmodeled vehicle dynamics due primarily to unsteady aerodynamic and structural effects, parametric uncertainty in the mass distribution and aerodynamic coefficients, and nonlinearities. The nonlinearities include both those that were in the simplified global model, which have been eliminated through linearization, and also higher-order nonlinearities that were not represented even in the global model. Both are treated as sources of uncertainty in the linearized model. This strategy works well because the idealized trajectory creates a relative equilibrium about which a linearization is quite reasonable, and the effects of nonlinearities do not dominate the local behavior about the trajectories. It is easy to imagine many circumstances where this clean separation is not effective, because there is so much uncertainty that either the idealized trajectory is not meaningful or the local
OCR for page 164
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force behavior cannot be kept close enough to the idealized trajectory to allow the nonlinearities to be treated as uncertainties. Control theory also has other weaknesses that must be overcome. While mathematical sophistication is a strength of control theorists, they must overcome the natural distance this tends to create with other engineering disciplines. This is one reason why control theory has been applied to dynamical systems and computational complexity with some early successes, but has achieved less success in other areas. The limited connection with modeling and physics is even more troubling, as control theorists tend to view modeling as a mystical and unpleasant activity to be performed by others, hopefully far away. ANALYSIS OF UNCERTAIN DYNAMICAL SYSTEMS While even a superficial exposition of the current state of the art in analysis of uncertain dynamical systems requires mathematics well beyond the scope of this paper, it is possible to suggest some of the ideas and difficulties with simple drawings. Recall the interference analysis. We can think of a three-dimensional solid component as being defined as a subset of real Euclidean 3-space. Thus, interference analysis is checking for any intersections of these subsets other than those that are specified. We can similarly think of components in a dynamical system as being defined as subsets of all the possible time trajectories that their state and boundary conditions can take. Thus, a circuit component can be thought of as specifying some set of currents and voltages, a mechanical component as specifying some set of velocities, positions, and forces, and so on. These sets are potentially very complicated as they are subsets of infinite dimensional spaces of time trajectories. Differential equations can be thought of as constraints that determine the set of behaviors. An interconnection of components is equivalent to the intersection of the subsets that describe their behaviors. For example, two circuit elements connected at their terminals each constrains the signals between them, and an interconnection simply means that the constraints of both components are in effect. Engineering design may then be thought of as connecting components in such a way as to produce only a certain desired set of behaviors and no others. Undesirable behaviors are analogous to undesirable interferences in three-dimensional solids, in that they involve unwanted intersections of sets. To make this point of view more concrete, recall the fluttering paper example, and assume we use a rigid body model of the paper in a case where the folds are fairly flat. The boundary conditions between the air and paper consist of the paper's position and orientation and their rates and the forces between the paper and the air. Both the paper and the air model put constraints on what these variables can be, and dropping the paper in air forces both sets of constraints to hold simultaneously. One solution consistent with the constraints is steady fall-
OCR for page 165
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force ing, but there are other fluttering motions that are also possible. The challenge in complex systems is discovering these extra solutions that may be undesirable. If components are linear with no uncertainty, then their sets of behaviors are linear subspaces, and it is relatively easy to check globally for undesirable interconnections. This would be analogous to the three-dimensional solids all being just lines and planes. Uncertain or nonlinear components are more complicated to analyze. Very simple uncertain linear problems are NP hard, and simple nonlinear problems are undecidable. The strategy that has been exploited very successfully in robust control theory is a natural generalization of the bounding box idea to this setting of components of dynamical systems. Here the bounding boxes are in infinite dimensional spaces, and checking for their intersection requires sophisticated mathematical and computational machinery. So far, this is the only known method that successfully handles both parametric uncertainty and unmodeled dynamics and overcomes to some extent the intractability of these problems. While the generalized bounding box methods (they are not called this in robust control theory, but are referred to with a variety of other, more technical terms) have been successful in control systems analysis and design (they are widely used throughout the world), their application outside of controls has been limited. What is particularly needed now is to put these methods more in the context of component interconnections, not just the plant-controller paradigm of standard control theory. Also, there remains a great need for methods to analyze uncertainty and nonlinearity together in some nontrivial way. Developing bifurcation analysis tools that allow for uncertainty would be a good initial step, and research in this direction is under way. In robustness analysis of uncertain systems, it is usually much easier to find a failure if one exists than to guarantee that none exist when that is the case. This inherent asymmetry is present in three-dimensional interference analysis and software design and will be a major feature of VE. We must try to overcome this as much as possible, but recognize that a substantial asymmetry is unavoidable. CASE STUDIES REVISITED While we are far from having an integrated theory of VE, we can gather the various ideas we have discussed from dynamical systems, computer science, and control theory and briefly revisit the case studies. The success stories in the 777 solid modeling, in CFD, and in VLSI are encouraging, but extrapolation to the broader VE enterprise must be done with caution. Each success depends on very special features of the problem area, and there are substantial challenges within even these limited domains to extending the existing tools. None of these areas has faced up to uncertainty management in heterogeneous systems, though all are being increasingly faced with exactly that issue. Among the failures considered, the Estonia Ferry disaster is the one most
OCR for page 166
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force FIGURE B.11 Other foundations for VE theory. likely to have benefited from the use of three-dimensional solid CAD tools such as were used for the 777. The Titanic, Tacoma Narrows Bridge, subsynchronous resonance, and Ariane 5 failures can all be traced to specific unmodeled dynamics whose analysis, had it been considered, was well within the capability available at the time. Thus it is easy after the fact to view these as simple problems with simple solutions, but the deeper question is whether a disciplined and systematic approach to VE would help avoid such mishaps. The answer is not obvious because each of these failures involved heterogeneous interactions and dynamics that are unlike the success stories. The telephone and power system failures and the Denver airport baggage handling system fiasco are more clearly examples where uncertainty management in complex systems went awry. These highly interconnected and automated systems are intended to improve performance and robustness and at the same time reduce cost, and they generally do so with respect to the uncertainties and objectives that are considered primary in these systems. Unfortunately, the very complexity introduced to handle uncertainties in some aspects of the system's environment lead to vulnerabilities elsewhere. It is tempting to imagine that a design environment that stressed uncertainty management and explicit representation of uncertainty across discipline boundaries would have encouraged design engineers to be alerted in advance to the potential for these failures, but we will have to wait until we have a better picture of exactly what such an environment would consist of. The challenge will be to avoid believing too much in either virtual worlds, or our past experiences with real ones, as both can mislead us about future realities. Figure B.11 is intended to convey the way in which some existing communities are addressing the various aspects of VE models: uncertainty, interconnec-
OCR for page 167
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force tion, dynamics, nonlinearity, and complexity. It is intended to suggest that all the issues are being addressed, but in a fragmented way. We touched briefly and informally on all these topics except statistics. CASE here means computer-aided software engineering, and complexity theory is computational complexity in theoretical computer science. There are other areas that should contribute to a VE theory, such as nonequilibrium physics, all aspects of scientific computing and numerical methods, optimization, and discrete-event and hybrid systems. We have argued that while sophisticated hardware and software infrastructures are needed to form the substrate on which robust VE tools can be implemented, the infrastructure aspects of M&S are already emphasized to a high degree, and the issues focused on in this appendix need comparable attention. In doing so we have perhaps paid inadequate attention to the need for new and novel software and user-interface paradigms that would address unique needs of VE. We regret we have had neither the time nor the expertise to explore this further. An aspect of computing that we will briefly discuss, since it is so ubiquitous, is so-called “soft computing.” SOFT AND HARD COMPUTING Soft computing is usually taken to include fuzzy logic, neural-net computing, genetic algorithms, and so on, in contrast to the “hard computing techniques” of, say, numerical analysis, mathematical programming, structured and object-oriented programming, probability theory, differential equations, “hard” AI, and so on. According to its proponents, such as Lotfi Zadeh (see, e.g., Zadeh, 1994), “soft computing will revolutionize computing.” While it is certainly beyond the scope of this appendix to give a thorough discussion of this area, we can provide at least one perspective. There are two standard arguments made for soft computing. The first is that many problems do not lend themselves to hard computing solutions because the systems under consideration are dominated by what we would traditionally call “soft” issues, like economic and societal systems, and anything involving human decision making, common-sense reasoning, and natural language. Hard computing and hard AI have failed to achieve long-standing goals of making human-computer interactions more human-friendly precisely because they have failed to appreciate soft computing approaches. Soft computing, especially fuzzy logic, allows programming with natural language. Indeed, Zadeh has characterized fuzzy logic as “computing with words.” The hope is that if you know a solution and you can simply and clearly articulate it in words, then you can program directly without translation to some programming language. There is substantial controversy regarding the degree to which fuzzy logic solves this problem, but the goal is certainly admirable, and there are cases in which fuzzy logic has been successful. On the other hand, many problems do not fit the fuzzy paradigm at all. In some cases, we can do a particular task well, but we cannot clearly articulate how we do it. Examples include chess
OCR for page 168
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force playing, vision, speech recognition, and almost all motor skills, such as those involved in sports or physical labor. Many of the tasks in which humans greatly outperform machines are also ones in which lower animals outperform humans. While biological systems do provide useful inspirations for machine automation, only humans typically articulate in words a detailed description of their own behavior. Perhaps more importantly, we often need the methods of mathematics, science, and engineering to help us find a solution. And in still other cases, using such methods permits us to find a better and more robust solution than possible with the simpler forms of fuzzy logic that have such intuitive appeal. By and large, we believe that the difficult problems of the VE enterprise are problems in which our naive intuition is likely to be dangerously wrong. In such cases, we should be cautious of seductive shortcuts. The second argument for soft computing, and again fuzzy logic in particular, is that they more naturally exploit the tolerance for imprecision, uncertainty, partial truth, and approximation that characterize human reasoning. In the context of VE, it is useful to distinguish two kinds of uncertainty: The imprecision and ambiguities in our natural language, which parallels our sometimes limited ability to precisely specify what we want a system to do. The uncertainty in our models of physical systems, as has been emphasized in this appendix. While we have emphasized the latter, in the early stages in design of engineering systems the former can often dominate. If VE is successful in dealing effectively with type 2 uncertainty, then type 1 will be increasingly critical to overall system performance. It is here where fuzzy logic and soft computing hold the greatest promise. Advocates argue, though, that fuzzy logic is also ideally suited to handle uncertainty of type 2 as well. We disagree. Fuzzy logic is intended to capture properties of human language and simply does not address in any meaningful way many of the kinds of uncertainty we have discussed in this appendix and how uncertainty propagates with dynamics and interconnection. And, if one tried to use fuzzy logic to do so, it would quickly lose its comfortable “natural-language features.” Fuzzy logic may be useful in representing human decision making in a simulation environment, but we have not considered that issue here. It may also be useful in a variety of engineering contexts that are ultimately much simpler than those in VE. Similar remarks apply to genetic algorithms. Optimization, and particular global search techniques, will play a critical role in present and future VE systems. Indeed, our proto-VE examples of aircraft design with CFD, VLSI, and CAD of the type used in the Boeing 777 are domains where global optimization is either already playing a huge role (VLSI) or a growing role. Statistical methods, advanced optimization theory, and even theoretical computer science (decidability, NP-hardness) are creating a foundation for this subject, both in academic research
OCR for page 169
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force and in industrial application. From this point of view, genetic algorithms are a very minor piece of the picture. Their popularity is due primarily to the ease with which people can use them (people who include not only deeply capable scientists, but also more ordinary people with no or little expertise in statistics, optimization, or complexity theory). Genetic algorithms are often mentioned as a moderately effective way to do global search, especially on highly unstructured problems. Based on our experience, which tends to be in hard areas of engineering rather than, say, softer problems of military combat modeling, we remain skeptical. Despite the strong market demands for commercial software to assist in global search in such problems as VLSI design and analysis of uncertain dynamical systems, genetic algorithms have had almost no impact relative to more mathematical approaches such as branch and bound, and problem-specific heuristics. This is not to say, however, that genetic algorithms have no role to play in VE. The conceptual simplicity of the approach means that it can be used by domain experts who may not be familiar with more sophisticated optimization ideas or may not want to invest the time to program a better algorithm. Genetic algorithms can be used to explore global optimization in a new domain, and if it is successful, then there is clear encouragement for further investigation. If not, little investment has been made. “COMPLEX ADAPTIVE SYSTEMS” AND SOFT COMPLEXITY A term that often arises in conjunction with soft computing is “complex adaptive systems,” which can be considered to be a research area in its own right or a special case of what we have discussed here under the rubric of VE. It is not, however, a “new science,” nor is it a substitute for the work we have described. Instead, what it has accomplished so far is to provide a set of metaphors for taking new looks at difficult problems involving complex systems. While the celebration of chaos, nonlinearity, and emergent phenomena has perhaps been overdone, and while popularizers have sometimes given them a nearly mystical flavor that seems bizarre to those of us working in the VE domain that includes control, dynamical systems, nonequilibrium physics, and complexity theory, the metaphors and popularized discussions have greatly broadened the audience and are helping to open minds regarding the value of experimenting with methods quite different from the traditional ones. In this sense, work on complex adaptive systems is helpful to the VE enterprise. The concern, of course, is that the simplifications of popularization— which sometimes include exaggerated promises and claims—will discredit those associated with complexity research when those exaggerations are better recognized. This is a common problem in science. For example, there were backlashes against artificial intelligence and expert systems because the more exaggerated claims were finally recognized as such. The backlashes were sometimes quite unfortunate, because the research in these areas has had profound effects. In any
OCR for page 170
Technology for the United States Navy and Marine Corps, 2000-2035: Becoming a 21st-Century Force case, as we have indicated from the very beginning of this appendix, dynamical systems concepts will necessarily be at the very heart of any useful theory of VE. It is important that VE researchers develop the kind of nonlinear intuition that the subject encourages and also build on existing methods for analysis of nonlinear systems. Both the concept of chaos —that apparent complexity and randomness can arise from deep simplicity —and the concept of emergence—that apparent order and simplicity can arise from deep complexity —are of great importance. On the other hand, they are empty without the more technical concepts such as phase space, bifurcation, strange attractors, Poincare maps, Lyapunov exponents, Hamiltonians, Euler-Lagrange equations, symplectic maps, integrability, self-organized criticality, ergodicity, and entropy. Unfortunately, there is no easy access to this deeper work. To end this discussion, we might tentatively propose a notion of “soft complexity” analogous to, and including, “soft computing,” in the same way that we might propose a notion of “hard complexity” that is analogous to and includes “hard computing.” The flavor of the distinction would be as follows: Soft complexity equals emergence, fractals, artificial life, complex adaptive systems, edge of chaos, control of chaos, . . . plus soft computing, fuzzy logic, neural nets, and genetic algorithms. Hard complexity equals information theory, algorithmic complexity, computational complexity, dynamical systems, control theory, CASE/CAD, nonequilibrium physics, statistics, numerical analysis, and so on. This appendix has clearly advocated the relative importance of “hard” over “soft” complexity in VE. Some of the more extreme advocates for soft complexity claim it will revolutionize analysis and design of complex systems and obviate the need for the “structured and mathematical approach” advocated here. While we obviously disagree with this assessment, it is likely that soft complexity can help make concepts of hard complexity accessible, albeit in a limited way, to a nontechnical audience. It is also likely that the soft complexity concepts will be quite valuable in communication and, probably, for certain types of initial exploration of concepts. In any case, popular expositions of soft complexity will continue to emerge and will have effects on decisions about investment. Our hope is that papers such as the current appendix will help maintain perspectives. 9 9 For differing perspectives, see a selection of papers by users of fuzzy logic, including engineers, in Proceedings of the IEEE, March 1995. See also the collections of Zadeh's papers (Yager et al., 1987). And, in this volume, see Appendix G for examples of fuzzy logic research.
Representative terms from entire chapter: