Heuristic Search

An admissible heuristic never overestimates the true cost to reach the goal from any given state. This is the critical property that guarantees A* and similar algorithms will find an optimal solution (the shortest path or lowest-cost plan).

• Example: In pathfinding, the straight-line Euclidean distance to the goal is admissible, as it's the shortest possible path, never longer than the actual traversable route.
• Consequence: If a heuristic is admissible, the first time A* expands a goal node, it has found the optimal path.

A consistent heuristic satisfies the triangle inequality. For any node n and its successor n', the estimated cost from n to the goal is not greater than the step cost to n' plus the estimated cost from n' to the goal. Formally: h(n) ≤ c(n, n') + h(n').

• Implication: Consistency is a stronger condition than admissibility. A consistent heuristic is always admissible, but not all admissible heuristics are consistent.
• Key Benefit: When a heuristic is consistent, A* never needs to re-expand nodes, making it more efficient. The f(n) value (total estimated cost) is non-decreasing along any path.

The informedness of a heuristic refers to how accurately it estimates the true cost, while remaining admissible. A more informed heuristic (closer to the true cost without exceeding it) guides the search more directly toward the goal.

• Trade-off: There is often a balance between the computational cost of evaluating the heuristic and its power to prune the search space.
• Dominance: If for all nodes n, h1(n) ≥ h2(n) and both are admissible, then h1 dominates h2. A* using h1 will never expand more nodes than A* using h2 and will usually expand fewer.

Completeness guarantees the algorithm will find a solution if one exists. Optimality guarantees the solution found is the lowest-cost one.

• A with an admissible heuristic* is both complete and optimal, given a finite branching factor and positive step costs.
• Contrast with Greedy Best-First Search: This uses only the heuristic h(n) and is not optimal, as it can be misled by an inaccurate heuristic down a suboptimal path.
• Role of f(n): A* balances the cost-so-far g(n) and the estimated cost-to-go h(n) in its evaluation function f(n) = g(n) + h(n). This balance is what ensures optimality.

Effective heuristics are often derived from a simplified or abstracted model of the planning problem. By relaxing constraints, you can compute costs that are admissible.

• Common Relaxations:
  • Ignore all obstacles: The straight-line distance heuristic.
  • Ignore interaction constraints: In task planning, assuming resources are always available.
  • Ignore kinematics: Planning for a point robot instead of one with complex dynamics.
• Pattern Databases: Precomputed tables of exact solution costs for subproblems (or "patterns") of a larger state space, providing a highly informed, admissible heuristic.

Weighted A* is a variant that trades optimality for computational speed by inflating the heuristic. Its evaluation function is f(n) = g(n) + ε * h(n), where ε > 1 is a weight. This gives the heuristic more influence, making the search more greedy and directing it toward the goal more aggressively. While this can result in a suboptimal solution, the path cost is guaranteed to be no worse than ε times the optimal cost. It is crucial in real-time applications like robotics where a bounded suboptimal plan is acceptable if it can be generated within strict time constraints, such as for replanning in dynamic environments.

Greedy Best-First Search expands the node that appears to be closest to the goal, based solely on the heuristic function h(n). It prioritizes speed and memory efficiency over optimality. While it is often very fast, it can produce poor solutions because it ignores the cost incurred so far (g(n)). It is prone to getting stuck in local minima or following misleading heuristics. This algorithm is useful for quick, approximate planning where solution cost is less critical than search time, or as a component within more complex algorithms like A*, which balances it with the known path cost.

The power of a heuristic search algorithm is dictated by the quality of its heuristic function h(n). Key properties include:

• Admissibility: h(n) never overestimates the true cost to the goal. This is required for A*'s optimality.
• Consistency (Monotonicity): h(n) satisfies h(n) ≤ c(n, n') + h(n') for every successor n' of n. This ensures the f(n) cost is non-decreasing.
• Dominance: A heuristic h1 dominates h2 if h1(n) ≥ h2(n) for all n. A more dominant heuristic expands fewer nodes, making the search more efficient.

Common heuristics include:

• Euclidean distance for navigation in open space.
• Manhattan distance for grid worlds with 4-directional movement.
• Relaxed Problem Heuristics: Derived from a simplified version of the planning problem (e.g., ignoring collision constraints).

In Task and Motion Planning (TAMP), heuristic search operates in a combined state space that includes both discrete symbolic states (e.g., object-in-gripper) and continuous geometric configurations. The heuristic must guide the search through this hybrid space. Common approaches include:

• Abstract Graph Heuristics: Using the cost of a solution to a relaxed task planning problem (e.g., ignoring kinematics) as the heuristic for the full TAMP problem.
• Geometric Heuristics: Estimating the cost of a motion between two configurations, often using simple metrics like Euclidean distance in configuration space.
• Hierarchical Heuristics: Using the cost from a higher-level task graph or behavior tree to guide lower-level motion planning, enabling efficient decomposition of complex problems like dexterous manipulation.

The canonical informed search algorithm that combines uniform-cost search (actual cost from start, g(n)) with greedy best-first search (estimated cost to goal, h(n)). It is optimal and complete when using an admissible heuristic. It is the practical instantiation of heuristic search for pathfinding and planning.

• Key Property: Expands nodes with the lowest f(n) = g(n) + h(n) first.
• Use Case: Foundational for robotic path planning in grid worlds and geometric spaces.

The formal set of all possible configurations or situations a system (e.g., a robot, a game, a planning problem) can be in. Heuristic search algorithms operate by systematically exploring this space.

• Representation: Defined by state variables (e.g., robot joint angles, object positions, inventory).
• Search Graph: States are nodes; possible actions between them are edges.
• Challenge: The space is often astronomically large (combinatorial explosion), making uninformed search intractable.

The algorithmic field of computing a sequence of valid configurations (a path or trajectory) for a robot to move from a start to a goal while avoiding obstacles and satisfying constraints. Heuristic search (e.g., A*) is a primary method for discretized versions of this problem.

• Configuration Space (C-Space): The state space for motion planning, where obstacles become forbidden regions.
• Hierarchy: Often sits below task planning in a hierarchical system; the task planner decides what to do, the motion planner figures out how to move.

The process of breaking a high-level, abstract goal into a structured sequence or hierarchy of simpler, executable subtasks. Heuristic search can be applied to find optimal sequences within the space of possible decompositions.

• Relation to Search: The search space consists of partially decomposed tasks. The heuristic estimates the cost/effort to complete a partially decomposed task.
• Formalisms: Hierarchical Task Networks (HTNs) and Behavior Trees provide structured frameworks for this decomposition.

A class of motion planning algorithms (e.g., RRT, PRM) designed for high-dimensional continuous spaces. Instead of exploring a discrete grid, they probe the configuration space with random samples to build a graph or tree of feasible paths.

• Contrast with Heuristic Search: Does not require an explicit discrete representation or a heuristic function. Excels in complex, continuous spaces where defining a good heuristic is difficult.
• Hybrid Use: Often used in tandem; a heuristic search might plan a coarse discrete path, and a sampling-based planner refines it into a smooth, dynamically-feasible trajectory.

The standardized, formal language used to model classical planning problems for AI. It defines predicates, actions, objects, and an initial and goal state, creating a well-defined state space for planners to search.

• Heuristic Function Source: Modern planners using PDDL (e.g., Fast Downward) derive sophisticated domain-independent heuristics (like the FF heuristic or landmark heuristic) from the logical structure of the PDDL model to guide the search.
• Abstraction: Allows heuristic search to operate on a symbolic representation of the world, which is then mapped to physical motions.