Hybrid A* Planning for Automated Valet Parking

The problem

Automated valet parking must plan drivable paths in tight car parks with forward and reverse moves. Grid A* ignores vehicle kinematics and produces undrivable paths, while Hybrid A* searches over continuous poses with motion primitives and analytic Reeds-Shepp expansions. Its parameters strongly affect success, path quality and run time, and these need careful study.

Objectives

• Build car park maps and vehicle-aware costmaps.
• Plan forward and reverse paths with Hybrid A* for different bay types.
• Smooth and track the paths with a controller in a kinematic simulation.
• Study parameter effects on success rate, path quality and planning time.
• Compare with RRT* or grid A* plus smoothing as baselines.

What you need

Key concepts

Hybrid A*

A search over discretised cells that stores continuous poses, expanding with steering-constrained motion primitives so every path segment is drivable.

Reeds-Shepp curves

Shortest paths between two poses for a car that can drive forwards and backwards with a minimum turning radius; used to connect the search directly to the goal.

Analytic expansion

Periodically trying a Reeds-Shepp connection from the current node to the goal; if collision-free, the search ends early.

Direction-switch penalty

A cost on changing between forward and reverse, which reduces the number of gear changes in the final path.

Step-by-step guide

1. 1

   Define requirements

   Set the scope: low-speed planning (below 10 km/h) in a structured car park, with a given map, from a drop-off point to a free bay. Requirements: collision-free path with a clearance margin, a maximum number of direction changes for each bay type, planning time within a budget such as one second on a PC, and final pose within set position and heading tolerances. Choose a compact EV's dimensions and turning radius.

   Checkpoint: A requirements table with tolerances, clearances and timing budget.

2. 2

   Build maps and costmaps

   Create car park layouts with perpendicular, 45-degree angled and parallel bays, aisles of different widths and pillars. Represent them as occupancyMap objects at 0.1 to 0.2 m resolution. Create a vehicleCostmap with the vehicle's dimensions and an inflationCollisionChecker using several circles along the vehicle. Mark occupied bays randomly to generate many test cases. Check the collision checker on hand-placed poses that just touch and just clear a parked car before trusting it.

   Checkpoint: Maps for each bay type with collision checking that blocks the car from overlapping parked vehicles.

3. 3

   Configure Hybrid A*

   Create a stateSpaceSE2 with map bounds, a validatorOccupancyMap tied to the map and a plannerHybridAStar with minimum turning radius, motion primitive length, number of primitives, reverse cost, direction-switching cost and analytic expansion interval. Plan from start to a perpendicular bay goal and plot the result with forward and reverse segments coloured differently. Start with the default primitive settings, then confirm that the minimum turning radius you set matches the vehicle and that the path respects it everywhere.

   Checkpoint: A valid forward-and-reverse path into a perpendicular bay.

4. 4

   Plan all bay types

   Run the planner for perpendicular, angled and parallel bays, nose-in and reverse-in where relevant, from several start poses. Record success, path length, number of direction changes, minimum clearance and planning time. Inspect failures: whether the goal was unreachable, primitives too coarse, or the search ran out of iterations. Save every failed case with its start pose and map so it can be replayed after parameter changes, and keep a fixed random seed for the bay occupancy.

   Checkpoint: Per-bay-type success and quality statistics, with failure causes identified.

5. 5

   Smooth and time-parameterise

   Split each path at direction changes and smooth each segment with smoothPathSpline, then check the smoothed path still passes collision checks. Generate a speed profile with low maximum speed, acceleration limits and stops at each direction change. Compare curvature before and after smoothing and confirm it stays below the vehicle's maximum. If smoothing creates a collision, keep the original segment and note the case.

   Checkpoint: Smoothed, collision-free segments with speed profiles and curvature within limits.

6. 6

   Track the path in simulation

   Simulate a kinematic bicycle model following each segment with lateralControllerStanley, switching the controller direction for reverse segments, and a simple longitudinal speed controller. Measure tracking error and final pose error. Add small actuator delays and position noise to test robustness. Re-plan from the actual pose if the final error exceeds tolerance. Report how often replanning was needed and how much time it added to the manoeuvre.

   Checkpoint: Closed-loop runs that end within the final pose tolerance for most cases.

7. 7

   Run a parameter study

   Sweep motion primitive length, number of primitives, reverse cost, direction-switching cost and analytic expansion interval in a factorial or Latin hypercube design over many random car park cases. Record success rate, planning time, path length and direction changes. Fit simple models or plots that show which parameters matter most for each bay type. Use the same random cases for every setting so differences come from the parameters only.

   Checkpoint: Parameter-effect plots and a recommended setting per bay type.

8. 8

   Compare with baselines

   Run the same cases with grid A* followed by smoothing and with an RRT*-based planner using a Reeds-Shepp state space (plannerRRTStar with stateSpaceReedsShepp). Compare success rate, path quality and planning time. Discuss where each method fails, such as grid A* producing infeasible curvature and RRT* needing long run times for narrow bays. Give each planner the same time budget and collision checker so the comparison is fair.

   Checkpoint: A comparison table across planners and bay types.

9. 9

   Report

   Write up maps, planner configuration, smoothing, tracking, parameter study and baseline comparison. Include figures of representative paths and failure cases. Discuss what is needed for deployment, such as localisation accuracy, dynamic obstacles and handling of map errors, and relate it to the ODD of a valet parking function. Provide the final parameter table and scripts so the study can be repeated on new car park layouts.

   Checkpoint: A thesis chapter with quantified results and clear recommendations.

Testing & validation

• Planning success rate per bay type across random car park cases.
• Path length, direction changes and minimum clearance.
• Planning time distribution against the budget.
• Closed-loop tracking and final pose error.

Expected results

A Hybrid A* valet parking planner with smoothing and tracking, a parameter study that identifies key settings per bay type, and a comparison with grid A* and RRT* baselines.

Take it further

• Add moving pedestrians and replan in real time.
• Use a lidar-based occupancy map generated in simulation instead of a given map.
• Generate C code for the planner and measure execution time on an embedded processor.

Viva and review questions

Learn it at DIYguru

These DIYguru courses and programmes teach what this project needs.