Planning and navigation

• Trace a shortest-path search on a small cost grid, inflate obstacles for robot size, and define when new evidence invalidates a plan.

• data-structures
• vectors-frames

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.

Problem

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?

Steps

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.

Result

The 7-step detour is cheaper under this cost model, 7 versus 9, even though it is 0.2 m longer.

Sanity check

Without the risk penalty the 5-step path would win; the reversal comes entirely from an explicit, inspectable design weight.

Why inflate obstacles before grid planning for a circular robot?

A. To make the map look higher resolution B. To convert body-clearance constraints into a point-center planning problem C. To eliminate localization uncertainty automatically D. To guarantee the motors can follow every grid corner

Your answer: ______________________________

Reasoning:

Goal

Trace A* on a tabletop grid and expose how footprint inflation changes feasible routes.

Equipment

• Graph paper or printed 10 × 10 grid
• coins or blocks as obstacles
• cardboard robot footprint
• pencil
• calculator or short script

Procedure

1. Define four-neighbor moves of cost 1, start, goal, and occupied cells; state how unknown cells are treated.
2. Run A* using Manhattan h and record each expanded cell’s g, h, and parent until the goal is reached.
3. Trace the resulting center path with the cardboard footprint and identify any body collision.
4. Inflate obstacles by the footprint radius in cells and replan.
5. 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.

What to 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.

Transfer challenge

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.

Cautions

• Keep this lab unpowered or use a stationary simulator; any later moving test needs low speed, a clear area, and an independent stop.

Learner: ____________________ Date: ____________________

Evidence artifact or file: ____________________________________________

Notes: