Intelligent Systems Lecture Notes

14 September 2011 • Basic State-Space Search

---

Outline

• General search.
• Uninformed search.
  • Depth-first search.
  • Breadth-first search.
  • Lowest-cost-first search.
• Heuristics and A* searching.

A State-Space Interface

interface Problem 

  abstract class State { }

  Set<State> initialStates()

  Boolean isGoalState(State s)

  Set<State> nextStates(State s)

  double moveCost(State from, State to)

See the code.

A State-Space Search Interface

interface StateSpaceSearch

  interface SolutionPath 
  extends Queue<Problem.State>

  SolutionPath search(Problem problem)

  interface Comparison
    boolean isBetterThan(
      SolutionPath a, SolutionPath b)

  SolutionPath search(
    Problem problem, Comparison c)

See the code.

Simple Search

Problem.State
solve(Problem p)

  states = p.states()

  while !states.empty()
    s = states.pick()
    if p.goalState(s)
      return s

  return null

Simple Search Problems

• Only answers the question “is there a solution?”, not “how is the problem solved?”.
• Doesn’t handle infinite state sets well.
• Doesn’t handle constrained solutions well.
  • Cheapest, fastest, best after no more than five minutes work.
• Wasteful of information, and hard to improve.

Improving Search

• Improving search—improving anything—involves exploiting information.

Graph Search

SolutionPath search(Problem problem)

  Set<Path> pendingPaths = initialPaths(problem)

  while !pendingPaths.isEmpty()
    Path path = pick(pendingPaths)
    for Problem.State neighbor : 
        problem.moveResults(path.lastState())
      Path newPath = path.addStep(neighbor)
      if problem.isGoalState(neighbor)
	return newPath
      pendingPaths.add(newPath)

  return new Path()

• See the code.

Observations

• The search exploits some of the graph structure.
  • Answering the “if solvable” and “solved how” questions.
• The search is nondeterministic.

  Path path = pick(pendingPaths)
  for Problem.State neighbor : 
      problem.moveResults(path.lastState())
  

• The other problems remain.

Graph Optimal Search

SolutionPath search(Problem problem, Comparison c)

  SolutionPath bestSolution = new Path()
  Set<Path> pendingPaths = initialPaths(problem)

  while !pendingPaths.isEmpty()
    Path path = pick(pendingPaths)
    for Problem.State neighbor : 
        problem.moveResults(path.lastState())
      Path newPath = path.addStep(neighbor)
      if    problem.isGoalState(neighbor)
         && c.isBetterThan(newPath, bestSolution)
	bestSolution = newPath
      pendingPaths.add(newPath)

  return bestSolution

• See the code.

Depth-First Search

SolutionPath search(Problem problem)

  Stack<Path> pendingPaths = initialPaths(problem)

  while !pendingPaths.isEmpty()
    Path path = pendingPaths.pop()
    for Problem.State neighbor : 
        problem.moveResults(path.lastState())
      Path newPath = path.addStep(neighbor)
      if problem.isGoalState(neighbor)
	return newPath
      pendingPaths.push(newPath)

  return new Path()

Breadth-First Search

Queue<Problem.State> solve(Problem p)

  paths = 
    Queue(Queue(s | s ∈ p.startStates()))

  while !paths.empty()
    path = paths.get()
    s = path.tail()
    if p.goalState(s)
      return path
    for n in p.nextStates(s)
      paths.put(path.copy().add(n))

  return Queue()

Uninformed Searches

• Depth- and breadth-first searches are relatively uninformed.
  • They use graph information, but not problem information.
• Edge costs are the most commonly exploited problem information.
  • Assuming the edge costs are non-negative.
• Even if not required, finding a minimum-cost solution avoids problems.

Least-Cost-First Search

Queue<Problem.State> solve(Problem p)

  paths = 
    MinQueue(Queue(s | s ∈ p.startStates()))

  while !paths.empty()
    path = paths.get()
    s = path.tail()
    if p.goalState(s)
      return path
    for n in p.nextStates(s)
      paths.put(path.copy().add(n))

  return Queue()

Observations

• LCF search is BFS with a min priority queue over path costs.
• LCF search returns optimal (minimal) solutions.
• LCF search doesn’t get trapped in infinite loops.
  • But they can slow the algorithm down.
• A similar trick can be applied to DFS, but is much less effective.

Heuristics

• Searches can also exploit goal information.
  • Either the goals themselves or their characterization.
• A heuristic is an estimate (guess) of the “distance” between a state and a goal.

A* Search

• A* search is a variation on LCF search.
• Given a heuristic function h, define the total cost estimate T as

  T(v₀, …, v_k) = C(v₀, …, v_k) + h(v_k).

• The min priority queue orders paths on T.

Comparing Searches

• Searches can be compared on resources (time or space) taken, or results produced (quality or accuracy).
  • And other criteria too.
• Resources used can be estimated via asymptotics or measured in execution.
  • Worst-case (Big-O) asymptotic estimates.

Summary

• Breadth- and depth-first search use minimal problem information to find solutions.
• A* search uses a cost-to-goal heuristic to improve searching.
• Improve searching (or anything) by exploiting more and better information.
  • Often the information’s available for free.
• If information’s not available or too expensive, make good guesses using heuristics.

References

• Search and Computational Complexity in IS (Chapter 3) in Intelligent Systems by Robert Schalkoff from Jones and Bartlett, 2009.

Credits

• Oranges and Nicely squeezed oranges by Ant & Carrie Coleman under a Creative Commons BY NC ND license.

---

This page last modified on 2011 September 15.