In the designs we favour, AI navigation sits around classical search and feeds it better numbers. A*, Dijkstra and RRT guarantee a shortest path on a fixed graph with a fixed heuristic, but that guarantee stops applying once the cost function becomes dynamic, partially observable or shaped by what other agents are likely to do. Learned components (a heuristic, a cost map, sometimes an end-to-end policy) are the practical way to close that gap. The measured results below show where each side wins, and why the hybrid is the design we would start from.
How AI navigation differs from A* and Dijkstra
The difference starts with what the system plans from. Model-based navigation plans a path from a mathematical model of the environment, using dynamic programming or graph search, while model-free navigation learns a policy through reinforcement learning or apprenticeship learning and keeps no explicit model. In a standard mobile-robot stack the classical version looks like GMapping for mapping, Adaptive Monte Carlo Localization for position, A* as the global planner and the Dynamic Window Approach (DWA) as the local planner. DWA picks the linear and angular velocity pairs the robot can actually reach in the next control period, then drops any pair that would not let it stop before hitting an obstacle.
One study compared A, Dijkstra, RRT and an ant-colony optimiser on weighted road networks derived from satellite imagery and airborne LiDAR, and among the planners it tested, Dijkstra gave the most stable and efficient performance in both 2D and 3D, especially on dense pixel-level maps.
The learned policy in another study failed differently. The study trained mapless deep reinforcement learning (DRL) agents on depth images in static simulated indoor environments. Its best goal-reaching agent got to the goal 96.9% of the time in its training environment, and only 35.5% of the time under different conditions. Inside the training environment the agent’s trajectories were straighter and shorter than those of the Turtlebot2 navigation stack running Dijkstra and DWA, and it preferred going between obstacles rather than planning around them. The authors put the drop down to the agent not being able to localise its goal reliably once conditions changed.
So the honest contrast is this. Classical search gives guarantees on the model it is given, and the learned policy in that study beat it on path length in its training environment, then dropped sharply under changed conditions.
Why the strongest planners keep A* and learn the heuristic or cost map
We favour the hybrid because it learns the part classical search gets wrong and leaves the guarantees in place. Instance-independent heuristics such as Manhattan distance ignore obstacles, so A* guided by them performs poorly in obstacle-rich grids. One method uses transformers to learn instance-dependent heuristic proxies. One of them, a path-probability map, plugs into Focal Search as a secondary heuristic and keeps the bounded-suboptimality guarantee. The authors report up to a 4x cut in A* computational effort, with solution costs less than 0.3% above optimal on average.
Neural A* takes a related route. It makes A* differentiable and couples it with a convolutional encoder that turns a problem instance into a guidance map, so the whole planner trains end to end against expert paths. Neural A* also predicted realistic human trajectories by planning directly on natural image inputs.
Cost maps are the other place where learning enters. A purely geometric robot may treat a field of tall grass as untraversable and never reach its goal. BADGR learns navigational affordances from self-supervised real-world data, with no simulation or human labelling, and it can take terrain preferences into account. On off-road courses from 400 m to 3,150 m, a self-supervised costmap method that combines exteroceptive data with proprioceptive feedback cut interventions by up to 57% against an occupancy-based baseline.
Nav2’s costmap is already built to accept AI outputs. The Nav2 Costmap 2D package lists sensor-processing plugins for AI outputs, depth-sensor obstacle buffering and semantic information, and the planner and controller servers use the result to check for collisions and higher-cost areas. A learned traversability model becomes one more layer, and the planner on top stays the same.
Classical, learned or hybrid: a component-by-component guide
| Navigation situation | What the evidence favours | Basis |
|---|---|---|
| Static weighted road map on a dense pixel grid | Dijkstra | Most stable among the classical planners tested on 2D and 3D road maps |
| Obstacle-rich grid where search effort matters | A* with a learned heuristic, keeping bounded suboptimality | Up to 4x less search effort, under 0.3% cost overhead |
| Terrain where geometry misleads (grass, mud, slopes) | Learned traversability costmap feeding a classical planner | Up to 57% fewer interventions off-road |
| Map changes as the robot moves | Incremental replanning (D* Lite) plus a local planner | Reuses earlier searches instead of replanning from scratch |
| Dense human crowds | Learned local policy that models interactions | Attention-based DRL anticipates crowd dynamics |
| No prior map, environment like the training set | Mapless DRL, with a generalisation drop expected | One simulated agent: 96.9% in training vs 35.5% under changed conditions |
| Finding objects in unseen buildings | Modular semantic map plus planning, not end-to-end | Beat end-to-end baselines in Habitat ObjectNav |
How do AI navigation systems handle obstacles that move?
Incremental and real-time replanning are the classical answers to changing environments. D* Lite applies Lifelong Planning A* to navigation in unknown terrain: it reuses information from earlier searches, so it solves a series of similar search problems much faster than starting each one from scratch. Autonomous mobile robots can also run real-time replanning in the operation layer, which closes the gap between planning and execution. Online planning in unpredictable environments still carries real computational cost.
In Nav2, the ROS 2 navigation stack, a behaviour tree orchestrates the navigator’s tasks, and the stack includes methods designed for dynamic environments.
Learned policies help where the obstacles are people in dense crowds. Crowd-Robot Interaction (2018) uses self-attention to model human-human as well as human-robot interactions, because earlier DRL policies cooperated less well as crowds grew. Perception has a dynamic-scene problem of its own. vSLAM systems typically assume a static scene and photometric consistency. DynaVINS addresses this by predicting the motion of dynamic objects so that visual-inertial SLAM keeps updating its map as the scene changes. The 2023 review that reports this also warns that deep-learning SLAM can degrade in highly dynamic, unstructured environments its training did not cover.
Keeping robots and drones on course without GPS or a prior map
Indoor techniques split into map-based, map-building and mapless approaches, and mapless methods rely mainly on visual data to infer where the goal is. The usual approach is SLAM in a map-building system.
Mapless DRL is attractive because it needs no map, depends less on sensor accuracy and needs less environment-specific engineering. The real-world numbers show the cost. In a 2020 study, a Soft Actor-Critic policy for depth-based mapless navigation was trained in simulation with incrementally increasing environment complexity, then tested on a Wifibot with an Intel RealSense D435 in a 7 m by 7 m room with four box obstacles. The approach doubled the success rate of a naive training strategy, and the best incrementally trained model reached 47% success. The authors expect it to fail in labyrinth-like environments, because the depth observations would differ too much from training.
The headline simulation results need careful reading. DD-PPO trained an agent for 2.5 billion steps and essentially solved PointGoal navigation in unseen environments without a map, but it used an RGB-D camera together with a GPS and compass sensor. That makes it a map-free result, not a GPS-free one. The compute side is useful planning input: DD-PPO scaled to a 107x speedup on 128 GPUs, and it reached 90% of peak performance at 100 million steps, in under a day on 8 GPUs. Truly GPS-free learned navigation has been shown too: Mirowski and colleagues trained an LSTM-based network on real city-scale imagery to navigate without maps or GPS.
The gap between simulation and reality strongly limits these methods. Many RL navigation algorithms that do well in simulation cannot handle real-world problems because of the gap between simulated and real scenes. Adding a vSLAM map to the navigation loop is one way to narrow that gap, and modular semantic exploration transferred to a physical robot with similar performance thanks to its domain-agnostic module design. The evidence here favours a SLAM or semantic-map backbone with learned perception over an end-to-end policy.
What computer vision contributes to AI navigation
Computer vision supplies depth, obstacles, semantics and ego-motion estimates. Depth is central to scene reconstruction, self-localisation and obstacle avoidance. RGB images are sensitive to lighting and colour changes that may have nothing to do with the navigation task, while depth images carry geometry and have given good results in DRL. One comparison found a classical modular pipeline beat a learned agent when given RGB-D input, but failed badly without depth.
Deep networks can recover per-pixel depth from single images, and combining learned depth with traditional vSLAM overcomes monocular scale ambiguity and can replace RGB-D sensors for mapping. Learned pose networks also avoid the keyframe and feature tuning of traditional visual odometry. Traditional feature-based methods also fail to initialise and track in low-texture and repeated-texture scenes.
On the semantic side, detectors such as Faster R-CNN and YOLO give real-time object detection, and encoder-decoder segmentation networks such as U-Net and DeepLab label each pixel for finer scene understanding. Nav2 costmaps accept AI outputs and semantic information as layers, and semantic maps guide exploration.
Vision also brings its own failure modes. Cameras are limited in low light, fog and rain. Robustness to poor lighting, occlusion and sensor noise remains an open problem for deep models, and training needs large datasets that often have to be synthesised or cleaned. When a navigation system misbehaves in the field, we would check the perception layer before the planner, because a planner can only be as good as the costs it is given.
The open question is generalisation
For one simulated agent, success fell 61 points, from 96.9% in training to 35.5% under different conditions. The 2023 review calls for more work on combining deep learning with conventional navigation methods. The design we would start from: classical search and replanning carry the guarantees, while learned heuristics, costmaps and perception go where hand-written rules are weakest. Each learned part should be tested on conditions it was not trained on before anyone trusts it. The same tension between learned models and established methods runs through AI tools for drug discovery, where models also need testing beyond their training data.
