TwiddleLab / Artificial Intelligence / Search, Games and Plans

Project: Pathfinder Robot

Lesson 11 of 11 · 8 min · Free, no account needed

What you will learn

• Breadth-first finds the path with the fewest squares, but checks many squares on the way.
• A* uses a guess of the distance left and checks far fewer squares; trusting the guess too much can cost path length.
• When squares cost different amounts (path cost), the fewest squares is not always the fastest. A* that adds up costs finds the cheapest path.
• Map apps do the same with traffic: each road gets a cost in minutes.

Start the lesson

How the lesson goes

1. A delivery robot must cross the park before the ice cream melts. Pick its brain. First, pick its park.

   Tap a park.

2. Make the park yours: put some benches in the way.

   Tap or drag across squares. Keep a way to the star of 28 steps or fewer.

3. Brain one: breadth-first. Run it on your park.

   It finds the shortest path. Watch how many squares it checks on the way.

4. The robot's battery is small. Which brain should it get?

   Play both on your park, then tap your choice.

   Both find a shortest path, because the squares-count guess never says farther than the truth. A* spends its checks near the line toward the star, so it saves battery.

5. New problem: not every square takes the same time.

   Mud is slow: 3 minutes a square instead of 1. The total is the path cost. Breadth-first counts squares; A* can add up costs instead (g becomes minutes so far) and find the cheapest path.

6. Paint mud on your park so the fastest route walks around it.

   Blue dashes: the route with the fewest squares. Green: the route with the fewest minutes.

7. Tune the robot's trust in its guess on your park.

   f = g + w x h. Find the w that checks the fewest squares and still finds the shortest path.

   On open parks the guess is close to the truth, so trusting it a bit more than 1 can save checks without lengthening the path. Push it too far and the robot rushes into dead ends near the star.

8. The big park: breadth-first checks 188 squares to cross it. How many will A* check?

   Put your pin.

9. Classic: deliver across the big park.

   Path of 30 squares or fewer, at most 120 squares checked. Pick a brain and run.

10. A map app picks a route through town. Which one does it pick?

    Traffic jams (brown) take 3 minutes a block. Clear roads take 1.

    Route A is shorter in blocks, but its 3 jammed blocks cost 3 minutes each: 6 + 9 = 15 minutes. Route B is 13 clear blocks: 13 minutes. Navigators run a search like A* with costs: every road gets a time from live traffic.

11. Final delivery. The ice cream melts after 18 minutes. Which robot do you send?

    Play both, then tap the robot you hire.

    The squares robot goes straight through 3 mud squares: 13 squares but 19 minutes. The minutes robot walks 17 squares on dry paths: 17 minutes, before the ice cream melts at 18.

Previous lesson: Constraint Puzzles · Part of the course: Search, Games and Plans

Lessons are interactive and need JavaScript. Turn it on to play them.