paths might become feasible solutions after certain
genetic operations, they cause several problems. First,
a penalty term is needed to append to the fitness
function in order to distinguish feasible and infeasible
paths, which will inevitably increase the computation
load and decrease the search speed. Secondly, most of
the genetic operations to the infeasible paths are
meaningless. For instance, the crossover of two
infeasible individuals can hardly generate a feasible
one. Thirdly, some special genetic operators need to be
designed for these infeasible individuals. For example,
node-repair and line-repair operators in reference [8]
are specifically designed for repairing the infeasible
paths.
2.2.2 The obstacle avoidance algorithm. An obstacle
avoidance algorithm is proposed in this paper for
generating the first population. The proposed algorithm
consists of the following steps as illustrated in Fig. 2.
Y
A
X
B
Fig. 2
Diagram for the obstacle avoidance
algorithm
Step 1: Draw a line segment XY from the start node
X to the goal node Y.
Step 2: If XY intersects an obstacle area O, continue;
otherwise output XY as the shortest path.
Step 3: Select randomly one node A in the obstacle
area O and on XY and then draw an orthogonal line
(either right or left side) to XY from node A. If the
orthogonal line intersects a free area F, select one node
B in F randomly; otherwise stop.
Step 4: Connect nodes X and B, as well as nodes B
and Y.
Step 5: Replace B with Y in line segment XB and B
with X in line segment BY.
Step 6: Repeat steps 1 to 5 until none of the line
segments from X to Y intersects any obstacle area.
Step 7: A collision-free initial path is then generated
and encoded by the series of grid numbers of the line
segments from X to Y.
It should be noted that every orthogonal line from
one obstacle areas should be drawn to the same side
(right or left) as shown in Fig. 2.
Example: A 7×5 environment with one obstacle area,
as shown in Fig. 3, is used to illustrate the generation
process of initial paths. Here node 0 is the start node
and node 34 is the goal node.
28 29 30 31 32 33 34
21 22 23 24 25 26 27
14 15 16 17 18 19 20
7 8 9 10 11 12 13
0 1 2 3 4 5 6
(a) Generation process
28 29 30 31 32 33 34
21 22 23 24 25 26 27
14 15 16 17 18 19 20
7 8 9 10 11 12 13
0 1 2 3 4 5 6
(b) The final path
Fig. 3
Example of initial path generation with
consideration of one obstacle area
At first, a line segment between node 0 and node 34
is drawn, and it intersects with the obstacle area. Then
node 9 is selected randomly and an orthogonal line to
the right side from node 9 is produced. The orthogonal
line intersects the free area at node 3. As the line
segment between nodes 3 and 34 still intersects the
obstacle area, node 3 is set as the start node and node
34 as the goal node, and the above process is repeated.
After that, two line segments (one is between node 3
and node 5, the other is between node 5 and node 34)
are generated, and they no longer intersect the obstacle
area. Hence a collision-free initial path (0, 3, 5, 34) is
produced, as shown in Fig. 3(b).
Different initial paths could be generated as there are
various choices of intersection nodes in the obstacle
area or free area and the side (right or left) of the
orthogonal line.
If many obstacles exist in mobile robot environment,
we can separate the whole generation process with
multi-obstacles into several generation processes with
one obstacle each so that we can apply the obstacle
avoidance algorithm without any changes. Here is an
example.
Fig. 4 is a 10×10 grid environment with five
obstacles, with node 0 as the start node and node 99 as
the goal node. At first, a line segment between node 0
and node 99 is drawn, and it intersects the free area at
node 33 and node 44. Each node in the free area can be