Article

Genetic evolution of hierarchical behavior structures

Authors:

Brian G. Woolley,

Gilbert L. PetersonAuthors Info & Claims

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

Pages 1731 - 1738

https://doi.org/10.1145/1276958.1277296

Published: 07 July 2007 Publication History

Abstract

The development of coherent and dynamic behaviors for mobile robots is an exceedingly complex endeavor ruled by task objectives, environmental dynamics and the interactions within the behavior structure. This paper discusses the use of genetic programming techniques and the unified behavior framework to develop effective control hierarchies using interchangeable behaviors and arbitration components. Given the number of possible variations provided by the framework, evolutionary programming is used to evolve the overall behavior design. Competitive evolution of the behavior population incrementally develops feasible solutions for the domain through competitive ranking. By developing and implementing many simple behaviors independently and then evolving a complex behavior structure suited to the domain, this approach allows for the reuse of elemental behaviors and eases the complexity of development for a given domain. Additionally, this approach has the ability to locate a behavior structure which a developer may not have previously considered, and whose ability exceeds expectations. The evolution of the behavior structure is demonstrated using agents in the Robocode environment, with the evolved structures performing up to 122 percent better than one crafted by an expert.

References

[1]

R. C. Arkin. "Behavior-based robot navigation for extended domains." Adaptive Behavior, vol. 1, pp. 201--225, 1992.

Digital Library

[2]

J. E. Baker. "Reducing bias and inefficiency in the selection algorithm." Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and their Application, pp. 14--21, 1987.

Digital Library

[3]

V. Braitenberg. Vehicles: Experiments in Synthetic Psychology. Cambridge, MA: MIT Press, 1984.

[4]

R. A. Brooks. "A Robust Layered Control System for a Mobile Robot." IEEE Journal of Robotics and Automation, vol. RA-2, pp. 14--23, 1986.

[5]

R. A. Brooks. "New Approaches to Robotics." Science, vol. 253, pp. 1227--1232, 1991.

[6]

C. Coello Coello, D. Van Veldhuizen, and G. Lamont. Evolutionary Algorithms for Solving Multi-Objective Problems. New York, NY: Kluwer Academic, 2002.

Digital Library

[7]

J. Connell. "A Behavior-Based Arm Controller." IEEE Transactions on Robotics and Automation, vol. 5, pp. 784--791, 1989.

[8]

R. J. Firby, "Adaptive execution in complex dynamic worlds," Ph.D. Dissertation, Yale University, YALEU/CSD/RR #672, 1989.

Digital Library

[9]

E. Gamma, R. Helm, R. Johnson, J. Vlissides. Design Patterns. Boston, MA: Addison-Wesley, 1994.

[10]

E. Gat. "On Three-Layer Architectures." Artificial Intelligence and Mobile Robots: Case Studies of Successful Robot Systems, pp. 195 -- 210, 1998.

Digital Library

[11]

D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley, 1989.

Digital Library

[12]

P. Husbands. "Genetic Algorithm in Optimization and Adaptation." Advances in Parallel Algorithms, pp. 227 -- 276, 1992.

Digital Library

[13]

L. P. Kaelbling, "An Architecture for Intelligent Reactive Systems," in SRI International Technical Note No. 400. Menlo Park, CA, 1986.

[14]

J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press, 1992.

Digital Library

[15]

P. Maes. "Situated Agents Can Have Goals." Robotics and Autonomous Systems, vol. 6, pp. 49 -- 70, 1990.

Digital Library

[16]

M. Nelson. "Robocode Central." http://robocode.sourceforge.net, 2006.

[17]

J. Rosenblatt. "DAMN: A distributed Architecture for Mobile Navigation." the AAAI Spring Symposium on Lessons Learned for Implemented Software Architectures for Physical Agents, pp. 167 -- 178, 1995.

[18]

J. Rosenblatt. "Utility Fusion: Map-Based Planning in a Behavior-Based System." Field and Service Robotics, pp. 411--418, 1998.

[19]

M. Shaw and D. Garlan. Software Architecture: Perspectives on an Emerging Dicipline. Upper Saddle River, NJ: Prentice Hall, 1996.

Digital Library

[20]

J. Togelius. "Evolution of a subsumption architecture neurocontroller." Journal of Intelligent and Fuzzy Systems, vol. 15, pp. 15--20, 2004.

Digital Library

[21]

J. Togelius and S. M. Lucas. "Evolving controllers for simulated car racing." Arxiv preprint cs.NE/0611006, 2006.

[22]

H. Utz, G. Kraetzschmar, G. Mayer, and G. Palm. "Hierarchical Behavior Organization." 2005 International Conference on Intelligent Robots and Systems, 2005.

[23]

B. Woolley and G. Peterson, "Unified Behavior Framework for Reactive Robot Control," Technical Report, Air Force Institute of Technology, WPAFB, OH, 2007.

Cited By

Desplenter TTrejos A(2020)A Control Software Framework for Wearable Mechatronic DevicesJournal of Intelligent & Robotic Systems10.1007/s10846-019-01144-5Online publication date: 21-Jan-2020
https://doi.org/10.1007/s10846-019-01144-5
Gomes JChristensen A(2018)Comparing Approaches for Evolving High-Level Robot Control Based on Behaviour Repertoires2018 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2018.8477699(1-6)Online publication date: Jul-2018
https://doi.org/10.1109/CEC.2018.8477699

Index Terms

Genetic evolution of hierarchical behavior structures
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Robotics
      1. Robotic autonomy
2. Software and its engineering
  1. Software creation and management
    1. Software development techniques
      1. Software prototyping
    2. Software post-development issues
      1. Software evolution

Recommendations

Unified Behavior Framework for Reactive Robot Control

Behavior-based systems form the basis of autonomous control for many robots. In this article, we demonstrate that a single software framework can be used to represent many existing behavior based approaches. The unified behavior framework presented, ...
Creating emergent behaviors: two robotics labs that combine reactive behaviors
SIGCSE '05: Proceedings of the 36th SIGCSE technical symposium on Computer science education

Most undergraduate robotics courses introduce reactive behaviors, behaviors that are not mediated by world knowledge or a world model. What is missing from these courses, however, is the experience of combining reactive behaviors to create emergent ...
Adaptive Behaviors in Autonomous Navigation with Collision Avoidance and Bounded Velocity of an Omnidirectional Mobile Robot

Integration of Control Theory and Genetic Programming paradigm toward development a family of controllers is addressed in this paper. These controllers are applied for autonomous navigation with collision avoidance and bounded velocity of an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

July 2007

2313 pages

ISBN:9781595936974

DOI:10.1145/1276958

General Chair:
Hod Lipson
Cornell University, USA

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO07

Sponsor:

GECCO07: Genetic and Evolutionary Computation Conference

July 7 - 11, 2007

London, England

Acceptance Rates

GECCO '07 Paper Acceptance Rate 266 of 577 submissions, 46%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
345
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Desplenter TTrejos A(2020)A Control Software Framework for Wearable Mechatronic DevicesJournal of Intelligent & Robotic Systems10.1007/s10846-019-01144-5Online publication date: 21-Jan-2020
https://doi.org/10.1007/s10846-019-01144-5
Gomes JChristensen A(2018)Comparing Approaches for Evolving High-Level Robot Control Based on Behaviour Repertoires2018 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2018.8477699(1-6)Online publication date: Jul-2018
https://doi.org/10.1109/CEC.2018.8477699

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents