Heuristic Function

An admissible heuristic never overestimates the true cost to reach the goal from any given node. This is the fundamental property required for A* search to guarantee an optimal solution. Formally, for all nodes n, h(n) ≤ h*(n), where h*(n) is the true optimal cost to the goal.

• Example: In a grid-based pathfinding problem, the straight-line Euclidean distance is an admissible heuristic for the shortest path, as it represents the shortest possible distance (a straight line) and thus never overestimates the actual path cost, which must navigate around obstacles.

A consistent heuristic satisfies the triangle inequality. For every node n and its successor n' generated with cost c(n, n'), the heuristic estimate must obey: h(n) ≤ c(n, n') + h(n'). This implies that the total estimated cost f(n) = g(n) + h(n) is non-decreasing along any path.

• Key Consequence: Consistency is a stronger condition than admissibility. All consistent heuristics are admissible, but not all admissible heuristics are consistent. Consistency ensures A* finds an optimal path without needing to re-expand nodes, making it more efficient.

Given two admissible heuristics h1 and h2, h1 dominates h2 if, for all nodes n, h1(n) ≥ h2(n). A dominating heuristic provides a tighter (higher) estimate of the true cost, which is still admissible as long as it doesn't overestimate.

• Impact on Search: A dominating heuristic is more informed. It reduces the size of the search space that A* must explore because it increases the f-cost of more nodes, pruning them from consideration earlier. This leads to faster search times while maintaining optimality.

A heuristic must be computationally inexpensive to evaluate. The benefit of reducing the number of node expansions can be negated if calculating h(n) is overly complex. The ideal heuristic provides a strong guiding estimate with minimal computational overhead.

• Trade-off: There is often a direct trade-off between the informedness of a heuristic (how close it is to the true cost) and the time required to compute it. For real-time systems like robotic pathfinding, a simple, fast heuristic (e.g., Manhattan distance) is often preferred over a more accurate but slower one.

Effective heuristics are derived from a relaxed model of the original problem. By removing constraints, you create a simpler problem whose exact solution cost can be used as an admissible heuristic for the harder problem.

• Common Relaxation Techniques:
  • Ignore constraints: For the 8-puzzle, a heuristic that ignores tile interaction (Misplaced Tiles) or ignores movement blocking (Manhattan Distance).
  • Solve a subproblem: Use the cost of solving part of the problem.
  • Use a pattern database: Precompute exact costs for subsets of the state space.

The properties of the heuristic directly determine the guarantees of the search algorithm.

• Admissibility + A = Optimality*: Guarantees the first solution found is optimal.
• Consistency + A = Efficiency*: Guarantees optimality and that states are expanded at most once.
• Non-admissible Heuristics: Algorithms like weighted A* use a heuristic that may overestimate (w * h(n), where w > 1). This sacrifices optimality guarantees for dramatic improvements in search speed, finding a potentially suboptimal solution much faster—a critical trade-off in real-time fleet orchestration.

The Manhattan distance (or L1 distance) is a common heuristic for grid-based pathfinding, such as in warehouse navigation. It calculates the sum of the absolute differences in the x and y coordinates between the current node and the goal: h(n) = |x₁ - x₂| + |y₁ - y₂|. This is admissible for movement restricted to four directions (up, down, left, right), as it never overestimates the true cost. It is computationally inexpensive and often used in A search* for robotic navigation on factory floors.

The Euclidean distance (or L2 distance) is the straight-line distance between two points: h(n) = √((x₁ - x₂)² + (y₁ - y₂)²). It is the ideal heuristic for agents that can move freely in any direction, as it provides the shortest possible path estimate. This heuristic is admissible and often more informed than Manhattan distance in continuous spaces, leading to fewer node expansions in algorithms like A*. It's fundamental for drone routing or any system with omnidirectional movement.

Chebyshev distance (or L∞ distance) is defined as the maximum of the absolute differences along any coordinate dimension: h(n) = max(|x₁ - x₂|, |y₁ - y₂|). This is the appropriate heuristic for movement that allows eight directions (including diagonals) on a grid, where moving diagonally costs the same as moving orthogonally (often a cost of 1). It is admissible for this movement model and ensures the heuristic never overestimates the cost to reach the goal.

The null heuristic sets h(n) = 0 for all nodes. This reduces the A* search algorithm to Dijkstra's algorithm, which explores all nodes equally in all directions without a goal-directed bias. While it guarantees an optimal path, it is computationally expensive as it explores a much larger search space. It's used when no suitable problem-specific heuristic is available or when the search must be uninformed to guarantee correctness in complex cost landscapes.

In priority-based routing and scheduling, a deadline can serve as a temporal heuristic. For a task with a deadline D, a simple heuristic is the remaining time: h(t) = D - current_time. This guides schedulers like Earliest Deadline First (EDF). More sophisticated versions may estimate the minimum travel time to a goal location and compare it to the time remaining, helping an algorithm prioritize agents or tasks that are temporally critical. This is central to dynamic replanning under time-window constraints.

A powerful method for deriving admissible heuristics is to solve a relaxed version of the original problem, where some constraints are removed. The cost of the solution to the easier problem becomes the heuristic estimate for the hard one.

• Example: For the 8-puzzle, a relaxed problem might allow tiles to move to any adjacent square (ignoring whether it's occupied). The heuristic h(n) becomes the sum of each tile's Manhattan distance to its goal position. This sum of Manhattan distances is a well-known, effective, and admissible heuristic for A* search in sliding puzzle problems.

A* is a best-first graph traversal and pathfinding algorithm that guarantees an optimal solution by combining Dijkstra's algorithm (actual cost from start) with a heuristic function (estimated cost to goal). It maintains two values for each node:

• g(n): The exact cost of the path from the start node to node n.
• h(n): The heuristic estimate from node n to the goal. The algorithm expands nodes with the lowest total cost f(n) = g(n) + h(n). For optimality, the heuristic must be admissible (never overestimates) and consistent.

An admissible heuristic is one that never overestimates the true cost to reach the goal state. This property is critical for the optimality of algorithms like A* search. Common examples in pathfinding include:

• Euclidean distance (straight-line distance) in a plane.
• Manhattan distance (sum of absolute differences) on a grid with 4-directional movement. If h*(n) is the true optimal cost from n to the goal, admissibility requires h(n) ≤ h*(n) for all nodes n. An inadmissible heuristic may find a path faster but cannot guarantee it is the shortest.

A cost function is a mathematical function that quantifies the penalty or expense of a particular path, action, or solution state. In routing, it is the objective an algorithm aims to minimize. Key components include:

• Travel distance (e.g., meters).
• Time elapsed (e.g., seconds).
• Energy consumption (e.g., watt-hours).
• Monetary cost (e.g., fuel). A heuristic function h(n) is an estimate of the remaining cost from a node n to the goal, as defined by the true cost function the algorithm is optimizing.

Greedy Best-First Search is a search algorithm that expands the node deemed closest to the goal based solely on the heuristic function h(n). Unlike A*, it ignores the cost incurred so far (g(n)). Characteristics:

• Not optimal: It may find a suboptimal path because it pursues the heuristic target myopically.
• Not complete: It can get stuck in loops if no cycle detection is used.
• Often faster: It typically explores fewer nodes than A* to find a solution, but not necessarily the best one. It demonstrates the power and the limitation of relying purely on a heuristic.

A priority queue is an abstract data type essential for implementing heuristic search algorithms. It stores elements (e.g., graph nodes) each associated with a priority value. The element with the highest (or lowest) priority is served first. In A* search:

• Nodes are inserted with priority f(n) = g(n) + h(n).
• The queue efficiently returns the node with the lowest f(n) for expansion. Common implementations include binary heaps and Fibonacci heaps, which provide efficient O(log n) insertion and extraction of the minimum element.

Dijkstra's algorithm is a foundational graph search algorithm that finds the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights. It can be viewed as a special case of A* search where the heuristic function h(n) = 0 for all nodes n. Key properties:

• Guarantees optimality for the defined cost metric.
• Blind search: It expands nodes in a wavefront based solely on accumulated cost g(n), without guidance toward the goal.
• Less efficient for point-to-point search compared to A* with a good heuristic, as it explores more nodes uniformly in all directions.