> ~n(
/0LDArialy0z[ 0@.
@n?" dd@ @@`` XWR
MM5 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQR,TUV0AA@Iʚ;ʚ;g4BdBd z[ 0vppp@<4ddddL 0|y<4BdBdL< 0
0___PPT10
___PPT9D$,(( 9b#Problems, Problem Spaces and SearchDr. Suthikshn Kumar Contents4Defining the problem as a State Space Search
Production Systems
Control Strategies
Breadth First Search
Depth First Search
Heuristic Search
Problem Characteristics
Is the Problem Decomposable?
Can Solution Steps be ignored or undone?
Production system characteristics
Issues in the design of search programs
5Z5$To build a system to solve a problem%%(Define the problem precisely
Analyse the problem
Isolate and represent the task knowledge that is necessary to solve the problem
Choose the best problem-solving techniques and apply it to the particular problem." *Defining the problem as State Space Search++(The state space representation forms the basis of most of the AI methods.
Its structure corresponds to the structure of problem solving in two important ways:
It allows for a formal definition of a problem as the need to convert some given situation into some desired situation using a set of permissible operations.
It permits us to define the process of solving a particular problem as a combination of known techniques (each represented as a rule defining a single step in the space) and search, the general technique of exploring the space to try to find some path from current state to a goal state.
Search is a very important process in the solution of hard problems for which no more direct techniques are available..Z5Z5Example: Playing ChessTo build a program that could play chess , we could first have to specify the starting position of the chess board, the rules that define the legal moves, and the board positions that represent a win for one side or the other.
In addition, we must make explicit the previously implicit goal of not only playing the legal game of chess but also winning the game, if possible,
zz
Playing chessThe starting position can be described as an 8by 8 array where each position contains a symbol for appropriate piece.
We can define as our goal the check mate position.
The legal moves provide the way of getting from initial state to a goal state.
They can be described easily as a set of rules consisting of two parts:
A left side that serves as a pattern to be matched against the current board position.
And a right side that describes the change to be made to reflect the move
However, this approach leads to large number of rules 10120 board positions !!
Using so many rules poses problems such as:
No person could ever supply a complete set of such rules.
No program could easily handle all those rules. Just storing so many rules poses serious difficulties.vAPP{PPA8
?
,Defining chess problem as State Space search--(We need to write the rules describing the legal moves in as general a way as possible.
For example:
White pawn at Square( file e, rank 2) AND Square( File e, rank 3) is empty AND Square(file e, rank 4) is empty, then move the pawn from Square( file e, rank 2) to Square( file e, rank 4).
In general, the more succintly we can describe the rules we need, the less work we will have to do to provide them and more efficient the program.BdZZZd,w uWater Jug Problem9The state space for this problem can be described as the set of ordered pairs of integers (x,y) such that x = 0, 1,2, 3 or 4 and y = 0,1,2 or 3; x represents the number of gallons of water in the 4-gallon jug and y represents the quantity of water in 3-gallon jug
The start state is (0,0)
The goal state is (2,n)
:Z:[&Production rules for Water Jug Problem''(KThe operators to be used to solve the problem can be described as follows:
LK Production rules
To solve the water jug problemRequired a control structure that loops through a simple cycle in which some rule whose left side matches the current state is chosen, the appropriate change to the state is made as described in the corresponding right side, and the resulting state is checked to see if it corresponds to goal state.
One solution to the water jug problem
Shortest such sequence will have a impact on the choice of appropriate mechanism to guide the search for solution.
(Z!Formal Description of the problem""(Define a state space that contains all the possible configurations of the relevant objects.
Specify one or more states within that space that describe possible situations from which the problem solving process may start ( initial state)
Specify one or more states that would be acceptable as solutions to the problem. ( goal states)
Specify a set of rules that describe the actions ( operations) available. " PProduction Systems~A production system consists of:
A set of rules, each consisting of a left side that determines the applicability of the rule and a right side that describes the operation to be performed if that rule is applied.
One or more knowledge/databases that contain whatever information is appropriate for the particular task. Some parts of the database may be permanent, while other parts of it may pertain only to the solution of the current problem.
A control strategy that specifies the order in which the rules will be compared to the database and a way of resolving the conflicts that arise when several rules match at once.
A rule applier$!P^P
Production systemTInorder to solve a problem:
We must first reduce it to one for which a precise statement can be given. This can be done by defining the problem s state space ( start and goal states) and a set of operators for moving that space.
The problem can then be solved by searching for a path through the space from an initial state to a goal state.
The process of solving the problem can usefully be modelled as a production system. $PP$Control StrategiesHow to decide which rule to apply next during the process of searching for a solution to a problem?
The two requirements of good control strategy are that
it should cause motion.
It should be systematic&00 Breadth First SearchAlgorithm:
Create a variable called NODE-LIST and set it to initial state
Until a goal state is found or NODE-LIST is empty do
Remove the first element from NODE-LIST and call it E. If NODE-LIST was empty, quit
For each way that each rule can match the state described in E do:
Apply the rule to generate a new state
If the new state is a goal state, quit and return this state
Otherwise, add the new state to the end of NODE-LISTpt t!BFS Tree for Water Jug problem(
&Algorithm: Depth First SearchYIf the initial state is a goal state, quit and return success
Otherwise, do the following until success or failure is signaled:
Generate a successor, E, of initial state. If there are no more successors, signal failure.
Call Depth-First Search, with E as the initial state
If success is returned, signal success. Otherwise continue in this loop.:" Z" Z'BacktrackingIn this search, we pursue a singal branch of the tree until it yields a solution or until a decision to terminate the path is made.
It makes sense to terminate a path if it reaches dead-end, produces a previous state. In such a state backtracking occurs
Chronological Backtracking: Order in which steps are undone depends only on the temporal sequence in which steps were initially made.
Specifically most recent step is always the first to be undone.
This is also simple backtracking.Z( Advantages of Depth-First Search!!(DFS requires less memory since only the nodes on the current path are stored.
By chance, DFS may find a solution without examining much of the search space at all. )Advantages of BFSBFS will not get trapped exploring a blind alley.
If there is a solution, BFS is guarnateed to find it.
If there are multiple solutions, then a minimal solution will be found.Q
V*TSPA simple motion causing and systematic control structure could solve this problem.
Simply explore all possible paths in the tree and return the shortest path.
If there are N cities, then number of different paths among them is 1.2& .(N-1) or (N-1)!
The time to examine single path is proportional to N
So the total time required to perform this search is proportional to N!
For 10 cities, 10! = 3,628,800
This phenomenon is called Combinatorial explosion.Z+Branch and BoundkBegin generating complete paths, keeping track of the shortest path found so far.
Give up exploring any path as soon as its partial length becomes greater than the shortest path found so far.
Using this algorithm, we are guaranteed to find the shortest path.
It still requires exponential time.
The time it saves depends on the order in which paths are explored. lZl,Heuristic SearchA Heuristic is a technique that improves the efficiency of a search process, possibly by sacrificing claims of completeness.
Heuristics are like tour guides
They are good to the extent that they point in generally interesting directions;
They are bad to the extent that they may miss points of interest to particular individuals.
On the average they improve the quality of the paths that are explored.
Using Heuristics, we can hope to get good ( though possibly nonoptimal ) solutions to hard problems such asa TSP in non exponential time.
There are good general purpose heuristics that are useful in a wide variety of problem domains.
Special purpose heuristics exploit domain specific knowledgeP,
#-Nearest Neighbour Heuristic It works by selecting locally superior alternative at each step.
Applying to TSP:
Arbitrarily select a starting city
To select the next city, look at all cities not yet visited and select the one closest to the current city. Go to next step.
Repeat step 2 until all cities have been visited.
This procedure executes in time proportional to N2
It is possible to prove an upper bound on the error it incurs. This provides reassurance that one is not paying too high a price in accuracy for speed.lRZ Z ZR1
.Heuristic FunctionAThis is a function that maps from problem state descriptions to measures of desirsability, usually represented as numbers.
Which aspects of the problem state are considered,
how those aspects are evaluated, and
the weights given to individual aspects are chosen in such a way that
the value of the heuristic function at a given node in the search process gives as good an estimate as possible of whether that node is on the desired path to a solution.
Well designed heuristic functions can play an important part in efficiently guiding a search process toward a solution.
B{ZZ&Z{&L
8"Example Simple Heuristic functions##(Chess : The material advantage of our side over opponent.
TSP: the sum of distances so far
Tic-Tac-Toe: 1 for each row in which we could win and in we already have one piece plus 2 for each such row in we have two pieces_{9Problem CharacteristicsInorder to choose the most appropriate method for a particular problem, it is necessary to analyze the problem along several key dimensions:
Is the problem decomposable into a set of independent smaller or easier subproblems?
Can solution steps be ignored or at least undone if they prove unwise?
Is the problem s universe predictable?
Is a good solution to the problem obvious without comparison to all other possible solutions?
Is the desired solution a state of the world or a path to a state?
Is a large amount of knowledge absolutely required to solve the problem or is knowledge important only to constrain the search?
Can a computer that is simply given the problem return the solution or will the solution of the problem require interaction between the computer and a person?.PP$0;Is the problem Decomposable?Whether the problem can be decomposed into smaller problems?
Using the technique of problem decomposition, we can often solve very large problems easily.<Blocks World ProblemFollowing operators are available:
CLEAR(x) [ block x has nothing on it]-> ON(x, Table)
CLEAR(x) and CLEAR(y) -> ON(x,y) [ put x on y]b#! ?(Can Solution Steps be ignored or undone?))(.Suppose we are trying to prove a math theorem.We can prove a lemma. If we find the lemma is not of any help, we can still continue.
8-puzzle problem
Chess: A move cannot be taken back.
Important classes of problems:
Ignorable ( theorem proving)
Recoverable ( 8-puzzle)
Irrecoverable ( Chess)
The recoverability of a problem plays an important role in determining the complexity of the control structure necessary for the problem s solution.
Ignorable problems can be solved using a simple control structure that never backtracks
Recoverable problems can be solved by a slightly more complicated control strategy that does sometimes make mistakes
Irrecoverable problems will need to be solved by systems that expends a great deal of effort making each decision since decision must be final.
tPLPP]PPL]&
@ Is the universe Predictable?Certain Outcome ( ex: 8-puzzle)
Uncertain Outcome ( ex: Bridge, controlling a robot arm)
For solving certain outcome problems, open loop approach ( without feedback) will work fine.
For uncertain-outcome problems, planning can at best generate a sequence of operators that has a good probability of leading to a solution. We need to allow for a process of plan revision to take place.ZA!(Is a good solution absolute or relative?))(Any path problem
Best path problem
Any path problems can often be solved in a reasonable amount of time by using heuristics that suggest good paths to explore.
Best path problems are computationally harder.
ZE""Is the solution a state or a path?lExamples:
Finding a consistent interpretation for the sentence The bank president ate a dish of pasta salad with the fork . We need to find the interpretation but not the record of the processing.
Water jug : Here it is not sufficient to report that we have solved , but the path that we found to the state (2,0). Thus the a statement of a solution to this problem must be a sequence of operations ( Plan) that produces the final state.
X
6:=F#What is the role of knowledge?Two examples:
Chess: Knowledge is required to constrain the search for a solution
Newspaper story understanding: Lot of knowledge is required even to be able to recognize a solution.
Consider a problem of scanning daily newspapers to decide which are supporting the democrats and which are supporting the republicans in some election. We need lots of knowledge to answer such questions as:
The names of the candidates in each party
The facts that if the major thing you want to see done is have taxes lowered, you are probably supporting the republicans
The fact that if the major thing you want to see done is improved education for minority students, you are probably supporting the democrats.
etc\PPP7P7G$0Does the task require Interaction with a person?11(The programs require intermediate interaction with people for additional inputs and to provided reassurance to the user.
There are two types of programs:
Solitary
Conversational:
Decision on using one of these approaches will be important in the choice of problem solving method.
<ZZgZgN%Problem Classification/There are several broad classes into which the problems fall. These classes can each be associated with generic control strategy that is appropriate for solving the problems:
Classification : ex: medical diagnostics, diagnosis of faults in mechanical devices
Propose and Refine: ex: design and planning
&=!Production System Characteristics""(Can production systems, like problems, be described by a set of characteristics that shed some light on how they can easily be implemented?
If so, what relationships are there between problem types and the types of production systems best suited to solving the problems?
Classes of Production systems:
Monotonic Production System: the application of a rule never prevents the later application of another rule that could also have been applied at the time the first rule was selected.
Non-Monotonic Production system
Partially commutative Production system: property that if application of a particular sequence of rules transforms state x to state y, then permutation of those rules allowable, also transforms state x into state y.
Commutative Production systemL" PPPP&$Four Categories of Production System%%(Q''Issues in the design of search programs(((The direction in which to conduct the search ( forward versus backward reasoning).
How to select applicable rules ( Matching)
How to represent each node of the search process ( knowledge representation problem)R(SummaryFour steps for designing a program to solve a problem:
Define the problem precisely
Analyse the problem
Identify and represent the knowledge required by the task
Choose one or more techniques for problem solving and apply those techniques to the problem.
,7 7,T/D
"
#$%/01234567:>BCDHI J!K"L#M$O%S& ` 33` Sf3f` 33g` f` www3PP` ZXdbmo` \ғ3y`Ӣ` 3f3ff` 3f3FKf` hk]wwwfܹ` ff>>\`Y{ff` R>&- {p_/̴>?" dd@,|?" dd@ " @ ` n?" dd@ @@``PR @ ` `p>>f(
6u `}
T Click to edit Master title style!
!
0d `
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
0@ ^ `
>*
0 ^
@*
0 ^ `
@*H
0h ? 3380___PPT10.pP0 Default Design
0zr0
(
0ȱ P
P*
0$
R*
d
c$ ?
0D
0
RClick to edit Master text styles
Second level
Third level
Fourth level
Fifth level!
S
6 _P
P*
60 _
R*
H
0h ? 3380___PPT10.o:$ $(
r
Sx>
r
SDz `
H
0h ? 3380___PPT10. ,T$
P$(
r
S `}
r
S `
H
0h ? 3380___PPT10.L:
`:(
r
S `}
S `
"p`PpH
0h ? 3380___PPT10.$$
p$(
r
S `}
r
S4 `
H
0h ? 3380___PPT10.P54$
$(
r
S,) `}
r
S) `
H
0h ? 3380___PPT10.)$
$$(
$r
$ S<3 `}
r
$ SL0 `
H
$0h ? 3380___PPT10.Ӳw$
($(
(r
( SpE `}
r
( SF `
H
(0h ? 3380___PPT10.@w$
,$(
,r
, S_ `}
r
, S8g `
H
,0h ? 3380___PPT10.o\i$
##02LLi#(
Lr
L S|y `}
x
L c$Pz
7" @
LL#"2&r;:;::;:@l
$L
<~?K
Pour water from the 3 gallon jug into the 4 gallon jug until the 4-gallon jug is fullYY @`
#L
<t}?pK
T(4, y-(4-x))
@`
"L
<(?`K
p
(x,y) if x+y >= 4 and y >0, @`
!L
<@?K
`
I7 @`
L
<p?K
l$Empty the 3 gallon jug on the ground%% @`
L
<賒?pK
M(x,0) @`
L
<x?`pK
w
(x,y) if y >0
@`
L
<?`K
I6 @`
L
<ϒ?
^Empty the 4 gallon jug @`
L
<ؒ?p
N(0, y) @`
L
<ڒ?`
p
v(x,y) if x>0
@`
L
<P?
`
I5 @`
L
<0?
o'Pour some water out of the 3-gallon jug(( @`
L
<?p
r(x, y-d) @`
L
<?` p
x(x,y) if y > 0 @`
L
<,? `
I4 @`
L
<?a
o'Pour some water out of the 4 gallon jug(( @`
L
<$$?pa
r(x-d, y) @`
L
<?`ap
x(x,y) if x > 0 @`
L
<6?a`
I3 @`
L
<??'a
]Fill the 3 gallon jug @`
L
<H1?p'a
M(x,3) @`
L
<J?`'pa
w
(x,y) if y <3
@`
L
<,[?'`a
I2 @`
L
<d?'
]Fill the 4 gallon jug @`
L
<`m?p'
M(4,y) @`
L
<(_?`p'
x(x,y) if x < 4 @`
L
<?`'
I1 @`
L
<`?@
mDescritpion @`
L
<4z?p@
R
Next State @`
L
<8?`@p
U
Current state @`
L
<?@`
gSl No @``B
%L
0o
?@@ZB
&L
s*1
?ZB
'L
s*1
?''ZB
(L
s*1
?aaZB
)L
s*1
? ZB
*L
s*1
?
ZB
+L
s*1
?ZB
,L
s*1
?K
K
`B
-L
0o
?`B
.L
0o
?@ZB
/L
s*1
?`@`ZB
0L
s*1
?p@pZB
1L
s*1
?@`B
2L
0o
?@H
L0h ? 3380___PPT10.,HĚ
`"LY(
Xr
X ST `}
`
LY#"& `
X
< ?"`B
`
}5Empty the 2 gallons in the 4-gallon jug on the ground66 @`
X
< ?"`
B
M(0,y) @`
X
< ?"`<
M(2,y) @`
X
< ?"`
<
J12 @`
X
< ?"`B`
:Pour the 2 gallons from 3-gallon jug into the 4-gallon jug;; @`
X
< ?"`B
M(2,0) @`
X
< ?"`<
M(0,2) @`
X
< ?"` <
J11 @`
X
< ?"`B `
>Pour all the water from the 4-gallon jug into the 3-gallon jug?? @`
X
< ?"` B
r(0, x+y) @`
X
<! ?"`<
(x, y) if x+y <= 3 and x>0
@`
X
<2 ?"` <
J10 @`
X
<, ?"`B`
>Pour all the water from the 3-gallon jug into the 4-gallon jug?? @`
X
<E ?"`B
r(x+y, 0) @`
X
<DO ?"`<
(x, y) if x+y <=4 and y>0
@`
X
< X ?"` <
I9 @`
X
<a ?"`B`
UPour water from the 4-gallon jug into the 3-gallon jug until the 3-gallon jug is fullVV @`
X
<d ?"`B
T(x-(3-y), 3)
@`
X
<l ?"`<
(x, y) if x+y >= 3 and x>0
@`
X
<`} ?"` <
I8 @``B
X
01
? ``B
X
01
? ``B
X
01
? ` `B
X
01
? ``B
X
01
?
`
`B
X
0o
? ``B
X
0o
? `B
X
01
?<<`B
X
01
?`B
X
01
?BB`B
X
0o
?``H
X0h ? 3380___PPT10.o]
)4`(
`r
` S `}
x
` c$p 0
l p`!
4`#"2&DCEDDCEDp`!
1`
<h?
`
O9 0r 11 @`
/`
<8?
I2 @`
-`
<<?p
I0 @`
`
<ܞ?`!
@ @`
`
<H?!
I0 @`
`
<?p!
I2 @`
`
<?U`
O5 or 12 @`
`
<?U
I2 @`
`
<?pU
I4 @`
`
<?`U
I7 @`
`
<0?U
I3 @`
`
<?pU
I3 @`
`
<? `
I2 @`
`
<
?
I0 @`
`
<d?p
I3 @`
`
<?`
I9 @`
`
<<(?
I3 @`
`
<0?p
I0 @`
`
<$9?E`
I2 @`
`
<,B?E
I0 @`
`
<4K?pE
I0 @`
`
<(T?`E
TRule applied
@`
`
<]?E
cGallons in the 3-gallon jug @`
`
<f?pE
cGallons in the 4-gallon jug @``B
`
0o
?p`ZB
`
s*1
?pE`EZB
`
s*1
?p`ZB
`
s*1
?p ` ZB
`
s*1
?p`ZB
`
s*1
?pU`UZB
`
s*1
?p
`
`B
!`
0o
?p!`!`B
"`
0o
?pp!ZB
#`
s*1
?!ZB
$`
s*1
?!`B
%`
0o
?``!ZB
.`
s*1
?p`H
`0h ? 3380___PPT10.
:
h:(
hr
h Sܒ `}
h SĘ `
"p`PpH
h0h ? 3380___PPT10.^$
x$(
xr
x S `}
r
x SԪ `
H
x0h ? 3380___PPT10.Jg$
$(
r
SȽ `}
r
S `
H
0h ? 3380___PPT10.pnX"$
$(
r
S `}
r
S `
H
0h ? 3380___PPT10.n:
0:(
r
S `}
S `
"xdH
0h ? 3380___PPT10.>}
@} (
r
SL `}
04e"` @
5(0,0) 2
0"`p
5(4,0) 2
0"`
5(0,3) 2
0,"`
m
5(4,3) 2
0"`P
=
5(0,0) 2
0D"`P
=
5(1,3) 2
0"`P
=
5(4,3) 2
0L"`P
p=
5(0,0) 2
0
"`
@
5(3,0) 2RB
@
s*D
RB
s*D
RB
@
s*Dp
RB
s*DP
RB
s*DpP
RB
@
s*D
P
RB
s*DP
RB
s*Dp
H
0h ? 3380___PPT10.@"0:
:(
r
S `}
Sf `
"p`PpH
0h ? 3380___PPT10.7`N$
$(
r
S* `}
r
S+ `
H
0h ? 3380___PPT10.8Ҧ$
$(
r
Sx> `}
r
SL? `
H
0h ? 3380___PPT10.8P
$
$(
r
SL `}
r
SXM `
H
0h ? 3380___PPT10.8[$
$(
r
S@Y `}
r
SZ `
H
0h ? 3380___PPT10.9`ɻ$
$(
r
S@m `}
r
Sn `
H
0h ? 3380___PPT10.9P#^P$
$(
r
S `
r
S\ `
H
0h ? 3380___PPT10.:K:
:(
r
S `}
S `
"p`PpH
0h ? 3380___PPT10.;WC$
$(
r
S `}
r
S `
H
0h ? 3380___PPT10.;O$
$(
r
S `}
r
S `
H
0h ? 3380___PPT10.=/9$
$(
r
S `}
r
S` `
H
0h ? 3380___PPT10.=8$
$(
r
S `}
r
S( `
H
0h ? 3380___PPT10.@
(
r
SL `}
r
S P
s*<"`
1C 2
s*"`
1A 2
s*<"`
1B 2
s*"`
1A 2
s*"`
1B 2
s*"`
1C 2LB
c$D`LB
c$D
0
>Start: ON(C,A) 2
0
KGoal: ON(B,C) and ON(A,B) 2
0"`0
7ON(B,C) 2
0"`P
P
=
CON(B,C) and ON(A,B) 2
0"`
7ON(B,C) 2
0"`0
7ON(A,B) 2
0|"`@0`-
8CLEAR(A) 2
0!"`@ -
7ON(A,B) 2
0%"``}
8CLEAR(A) 2
0)"` }
7ON(A,B) 2LB
@
c$D@0LB
c$D@ 0LB
@
c$D
P@LB
c$D
P@LB
c$D
00LB
c$D0LB
c$D0H
0h ? 3380___PPT10.A Z$
@$(
r
S8 `}
r
S(@ `
H
0h ? 3380___PPT10.B$
P$(
r
S @``B
#H
0o
? `ZB
$H
s*1
? `ZB
%H
s*1
? ]`]`B
&H
0o
? ``B
'H
0o
? ZB
(H
s*1
?ZB
)H
s*1
?`B
*H
0o
?``H
H0h ? 3380___PPT10. :$
PT$(
Tr
T S `}
r
T Sp" `
H
T0h ? 3380___PPT10.3:
`X:(
Xr
X SdD `}
X SG `
"p`PpH
X0h ? 3380___PPT10.]o
0@(
X
C
Sl
0
H
0h ? 3380___PPT10.`;
00(
0X
0 C
0 S
0
H
00h ? 3380___PPT10. c
04(
4X
4 C
4 S
0
H
40h ? 3380___PPT10. c
08(
8X
8 C
8 S!
0
H
80h ? 3380___PPT10. c
0<(
<X
< C
< S:
0
H
<0h ? 3380___PPT10. c
0@(
@X
@ C
@ SPN
0
H
@0h ? 3380___PPT10. c
0D(
DX
D C
D Sc
0
H
D0h ? 3380___PPT10. c
0 H(
HX
H C
H Sv
0
H
H0h ? 3380___PPT10. c
0@P(
PX
P C
P S0
0
H
P0h ? 3380___PPT10.,v
0l(
lX
l C
l S~
0
H
l0h ? 3380___PPT10.@
0p(
pX
p C
p Sl
0
H
p0h ? 3380___PPT10.
0t(
tX
t C
t S
0
H
t0h ? 3380___PPT10.
0|(
|X
| C
| S
0
H
|0h ? 3380___PPT10.O
0(
X
C
S
0
H
0h ? 3380___PPT10.@
0P(
X
C
Ss
0
H
0h ? 3380___PPT10.Y
0`(
X
C
Sh
0
H
0h ? 3380___PPT10.Y
0p(
X
C
S
0
H
0h ? 3380___PPT10.Y
0(
X
C
S(
0
H
0h ? 3380___PPT10.<:;
0 (
X
C
S;
0
H
0h ? 3380___PPT10.<;
00(
X
C
SJ
0
H
0h ? 3380___PPT10.<;
0@(
X
C
SV
0
H
0h ? 3380___PPT10.<;
0P(
X
C
Sj
0
H
0h ? 3380___PPT10.<;
0`(
X
C
S}
0
H
0h ? 3380___PPT10.<;
0p(
X
C
Sh
0
H
0h ? 3380___PPT10.<;
0(
X
C
S
0
H
0h ? 3380___PPT10.<;
0(
X
C
S@
0
H
0h ? 3380___PPT10.<;
0(
X
C
S
0
H
0h ? 3380___PPT10.=
0(
X
C
Sp
0
H
0h ? 3380___PPT10.=*
0(
X
C
S(
0
H
0h ? 3380___PPT10.BQ
0 (
X
C
Sp<
0
H
0h ? 3380___PPT10.BQ
00(
X
C
S
0
H
0h ? 3380___PPT10.BQ
0p(
X
C
SO
0
H
0h ? 3380___PPT10.F0p
0 (
X
C
Sg
0
H
0h ? 3380___PPT10.F0p
!
0$(
$X
$ C
$ S<}
0
H
$0h ? 3380___PPT10.F0p
"
04(
4X
4 C
4 SP
0
H
40h ? 3380___PPT10.F dN#
08(
8X
8 C
8 S0
0
H
80h ? 3380___PPT10.F dN$
0<(
<X
< C
< S
0
H
<0h ? 3380___PPT10.F dN%
0D(
DX
D C
D S
0
H
D0h ? 3380___PPT10.څt&
0@P(
PX
P C
P S
0
H
P0h ? 3380___PPT10.+rP0n4~2x`΄&R~tJLNPRTVY[^(]<_Padc$fxegik-Y 5
wmoqtv,x@zT|h~|'7'*4,̈`.020D4XR9F2Hl(?
Sn(
/0LDArialy0z[ 0@.
@n?" dd
On-screen Shown-shzm/)A
1ArialDefault Design$Problems, Problem Spaces and Search Contents%To build a system to solve a problem+Defining the problem as State Space SearchExample: Playing ChessPlaying chess-Defining chess problem as State Space searchWater Jug Problem'Production rules for Water Jug ProblemProduction rulesTo solve the water jug problem"Formal Description of the problemProduction SystemsProduction systemControl StrategiesBreadth First SearchBFS Tree for Water Jug problemAlgorithm: Depth First Search
Backtracking!Advantages of Depth-First SearchAdvantages of BFSTSPBranch and BoundHeuristic SearchNearest Neighbour HeuristicHeuristic Function#Example Simple Heuristic functionsProblem CharacteristicsIs the problem Decomposable?Blocks World Problem)Can Solution Steps be ignored or undone?Is the universe Predictable?)Is a good solution absolute or relative?#Is the solution a state or a path?What is the role of knowledge?1Does the task require Interaction with a person?Problem Classification"Production System CharacteristicsMonotonic Production SystemsCommutative Production system!Partially Commutative, Monotonic%Non Monotonic, Partially CommutativeNot partially CommutativeNon %Four Categ+_DzSuthikshn Kumar.C.RSuthikshn Kumar.C.Rories of Production System(Issues in the design of search programsSummaryFonts UsedDesign Template
Slide Titles/0(`YT
MM5 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQR,TUVWX0AA@Iʚ;ʚ;g4BdBd z[ 0vppp@<4ddddL 0|y<4BdBdL< 0
0___PPT10
___PPT9D$,(( 9b#Problems, Problem Spaces and SearchDr. Suthikshn Kumar Contents4Defining the problem as a State Space Search
Production Systems
Control Strategies
Breadth First Search
Depth First Search
Heuristic Search
Problem Characteristics
Is the Problem Decomposable?
Can Solution Steps be ignored or undone?
Production system characteristics
Issues in the design of search programs
5Z5$To build a system to solve a problem%%(Define the problem precisely
Analyse the problem
Isolate and represent the task knowledge that is necessary to solve the problem
Choose the best problem-solving techniques and apply it to the particular problem." *Defining the problem as State Space Search++(The state space representation forms the basis of most of the AI methods.
Its structure corresponds to the structure of problem solving in two important ways:
It allows for a formal definition of a problem as the need to convert some given situation into some desired situation using a set of permissible operations.
It permits us to define the process of solving a particular problem as a combination of known techniques (each represented as a rule defining a single step in the space) and search, the general technique of exploring the space to try to find some path from current state to a goal state.
Search is a very important process in the solution of hard problems for which no more direct techniques are available..Z5Z5Example: Playing ChessTo build a program that could play chess , we could first have to specify the starting position of the chess board, the rules that define the legal moves, and the board positions that represent a win for one side or the other.
In addition, we must make explicit the previously implicit goal of not only playing the legal game of chess but also winning the game, if possible,
zz
Playing chessThe starting position can be described as an 8by 8 array where each position contains a symbol for appropriate piece.
We can define as our goal the check mate position.
The legal moves provide the way of getting from initial state to a goal state.
They can be described easily as a set of rules consisting of two parts:
A left side that serves as a pattern to be matched against the current board position.
And a right side that describes the change to be made to reflect the move
However, this approach leads to large number of rules 10120 board positions !!
Using so many rules poses problems such as:
No person could ever supply a complete set of such rules.
No program could easily handle all those rules. Just storing so many rules poses serious difficulties.vAPP{PPA8
?
,Defining chess problem as State Space search--(We need to write the rules describing the legal moves in as general a way as possible.
For example:
White pawn at Square( file e, rank 2) AND Square( File e, rank 3) is empty AND Square(file e, rank 4) is empty, then move the pawn from Square( file e, rank 2) to Square( file e, rank 4).
In general, the more succintly we can describe the rules we need, the less work we will have to do to provide them and more efficient the program.BdZZZd,w uWater Jug Problem9The state space for this problem can be described as the set of ordered pairs of integers (x,y) such that x = 0, 1,2, 3 or 4 and y = 0,1,2 or 3; x represents the number of gallons of water in the 4-gallon jug and y represents the quantity of water in 3-gallon jug
The start state is (0,0)
The goal state is (2,n)
:Z:[&Production rules for Water Jug Problem''(KThe operators to be used to solve the problem can be described as follows:
LK Production rules
To solve the water jug problemRequired a control structure that loops through a simple cycle in which some rule whose left side matches the current state is chosen, the appropriate change to the state is made as described in the corresponding right side, and the resulting state is checked to see if it corresponds to goal state.
One solution to the water jug problem
Shortest such sequence will have a impact on the choice of appropriate mechanism to guide the search for solution.
(Z!Formal Description of the problem""(Define a state space that contains all the possible configurations of the relevant objects.
Specify one or more states within that space that describe possible situations from which the problem solving process may start ( initial state)
Specify one or more states that would be acceptable as solutions to the problem. ( goal states)
Specify a set of rules that describe the actions ( operations) available. " PProduction Systems~A production system consists of:
A set of rules, each consisting of a left side that determines the applicability of the rule and a right side that describes the operation to be performed if that rule is applied.
One or more knowledge/databases that contain whatever information is appropriate for the particular task. Some parts of the database may be permanent, while other parts of it may pertain only to the solution of the current problem.
A control strategy that specifies the order in which the rules will be compared to the database and a way of resolving the conflicts that arise when several rules match at once.
A rule applier$!P^P
Production systemTInorder to solve a problem:
We must first reduce it to one for which a precise statement can be given. This can be done by defining the problem s state space ( start and goal states) and a set of operators for moving that space.
The problem can then be solved by searching for a path through the space from an initial state to a goal state.
The process of solving the problem can usefully be modelled as a production system. $PP$Control StrategiesHow to decide which rule to apply next during the process of searching for a solution to a problem?
The two requirements of good control strategy are that
it should cause motion.
It should be systematic&00
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~,Root EntrydO))
Current User1YSummaryInformation(TPowerPoint Document(hzDocumentSummaryInformation8t@ @@``0(`YT
MM5 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQR,TUVWX0AA@Iʚ;ʚ;g4BdBd z[ 0vppp@<4ddddL 0|y<4BdBdL< 0
0___PPT10
___PPT9D$,(( 9b#Problems, Problem Spaces and SearchDr. Suthikshn Kumar Contents4Defining the problem as a State Space Search
Production Systems
Control Strategies
Breadth First Search
Depth First Search
Heuristic Search
Problem Characteristics
Is the Problem Decomposable?
Can Solution Steps be ignored or undone?
Production system characteristics
Issues in the design of search programs
5Z5$To build a system to solve a problem%%(Define the problem precisely
Analyse the problem
Isolate and represent the task knowledge that is necessary to solve the problem
Choose the best problem-solving techniques and apply it to the particular problem." *Defining the problem as State Space Search++(The state space representation forms the basis of most of the AI methods.
Its structure corresponds to the structure of problem solving in two important ways:
It allows for a formal definition of a problem as the need to convert some given situation into some desired situation using a set of permissible operations.
It permits us to define the process of solving a particular problem as a combination of known techniques (each represented as a rule defining a single step in the space) and search, the general technique of exploring the space to try to find some path from current state to a goal state.
Search is a very important process in the solution of hard problems for which no more direct techniques are available..Z5Z5Example: Playing ChessTo build a program that could play chess , we could first have to specify the starting position of the chess board, the rules that define the legal moves, and the board positions that represent a win for one side or the other.
In addition, we must make explicit the previously implicit goal of not only playing the legal game of chess but also winning the game, if possible,
zz
Playing chessThe starting position can be described as an 8by 8 array where each position contains a symbol for appropriate piece.
We can define as our goal the check mate position.
The legal moves provide the way of getting from initial state to a goal state.
They can be described easily as a set of rules consisting of two parts:
A left side that serves as a pattern to be matched against the current board position.
And a right side that describes the change to be made to reflect the move
However, this approach leads to large number of rules 10120 board positions !!
Using so many rules poses problems such as:
No person could ever supply a complete set of such rules.
No program could easily handle all those rules. Just storing so many rules poses serious difficulties.vAPP{PPA8
?
,Defining chess problem as State Space search--(We need to write the rules describing the legal moves in as general a way as possible.
For example:
White pawn at Square( file e, rank 2) AND Square( File e, rank 3) is empty AND Square(file e, rank 4) is empty, then move the pawn from Square( file e, rank 2) to Square( file e, rank 4).
In general, the more succintly we can describe the rules we need, the less work we will have to do to provide them and more efficient the program.BdZZZd,w uWater Jug Problem9The state space for this problem can be described as the set of ordered pairs of integers (x,y) such that x = 0, 1,2, 3 or 4 and y = 0,1,2 or 3; x represents the number of gallons of water in the 4-gallon jug and y represents the quantity of water in 3-gallon jug
The start state is (0,0)
The goal state is (2,n)
:Z:[&Production rules for Water Jug Problem''(KThe operators to be used to solve the problem can be described as follows:
LK Production rules
To solve the water jug problemRequired a control structure that loops through a simple cycle in which some rule whose left side matches the current state is chosen, the appropriate change to the state is made as described in the corresponding right side, and the resulting state is checked to see if it corresponds to goal state.
One solution to the water jug problem
Shortest such sequence will have a impact on the choice of appropriate mechanism to guide the search for solution.
(Z!Formal Description of the problem""(Define a state space that contains all the possible configurations of the relevant objects.
Specify one or more states within that space that describe possible situations from which the problem solving process may start ( initial state)
Specify one or more states that would be acceptable as solutions to the problem. ( goal states)
Specify a set of rules that describe the actions ( operations) available. " P
!"#$%&'*+-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Production Systems~A production system consists of:
A set of rules, each consisting of a left side that determines the applicability of the rule and a right side that describes the operation to be performed if that rule is applied.
One or more knowledge/databases that contain whatever information is appropriate for the particular task. Some parts of the database may be permanent, while other parts of it may pertain only to the solution of the current problem.
A control strategy that specifies the order in which the rules will be compared to the database and a way of resolving the conflicts that arise when several rules match at once.
A rule applier$!P^P
Production systemTInorder to solve a problem:
We must first reduce it to one for which a precise statement can be given. This can be done by defining the problem s state space ( start and goal states) and a set of operators for moving that space.
The problem can then be solved by searching for a path through the space from an initial state to a goal state.
The process of solving the problem can usefully be modelled as a production system. $PP$Control StrategiesHow to decide which rule to apply next during the process of searching for a solution to a problem?
The two requirements of good control strategy are that
it should cause motion.
It should be systematic&00 Breadth First SearchAlgorithm:
Create a variable called NODE-LIST and set it to initial state
Until a goal state is found or NODE-LIST is empty do
Remove the first element from NODE-LIST and call it E. If NODE-LIST was empty, quit
For each way that each rule can match the state described in E do:
Apply the rule to generate a new state
If the new state is a goal state, quit and return this state
Otherwise, add the new state to the end of NODE-LISTpt t!BFS Tree for Water Jug problem(
&Algorithm: Depth First SearchYIf the initial state is a goal state, quit and return success
Otherwise, do the following until success or failure is signaled:
Generate a successor, E, of initial state. If there are no more successors, signal failure.
Call Depth-First Search, with E as the initial state
If success is returned, signal success. Otherwise continue in this loop.:" Z" Z'BacktrackingIn this search, we pursue a singal branch of the tree until it yields a solution or until a decision to terminate the path is made.
It makes sense to terminate a path if it reaches dead-end, produces a previous state. In such a state backtracking occurs
Chronological Backtracking: Order in which steps are undone depends only on the temporal sequence in which steps were initially made.
Specifically most recent step is always the first to be undone.
This is also simple backtracking.Z( Advantages of Depth-First Search!!(DFS requires less memory since only the nodes on the current path are stored.
By chance, DFS may find a solution without examining much of the search space at all. )Advantages of BFSBFS will not get trapped exploring a blind alley.
If there is a solution, BFS is guarnateed to find it.
If there are multiple solutions, then a minimal solution will be found.Q
V*TSPA simple motion causing and systematic control structure could solve this problem.
Simply explore all possible paths in the tree and return the shortest path.
If there are N cities, then number of different paths among them is 1.2& .(N-1) or (N-1)!
The time to examine single path is proportional to N
So the total time required to perform this search is proportional to N!
For 10 cities, 10! = 3,628,800
This phenomenon is called Combinatorial explosion.Z+Branch and BoundkBegin generating complete paths, keeping track of the shortest path found so far.
Give up exploring any path as soon as its partial length becomes greater than the shortest path found so far.
Using this algorithm, we are guaranteed to find the shortest path.
It still requires exponential time.
The time it saves depends on the order in which paths are explored. lZl,Heuristic SearchA Heuristic is a technique that improves the efficiency of a search process, possibly by sacrificing claims of completeness.
Heuristics are like tour guides
They are good to the extent that they point in generally interesting directions;
They are bad to the extent that they may miss points of interest to particular individuals.
On the average they improve the quality of the paths that are explored.
Using Heuristics, we can hope to get good ( though possibly nonoptimal ) solutions to hard problems such asa TSP in non exponential time.
There are good general purpose heuristics that are useful in a wide variety of problem domains.
Special purpose heuristics exploit domain specific knowledgeP,
#-Nearest Neighbour Heuristic It works by selecting locally superior alternative at each step.
Applying to TSP:
Arbitrarily select a starting city
To select the next city, look at all cities not yet visited and select the one closest to the current city. Go to next step.
Repeat step 2 until all cities have been visited.
This procedure executes in time proportional to N2
It is possible to prove an upper bound on the error it incurs. This provides reassurance that one is not paying too high a price in accuracy for speed.lRZ Z ZR1
.Heuristic FunctionAThis is a function that maps from problem state descriptions to measures of desirsability, usually represented as numbers.
Which aspects of the problem state are considered,
how those aspects are evaluated, and
the weights given to individual aspects are chosen in such a way that
the value of the heuristic function at a given node in the search process gives as good an estimate as possible of whether that node is on the desired path to a solution.
Well designed heuristic functions can play an important part in efficiently guiding a search process toward a solution.
B{ZZ&Z{&L
8"Example Simple Heuristic functions##(Chess : The material advantage of our side over opponent.
TSP: the sum of distances so far
Tic-Tac-Toe: 1 for each row in which we could win and in we already have one piece plus 2 for each such row in we have two pieces_{9Problem CharacteristicsInorder to choose the most appropriate method for a particular problem, it is necessary to analyze the problem along several key dimensions:
Is the problem decomposable into a set of independent smaller or easier subproblems?
Can solution steps be ignored or at least undone if they prove unwise?
Is the problem s universe predictable?
Is a good solution to the problem obvious without comparison to all other possible solutions?
Is the desired solution a state of the world or a path to a state?
Is a large amount of knowledge absolutely required to solve the problem or is knowledge important only to constrain the search?
Can a computer that is simply given the problem return the solution or will the solution of the problem require interaction between the computer and a person?.PP$0;Is the problem Decomposable?Whether the problem can be decomposed into smaller problems?
Using the technique of problem decomposition, we can often solve very large problems easily.<Blocks World ProblemFollowing operators are available:
CLEAR(x) [ block x has nothing on it]-> ON(x, Table)
CLEAR(x) and CLEAR(y) -> ON(x,y) [ put x on y]b#! ?(Can Solution Steps be ignored or undone?))(.Suppose we are trying to prove a math theorem.We can prove a lemma. If we find the lemma is not of any help, we can still continue.
8-puzzle problem
Chess: A move cannot be taken back.
Important classes of problems:
Ignorable ( theorem proving)
Recoverable ( 8-puzzle)
Irrecoverable ( Chess)
The recoverability of a problem plays an important role in determining the complexity of the control structure necessary for the problem s solution.
Ignorable problems can be solved using a simple control structure that never backtracks
Recoverable problems can be solved by a slightly more complicated control strategy that does sometimes make mistakes
Irrecoverable problems will need to be solved by systems that expends a great deal of effort making each decision since decision must be final.
tPLPP]PPL]&
@ Is the universe Predictable?Certain Outcome ( ex: 8-puzzle)
Uncertain Outcome ( ex: Bridge, controlling a robot arm)
For solving certain outcome problems, open loop approach ( without feedback) will work fine.
For uncertain-outcome problems, planning can at best generate a sequence of operators that has a good probability of leading to a solution. We need to allow for a process of plan revision to take place.ZA!(Is a good solution absolute or relative?))(Any path problem
Best path problem
Any path problems can often be solved in a reasonable amount of time by using heuristics that suggest good paths to explore.
Best path problems are computationally harder.
ZE""Is the solution a state or a path?lExamples:
Finding a consistent interpretation for the sentence The bank president ate a dish of pasta salad with the fork . We need to find the interpretation but not the record of the processing.
Water jug : Here it is not sufficient to report that we have solved , but the path that we found to the state (2,0). Thus the a statement of a solution to this problem must be a sequence of operations ( Plan) that produces the final state.
X
6:=F#What is the role of knowledge?Two examples:
Chess: Knowledge is required to constrain the search for a solution
Newspaper story understanding: Lot of knowledge is required even to be able to recognize a solution.
Consider a problem of scanning daily newspapers to decide which are supporting the democrats and which are supporting the republicans in some election. We need lots of knowledge to answer such questions as:
The names of the candidates in each party
The facts that if the major thing you want to see done is have taxes lowered, you are probably supporting the republicans
The fact that if the major thing you want to see done is improved education for minority students, you are probably supporting the democrats.
etc\PPP7P7G$0Does the task require Interaction with a person?11(The programs require intermediate interaction with people for additional inputs and to provided reassurance to the user.
There are two types of programs:
Solitary
Conversational:
Decision on using one of these approaches will be important in the choice of problem solving method.
<ZZgZgN%Problem Classification/There are several broad classes into which the problems fall. These classes can each be associated with generic control strategy that is appropriate for solving the problems:
Classification : ex: medical diagnostics, diagnosis of faults in mechanical devices
Propose and Refine: ex: design and planning
&=!Production System Characteristics""(Can production systems, like problems, be described by a set of characteristics that shed some light on how they can easily be implemented?
If so, what relationships are there between problem types and the types of production systems best suited to solving the problems?
Classes of Production systems:
Monotonic Production System: the application of a rule never prevents the later application of another rule that could also have been applied at the time the first rule was selected.
Non-Monotonic Production system
Partially commutative Production system: property that if application of a particular sequence of rules transforms state x to state y, then permutation of those rules allowable, also transforms state x into state y.
Commutative Production systemL" PPPP&$Four Categories of Production System%%(Q''Issues in the design of search programs(((The direction in which to conduct the search ( forward versus backward reasoning).
How to select applicable rules ( Matching)
How to represent each node of the search process ( knowledge representation problem)R(SummaryFour steps for designing a program to solve a problem:
Define the problem precisely
Analyse the problem
Identify and represent the knowledge required by the task
Choose one or more techniques for problem solving and apply those techniques to the problem.
,7 7,T/|
"
#$%/01234567:>BCDHI J!K"L#M$O%S&T'U($
'PT$(
Tr
T S `}
r
T Sp" `
H
T0h ? 3380___PPT10.3:
(`X:(
Xr
X SdD `}
X SG `
"p`PpH
X0h ? 3380___PPT10.]o'
0p\(
\X
\ C
\ S|
0
H
\0h ? 3380___PPT10.`H((
0`(
`X
` C
` S
0
H
`0h ? 3380___PPT10.`H(r Q
T 8L(?
`Un(
/0LDArialy0z[ 0@.
@n?" dd@ @@``
!"#$%&'()*+,-./03245Oh+'0$`hx
Slide 1Suthikshn Kumar.C.RSuthikshn Kumar.C.R23hMicrosoft PowerPointP@ 1.@ "@0:
Gg ---@ !--'@Arial-. -2
+Problems, Problem Spaces )"""3)"""3)"!"."System-@Arial-. 2
uW
and Search""")""".-@Arial-.
2
'Dr. .-@Arial-. 2
n Suthikshnh
.-@Arial-. 2
>Kumar&.-՜.+,0D
Breadth First SearchAlgorithm:
Create a variable called NODE-LIST and set it to initial state
Until a goal state is found or NODE-LIST is empty do
Remove the first element from NODE-LIST and call it E. If NODE-LIST was empty, quit
For each way that each rule can match the state described in E do:
Apply the rule to generate a new state
If the new state is a goal state, quit and return this state
Otherwise, add the new state to the end of NODE-LISTpt t!BFS Tree for Water Jug problem(
&Algorithm: Depth First SearchYIf the initial state is a goal state, quit and return success
Otherwise, do the following until success or failure is signaled:
Generate a successor, E, of initial state. If there are no more successors, signal failure.
Call Depth-First Search, with E as the initial state
If success is returned, signal success. Otherwise continue in this loop.:" Z" Z'BacktrackingIn this search, we pursue a singal branch of the tree until it yields a solution or until a decision to terminate the path is made.
It makes sense to terminate a path if it reaches dead-end, produces a previous state. In such a state backtracking occurs
Chronological Backtracking: Order in which steps are undone depends only on the temporal sequence in which steps were initially made.
Specifically most recent step is always the first to be undone.
This is also simple backtracking.Z( Advantages of Depth-First Search!!(DFS requires less memory since only the nodes on the current path are stored.
By chance, DFS may find a solution without examining much of the search space at all. )Advantages of BFSBFS will not get trapped exploring a blind alley.
If there is a solution, BFS is guarnateed to find it.
If there are multiple solutions, then a minimal solution will be found.Q
V*TSPA simple motion causing and systematic control structure could solve this problem.
Simply explore all possible paths in the tree and return the shortest path.
If there are N cities, then number of different paths among them is 1.2& .(N-1) or (N-1)!
The time to examine single path is proportional to N
So the total time required to perform this search is proportional to N!
For 10 cities, 10! = 3,628,800
This phenomenon is called Combinatorial explosion.Z+Branch and BoundkBegin generating complete paths, keeping track of the shortest path found so far.
Give up exploring any path as soon as its partial length becomes greater than the shortest path found so far.
Using this algorithm, we are guaranteed to find the shortest path.
It still requires exponential time.
The time it saves depends on the order in which paths are explored. lZl,Heuristic SearchA Heuristic is a technique that improves the efficiency of a search process, possibly by sacrificing claims of completeness.
Heuristics are like tour guides
They are good to the extent that they point in generally interesting directions;
They are bad to the extent that they may miss points of interest to particular individuals.
On the average they improve the quality of the paths that are explored.
Using Heuristics, we can hope to get good ( though possibly nonoptimal ) solutions to hard problems such asa TSP in non exponential time.
There are good general purpose heuristics that are useful in a wide variety of problem domains.
Special purpose heuristics exploit domain specific knowledgeP,
#-Nearest Neighbour Heuristic It works by selecting locally superior alternative at each step.
Applying to TSP:
Arbitrarily select a starting city
To select the next city, look at all cities not yet visited and select the one closest to the current city. Go to next step.
Repeat step 2 until all cities have been visited.
This procedure executes in time proportional to N2
It is possible to prove an upper bound on the error it incurs. This provides reassurance that one is not paying too high a price in accuracy for speed.lRZ Z ZR1
.Heuristic FunctionAThis is a function that maps from problem state descriptions to measures of desirsability, usually represented as numbers.
Which aspects of the problem state are considered,
how those aspects are evaluated, and
the weights given to individual aspects are chosen in such a way that
the value of the heuristic function at a given node in the search process gives as good an estimate as possible of whether that node is on the desired path to a solution.
Well designed heuristic functions can play an important part in efficiently guiding a search process toward a solution.
B{ZZ&Z{&L
8"Example Simple Heuristic functions##(Chess : The material advantage of our side over opponent.
TSP: the sum of distances so far
Tic-Tac-Toe: 1 for each row in which we could win and in we already have one piece plus 2 for each such row in we have two pieces_{9Problem CharacteristicsInorder to choose the most appropriate method for a particular problem, it is necessary to analyze the problem along several key dimensions:
Is the problem decomposable into a set of independent smaller or easier subproblems?
Can solution steps be ignored or at least undone if they prove unwise?
Is the problem s universe predictable?
Is a good solution to the problem obvious without comparison to all other possible solutions?
Is the desired solution a state of the world or a path to a state?
Is a large amount of knowledge absolutely required to solve the problem or is knowledge important only to constrain the search?
Can a computer that is simply given the problem return the solution or will the solution of the problem require interaction between the computer and a person?.PP$0;Is the problem Decomposable?Whether the problem can be decomposed into smaller problems?
Using the technique of problem decomposition, we can often solve very large problems easily.<Blocks World ProblemFollowing operators are available:
CLEAR(x) [ block x has nothing on it]-> ON(x, Table)
CLEAR(x) and CLEAR(y) -> ON(x,y) [ put x on y]b#! ?(Can Solution Steps be ignored or undone?))(.Suppose we are trying to prove a math theorem.We can prove a lemma. If we find the lemma is not of any help, we can still continue.
8-puzzle problem
Chess: A move cannot be taken back.
Important classes of problems:
Ignorable ( theorem proving)
Recoverable ( 8-puzzle)
Irrecoverable ( Chess)
The recoverability of a problem plays an important role in determining the complexity of the control structure necessary for the problem s solution.
Ignorable problems can be solved using a simple control structure that never backtracks
Recoverable problems can be solved by a slightly more complicated control strategy that does sometimes make mistakes
Irrecoverable problems will need to be solved by systems that expends a great deal of effort making each decision since decision must be final.
tPLPP]PPL]&
@ Is the universe Predictable?Certain Outcome ( ex: 8-puzzle)
Uncertain Outcome ( ex: Bridge, controlling a robot arm)
For solving certain outcome problems, open loop approach ( without feedback) will work fine.
For uncertain-outcome problems, planning can at best generate a sequence of operators that has a good probability of leading to a solution. We need to allow for a process of plan revision to take place.ZA!(Is a good solution absolute or relative?))(Any path problem
Best path problem
Any path problems can often be solved in a reasonable amount of time by using heuristics that suggest good paths to explore.
Best path problems are computationally harder.
ZE""Is the solution a state or a path?lExamples:
Finding a consistent interpretation for the sentence The bank president ate a dish of pasta salad with the fork . We need to find the interpretation but not the record of the processing.
Water jug : Here it is not sufficient to report that we have solved , but the path that we found to the state (2,0). Thus the a statement of a solution to this problem must be a sequence of operations ( Plan) that produces the final state.
X
6:=F#What is the role of knowledge?Two examples:
Chess: Knowledge is required to constrain the search for a solution
Newspaper story understanding: Lot of knowledge is required even to be able to recognize a solution.
Consider a problem of scanning daily newspapers to decide which are supporting the democrats and which are supporting the republicans in some election. We need lots of knowledge to answer such questions as:
The names of the candidates in each party
The facts that if the major thing you want to see done is have taxes lowered, you are probably supporting the republicans
The fact that if the major thing you want to see done is improved education for minority students, you are probably supporting the democrats.
etc\PPP7P7G$0Does the task require Interaction with a person?11(The programs require intermediate interaction with people for additional inputs and to provided reassurance to the user.
There are two types of programs:
Solitary
Conversational:
Decision on using one of these approaches will be important in the choice of problem solving method.
<ZZgZgN%Problem Classification/There are several broad classes into which the problems fall. These classes can each be associated with generic control strategy that is appropriate for solving the problems:
Classification : ex: medical diagnostics, diagnosis of faults in mechanical devices
Propose and Refine: ex: design and planning
&=!Production System Characteristics""(Can production systems, like problems, be described by a set of characteristics that shed some light on how they can easily be implemented?
If so, what relationships are there between problem types and the types of production systems best suited to solving the problems?
Classes of Production systems:
Monotonic Production System: the application of a rule never prevents the later application of another rule that could also have been applied at the time the first rule was selected.
Non-Monotonic Production system
Partially commutative Production system: property that if application of a particular sequence of rules transforms state x to state y, then permutation of those rules allowable, also transforms state x into state y.
Commutative Production systemL" PPPP&$Four Categories of Production System%%(Q''Issues in the design of search programs(((The direction in which to conduct the search ( forward versus backward reasoning).
How to select applicable rules ( Matching)
How to represent each node of the search process ( knowledge representation problem)R(SummaryFour steps for designing a program to solve a problem:
Define the problem precisely
Analyse the problem
Identify and represent the knowledge required by the task
Choose one or more techniques for problem solving and apply those techniques to the problem.
,7 7,T/|
"
#$%/01234567:>BCDHI J!K"L#M$O%S&T'U(r(?
zUn(
/0LDArialy0z[ 0@.
@n?" dd@ @@``0(`YT
MM5 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQR,TUVWX0AA@Eʚ;ʚ;g4DdDd z[ 0ppp@<4ddddL 0|y<4BdBdL< 00___PPT10
___PPT9D$,((9b#Problems, Problem Spaces and SearchDr. Suthikshn Kumar Contents4Defining the problem as a State Space Search
Production Systems
Control Strategies
Breadth First Search
Depth First Search
Heuristic Search
Problem Characteristics
Is the Problem Decomposable?
Can Solution Steps be ignored or undone?
Production system characteristics
Issues in the design of search programs
5Z5$To build a system to solve a problem%%(Define the problem precisely
Analyse the problem
Isolate and represent the task knowledge that is necessary to solve the problem
Choose the best problem-solving techniques and apply it to the particular problem." *Defining the problem as State Space Search++(The state space representation forms the basis of most of the AI methods.
Its structure corresponds to the structure of problem solving in two important ways:
It allows for a formal definition of a problem as the need to convert some given situation into some desired situation using a set of permissible operations.
It permits us to define the process of solving a particular problem as a combination of known techniques (each represented as a rule defining a single step in the space) and search, the general technique of exploring the space to try to find some path from current state to a goal state.
Search is a very important process in the solution of hard problems for which no more direct techniques are available..Z5Z5Example: Playing ChessTo build a program that could play chess , we could first have to specify the starting position of the chess board, the rules that define the legal moves, and the board positions that represent a win for one side or the other.
In addition, we must make explicit the previously implicit goal of not only playing the legal game of chess but also winning the game, if possible,
zz
Playing chessThe starting position can be described as an 8by 8 array where each position contains a symbol for appropriate piece.
We can define as our goal the check mate position.
The legal moves provide the way of getting from initial state to a goal state.
They can be described easily as a set of rules consisting of two parts:
A left side that serves as a pattern to be matched against the current board position.
And a right side that describes the change to be made to reflect the move
However, this approach leads to large number of rules 10120 board positions !!
Using so many rules poses problems such as:
No person could ever supply a complete set of such rules.
No program could easily handle all those rules. Just storing so many rules poses serious difficulties.vAPP{PPA8
?
,Defining chess problem as State Space search--(We need to write the rules describing the legal moves in as general a way as possible.
For example:
White pawn at Square( file e, rank 2) AND Square( File e, rank 3) is empty AND Square(file e, rank 4) is empty, then move the pawn from Square( file e, rank 2) to Square( file e, rank 4).
In general, the more succintly we can describe the rules we need, the less work we will have to do to provide them and more efficient the program.BdZZZd,w uWater Jug Problem9The state space for this problem can be described as the set of ordered pairs of integers (x,y) such that x = 0, 1,2, 3 or 4 and y = 0,1,2 or 3; x represents the number of gallons of water in the 4-gallon jug and y represents the quantity of water in 3-gallon jug
The start state is (0,0)
The goal state is (2,n)
:Z:[&Production rules for Water Jug Problem''(KThe operators to be used to solve the problem can be described as follows:
LK Production rules
To solve the water jug problemRequired a control structure that loops through a simple cycle in which some rule whose left side matches the current state is chosen, the appropriate change to the state is made as described in the corresponding right side, and the resulting state is checked to see if it corresponds to goal state.
One solution to the water jug problem
Shortest such sequence will have a impact on the choice of appropriate mechanism to guide the search for solution.
(Z!Formal Description of the problem""(Define a state space that contains all the possible configurations of the relevant objects.
Specify one or more states within that space that describe possible situations from which the problem solving process may start ( initial state)
Specify one or more states that would be acceptable as solutions to the problem. ( goal states)
Specify a set of rules that describe the actions ( operations) available. " PProduction Systems~A production system consists of:
A set of rules, each consisting of a left side that determines the applicability of the rule and a right side that describes the operation to be performed if that rule is applied.
One or more knowledge/databases that contain whatever information is appropriate for the particular task. Some parts of the database may be permanent, while other parts of it may pertain only to the solution of the current problem.
A control strategy that specifies the order in which the rules will be compared to the database and a way of resolving the conflicts that arise when several rules match at once.
A rule applier$!P^P
Production systemTInorder to solve a problem:
We must first reduce it to one for which a precise statement can be given. This can be done by defining the problem s state space ( start and goal states) and a set of operators for moving that space.
The problem can then be solved by searching for a path through the space from an initial state to a goal state.
The process of solving the problem can usefully be modelled as a production system. $PP$Control StrategiesHow to decide which rule to apply next during the process of searching for a solution to a problem?
The two requirements of good control strategy are that
it should cause motion.
It should be systematic&00 Breadth First SearchAlgorithm:
Create a variable called NODE-LIST and set it to initial state
Until a goal state is found or NODE-LIST is empty do
Remove the first element from NODE-LIST and call it E. If NODE-LIST was empty, quit
For each way that each rule can match the state described in E do:
Apply the rule to generate a new state
If the new state is a goal state, quit and return this state
Otherwise, add the new state to the end of NODE-LISTpt t!BFS Tree for Water Jug problem(
&Algorithm: Depth First SearchYIf the initial state is a goal state, quit and return success
Otherwise, do the following until success or failure is signaled:
Generate a successor, E, of initial state. If there are no more successors, signal failure.
Call Depth-First Search, with E as the initial state
If success is returned, signal success. Otherwise continue in this loop.:" Z" Z'BacktrackingIn this search, we pursue a singal branch of the tree until it yields a solution or until a decision to terminate the path is made.
It makes sense to terminate a path if it reaches dead-end, produces a previous state. In such a state backtracking occurs
Chronological Backtracking: Order in which steps are undone depends only on the temporal sequence in which steps were initially made.
Specifically most recent step is always the first to be undone.
This is also simple backtracking.Z( Advantages of Depth-First Search!!(DFS requires less memory since only the nodes on the current path are stored.
By chance, DFS may find a solution without examining much of the search space at all. )Advantages of BFSBFS will not get trapped exploring a blind alley.
If there is a solution, BFS is guarnateed to find it.
If there are multiple solutions, then a minimal solution will be found.Q
V*TSPA simple motion causing and systematic control structure could solve this problem.
Simply explore all possible paths in the tree and return the shortest path.
If there are N cities, then number of different paths among them is 1.2& .(N-1) or (N-1)!
The time to examine single path is proportional to N
So the total time required to perform this search is proportional to N!
For 10 cities, 10! = 3,628,800
This phenomenon is called Combinatorial explosion.Z+Branch and BoundkBegin generating complete paths, keeping track of the shortest path found so far.
Give up exploring any path as soon as its partial length becomes greater than the shortest path found so far.
Using this algorithm, we are guaranteed to find the shortest path.
It still requires exponential time.
The time it saves depends on the order in which paths are explored. lZl,Heuristic SearchA Heuristic is a technique that improves the efficiency of a search process, possibly by sacrificing claims of completeness.
Heuristics are like tour guides
They are good to the extent that they point in generally interesting directions;
They are bad to the extent that they may miss points of interest to particular individuals.
On the average they improve the quality of the paths that are explored.
Using Heuristics, we can hope to get good ( though possibly nonoptimal ) solutions to hard problems such asa TSP in non exponential time.
There are good general purpose heuristics that are useful in a wide variety of problem domains.
Special purpose heuristics exploit domain specific knowledgeP,
#-Nearest Neighbour Heuristic It works by selecting locally superior alternative at each step.
Applying to TSP:
Arbitrarily select a starting city
To select the next city, look at all cities not yet visited and select the one closest to the current city. Go to next step.
Repeat step 2 until all cities have been visited.
This procedure executes in time proportional to N2
It is possible to prove an upper bound on the error it incurs. This provides reassurance that one is not paying too high a price in accuracy for speed.lRZ Z ZR1
.Heuristic FunctionAThis is a function that maps from problem state descriptions to measures of desirsability, usually represented as numbers.
Which aspects of the problem state are considered,
how those aspects are evaluated, and
the weights given to individual aspects are chosen in such a way that
the value of the heuristic function at a given node in the search process gives as good an estimate as possible of whether that node is on the desired path to a solution.
Well designed heuristic functions can play an important part in efficiently guiding a search process toward a solution.
B{ZZ&Z{&L
8"Example Simple Heuristic functions##(Chess : The material advantage of our side over opponent.
TSP: the sum of distances so far
Tic-Tac-Toe: 1 for each row in which we could win and in we already have one piece plus 2 for each such row in we have two pieces_{9Problem CharacteristicsInorder to choose the most appropriate method for a particular problem, it is necessary to analyze the problem along several key dimensions:
Is the problem decomposable into a set of independent smaller or easier subproblems?
Can solution steps be ignored or at least undone if they prove unwise?
Is the problem s universe predictable?
Is a good solution to the problem obvious without comparison to all other possible solutions?
Is the desired solution a state of the world or a path to a state?
Is a large amount of knowledge absolutely required to solve the problem or is knowledge important only to constrain the search?
Can a computer that is simply given the problem return the solution or will the solution of the problem require interaction between the computer and a person?.PP$0;Is the problem Decomposable?Whether the problem can be decomposed into smaller problems?
Using the technique of problem decomposition, we can often solve very large problems easily.<Blocks World ProblemFollowing operators are available:
CLEAR(x) [ block x has nothing on it]-> ON(x, Table)
CLEAR(x) and CLEAR(y) -> ON(x,y) [ put x on y]b#! ?(Can Solution Steps be ignored or undone?))(.Suppose we are trying to prove a math theorem.We can prove a lemma. If we find the lemma is not of any help, we can still continue.
8-puzzle problem
Chess: A move cannot be taken back.
Important classes of problems:
Ignorable ( theorem proving)
Recoverable ( 8-puzzle)
Irrecoverable ( Chess)
The recoverability of a problem plays an important role in determining the complexity of the control structure necessary for the problem s solution.
Ignorable problems can be solved using a simple control structure that never backtracks
Recoverable problems can be solved by a slightly more complicated control strategy that does sometimes make mistakes
Irrecoverable problems will need to be solved by systems that expends a great deal of effort making each decision since decision must be final.
tPLPP]PPL]&
@ Is the universe Predictable?Certain Outcome ( ex: 8-puzzle)
Uncertain Outcome ( ex: Bridge, controlling a robot arm)
For solving certain outcome problems, open loop approach ( without feedback) will work fine.
For uncertain-outcome problems, planning can at best generate a sequence of operators that has a good probability of leading to a solution. We need to allow for a process of plan revision to take place.ZA!(Is a good solution absolute or relative?))(Any path problem
Best path problem
Any path problems can often be solved in a reasonable amount of time by using heuristics that suggest good paths to explore.
Best path problems are computationally harder.
ZE""Is the solution a state or a path?lExamples:
Finding a consistent interpretation for the sentence The bank president ate a dish of pasta salad with the fork . We need to find the interpretation but not the record of the processing.
Water jug : Here it is not sufficient to report that we have solved , but the path that we found to the state (2,0). Thus the a statement of a solution to this problem must be a sequence of operations ( Plan) that produces the final state.
X
6:=F#What is the role of knowledge?Two examples:
Chess: Knowledge is required to constrain the search for a solution
Newspaper story understanding: Lot of knowledge is required even to be able to recognize a solution.
Consider a problem of scanning daily newspapers to decide which are supporting the democrats and which are supporting the republicans in some election. We need lots of knowledge to answer such questions as:
The names of the candidates in each party
The facts that if the major thing you want to see done is have taxes lowered, you are probably supporting the republicans
The fact that if the major thing you want to see done is improved education for minority students, you are probably supporting the democrats.
etc\PPP7P7G$0Does the task require Interaction with a person?11(The programs require intermediate interaction with people for additional inputs and to provided reassurance to the user.
There are two types of programs:
Solitary
Conversational:
Decision on using one of these approaches will be important in the choice of problem solving method.
<ZZgZgN%Problem Classification/There are several broad classes into which the problems fall. These classes can each be associated with generic control strategy that is appropriate for solving the problems:
Classification : ex: medical diagnostics, diagnosis of faults in mechanical devices
Propose and Refine: ex: design and planning
&=!Production System Characteristics""(Can production systems, like problems, be described by a set of characteristics that shed some light on how they can easily be implemented?
If so, what relationships are there between problem types and the types of production systems best suited to solving the problems?
Classes of Production systems:
Monotonic Production System: the application of a rule never prevents the later application of another rule that could also have been applied at the time the first rule was selected.
Non-Monotonic Production system
Partially commutative Production system: property that if application of a particular sequence of rules transforms state x to state y, then permutation of those rules allowable, also transforms state x into state y.
Commutative Production systemL" PPPP&$Four Categories of Production System%%(Q''Issues in the design of search programs(((The direction in which to conduct the search ( forward versus backward reasoning).
How to select applicable rules ( Matching)
How to represent each node of the search process ( knowledge representation problem)R(SummaryFour steps for designing a program to solve a problem:
Define the problem precisely
Analyse the problem
Identify and represent the knowledge required by the task
Choose one or more techniques for problem solving and apply those techniques to the problem.
,7 7,T/|
"
#$%/01234567:>BCDHI J!K"L#M$O%S&T'U(r?
xU\z(
/0LDArialy0z[ 0@.
@n?" dd@ @@```Xx_Z
MM5 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQR,TUVWXYZ[\]^0AA@Eʚ;ʚ;g4?d?d z[ 0ppp@<4ddddL 0|y<4BdBdL< 00___PPT10
___PPT9D$,((m#Problems, Problem Spaces and SearchDr. Suthikshn Kumar Contents4Defining the problem as a State Space Search
Production Systems
Control Strategies
Breadth First Search
Depth First Search
Heuristic Search
Problem Characteristics
Is the Problem Decomposable?
Can Solution Steps be ignored or undone?
Production system characteristics
Issues in the design of search programs
5Z5$To build a system to solve a problem%%(Define the problem precisely
Analyse the problem
Isolate and represent the task knowledge that is necessary to solve the problem
Choose the best problem-solving techniques and apply it to the particular problem." *Defining the problem as State Space Search++(The state space representation forms the basis of most of the AI methods.
Its structure corresponds to the structure of problem solving in two important ways:
It allows for a formal definition of a problem as the need to convert some given situation into some desired situation using a set of permissible operations.
It permits us to define the process of solving a particular problem as a combination of known techniques (each represented as a rule defining a single step in the space) and search, the general technique of exploring the space to try to find some path from current state to a goal state.
Search is a very important process in the solution of hard problems for which no more direct techniques are available..Z5Z5Example: Playing ChessTo build a program that could play chess , we could first have to specify the starting position of the chess board, the rules that define the legal moves, and the board positions that represent a win for one side or the other.
In addition, we must make explicit the previously implicit goal of not only playing the legal game of chess but also winning the game, if possible,
zz
Playing chessThe starting position can be described as an 8by 8 array where each position contains a symbol for appropriate piece.
We can define as our goal the check mate position.
The legal moves provide the way of getting from initial state to a goal state.
They can be described easily as a set of rules consisting of two parts:
A left side that serves as a pattern to be matched against the current board position.
And a right side that describes the change to be made to reflect the move
However, this approach leads to large number of rules 10120 board positions !!
Using so many rules poses problems such as:
No person could ever supply a complete set of such rules.
No program could easily handle all those rules. Just storing so many rules poses serious difficulties.vAPP{PPA8
?
,Defining chess problem as State Space search--(We need to write the rules describing the legal moves in as general a way as possible.
For example:
White pawn at Square( file e, rank 2) AND Square( File e, rank 3) is empty AND Square(file e, rank 4) is empty, then move the pawn from Square( file e, rank 2) to Square( file e, rank 4).
In general, the more succintly we can describe the rules we need, the less work we will have to do to provide them and more efficient the program.BdZZZd,w uWater Jug Problem9The state space for this problem can be described as the set of ordered pairs of integers (x,y) such that x = 0, 1,2, 3 or 4 and y = 0,1,2 or 3; x represents the number of gallons of water in the 4-gallon jug and y represents the quantity of water in 3-gallon jug
The start state is (0,0)
The goal state is (2,n)
:Z:[&Production rules for Water Jug Problem''(KThe operators to be used to solve the problem can be described as follows:
LK Production rules
To solve the water jug problemRequired a control structure that loops through a simple cycle in which some rule whose left side matches the current state is chosen, the appropriate change to the state is made as described in the corresponding right side, and the resulting state is checked to see if it corresponds to goal state.
One solution to the water jug problem
Shortest such sequence will have a impact on the choice of appropriate mechanism to guide the search for solution.
(Z!Formal Description of the problem""(Define a state space that contains all the possible configurations of the relevant objects.
Specify one or more states within that space that describe possible situations from which the problem solving process may start ( initial state)
Specify one or more states that would be acceptable as solutions to the problem. ( goal states)
Specify a set of rules that describe the actions ( operations) available. " PProduction Systems~A production system consists of:
A set of rules, each consisting of a left side that determines the applicability of the rule and a right side that describes the operation to be performed if that rule is applied.
One or more knowledge/databases that contain whatever information is appropriate for the particular task. Some parts of the database may be permanent, while other parts of it may pertain only to the solution of the current problem.
A control strategy that specifies the order in which the rules will be compared to the database and a way of resolving the conflicts that arise when several rules match at once.
A rule applier$!P^P
Production systemTInorder to solve a problem:
We must first reduce it to one for which a precise statement can be given. This can be done by defining the problem s state space ( start and goal states) and a set of operators for moving that space.
The problem can then be solved by searching for a path through the space from an initial state to a goal state.
The process of solving the problem can usefully be modelled as a production system. $PP$Control StrategiesHow to decide which rule to apply next during the process of searching for a solution to a problem?
The two requirements of good control strategy are that
it should cause motion.
It should be systematic&00 Breadth First SearchAlgorithm:
Create a variable called NODE-LIST and set it to initial state
Until a goal state is found or NODE-LIST is empty do
Remove the first element from NODE-LIST and call it E. If NODE-LIST was empty, quit
For each way that each rule can match the state described in E do:
Apply the rule to generate a new state
If the new state is a goal state, quit and return this state
Otherwise, add the new state to the end of NODE-LISTpt t!BFS Tree for Water Jug problem(
&Algorithm: Depth First SearchYIf the initial state is a goal state, quit and return success
Otherwise, do the following until success or failure is signaled:
Generate a successor, E, of initial state. If there are no more successors, signal failure.
Call Depth-First Search, with E as the initial state
If success is returned, signal success. Otherwise continue in this loop.:" Z" Z'BacktrackingIn this search, we pursue a singal branch of the tree until it yields a solution or until a decision to terminate the path is made.
It makes sense to terminate a path if it reaches dead-end, produces a previous state. In such a state backtracking occurs
Chronological Backtracking: Order in which steps are undone depends only on the temporal sequence in which steps were initially made.
Specifically most recent step is always the first to be undone.
This is also simple backtracking.Z( Advantages of Depth-First Search!!(DFS requires less memory since only the nodes on the current path are stored.
By chance, DFS may find a solution without examining much of the search space at all. )Advantages of BFSBFS will not get trapped exploring a blind alley.
If there is a solution, BFS is guarnateed to find it.
If there are multiple solutions, then a minimal solution will be found.Q
V*TSPA simple motion causing and systematic control structure could solve this problem.
Simply explore all possible paths in the tree and return the shortest path.
If there are N cities, then number of different paths among them is 1.2& .(N-1) or (N-1)!
The time to examine single path is proportional to N
So the total time required to perform this search is proportional to N!
For 10 cities, 10! = 3,628,800
This phenomenon is called Combinatorial explosion.Z+Branch and BoundkBegin generating complete paths, keeping track of the shortest path found so far.
Give up exploring any path as soon as its partial length becomes greater than the shortest path found so far.
Using this algorithm, we are guaranteed to find the shortest path.
It still requires exponential time.
The time it saves depends on the order in which paths are explored. lZl,Heuristic SearchA Heuristic is a technique that improves the efficiency of a search process, possibly by sacrificing claims of completeness.
Heuristics are like tour guides
They are good to the extent that they point in generally interesting directions;
They are bad to the extent that they may miss points of interest to particular individuals.
On the average they improve the quality of the paths that are explored.
Using Heuristics, we can hope to get good ( though possibly nonoptimal ) solutions to hard problems such asa TSP in non exponential time.
There are good general purpose heuristics that are useful in a wide variety of problem domains.
Special purpose heuristics exploit domain specific knowledgeP,
#-Nearest Neighbour Heuristic It works by selecting locally superior alternative at each step.
Applying to TSP:
Arbitrarily select a starting city
To select the next city, look at all cities not yet visited and select the one closest to the current city. Go to next step.
Repeat step 2 until all cities have been visited.
This procedure executes in time proportional to N2
It is possible to prove an upper bound on the error it incurs. This provides reassurance that one is not paying too high a price in accuracy for speed.lRZ Z ZR1
.Heuristic FunctionAThis is a function that maps from problem state descriptions to measures of desirsability, usually represented as numbers.
Which aspects of the problem state are considered,
how those aspects are evaluated, and
the weights given to individual aspects are chosen in such a way that
the value of the heuristic function at a given node in the search process gives as good an estimate as possible of whether that node is on the desired path to a solution.
Well designed heuristic functions can play an important part in efficiently guiding a search process toward a solution.
B{ZZ&Z{&L
8"Example Simple Heuristic functions##(Chess : The material advantage of our side over opponent.
TSP: the sum of distances so far
Tic-Tac-Toe: 1 for each row in which we could win and in we already have one piece plus 2 for each such row in we have two pieces_{9Problem CharacteristicsInorder to choose the most appropriate method for a particular problem, it is necessary to analyze the problem along several key dimensions:
Is the problem decomposable into a set of independent smaller or easier subproblems?
Can solution steps be ignored or at least undone if they prove unwise?
Is the problem s universe predictable?
Is a good solution to the problem obvious without comparison to all other possible solutions?
Is the desired solution a state of the world or a path to a state?
Is a large amount of knowledge absolutely required to solve the problem or is knowledge important only to constrain the search?
Can a computer that is simply given the problem return the solution or will the solution of the problem require interaction between the computer and a person?.PP$0;Is the problem Decomposable?Whether the problem can be decomposed into smaller problems?
Using the technique of problem decomposition, we can often solve very large problems easily.<Blocks World ProblemFollowing operators are available:
CLEAR(x) [ block x has nothing on it]-> ON(x, Table)
CLEAR(x) and CLEAR(y) -> ON(x,y) [ put x on y]b#! ?(Can Solution Steps be ignored or undone?))(.Suppose we are trying to prove a math theorem.We can prove a lemma. If we find the lemma is not of any help, we can still continue.
8-puzzle problem
Chess: A move cannot be taken back.
Important classes of problems:
Ignorable ( theorem proving)
Recoverable ( 8-puzzle)
Irrecoverable ( Chess)
The recoverability of a problem plays an important role in determining the complexity of the control structure necessary for the problem s solution.
Ignorable problems can be solved using a simple control structure that never backtracks
Recoverable problems can be solved by a slightly more complicated control strategy that does sometimes make mistakes
Irrecoverable problems will need to be solved by systems that expends a great deal of effort making each decision since decision must be final.
tPLPP]PPL]&
@ Is the universe Predictable?Certain Outcome ( ex: 8-puzzle)
Uncertain Outcome ( ex: Bridge, controlling a robot arm)
For solving certain outcome problems, open loop approach ( without feedback) will work fine.
For uncertain-outcome problems, planning can at best generate a sequence of operators that has a good probability of leading to a solution. We need to allow for a process of plan revision to take place.ZA!(Is a good solution absolute or relative?))(Any path problem
Best path problem
Any path problems can often be solved in a reasonable amount of time by using heuristics that suggest good paths to explore.
Best path problems are computationally harder.
ZE""Is the solution a state or a path?lExamples:
Finding a consistent interpretation for the sentence The bank president ate a dish of pasta salad with the fork . We need to find the interpretation but not the record of the processing.
Water jug : Here it is not sufficient to report that we have solved , but the path that we found to the state (2,0). Thus the a statement of a solution to this problem must be a sequence of operations ( Plan) that produces the final state.
X
6:=F#What is the role of knowledge?Two examples:
Chess: Knowledge is required to constrain the search for a solution
Newspaper story understanding: Lot of knowledge is required even to be able to recognize a solution.
Consider a problem of scanning daily newspapers to decide which are supporting the democrats and which are supporting the republicans in some election. We need lots of knowledge to answer such questions as:
The names of the candidates in each party
The facts that if the major thing you want to see done is have taxes lowered, you are probably supporting the republicans
The fact that if the major thing you want to see done is improved education for minority students, you are probably supporting the democrats.
etc\PPP7P7G$0Does the task require Interaction with a person?11(The programs require intermediate interaction with people for additional inputs and to provided reassurance to the user.
There are two types of programs:
Solitary
Conversational:
Decision on using one of these approaches will be important in the choice of problem solving method.
<ZZgZgN%Problem Classification/There are several broad classes into which the problems fall. These classes can each be associated with generic control strategy that is appropriate for solving the problems:
Classification : ex: medical diagnostics, diagnosis of faults in mechanical devices
Propose and Refine: ex: design and planning
&=!Production System Characteristics""(Can production systems, like problems, be described by a set of characteristics that shed some light on how they can easily be implemented?
If so, what relationships are there between problem types and the types of production systems best suited to solving the problems?
Classes of Production systems:
Monotonic Production System: the application of a rule never prevents the later application of another rule that could also have been applied at the time the first rule was selected.
Non-Monotonic Production system
Partially commutative Production system: property that if application of a particular sequence of rules transforms state x to state y, then permutation of those rules allowable, also transforms state x into state y.
Commutative Production systemL" PPPV)Monotonic Production SystemsProduction system in which the application of a rule never prevents the later application of another rule that could also have been applied at the time the first rule was applied.
i.e., rules are independent.W*Commutative Production system(YA partially Commutative production system has a property that if the application of a particular sequence of rules transform state x into state y, then any permutation of those rules that is allowable, also transforms state x into state y.
A Commutative production system is a production system that is both monotonic and partially commutative. ZZZX+ Partially Commutative, Monotonic!!(These production systems are useful for solving ignorable problems.
Example: Theorem Proving
They can be implemented without the ability to backtrack to previous states when it is discovered that an incorrect path has been followed.
This often results in a considerable increase in efficiency, particularly because since the database will never have to be restored, It is not necessary to keep track of where in the search process every change was made.
They are good for problems where things do not change; new things get created.PY,$Non Monotonic, Partially Commutative%%(WUseful for problems in which changes occur but can be reversed and in which order of operations is not critical.
Example: Robot Navigation, 8-puzzle, blocks world
Suppose the robot has the following ops: go North (N), go East (E), go South (S), go West (W). To reach its goal, it does not matter whether the robot executes the N-N-E or N-E-N.XXZ-Not partially CommutativeProblems in which irreversible change occurs
Example: chemical synthesis
The ops can be :Add chemical x to the pot, Change the temperature to t degrees.
These ops may cause irreversible changes to the potion being brewed.
The order in which they are performed can be very important in determining the final output.
(X+y) +z is not the same as (z+y) +x
Non partially commutative production systems are less likely to produce the same node many times in search process.
When dealing with ones that describe irreversible processes, it is partially important to make correct decisions the first time, although if the universe is predictable, planning can be used to make that less important.P><K
[.Non P&$Four Categories of Production System%%(Q''Issues in the design of search programs(((The direction in which to conduct the search ( forward versus backward reasoning).
How to select applicable rules ( Matching)
How to represent each node of the search process ( knowledge representation problem)R(SummaryFour steps for designing a program to solve a problem:
Define the problem precisely
Analyse the problem
Identify and represent the knowledge required by the task
Choose one or more techniques for problem solving and apply those techniques to the problem.
,7 7T/|
"
#$%/01234567:>BCDHI J!K"L#M$O%S&T'U($
d$(
dr
d S = `}
=
r
d SD'= `=
H
d0h ? 3380___PPT10.*$
h$(
hr
h S= `}
=
r
h S)= `=
H
h0h ? 3380___PPT10. $
l$(
lr
l S `}
r
l S= `=
H
l0h ? 3380___PPT10.pGm$
p$(
pr
p Sh `}
r
p S `
H
p0h ? 3380___PPT10.PZ$
t$(
tr
t Sx `}
r
t S$ `
H
t0h ? 3380___PPT10.`7$
x$(
xr
x Sxq `}
r
x S(Ϲ `
H
x0h ? 3380___PPT10.S!r$V`m?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~,
!"#$%&'()*+,-./0345ommutativeNot partially CommutativeNon %Four Categ_DzPawanPawanSuthikshn Kumar.C.Rories of Production System(Issues in the design of search programsSummaryFonts UsedDesign Template
Slide Titles/