Overview
Built an autonomous, genetic-algorithm based path planning algorithm from first principles.
What it does
Generates collision-free paths a robot can take on a 500 x 500 binary map using a Genetic Algorithm. Supports three selection strategies, two crossover operators and adaptive mutation/immigration rates to converge quickly on near-optimal paths.
Why it’s interesting
Demonstrates how low-level GA techniques can solve real-world motion-planning problems without external libraries.
Key Technical Points
- Fully modular: Supports roulette-wheel, tournament and rank-based selection alongside both uniform and 2 point crossover with both swap mutation and creep mutation.
- Adaptive operators: Crossover probability decays while mutation probability rises, plus an immigration strategy to maintain diversity.
- Advanced Strategies: Used complex strategies like elitism and immigration to preserve strong solutions whilst maintaining diversity. Also added convergence, stagnation and max generation checks to allow for early termination.
- Fitness function: Combines Euclidean path length with heavy obstacle penalties, yielding robust solutions even on noisy maps.
- Fast execution & Profiling: Reduced runtime by favouring vectorised MATLAB operations over iteration-heavy methods and profiling key GA stages to identify bottlenecks.
Tech Stack
Language: MATLAB