Robotics & control

Robot Path Planning Challenge

Plans a robot's route across a 10 x 10 floor from a start cell to a goal cell past up to five rectangular obstacles, in 4 or 8 directions with 10/14 move costs and no squeezing past corners, by Dijkstra, A* or weighted A*, one expansion per step. Returns the route with its cost, steps, turns and true length in cells and metres, the open-floor cost and the detour, the search effort (cells expanded, the largest open list, wasted expansions), a frame for every step and the state of every cell, and checks a route of straight segments the learner draws against every obstacle. Refuses invalid inputs plainly, warns of a blocked start or goal and of no route, and scores five challenges. For learning graph search.

Last updated

Calculator overview

Inputs and outputs

This summary comes from the calculator's published input and output contract.

Inputs

Obstacles (row k is obstacle k: a block of whole cells from its first to its last row and column; leave a row blank when not used)
When omitted Blank
About this input

Up to five rectangular obstacles: row k is obstacle k with its first row, first column, last row and last column, each a whole number from 1 to 10, the first no later than the last. Obstacle k blocks every cell from its first to its last row and column; obstacles may overlap. A row in use must be complete; leave a row blank when it is not used. The whole table is optional.

Default 1 row
ColumnRange or allowed values
First row 1 to 10
First column 1 to 10
Last row 1 to 10
Last column 1 to 10
Your route's waypoints (row j is waypoint j; the route runs from the start through the waypoints in use to the goal)
When omitted Blank
About this input

Your route's waypoints, one per row in order (waypoint 1 first), each with its row and column, whole numbers from 1 to 10. Your route runs from the start through the waypoints in use, in order, to the goal in straight segments. A waypoint in use needs both numbers; a blank row is skipped. The whole table is optional.

Default 0 rows
ColumnRange or allowed values
Row 1 to 10
Column 1 to 10
Heuristic weight (required)
About this input

The weight w of weighted A*, from 1 to 5 in steps of 0.25. It is checked with every method but applied only with Weighted A*.

Default 2 Range 1 to 5
Start row (required)
About this input

The start cell's row on the 10 x 10 floor, a whole number from 1 (top) to 10.

Default 8 Range 1 to 10
Start column (required)
About this input

The start cell's column, a whole number from 1 (left) to 10.

Default 2 Range 1 to 10
Search method (required)
About this input

Dijkstra (priority = cost so far), A* (cost so far + the estimate to the goal) or Weighted A* (cost so far + the weight x the estimate).

Default Dijkstra Allowed Dijkstra, A*, Weighted A*
Moves (required)
About this input

4 directions (east, north, west, south, cost 10 each) or 8 directions (adding the diagonals, cost 14 each; a diagonal needs both cells beside it free).

Default 4 directions Allowed 4 directions, 8 directions
Challenge number (required)
About this input

Selects a challenge: 0 for none, 1 to 5 for a predefined challenge whose settings replace the inputs it fixes.

Default 0 Range 0 to 5
Cell size (required)
About this input

The side of one floor cell in m; it only scales the route length in metres.

Unit m Default 0.5 Range 0.1 to 10
Goal row (required)
About this input

The goal cell's row, a whole number from 1 to 10.

Default 3 Range 1 to 10
Goal column (required)
About this input

The goal cell's column, a whole number from 1 to 10.

Default 9 Range 1 to 10
Your prediction (challenge 1) (required)
About this input

Your prediction for challenge 1: Not yet predicted, or the band of cells A* expands (1 to 20 nodes up to 81 to 100 nodes). The search results of challenge 1 stay hidden until you predict. Not used outside challenge 1 and never overridden.

Default Not yet predicted Allowed Not yet predicted, 1 to 20 nodes, 21 to 40 nodes, 41 to 60 nodes, 61 to 80 nodes, 81 to 100 nodes

Outputs

Largest open list
About this output

The largest number of open cells at any step. Blank when the search cannot run or challenge 1 awaits a prediction.

Unit cells
Open-floor route cost
About this output

The cost of the best route on an open floor (the Manhattan or octile distance in cost units).

Unit cost units
The route the search found, from the start (step 0) to the goal: each cell, its cost so far and the move into it
About this output

The route the search found: one row per route cell from the start (step 0) to the goal, with its row, column, cost so far and the move into it (Start, then E, N, W, S, NE, NW, SW or SE); blank when there is no route or while challenge 1 awaits a prediction.

No unit declared
Route length in metres
About this output

The route's true length in m (true length x cell size). Blank when there is no route, the search cannot run, or challenge 1 awaits a prediction.

Unit m
Route cost
About this output

The cost of the route the search found, in cost units (10 per straight step, 14 per diagonal). Blank when there is no route, the search cannot run, or challenge 1 awaits a prediction.

Unit cost units
Model Status
About this output

NOT VALID with the reason when an input cannot be used; CHECK when the results are shown but the start or the goal is inside an obstacle, the start is the goal, or there is no route; otherwise OK.

No unit declared
True length less cost over 10
About this output

The true length less the cost read as a length (cost/10), in cells: the price of approximating the square root of 2 by 1.4. Blank when there is no route, the search cannot run, or challenge 1 awaits a prediction.

Unit cells
Model version
About this output

The model version.

No unit declared
The floor cells (row-major): blocked, cost so far, estimate to the goal, and the steps at which each was expanded, reached and placed on the route
About this output

The floor cells, row by row (100 rows): row, column, 1 when blocked, the cost so far (blank when never reached), the estimate to the goal (blank on a blocked cell), the step at which the cell was expanded, the step at which it was first reached and its step on the route (each blank when it does not apply). The cost and step columns are blank while challenge 1 awaits a prediction.

No unit declared
Formula module versions
About this output

The formula modules the model is built from, with their versions.

No unit declared
Route steps
About this output

The number of moves on the route. Blank when there is no route, the search cannot run, or challenge 1 awaits a prediction.

Unit moves
Start row used
About this output

The start row used (the challenge's when a challenge fixes it).

No unit declared
Start column used
About this output

The start column used (the challenge's when a challenge fixes it).

No unit declared
Straight steps
About this output

The straight moves on the route. Blank when there is no route, the search cannot run, or challenge 1 awaits a prediction.

Unit moves
Wasted expansions
About this output

The expanded cells that are not on the route. Blank when there is no route, the search cannot run, or challenge 1 awaits a prediction.

Unit cells
The obstacles used (a challenge's fixed map shows here)
About this output

The obstacles used: one row per obstacle in use with its number and its first and last rows and columns (a challenge's fixed map shows here); rows not in use blank.

No unit declared
Turns on the route
About this output

The changes of direction along the route. Blank when there is no route, the search cannot run, or challenge 1 awaits a prediction.

No unit declared
True route length
About this output

The route's true length in cells: straight steps + diagonal steps x the square root of 2. Blank when there is no route, the search cannot run, or challenge 1 awaits a prediction.

Unit cells
Search method used
About this output

The search method used (the challenge's when a challenge fixes it).

No unit declared
The search film: one frame per expansion, the cell expanded, its cost so far and priority, and the open and closed counts after it
About this output

The search film: 101 rows, frame k = 0 to 100, each with the step, the row and column of the cell expanded, its cost so far and priority (all blank at frame 0), and the open and closed counts after the step. Frames after the last expansion are blank; frames 1 to 100 are blank while challenge 1 awaits a prediction; the whole grid is blank when the search cannot run.

No unit declared
Expanded cells on the route
About this output

The share of expanded cells that lie on the route, in %. Blank when there is no route, the search cannot run, or challenge 1 awaits a prediction.

Unit %
Your route less the grid route
About this output

Your route's length less the grid route's true length, in cells (negative when yours is shorter). Blank when there is no route, the search cannot run, or challenge 1 awaits a prediction.

Unit cells
Challenge score
About this output

The challenge score: 100 when met, else 0.

No unit declared
Challenge: the value scored
About this output

The value the selected challenge scores: the cells expanded (1 and 3), the route cost over the open-floor cost (2), your route less the grid route in cells (4) or the wasted expansions (5); blank when not valid, awaiting a prediction or not available.

No unit declared
Challenge result
About this output

No challenge selected, MET or NOT MET.

No unit declared
Detour over the open floor
About this output

How much more the route costs than the open-floor route, in %. Blank when there is no route, the search cannot run, or challenge 1 awaits a prediction. Blank also when the open-floor cost is 0.

Unit %
Moves used
About this output

The moves used (the challenge's when a challenge fixes it).

No unit declared
Blocked cells
About this output

The number of floor cells covered by the obstacles.

Unit cells
Weight applied to the estimate
About this output

The weight applied to the estimate: 0 for Dijkstra, 1 for A*, the heuristic weight for Weighted A*.

No unit declared
Cell size used
About this output

The cell size used, m (never fixed by a challenge).

Unit m
Challenge goal
About this output

The goal of the selected challenge (blank with none).

No unit declared
Challenge feedback
About this output

Feedback on the selected challenge: the prediction prompt, the met text or the not-met hint (blank with none).

No unit declared
Diagonal steps
About this output

The diagonal moves on the route. Blank when there is no route, the search cannot run, or challenge 1 awaits a prediction.

Unit moves
Your route: the start, the waypoints in use and the goal, the length of the segment ending at each point and the obstacle it hits (0 when clear)
About this output

Your route: point 0 the start, points 1 to 6 the waypoints in use (rows not in use blank) and point 7 the goal, each with its row and column, the length of the segment that ends there in cells and the obstacle it hits (0 when clear; blank at point 0).

No unit declared
First segment that hits
About this output

The first segment of your route, in route order, that hits an obstacle; blank when clear.

No unit declared
Your route's length
About this output

The true length of your route in cells.

Unit cells
Your route's segments
About this output

The number of straight segments of your route (1 + the waypoints in use).

No unit declared
Your route's check
About this output

Clear, or which obstacle the first hitting segment meets and on which segment (touching an edge or a corner counts).

No unit declared
Goal column used
About this output

The goal column used (the challenge's when a challenge fixes it).

No unit declared
Cells expanded
About this output

The number of cells the search expanded. Blank when the search cannot run or challenge 1 awaits a prediction.

Unit cells
Goal row used
About this output

The goal row used (the challenge's when a challenge fixes it).

No unit declared
Obstacle it hits
About this output

The lowest-numbered obstacle that segment hits; blank when clear.

No unit declared
Heuristic weight used
About this output

The heuristic weight used (the challenge's when a challenge fixes it).

No unit declared
This page is provided by LogicCommons for informational purposes only. Results are analysis outputs computed from the inputs you supply and are not professional advice. Verify all inputs and results independently.

LogicCommons is in beta. If a result, label, or reference looks wrong, tell us here; we read every message.

Methodology

Purpose and model boundary

This lab plans a robot's route across a 10 by 10 floor of square cells, from a start cell to a goal cell, past up to five rectangular obstacles. The robot moves from cell centre to cell centre in 4 directions (east, north, west, south) or in 8 (adding the four diagonals). One search runs per calculation, chosen by you: Dijkstra's algorithm, A* or weighted A*. The search expands one cell per step, at most 100 steps, and the lab returns the route it found with its cost, steps, turns and true length, the open-floor cost and the detour, the search effort (cells expanded, the largest open list, wasted expansions), a frame for every step and the state of every floor cell. It also checks a route of straight segments that you draw through up to six waypoints against every obstacle. Five scored challenges use the same model.

It is a lab for learning how graph search works: why Dijkstra's algorithm floods outward, how the estimate of the remaining distance pulls A* toward the goal, what a weight on that estimate buys and costs, and why a route on a grid is longer than a straight line. It is not a motion planner. The robot is a point with no size, no turning cost, no dynamics and no sensing; the floor is fixed and fully known; and the diagonal cost of 14 only approximates the true diagonal length. Do not use it to plan the motion of a real robot or vehicle.

The model is the calculation authority. The page sends the values you set to the model and draws only what it returns: the floor, the obstacles, the open and expanded cells of every frame, the planned route, your own route and its collisions, and the chart of open and closed counts. The page computes no route, cost, estimate or expansion itself.

Inputs and units

Positions are floor cells: row 1 is the top row and column 1 the left column. Costs are in cost units (10 for a straight move, 14 for a diagonal one). Lengths are in cells and, scaled by the cell size, in metres.

Input Meaning and unit
Start row, start column The start cell, each a whole number from 1 to 10 (defaults: row 8, column 2).
Goal row, goal column The goal cell, each a whole number from 1 to 10 (defaults: row 3, column 9).
Obstacles Up to five rectangles, one per row: first row, first column, last row and last column, each a whole number from 1 to 10, the first no later than the last. Obstacle k blocks every floor cell from its first to its last row and column; obstacles may overlap. A row in use must be complete; a blank row is not used. The whole table is optional (default: one obstacle covering rows 2 to 8 of columns 5 and 6).
Moves 4 directions (east, north, west, south, cost 10 each) or 8 directions (adding the diagonals, cost 14 each). Default 4 directions.
Search method Dijkstra, A* or Weighted A*. Default Dijkstra.
Heuristic weight The weight w of weighted A*, from 1 to 5 in steps of 0.25 (default 2). It is checked with every method but applied only with Weighted A*.
Cell size The side of one floor cell, from 0.1 to 10 m (default 0.5 m). It only scales the route length in metres.
Your route's waypoints Up to six waypoints, one per row in order, each a row and a column from 1 to 10. Your route runs from the start through the waypoints in use to the goal in straight segments. A waypoint in use needs both numbers; a blank row is skipped. The whole table is optional and blank by default.
Challenge number 0 for free exploration, or 1 to 5 to load a challenge.
Your prediction (challenge 1) Not yet predicted, or the band of cells A* expands: 1 to 20, 21 to 40, 41 to 60, 61 to 80 or 81 to 100. Used only in challenge 1.

Where each input is set:

  • On the canvas only: the start and the goal (the S and G markers, dragged to a cell), the obstacles (drawn with two taps on opposite corner cells, resized by dragging a corner, moved by the handle on the top edge and removed with their × or Delete), the moves (4 or 8 directions), your route's waypoints (added on the floor in Advanced, and whenever challenge 4 is selected) and your prediction for challenge 1.
  • In the input panel: the search method, the heuristic weight, the cell size and the challenge number.
  • Every marker snaps to whole cells. Pressing Enter on a selected marker opens its exact row and column.

Governing relationships

The floor as a graph. Floor cell n = 10·(r - 1) + c, for row r and column c, is a node. A cell is blocked when any obstacle in use covers it. From a free cell the robot may move to a free neighbour: east, north, west or south at cost 10, and with 8 directions also north-east, north-west, south-west or south-east at cost 14. A diagonal move is allowed only when both cells beside it are free, so the robot never squeezes past an obstacle's corner.

The estimate to the goal. With dr and dc the row and column distances from cell n to the goal,

  • with 4 directions, h(n) = 10·(dr + dc), the Manhattan distance;
  • with 8 directions, h(n) = 10·max(dr, dc) + 4·min(dr, dc), the octile distance 10·(max - min) + 14·min.

Both are whole numbers in cost units and both are consistent for their moves: h(n) is never more than the cost of a move to a neighbour m plus h(m). So A* finds a cheapest route without ever reopening a cell.

The priority. Each open cell carries its cost so far g, the cost of the cheapest route to it found yet, and a priority f = g + w·h, where the applied weight w is 0 for Dijkstra, 1 for A* and the heuristic weight for weighted A*. Each step expands the open cell with the lowest f. Ties go to the lower estimate h, then to the lower cell number (row by row from the top left). Because every cost is a whole number and every weight a whole number of quarters, every comparison is exact.

One expansion per step. The expanded cell is closed and never reopened. If it is not the goal, each free neighbour that is not closed takes the cheaper of its old cost and the cost through the expanded cell, and becomes open. The search stops when it expands the goal, or with no route when nothing is left open.

Optimality and the weight. Dijkstra (w = 0) and A* (w = 1, with a consistent estimate) both return a route of the least cost under the 10 and 14 move costs. With w above 1 the search is greedier: it usually expands fewer cells, and its route costs at most w times the least cost.

The route. The route is read back from the goal: each cell's predecessor is the first closed neighbour, in the fixed order E, N, W, S, NE, NW, SW, SE, whose cost plus the move cost equals the cell's own cost. So when two routes cost the same, the order decides which one is shown.

Lengths and the metric.

  • Route cost = 10·(straight steps) + 14·(diagonal steps).
  • True length = straight steps + diagonal steps·√2, in cells; in metres, the true length times the cell size.
  • Metric gap = diagonal steps·(√2 - 1.4), in cells: the true length less the cost read as a length (cost / 10).
  • Open-floor cost: the estimate h of the start, which is the cost of the best route with no obstacles.
  • Detour = 100·(route cost - open-floor cost) / open-floor cost, in %.

The costs 10 and 14 approximate 1 and √2 = 1.41421... by 1.4, so five diagonals cost the same as seven straight moves although their true lengths are about 7.07 and 7 cells. The search finds the route that is cheapest under the stated costs and reports its true length beside its cost.

Your route. Each segment of your route runs from the centre of one cell to the centre of the next point. The lab tests every segment against every obstacle exactly, using the separating-axis test for a segment and a box: the segment meets the rectangle when their bounding boxes overlap and the rectangle's four corners do not all lie strictly on one side of the segment's line. Touching an edge or a corner counts as a hit. Each segment's length is √((column change)² + (row change)²) in cells, and your route's length is their sum.

Calculation sequence

  1. Check the inputs in the order of the list under Errors and warnings, on the values you entered.
  2. Take the values used: in a challenge, its own start, goal, obstacles, moves, method and weight, except the inputs that challenge leaves to you. The cell size and the prediction are never replaced.
  3. Mark the blocked cells, compute the estimate of every cell and the neighbours of every cell under the corner rule.
  4. If the start and the goal are both free, run the search: the start opens at step 0, and each step 1 to 100 expands one cell and updates its neighbours, until the goal is expanded or nothing is open.
  5. Read each cell's final cost, the step at which it was first reached and the step at which it was expanded, then walk the route back from the goal to the start.
  6. Count the route's straight and diagonal steps and turns, and compute its cost, true length, length in metres, metric gap, detour, wasted expansions and the share of expanded cells on the route.
  7. Check your route's segments against every obstacle and compare its length with the grid route.
  8. Set the status and, in a challenge, score it.

Outputs and interpretation

The route (blank when there is no route, the search cannot run, or challenge 1 awaits a prediction):

  • Route cost: in cost units, 10 per straight move and 14 per diagonal one.
  • True route length: in cells; route length in metres: the true length times the cell size.
  • Route steps, straight steps, diagonal steps and turns on the route (the changes of direction).
  • True length less cost over 10: the metric gap in cells, never negative; it grows by about 0.0142 cells per diagonal.
  • Detour over the open floor: how much more the route costs than the open-floor route, in % (blank also when the open-floor cost is 0).

The search effort:

  • Cells expanded: the cells the search closed, shown whenever the search runs, also when there is no route.
  • Largest open list: the largest number of open cells at any step.
  • Wasted expansions: expanded cells not on the route; expanded cells on the route: the share of expanded cells that lie on the route, in %.

The map: the open-floor route cost (the cost with no obstacles, in cost units), the number of blocked cells, and the weight applied to the estimate (0, 1 or the heuristic weight).

Your route: its number of segments (1 plus the waypoints in use), its length in cells, its check (Clear, or "Hits obstacle k on segment j" for the first segment that hits), the first segment that hits and the lowest-numbered obstacle it hits, and your route less the grid route in cells (negative when yours is shorter).

Tables: the search film (one frame per step: the cell expanded, its cost so far and priority, and the open and closed counts after it; frame 0 is the start, with only its counts), the floor cells (blocked, cost so far, estimate to the goal, and the steps at which each was expanded, reached and placed on the route), the planned route (each cell from the start, its cost so far and the move into it: Start, then E, N, W, S, NE, NW, SW or SE), your route's points with each segment's length and the obstacle it hits, and the obstacles used.

Settings used: the start, goal, moves, method, weight and cell size in effect (a challenge's own while it is selected).

Reading the canvas: in frame k a floor cell is drawn as expanded (closed) when its expansion step is at most k, as open when its reach step is at most k and it is not closed, and as unreached otherwise. The cell expanded at that step is marked, and the route appears at the last step. The chart below plots the open and closed counts of every step. Play the film, or click the chart to go to a step. Compare Dijkstra and A* on the same map: they return routes of the same cost, but A* usually expands far fewer cells, because the estimate tells it where the goal is.

Challenges

Selecting a challenge loads its own map and settings; the page names the inputs that challenge lets you change, and the rest are fixed. The model scores each challenge MET (100 points) or NOT MET (0), shows the value it scored, and gives a one-line hint while the challenge is not met.

  1. Predict the expansions. Dijkstra expands 85 cells to plan this route. Predict how many A* expands. It is met when your band (1 to 20, 21 to 40, 41 to 60, 61 to 80 or 81 to 100 cells) holds the number of cells A* expands.
  2. Force a detour. Place at most two obstacles so the best route costs at least 1.5 times the open-floor cost, while a route still exists. The value scored is the route cost over the open-floor cost.
  3. Tune the weight. Choose a weight so weighted A* expands at most 30 cells while its route costs at most 10% more than the best route (132). The value scored is the number of cells expanded.
  4. Beat the grid. Draw a route of at most four straight segments that misses the obstacle and is truly shorter than the grid route. It is met when a route exists, no segment hits the obstacle, your route has at most four segments and is shorter than the grid route by more than 1×10⁻⁹ cells. The value scored is your route less the grid route.
  5. No wasted steps. Move the start so that A* expands only cells on its route (no wasted expansions), at least 8 steps from the goal. The value scored is the number of wasted expansions.

Challenge 1 holds back the answer until you predict. While your prediction reads Not yet predicted, the film after frame 0, the planned route, the costs, reach and expansion steps of the floor cells and every route and search number are blank, and the challenge reads NOT MET with a prompt to predict first. The map, the estimates and the open-floor cost stay shown. Once you predict, every result appears and the challenge is scored. Your prediction changes nothing outside challenge 1.

What to take from the lab: a search that knows roughly where the goal is does far less work for the same answer; a weight above 1 trades a little route quality for speed; and a route on a grid is longer than the straight line between the same points.

Validation and status logic

The status reads the first match in the list under Errors and warnings. The NOT VALID checks run first, on the values you entered, also while a challenge is selected. The CHECK items run next, on the values used, so they also apply inside challenges. A challenge number that is not a whole number from 0 to 5 counts as no challenge selected. Otherwise the status is OK.

Assumptions and limitations

  • A 10 by 10 floor of square cells; up to five rectangular obstacles made of whole cells; up to six waypoints.
  • The robot is a point moving between cell centres, 4 or 8 ways; a diagonal needs both cells beside it free. No robot size, turning cost, dynamics, sensing or map uncertainty, and no moving obstacles.
  • The costs 10 and 14 approximate 1 and √2. "Cheapest" means cheapest under those costs; a route at any angle, such as your drawn route, can be shorter than every grid route.
  • Ties between equal priorities go to the lower estimate, then the lower cell number; between equally cheap routes, to the fixed direction order. Another search with another tie rule can expand a different number of cells and show a different route of the same cost.
  • At most 100 expansions, which always suffices on this floor.
  • Your route counts as shorter than the grid route only by more than 1×10⁻⁹ cells, so two routes of exactly equal length never count as shorter.

Restrictions and non-computing states

Under NOT VALID every result, table and chart is blank; the challenge reads NOT MET with a score of 0 when a challenge is selected, and its goal and hint stay shown.

When the start or the goal is inside an obstacle, the search does not run: every route and search result is blank, while the open-floor cost, the blocked cells, the map, the estimates, the obstacles used and your route's check stay shown. When the start is the goal, everything is shown with a route cost of 0 and no steps. When there is no route, the cells expanded, the largest open list and the film are shown, and every route result is blank.

In challenge 1, until you predict, the search results are held back as described under Challenges.

Errors and warnings

The status messages, first match wins:

  • NOT VALID: the start and the goal each need a whole-number row and column from 1 to 10
  • NOT VALID: choose 4 directions or 8 directions for the moves
  • NOT VALID: choose Dijkstra, A* or Weighted A* as the search method: the method must match one of the three exactly, including its capital letters.
  • NOT VALID: the heuristic weight must be from 1 to 5 in steps of 0.25: checked whatever the method.
  • NOT VALID: the cell size must be from 0.1 to 10 m
  • NOT VALID: obstacle k needs whole-number rows and columns from 1 to 10, with the first row and column no later than the last, or leave the row blank: k is the lowest obstacle row at fault.
  • NOT VALID: waypoint k needs a whole-number row and column from 1 to 10, or leave the row blank: k is the lowest waypoint row at fault.
  • NOT VALID: the challenge number must be a whole number from 0 to 5, and the prediction one of the listed choices
  • CHECK: the start cell is inside an obstacle, so the robot cannot set off; move the start or the obstacle
  • CHECK: the goal cell is inside an obstacle, so it can never be reached; move the goal or the obstacle
  • CHECK: the start and the goal are the same cell, so the route is empty
  • CHECK: there is no route: the obstacles cut the goal off from the start, and the search expanded every cell it could reach: an unreachable goal is a result in itself; the search effort is shown.
  • OK: the inputs are valid and the search found a route.

References

This laboratory is an educational model of shortest-path search on a grid. The floor is a graph of square cells joined by straight moves of cost 10 and, optionally, diagonal moves of cost 14. Dijkstra's algorithm expands the open cell with the lowest cost so far; A* adds an estimate of the remaining cost, the Manhattan distance for 4 directions or the octile distance for 8, and still finds a cheapest route because the estimate never overstates it; weighted A* multiplies the estimate by a weight above 1 and trades route cost for fewer expansions. A drawn route of straight segments is tested against each rectangular obstacle with the separating-axis test.

Sources and further reading

  • Dijkstra's shortest-path algorithm: E. W. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik 1(1), 1959, pages 269-271. doi:10.1007/BF01386390
  • The A* search, its use of an estimate of the remaining cost, and why an estimate that never overstates that cost gives a cheapest path: P. E. Hart, N. J. Nilsson and B. Raphael, "A formal basis for the heuristic determination of minimum cost paths", IEEE Transactions on Systems Science and Cybernetics 4(2), 1968, pages 100-107. doi:10.1109/TSSC.1968.300136
  • Weighting the estimate against the cost so far: I. Pohl, "Heuristic search viewed as path finding in a graph", Artificial Intelligence 1(3-4), 1970, pages 193-204. doi:10.1016/0004-3702(70)90007-X
  • The Manhattan and diagonal (octile) distances on square grids, and the trade between speed and route quality when the estimate is scaled up: A. Patel, Heuristics, part of Amit's Thoughts on Pathfinding, Stanford University theory group pages. Stanford
  • Testing a line segment against a box by separating axes: C. Ericson, Real-Time Collision Detection, Morgan Kaufmann, 2005, chapter 5, Basic Primitive Tests.

No table or text from any of these publications is reproduced, and none of their authors or publishers has reviewed or endorses this laboratory.

This laboratory is for learning. Its results hold only within its stated ranges; the robot is a point on a 10 by 10 grid with no size, dynamics or sensing, so a planned route here is not a safe path for a real robot.

Links were current at build time. If one moves, search the document's title rather than reporting a broken link as a defect.

Results are informational and not professional advice. See our Terms of Use. Powered by SpreadsheetWeb · About · Privacy · Terms