Page 140 - Innovations in Intelligent Machines

Evolution-based Dynamic Path Planning for Autonomous Vehicles 131
Index Score Index Score
1 3 Fitness 1 3
2 270 2 2
3 3
486
4 4
120
5 5
360
6 6
167
7 7
randomly
8 8
select
Fig. 10. Illustration of the tournament selection scheme. The plan with index num-
ber 2 is compared to other four randomly selected plans

For each individual i ∈{1, 2,... , (µ + λ)}:
1. Draw q ≥ 2 individuals randomly from the population (excluding individ-
ual i) with uniform probability 1 . Denote these competitors by the
µ+λ−1
indices {i 1 ,i 2 ,...,i q }.
2. Compare individual i’s fitness against each of the competitors, i j ,j ∈
1, 2,... ,q. Whenever the fitness of individual i is not worse than that of
competitor i j , individual i scores a point.
The score that each individual receives during the tournament is an integer
in the range [0,q]. After the scores of all individuals are determined, the top
µ individuals with the best scores are selected as the parents for the next
generation.

Path Planning Example

To demonstrate the performance of the planning algorithm, we present the
results of a static path planning problem. In this problem, the mission objec-
tive is to observe all the assigned targets and return safely to the goal location.
The path planner runs the evolutionary algorithm with a population size of
30. The tournament selection algorithm selects 15 of them to be parents for
the next evolution cycle. The score weighting function of each task is shown
in Figure 11. Unless otherwise specified, the profile of this function is the same
for this example and all other planning examples presented in other sections.
The performance of the the planning algorithm was validated using the
Open Experimental Platform (OEP) simulation program developed by the
Boeing Company. The OEP is designed for evaluation of planning and coordi-
nated control methodologies in a Monte Carlo simulation. System parameters
can be specified as constants or random variables with specific probability
distributions. The OEP can simulate large numbers of vehicles and targets.