Glossary

Fictionlab > Glossary > A* algorithm

A* algorithm

A* algorithm – definition

A* (A-star) is a graph-search algorithm used to find a minimum-cost path between a start state and a goal state. In mobile robotics, it is commonly applied to a 2D occupancy grid or costmap representing the area accessible to an unmanned ground vehicle (UGV). The algorithm evaluates candidate states using both the accumulated path cost and an estimate of the remaining cost to the goal.

A* is defined by the evaluation function:

f(n) = g(n) + h(n)

In this expression, g(n) is the known cost from the start node to node n, h(n) is the heuristic estimate from n to the goal, and f(n) is the priority used to select the next node for expansion. When the heuristic is admissible, meaning that it never overestimates the true remaining cost, A* can return an optimal path for the defined graph and cost function. In graph-search implementations that do not reopen expanded nodes, the heuristic must also be consistent to guarantee optimality.

The algorithm was formalised by Peter Hart, Nils Nilsson, and Bertram Raphael in their 1968 IEEE publication, A Formal Basis for the Heuristic Determination of Minimum Cost Paths. In UGV navigation, A* is usually a global planner. It computes a route through a map before a local controller generates velocity commands for the robot.

How A* works on a UGV costmap

A* treats the navigable environment as a set of connected nodes. In ROS 2 navigation systems, these nodes are commonly cells of an occupancy grid or a layered costmap. Each cell may represent free space, an obstacle, unknown space, or a traversal cost caused by inflation around obstacles.

The search process maintains the following core data structures:

  • Open set – candidate nodes waiting to be evaluated, usually implemented as a priority queue ordered by f(n).
  • Closed set – nodes already expanded by the planner.
  • Parent relation – a record used to reconstruct the final path from the goal back to the start.

For a four-connected grid, a node can usually connect to north, south, east, and west neighbours. An eight-connected grid also permits diagonal moves. The selected connectivity affects path shape, computational cost, and the distance metric used by the heuristic.

Common admissible heuristics, when matched to the movement and cost model, include Manhattan distance for four-connected grids and Euclidean or octile distance for grids that allow diagonal motion. A zero heuristic turns A* into Dijkstra’s algorithm. A more informed heuristic usually reduces the number of expanded cells, but it must remain compatible with the cost model if optimality is required.

A* in ROS 2 navigation

In ROS 2, A* is commonly used within the Navigation2 framework, also known as Nav2. Nav2 separates global path planning, local control, costmap generation, behaviour execution, and lifecycle management into individual nodes. A global planner normally receives a start pose, a goal pose, and a global costmap.

The primary Nav2 interface for navigation requests is the nav2_msgs/action/NavigateToPose action. Global planners return paths using nav_msgs/msg/Path. A path consists of ordered geometry_msgs/msg/PoseStamped messages expressed in a defined coordinate frame.

ROS coordinate-frame conventions are specified by REP 105. A mobile robot navigation stack normally uses the map, odom, and base_link frames. Incorrect transforms between these frames can cause a valid A* implementation to produce an unusable path.

The Nav2 nav2_navfn_planner plugin provides a grid-based planner derived from the NavFn implementation and supports an A* mode through the use_astar parameter. Nav2 also provides Smac planners, including SmacPlanner2D, which uses an A*-based search approach for 2D costmaps. Configuration options vary between ROS 2 distributions, so parameters should be checked against the documentation for the deployed Nav2 release.

planner_server:
  ros__parameters:
    planner_plugins: ["GridBased"]

    GridBased:
      plugin: "nav2_navfn_planner/NavfnPlanner"
      use_astar: true
      allow_unknown: false
      tolerance: 0.5

The example shows a Nav2 planner plugin configuration. The tolerance value is expressed in metres because Nav2 uses ROS standard SI units. Its operational effect depends on the map resolution, obstacle configuration, and reachable goal cells.

Map and sensor requirements

A* does not create a map and does not estimate robot pose. It requires an existing graph or costmap. On an autonomous UGV, that input is commonly generated from SLAM, a static map, sensor-based obstacle layers, or a combination of these sources.

The ROS message type nav_msgs/msg/OccupancyGrid stores map data as integer occupancy values. According to the ROS message definition, -1 denotes unknown cells, while values from 0 to 100 represent occupancy probabilities. The map metadata includes resolution in metres per cell, width, height, and origin pose.

  • 2D LiDAR can provide obstacle observations for a local or global costmap.
  • Depth cameras can contribute point-cloud or obstacle data after filtering and frame transformation.
  • IMU and wheel odometry support the odom transform used by local navigation.
  • GNSS/RTK can support outdoor localisation when integrated with an appropriate map and state-estimation pipeline.

Map resolution is a critical practical parameter. Smaller cells improve obstacle representation but increase the number of graph nodes and the planning workload. A map with half the cell size has approximately four times as many cells over the same 2D area. This increases memory use and can increase A* search time.

A* on Leo Rover and Raph Rover

Leo Rover is a four-wheel, differential-drive mobile platform with ROS 2 support on a Raspberry Pi-based compute unit. A* can be used as the global planning component of a Leo Rover navigation stack, but it does not make the platform autonomous by itself. The robot requires localisation, a map or live costmap, correct transforms, collision checking, and a local controller.

For a Leo Rover operating indoors, a typical pipeline is: LiDAR or depth sensing, SLAM or map-based localisation, Nav2 costmaps, an A*-based global planner, and a local controller that produces differential-drive velocity commands. The resulting route should be checked against the robot footprint and inflation radius rather than treated as a centre-point trajectory.

Raph Rover can use the same ROS 2 planning architecture where a larger payload capacity is required, for example when carrying a higher-performance compute unit, a larger LiDAR, or multiple perception sensors. Its footprint, motion limits, sensor placement, and stopping distance must be represented in the costmap and controller configuration. A path valid for Leo Rover is not automatically collision-free or dynamically appropriate for Raph Rover.

Limitations and trade-offs

A* plans over the information available at planning time. It cannot predict moving people, changing terrain, wheel slip, or sensor blind spots. A local planner or controller must react to obstacles that appear after the global path has been generated.

Standard grid-based A* also does not inherently model differential-drive turning constraints, reverse motion penalties, or terrain traversability. For applications requiring orientation-aware planning, Nav2 hybrid-A* variants or motion-model-aware planners may be more appropriate than a basic 2D grid search.

Normative references and technical sources

The following primary documentation defines the ROS interfaces and conventions most relevant to A* integration on ROS 2 mobile robots:

See also