02 Search Algorithms

Slides

This module is also available in the following versions

State Model for Classical Planning

State Model: Classical Planning

State Model \(\mathcal{S}(P)\):

  • finite and discrete state space \(S\)
  • a known initial state \(s_{0} \in S\)
  • a set \(\textstyle S_G \subseteq S\) of goal states
  • actions \(A(s) \subseteq A\) applicable in each \(s \in S\)
  • a deterministic transition function \(s' = f(a, s)\) for \(a \in A(s)\)
  • positive action costs \(c(a, s)\)

A solution is a sequence of applicable actions that maps \(s_0\) into \(S_G\), and it is optimal if it minimizes sum of action costs (e.g., # of steps)

Different models and controllers obtained by relaxing assumptions in blue …

Solving the State Model: Path-finding in graphs

Search algorithms for planning exploit the correspondence between classical state models \(\mathcal{S}(P)\) and directed graphs:

  • The nodes of the graph represent the states \(s\) in the model
  • The edges \((s, s')\) capture corresponding transitions in the model with the same cost

In the planning as heuristic search formulation, the problem \(P\) is solved by path-finding algorithms over the graph associated with model \(\mathcal{S}(P)\)

Classification of Search Algorithms

Blind search vs. heuristic (or informed) search:

  • Blind search algorithms: Only use the basic ingredients for general search algorithms.
    • e.g., Depth First Search (DFS),
    • Breadth-first Search (BrFS),
    • Uniform Cost (Dijkstra), and
    • Iterative Deepening (ID)
  • Heuristic search algorithms: Additionally use heuristic functions which estimate the distance (or remaining cost) to the goal.
    • e.g., A\(^*\), IDA\(^*\), Hill Climbing, Best First, WA\(^*\), DFS B&B, LRTA\(^*\), …

Classification of Search Algorithms (continued)

Systematic search vs. local search:

  • Systematic search algorithms: Considers a large number of search nodes simultaneously; maintains an explicit frontier or open list of states still to explore, and often also a closed list of visited states.

  • Local search algorithms: Local search usually keeps just one current state (or a small number), and repeatedly moves to a neighbouring state that seems better according to an evaluation function.

  • This is not a black-and-white distinction; there are crossbreeds (e.g., enforced hill-climbing).

What works where in planning?

Blind search vs. heuristic search:

  • For satisficing planning, heuristic search vastly outperforms blind algorithms pretty much everywhere.
  • For optimal planning, heuristic search also is better (but the difference is less pronounced).

Systematic search vs. local search:

  • For satisficing planning, there are successful instances of each.
  • For optimal planning, systematic algorithms are required.

We cover a subset of search algorithms most successful in planning. Only some blind search algorithms are covered (refer to Russel & Norvig Chapters 3 and 4).

Search terminology

  • Search node \(n\): Contains a state reached by the search, plus information about how it was reached.
  • Path cost \(g(n)\): The cost of the path reaching \(n\).
  • Optimal cost \(g^*\): The cost of an optimal solution path. For a state \(s\), \(g^*(s)\) is the cost of a cheapest path reaching \(s\).
  • Node expansion: Generating all successors of a node, by applying all actions applicable to the node’s state \(s\). Afterwards, the state \(s\) itself is also said to be expanded.
  • Search strategy: Method for deciding which node is expanded next.
  • Open list: Set of all nodes that currently are candidates for expansion. Also called frontier.
  • Closed list: Set of all states that were already expanded. Used only in graph search, not in tree search (up next). Also called explored set.

World States versus Search States

Search Space for Classical Search

A classical search space is defined by the following three operations:

  • \(\text{start}()\): Generate the start (search) state.
  • \(\text{is-goal}(s)\): Test whether a given search state is a target (goal) state.
  • \(\text{succ}(s)\): Generates the successor states \((a, s')\) of search state \(s\), along with the actions through which they are reached.

Search states \(\neq\) world states?

  • Progression (forward reasoning from initial state)?:
  • Regression (backwards reasoning from goal)?::

  • We consider progression in the entire course, unless explicitly stated otherwise.

  • We use ‘\(s\)’ to denote world and search states interchangeably

Search States versus Search Nodes

  • Search states \(s\): are states (vertices) of the search space.
  • Search nodes \(\sigma\): are search states, plus information on where/when/how they are encountered during search (i.e. bookkeeping information).
What is in a search node?

Different search algorithms store different information in a search node \(\sigma\), but typical information includes:

  • \(\text{state}(\sigma)\): Associated search state.
  • \(\text{parent}(\sigma)\): Pointer to search node from which \(\sigma\) is reached.
  • \(\text{action}(\sigma)\): An action leading from \(\text{state}(\text{parent}(\sigma))\) to \(\text{state}(\sigma)\).
  • \(g(\sigma)\): Cost of \(\sigma\) (cost of path from the root node to \(\sigma\)).

For the root node, \(\text{parent}(\sigma)\) and \(\text{action}(\sigma)\) are undefined.

Criteria for Evaluating Search Strategies

Guarantees:

  • Completeness: Is the strategy guaranteed to find a solution when there is one?
  • Optimality: Are the returned solutions guaranteed to be optimal?

Computational Complexity:

  • Time Complexity: How long does it take to find a solution? (Measured in generated states.)
  • Space Complexity: How much memory does the search require? (Measured in states.)

Typical state space features governing complexity:

  • Branching factor \(b\): How many successors does each state have?
  • Goal depth \(d\): The number of actions required to reach the shallowest goal state.

Heuristic Functions

Heuristic Search Algorithms

Heuristic search algorithms are the most common and overall most successful algorithms for classical planning.

The Origins of Heuristic Search: Shakey, 1972

Heuristic search algorithms: Systematic

  • Greedy best-first search.

    • One of the three most popular algorithms in satisficing planning

  • Weighted A*.

    • One of the three most popular algorithms in satisficing planning

  • A*.

    • Most popular algorithm in optimal planning (rarely ever used for satisficing planning)

  • IDA*, depth-first branch-and-bound search, breadth-first heuristic search, …

Heuristic search algorithms: Local

  • Hill-climbing.

  • Enforced hill-climbing.

    • One of the three most popular algorithms in satisficing planning

  • Other algorithms include beam search, tabu search, genetic algorithms, simulated annealing, etc.

Heuristic Search: Basic Idea

  • A heuristic function \(h\) estimates the cost of an optimal path to the goal

  • Search gives a preference to explore states with small \(h\).

Heuristic Functions

Heuristic searches require a heuristic function to estimate remaining cost

Definition: Heuristic Function

Let \(\Pi\) be a planning problem with state space \(\Theta_\Pi\).

  • A heuristic function, or heuristic, for \(\Pi\) is a function \(h : S \mapsto \mathbb{R}^+_0 \cup \{\infty\}\)

  • Its value \(h(s)\) for state \(s\) is referred to as the state’s heuristic value, or just \(h\)-value

Definition: Remaining Cost, \(h^{*}\)

Let \(\Pi\) be a planning problem with state space \(\Theta_\Pi\).

  • For a state \(s \in S\), the state’s remaining cost is the cost of an optimal plan for \({\color{blue}s}\), or \({\color{blue}\infty}\) if there exists no plan for \(s\).

  • The perfect heuristic for \(\Pi\), written \(\color{blue}{h^{*}}\), assigns every \(s \in S\) its remaining cost as the heuristic value.

Heuristic Functions: Discussion

What does it mean to estimate remaining cost?

  • For many heuristic search algorithms, \(h\) does not need to have any properties for the algorithm to work (meaning being correct and complete).

    • \(h\) is any function from states to numbers…

  • Search performance depends crucially on how well \(h\) reflects \(h^{*}\)

    • This is informally called the informedness or quality of \(h\).

  • For some search algorithms, such as \(A^{*}\), the relationship between formal quality properties of \(h\) and search efficiency can be proven (number of expanded nodes).

  • For other search algorithms, “it works well in practice” is often as good an analysis as one gets.

We will analyse in a later Module detail approximations to one particularly important heuristic function in planning: \(h^+\).

Heuristic Functions: Discussion (continued)

  • Search performance depends crucially on the informedness of \(h\)

Are there other properties of \(h\) that search performance crucially depends on?

What about edge cases?

Important Properties of Heuristic Functions

Definition: Heuristic Function Properties

Let \(\Pi\) be a planning problem with state space \(\Theta_\Pi=(S,L,c,T,I,S^G)\), and let \(h\) be a heuristic for \(\Pi\).

  • \(h\) is safe if for all \(s \in S, h(s) = \infty\ \Longrightarrow\ h^*(s) = \infty\)
  • \(h\) is goal-aware if \(h(s)=0\) for all goal states \(s\in S^G\)
  • \(h\) is admissible if \(h(s)\le h^*(s)\) for all \(s\in S\)
  • \(h\) is consistent if \(h(s)\le h(s') + c(a)\) for all transitions \(s \xrightarrow{a} s'\)
  • Note that \(h^*(s)\) is the perfect heuristic for state \(s\) (optimal cost-to-go), and \(h(s)\) is the value actually returned by the heuristic function.
  • \(T\) is the transition relation which specifies which successor states can be reached from which states under which action and \(L\) are the action or operator labels.

Relationships between properties of Heuristic Functions

What are the relationship between these properties?

  • safety (never discard a state that could lead to a valid solution)
  • goal-awareness (assigns \(0\) to every goal state)
  • admissibility (never over estimates true cost to a goal)
  • consistency (recognises triangle inequality over transitions)

Local Search Algorithms

Hill-Climbing

Hill-Climbing

\(\sigma := make\text{-}root\text{-}node(init())\)
forever:
  if \(is\text{-}goal(state(\sigma))\):
    return \(extract\text{-}solution(\sigma)\)
  \(\Sigma' := \{\, make\text{-}node(\sigma,a,s') \mid (a,s') \in {\color{blue}succ}(state(\sigma)) \,\}\)
  \(\sigma :=\) choose an element of \(\Sigma'\) minimising \(h\)  \({\color{blue}\text{/* random tie breaking */}}\)

  • Makes sense only if \(h(s) > 0\) for \(s \notin S^G\) (i.e. all non-goal states have a positive heuristic)

Is this complete or optimal?

Enforced Hill-Climbing

Enforced Hill-Climbing: Procedure \(improve\)

def \(improve(\sigma_0):\)
  \(queue :=\) new FIFO queue
  \(queue.\text{push-back}(\sigma_0)\)
  \(closed := \emptyset\)
  while not \(queue.\text{empty}()\):
    \(\sigma := queue.\text{pop-front}()\)
    if \(state(\sigma) \notin closed\):
      \(closed := closed \cup \{state(\sigma)\}\)
      if \(h(state(\sigma)) < h(state(\sigma_0))\): return \(\sigma\)    /* If better state is found return it */
      for each \((a,s') \in {\color{blue}succ}(state(\sigma))\):
        \(\sigma' := \text{make-node}(\sigma,a,s')\)
        \(queue.\text{push-back}(\sigma')\)
  fail

Is essentially breadth-first search for a state with strictly smaller \(h\)-value

  • Keep hill climbing, but when stuck, systematically search outward until you find an improvement (less easily gets stuck)
Enforced Hill-Climbing

\(\sigma := make\text{-}root\text{-}node(init())\)
while not \(is\text{-}goal(state(\sigma))\):
  \(\sigma := improve(\sigma)\)
return \(extract\text{-}solution(\sigma)\)

Is enforced hill-climbing optimal?

Is enforced hill-climbing complete?

Properties of Search Algorithms

DFS BrFS ID \(A^*\) HC IDA* IW
Complete No Yes Yes Yes No Yes No
Optimal No Yes\(^*\) Yes Yes No Yes No
Time \(\infty\) \(b^d\) \(b^d\) \(b^d\) \(\infty\) \(b^d\) \(b \cdot n^k\)
Space \(b \cdot d\) \(b^d\) \(b \cdot d\) \(b^d\) \(b\) \(b \cdot d\) \(n^k\)
  • Parameters: \(d\) is solution depth; \(b\) is branching factor (number of applicable actions)
  • Breadth-first search (BrFS) is optimal when costs are uniform.
  • \(A^*\)/\(IDA^*\) are optimal when \(h\) is admissible, i.e., \(h \le h^*\)
  • For IW, \(n\) is the number of features and \(k\) is the width parameter.

Conclusion

Questions

Question (Revisited)

If we set \(h(s) := 0\) for all \(s\), what does \(A^{*}\) become?

(A) Breadth-first search

(C) Uniform-cost search

(B) Depth-first search

(D) Depth-limited search

Question

If we set \(h(s) := 0\) for all \(s\), what does greedy best-first search become?

(A) Breadth-first search

(C) Uniform-cost search

(B) Depth-first search

(D) A), B) and C)

Question

Is informed search always better than blind search?

(A): Yes.

(B): No.

Summary

Distinguish: World states, search states, search nodes.

  • World state: Situation in the world modelled by the planning problem.

  • Search state: Subproblem remaining to be solved.

    • In progression, world states and search states are identical.
    • In regression, search states are sub-goals describing sets of world states.

  • Search node: Search state + information on “how we got there”.

Search algorithms mainly differ in order of node expansion:

  • Blind vs. heuristic (or informed) search.
  • Systematic vs. local search.

Search strategies differ in the order in which they expand search nodes, and in the way they use duplicate elimination.

Criteria for evaluating them include completeness, optimality, time complexity, and space complexity.

  • Breadth-first search is optimal but uses exponential space;

  • Depth-first search uses linear space but is not optimal;

  • Iterative deepening search combines the virtues of both.

Heuristic Functions are estimators for remaining cost.

  • Usually, the more informed the search is, the better the performance.
  • Desiderata includes safety, goal-awareness, admissibility, and consistency.
  • The ideal is a perfect heuristic \(h^*\).

Heuristic Search Algorithms:

  • Most common algorithms for satisficing planning are:
    • Greedy best-first search
    • Weighted \(A^*\)
    • Enforced hill-climbing
  • Most common algorithm for optimal planning are:
    • \(A^*\)

Additional Reading

  • Artificial Intelligence: A Modern Approach, Russell and Norvig (Third Edition)
    • An overview of various search algorithms, including blind searches as well as greedy best-first search and \(A^*\).
    • See Chapter 3: “Solving Problems by Searching” and the first half of Chapter 4: “Beyond Classical Search”.
  • Search tutorial in the context of path-finding: http://www.redblobgames.com/pathfinding/a-star/introduction.html