The problem
Automated valet parking and low-speed navigation need a global route through a car park. A* on an occupancy grid is the standard starting point because it is simple, complete and fast, but its output depends on grid resolution, heuristic choice and obstacle inflation, and its grid paths are not directly drivable by a car.
Objectives
- Build occupancy grid maps of parking lots with configurable resolution.
- Implement A* and Dijkstra with 4- and 8-connected neighbours.
- Compare heuristics for optimality and nodes expanded.
- Inflate obstacles for vehicle size and smooth the path for drivability.
What you need
Tools and toolboxes
- Python with NumPy and Matplotlib — Grid maps, A* implementation with heapq, and visualisation.
- MATLAB — An alternative implementation; binaryOccupancyMap and plannerAStarGrid from Navigation Toolbox as a reference.
- Navigation Toolbox (optional) — plannerAStarGrid and inflate to cross-check your implementation.
Software
- Python 3 with NumPy, SciPy and Matplotlib, or MATLAB with Navigation Toolbox
Extra parts and data
None beyond the software above.
Key concepts
- Occupancy grid
- A map divided into cells marked free or occupied. Resolution sets the trade-off between path accuracy and search effort.
- Admissible heuristic
- An estimate of remaining cost that never overestimates it, such as straight-line distance; it guarantees A* finds the shortest path.
- Configuration-space inflation
- Growing obstacles by the vehicle's radius so the vehicle can be planned as a point.
Step-by-step guide
- 1
Define the task
State the problem: find the shortest collision-free route from a car park entrance to a target bay on a 2D map, for a car approximated by a circle of given radius. Define metrics: path length, nodes expanded, planning time, minimum clearance and number of sharp turns. Decide on test resolutions such as 0.5, 0.25 and 0.1 m per cell and list map variants.
Checkpoint: A short specification with metrics and test conditions.
- 2
Build the maps
Draw three car park layouts to scale: an open lot with rows of bays, a lot with pillars and a narrow multi-row layout. Create them as images or arrays of free and occupied cells, with aisles about 6 m wide and bays about 2.5 by 5 m, adjusting to the layout you model. Write a function to convert between metres and grid indices. Mark entrance and several goal bays.
Checkpoint: Three maps plotted at each resolution with entrance and goals marked.
- 3
Inflate obstacles
Compute the vehicle's bounding circle radius from half its diagonal, or a smaller radius if using multiple circles, and inflate obstacles by that radius using a distance transform (scipy.ndimage.distance_transform_edt) or binary dilation. Plot inflated maps and check that aisles remain passable. Note where conservative inflation blocks narrow but feasible gaps. Compare a single bounding circle with two or three smaller circles along the car's length, and record how much free space each approximation recovers in narrow aisles.
Checkpoint: Inflated maps with passable aisles and noted problem spots.
- 4
Implement A* and Dijkstra
Write A* with a priority queue (heapq), storing g-cost, parent and a closed set. Support 4- and 8-connected moves, with diagonal cost of square root of two. Implement Dijkstra as A* with a zero heuristic. Add counters for expanded nodes and timing. Test on a tiny hand-made grid where the correct answer is known before running on car park maps.
Checkpoint: Both algorithms return the known shortest path on the hand-made grid.
- 5
Compare heuristics
Run A* with Manhattan, Euclidean and octile heuristics, plus a weighted A* with inflated heuristic (for example 1.5 times Euclidean). Record path length, nodes expanded and time for every map, resolution and goal. Confirm that admissible heuristics give the same optimal length as Dijkstra while expanding fewer nodes, and quantify how weighted A* trades optimality for speed. Repeat timing runs several times and report the median, since short run times are noisy.
Checkpoint: A results table showing optimality and nodes expanded per heuristic.
- 6
Add clearance cost
Grid paths often hug inflated obstacles. Add a cost term that penalises cells close to obstacles, using the distance transform, so paths keep to aisle centres. Compare minimum and mean clearance and path length with and without this term. Choose a weight that improves clearance without large detours. Keep the clearance weight in a configuration file and plot path length and minimum clearance against it, so the chosen value is justified by the trade-off rather than picked by eye.
Checkpoint: Paths that stay nearer aisle centres with a small increase in length.
- 7
Smooth the path
Remove redundant waypoints with line-of-sight shortcutting, checking each shortcut against the inflated map, then fit a smoothing spline. Compute curvature along the result and compare it with the car's maximum curvature (one over minimum turning radius). Report where the smoothed path is still too sharp, which motivates kinematic planners such as Hybrid A*. Plot the original, shortcut and smoothed paths together on the inflated map for each test case.
Checkpoint: Smoothed paths plotted with curvature, and infeasible segments highlighted.
- 8
Evaluate and report
Summarise results across maps, resolutions and heuristics in tables and plots. Discuss the resolution trade-off, heuristic behaviour and the limits of grid planning for a car that cannot turn on the spot. Cross-check a few cases with plannerAStarGrid if MATLAB is available. Include all code and maps so results can be reproduced. Add a short section explaining how resolution affects both path quality and memory use, with numbers from your runs.
Checkpoint: A report with comparison tables, path plots and a clear discussion of limitations.
Testing & validation
- Path length equal to Dijkstra for admissible heuristics.
- Nodes expanded and planning time per heuristic and resolution.
- Minimum clearance before and after the clearance cost.
- Curvature of smoothed paths against the vehicle's limit.
Expected results
A tested A* planner for car park grids with heuristic and resolution comparisons, clearance-aware costs and smoothing, and a clear picture of where grid planning stops being drivable.
Take it further
- Implement Hybrid A* to respect vehicle kinematics.
- Add dynamic obstacles and replanning with D* Lite.
- Track the smoothed path with pure pursuit in simulation.
Viva and review questions
Why does an admissible heuristic guarantee an optimal path?
Because it never overestimates the remaining cost, A* cannot close the goal through a longer path while a shorter one remains in the open list.
Why inflate obstacles?
So the vehicle can be planned as a point; any free cell in the inflated map is a position where the vehicle's circle does not touch an obstacle.
Why is a grid A* path not directly drivable?
It can contain sharp turns and sideways steps that violate the car's minimum turning radius and non-holonomic constraints.
Learn it at DIYguru
These DIYguru courses and programmes teach what this project needs.