Featured Robotics Project
Escape Challenge
Autonomous exploration + mapping + escape behavior using obstacle distance grids, A* planning, frontier exploration, and a simple state machine.
What it does
Explores a maze, builds a map, returns home, then escapes after an “edge removal”.
Core algorithms
Obstacle distance grid + 8-way A* + frontier detection + centroid navigation.
Safety
Blocks cells near obstacles and biases paths away from walls.
Obstacle Distance Grid
Turns raw mapping into “safe-to-traverse” planning space.
Key details
- Assumes the environment is mostly static while mapping.
- Models the robot as a point by “growing” obstacles to handle robot footprint.
- Uses 8-way expansion so diagonal travel is allowed (efficient paths).
A* Planning
Fast, direct paths using an 8-connected grid.
Heuristic
Euclidean distance pairs naturally with 8-way expansion and supports diagonal shortest paths.
- Considered alternatives: Manhattan (4-way) and diagonal distance heuristics.
- Rotation cost could be added by weighting turn magnitude into g(x).
Reality vs tests
Some scripted cases may fail even if real-world runs succeed due to sensor noise + replanning.
Frontier Detection
Frontiers are the boundary between known free space and unknown space.
Definition + growth
- A cell is a frontier if it’s free and adjacent to unknown space.
- Frontier cells are grown/clustered into connected components.
- Navigates toward the middle to maximize new mapped area.
Limitation
Noise can create tiny “fake” frontiers. A gain-based method could prioritize higher information gain targets.
Exploration Behavior
Why centroid navigation works—and where it breaks.
- Centroids may be unreachable or sit inside tight geometry.
- Doesn’t prioritize closest reachable frontier points (can waste time/energy).
- Treats frontiers “equally” instead of choosing the most promising region.
Safety + Parameters
Hard constraints + soft bias away from obstacles.
Hard safety block
Cells within 0.05 m of occupied cells are treated as blocked.
Soft safety bias
A safety weighting factor of 0.6 biases the path away from obstacles.
Escape Logic
After edge removal, re-explore and drive toward the farthest frontier to exit.
Behavior
- Reset map after detecting edge removal (challenge-allowed approach).
- Navigate toward the largest / farthest frontier first to escape.
- Kept the Lab 12 state machine for clarity and reliability.
Reflection
Biggest improvements: better tuning/testing of safety distance (to prevent wall clips), and more principled detection of wall removal (phase out old map values instead of full reset).