MACOGA Path Planning

A reproducible ACO-GA grid path-planning experiment with geometric validation

Result at a glance

The committed figures and metrics were regenerated with seed=42, a 15 x 15 grid, and an obstacle ratio of 0.23.

Initial environment	Final path comparison

Stage	Nodes	Geometric length	Turns	Collision-free	Reaches goal
ACO	19	22.1421	8	Yes	Yes
GA	19	22.1421	6	Yes	Yes
Simplified	7	21.7858	5	Yes	Yes

For this seed, GA improves path smoothness rather than distance. The simplifier then removes redundant waypoints and slightly reduces geometric length. The repository reports this honestly instead of claiming every stage improves every metric.

Pipeline

flowchart LR
    A[Seeded grid generation] --> B[BFS reachability check]
    B --> C[Improved ACO]
    C --> D[GA selection / crossover / mutation]
    D --> E[Collision-aware simplification]
    E --> F[Metrics + five result figures]

Loading

1. Accessible environment

Obstacles are sampled from a seeded NumPy RNG. A bounded BFS validation rejects unreachable maps, avoiding the original unbounded recursive regeneration behavior.

2. ACO initialization

Thirty ants use pheromone intensity, goal-distance heuristics, and neighborhood information to search for a feasible path. Pheromone evaporation and deposition reinforce shorter valid paths.

3. GA refinement

The ACO result initializes the population. Selection uses fitness-weighted probabilities; crossover occurs at shared path nodes; mutation replans a subsegment with ACO. Crossover now produces two children and preserves population size instead of silently halving the population each generation.

4. Path simplification

Collinear points are removed first. A Bresenham-style collision check then reconnects non-adjacent nodes whenever the direct segment is obstacle-free.

Full visual trace

ACO pheromone map	GA path

Reproduce the experiment

python -m venv .venv
# Windows: .venv\Scripts\activate
# Linux/macOS: source .venv/bin/activate
pip install -r requirements.txt
pytest -q
python main.py --seed 42 --size 15 --obstacle-ratio 0.23 --output-dir results

The command is headless-safe and writes:

results/01_initial_environment.png
results/02_aco_result.png
results/03_ga_optimized.png
results/04_final_simplified.png
results/05_path_comparison.png
results/metrics.json

Change the random environment without changing code:

python main.py --seed 7 --size 30 --obstacle-ratio 0.20 --output-dir results_seed7

Repository map

File	Responsibility
environment.py	obstacle generation, BFS reachability, neighbors, collision checks
aco.py	ant path construction and pheromone update
ga.py	selection, population-preserving crossover, ACO mutation
path_simplification.py	collinearity removal and collision-aware reconnection
path_metrics.py	length, turn count, collision and endpoint validation
main.py	reproducible CLI experiment and figure generation
tests/	reachability, simplification, and population regression tests

Engineering improvements over the original reproduction

• Added a deterministic --seed and parameterized CLI.
• Replaced unbounded recursive map regeneration with bounded attempts and a clear failure.
• Fixed GA crossover population shrinkage.
• Removed interactive plotting from the core pipeline so CI and servers can run it.
• Added geometric metrics and validity checks rather than comparing node counts alone.
• Added regression tests and GitHub Actions.
• Regenerated the committed result gallery from the documented command.

What the metrics mean

• Nodes: stored waypoints, useful for controller and memory complexity.
• Geometric length: sum of Euclidean segment lengths, more meaningful than node count for diagonal motion.
• Turns: direction changes, a simple smoothness proxy.
• Collision-free: every segment passes the grid collision check.
• Reaches goal: path starts and ends at the configured endpoints.

Limitations

• One seed is a reproducible case study, not a statistical benchmark.
• The current fitness combines path length and angular smoothness with fixed weights.
• Dynamic obstacles, robot footprint, kinematic constraints, and execution noise are outside this grid experiment.
• A stronger evaluation would run many seeds and compare ACO, ACO-GA, A*, and RRT* with confidence intervals.

Interview summary

I reproduced an ACO-GA path-planning pipeline, then improved its engineering validity. I found that crossover reduced the population size each generation, fixed it to preserve two offspring per pair, made map generation deterministic and bounded, added headless execution and geometric metrics, and verified the result with regression tests. On seed 42, GA reduced turns from 8 to 6 while simplification reduced the path from 19 to 7 waypoints without introducing collisions.

Historical material

The repository retains the original reproduction presentation and work report for learning provenance. They are not required to run the experiment.