Planning and navigation
Represent free space and costs explicitly, then compare a planned path with the robot’s footprint, uncertainty, and replanning rules.
- Trace a shortest-path search on a small cost grid, inflate obstacles for robot size, and define when new evidence invalidates a plan.
Related study — optional context
Understand
The working idea
Planning chooses a sequence of actions toward a goal; navigation executes and revises that plan using localization and perception. A route for a point drawn on paper is not automatically safe for a robot with width, turning limits, and uncertain pose. The map is a model: cells or geometric regions may be free, occupied, unknown, or assigned traversal cost.
A graph represents possible states as nodes and allowed moves as edges. Dijkstra’s algorithm expands the lowest accumulated cost g. A* expands by f = g + h, where h estimates remaining cost. If h never overestimates the true remaining cost, A* can retain shortest-path guarantees under its assumptions while exploring fewer nodes. On a four-neighbor grid with unit moves, Manhattan distance |Δx| + |Δy| is an admissible heuristic. Edge costs can represent distance, time, energy, or risk, but mixing units without an explicit weighting produces meaningless optimization.
Robot footprint matters. Configuration-space reasoning expands obstacles by the robot’s radius, then plans the center as if it were a point. A 300 mm-wide robot needs more than a 300 mm nominal gap once clearance and localization uncertainty are included. Choosing 200 mm obstacle inflation for a 150 mm half-width plus 50 mm margin is a concrete build decision; the margin must be justified and tested.
A common misconception is that the shortest grid path is a drivable trajectory. It may contain instantaneous 90° turns, graze inflated corners, or cross space that changed after mapping. A local controller must follow a feasible trajectory and stop or replan when observations contradict the map. Another failure is treating unknown as free merely to find a route. Define map resolution, footprint, cost meaning, goal tolerance, stale-data limits, and replanning triggers. Planning cannot compensate for an unlocalized robot or a sensor that cannot observe the relevant hazard.
Follow the reasoning
Worked example
A four-neighbor grid uses 0.10 m cells. A path takes 7 orthogonal moves around an obstacle. A direct-looking alternative takes 5 moves but crosses one cell with added risk cost 4. Which has lower stated cost if each move costs 1?
- 1
Detour cost = 7 moves × 1 = 7.
- 2
Risky path cost = 5 move cost + 4 risk cost = 9.
- 3
Geometric lengths are 0.7 m and 0.5 m, but the objective includes the declared risk penalty.
The 7-step detour is cheaper under this cost model, 7 versus 9, even though it is 0.2 m longer.
Sanity checkWithout the risk penalty the 5-step path would win; the reversal comes entirely from an explicit, inspectable design weight.
Try it yourself
Independent check
Move to the bench
Trace A* on a tabletop grid and expose how footprint inflation changes feasible routes.
- Graph paper or printed 10 × 10 grid
- coins or blocks as obstacles
- cardboard robot footprint
- pencil
- calculator or short script
Experiment
- Define four-neighbor moves of cost 1, start, goal, and occupied cells; state how unknown cells are treated.
- Run A* using Manhattan h and record each expanded cell’s g, h, and parent until the goal is reached.
- Trace the resulting center path with the cardboard footprint and identify any body collision.
- Inflate obstacles by the footprint radius in cells and replan.
- Introduce a deliberate fault by using h = 3 × Manhattan distance; compare expansion/order and note that optimality is no longer guaranteed, then restore admissible h.
Observe
- Expected: inflation removes center cells whose footprints would overlap an obstacle and may lengthen or eliminate the route.
- Record actual expanded-node order and path cost for both maps; a predicted shortest path is not physical clearance evidence.
- Expected fault diagnostic: an overestimating heuristic may rush toward the goal and can return a higher-cost path on a suitable map.
For a vacuum-like bench robot, define a cost for distance, an unknown-space policy, and a replanning trigger when a movable chair appears; do not treat it as an appliance-equivalent design.
- Keep this lab unpowered or use a stationary simulator; any later moving test needs low speed, a clear area, and an independent stop.
Keep evidence
Bench note
Record what you expected, what you actually measured or observed, and one difference worth investigating. This is self-reported evidence, not a certification.