Once a robot has a general understanding of its surroundings, it faces two big challenges: choosing a sensible route through that space and keeping itself on track as it moves. Route planning is about deciding where to go next, while progress tracking is about checking how well the robot is following the plan.
How Robots Plan a Route
At its core, route planning is the process of finding a safe pathway through an environment while avoiding collisions. There are several families of approaches, each useful for different situations.
Graph Search Methods
When the environment can be broken into a tidy network of positions, the robot can treat each position as a node in a graph and search that graph for a good route. Two of the most widely used approaches are Dijkstra’s algorithm and A*.
Dijkstra’s Algorithm
Dijkstra’s method follows a simple principle: find the shortest possible path by exploring every reachable position in order of increasing distance from the start. It begins by assigning the start position a distance of zero and treating all other positions as extremely far away. It then repeatedly selects the position with the shortest known distance, examines all its neighbouring positions, and updates their distances if a shorter route is found through the current point. Once all neighbours are checked, that position is marked as complete, meaning its shortest distance is known for sure. This process repeats until the goal is reached.
Dijkstra’s strength lies in its reliability. If a shortest path exists, it will find it. However, it has a significant drawback: it does not pay attention to where the goal is. It explores every direction equally, even those that clearly lead away from the destination. In large environments, this can make it slower than necessary.
A* Algorithm
A* builds on Dijkstra’s idea but adds an important improvement: it estimates how far each position is from the goal. This estimate, called a heuristic, acts like a sense of direction. Instead of exploring everything blindly, A* prioritises the positions that seem both cheap to reach and likely to lead toward the goal.
The robot calculates two values for each new position it considers: the actual cost travelled so far and the estimated remaining distance. These are added together to produce a priority value. The algorithm always chooses the position with the lowest priority value, meaning it tends to look in promising directions first.
This combination of real cost and estimated cost helps A* find excellent routes while avoiding huge amounts of unnecessary exploration. It is often the best balance between speed and accuracy, which is why it is one of the most widely used algorithms in robotics today.
Dynamic Replanning
Real-world conditions can change rapidly, and a path that looked safe when the robot started may become blocked or unsafe moments later. A person might walk into the robot’s path, a door could close unexpectedly, or a new obstacle might appear. Because of this, modern robots need to do more than simply plan once and follow the route rigidly. They need the ability to adapt on the move.
Dynamic replanning allows a robot to revise its route while it is still travelling. Instead of discarding the entire plan and starting again, the robot updates only the parts of the route affected by the new information. This makes the process much faster and keeps the robot responsive.
The robot continually monitors its surroundings using its sensors. If the situation matches what the robot expected, it simply follows the existing route. But if something changes, the robot performs a quick check to see whether the current path is still valid. If it is not, the planner immediately begins adjusting the route.
Algorithms designed for this type of adaptation reuse the work already done. A well-known example is D*, which stands for Dynamic A*. Instead of performing a full search from scratch, D* recalculates only the sections influenced by the change. For example, if a single link between two positions becomes blocked, D* updates only the parts of the graph that depend on that link, allowing the robot to recover and find a safe alternative very quickly.
This cycle of sensing, checking, and updating continues throughout the journey. Dynamic replanning is essential in busy or unpredictable environments such as homes, warehouses, and urban spaces where static plans would quickly become outdated.
Sampling-Based Planners
When robots move in complex ways, such as robot arms with many joints, the number of possible positions becomes enormous. In these cases, planners often rely on random sampling rather than examining every possibility.
Probabilistic Roadmaps (PRMs) work by creating a network of random, collision-free points and then linking them into a graph. The robot’s start and goal are added to this network, and a path is searched within the graph.
Rapidly-Exploring Random Trees (RRTs) grow outward from the robot’s starting position, extending branches toward random points until one of them reaches the goal. These methods don’t guarantee the perfect path, but they can find workable solutions in large, complex spaces where traditional search would be too slow.
Learning-Based Approaches
Some robots operate in environments that are unpredictable or change constantly. In these situations, learning-based planning can be helpful. Through reinforcement learning, a robot tries different actions and observes which ones lead to success. Deep learning can also interpret complex sensor data and suggest safe motions. While flexible, these methods are often combined with more traditional planners to ensure safety.
How Robots Track Their Progress
Once a route is planned, the robot must ensure it actually follows it. To do this, it repeatedly estimates its position using sensors such as wheel encoders, motion sensors, and cameras. This process, known as localisation, allows the robot to compare where it thinks it is with where the plan expects it to be.
As the robot moves, it looks at the nearest part of the planned path and measures how far it has drifted, either sideways or along the route. Small corrections are constantly made by turning slightly more, slowing down, or adjusting orientation. This feedback loop continues throughout the journey.
If something unexpected appears, such as a person stepping out or a box in the way, the robot updates its understanding of the environment and checks whether the original plan still works. If not, it triggers a quick replanning step so that it can continue safely.
