Move away to find a way around.
The goal is to the right, but the route first turns down. Execute a few steps, then inspect the completed search. Which controls move the robot?
05 / Motion & navigation · Beginner
A*
pathfinding.
Would you move away from the goal?
A wall changes the route. A* (A-star) searches the known map.
Then one robot follows the waypoints.
- Lower bound, ignoring walls
- 7 m
- Shortest grid route
- 17 m
- Actually travelled
- 0 m
S: start · G: goal · grey: known wall · dashed: planned route · each cell: 1 × 1 m
An interactive browser simulation. A complete known map, exact position and planar point motion. The 3D view adds no flight dynamics or live execution.
No previous workshop needed.
Before you begin
The goal is to the right.
The first step goes down.
The robot must leave the U before going around it. After one second, it is slightly farther from the goal. Follow the whole route to see why.
Explore the four questionsMethod & assumptionsA* / Dijkstra · one robot · complete static map · exact position
Four-neighbor grid · waypoint following · no replanning
- Graph search
- A* / Dijkstra
A* ranks cells by g + Manhattan h. Dijkstra sets h = 0. Both seek the shortest route on this four-neighbor unit-cost graph.
- Decision architecture
- One onboard planner
A single robot knows the full static map, start and goal. No coordinator, peer messages or network is involved.
- Execution rule
- Waypoint following
Move toward one waypoint at 1 m/s, clamp at arrival, then take the next. The direct baseline supplies only the goal.
- Timing and fidelity
- Planar point kinematics
Planning has zero modeled time; execution uses 0.1 s steps. No body radius, heading dynamics, GPS loss or uncertain estimates.
Optimality boundary: the shortest grid route is not necessarily the shortest continuous-space route or a feasible trajectory for a real vehicle. The 3D drone uses a fixed 0.8 m display height; walls keep exact blocked-cell footprints. Aircraft size and heading do not change point-contact evaluation.
01 / Try it
A route is a plan. Arrival takes motion.
■ WallO Frontier× Settled┄ Planned route━━ Actual trail
S: start · G: goal · A: robot. Select a cell to inspect search costs. Robot marker size is illustrative; this is point motion.
Planned length
Actually travelled0.0 mIncludes travel up to first contact
Distance to goal7.0 mEuclidean evaluator measurement
Motion time0.0 sStep 0 / 400 · search time not modeled
Inspect the completed search
Inspect how the route was found.
This is the search completed before motion. Its controls show the history computed in this browser; the robot and final route stay unchanged. This is not a recording from an external system.
g: discovered cost from start · h: remaining lower bound · f = g + h. Costs are metres. Unknown is not zero.
Watch the movement
Follow one waypoint at a time.
- State
- Next waypoint
- Exact x position
- Exact y position
Goal distance can rise while a valid route goes around a wall. Search does not give the follower an avoidance controller.
Inspect the waypoint sequence
Each graph edge joins free cell centers. Turns are instantaneous; a vehicle with size or turning constraints needs a different model.
02 / Follow a question
Find a way.
Then test the plan.
Change the search, remove the planner or close the only opening.
Same route. Different search.
A* and Dijkstra both plan 17 m on this map. A* pops 30 cells; Dijkstra pops 95. What changes when the search has an estimate of the remaining distance?
A goal alone is not a safe route.
Direct motion reaches the goal on open ground. Add the U wall and the same follower makes contact after 1.5 s. The evaluator stops it at the wall.
No connection. No route.
Seal the opening. Both searches exhaust six reachable cells, then report no path. No waypoint is issued; the robot stays at its start.
Each case starts paused. Diagrams use the model’s map and routes. Search pops count selected cells, including the goal; they do not measure computing time.
Compare all nine reference runs Route · search · motion
Identical starts, goals, maps and follower. A* and Dijkstra optimize graph distance; the direct baseline skips obstacle planning.
| Map | Method | Outcome | Planned | Travelled | Motion time | Search pops |
|---|
03 / Go deeper
What have we spent?
What might remain?
A* adds the distance found so far to a lower bound on what remains. On this grid, Manhattan distance counts horizontal and vertical steps while ignoring walls.
At the start · A* on the U map
- g · so far
- 0
- h · to go
- 7
- f · total
- 7
All three costs are in metres. The initial score is 0 + 7 = 7. Walls make the shortest route on this grid 17 m.
Dijkstra uses h = 0, so only the discovered cost g determines its score.
Read the search, assumptions & sources
f(n) = g(n) + h(n)
h(n) = |xₙ − x_goal| + |yₙ − y_goal|
Dijkstra: h(n) = 0
g: cost found so far
Every free horizontal or vertical edge costs 1 m. Relax a neighbor only when the candidate cost is strictly lower; store the predecessor.
h: a consistent lower bound
For adjacent cells, h(n) ≤ 1 + h(neighbor). Settled nodes need no reopening under this condition. Different heuristics need different checks.
f: next cell to inspect
Select smallest f, then smallest h, then cell ID. Stop when the goal is popped. An empty frontier means no route exists in this graph.
Motion has a different rule
Move at most v·dt toward the next waypoint and clamp at arrival. The evaluator checks the whole segment for contact. Finding a path is not reaching the goal.
Primary sources: Hart, Nilsson & Raphael (1968), A Formal Basis for the Heuristic Determination of Minimum Cost Paths ↗; Dijkstra (1959), A Note on Two Problems in Connexion with Graphs ↗, Problem 2. The kinematic follower and collision evaluator are separately declared teaching models.
Shortest means shortest on this four-neighbor grid. A vehicle with size, turning limits or uncertain position needs additional models. The final route remains visible while you inspect earlier search snapshots; it is the completed search’s result.
Keep the thread
What if the robot
is wrong about its position?
Follow a known route with noisy measurements. Compare dead reckoning and Kalman filtering, and see how a reported arrival can differ from reality.