Journal of Robotics, Networking and Artificial Life, Vol. 2, No. 3 (December 2015), 144-147

The Effect of Duration of Both Stages of Incremental Genetic Programming on its Efficiencyof Evolution of Snakebot
Naoki Mukosaka, Yasuto Nishiwaki, Ivan Tanev, Katsunori Shimohara

Graduate School of Science and Engineering, Doshisha University,
1-3 Tatara-Miyakotani, Kyotanabe, Kyoto 610-0321, Japan

E-mail: mukosaka2012@sil.doshisha.ac.jp, nishiwaki2012@sil.doshishsa.ac.jp, itanev@mail.doshisha.ac.jp,kshimoha@mail.doshisha.ac.jp
www.doshisha.ac.jp

Abstract
The objective of our work is to investigate the optimal combination of durations of both stages of incremental
Genetic Programming (IncGP) on the simulated Snake-like robots (Snakebots). The obtained results suggest thatthe number of generations cannot be used as criteria for separating the two stages of IncGP. We hypothesized that
qualitative criterion, such as the emergence of smooth sidewinding locomotion at the first stage of evolution could
be used instead, and conducted additional experiments that proved its worthiness.
Keywords: Genetic Programming, Snake-like Robot, Incremental Genetic Programming, Evolution.

1. Introduction
Compared to the wheeled and legged vehicles, thewheel-less, limbless Snake-like robots (Snakebots) are
more robust and adaptable to both the environmental
changes and partial damage. Some of the useful featuresof Snakebots include smaller size of the cross-sectionalarea, stability, ability to operate in rugged terrain, goodtraction, high redundancy, and complete sealing of theinternal mechanisms1. Due to the morphologicalcomplexity of Snakebots, an automated approach ofdeveloping their controller via Genetic Programming(GP) is often used1.
However, the evolution of Snakebot from scratch
via GP is rather inefficient when the bot is situated in achallenging environment. The main reason for such
inefficiency is that the evolution needs tosimultaneously discover both (i) the generic locomotion
traits (that are common for all well-moving bots,
regardless of the environment) and (ii) the specific traits
that are needed to overcome the obstacles in thesechallenging terrains.
In order to improve the efficiency of such anevolution, in our previous work2, we divided the task ofevolving the locomotion of simulated Snakebot inchallenging terrain into two consecutive, simpler subtasks, implemented as two consecutive stages of anincremental Genetic Programming (IncGP): at the firststage we applied GP to evolve a pool of bots that areable to move fast in a smooth, open terrain. Then,
during the second stage, we used this pool to seed thePublished by Atlantis Press
Copyright: the authors
144

Naoki Mukosaka, Yasuto Nishiwaki, Ivan Tanev, Katsunori Shimohara

initial population of the bots that are further subjected toevolution in the challenging environment. We
demonstrated that the two-staged incremental evolution
via IncGP, consisting of two stages of 40 generations
each, features a much improved efficiency over thecanonical GP2.
The objective of our current work is to investigate
the optimal combination of durations of both stages ofincGP. We assume a fixed runtime budget of evolution,corresponding to 80 generations overall. Therefore, ourexperiments involved evolution of Snakebot via incGP
with 7 combinations of durations of both stages ofevolution: from 10 generations of the first stage and 70
generations of the second one, to 70 generations of thefirst and 10 generations of the second one (i.e., 10 and70, 20 and 60, 30 and 50,…, and, finally, 70 and 10,respectively).
2. Simulated Snakebot
In our work we used the Open Dynamics Engine3(ODE) physics library to simulate the articulated rigid
body dynamics of the Snakebot2. ODE allows
accounting for all forces, resulting from friction,gravity, actuators, and collisions between the segmentsof the simulated bot, and the environment. The
Snakebot is identical to the one as used in our prior
work1, 2, 4, and 5. It is simulated as 15 identical sphericalmorphological segments (“vertebrae”). Pairs of nearby
segment are linked by universal (Cardano) joints and all
joints are powered by two (horizontal and vertical)
identical actuators (“muscles”).
In this study we use IncGP to evolve such motion
patterns of the segments of the bot that result in fastest
speed of locomotion of the bot. Considering therepresentation of Snakebot, this task could be rephrased
as developing the temporal patterns of desired turning
angles of horizontal and vertical actuators of eachsegment, that result in fastest overall locomotion ofSnakebot. The proposed representation of Snakebot as ahomogeneous
systemcomprisingidentical
morphological segments is intended to significantly
reduce the size of the search space of the IncGP (as weneed to evolve the functionality of one pairs of actuators
only) and to facilitate favorable scalability
characteristics of the latter.
3. Simulation Setup
We employed IncGP in
evolutionary stages as follows:

twoconsecutive

 First, we implemented 30 independent runs ofcanonical GP to evolve the Snakebot in a smoothterrain for N generations (N=10, 20, 30, …, 70), andcreated a pool of 6 best-of-run, fast moving
Snakebots for each corresponding value of N.
 In the second stage of IncGP, we conducted
additional 30 independent runs, (for 80-Ngenerations) to evolve the bot, situated in achallenging terrain. The initial population of each ofthese runs is seeded with the 6 fast moving bots,obtained in the first stage of GP, plus additional 194
randomly created bots. For the second stage ofIncGP, we considered two cases of challenging
environment, and one case of partial damage, aselaborated below.
The considered two cases of challenging terrain
include (i) a “pen” of walls (which surrounds the botfrom all four sides), and (ii) multiple small immobile(i.e., fixed to the ground) obstacles. In the first case, theheight of the wall is automatically increased each time
the bot overcomes it. Therefore, the maximum height ofthe cleared wall (at the end of evolutionary run) could
be viewed as a measure of the ability of the bot toovercome walls. In the second case, the average speedof the bot (calculated from the travelled center of thegravity of the latter and the time of the trial) is
considered as a measure of the ability of bot toovercome obstacles.
In addition, we conducted experiments with IncGPon evolutionary adaptation of the bot to its partial
damage to 6 (out of 15) segments. In this case, we
assumed that the damage renders the joint at the tailside of the affected segment completely immobile.
The main parameters of IncGP are summarized inTable 1. We used our in-house DOM/XML-based
implementation of GP6.
Table. 1. Main parameters of IncGPCategory
Genotype
Population size
Selection
Elitism
Mutation

Published by Atlantis Press
Copyright: the authors
145

Value
Patterns of the turning angles of:(i) horizontal actuator, and(ii)Vertical actuator
200 individuals
Binary Tournament, ratio: 0.1
Reproduction ratio: 0.9
Best 4 individuals
Random, single point, ratio: 0.01

The Effect of Duration

4.

Experimental Results

The experimental results of each of cases are shownin Fig.1, Fig.2, and Fig.3, respectively.

of the Snakebots (in tree nodes) evolved in the firststage, and (ii) the performance of the best-evolved bot at
the second stage of IncGP.
Table. 2. The complexity of genotypes and fitness values in
IncGP. FNavr and FFavr denote the average number of tree
nodes and the average fitness in the first stage of IncGP,
respectively. HofWavr is the height of wall that the bot
overcame in the second stage of IncGP. FMOavr and D6Favr
are the average fitness values in the second stage for the casesof environment with multiple small obstacles and damage tosix segments, respectively.

Fig. 1. Dynamics of the height of walls overcame by Snakebotin the second stage of IncGP. Unit on the ordinate corresponds
to 1/4th of the diameter of the spherical segments of the bot.

Duration of First(F) and second (S)stages of IncGP
F:10 S:70
F:20 S:60

FNavr FFavr HofWavr FMOavr D6Favr
54.67 87.3
74
89.5

8.067
6.7

109
79.8

95.17
72.6

F:30 S:50
F:40 S:40

82.67 103
95.83 103

7.933
7.7

105
89.3

99.2
91.53

F:50 S:30
F:60 S:2093.17 107
68112

8.233
9.133

106
110

88.63
100.1

F:70 S:1077.67 100

6.667

91.4

79.07

Fig. 2. Fitness convergence of evolving Snakebot inchallenging environment with many small obstacles

Therefore, we hypothesize that the criteria forterminating the first stage of IncGP and initializing thesecond one might not be necessarily a quantitative one.
Rather, an aesthetic, intuitive, subjective, and informal
evaluation from the human about the presence ofgeneric locomotion would suffice for the switch
between the both stages of IncGP.
In order to verify this hypothesis, conducted
additional experiments intended to estimate theimportance of human-judged evaluation of theSnakebots as follows:

Fig. 3. Fitness convergence of evolving Snakebot with afailure of 6 (out of 15) segments

 First, we implemented 6 independent runs ofcanonical GP to evolve the Snakebot in a smoothterrain for N generations (N=10, 20, 30, …, 70), andcreated a pool of 6 fast moving Snakebots.
 In the second stage of IncGP, we conducted
additional 6 independent runs (for 80-N generation)of evolution of the bot, situated in the challenging
terrain. For the second stage of IncGP, we only
considered the case of “pen” of walls.

The statistical results including the complexity ofgenotype (in number of tree nodes) and fitness value aresummarized in Table 2.
5. Discussion
The experimental results suggest that neither thenumber of generations nor the obtained fitness value atthe first stage of IncGP can be used as criteria for
optimization of the duration of the two stages of IncGP.
Moreover, as the results in Table 2 indicate, there is nocorrelation between (i) the complexity of the genotype

We conducted the above mentioned experiments
four times for each combination of durations of bothstages. We looked at the visual phenotypic traits of thebest-of-run, fast moving generic bots obtained at thefirst stage of IncGP. We noticed that the number of bots

Published by Atlantis Press
Copyright: the authors
146

Naoki Mukosaka, Yasuto Nishiwaki, Ivan Tanev, Katsunori Shimoharathat move smoothly via sidewinding, and featuresinusoidal shape, correlates well with the degree ofsuccess at the second stage of IncGP. These results aresummarized in Fig.4. As figure illustrates, the quality ofthe bots (i.e., the maximum height of the wall itovercomes), evolved in the second stage of IncGP,increases with the increase of the number of smoothsidewinders from one to four in the pool of the six bots
used for seeding of the second stage of IncGP.
Additional increase of the number of smoothsidewinders to five and six is associated with a decreaseof the quality in bots evolved at the second stage ofIncGP. The reason for such an anomaly is that
achieving five or six smooth sidewinding bots at thefirst stage usually requires an evolution for too many
generations N, and the remaining budget of the numberof generations (80-N) for the second stage does notallow enough time for the bot to learn how to overcometall walls. From another perspective, the nonmonotonous nature of the dependency illustrated in
Fig.4 suggests that there is an optimal point in
configuring the IncGP, and that our consideration of thevisual, qualitative phenotypic traits of the evolved
Snakebots facilitated the discovery of this point.

Fig. 4. Maximum height of walls that are overcame by
Snakebot in second stage as a function of the number ofsmooth sidewinding bots evolved in first stage of IncGP.

6. Conclusion
In this paper, we investigated the effect of durationof both stages of incremental genetic programming on
its efficiency of evolution of Snakebot. We discoveredthat the success of the second stage does not depend on
the quantitative metrics (e.g., number of generations,fitness value, complexity of genotype, etc.) pertinent to
the first stage of evolution of the bot. Consequently, wecould conclude that these quantitative metrics could not
be used as reliable criteria to decide the switch from thefirst stage of IncGP to the second one.

We experimentally proved our hypothesis that thesmooth sidewinding with an aesthetically wellperceived sinusoidal shape of the bot can be consideredas phenotypic traits of the generic locomotion gaits thatare very important for the success of the second stage ofevolution. Once the evolution discovers these genericgaits, it could terminate the first stage of evolution andswitch its efforts to the second stage. During the latter,these generic gaits could be enhanced further byincorporating additional features that are specificallyneeded to deal with the surrounding challenging terrain.
This discovery opens up the opportunity for an original
way of incorporating interactive evolution into IncGP ina way that allows a human to subjectively influence theoptimal breakdown between the both stages of IncGP.
We are planning to investigate this opportunity in ourfuture work.
Acknowledgement
The first author would like to thank the members of
the Laboratory of Socioinformatics at Doshisha
University for their support of this study.
References
1. 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, Number 4, August 2005,
pp.632-645
2. N. Mukosaka, I. Tanev, and K. Shimhara, Performance ofIncremental Genetic Programming on Adaptability of
Snake-like Robot, 17th Asia Pacific Symposium onIntelligent and Evolutionary Systems, IES2013, Volume 24,
2013, pp.152-157
3. R. Smith, Open Dynamics Engine, URL: http://ode.org/
4. T. Kuyucu, I. Tanev and K. Shimohara, Incremental Genetic
Programming Via Genetic Transpositions For Efficient
Coevolution Of Locomotion And Sensing Of Simulated
Snake-Like Robot Proceedings of the 20th he European
Conference on Artificial Life (ECAL-2011), 8th - 12thAugust 2011, Paris, France, pp. 439-446
5. I. Tanev, T. Kuyucu, and K. Shimohara, On the Cumulative
Effect of Bloat and Genetic Transposition on the Efficiency
of Incremental Evolution of Snake-like Robot Genetic andEvolutionary Computation Conference, GECCO-2012, July
7-11, 2012, Philadelphia, USA, pp.161-168
6. I. Tanev. Dom/xml-based Portable Genetic Representationof the Morphology, Behavior and Communication Abilities
of Evolvable Agents, Artificial Life and Robotics, 2004,
8:52–56

Published by Atlantis Press
Copyright: the authors
147