Genetic Algorithm Path Planning · Population of Waypoint Sequences
Abstract
A genetic algorithm encodes paths as fixed-length sequences of intermediate waypoints, evolves a population of 60 candidates over 120 generations, and returns the best solution. Selection is truncation (keep the top half), recombination is uniform crossover at the waypoint level, mutation is Gaussian. Fitness is path length plus a hard penalty for any segment that intersects an obstacle. The method is a metaheuristic: it gives no completeness or optimality guarantees, but it produces among the shortest geometrically-valid paths of the four planners on this site when it does find a feasible solution.
Algorithm
individual: 6 (x, y) waypoints, real-valued, in the grid bounds
fitness: length(start, w_1, w_2, …, w_6, goal) + 50 · n_collisions
selection: sort by fitness, keep top 30 (truncation)
crossover: uniform per waypoint between two random survivors
mutation: Gaussian noise σ = 1.5 grid units, applied to 15 % of
waypoint coordinates, then clipped to the grid bounds
Population size = 60, generations = 120. The collision penalty (50 × number of segments crossing an obstacle) is large enough that any feasible candidate dominates any infeasible one in the ranking, but small enough that the gradient toward feasibility is smooth.
Diagnostic: Convergence and Best Path
The left panel shows best-of-population fitness vs generation: a steep early descent as the random initial population is replaced by feasible offspring, then a slow refinement of path length. The right panel shows the best individual's path on environment 0.
Headline Numbers
| Environment | Outcome | Plan time | Path length | Length vs A* |
|---|---|---|---|---|
| 0: scattered rectangles | success | 3274 ms | 38.42 | −4 % |
| 1: maze channels | no feasible | 2727 ms | n/a | n/a |
| 2: bottleneck | success | 3137 ms | 39.84 | −7 % |
| 3: cluttered | success | 2960 ms | 39.01 | +1 % |
When the GA solves a problem, it produces among the shortest paths of the four planners: within ±7 % of A* and visibly straighter than RRT. The cost is wall-clock time: 3 seconds against A*'s 1–3 ms. The maze is a soft failure: 120 generations is not enough to evolve a 6-waypoint path through a tight corridor with multiple constrained turns. A larger waypoint count or a problem-aware mutation operator would help.
When a metaheuristic earns its place
- Multi-objective fitness. If the score combines length, energy, smoothness, and risk in ways that destroy admissibility for A* and break the metric structure RRT* needs, a GA can optimise the composite objective directly.
- Discontinuous obstacle representations. GAs do not need a metric or a heuristic; they only need a fitness function evaluator. That is generous about how obstacles are described.
- Anytime planner. Like RRT, the GA always has a current-best individual that improves with more generations.
Against A* on a clean grid problem, a GA loses on every dimension that matters: optimality, completeness, run-time. Its place is in the problems where A* and RRT do not apply cleanly.
Cross-Planner Comparison on env 0
