Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Increasingly, high-assurance applications rely on autonomic systems to respond to changes in their environment. The inherent uncertainty present in the environment of autonomic systems makes it difficult for developers to identify and model resilient autonomic behavior prior to deployment. In this paper, we propose Avida-MDE, a digital evolution approach to the generation of behavioral models (i.e., a set of interacting finite state machines) that capture autonomic system behavior that is potentially resilient to a variety of environmental conditions. We use an evolving population of digital organisms to generate behavioral models, where the organisms are subjected to natural selection and are rewarded for generating behavioral models that meet developer requirements. To illustrate this approach, we successfully applied it to the generation of behavioral models describing the navigation behavior of an autonomous robot.

REFERENCES

• 1: Grady Booch , James Rumbaugh , Ivar Jacobson, The Unified Modeling Language user guide, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1999
• 2: K. Chellapilla and D. Czarnecki. A preliminary investigation into evolving modular finite state machines. In Congress on Evolutionary Computation, 1999.
• 3: D. C. Dennett. The new replicators. In M. Pagel, editor, The Encyclopedia of Evolution, volume 1, pages E83--E92. Oxford University Press, 2002.
• 4: L. J. Fogel, P. J. Angeline, and D. B. Fogel. An evolutionary programming approach to self-adaptation on finite state machines. In Evolutionary Programming, 1995.
• 5: H. J. Goldsby, B. H. C. Cheng, P. K. McKinley, D. B. Knoester, and C. A. Ofria. Digital evolution of behavioral models for autonomic systems. In Proceedings of the 5th International Conference on Autonomic Computing (ICAC 2008), Chicago, Illinois, June 2008.
• 6: D. Harel, H. Kugler, and A. Pnueli. Synthesis revisited: Generating statechart models from scenario-based requirements. In Formal Methods in Software and Systems Modeling, 2005.
• 7: G. Holzmann. The Spin Model Checker, Primer and Reference Manual. Addison-Wesley, Reading, Massachusetts, 2004.
• 8: Y. Inagaki. On synchronized evolution of the network of automata. IEEE Transactions on Evolutionary Computation, 6, 2002.
• 9: Barbara Jobstmann , Roderick Bloem, Optimizations for LTL Synthesis, Proceedings of the Formal Methods in Computer Aided Design, p.117-124, November 12-16, 2006 [doi>10.1109/FMCAD.2006.22]
• 10: Raman Kazhamiakin , Marco Pistore , Marco Roveri, Formal Verification of Requirements using SPIN: A Case Study on Web Services, Proceedings of the Software Engineering and Formal Methods, Second International Conference, p.406-415, September 28-30, 2004 [doi>10.1109/SEFM.2004.19]
• 11: Minseong Kim , Suntae Kim , Sooyong Park , Mun-Taek Choi , Munsang Kim , Hassan Gomaa, UML-based service robot software development: a case study, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134360]
• 12: Sascha Konrad , Heather Goldsby , Karli Lopez , Betty H. C. Cheng, Visualizing Requirements in UML Models, Proceedings of the 1st international workshop on Requirements Engineering Visualization, p.1, September 11-11, 2006 [doi>10.1109/REV.2006.11]
• 13: John R. Koza, Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers, Norwell, MA, 2003
• 14: Ingolf Krüger , Radu Grosu , Peter Scholz , Manfred Broy, From MSCs to statecharts, Proceedings of the IFIP WG10.3/WG10.5 international workshop on Distributed and parallel embedded systems, p.61-71, October 1998, Scholoß Eringerfeld, Germany
• 15: S. M. Lucas and T. J. Reynolds. Learning DFA: evolution versus evidence driven state merging. In Congress on Evolutionary Computation, 2003.
• 16: S. Luke, S. Hamahashi, and H. Kitano. "Genetic" programming. In Genetic and Evolutionary Computation Conference, 1999.
• 17: Philip McKinley , Betty H. C. Cheng , Charles Ofria , David Knoester , Benjamin Beckmann , Heather Goldsby, Harnessing Digital Evolution, Computer, v.41 n.1, p.54-63, January 2008 [doi>10.1109/MC.2008.17]
• 18: Philip K. McKinley , Seyed Masoud Sadjadi , Eric P. Kasten , Betty H. C. Cheng, Composing Adaptive Software, Computer, v.37 n.7, p.56-64, July 2004 [doi>10.1109/MC.2004.48]
• 19: William E. McUmber , Betty H. C. Cheng, A general framework for formalizing UML with formal languages, Proceedings of the 23rd International Conference on Software Engineering, p.433-442, May 12-19, 2001, Toronto, Ontario, Canada
• 20: Charles Ofria , Claus O. Wilke, Avida: a software platform for research in computational evolutionary biology, Artificial Life, v.10 n.2, p.191-229, April 2004 [doi>10.1162/106454604773563612]
• 21: Steen Rasmussen , Carsten Knudsen , Pasmus Feldberg , Morten Hindsholm, The coreworld: emergence and evolution of cooperative structures in a computational chemistry, Physica D, v.42 n.1-3, p.111-134, June 1990
• 22: T. S. Ray. An approach to the synthesis of life. In C. G. Langton, C. Taylor, J. D. Farmer, and S. Rasmussen, editors, Artificial Life II, pages 371--408. Addison-Wesley, Reading, MA, USA, 1992.
• 23: Douglas C. Schmidt, Guest Editor's Introduction: Model-Driven Engineering, Computer, v.39 n.2, p.25, February 2006 [doi>10.1109/MC.2006.58]
• 24: Hooman Shayani , Peter J. Bentley, A more bio-plausible approach to the evolutionary inference of finite state machines, Proceedings of the 2007 GECCO conference companion on Genetic and evolutionary computation, July 07-11, 2007, London, United Kingdom [doi>10.1145/1274000.1274039]
• 25: Sebastian Uchitel , Greg Brunet , Marsha Chechik, Behaviour Model Synthesis from Properties and Scenarios, Proceedings of the 29th international conference on Software Engineering, p.34-43, May 20-26, 2007 [doi>10.1109/ICSE.2007.21]
• 26: Sebastian Uchitel , Jeff Kramer , Jeff Magee, Synthesis of Behavioral Models from Scenarios, IEEE Transactions on Software Engineering, v.29 n.2, p.99-115, February 2003 [doi>10.1109/TSE.2003.1178048]
• 27: Hung Tran Van , Axel van Lamsweerde , Philippe Massonet , Christophe Ponsard, Goal-Oriented Requirements Animation, Proceedings of the Requirements Engineering Conference, 12th IEEE International, p.218-228, September 06-10, 2004 [doi>10.1109/RE.2004.24]
• 28: Jon Whittle , Praveen K. Jayaraman, Generating Hierarchical State Machines from Use Case Charts, Proceedings of the 14th IEEE International Requirements Engineering Conference (RE'06), p.16-25, September 11-15, 2006 [doi>10.1109/RE.2006.25]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Self-modifying machines (e.g., neural networks)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

General Terms:
Experimentation

Keywords:
autonomic computing, digital evolution, model checking, model-driven engineering