Transcript Informed search

CMSC 671
Fall 2010
Thu 9/9/10
Uninformed Search (summary)
Informed Search
Functional Programming (revisited)
Prof. Laura Zavala, [email protected], ITE 373, 410-455-8775
Functional
Programming
Cool Things About Lisp
• Functions as objects (pass a function as an
argument)
• Lambda expressions (construct a function on
the fly)
• Lists as first-class objects
• Program as data
• Macros (smart expansion of expressions)
• Symbol manipulation
Functional Programming
• Decomposes a problem into a set of functions
• Has its roots in Lambda Calculus
• Formal system for function definition, function
application and recursion.
• Functions as objects (pass a function as an argument)
• Lambda expressions (construct a function on the fly)
• Functions don't have any internal state (global and
local variables)
• Recursion
• Truly functional programs are highly parallelizable
Functional Programming
Languages
 A focus on LISt Processing (Lisp).
 Built-in map(), reduce(), and filter(), and the
operator lambda.
 Lisp, Scheme, Haskell, ML, OCAML,
Clean, Mercury, Erlang, and a few others.
 Python – Procedural, object-oriented, FP
 Clojure - a dynamically-typed, functional
programming language that runs on the JVM
and provides interoperability with Java.
Lisp Map Function
 Apply a function to all elements of a list,
and return the resulting list
 Lisp has a whole family of map functions
 map, maplist, mapcar, etc.
> mapcar #’(lambda (x) (+ x 10)
‘(1 2 3))
(11 12 13)
> mapcar #’list
‘(a b c)
‘(11 2 3 4))
((A 1) (B 2) (C 3))
Lisp Reduce Function
 Boiling down a sequence into a single value
 The function must be a function of two
arguments
> reduce #’fn ‘(a b c d))
is equivalent to
> (fn (fn (fn ‘a ‘b) ‘c) ‘d)
> reduce #’+ ‘(1 2 3))
(6)
Uninformed Search (summary)
Building goal-based agents
To build a goal-based agent we need to answer the
following questions:
 What is the goal to be achieved?
 What are the actions?
 What relevant information is necessary to encode in
order to describe the state of the world, describe the
available transitions, and solve the problem?
Initial
state
Goal
state
Actions
8 puzzle
State: 3 x 3 array configuration of the tiles on
the board.
Operators: Blank Left, Blank Right, Blank Up,
Blank Down.
Initial State: A particular configuration of the
board.
Goal: A particular configuration of the board.
8 puzzle – Search Tree
Study this map of Romania. Note the distances between cities and try and calculate the shortest route
between Arad and Bucharest.
http://www.cs.nott.ac.uk/~ajp/
Neamt
Oradea
71
Zerind
87
75
Iasi
151
Arad
Optimal route is (140+80+97+101) = 418 miles
140
92
Vaslui
118
Sibiu
Timisoara
99
Faragas
142
80
111
Lugoj
211
Rimnicu
70
Urziceni
97
146
75
101
Bucharest
138
Dobreta
120
Hirsova
86
Pitesti
Mehadia
98
86
90
Craiova
Giurgui
Eforie
Search Tree
http://www.ics.uci.edu/~smyth/
Search Tree
http://www.ics.uci.edu/~smyth/
Search Tree
http://www.ics.uci.edu/~smyth/
Evaluating search strategies
 Completeness
 Guarantees finding a solution whenever one exists
 Time complexity
 How long (worst or average case) does it take to find a solution?
Usually measured in terms of the number of nodes expanded
 Space complexity
 How much space (memory) is used by the algorithm? Usually
measured in terms of the maximum size of the “nodes” list during the
search
 Optimality/Admissibility
 If a solution is found, is it guaranteed to be an optimal one? That is, is
it the one with minimum cost?
Uninformed Search Methods
Breadth-First vs Depth-First (DFS)
Breadth-First
Exponential time and space O(bd)
Optimal if costs are the same
Uniform-Cost (UCS)
complete and optimal
Depth-First
Exponential time O(bd)
Linear space O(bd)
May not terminate
Iterative Deepening
solves the infinite-path problem
Bi-directional search
 Alternate searching from the start state toward the goal and
from the goal state toward the start.
 Stop when the frontiers intersect.
 Works well only when there are unique start and goal states.
 Requires the ability to generate “predecessor” states.
 Can (sometimes) lead to finding a solution more quickly.
Uninformed Search Results
Example for illustrating uninformed search strategies
S
3
A
3
D
B
15
7
E
8
1
C
20
G
5
Depth-First Search
S
3
3
D
B
15
E
8
1
A
7
Expanded node
C
20
G
5
S0
A3
D6
E10
G18
Nodes list
{ S0 }
{ A3 B1 C8 }
{ D6 E10 G18 B1 C8 }
{ E10 G18 B1 C8 }
{ G18 B1 C8 }
{ B1 C8 }
Solution path found is S A G, cost 18
Number of nodes expanded (including goal node) = 5
Breadth-First Search
Expanded node
S
3
3
D
A
B
15
7
E
8
1
20
G
S0
C A3
1
B
5
C8
D6
E10
G18
Nodes list
{ S0 }
{ A3 B1 C8 }
{ B1 C8 D6 E10 G18 }
{ C8 D6 E10 G18 G21 }
{ D6 E10 G18 G21 G13 }
{ E10 G18 G21 G13 }
{ G18 G21 G13 }
{ G21 G13 }
Solution path found is S A G , cost 18
Number of nodes expanded (including goal node) = 7
Uniform-Cost Search
Expanded node
S
3
3
D
A
B
15
7
E
8
1
C
20
G
5
S0
B1
A3
Nodes list
{ S0 }
{ B1 A3 C8 }
{ A3 C8 G21 }
{ D6 C8 E10 G18 G21 }
D6
C8
E10
G13
{ C8 E10 G18 G1 }
{ E10 G13 G18 G21 }
{ G13 G18 G21 }
{ G18 G21 }
Solution path found is S B G, cost 13
Number of nodes expanded (including goal node) = 7
How they perform
 Depth-First Search:
 Expanded nodes: S A D E G
 Solution found: S A G (cost 18)
 Breadth-First Search:
 Expanded nodes: S A B C D E G
 Solution found: S A G (cost 18)
 Uniform-Cost Search:
 Expanded nodes: S A D B C E G
 Solution found: S B G (cost 13)
This is the only uninformed search that worries about costs.
 Iterative-Deepening Search:
 nodes expanded: S S A B C S A D E G
 Solution found: S A G (cost 18)
Bi-directional search
 Alternate searching from the start state toward the goal and
from the goal state toward the start.
 Stop when the frontiers intersect.
 Works well only when there are unique start and goal states.
 Requires the ability to generate “predecessor” states.
 Can (sometimes) lead to finding a solution more quickly.
Comparing Search Strategies
Avoiding Repeated States
In increasing order of effectiveness in
reducing size of state space and with
increasing computational costs:
1. Do not return to the state you just came
from.
2. Do not create paths with cycles in them.
3. Do not generate any state that was ever
created before.
Net effect depends on frequency of “loops”
in state space.
Informed Search Methods
Informed search strategy
 Uses problem-specific knowledge to assess
whether one non-goal state is “morepromising” than another.
 The strategy and knowledge used for the
assessment is known as heuristic.
Heuristic
Merriam-Webster's Online Dictionary
Heuristic (pron. \hyu-’ris-tik\): adj. [from Greek heuriskein to discover.]
involving or serving as an aid to learning, discovery, or problemsolving by experimental and especially trial-and-error methods
The Free On-line Dictionary of Computing (15Feb98)
heuristic 1. <programming> A rule of thumb, simplification or educated
guess that reduces or limits the search for solutions in domains that are
difficult and poorly understood. Unlike algorithms, heuristics do not
guarantee feasible solutions and are often used with no theoretical
guarantee. 2. <algorithm> approximation algorithm.
From WordNet (r) 1.6
heuristic adj 1: (computer science) relating to or using a heuristic rule 2:
of or relating to a general formulation that serves to guide investigation
[ant: algorithmic] n : a commonsense rule (or set of rules) intended to
increase the probability of solving some problem [syn: heuristic rule,
heuristic program]
Heuristic function
Define a heuristic function h(n) that
estimates the “goodness” of a node n.
 Specifically, h(n) = estimated cost (or distance)
of minimal cost path from n to a goal state.
The heuristic function is an estimate of how
close we are to a goal, based on domainspecific information that is computable from
the current state description.
Examples of Heuristics
Examples:
 Missionaries and Cannibals: Number of people on
starting river bank
 8-puzzle: Number of tiles out of place
 8-puzzle: Sum of distances each tile is from its
goal position (Manhattan Distance)
In general:
 h(n) ≥ 0 for all nodes n
 h(n) = 0 implies that n is a goal node
 h(n) = ∞ implies that n is a dead-end that can
never lead to a goal
Best-first search
Order nodes on the nodes list by increasing
value of an evaluation function f (n)
 f (n) incorporates domain-specific information in
some way.
 Incorportes a heuristic function h(n) as a
component of f.
This is a generic way of referring to the class
of informed methods.
 We get different searches depending on the
evaluation function f (n)
Greedy search
Evaluates nodes by using just the heuristic
function f (n) = h(n).
Selects node to expand believed to be closest
(hence “greedy”) to a goal node (i.e., select
node with smallest f value)
Not complete
Not admissible
Greedy Search
h = Straight Line
Distance
253
176
Algorithm A*
 Use as an evaluation function
S
f (n) = g(n) + h(n)
8
1
5
 g(n) = minimal-cost path from the
1
start state to state n.
5 B
A
C 8
 The g(n) term adds a “breadth9
3
first” component to the evaluation
5
1
function.
4 D
G
 Ranks nodes on search frontier by
estimated cost of solution from
9
start node through the given node g(d)=4
C is chosen
to goal.
next to expand
h(d)=9
Evaluating
 Admissible heuristic – Never overestimates
the cost to reach the goal
 SLD – Shortest path between any two points is a
straight line, so it can not be an overestimate.
 Consistency – estimated cost of reaching
goal from n is no greater than step cost n to
n’ plus estimated cost of reaching goal from
n’
 h(n) <= c(n,a,n’) + h(n’)
Algorithm A*
Complete whenever the
S
branching factor is finite, and
1
5 8
every operator has a fixed 1
5 B
A
positive cost
C 8
9
3
Optimally efficient for any
5
1
4 D
given consistent heuristic
G
9
g(d)=4
h(d)=9
C is chosen
next to expand
A* in action
 Remember that the A* search pattern is the union of two
evaluation functions. In the following demonstration the A*
search pattern evaluates the cost of the path so far (UCS),
together with an admissible heuristic function based on the
shortest line distance (SLD) between between the initial
state and the goal location, such that
 hSLD(n) = straight line distance between n and the goal
location.
 The following is table of the straight line distances between
some of the major Romanian cities and and the goal state,
Bucharest.
Straight Line Distances to Bucharest
Town
SLD
Town
SLD
Arad
366
Mehadai
241
Bucharest
0
Neamt
234
Craiova
160
Oradea
380
Dobreta
242
Pitesti
98
Eforie
161
Rimnicu
193
Fagaras
178
Sibiu
253
Giurgiu
77
Timisoara
329
Hirsova
151
Urziceni
80
Iasi
226
Vaslui
199
Lugoj
244
Zerind
374
We can use straight line distances as an admissible heuristic as they
will never overestimate the cost to the goal: there is no shorter
distance between two cities than the straight line distance.
We have now arrived at Bucharest. As this is the lowest cost node AND the goal state we
InWe
We
Once
Press
actual
have
now
begin
now
Arad
Rimnicu
Fagaras
space
expand
just
fact,
expand
with
isto
expanded
the
isis
see
the
expanded
Fagaras
expanded
Sibiu
Rimnicu
Pitesti
algorithm
an
initial
A*
(that
awe
(that
(that
node
search
state
(that
we
look
we
will
is,
is,
is,
look
(Pitesti)
look
of
we
is,
for
we
not
of
we
Arad.
we
expand
for
the
the
expand
for
really
expand
expand
the
Romanian
that
node
the
The
lowest
the
recognise
node
revealed
the
the
cost
with
the
node
node
node
with
of
cost
node
map
the
reaching
with
Bucharest,
with
that
with
lowest
the
node.
featured
with
the
we
lowest
the
the
As
the
lowest
Arad
have
cost.
lowest
lowest
you
in
but
lowest
cost.
Sibiu
found
the
from
it
value
can
value
value
As
has
previous
value
Arad
see,
has
Bucharest.
you
aofof
cost
of
the
we
fof
(or
fcan
).f).
slide.
).
lowest
fnow
Press
of
gPress
).see,
Press
value)
418.
Press
Ithave
Note:
space
just
Pitesti
value
space
Ifis 0
can terminate the search. If you look back over the slides you will see that the solution
for
has
there
keeps
space
two
Throughout
miles.
space
to
continue
f.the
Bucharest
is
(The
to
expanding
to
The
lowest
any
continue
continue
cost
straight
other
the
the
value
nodes.
tosearch.
animation
the
lower
the
reach
the
line
for
lowest
search.
One
search.
Sibiu
cost
f.
distance
(The
of
all
cost
node
these
from
nodes
cost
nodes
from
(and
nodes
Arad
to
are
Arad
reach
(based
inlabelled
is(this
Arad
140
toPitesti
case
on
Bucharest
miles,
–with
f Sibiu
)there
from
until
and
f(n)
–isArad
(or
itRimnicu
the
one
=
finds
hg(n)
straight
is
value)
cheaper
317
a +goal
–h(n).
miles,
Pitesti
isline
node,
state
366
However,we
distance
and
–miles.
AND
Fagaras,
Bucharest
theit
This
from
straight
has
with
will
gives
)the
returned by the A* search pattern ( Arad – Sibiu – Rimnicu – Pitesti – Bucharest ), is in fact
Sibiu
aline
lowest
has
be
us
cost
ausing
an
distance
total
to
of
fvalue
value
the
417)
the
value
goal
from
of
abbreviations
then
off.of
state
418.
So,
Pitesti
(we
f we
The
=
isneed
g253
must
to
+other
f,the
to
hmiles.
g)expand
now
and
366
goal
node
This
move
h
miles.
state
to
(Arad
it make
in
gives
is
to
Press
case
98
–Fagaras
Sibiu
the
amiles.
ittotal
space
leads
notation
–and
of
This
Fagaras
toto
393
expand
asimpler
gives
better
miles).
– Bucharest
ait.
the
solution
total
Press
initial
ofspace
space
(2)
415
to
state
)Bucharest
has
miles).
to
ofcontinue.
an
move
Arad.
f Press
value
than
to
the optimal solution.
this450.
space
the
of
418
node
toWe
solution
move
and
therefore
expand
towe
thishave
move
node
it. already
and
to the
expand
found.
first Bucharest
it.Press space
nodetoand
continue.
expand it. Press space to continue
Zerind
Oradea
F= 75 + 374
F= 449
F= 291 + 380
F= 671
F= 0 + 366
Arad
F= 366
Fagaras
Sibiu
F= 239 + 178
F= 417
F= 140 + 253
F= 118 + 329
F= 447
Timisoara
F= 220 + 193
F= 413
Bucharest(2)
F= 393
F= 450 + 0
Rimnicu
F= 450
Bucharest
F= 418 + 0
Pitesti
Craiova
F= 366 + 160
F= 526
http://www.cs.nott.ac.uk/~ajp/
F= 317 + 98
F= 415
F= 418
Features of an A* Search
 A* is optimal and complete, but it is not all good news. It
can be shown that the number of nodes that are searched
is still exponential to the length of the search space for
most problems. This has implications not only for the
time taken to perform the search but also the space
required. Of these two problems the search complexity is
more serious.
 If you examine the animation on the previous slide you
will notice an interesting phenomenon. Along any path
from the root, the f-cost never decreases. This is no
accident. It holds true for all admissible heuristics. A
heuristic for which it holds is said to exhibit
monotonicity.
 Because A* expands the leaf nodes of lowest f, we can
see that an A* search fans out from the start node, adding
nodes in concentric bands of increasing f-cost. These
bands can be modelled as contours in the state space.
Dealing with hard problems
 For large problems, A* often requires too much space.
 Two variations conserve memory: IDA* and SMA*
 IDA* -- iterative deepening A*
 uses successive iteration with growing limits on f. For
example,
 A* but don’t consider any node n where f (n) > 10
 A* but don’t consider any node n where f (n) > 20
 A* but don’t consider any node n where f (n) > 30, ...
 SMA* -- Simplified Memory-Bounded A*
 uses a queue of restricted size to limit memory use.
 throws away the “oldest” worst solution.
What’s a good heuristic?
If h1(n) < h2(n) ≤ h*(n) for all n, h2 is better
than (dominates) h1
 Relaxing the problem: remove constraints to create a
(much) easier problem; use the solution cost for this problem
as the heuristic function
 Combining heuristics: take the max of several admissible
heuristics: still have an admissible heuristic, and it’s better!
 Identify good features, then use a learning algorithm to
find a heuristic function: also may lose admissibility
Summary: Informed search
 Best-first search is general search where the minimum-cost
nodes (according to some measure) are expanded first.
 Greedy search uses minimal estimated cost h(n) to the goal state
as measure. This reduces the search time, but the algorithm is
neither complete nor optimal.
 A* search combines uniform-cost search and greedy search: f (n)
= g(n) + h(n). A* handles state repetitions and h(n) never
overestimates.
 A* is complete and optimal, but space complexity is high.
 The time complexity depends on the quality of the heuristic
function.
 IDA* and SMA* reduce the memory requirements of A*.
Thanks for coming -- see you
next Tuesday!