| Planner | Approach | Property to know | Planning use |
|---|---|---|---|
| Dijkstra’s algorithm | Grid or graph search, dated 1959 | Finds the shortest path, given unlimited computation time and resources | Baseline when path length matters more than search effort |
| A* | Dijkstra plus a heuristic, dated 1968 | Can often find an optimal path much faster than Dijkstra | Sensible first choice on a known indoor map |
| Most grid-based planners | Discretized map of cells | Resolution complete | Check the map resolution before blaming the algorithm |
| RRT | Randomly grown tree, dated 1998 | Probabilistically complete | Consider when a grid is a poor fit for the space |
Dates, the heuristic idea and the completeness terms above come from MIT’s robotic path planning course notes and The Construct’s path planning basics course.
Robot path planning algorithms for an indoor mobile robot come down to grid search on a known map or random sampling in awkward spaces. Start with A* on a costmap, and move to RRT only when a grid stops fitting.
This guide covers route computation for indoor autonomous robots and leaves the rest of the navigation stack aside. The map these planners search is explained in what is an occupancy grid map, so read that if the grid terms below are new.
Prepare the map before choosing a planner
MIT’s course notes describe robotic path planning as determining how an object can navigate through a space with known or unknown obstacles while minimizing collisions. Path planning is the route-finding core of motion planning for mobile robots, and every planner in this guide needs a map representation to work on.
The most common representation indoors is the occupancy grid. It assigns each square either a binary or a probabilistic value of being full or empty. Nav2 and similar stacks then layer a costmap on top, so that cells near obstacles carry extra cost and the planner prefers to keep its distance.
Work through the preparation in this order:
- Build or load the grid. Decide whether cells hold binary or probabilistic occupancy, because every later choice assumes one or the other.
- Add the costmap layers. Inflate obstacles so the planned line is not drawn right against walls and furniture.
- Describe the space. A tidy room of known furniture suits a grid. Irregular or very large open areas may justify sampling instead.
- Pick one planner and test it. Change planners only when the paths it returns do not suit the robot.
Grid search with Dijkstra’s algorithm and A*
Grid search is the right family for most indoor robots, because an indoor map is usually already a grid. Two algorithms dominate it, and the question of how A* differs from Dijkstra’s algorithm has a short answer: A* adds a heuristic.
Dijkstra’s algorithm
MIT’s notes date Dijkstra’s algorithm to 1959. It can guarantee that the shortest path is found, but only if it is given unlimited computation time and resources. On a small map that condition costs little. On a large map it is the thing to watch, because the search spreads in every direction rather than heading for the goal.
A*
A* is another path-finding algorithm that extends Dijkstra’s algorithm by adding heuristics, and the same notes date it to 1968. The heuristic weights each node’s cost by its Euclidean distance to the endpoint, which pulls the search toward the goal. The Construct’s course says A* can often find an optimal path much faster than Dijkstra’s algorithm. The word to keep in mind is often: it is a tendency, not a measured speed-up.
For an indoor robot with a known goal and a mapped floor, A* is the better default. Dijkstra’s algorithm suits cases where you want the plain shortest-path search without a heuristic steering it.
Sampling-based planning with RRT
RRT quickly searches a space by randomly expanding a space-filling tree, and MIT’s notes date rapidly-exploring random trees to 1998. Instead of visiting every cell, the planner adds random points to a tree until a branch reaches the goal.
When RRT beats grid search
RRT is a better choice than grid search when discretizing the space is the awkward part. It works on the space directly, so it does not depend on how finely a grid was cut. That makes it worth considering for cluttered or irregular layouts where a grid would need to be very fine to be useful.
For a standard indoor map that already exists as an occupancy grid, the simpler A* is usually the safer route. Keep these trade-offs in view:
- No fixed-time promise. Sampling-based planners are probabilistically complete. The probability of finding a solution approaches 1 as time approaches infinity, so a path is likely but not guaranteed within a fixed budget.
- Collision checks dominate. The planner must check each new point for collisions, which can be the most computationally expensive part. Lazy collision evaluation is one way to reduce that cost.
- Random results. Because the tree grows randomly, repeat runs on the same map need not produce the same route.
Global and local planning
The difference between global and local planning is scope. A global planner computes a route from start to goal across the whole map. The Construct’s course frames path planning in autonomous navigation as exactly this global path planning problem. Everything above, from A* to RRT, is a global method.
A local planner works at a smaller scale. It takes the global route and follows it while dealing with what the map did not show, such as a person stepping into the corridor. That reactive layer is a separate topic, covered where readers ask how do autonomous robots avoid obstacles. Keep the two jobs apart when you tune: a poor global route cannot be fixed by a better local planner, and the reverse is also true.
Planner plugins in Nav2
Nav2 offers its global planners as plugins that you configure in the planner_server. The configuration examples name NavfnPlanner and SmacPlanner, and moving between them is a matter of swapping the plugin identifier.
| Plugin | Identifier in the configuration | Planning use |
|---|---|---|
| NavFn | nav2_navfn_planner/NavfnPlanner | Straightforward starting point for a grid-based route |
| Smac Planner | smac_planner/SmacPlanner | Choose when you want to select the search’s motion model |
Plugin identifiers and the motion models below are taken from a Nav2 planner configuration discussion on GitHub.
The Smac configuration lists 2D Moore and Von Neumann motion models, along with SE2 Dubin and Reeds-Shepp. The 2D options belong to plain grid stepping, while the SE2 options are a separate family. Settle on the family first, then tune within it.
Start with one plugin, confirm that the route it returns is acceptable on your map, and switch only if it is not. Changing the planner, the costmap and the local planner together makes it impossible to tell which change helped.
Troubleshooting planner behaviour
- The route hugs walls. The costmap’s cost scaling should match the inflation layer’s parameter. The example configuration in the Nav2 discussion uses a cost_scaling_factor of 10.0, so compare your two values before touching the planner.
- The planner will not load. Check that the identifier in the planner_server configuration is spelled exactly as the plugin’s published string.
- RRT feels slow. Look at collision checking first, since it can be the most expensive part of the search.
Frequently asked questions
What does resolution complete mean for a grid planner?
Most grid-based algorithms are resolution complete, which ties their completeness to the resolution of the discretized map. A grid that is too coarse can hide a path that a finer one would reveal.
Is RRT* better than RRT?
RRT* is an extension of RRT that connects each new point in a way that minimizes the overall path length. It suits cases where the route’s length matters, not only whether a route exists.
Why do planners treat the robot as a point?
In configuration space, all obstacles are enlarged by half of the longest extension of the robot, so the robot itself can be treated as a point mass. Inflating obstacles in a costmap serves the same purpose, as described in MIT’s notes.
