Why is mathematics important in robot path planning? A robot does not merely “see a destination and go”. It represents space, divides motion into possible states, assigns costs, predicts which choices look promising and updates when sensors disagree with the map. Graph theory, geometry, probability and optimisation turn movement into a searchable problem.
This guide centres on A* search and heuristics, then connects the algorithm to real robotic limits. A shortest path on a grid may be impossible for a wide robot, too sharp for a vehicle, energy-hungry on a slope or unsafe under uncertainty. The mathematics matters twice: first to find a path, and again to decide whether the path deserves to be followed.
The Short Answer: Turn Space Into a Graph
A graph contains nodes and edges. A node can represent a grid cell, road junction, robot pose or configuration. An edge represents an allowed move. Each edge has a cost: distance, time, energy, risk or a weighted combination.
Path planning asks for a sequence of connected nodes from start to goal with minimum acceptable total cost. Dijkstra’s algorithm expands the cheapest known frontier. A* adds a heuristic estimate of remaining cost, allowing the search to focus toward the goal.
- State describes where the robot is and sometimes its orientation or speed.
- Action changes one state into another.
- Edge cost prices that action.
- Path cost g(n) is cost already accumulated to node n.
- Heuristic h(n) estimates cost remaining to the goal.
- Evaluation f(n) equals g(n)+h(n).
- Constraint rules out motion that violates geometry or safety.
The simple formula f=g+h is powerful because it balances evidence already paid with an informed estimate of what remains.
From Floor Plan to Occupancy Grid
An occupancy grid divides a map into cells. Each cell may be free, occupied or unknown, often with a probability. A four-connected grid allows up, down, left and right. An eight-connected grid also permits diagonals.
If horizontal and vertical moves cost 1, while diagonal moves cost √2, path cost approximates Euclidean distance better than charging 1 for every move. A diagonal across a unit square is longer than one side.
Resolution trade-off
A 10 m by 10 m room represented with 0.5 m cells has 20×20 = 400 cells. At 0.1 m, it has 100×100 = 10,000 cells. Finer resolution captures narrower spaces but creates 25 times as many cells.
Memory and search time grow. Yet a grid too coarse can erase a doorway or create a false gap. Resolution should match robot size, sensor quality and task.
Did You Know? A map is already a mathematical model before an algorithm searches it. If the grid misrepresents the world, a perfect A* implementation returns the best path through the wrong map.
Dijkstra’s Baseline
Dijkstra’s algorithm maintains a best-known cost from the start. It repeatedly selects the frontier node with smallest g, relaxes outgoing edges and records cheaper routes. With non-negative edge costs, it finds an optimal path.
Imagine nodes S, A, B and G. Edges: S–A costs 2, S–B costs 5, A–B costs 1, A–G costs 7, B–G costs 2. Direct-looking S–B–G costs 7. S–A–B–G costs 2+1+2 = 5, so it is better.
The algorithm’s “relaxation” updates B from cost 5 to 3 after reaching A. This is dynamic correction: a first estimate is not sacred when a cheaper route appears.
For a robot, nodes can number in the thousands or millions. Dijkstra’s search may explore broadly even when the goal lies in one direction. A* uses a heuristic to prioritise.
A* Search
A* chooses the open node with the smallest f(n)=g(n)+h(n). g is exact cost from the start along the current best path. h is an estimate from n to the goal.
If h=0 everywhere, A* becomes Dijkstra’s algorithm. If h is informative and appropriately bounded, A* can examine far fewer nodes while retaining optimality under standard conditions.
A small worked example
Suppose start S connects to A with cost 2 and B with cost 4. The goal estimates are h(A)=4 and h(B)=1. Then f(A)=6 and f(B)=5, so B is expanded first.
If B connects to goal with cost 5, that route totals 9. A later expansion through A may find A–C costs 2 and C–G costs 2, total 6. A* does not stop merely because it first sees a goal route unless its termination conditions establish optimality.
Open and closed sets
The open set contains discovered nodes awaiting expansion. The closed set records processed nodes under an implementation’s rules. Each node stores a parent so the final path can be reconstructed backwards from goal.
A priority queue makes selecting smallest f efficient. Data structures matter: the same mathematical algorithm can run slowly with a poor implementation.
Admissible Heuristics
A heuristic is admissible if it never overestimates true remaining cost. On a four-connected grid with unit moves and no negative costs, Manhattan distance |Δx|+|Δy| is admissible because obstacles can only make the route longer.
On an eight-connected grid with diagonal cost √2, Euclidean distance is admissible. Manhattan distance can overestimate a diagonal route and therefore may lose the usual optimality guarantee unless movement costs are defined differently.
Consistency
A heuristic is consistent if h(n) ≤ cost(n,n')+h(n') for every edge. This resembles the triangle inequality. Consistency prevents estimated remaining cost from dropping by more than the step just taken and simplifies graph-search behaviour.
An admissible but weak heuristic, such as zero, explores many nodes. A strong admissible heuristic close to the true cost focuses search. Designing h is about useful information without unjustified optimism in the wrong direction.
Weighted A*
Weighted A* uses f=g+wh with w>1. It may find a route faster by prioritising the goal estimate more strongly, but can sacrifice optimality. The engineering choice depends on whether a slightly longer path is acceptable for faster planning.
State the guarantee. “Fast” and “shortest” are separate objectives.
Heuristic Examples
| Movement model | Candidate heuristic | Caution |
|---|---|---|
| 4-neighbour grid, unit costs | Manhattan distance | Assumes no cheaper diagonal |
| Free plane, distance cost | Euclidean distance | Ignores obstacles |
| 8-neighbour grid | Octile distance | Must match diagonal cost |
| Road network | Straight-line distance | Cost must be at least geometric distance |
| Energy terrain | Lower-bound energy | Needs a defensible physical bound |
If cost is travel time, straight-line distance alone has wrong units. Divide by a valid maximum speed to obtain a lower-bound time. Unit analysis improves heuristic design.
Robot Size and Configuration Space
A point robot can pass through any non-occupied cell. A physical robot has width and shape. Configuration space expands obstacles by the robot footprint and treats the robot reference point as a point.
If a circular robot has radius 0.3 m, obstacles are inflated by at least that radius, plus an appropriate margin under the model. A corridor 0.5 m wide that looks open on a centreline map becomes blocked.
For a rectangular robot that rotates, state includes orientation. A pose can be (x,y,θ). A passage may be feasible only at certain angles. The search dimension grows from a 2D grid to a 3D configuration lattice.
Curse of dimensionality
A robot arm with six joints has a six-dimensional configuration space. If each joint has 100 sampled angles, a full grid would have 100^6 states—one trillion. Sampling-based planners such as probabilistic roadmaps and rapidly exploring random trees address high-dimensional spaces differently.
A* remains useful on discretised state lattices, but the representation must stay computationally manageable.
Kinematic Constraints
A car-like robot cannot move sideways instantly and has a minimum turning radius. A grid path with right-angle corners may be geometrically collision-free but dynamically impossible.
A state lattice precomputes motion primitives that respect vehicle kinematics. Edges become short feasible trajectories rather than arbitrary neighbour jumps. Cost can include distance, reverse motion, steering change and clearance.
Curvature
Curvature κ is roughly inverse turning radius R: κ=1/R for a circle. A vehicle with minimum radius 4 m has maximum curvature magnitude 0.25 m⁻¹. A smoothed path must respect this.
Shortest geometric path is not always most driveable. Repeated sharp turns cost time and control effort. A cost function can penalise curvature or steering changes.
Cost Functions
Path cost can combine several terms:
J = wd×distance + wt×time + we×energy + wr×risk + ws×smoothness.
Weights convert priorities into a scalar objective. They also introduce judgement. Doubling wr may send the robot farther from obstacles. If units differ, normalise terms or interpret weights carefully.
Pareto trade-offs
One path may be short but close to hazards; another long but clear. Neither dominates if each is better on one objective. A Pareto frontier shows non-dominated options rather than hiding the choice in one weighted score.
In a household robot, comfort and predictability may matter. In a planetary rover, energy and terrain risk may dominate. There is no universal best cost function.
NASA’s Planning and Scheduling Group describes planning systems that search for shortest or fuel-efficient plans across missions. The public description supports the general mechanism; mission algorithms remain task-specific.
Uncertainty and Occupancy Probability
Sensors are noisy. A lidar return, camera classifier or sonar measurement does not produce perfect certainty. Occupancy grids can store probabilities or log-odds and update them with new evidence.
If prior occupancy probability is 0.2 and a measurement is more likely when occupied than free, Bayesian updating raises the probability. Repeated independent consistent evidence can strengthen belief, but sensor errors may be correlated.
Unknown is not free
Treating unknown cells as free makes exploration bold but risky. Treating them as occupied can stop progress. A planner may assign an exploration cost, require sensor visibility or use a separate frontier-exploration strategy.
Risk-aware planning can minimise expected cost or constrain collision probability. Expected value can hide rare severe outcomes, so chance constraints or worst-case analysis may be needed.
NASA JPL’s NeBula autonomy research describes multi-robot exploration in unknown extreme environments with belief-aware perception and planning. The work illustrates why a fixed perfect map is an unrealistic assumption.
Replanning in a Changing World
A warehouse aisle may become blocked. A pedestrian can cross. A rover can discover loose soil. Replanning algorithms reuse earlier search information when edge costs change.
D* Lite and related methods update paths efficiently rather than starting fully from scratch. Model predictive control plans over a moving horizon, executes part of a trajectory and replans.
Global and local planners
A global planner finds a route through the map. A local planner handles immediate obstacles and dynamics. If the local planner repeatedly cannot follow the global path, the global representation or cost may be wrong.
Layered planning needs coordination. A locally attractive detour can trap the robot; a globally optimal line can be unsafe now. Feedback closes the loop.
A Complete Grid Example
Imagine a 7×7 grid. Start is (1,1), goal (7,7). Cells (3,1) through (3,5) form a wall except opening at (3,4). Four-neighbour moves cost 1.
Manhattan h from start is |7−1|+|7−1|=12. The direct Manhattan lower bound ignores the wall. A* expands nodes with small g+h, reaches the opening and constructs a route.
If the wall forces two extra steps, optimal path cost may be 14. The heuristic never exceeded true remaining cost, so it remained admissible.
Now add terrain cost 5 to muddy cells. A geometrically shortest 14-step route crossing four muddy cells costs 10 normal steps + 4×5 = 30. A 17-step all-normal detour costs 17 and is better. “Shortest” depends on what an edge costs.
Tie-breaking
Several nodes can have equal f. Tie-breaking toward larger g may follow a narrower front; other rules affect search order but not optimal cost under suitable conditions. Visual differences do not necessarily mean different answers.
Path Smoothing
Grid paths zigzag. Smoothing replaces corners with curves or line-of-sight shortcuts while preserving collision clearance and kinematic feasibility.
If points A, B and C form a right-angle detour but segment AC is obstacle-free, remove B. Repeating this shortens the polyline. For a vehicle, use splines or clothoids with curvature constraints.
Smoothing after search can create collisions if it cuts corners near inflated obstacles. Validate the continuous path, not just the original cells.
For a related curve mechanism, read Why Mathematics? | Bézier Curves, Animation and Digital Design. Animation and robotics use curves differently, but both need controlled geometry between points.
Complexity and Performance
With a binary heap, Dijkstra and A* often have complexity expressed around O((V+E)log V), depending on implementation. Big-O describes growth, not exact seconds. Map structure, heuristic strength and memory access matter.
Measure expanded nodes, planning time, path cost and success rate. A faster algorithm that returns infeasible paths is not better. A planner tested only on easy maps may fail in narrow passages.
Benchmark fairness
Use the same maps, start-goal pairs, robot footprint and cost definition. Report hardware and time limits. Randomised planners need multiple trials and variation, not one lucky run.
NASA’s machine-learning-based rover path-planning report discusses learned heuristics that reduce expensive terrain evaluations while maintaining or improving navigation measures in its tested context. It is evidence for a specific method, not proof that learned heuristics always outperform classical ones.
Machine Learning and Heuristics
A model can predict terrain difficulty or remaining cost from past data. If it overestimates, classic A* optimality may be lost. Hybrid systems can use learned predictions for ordering while retaining certified lower bounds for guarantees.
Training distribution matters. A heuristic learned on flat indoor floors may fail on rocks, glare or unusual obstacles. Monitor uncertainty and keep fallback behaviour.
The broader lesson appears in Why Mathematics? | Machine Learning, Loss Functions and Gradient Descent. Learning tunes predictions; planning uses predictions inside a sequential decision system.
Common Misconceptions
“A* always finds the shortest path”
Only under stated conditions: suitable non-negative costs, implementation and an admissible/consistent heuristic for the usual guarantee.
“The heuristic is a guess, so accuracy does not matter”
Its properties control efficiency and guarantees. An overestimate may change optimality.
“A free grid cell is safe”
Not unless robot footprint, uncertainty and motion between cells are considered.
“Shortest distance is best”
Time, energy, risk, turning and clearance can matter more.
“A complete map means no replanning”
The environment and localisation can change. Feedback remains necessary.
“More detailed grids are always better”
They increase computation and may amplify noisy map detail. Resolution should match task and sensing.
Which Mathematics Matters?
| Mathematics | Planning use | Student question |
|---|---|---|
| Graph theory | Nodes, edges, paths | What moves are allowed? |
| Geometry | Distance and clearance | Does the robot fit? |
| Algebra | f=g+h | What is paid and estimated? |
| Inequalities | Admissibility and constraints | Is the bound valid? |
| Probability | Occupancy and risk | How certain is the map? |
| Optimisation | Minimum-cost routes | Which objective matters? |
| Calculus | Smooth trajectories | Are speed and curvature feasible? |
| Computing | Priority queues and complexity | How does performance scale? |
This is mathematics in AI without magic. The robot’s “decision” is a model, cost function, search process and feedback loop that people designed and must test.
A Student Coding Project
Create a small grid in a spreadsheet or programming language. Mark obstacles, start and goal. Implement breadth-first search for unit costs, then Dijkstra for varied costs, then A* with Manhattan distance.
Display expanded cells. Compare path cost and node count. Add diagonal moves and observe why the heuristic must change. Inflate obstacles by one cell to model a larger robot.
Next, add random blocked cells after the first path and replan. Record failures. Write a test suite:
- Start equals goal should return cost zero.
- An isolated goal should report no path.
- With no obstacles and unit four-neighbour moves, cost should equal Manhattan distance.
- Raising one edge cost must not produce a cheaper path through it.
- Path cells must all be valid.
The project is safe because it remains a simulation. Do not connect untested code to moving hardware near people.
Guidance for Parents and Students
Questions that turn a demo into evidence
Ask the student to predict the route before running code. Then change one feature: add a wall, raise a terrain cost, allow diagonal motion or inflate obstacles. The student should explain which part of the model changed and why the new result follows.
Useful review questions include:
- Is the returned path valid under every movement rule?
- Does its cost equal the sum of its edges?
- Can Dijkstra confirm the optimal cost on a small map?
- How many states were expanded, and what was peak frontier size?
- Does tie-breaking change the route but not optimal cost?
- What happens when the goal is unreachable?
These checks reward reasoning, not animation. A colourful robot that reaches the goal once is weaker evidence than a plain test suite that catches incorrect paths.
Keep the world model visible
Display occupied, free and unknown cells differently. Draw the robot footprint or inflated obstacles, not just its centre. Show start, goal, explored cells and final path. If costs vary, use a labelled scale rather than unexplained colours.
Visibility helps reveal when an algorithm solves the wrong problem. A route through an unknown zone may be cheapest only because unknown cells were accidentally assigned zero cost. A route grazing a wall may look safe only because the displayed dot is smaller than the robot.
Ethical and operational limits
A school project should run in simulation or a controlled tabletop space at safe speed with adult supervision. It should not control vehicles, medical equipment or machines near the public. Real deployment requires engineering assurance, cybersecurity, monitoring, emergency stops and accountability beyond search code.
When optimisation affects people, document whose time, comfort or access is represented. A hospital delivery robot that blocks a corridor may have a short route but a poor operational outcome. Mathematics reveals trade-offs only when the cost function includes them honestly.
Parents can use a familiar maze. Ask the child to label each square with cost-so-far and distance-to-go. The arithmetic reveals why moving toward the goal can still be wrong when a wall blocks the route.
Students should distinguish algorithm from representation. When a route looks absurd, inspect map, edge costs, footprint and heuristic before blaming “AI”.
For a real transport analogy, Why Mathematics? | School Commutes, Maps and Route Planning shows how human routes also trade distance, transfers, time and reliability.
Careers and Learning Pathways
Path planning appears in robotics, autonomous vehicles, games, logistics, aerospace, manufacturing, mapping and computer science research. Roles combine mathematics with software, electronics, mechanics, perception, safety and human factors.
Mathematics alone does not guarantee entry or employment. Students should check current course requirements and build fundamentals in algebra, geometry, probability and coding. A small tested planner demonstrates reasoning more honestly than a large unverified demo.
Build tests before adding features
Create tiny maps where the answer is known. One should have a straight unobstructed route. One should require a detour. One should have no route. One should make a tempting but expensive edge worse than a longer cheap path. For each map, assert whether a path exists and its expected cost.
Then compare A* with Dijkstra using the same graph. With an admissible heuristic and correct implementation, both should return the same optimal cost, while A* may expand fewer nodes. If costs differ, treat that as a bug or an assumption mismatch before celebrating speed.
Measure more than runtime. Record expanded nodes, path cost, memory, clearance and replans. A result that is fast only because it ignores orientation or robot size is not a fair improvement.
Designing a Cost Function Without Hiding Values
A planner often combines distance, time, turning, energy, risk and comfort. One simplified edge cost could be
\[ c = d + \alpha T + \beta R, \]
where d is distance, T is a turning penalty and R is a risk score. The weights alpha and beta are not mathematical truths. They encode how much the designer is willing to trade one objective for another.
Suppose route A is 20 m with turning score 8 and risk score 1, while route B is 24 m with turning score 2 and risk score 0. With alpha = 0.5 and beta = 10, costs are 34 for A and 25 for B. The longer route wins. If beta is reduced to 1, both cost 25. The best path changed because the value judgement changed, not because geometry changed.
Normalisation matters when terms use different scales. Adding metres directly to a probability or degrees without explaining units can make one term dominate accidentally. A designer might divide each measure by a meaningful reference, convert it to an estimated time or energy, or keep objectives separate and present a Pareto frontier.
Safety constraints should not always be softened into a penalty. A forbidden region remains forbidden even if crossing it saves enough distance. The model should distinguish hard constraints from preferences.
Landmark Heuristics and Better Lower Bounds
Straight-line distance is easy, but obstacles can make it weak. One way to build a stronger admissible heuristic on a fixed graph is to precompute shortest-path distances to selected landmarks. The triangle inequality gives a lower bound such as
\[ h(n)=|d(L,goal)-d(L,n)|. \]
Take the maximum bound over several landmarks. If stored distances are exact and graph assumptions match, this can guide search more strongly without overestimating.
The trade-off is memory and preprocessing. Landmark placement also matters: several landmarks clustered in one corner may add little information elsewhere. This shows a recurring computing pattern—spend resources before a query to answer many later queries faster.
Students need not implement landmarks first. Manhattan, Euclidean or octile distance is enough to learn A*. The advanced method is useful because it shows that a heuristic can be derived from a proof, not merely chosen by intuition.
Multi-Robot Planning and Time as a Dimension
Two robots can each have a collision-free geometric path and still collide with each other. Coordination adds time to the state. A vertex conflict occurs when two robots occupy the same location at the same time. An edge conflict occurs when they swap positions across the same edge in opposite directions.
A simple classroom method plans one robot first, then treats its timed reservations as obstacles for the next. This is easy but gives priority to the first robot and may miss a better joint solution. More advanced methods search over constraints or joint states. The state space grows rapidly because combinations multiply.
Consider two robots approaching a one-cell-wide doorway. Pure shortest paths send both into the doorway at the same time. A valid schedule might delay one robot by two steps. Route geometry barely changes, but makespan and waiting time do. Optimising total travel may conflict with fairness if the same robot always waits.
This example links algorithms to social choices. Fleet planners for warehouses, hospitals or campuses may need throughput, energy, priority jobs and human comfort. Mathematics makes those trade-offs explicit, but people remain responsible for choosing them.
From Path to Trajectory
A grid path is usually a sequence of positions. A physical robot needs a trajectory: position, velocity and often acceleration as functions of time. Corners that are geometrically valid may require an instantaneous heading change, which no ordinary vehicle can execute.
Time parameterisation assigns speeds while respecting limits. If a robot must travel 3 m from rest and stop, a naive constant 1 m/s calculation gives three seconds but ignores acceleration and braking. With acceleration limited to 0.5 m/s², the achievable speed profile and total time differ.
Curvature matters for steering. Smoothing can replace sharp corners with arcs or splines, but the smoothed curve must be collision-checked again because it may cut across an obstacle. Faster is not automatically safer: sensor range, braking distance and localisation uncertainty constrain speed.
This is why robotics separates layers. Search proposes a route through abstract space. Trajectory generation makes motion dynamically feasible. Control tracks that trajectory. Perception updates the world model. A weakness in any layer can invalidate the overall result.
Explaining Planner Failure Clearly
“The robot got stuck” is not a diagnosis. A useful failure report distinguishes several possibilities:
- no path exists in the current graph;
- a path exists, but the heuristic or implementation failed;
- the map marks a real passage as occupied;
- the robot footprint was modelled too large for the passage;
- the global route exists, but the local controller cannot execute it;
- moving obstacles repeatedly invalidate the route;
- localisation error places the robot in the wrong state.
Log the map version, start, goal, parameters, expanded states and termination reason. Visualise final open and closed sets. Reproduce the issue on a saved map. This turns debugging into evidence rather than guesswork.
The same habits apply far beyond robots. Define the model, preserve inputs, separate infeasibility from software failure, and communicate uncertainty. Those are central benefits of learning mathematics through algorithms.
Frequently Asked Questions
What does A* stand for?
It is commonly pronounced “A-star”. The name distinguishes it from related search algorithms; it is not an abbreviation that needs expansion.
What is a heuristic?
An estimate used to guide search toward promising states. For optimal A*, it usually must not overestimate remaining cost.
Why not always use Euclidean distance?
The heuristic must match the movement and cost model. In some grids Manhattan or octile distance is stronger while remaining admissible.
What if there is no path?
The search should terminate with failure after exhausting reachable states. A robot then needs another goal, map update or human assistance.
Is path planning the same as obstacle avoidance?
No. Global planning chooses a route; local avoidance reacts to immediate obstacles. Systems often combine both.
Can A* plan for a robot arm?
Yes on a discretised configuration graph, but high dimensionality can make exhaustive grids impractical. Other planners are common.
Are learned heuristics safe?
They can improve speed, but guarantees depend on how predictions are integrated, tested and bounded.
What is the most important habit?
Define the state, allowed moves, cost and constraints before choosing an algorithm.
A Practical Learning Ladder
- Stage 1: Solve mazes with breadth-first search.
- Stage 2: Add varied edge costs and Dijkstra.
- Stage 3: Add A* and an admissible heuristic.
- Stage 4: Compare grid movement models.
- Stage 5: Inflate obstacles for robot size.
- Stage 6: Add orientation and turning constraints.
- Stage 7: Represent uncertainty and replan.
- Stage 8: Benchmark path quality, time and safety checks.
Final Perspective: A Route Is an Argument
A final comparison
Suppose Dijkstra expands 900 cells and returns a path costing 64. A* with an admissible heuristic expands 240 cells and returns cost 64. The result suggests the heuristic saved search work without sacrificing optimal cost on that case. It does not prove the same improvement on every map.
Now use weighted A* and obtain cost 68 after expanding only 90 cells. The planner is faster by these measures, but the returned path is 6.25% more costly than 64. Whether that trade-off is acceptable depends on the application and the algorithm's documented bound—not on speed alone.
Finally, inflate obstacles for the robot footprint and find that the original 64-cost corridor disappears. A new valid path costs 80. That is not necessarily algorithm failure. The original point-robot model asked an easier, physically wrong question. Better modelling can make a numerical result look worse while making the plan more truthful.
Report all three stages with the same map, hardware, implementation and timing method. A transparent benchmark tells readers what changed. A headline such as “A* is ten times better” does not.
A robot path is not merely a line. It is an argument: these states were considered, these moves were allowed, these costs mattered, this heuristic guided the search and these constraints were respected.
Mathematics makes that argument inspectable. Graphs organise choices. Geometry keeps the body out of walls. Heuristics focus computation. Probability represents uncertain maps. Optimisation exposes trade-offs.
That is why mathematics matters in robotics and AI. It replaces the vague instruction “go there safely” with a system that can be tested, challenged and improved—while reminding us that the quality of the route can never exceed the quality of the world model beneath it.