Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 38 ยท Projects and Practice

Project: A Grid Delivery Robot That Replans

Build a simulated delivery robot: plan with A*, drive with a proportional heading controller, discover hidden obstacles with a short-range sensor, and replan.

In this project you combine four ideas from this course: a map, a global planner (A*), a path follower (a simple controller), and replanning when the real world differs from the map. The robot is simulated in plain Python, so everything runs in your browser.

The story: a delivery robot starts at the dock in a building, and must reach room G. The building map it was given is slightly out of date: two boxes have been placed in corridors since it was drawn. The robot has a short-range sensor and discovers them only when it gets close.

Project architecture

Known map What the robot believes.
Planner A* on the known map.
Follower Steers toward the next waypoint.
Sensor Reveals walls within 1.5 m.
1 / 2

Step 1: plan and follow

First, the planner and a path follower without surprises. The robot is a unicycle: it has a position (x, y) and a heading theta, and we command a forward speed v and a turn rate omega.

The follower looks at the next waypoint (the center of the next cell on the path) and does two things each time step (dt = 0.1 s):

  • Turn proportionally to the heading error: omega = k_turn * error.
  • Go forward slower when the error is big and when the waypoint is close: v = v_max * cos(error) (clamped at zero), so it does not drive sideways.

When it is within 0.25 m of the waypoint, it moves on to the next one.

Python Step 1: A* plus a proportional heading controller

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check that the o marks follow the corridors. If the robot cuts a corner and touches a wall cell, a real robot would clip the wall: that is why we inflate obstacles (see configuration space) and why paths are smoothed and kept in the middle of corridors.

Step 2: discover surprises and replan

Now add the hidden obstacles. The real world has two extra boxes. The robot's known map starts as the printed building plan. A sensor reveals real obstacles within 1.5 m of the robot. Each time step the robot:

  1. Senses: adds any newly seen obstacle cells to its known map.
  2. Checks: if one of those cells lies on its remaining path, the plan is invalid.
  3. Replans: runs A* from the current cell on the updated map.
  4. Drives as before.

If no path exists any more, the robot reports failure instead of driving into the box.

Python Step 2: sensing, invalidating and replanning

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

B marks the surprise boxes. Read the log: the first box blocks the narrow bottom corridor, which the original plan wanted to use. The robot notices it about a meter ahead, throws the old path away, and replans around the whole building (45 moves instead of 26). Later it senses the second box in the top corridor, but its new path runs along the wider second lane, so the box is not on the path and no replan is needed. Make that top corridor one lane wide and run it again: both routes are then blocked and the robot must stop and report that no route exists.

Step 3: ideas to extend it

Pick one or more and implement it in the code above.

  1. Inflate obstacles by one cell so the robot keeps away from walls, and see if the "hit a wall" check always stays false.
  2. Use 8-connected moves with diagonal costs, then smooth the path by shortcutting.
  3. Add sensor noise and odometry drift: perturb x, y, th slightly and add a Kalman filter or a simple correction when passing known landmarks.
  4. Add a battery and a charging dock; use a behavior tree to decide between delivering and charging.
  5. Replan less often: only replan when new cells intersect the path (already done), and measure how many A* calls you save.
  6. Two robots that must avoid each other: reserve cells in time.
  7. Safety stop: if anything unknown appears within 0.4 m, stop immediately before replanning (safety).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does the robot replan only when a newly sensed obstacle lies on its remaining path?

    An obstacle off the path does not invalidate the plan, so the cheap check avoids needless searches.
  2. 2. In the follower, what does v = v_max * cos(error) achieve?

    When the heading error is large, cos(error) is small, so the robot mostly turns in place. When aligned, it goes at full speed.
  3. 3. What should the robot do if A* returns no path after a replan?

    No path means the known map has no route; the safe response is to stop and ask for help or wait for the map to change.
  4. 4. Why is the robot's known map separate from the true world in the simulation?

    The gap between belief and reality is the core problem of robotics. Keeping them separate lets you test how the robot copes with surprises.

Summary

  • A delivery robot combines a map, a global planner, a path follower, and a sensing-replanning loop.
  • A proportional heading controller plus speed scaling follows A* waypoints.
  • Keep the robot's belief (known map) separate from the world (true map) so you can test surprises.
  • Replan only when new information invalidates the current path, and stop safely if there is no route.
  • Real systems add inflation, smoothing, localization filters, and safety layers.

Next: Project: A Two-Link Arm Planner