Biomimicry for Optimization, Control, and Automation Springer London Berlin Heidelberg New York Hong Kong Milan Paris Tokyo Kevin M. Passino Biomimicry for Optimization, Control, and Automation With 365 Figures Kevin M. Passino Department of Electrical and Computer Engineering, 416 Dreese Laboratories, The Ohio State University, 2015 Neil Ave., Columbus, OH 43210, USA http://www.ece.osu.edu/(cid:1)passino BritishLibraryCataloguinginPublicationData Passino,KevinM. Biomimicryforoptimization,control,andautomation 1. Controlsystems 2. Adaptivecontrolsystems 3. Intelligentcontrol systems I. Title 003.5 ISBN1852338040 LibraryofCongressCataloging-in-PublicationData Passino,KevinM. Biomimicryforoptimization,control,andautomation/KevinM.Passino. p.cm. Includesbibliographicalreferencesandindex. ISBN1-85233-804-0(alk.paper) 1. Controlsystems. 2. Mathematicaloptimization. I. Title. TS156.8.P245 2004 629.8—dc22 2004041694 Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, DesignsandPatentsAct1988,thispublicationmayonlybereproduced,storedortransmitted,inanyformorbyanymeans,withthe prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms of licences issuedbytheCopyrightLicensingAgency.Enquiriesconcerningreproductionoutsidethosetermsshouldbesenttothepublishers. ISBN1-85233-804-0Springer-VerlagLondonBerlinHeidelberg Springer-VerlagisapartofSpringerScience+BusinessMedia springeronline.com ©Springer-VerlagLondonLimited2005 Theuseofregisterednames,trademarks,etc.inthispublicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuch namesareexemptfromtherelevantlawsandregulationsandthereforefreeforgeneraluse. Thepublishermakesnorepresentation,expressorimplied,withregardtotheaccuracyoftheinformationcontainedinthisbookand cannotacceptanylegalresponsibilityorliabilityforanyerrorsoromissionsthatmaybemade. Typesetting:Camera-readybyauthor PrintedandboundintheUnitedStatesofAmerica 69/3830-543210 Printedonacid-freepaper SPIN10967713 To Annie, my best friend, soul-mate, wife, y cielito and to our sweet children who fill our hearts with joy and whom we love so much, Carina, Juliana, Jacob, and Zacarias Preface Biomimicry uses our scientific understanding of biological systems to exploit ideasfromnaturein orderto constructsometechnology. Inthis book, wefocus onhowtousebiomimicryofthefunctionaloperationofthe“hardwareandsoft- ware”of biologicalsystems for thedevelopmentof optimizationalgorithmsand feedbackcontrolsystemsthatextendourcapabilitiestoimplementsophisticated levels of automation. The primary focus is not on the modeling, emulation, or analysis of some biological system. The focus is on using “bio-inspiration” to inject new ideas, techniques, and perspective into the engineering of complex automation systems. There are many biological processes that, at some level of abstraction, can berepresentedasoptimizationprocesses,manyofwhichhaveasabasicpurpose automatic control, decision making, or automation. For instance, at the level of everyday experience, we can view the actions of a human operator of some process (e.g., the driver of a car) as being a series of the best choices he or she makes in trying to achieve some goal (staying on the road); emulation of this decision-making process amounts to modeling a type of biological optimization and decision-making process, and implementation of the resulting algorithm results in “human mimicry” for automation. There are clearer examples of bi- ological optimization processes that are used for control and automation when you consider nonhuman biological or behavioral processes, or the (internal) bi- ology of the human and not the resulting external behavioral characteristics (like driving a car). For instance, there are homeostasis processes where, for instance, temperature is regulated in the human body. Another example is the neuralnetwork for “motor control” that helps keep us standing (balancing). In thecognitiveprocessofplanninginthebrain,thereistheevaluationofmultiple options (e.g., sequences of actions), and then the selection of the best one. The behavior of attentional systems can be seen as trying to dynamically focus on the most important entity in a changing environment. Learning can be seen as gatheringthe most useful informationfrom a complex noisy environment,or as a process of constructing the best possible representation of some aspect of the environment for use in decision making. Evolution can be viewed as a stochas- tic process that designs optimal and robust organisms according to Darwin’s principleof“survivalofthefittest” (i.e., the best-suitedorganismsforthe envi- ronment survive to reproduce). Both learning and evolution can be viewed as optimizationprocessesthatleadtoadaptations,overshortandlongtimescales, viii Biomimicry respectively. Foraging can be modeled as a sequential optimization process of making the best choices about where to go to find nutrients so as to maximize energy intake per time spent foraging, and how to avoid threats (e.g., getting eaten) at the same time. In cooperative (“social”) foraging, animals work to- gether to help the groupfind resources. Sometimes such socialanimals operate in cohesive “swarms” to forage and avoid threats. In competitive foraging, the forager must make the best decisions in the presence of its adversaries in order to survive. In this book, we will explain how to model such biological processes, and how to use them to develop or implement methods for optimization, control, and automation. We will be quite concerned with showing that our methods are verifiably correct (e.g., so that, if we use them in an engineering applica- tion, we know they will operate correctly and not necessarily have the same, possibly high, error rate as their biological counterparts). This drives the de- cision to include a significant amount of material on engineering methodology, simulation-based evaluations, and modeling and mathematical verification of properties of the systems we study (e.g., stability analysis and an emphasis on robustness). Theoverallgoalistoexpandthehorizonsforoptimization,control andautomation, but atthesametime to bepragmaticandkeepa firmfounda- tion in traditional engineering methods that have been consistently successful. Generally, the focus is on achieving high levels of “autonomy” for systems, not on the resulting “intelligence” of the system. It is hoped that this book will show you that the synthesis of the biomimicry viewpoint with traditional physics and mathematics-basedengineering, offers a very broadandpractically useful perspective, especially for very complex automation problems. For all these reasons, this book is likely to be primarily useful to persons interested in the areas of “intelligent systems,” “intelligent automation,” or what has been called “intelligent control” (essentially, the viewpoint here is that “biomimicry for optimization, control, and automation,” the title of this book, is the definition of the field of“intelligentcontrol”). While this book will likely be of most interest to engineers and computer scientists, it may also be interesting to some in the biological sciences and mathematical biology. A Quick Glance at Key Concepts and Topics If youwantto getabetter senseofwhatthis bookis about, firstscanthetable ofcontents,thengotothefirstfewpagesofeachpartandreadthe“Sequenceof EssentialConcepts”(theirconcatenationtellsthebasic“story”ofthisbook,and it may be useful to reread that story as you progress through the book). This givesahigh-levelviewofwhatyoucanlearnbyreadingthisbook,andhelpsome readers decide on which parts to focus on. For an even more detailed sequence of key concepts, scan the “side notes” that are in the margins throughout the entire book. These notes state in a concise way the important concepts. Preface ix Overview of the Book Part I serves as the introduction to the book and establishes the philosophy of the general methodologies that are used. First, we provide a detailed overview of the control engineering methodology for traditional feedback systems and complex automation systems. Next, scientific foundations for biomimicry for “intelligentcontrol”areestablished. Weoverviewsomeideasfrombiology,neu- roscience, psychology, behavioral/sensory ecology, foraging theory, and evolu- tionthathavebeenparticularlyusefulinprovidingbiologicallyinspiredcontrol methods. Also, we explain how to exploit human expertise on how to control systems (“human-mimicry”), and use this to achieve automation. In PartII, westudy methods to automatethose biologicalcontrolfunctions and human expertise that do not involve learning. First, we introduce the basics of neural networks and explain how they can serve as the “hard-wiring” for implementing control functions in animals. Next, we introduce fuzzy and expertcontrol,andprovideadesignexampletoclarifyhowaheuristicrule-based controller synthesis methodology works. We discuss how to perform Lyapunov stabilityanalysisofneuralandfuzzycontrolsystems. Weshowhowautonomous robots can perform path planning for obstacle avoidance, and how planning concepts can be used in the closed-loop via model predictive control. Then we introduce attentional systems, where animals seek to manage the complexity of sensory information via focusing and filtering. We introduce a model of an organism in a predator/prey environment that wants to “pay attention,” so that it can keep track of predator/prey locations. We introduce several attentional strategies (resource allocation methods), simulate their behavior, discuss attentional strategy design, and perform stability analysis. In Part III, we introduce learning. We overview the psychology and neu- roscience of learning. We focus on incorporating aspects of learning that arise from function approximation to improve performance in control systems while theyareinoperation. Wedefineseveralheuristicadaptivecontrol(learningcon- trol)strategiesthatarebasedontheunderlyingneuroscienceandpsychologyof learning(e.g.,reinforcementlearning). Wecoverleastsquares,steepestdescent, Newton, conjugate gradient,Levenberg-Marquardt,and clustering methods for trainingapproximators. Westudy basicissuesinlearningrelatedto generaliza- tion, overtraining/overfitting,online and offline learning, and model validation. Next, we show how the learning methods can be used to adapt the param- eters of the controller (or estimator) structures, defined in Part II, to create adaptive decision-making systems (i.e., ones that can learn to accommodate problems that arise in the environment). We explain how least squares and gradientoptimizationprocedurescanbe used to tune approximatorsto achieve adaptive control (i.e., automatic tuning of the controller in response to plant uncertainties) for nonlinear discrete-time systems. Finally, we show how to de- velop stable, continuous-time adaptive control systems that use fuzzy systems or neural networks as approximators. In Part IV, we explain how the genetic algorithm can be used to simulate evolution and solve optimization problems. Next, we discuss general issues in x Biomimicry stochastic optimization for design of controland automation systems. For this, we first overview the relevant biology of learning and evolutionary theories, in- cluding the concept of “highly optimized tolerance” and robustness trade-offs for complex systems, and synergies between evolution and learning (e.g., evo- lution of learning, the Baldwin effect, and evolved instinct-learning balance). We show how the “response surface methodology” for nongradient optimiza- tion and design can be used to understand robustness trade-offs in control and learning system design. We show how nongradient and “set-based” stochastic optimization methods can be used for robust design, and give an example of evolution of instinct-learning balance. Moreover, we discuss the use of evolu- tionary and stochastic optimization methods for “Darwinian design of physical control systems.” Next, we show how online “set-based” stochastic optimiza- tion algorithms can achieve a type of online evolution of controllers to achieve real-time evolutionary adaptive control. In PartV, after explaining thebasics offoragingtheoryandforagingsearch strategies, we show how “taxes” (motion) of populations of foraging E. coli bacteria can achieve optimization, either as individuals or as groups (swarms). We show how to simulate social foraging bacteria, and how they can work to- gethercooperativelytosolveanoptimizationproblem. We discuss the basicsof the modeling and stability analysis of foraging swarms, and study an applica- tiontocooperativecontrolformultipleautonomousvehicles(robots). Next, we discuss animal fighting behaviors and game theory models of cooperative and competitive foraging. In the final section, we discuss intelligent foraging. This section is designed to provide an integrated view of the methods studied in the book, point to futureresearchdirections, andto provideseveralchallengingde- signproblems, where the student is askedto integrate the methods of the book to develop and evaluate a group of social foraging vehicles or two competing intelligent teams. Topics Not Covered It is impossible to cover all the relevant biomimicry topics in one book, even withtherelativelynarrowfocusofoptimization,control,andautomation. Here, variouschoiceshavebeenmadeaboutwhattoinclude,choiceswhichdependon my energy level, my own expertise (or lack thereof), my experience with appli- cations,the needto limitbook length,theavailabilityofother goodbooks,and level of topic maturity in the literature at the time of the writing of this book. This led to little or no attention given to the following topics: (i) combinato- rial optimization and dynamic or linear programming,and its use in intelligent systems (e.g., in path planning, learning, and foraging); (ii) Bayesian belief networks (e.g., their use in decision making); (iii) temporal difference learning and “neuro-dynamic programming;” (iv) sensor management and multisensor integration; (v) immune systems and networks (e.g., in learning and connec- tions with evolution); (vi) construction or evolution of the structure of neural and fuzzy systems (i.e., automated approximator structure construction); (vii) Preface xi learningautomata; (viii) evolutionarygame theory andevolutionarydynamics; and(ix) study of other controlprocessesin biologicalsystems (e.g., in morpho- genesis,geneticnetworks,insidecells,motorcontrol,andhomeostasis). Someof these topics are relatively easy to understand, once you understand this book, while others would require a much more significant time investment. Consid- ering (ix), this book is generally stronger for biomimicry of the “higher level” functionalitiesofbiologicalsystems(e.g.,wemaystudythemotilebehaviorofa bacterium during foraging, but ignore the control processes inside the cell that are used to achieve the motile behavior). Regardless, for several of the above topics, there are exercises or design problems that help introduce them to the reader and show how they are relevant to the topics in this book. Also, refer- encesareprovidedtotheinterestedreaderwhowantstostudytheabovetopics further. Bibliographic References Toavoiddistractionsandproduceasmoothflowofthetext,citationsandexpla- nationsof,forexample,whatwasdonewhenandhoweachresearchcontribution built on and related to others, are generally not placed within the text. The referencing style adopted here is more like the one used for a typical textbook, rather than a research monograph. At the same time, however, each part ends witha“ForFurtherStudy”sectionthatisanannotatedbibliography. Forthese sections, note the following: • The main sources used for each chapter, and some related ones, are in- cluded. Sourcesthatmostsignificantlyaffected the contentandapproach of this book are highlighted. • There are recommendations on which books or papers to use to get in- troductions to some topics, and more detailed treatments of others. In particular, there are key references given in control theory and engineer- ing, and in several of the foundational “bio” topics. • Sources for applications of the methods are highlighted, as many of the techniques in this book have been used successfully in a wide array of problems, too many to reference here. • There is recommended reading for topics that were not covered here (see above list). • There are many lists of references that would help support the pursuit of research into the topics studied in this book. • Connections among a variety of topics are highlighted in the context of referencing researchareas. • A number of times the fuller lists of references for topics are found in the references that are cited, not here. This helped to keep the bibliography size here more manageable.