Chapter 4
Beyond Classical Search
Jane Hsu
National Taiwan University
Acknowledgements: This presentation is created by Jane hsu based
on the lecture slides from The Artificial Intelligence: A Modern
Approach by Russell & Norvig, a PowerPoint version by Min-Yen Kan,
as well as various materials from the web.
Outline
p Local Search Algorithms
n Hill climbing
n Simulated annealing
n Genetic algorithms
p Local search in continuous spaces
p Searching with nondeterministic actions
p Searching with partial observations
Beyond Classical Search © Jane Hsu 2
Standard Search Problem
p State space: the set of all states reachable
from the initial state
p State is a “black box” – any data structure
that supports
n successor function
n heuristic function, and
n goal test
Beyond Classical Search © Jane Hsu 3
Local Search Algorithms
Jane Hsu
National Taiwan University
Iterative Improvement Algorithms
p In many optimization problems, path is irrelevant;
the goal state itself is the solution
p State space = set of "complete" configurations
n Find optimal configuration, e.g., TSP
n Find configuration satisfying constraints, e.g., n-queens
p In such cases, we can use iterative improvement,
also called local search algorithms
n keep a single "current" state, try to improve it
n Constant space
n Online or offline search
Beyond Classical Search © Jane Hsu 5
Traveling Salesperson Problem
p Start with any complete tour, perform pair-wise
exchanges.
p Variants of this approach get within 1% of
optimal very quickly with thousands of cities.
Beyond Classical Search © Jane Hsu 6
Example: 8-Queens Problem
Jane Hsu 7
Beyond Classical Search © Jane Hsu 8
Hill-Climbing (Gradient Ascent/Descent)
“Like climbing Everest in thick fog with amnesia”
Beyond Classical Search © Jane Hsu 9
Local Maxima
Beyond Classical Search © Jane Hsu 10
Problems in Hill-Climbing Search
p Consider the state space landscape
Beyond Classical Search © Jane Hsu 11
Simulated Annealing
p Idea: escape local maxima by allowing some "bad"
moves but gradually decrease their size & frequency
p
Beyond Classical Search © Jane Hsu 12
Properties of Simulated Annealing
Beyond Classical Search © Jane Hsu 13
Local Beam Search
p Keep track of (top) k states rather than just one
n Start with k randomly generated states
n At each iteration, all the successors of all k states are
generated
n If any one is a goal state, stop; else select the k best
successors from the complete list and repeat.
p Question: is it k searches run in parallel?
p Problem: all k states end up on same local hill
p Solution idea: choose k successors randomly,
biased towards good ones.
Beyond Classical Search © Jane Hsu 14
Evolutionary Computation
Beyond Classical Search Keith Downing at TEDxTrondheim 15
https://youtu.be/D3zUmfDd79s
Genetic Algorithms
p Population: Start with k randomly
generated individuals (i.e. states)
n Individual: each is represented as a string over
a finite alphabet (often a string of 0s and 1s)
n Fitness function: evaluation of the “goodness”
of a given state.
p A successor is generated by combining
two parents from the current population.
p Produce the next generation of states by
selection, crossover, and mutation
Beyond Classical Search © Jane Hsu 16
Genetic Algorithms
p Fitness function: number of non-attacking pairs of queens
(min = 0, max = 8 × 7/2 = 28)
p 24/(24+23+20+11) = 31%
p 23/(24+23+20+11) = 29% etc
Beyond Classical Search © Jane Hsu 17
Crossover Operators
p States are encoded as strings
Beyond Classical Search © Jane Hsu 18
Beyond Classical Search © Jane Hsu 19
http://chriscummins.cc/s/genetics/ 20
Local Search in
Continuous Spaces
Example: Airport Site Planning
p Suppose we want to place three new
airports anywhere in Romania, such all
cities have easy access to airports.
n 6-D state space (x1,y1),(x2,y2),(x3,y3)
n Objective function
f(x1,y1,x2,y2,x3,y3) = sum of squared distances
from each city to its nearest airport
Beyond Classical Search © Jane Hsu 22
Continuous Search Spaces
p Most real-world environments are
continuous.
p Successor function would return infinitely
many states!
p Solution ideas
n Discretization
n Gradient of the objective function
p Empirical gradient
p Line search
n Newton-Raphson method to solve ∇f (x) = 0
Beyond Classical Search © Jane Hsu 23
Continuous Search Space
Beyond Classical Search © Jane Hsu 24
Searching with
Nondeterministic Actions
Possible States of Vacuum World
Beyond Classical Search © Jane Hsu 26
Erratic Vacuum World
p Action: Suck
n When applied to a dirty square the action
cleans the square and sometimes cleans up
dirt in an adjacent square, too.
n When applied to a clean square the action
sometimes deposit dirt on the carpet.
p Use a Results function that returns a set
of possible outcome states.
p Solution?
Beyond Classical Search © Jane Hsu 27
Contingency Plan
p [Suck, if State=5 then [Right, Suck] else []]
p Solutions for nondeterministic problems can
contain nested if-then-else statements.
p Selection of actions based on contingencies
arising during execution.
p Exact prediction is impossible for many real-
world problems.
n People keep their eyes open while walking/driving
Beyond Classical Search © Jane Hsu 28
AND-OR Search Trees
Beyond Classical Search © Jane Hsu 29
AND-OR Graph Search
Beyond Classical Search © Jane Hsu 30
Slippery Vacuum World
p Original vacuum world +
n Movement actions sometimes fail, leaving the
agent in the same location.
n There is no way to move reliably.
p All solutions for this problem are cyclic
plans
Beyond Classical Search © Jane Hsu 31
Search Graph with Cycles
Beyond Classical Search © Jane Hsu 32
Searching with Partial
Observations
Searching with No Observation
p (a) Sensorless vacuum world with
deterministic action, Right.
p (b) Slippery sensorless vacuum world
Beyond Classical Search © Jane Hsu 34
Belief-State Space (deterministic/sensorless)
Beyond Classical Search © Jane Hsu 35
Incremental Belief-State Search
p Build up the solution one physical state at
a time.
p First find a solution that works for state 1
p Then check if it works for state 2.
p If not, go back and find an alternative
solution for state 1.
p And so on.
p Similar to AND-OR search
Beyond Classical Search © Jane Hsu 36
Local Sensing Vacuum Worlds
Beyond Classical Search © Jane Hsu 37
Solving Partially Observable Problems
Beyond Classical Search © Jane Hsu 38
Prediction Update Cycles
Beyond Classical Search © Jane Hsu 39
