Wissensverarbeitung - Search -

Alexander Felfernig & Gerald Steinbauer

Institute for Software Technology

1

Wissensverarbeitung

Alexander Felfernig und Gerald SteinbauerInstitut für Softwaretechnologie

Inffeldgasse 16b/2A-8010 Graz

Austria

Wissensverarbeitung- Search -



2

Wissensverarbeitung

References

Skriptum (TU Wien, Institut für Informationssysteme, Thomas Eiter et al.) ÖH-Copyshop, Studienzentrum

Stuart Russell und Peter Norvig. Artificial Intelligence - A Modern Approach. Prentice Hall. 2003.

Vorlesungsfolien TU Graz (partially based on the slides of TUWien)



3

Wissensverarbeitung

Goals

Uninformed Search Strategies.Informed Search Strategies.



4

Wissensverarbeitung

SearchImportant method of Artificial Intelligence

Approaches:– Uninformed search– Informed search (exploit information/heuristics about the problem

structure)

Example:– Which is the shortest path from A to D?

A B

C

D

E



5

Wissensverarbeitung

Elements of a Search Problem

Start node (start state)Goal node (goal state)States are generated dynamically

– on the basis of generation rule R– example: move one element to the empty field

Search goal: sequence of rules that transform the start state to the goal state

3 6

2 1 4

5 8 7

1 2

8

3

4

7 6 5

startstate

goalstate



6

Wissensverarbeitung

Search Problem

Start state (S0)

Non-empty set of goal states (goal test)

Non-empty set of operators:– Transform state Si into state Si+1

– Transformation triggers costs (>0)– No cost estimation available default: unit costs

Cost function for search paths:– of individual transformations



7

Wissensverarbeitung

Properties of Search Methods

Completeness– Does the method find a solution, if one exists?

Space Complexity– How do memory requirements increase with increasing

sizes of search problems (search spaces)?

Time Complexity– What is the computing performance with increasing

sizes of search problems (search spaces)?

Optimality– Does the method identify the optimal solution

(if one exists)?



8

Wissensverarbeitung

Breadth-First Search (bfs)

Level-wise expansion of states

Systematic strategy– Expand all paths of length 1– Expand all paths of length 2– …

Completeness yes (if b is finite).

Space complexity: branching factor b, depth of the shallowest solution d: bd+1

Time complexity: bd+1

Optimality yes (if step costs are identical).



9

Wissensverarbeitung

bfs

[A] … [B,C,D] [B,C,D] … [C,D,E,F] [C,D,E,F] … [D,E,F,G] [D,E,F,G] … [E,F,G] [E,F,G] … [F,G] [F,G] … [G] [G]

A C

B

F

E

D G



10

Wissensverarbeitung

5

Uniform Cost Search (ucs)

Goal: „cheapest“ path from S to G (independent of # transitions)

Approach:– Expand S, then expand A (since A has the cheapest current path)– Solution not necessarily found opt. could be < 11– Expand B finally solution identified with path costs = 10

S B

C

G

A1

5

15 5

5

10S

B CA

1 5 15S

B CA

11

15

G

S

B CA

11 10

15

A G



11

Wissensverarbeitung

Generalization of bfs– Expand state with lowest related costs– There could be a solution with shorter path but higher costs– Corresponds to bfs if step costs are identical

Completeness yes (if b finite & step costs > ).

Space complexity: branching factor b, cost of the optimal solution C*: bC*/ + 1

Time complexity: bC*/ + 1

Optimality yes.

Uniform Cost Search (ucs)



12

Wissensverarbeitung

Depth First Search (dfs)

No level-wise expansion

Expansion of successor nodes of one „deepest state“

If no more states can be expanded backtracking

Completeness no (indefinite descent paths)

Space complexity: branching factor b, maximum depth of the search tree m: bm

Time complexity: bm

Optimality no.



13

Wissensverarbeitung

dfs

A C

B

F

E

D G

H

[A] … [B,C,D] [B,C,D] … [E,F,C,D] [E,F,C,D] … [H,F,C,D] [H,F,C,D] … [F,C,D] [F,C,D] … [C,D] [C,D] … [F,G,D] [F,G,D] … [G,D] [G,D]



14

Wissensverarbeitung

DF Iterative Deepening (dfid)

Search depth defined by bound lIf search depth l is reached backtrackingIf no solution has been found for level l l = l + 1Example using a binary tree:

Level 0:

Level 1:

Level 2:

Repeated dfsuntil search level l.



15

Wissensverarbeitung

DF Iterative Deepening

Completeness yes (if b is finite).

Space complexity: branching factor b, depth of the shallowest solution d: bd

Time complexity: bd

Optimality yes (if step costs are identical).



16

Wissensverarbeitung

Comparison of UninformedSearch Strategies



17

Wissensverarbeitung

Heuristic SearchInformed search which exploits problem- and

domain-specific knowledge

Estimation function: estimates the costs from the current node to the goal state

Heuristic approach denoted as best-first search, since best-evaluated state is chosen for expansion

Used notation:– f: estimation function; f* (the real function)– h(n): estimator of minimal costs from n to a goal state

Invariant for goal state Sn: h(n) = 0

Methods to be discussed:– Greedy search– A* search



18

Wissensverarbeitung

Greedy Search

Estimates minimal costs from current to the goal node

Does not take into account already existing costs, i.e.,– f(n) = h(n)

Completeness no (loopcheck needed).

Space complexity: branching factor b, maximum depth of the search tree m : bm

Time complexity: bm

Optimality no.



19

Wissensverarbeitung

Structure of Working Example



20

Wissensverarbeitung

Greedy Search

straight-line distance – h(sld)



21

Wissensverarbeitung

Greedy Search




22

Wissensverarbeitung

Greedy Search




23

Wissensverarbeitung

Summarizing Greedy Search

Use sld heuristicsChoose shortest path from Arad to Bucharest

– Arad: expand lowest h-value– Sibiu: expand lowest h-value– Fagaras: expand lowest h-value– Bucharest found

• path: Arad, Sibiu, Rimnicu, Pitesti, Bucharest• length of solution: 418km (in contrast to solution found – 450km)

Greedy search is based on local informationBetter choice: take into account already existing “efforts”



24

Wissensverarbeitung

Greedy Search: Loops



25

Wissensverarbeitung

A* SearchIn contrast to greedy search, it takes into account

already existing costs as well.– g(n) = path costs from start to current node

Results in a more fair selecting strategy for expansionEstimation function:

– f(n) = g(n) + h(n); h(n) the same as for greedy search

A*: best-first search method with the following properties:– Finite number of possible expansions– Transition costs are positive (min. )– admissible (h), i.e., h does never overestimate the real costs (it is

an optimistic heuristic)– Consequently: f never overestimates the real costs



26

Wissensverarbeitung

A* Search



27

Wissensverarbeitung

A* Search



28

Wissensverarbeitung

A* Search



29

Wissensverarbeitung

Summarizing A* Search

Used functions– g(n): real distance Arad-n– h(n): sld Bucharest-n

Taking into account global information improves the quality of the identified solution

Expansion ordering (lowest f-value) Sibiu, Rimnicu, Pitesti, Bucharest

Optimal solution will be found



30

Wissensverarbeitung

Determination of Heuristics

Heuristic function h must be optimisticNo formal rule set of determining heuristic functions

exists, however, some rules of thumb are there …Example (8-Puzzle)

– 2 heuristic functions h1 and h2

– h1: number of squares in wrong position– h2: sum(distances of fields from goal state)– Simplification: do not take into account the

influences of moves to other fields.

For start state, h1=7 and h2 = 15Dominance relationship: h2 dominates h1 since for each

n: h1(n) h2(n) h2 is assumed to be more efficient; h1 has tendency towards breadth first search.

startstate

goalstate



31

Wissensverarbeitung

Properties of A* Search

f-values along a path in the search tree are never decreasing (monotonicity property)

theorem: monoton(f) h(n1) c(n1,n2) + h(n2)

expansion of nodes with increasing f-value

goal



32

Wissensverarbeitung

Properties of A* Search

„Distance circles“ of 380, 400, 420km (f-values)Expand all n with f(n)380, then 400, …Let f* be the costs of an optimal solution:

– A* expands all n with f(n) < f* ,– some m with f(m) = f*, and– the goal state will be identified

Completeness yes (h is admissible).

Space complexity: exponential

Time complexity: exponential

Optimality yes.



33

Wissensverarbeitung

Optimality of A* Search

Suppose suboptimal goal (path to) G2 in the queue.Let n be an unexpanded node on a shortest path to an optimal

goal Gf(G2 ) = g(G2 ) since h(G2 )=0

> g(G) since G2 is suboptimal [f(G2) > g(G)]

>= f(n) since h is admissible [f(G2) > f(n)]Since f(G2) > f(n), A* will never select G2 for expansion



34

Wissensverarbeitung

Local SearchPreviously: systematic exploration of search space

– path to goal is solution to the problem

However, for some problems the path is irrelevant– for example, 8-queens problem– state space = set of configurations (complete)– goal: identify configuration which satisfies a set of constraints

Other algorithms can be used– local search algorithms– try to improve the current state by generating a follow-up state

(neighbor state)– are not systematic, not optimal, and not complete



35

Wissensverarbeitung

Local Search: Examplen-queens problem: positioning of n queens in an

nxn board s.t. the number of 2 queens positioned on the same column, row or diagonal is minimized or zero.



36

Wissensverarbeitung

Hill Climbing Algorithm“Finding the top of Mount Everest in a thick fog

while suffering from amnesia” [Russel & Norvig, 2003]

“Greedy local search”



37

Wissensverarbeitung

Hill Climbing: Local Maxima

Peak that is higher than each of its neighboring states but lower than the global maximum.

h = number of pairs of queens attacking each other

successor function: move single queen to another square in the same column

h = 1 local maximum (minimum): “every

move of a single queen makes the situation worse”

[Russel & Norvig 2003]



38

Wissensverarbeitung

Hill Climbing: Ridges

Sequence of local maxima.



39

Wissensverarbeitung

Hill Climbing: Plateaux

Evaluation function is “flat”, a local maximum or a shoulder from which progress is possible.



40

Wissensverarbeitung

Simulated Annealing

Hill climbing never selects downhill movesDanger of, for example, local maximaInstead of picking the best move, choose a random one and accept

also worse solutions with a decreasing probability



41

Wissensverarbeitung

Genetic AlgorithmsStart with k randomly generated states (the population)Each state (individual) represented by a string over a

finite alphabet (e.g., 1..8)Each state is rated by evaluation (fitness) function (e.g.,

#non-attacking pairs of queens – opt. = 28)Selection probability directly proportional to fitness

score, for example, 23/(24+23+20+11) 29%



42

Wissensverarbeitung

Genetic Algorithms: Cross-Over



43

Wissensverarbeitung

Genetic Algorithmfunction GENETIC_ALGORITHM( population, FITNESS-FN) return an

individualinput: population, a set of individualsFITNESS-FN, a function which determines the quality of the individualrepeatnew_population empty setloop for i from 1 to SIZE(population) dox RANDOM_SELECTION(population, FITNESS_FN) y RANDOM_SELECTION(population, FITNESS_FN)child REPRODUCE(x,y)if (small random probability) then child MUTATE(child )add child to new_populationpopulation new_populationuntil some individual is fit enough or enough time has elapsedreturn the best individual



44

Wissensverarbeitung

Thank You!

Documents

Wissensverarbeitung - Search -