Page 225 - Innovations in Intelligent Machines

218 S. Pr¨uter et al.
Length x 1 y 1 x 2 y 2 x 3 y 3

Fig. 24. Gene Encoding of an Individual

a parameter. A complete set of genes forms an individual. A new generation
is formed by selecting the best individuals from the parent generation and
applying evolutionary methods, such as recombination and mutation. After a
new generation is generated, each offspring is tested with a fitness function.
From all offspring, and in case of (µ + λ)-strategy also from the parents, the
µ best individuals are chosen as the parents of the next generation. µ usually
denotes the number of parents whereas λ is the number of generated children
for the next generation.

5.1 Gene Encoding

To apply genetic algorithms to the problem of path planning, the path needs
to be encoded into genes. An individual represents a possible path. The path
is stored in way points. The start and the destination point of the path are
not part of an individual. As the needed number of way points is not known
in advance, it is variable. Consequently, the gene length is variable too.
As shown in Fig. 24, each way point is stored in its x and y coordinates
as integer values.
The obstacles are relatively small compared to the size of the field and
their number cannot exceed nine because each team consists of five robots.
This leaves enough room for navigation, three way points between start and
end positions are sufficient to find a route. Therefore, the maximal number of
way points is set to three.

5.2 Fitness Function
The fitness function is important for the algorithm’s stability, because an inad-
equate function may lead to either stuck at local minima or oscillations around
an optimum. Fitness functions are usually constructed by accumulation of
weighted evaluation functions. In case of path planning, needed evaluation
functions are the path length and a collision avoidance term.
When choosing the representation of the obstacles, it needs to be consid-
ered that the calculation is done on the robot. Therefore, the memory footprint
is a very important factor.
Each obstacle is stored with its coordinates and its size. This allows for
obstacles of any shape. Vectored storing of obstacles provides a higher accu-
racy and a lower memory consumption but also rises the calculation effort.
The error function consists of the path length and the collision penalty
where path i denotes the length of the sub path, d i the distance between path
and the obstacle center in case the obstacle is hit, r o the radius of the obstacle,