A* Search Algorithm

An admissible heuristic is a condition where the estimated cost from any node n to the goal is never greater than the true cost. Formally, h(n) ≤ h*(n) for all n, where h*(n) is the true optimal cost-to-go. This property is the absolute requirement for A* to guarantee an optimal path. If a heuristic overestimates the cost, A* may find a suboptimal solution. In robotics, the Euclidean distance to the goal is a classic admissible heuristic for a robot moving in free space.

A consistent (or monotone) heuristic satisfies the triangle inequality: h(n) ≤ c(n, n') + h(n') for every successor node n' of n, where c(n, n') is the step cost. Consistency is a stronger condition than admissibility. It guarantees that:

• The f(n) cost (total estimated cost) is non-decreasing along any path.
• The first time A* expands a node, it has found the optimal path to it.
• The algorithm does not need to re-open nodes from the closed set, simplifying implementation. Most well-designed heuristics in robotics, like Euclidean distance, are consistent.

Given an admissible heuristic, A* is guaranteed to find the globally optimal path from the start to the goal, provided a path exists. This is its most critical property for motion planning, where fuel, time, or wear must be minimized. The proof relies on the fact that A* expands nodes in order of their f(n) score. Since f(n) for the goal node is its true cost when using an admissible heuristic, any path with a higher cost will have a higher f score and be expanded later (or not at all).

A* is complete on finite graphs with non-negative edge costs. This means it will always find a solution if one exists and will correctly terminate with failure if no path exists. Completeness is essential for reliable robotic systems; the planner must not silently fail. In infinite or continuous state spaces (like robot configuration space), basic A* is not directly applicable. However, when paired with a suitable discretization (e.g., a grid) or a sampling-based graph construction method, the overall planning approach retains this completeness property.

A*'s decision-making is governed by the evaluation function f(n) = g(n) + h(n).

• g(n) is the actual cost from the start node to node n. It represents the known, incurred cost.
• h(n) is the heuristic estimate of the cost from n to the goal. It represents the informed "guess" about the remaining cost.
• f(n) is the estimated total cost of the cheapest solution through n. The Open Set (frontier) is always ordered by f(n). This elegant combination of known past cost and estimated future cost is what balances thoroughness and directed search speed.

The accuracy of the heuristic h(n) directly controls A*'s performance. The closer h(n) is to the true cost h*(n) (without overestimating), the fewer nodes A* will expand. At the extremes:

• If h(n) = 0 for all n, A* degenerates into Dijkstra's Algorithm, which is optimal but expands nodes in all directions equally (slow).
• If h(n) = h*(n) (perfect heuristic), A* expands only the nodes on the optimal path, achieving ideal efficiency.
• In practice, a well-designed heuristic like straight-line distance provides a strong, admissible guide, making A* vastly more efficient than Dijkstra's for geometric pathfinding.

Dijkstra's algorithm is the foundational graph search method that guarantees the shortest path in a weighted graph with non-negative edges. It operates by systematically exploring nodes in order of their distance from the start.

• Key Difference from A:* It uses no heuristic; it explores uniformly in all directions.
• Computational Cost: It is often slower than A* for point-to-point queries as it explores a larger portion of the graph.
• Use Case: Optimal when no heuristic information is available or when finding the shortest path to all nodes from a single source.

Configuration Space is the mathematical abstraction where every possible state (position, orientation, joint angles) of a robot is mapped to a single point. Obstacles in the physical world become forbidden regions in this space.

• Purpose: Transforms the complex geometric problem of moving a physical shape into the simpler problem of finding a path for a point.
• Dimensionality: Equal to the number of degrees of freedom (DOF) of the robot (e.g., 3 for a ground robot, 6+ for a manipulator).
• A's Domain:* A* searches for a path through the free regions of this C-Space graph.

Rapidly-exploring Random Tree (RRT) is a sampling-based algorithm designed for high-dimensional, non-convex spaces. It grows a tree by randomly sampling the C-Space and extending the tree toward these samples.

• Comparison to A:* RRT is probabilistically complete but not optimal; A* is optimal but requires a discrete graph.
• Strength: Excels in complex, continuous spaces where constructing a full graph for A* is infeasible.
• Common Variant: RRT* converges towards an optimal solution given sufficient time.

Probabilistic Roadmap (PRM) is a sampling-based method that builds a graph (roadmap) of collision-free configurations in two phases: a learning phase and a query phase.

• Learning Phase: Randomly samples points in C-Space, connects nearby ones if a local path is collision-free.
• Query Phase: Uses a graph search like A* to find a path from start to goal on the constructed roadmap.
• Use Case: Ideal for multiple queries in a static environment, as the roadmap is built once and reused.

The heuristic function, denoted h(n), estimates the cost from the current node n to the goal. It is the defining component that makes A* smarter than Dijkstra's algorithm.

• Admissibility: Must never overestimate the true cost to the goal (required for optimality).
• Common Heuristics: Euclidean distance (for planar navigation) or Manhattan distance (for grid worlds).
• Effect: A well-designed heuristic (closer to the true cost without overestimating) dramatically reduces the number of nodes A* must explore.