article

Genetic programming incorporating biased mutation for evolution and adaptation of Snakebot

Author:

Ivan TanevAuthors Info & Claims

Genetic Programming and Evolvable Machines, Volume 8, Issue 1

Pages 39 - 59

https://doi.org/10.1007/s10710-006-9008-4

Published: 01 March 2007 Publication History

Abstract

In this work we propose an approach for incorporating learning probabilistic context-sensitive grammar (LPCSG) in genetic programming (GP), employed for evolution and adaptation of locomotion gaits of a simulated snake-like robot (Snakebot). Our approach is derived from the original context-free grammar which usually expresses the syntax of genetic programs in canonical GP. Empirically obtained results verify that employing LPCSG contributes to the improvement of computational effort of both (i) the evolution of the fastest possible locomotion gaits for various fitness conditions and (ii) adaptation of these locomotion gaits to challenging environment and degraded mechanical abilities of the Snakebot.

References

[1]

1. Y. Andrusenko Y., "Russian culture navigator: Miturich-Khlebnikovs: art trade runs in the family," URL: http://www.vor.ru/culture/cultarch191_eng.html.

[2]

2. J. Antonisse, "A grammar-based genetic algorithm," in Foundations of the Genetic Algorithm Workshop (FOGA), G. J. E. Rawlins (ed.), Morgan Kaufmann, CA, pp. 193-204.

[3]

3. P. J. Angeline, "Genetic programming and emergent intelligence," in Advances in Genetic Programming, K. E. Kinnear Jr. (ed.), MIT Press: Cambridge, MA, 1994, pp. 75-98.

Digital Library

[4]

4. W. Banzhaf, P. Nordin, R. Keller, and F. Francone, "Genetic Programming: An Introduction," Morgan Kaufmann: San Francisco, 1998.

[5]

5. J. C. Bongard and H. Lipson, "Automated damage diagnosis and recovery for remote robotics," in Proceedings of the 2004 International Conference on Robotics and Automation (ICRA 2004), IEEE (ed.), IEEE, New York, 2004, pp. 3545-3550.

[6]

6. P. Bosman and E. de Jong, "Learning probabilistic tree grammars for genetic programming," in Proceedings of the 8th International Conference on Parallel Problem Solving from Nature, X. Yao, E. Burke, et al. (eds.), (PPSN-04), Springer: Berlin, 2004, pp. 192-201.

[7]

7. J. W. Burdick, J. Radford, and G. S. Chirikjian, "A 'Sidewinding' locomotion gait for hyperredundant robots," in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 1993), IEEE (ed.), Atlanta, USA, IEEE Computer Society Press: Los Alamitos, CA, 1993, pp. 101-106.

[8]

8. L. H. Caporale, Darwin in the Genome: Molecular Strategies in Biological Evolution, McGraw-Hill/Contemporary Books: New York, 2002.

[9]

9. G. S. Chirikjian and J. W. Burdick, "The kinematics of hyper-redundant robotic locomotion," IEEE Trans. Robotics and Automation, vol. 11, pp. 781-793, 1995.

[10]

10. K. Dowling, "Limbless locomotion: learning to crawl," in Proceedings of the International Conference on Robotics and Automation (ICRA 1999), IEEE (ed.), IEEE, New York, 1999, pp. 3001-3006.

[11]

11. D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addision-Wesley, 1989.

[12]

12. D. E. Goldberg and K. Deb, "A comparative analysis of selection schemes used in genetic algorithms," in G. Rawlins (ed.), Foundations of Genetic Algorithms, Morgan Kaufmann, San Mateo, 1991, pp. 69-93.

[13]

13. R. Grzeszczuk and D. Terzopoulos, "Automated learning of muscle-actuated locomotion through control abstraction," in Proceedings of the 22nd Annual Conference on Computer Graphics (SIGGRAPH 1995), in Computer Graphics Proceedings, Annual Conference Series, 1995, pp. 63-70.

[14]

14. S. Hirose, A. Morishima, and S. Tukagosi, "Design of practical snake vehicle: Articulated body mobile robot KR-II," in Proc IEEE 5th International Conference on Advanced Robotics, IEEE (ed.), IEEE: New York, 1991, pp. 833-838.

[15]

15. S. Hirose, Biologically Inspired Robots: Snake-Like Locomotors and Manipulators, Oxford University Press, 1993.

Digital Library

[16]

16. K. Ito, T. Kamegawa, and F. Matsuno, "Extended QDSEGA for controlling real robots-acquisition of locomotion patterns for snake-like robot," in Proceedings of IEEE International Conference on Robotics and Automation (ICRA 2003), IEEE (ed.), IEEE: New York, 2003, pp. 791-796.

[17]

17. K. Ito and F. Matsuno, "A study of reinforcement learning for the robot with many degrees of freedom - acquisition of locomotion patterns for multi legged robot," in Proceedings of IEEE International Conference on Robotics and Automation (ICRA 2002), IEEE (ed.), IEEE: New York, 2002, pp. 3392- 3397.

[18]

18. S. Kamio, H. Mitsuhashi, and H. Iba, "Integration of genetic programming and reinforcement learning for real robots," in Proceedings of the Genetic and Evolutionary Computations Conference (GECCO 2003), Erickdr Cantu-Paz, et al. (eds.), Springer: Berlin, 2003, pp. 470-482.

[19]

19. H. Kimura, T. Yamashita, and S. Kobayashi, "Reinforcement learning of walking behavior for a four-legged robot," in Proceedings of the 40th IEEE Conference on Decision and Control (CDC 2001), J. Jim Zhu (ed.), IEEE: New York, 2001, pp. 411-416.

[20]

20. M. W. Kirschner and J. C. Gerhart, The Plausibility of Life: Resolving Darwin's Dilemma, Yale University Press, 2005.

[21]

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

[22]

22. J. R. Koza, M. A. Keane, J. Yu, F. H. Bennett III, and W. Mydlowec, "Automatic creation of human-competitive programs and controllers by means of genetic programming," Genetic Programming and Evolvable Machines, vol. 1, pp. 121-164, 2000.

Digital Library

[23]

23. I. B. Levitan and L. K. Kaczmarek, The Neuron: Cell and Molecular Biology, Oxford University Press: New York, 2002.

[24]

24. S. Mahdavi and P. J. Bentley, "Evolving motion of robots with muscles," in Proc of the the EvoROB2003, the 2nd European Workshop on Evolutionary Robotics, C. Ryan, T. Soule, et al. (eds.), EuroGP 2003, Springer: Berlin, pp. 655-664.

[25]

25. M. O'Neill and C. Ryan, Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language, Springer: Berlin, 2003.

[26]

26. J. Ostrowski and J. Burdick, "Gait kinematics for a serpentine robot," in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 1996), IEEE (ed.), IEEE: New York, 1996, pp. 1294-1299.

[27]

27. M. Pelikan, D. E. Goldberg, and E. Cantú-Paz, "BOA: the Bayesian optimization algorithm," in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99), W. Banzhaf, J. Daida et al. (eds.), Morgan Kaufmann Publishers: San Francisco, CA, 1999, pp. 525-532.

[28]

28. R. Pfeifer and C. Scheier, Understanding Intelligence, MIT Press: Cambridge, 2001.

[29]

29. B. Salemi, P. Will, and W.-M. Shen, "Distributed task negotiation in self-reconfigurable robots," in Proceedings of the IEEE/RSJ International Conference on Intelligent Robotics and systems (IROS 2003), IEEE (ed.), IEEE: New York, 2003, pp. 2448-2453.

[30]

30. R. Salustowicz and J. Schmidhuber, "Probabilistic incremental program evolution," Evolutionary Computation , vol. 5, pp. 123-141, 1997.

Digital Library

[31]

31. Y. Shan, R. I. McKay, and R. Baxter, "Grammar model-based program evolution," in Proceedings of the 2004 IEEE Congress on Evolutionary Computation, IEEE (ed.), Portland, Oregon, IEEE, New York, 20-23 June, 2004, pp. 478-485.

[32]

32. R. Smith, "Open Dynamics Engine," 2001-2006, URL: http://q12.org/ode/

[33]

33. K. Stoy, W.-M. Shen, and P. M. Will, "A simple approach to the control of locomotion in self-reconfigurable robots," Robotics and Autonomous Systems, vol. 44, pp. 191-200, 2003.

[34]

34. G. S. Hornby, S. Takamura, T. Yamamoto, and M. Fujita, "Autonomous evolution of dynamic gaits with two quadruped robots," IEEE Transactions on Robotics, vol. 21, pp. 402-410, 2005.

Digital Library

[35]

35. I. Tanev and T. Ray, "Evolution of sidewinding locomotion of simulated limbless, wheelless robots," Artificial Life and Robotics, Springer, 2005, vol. 9, pp. 117-122.

[36]

36. I. Tanev, T. Ray, and A. Buller, "Automated evolutionary design, robustness and adaptation of sidewinding locomotion of simulated Snake-like robot," IEEE Transactions on Robotics, vol. 21, pp. 632-645, 2005.

Digital Library

[37]

37. M. L. Wong, "Evolving recursive programs by using adaptive grammar based genetic programming," Genetic Programming and Evolvable Machines, vol. 6, pp. 421-455, 2005.

Digital Library

Cited By

Nametala CFaria WPereira Júnior B(2022)On the performance of the Bayesian optimization algorithm with combined scenarios of search algorithms and scoring metricsGenetic Programming and Evolvable Machines10.1007/s10710-022-09430-223:2(193-223)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s10710-022-09430-2
Kim KShan YNguyen XMckay R(2014)Probabilistic model building in genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-013-9205-x15:2(115-167)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1007/s10710-013-9205-x
Fukunaga AHiruma HKomiya KIba H(2012)Evolving controllers for high-level applications on a service robotGenetic Programming and Evolvable Machines10.1007/s10710-011-9152-313:2(239-263)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1007/s10710-011-9152-3

Index Terms

Genetic programming incorporating biased mutation for evolution and adaptation of Snakebot

Recommendations

Incorporating learning probabilistic context-sensitive grammar in genetic programming for efficient evolution and adaptation of snakebot
EuroGP'05: Proceedings of the 8th European conference on Genetic Programming

In this work we propose an approach of incorporating learning probabilistic context-sensitive grammar (LPCSG) in genetic programming (GP) employed for evolution and adaptation of locomotion gaits of simulated snake-like robot (Snakebot). In our approach ...
Learned mutation strategies in genetic programming for evolution and adaptation of simulated snakebot
GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

In this work we propose an approach of incorporating learned mutation strategies (LMS) in genetic programming (GP) employed for evolution and adaptation of locomotion gaits of simulated snake-like robot (Snakebot). In our approach the LMS are ...
On the cumulative effect of bloat and genetic transposition on the efficiency of incremental evolution of snake-like robot
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

We present a study on the cumulative effect of the bloat and the seeding of the initial population, inspired by genetic transposition (GT), on the efficiency of incremental evolution of simulated snake-like robot (Snakebot). In the proposed incremental ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Genetic Programming and Evolvable Machines

Genetic Programming and Evolvable Machines Volume 8, Issue 1

March 2007

106 pages

ISSN:1389-2576

Issue’s Table of Contents

Copyright © Copyright © 2007 Springer Science+Business Media, LLC.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 March 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nametala CFaria WPereira Júnior B(2022)On the performance of the Bayesian optimization algorithm with combined scenarios of search algorithms and scoring metricsGenetic Programming and Evolvable Machines10.1007/s10710-022-09430-223:2(193-223)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s10710-022-09430-2
Kim KShan YNguyen XMckay R(2014)Probabilistic model building in genetic programmingGenetic Programming and Evolvable Machines10.1007/s10710-013-9205-x15:2(115-167)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1007/s10710-013-9205-x
Fukunaga AHiruma HKomiya KIba H(2012)Evolving controllers for high-level applications on a service robotGenetic Programming and Evolvable Machines10.1007/s10710-011-9152-313:2(239-263)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1007/s10710-011-9152-3

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents