Informed Searching

Uses domain-specific hints about the location of goals. The hint is given by a heuristic function.

Heuristic Function

Estimates the cost of the cheapest path from the state at node $n$ to a goal state. Denoted by $h(n)$. $$

Used to guide the search algorithm towards promising paths, making search more efficient than uninformed methods.

Examples:

• In route finding: Straight-line distance to destination
• In 8-puzzle: Number of misplaced tiles or Manhattan distance

Admissible

When the heuristic is always equal to or lesser than the actual lowest cost.

Consistent

Aka. monotonic. When the estimated cost along any path is never decreasing. $h$ is consistent iff for any $n, n'$:

$$h(n) \leq c(n, a, n') + h(n')$$

Here:

• $n'$ is the successor node of $n$ after applying action $a$
• $h(n)$ is the heuristic of a node $n$
• $h(n')$ is the heuristic of a node $n'$
• $c(n, a, n')$ is the cost of the action $a$ from node $n$ to node $n'$.

Note

Every consistent heuristic function is admissible.

Algorithms

Best-First Search

A general search approach that prioritizes nodes based on an evaluation function. At each step, it selects the most promising node from the frontier according to some measure.

The frontier is typically implemented as a priority queue, ordered by the evaluation function value.

Evaluation Function

Denoted by $f(n)$. Used to determine which nodes to expand next. Assigns a numeric value to each node representing its promise or desirability. Exact details depends on the best-first search variant.

Greedy Best-First Search

$f(n) = h(n)$. Does not backtrack. Not complete. Might cause false-negatives if the heuristic is misleading. Might get on an infinite loop if full cycle checking is not done. Not optimal as it doesn’t take actual path cost into account.

def greedy_best_first_search(start, goal_test, successors, heuristic):
    """
    Args:
        start: The initial state.
        goal_test: Function(state) -> bool, returns True if state is a goal.
        successors: Function(state) -> list of (action, next_state).
        heuristic: Function(state) -> estimated cost to goal.

    Returns:
        path: List of (action, state) from start to goal, or None if no path found.
    """
    frontier = PriorityQueue()
    frontier.put((heuristic(start), start, []))
    explored = set()

    while not frontier.empty():
        h, state, path = frontier.get()

        if goal_test(state):
            return path + [(None, state)]

        if state in explored:
            continue
        explored.add(state)

        for action, next_state in successors(state):
            if next_state not in explored:
                frontier.put((heuristic(next_state), next_state, path + [(action, state)]))

    return None

A* Search

Most widely used form of best-first search. Uses an evaluation function $f(n) = g(n) + h(n)$ where:

• $g(n)$ - cost so far to reach node $n$ from the start state
• $h(n)$ - estimated cost from $n$ to the goal

Explores the node that appears to be closest to the goal while considering the actual cost. Combines the benefits of Dijkstra’s algorithm (which considers path cost) and greedy best-first search (which uses a heuristic). It expands nodes in order of their $f(n)$ values, maintaining completeness while being more efficient than uniform-cost search.

Complete iff search space is finite.

Optimal iff search space is finite and $h(n)$ is admissible. If $h(n)$ overestimates, optimal path might be ignored and a suboptimal path might be prioritized. If $h(n)$ is admissible, the issue is avoided.

A* becomes even more efficient if $h(n)$ is also consistent, as it never needs to reopen closed nodes.

import heapq

def a_star_search(start, goal_test, successors, heuristic):
    """
    Generic A* search algorithm.

    Args:
        start: The initial state.
        goal_test: Function(state) -> bool, returns True if state is a goal.
        successors: Function(state) -> list of (action, next_state, cost).
        heuristic: Function(state) -> estimated cost to goal.

    Returns:
        path: List of (action, state) from start to goal, or None if no path found.
    """
    frontier = []
    heapq.heappush(frontier, (heuristic(start), 0, start, []))
    explored = {}

    while frontier:
        f, g, state, path = heapq.heappop(frontier)

        if goal_test(state):
            return path + [(None, state)]

        if state in explored and explored[state] <= g:
            continue
        explored[state] = g

        for action, next_state, cost in successors(state):
            new_g = g + cost
            new_f = new_g + heuristic(next_state)
            heapq.heappush(frontier, (new_f, new_g, next_state, path + [(action, state)]))

    return None

Bidirectional A* Search

Optimized A* search algorithm. Runs 2 simultaneous searches from initial and goal states. Stops when the frontiers meet. Each search uses their own heuristic functions. One heuristic function cannot be defined from the another.

Beam Search

A variant of best-first search. Uses heuristic function alone. Similar to BFS. Puts a limit (beam width) on the size of the frontier. Not complete, and not optimal. Because some nodes are discarded.

Comparison

Algorithm	Completeness	Optimality	Time Complexity	Space Complexity
Greedy Best-First	No	No	$O(b^m)$	$O(b^m)$
A*	Yes*	Yes**	$O(b^d)$	$O(b^d)$
Bidirectional A*	Yes*	Yes**	$O(b^(d/2))$	$O(b^(d/2))$
Beam Search	No	No	$O(bk)$	$O(k)$

* Iff the graph is finite. ** Iff $h(n)$ is admissible.

Here:

• $b$ - branching factor
• $d$ - depth of the shallowest goal
• $m$ - maximum depth of the search tree
• $k$ - beam width

Performance of Heuristic Search

Depends on the quality of the heuristic function. A good heuristic can significantly reduce the search space and time. A poor heuristic can lead to inefficient search.

A good heuristic function can be constructed by:

• Relaxing the problem definition
• Storing precomputed solution costs for subproblems in a pattern database
• Defining landmarks
• Learning from the experience with the problem class

Heuristics from Relaxed Problems

A relaxed problem is a problem with fewer restrictions. The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.

Heuristics from Pattern Databases

Solution cost of a subproblem can also be used as an admissible heuristic for the original problem.

Pattern database stores these exact solution costs for every possible subproblem instance.