Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 46 ยท Projects

Project: Robot Maze Navigator

Build a simulated robot that senses walls with noisy sensors, localizes itself with a histogram filter, plans with A*, replans as beliefs change, and plots its trace.

This project ties the course together. You will build a robot that is dropped into a maze it can see only through four noisy wall sensors. It does not know where it is, and its wheels sometimes slip. To reach the goal it must do three things at once: work out where it is (probabilistic filtering, from the hidden Markov models lesson), plan a route (A* search), and act, look, and replan (the sense-plan-act loop from robotics basics).

Everything is plain Python and runs live in your browser. The seeds are fixed, so you can compare your numbers with the ones in this lesson, and then change the seeds, the noise levels or the maze and watch the behavior change.

The system

The robot lives on a grid. Each cell is either a wall or free. At every step it follows this loop:

graph LR
    S["Sense<br/>4 noisy wall bits"] --> U["Update belief<br/>(Bayes rule)"]
    U --> G["Pick best guess<br/>of own cell"]
    G --> P["Plan with A*<br/>guess to goal"]
    P --> A["Act<br/>first move of the plan"]
    A --> D["Predict belief<br/>(motion model)"]
    D --> S

One pass of the loop per time step. The plan is thrown away and rebuilt every step, so a better belief immediately gives a better route.

The pieces are:

Piece Model Where it comes from
World A grid of walls and free cells This lesson
Sensor Four bits: is there a wall north, east, south, west? Each bit is wrong with probability 0.10 Sensor noise from robotics basics
Motion A move succeeds with probability 0.85, otherwise the robot stays put Transition model of an HMM
Localization A histogram filter: one probability per free cell Forward algorithm
Planner A* with Manhattan distance on the grid Informed search

Notice the design decision: we keep a full belief (a probability for every cell) but plan with only its most likely cell. This is a common, cheap approximation. It works well when the belief is concentrated, and it can mislead the robot when two places look alike. You will see both cases.

Step 1: world and localization

The maze below has 40 free cells. The function true_reading computes what a perfect sensor would report for a cell; Robot.sense flips each bit with probability SENSOR_ERROR. The two filter functions are the whole localization algorithm:

  • predict(belief, d) pushes probability mass along the commanded move: 85 percent of each cell's mass moves one cell (if that cell is free), the rest stays. If the move would hit a wall, all the mass stays.
  • update(belief, reading) multiplies each cell's probability by the likelihood of the reading if the robot were in that cell, then divides by the total so the numbers sum to 1.

The likelihood is a product over the four sensors: 0.9 for each bit that matches what that cell would show, 0.1 for each bit that does not. This treats the sensors as independent given the position, which is the usual simplifying assumption.

The demo starts with a uniform belief ("I could be anywhere"), drives the robot along a fixed route, and prints how sure the filter is. The grid shows the belief as digits: 3 means roughly 30 to 39 percent, and . means under 5 percent.

Python Noisy sensors and a histogram filter

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.

Read the output closely. At step 0 the robot has seen a single reading and the filter already has a favorite, but its confidence is only 0.25: the cell at row 7, column 7 gives the same wall pattern, so the grid shows a second blob there. After a few moves the belief collapses onto one place. Look at steps 2 to 5, too. The slipping wheels leave the robot behind its commanded route, but the filter keeps assuming that moves usually succeed, so its guess is one or two columns off. When the robot reaches the corner at row 5, column 5, the wall pattern disagrees with the old guess and the estimate snaps back (step 6).

Note: A filter is only as good as its model. Here the model matches the simulator exactly. If you changed MOVE_SUCCESS inside the filter but not in the robot, the estimate would drift much more often. Mismatched models are the most common real-world cause of lost robots.

Step 2: planning and replanning

The planner is A* from the A* lesson, specialized to the grid: each move costs 1 and the heuristic is Manhattan distance, which is admissible because the robot cannot move diagonally or pass through walls. The function returns the list of moves and the number of nodes it expanded. It also accepts a set of blocked cells, which is how we model something the map did not predict.

The next demo plans the first route, drops an imaginary box on the way, walks until it bumps into it, and replans from where the robot stands.

Python A* plans, a box appears, A* replans

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.

The original plan has 18 moves and A* expanded 35 nodes. After the robot has walked 7 steps, the box blocks the corridor. Replanning from the new position costs another 32 expansions, and the new route is long (29 moves) because this corridor was the only short way: the robot has to walk back and take the detour around the maze. The total trip becomes 36 moves instead of 18. This is why replanning matters more than planning perfectly the first time. The last line shows the other outcome: if every way into the goal is sealed, A* returns None, and your robot must handle "no route exists" instead of crashing.

Step 3: the full navigator

Now we connect everything. The function navigate runs one complete mission:

  1. Start with a uniform belief and fold in the first sensor reading.
  2. Take the most likely cell as the current position estimate.
  3. Plan from that estimate to the goal with A* and execute only the first move.
  4. Predict the belief through the move and update it with the new reading.
  5. Repeat until the robot is really at the goal (the simulator knows; a real robot would stop when its belief is concentrated on the goal).

Replanning from scratch every step looks wasteful, but on a 40-cell maze A* takes microseconds. The code counts a replan only when the new plan is not simply the previous plan with its first move removed, that is, when new information actually changed the route.

The program runs eight seeds, prints a table, and then plots seed 4 with matplotlib: the true path in blue and the robot's own best guess of its position in red.

Python Full navigator with noisy sensors

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.

The shortest possible trip is 18 moves. With noisy motion the robot needs between 21 and 31 steps, which is what you would expect from a move that fails 15 percent of the time (18 / 0.85 is about 21). The interesting column is the last one, the number of steps where the best guess was wrong. Seeds 1, 5, 6 and 8 have at most 2 wrong guesses and finish close to the minimum. Seed 4 has 12 wrong guesses and takes 31 steps. In the plot, the red dashed line wanders away from the blue one during those stretches: the robot believed it was somewhere else, so A* planned from the wrong cell and sent it in a wrong direction. The belief eventually recovers because the walls the robot keeps sensing disagree with its guess.

Tip: Print the confidence next to the guess. A wiser robot would stop and look (stay put and sense again) whenever its best cell has, say, less than 50 percent probability, since a few extra readings are cheaper than a wrong turn.

Extensions

Pick one and try it. Each uses only things you have already built.

  • Look before leaping. When best(belief) has probability below 0.5, skip the move and only sense. Measure whether the average number of steps goes down across seeds 1 to 30.
  • Plan on the belief. Instead of planning from the single best cell, compute the expected cost of each first move by averaging A* path lengths over the belief. This handles ambiguous places better.
  • Noisier world. Raise SENSOR_ERROR to 0.25 and watch the error column. Then lower MOVE_SUCCESS to 0.6 (in both the robot and the filter).
  • Another map. Build a bigger maze, or one with loops, and see how the number of A* expansions grows.
  • Kidnapped robot. Teleport the robot to a random cell halfway through a run. A histogram filter recovers only if no cell ever drops to exactly zero, so mix a tiny uniform probability back into the belief after each update.
  • Particle filter. Replace the histogram with 500 particles that move and are re-sampled, as in the filtering lesson, so the map can be a continuous space.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does the navigator keep a belief over all cells instead of one position?

    With noisy sensors and slipping wheels the robot cannot be sure where it is. The belief stores a probability for every possible cell and is refined with Bayes rule after each reading.
  2. 2. What does the predict step of the histogram filter do?

    Prediction shifts mass along the commanded move, keeping 15 percent in place for a failed move. Uncertainty grows here and shrinks again in the update step.
  3. 3. The navigator replans with A* at every step. Why?

    Moves can fail and the position estimate changes as new readings arrive. Rebuilding the plan from the current best guess keeps the route consistent with what the robot now believes.
  4. 4. In seed 4 the robot takes 31 steps instead of about 21. What mostly explains this?

    The planner is optimal for the cell it is given. When the estimate is wrong, it plans a good route from the wrong place, and the robot wastes moves until the belief recovers.

Summary

  • A navigation robot combines three AI components: a probabilistic filter for state estimation, a search algorithm for planning, and a sense-plan-act loop to connect them.
  • The histogram filter alternates predict (motion model, uncertainty grows) and update (sensor likelihood, uncertainty shrinks).
  • Planning from the most likely cell is a cheap approximation that fails when the belief is wrong or ambiguous.
  • Replanning every step with A* is simple, and cheap enough on small maps.
  • Model mismatch and ambiguous places are the main reasons localization fails.
  • Fixed seeds make stochastic experiments reproducible and comparable.

Next: Practice: Classical AI Exercises.