A* Search

The admissibility of the heuristic function h(n) is the cornerstone of A*'s optimality guarantee. An admissible heuristic never overestimates the true cost to reach the goal from any node n. This property ensures that when A* selects a goal node for expansion, the path cost g(n) is guaranteed to be the minimum possible. If h(n) is admissible, A* is optimally efficient, meaning no other optimal algorithm that uses the same heuristic expands fewer nodes. A common example is using straight-line Euclidean distance as h(n) for pathfinding on a grid; it's always less than or equal to the actual path distance around obstacles.

A stronger property than admissibility is consistency (or monotonicity). A heuristic is consistent if for every node n and its successor n' generated by action a, the estimated cost satisfies the triangle inequality: h(n) ≤ cost(n, a, n') + h(n'). This implies that f(n) (the total estimated cost g(n) + h(n)) is non-decreasing along any path. The key practical implications are:

• Consistent heuristics guarantee A* finds optimal paths without needing to re-open nodes in the closed set.
• The algorithm's behavior is more predictable and efficient.
• All consistent heuristics are admissible, but not all admissible heuristics are consistent.

A*'s decision-making is driven by the evaluation function f(n) = g(n) + h(n), which estimates the total cost of the cheapest solution path passing through node n.

• g(n) (Cost-to-Come): The exact, known cost from the start node to n. It represents the path already taken.
• h(n) (Heuristic Cost-to-Go): An estimate of the cheapest cost from n to the goal. This is the "informed" part of the search that guides it toward the goal.
• The algorithm always expands the node in the open set with the lowest f(n) value, balancing the certainty of the past (g(n)) with an informed estimate of the future (h(n)).

A* is complete on finite graphs with a positive edge cost function and a finite branching factor, meaning it will always find a solution if one exists. Its time and space complexity are a function of the heuristic's accuracy. In the worst case, where the heuristic provides no guidance (h(n) = 0), A* degenerates to uniform-cost search (Dijkstra's algorithm), with an exponential time and space complexity of O(b^d), where b is the branching factor and d is the solution depth. With a perfect heuristic (h(n) equals the exact cost-to-go), complexity reduces to O(d), as the search proceeds directly to the goal. In practice, a good heuristic dramatically prunes the search space.

Standard A* finds an optimal path but can be slow in very large spaces. Weighted A (WA)** introduces a trade-off between optimality and speed by using the evaluation function f(n) = g(n) + w * h(n), where w > 1. This inflates the heuristic, making the search more greedy and goal-directed. While WA* does not guarantee optimality, it often finds a satisfactory solution much faster and provides an ε-optimal guarantee (solution cost ≤ ε * optimal cost, where ε = w). This is critical in real-time applications like video game AI or robotics, where a good path now is better than an optimal path too late.

Within Corrective Action Planning, A* is a foundational algorithm for an agent to compute an optimal sequence of corrective steps. The state space is defined by the agent's internal and external world model after an error is detected. Each action (e.g., "re-query API," "reformat data," "rollback transaction") has an associated cost (g(n)), often representing computational expense or risk. The heuristic h(n) estimates the remaining "effort" to reach a validated, correct state. By searching this space, the agent can find the minimal-cost recovery plan, embodying the principle of recursive error correction through optimal re-planning.

A heuristic function, denoted h(n), provides an admissible (never overestimating) estimate of the cost from a given node n to the goal. In A* Search, this estimate is combined with the known cost from the start (g(n)) to prioritize the most promising paths. Common heuristics include:

• Euclidean distance for spatial navigation.
• Manhattan distance for grid-based movement.
• Relaxed problem solutions (e.g., ignoring constraints) for logical planning. The quality of the heuristic directly determines A*'s efficiency; a perfect heuristic (h*(n)) would lead directly to the goal with no unnecessary exploration.

An admissible heuristic is a critical requirement for A* Search to guarantee optimality (finding the shortest path). It must never overestimate the true cost to reach the goal from any node. Formally, for all nodes n, h(n) ≤ h(n)**, where h(n) is the true optimal cost.

Examples:

• For a map, straight-line distance is admissible (air distance ≤ road distance).
• For the 8-puzzle, the number of misplaced tiles is admissible. If a heuristic is inadmissible, A* may find a path that is not the shortest, though it can still be useful for suboptimal, faster planning.

A* Search is both complete and optimal under standard conditions.

• Completeness: Guaranteed to find a solution if one exists, provided the branching factor is finite and step costs are positive.
• Optimality: Guaranteed to find the lowest-cost path, provided the heuristic is admissible. This optimality stems from its evaluation function f(n) = g(n) + h(n), which ensures no promising path is overlooked while avoiding exhaustive search. In graphs, optimality also requires a consistent (monotonic) heuristic to handle revisited nodes correctly.

A* can be implemented in two primary modes, affecting memory and correctness in graphs with cycles:

• Tree Search: Does not track visited states. It can re-explore nodes, leading to infinite loops in graphs, but is simpler. Requires the heuristic to be consistent to remain optimal in such environments.
• Graph Search: Maintains a closed set (or explored set) to avoid revisiting states. This is essential for finite graphs to ensure termination and is the standard implementation for pathfinding on maps. It requires more memory but is generally more efficient and robust.

Dijkstra's Algorithm is a foundational graph search algorithm that finds the shortest path from a source node to all other nodes in a graph with non-negative edge weights. It is a special case of A* Search where the heuristic function h(n) = 0 for all nodes. Consequently, it explores nodes in order of their g(n) (cost from start) alone.

Key Comparison with A:*

• A* is goal-directed and typically faster due to the heuristic.
• Dijkstra's is exhaustive within the cost radius and is used when no suitable heuristic is available or when paths to many goals are needed.

Greedy Best-First Search is an algorithm that expands the node deemed closest to the goal based solely on the heuristic function h(n). It prioritizes nodes with the smallest h(n).

Contrast with A:*

• Greedy: Uses f(n) = h(n). It is generally faster but not optimal and not complete (can get stuck in infinite loops).
• A*: Uses f(n) = g(n) + h(n). It is optimal and complete (with admissible heuristic) but may explore more nodes. Greedy search is useful for quick, approximate solutions where optimality is not critical, often finding a path rapidly but not necessarily the shortest.