2.Problems Problem Spaces and Search.ppt

AI

1. 19ECB336
ARTIFICIAL INTELLIGENCE
1

2. Problems, Problem Spaces and Search:
TobuildaAIsystemtosolveaparticularproblem,weneedtodo
thefollowingfourthings;
1.Definetheproblemprecisely.
2.Analysetheproblem.
3.Isolateandrepresentthetaskknowledgethatisnecessaryto
solvetheproblem.
4.Choosethebestproblem-solvingtechniquesandapplyitto
theparticularproblem.
ThestatespacerepresentationformsthebasisofmostoftheAI
methods.
2

3. Defining the problem as State Space Search
Itsstructurecorrespondstothestructureofproblemsolvingin
twoimportantways:
Itallowsforaformaldefinitionofaproblemastheneedto
convertsomegivensituationintosomedesiredsituationusing
asetofpermissibleoperations.
Itpermitsustodefinetheprocessofsolvingaparticular
problemasacombinationofknowntechniques(each
representedasaruledefiningasinglestepinthespace)and
search,thegeneraltechniqueofexploringthespacetotryto
findsomepathfromcurrentstatetoagoalstate.
Searchisaveryimportantprocessinthesolutionofhard
problemsforwhichnomoredirecttechniquesareavailable. 3

4. Defining the problem as State Space Search
Example:PlayingChess
Tobuildaprogramthatcould“playchess”,wecouldfirsthaveto
specifythestartingpositionofthechessboard,therulesthat
definethelegalmoves,andtheboardpositionsthatrepresenta
winforonesideortheother.
Inaddition,wemustmakeexplicitthepreviouslyimplicitgoalof
notonlyplayingthelegalgameofchessbutalsowinningthe
game,ifpossible,
Thestartingpositioncanbedescribedasan8x8arraywhere
eachpositioncontainsasymbolforappropriatepiece.
Wecandefineasourgoaltocheckmateposition.
4

5. Defining the problem as State Space Search
Thelegalmovesprovidethewayofgettingfrominitialstatetoa
goalstate.
Theycanbedescribedeasilyasasetofrulesconsistingoftwo
parts:
Aleftsidethatservesasapatterntobematchedagainstthe
currentboardposition.
Andarightsidethatdescribesthechangetobemadetoreflect
themove.
However, this approach leads to large number of rules 10^120
board positions!!
5

6. Defining the problem as State Space Search
Usingsomanyrulesposesproblemssuchas:
Nopersoncouldeversupplyacompletesetofsuchrules.
Noprogramcouldeasilyhandleallthoserules.Juststoringso
manyrulesposesseriousdifficulties.
Inordertominimizesuchproblems,Weneedtowritetherules
describingthelegalmovesinasgeneralawayaspossible.
Forexample:
6

7. Defining the problem as State Space Search
Ingeneral,wecandescribetherulesweneed,thelessworkwewill
havetodotoprovidethemandmoreefficienttheprogram.
7

8. Water Jug Problem
Thestatespaceforthisproblemcanbedescribedasthesetof
orderedpairsofintegers(x,y)suchthatx=0,1,2,3or4andy=0,1,2or
3;
Howcanwegettwogallonsofwaterinthefirstjug?
xrepresentsthenumberofgallonsofwaterinthe4-gallonjug
andyrepresentsthequantityofwaterin3-gallonjug.
Thestartstateis(0,0)andthegoalstateis(2,n),wherenmaybeany
butitislimitedtothreeholdingfrom0to3gallonsofwaterorempty.
8

9. ProductionrulesforWaterJugProblem
9

10. ProductionrulesforWaterJugProblem
10

11. To solve the water jug problem
Requiredacontrolstructurethatloopsthroughasimplecyclein
whichsomerulewhoseleftsidematchesthecurrentstateischosen,
theappropriatechangetothestateismadeasdescribedinthe
correspondingrightside,andtheresultingstateischeckedtoseeifit
correspondstogoalstate.
Shortestsuchsequencewillhaveaimpactonthechoiceof
appropriatemechanismtoguidethesearchforsolution.
11

12. Summarizing the formal description of the problem
1.Defineastatespacethatcontainsallthepossibleconfigurationsof
therelevantobjects.
2.Specifyoneormorestateswithinthatspacewhichdescribepossible
situationsfromwhichtheproblemsolvingprocessmaystart(initial
state).
3.Specifyoneormorestatesthatwouldbeacceptableassolutionsto
theproblem(goalstates).
4.Specifyasetofrulesthatdescribetheactions(operations)
available.
12

13. ProductionSystems
Aproductionsystemisamodelofcomputationthatprovidespattern-
directedcontrolofaproblem–solvingprocessandconsistsofaset
ofproductionrules,aworkingmemory,andarecognize–actcontrol
cycle.
Allofthesesystemsprovidetheoverallarchitectureofaproduction
systemsandallowtheprogrammertowriterulesthatdefine
particularproblemstobesolved.
13

14. ProductionSystems
Aproductionsystemconsistsof:
Asetofrules,eachconsistingofaleftsidethatdeterminesthe
applicabilityoftheruleandarightsidethatdescribestheoperationto
beperformedifthatruleisapplied.
Oneormoreknowledge/database(KB)thatcontainwhatever
informationisappropriatefortheparticulartask.Somepartsofthe
databasemaybepermanent,whileotherpartsofitmaypertainonly
tothesolutionofthecurrentproblem.
Acontrolstrategythatspecifiestheorderinwhichtheruleswillbe
comparedtothedatabaseandawayofresolvingtheconflictsthat
arisewhenseveralrulesmatchatonce.
Aruleapplier;CheckcurrentstatewithLHSofrulesinKBandfind
appropriateruletoapply. 14

15. ProductionSystems
Onecanoftenrepresenttheexpertisethatsomeoneusestodoanexpert
taskasrules.
Arulemeansastructurewhichhasanifcomponentandathen
component.
Thestatement,orsetofstatements,afterthewordifrepresentssomepattern
whichyoumayobserve.
Thestatement,orsetofstatements,afterthewordthenrepresentssome
conclusionthatyoucandraw,orsomeactionthatyoushouldtake.
IFsomecondition(s)existsTHENperformsomeaction(s)
•IF-THEN
•Test-Action
15

16. ProductionSystems
Thereforeproductionsystemcanbedescribedassetofproductionrules,
togetherwithsoftwarethatcanreasonwiththem.
ProductionSystemaresometimesknownasRuleBasedExpertSystem.
Arule-basedsystemconsistsof
•a set of IF-THEN rules
•a set of facts
•an interpretercontrolling the application of the rules, given the facts.
16

17. ProductionSystems
Inordertosolveaproblem:
Wemustreduceittooneforwhichaprecisestatementcanbegiven.
Thiscanbedonebydefiningtheproblem’sstatespace(startandgoal
states)andasetofoperatorsformovingthatspace.
Theproblemcanthenbesolvedbysearchingforapaththroughthe
statespacefromaninitialstatetoagoalstate.
Theprocessofsolvingtheproblemcanusefullybemodelledasa
productionsystem.
17

18. Example8-Puzzleproblem
Searchprocesscontains:
1.Expandinganode
2.Generatinganode
3.Comparing
4.Trackthepathandpathcost
18

19. Example8-Puzzleproblem
19

20. ControlStrategies
Howtodecidewhichruletoapplynextduringtheprocessof
searchingforasolutiontoaproblem?
Thetworequirementsofgoodcontrolstrategyare
itshouldcausemotion.
Itshouldbesystematic
20

21. Algorithm:BreadthFirstSearch
1.CreateavariablecalledNODE-LISTandsetittoinitialstate
2.UntilagoalstateisfoundorNODE-LISTisempty
do:
a.RemovethefirstelementfromNODE-LISTandcallitE.IfNODE-
LISTwasempty,quit.
b.ForeachwaythateachrulecanmatchthestatedescribedinE
do:
i.Applytheruletogenerateanewstate
ii.Ifthenewstateisagoalstate,quitandreturnthisstate
iii.Otherwise,addthenewstatetotheendofNODE-LIST
21

22. Algorithm:DepthFirstSearch
1.Iftheinitialstateisagoalstate,quitandreturnsuccess
2.Otherwise,dothefollowinguntilsuccessorfailureissignalled:
do:
a.Generateasuccessor,E,ofinitialstate.Iftherearenomore
successors,signalfailure.
b.CallDepth-FirstSearch,withEastheinitialstate
c.Ifsuccessisreturned,signalsuccess.Otherwisecontinueinthis
loop.
22

23. DepthFirstSearch(Cont.…)
Inthissearch,wepursueasinglebranchofthetreeuntilityieldsa
solutionoruntiladecisiontoterminatethepathismade.
Itmakessensetoterminateapathifitreachesdeadend,producesa
previousstate.Insuchastatebacktrackingoccurs.
ChronologicalBacktracking:Orderinwhichstepsareundone
dependsonlyonthetemporalsequenceinwhichstepswereinitially
made.
Specificallymostrecentstepisalwaysthefirsttobeundone.
Thisisalsosimplebacktracking.
23

24. Advantages
AdvantagesofDFS
DFSrequireslessmemorysinceonlythenodesonthecurrentpath
arestored.
Bychance,DFSmayfindasolutionwithoutexaminingmuchofthe
searchspaceatall.
AdvantagesofBFS
BFSwillnotgettrappedexploringablindalley.
Ifthereisasolution,BFSisguaranteedtofindit.
Iftherearemultiplesolutions,thenaminimalsolutionwillbefound.
24

25. TravelingSalesmanProblem(TSP)
Asalesmanhasalistofcities,eachofwhichhemustvisitexactlyonce.
Therearedirectroadsbetweeneachpairofcitiesonthelist.
Findtheroutethesalesmanshouldfollowfortheshortestpossible
roundtripthatbothstartsandfinishesatanyoneofthecities.
Asimplemotioncausingandsystematiccontrolstructurecouldsolve
thisproblem.
Simplyexploreallpossiblepathsinthetreeandreturntheshortest
path.
IfthereareNcities,thennumberofdifferentpathsamongthemis
1.2….(N-1)or(N-1)!.
ThetimetoexaminesinglepathisproportionaltoN!.
25

26. TravelingSalesmanProblem(TSP)
Sothetotaltimerequiredtoperformthissearchisproportionalto
N!.For10cities,10!=3,628,800whichisverylargenumber.
Thesalesmancouldnormallyvisitsnearly25cities.
ThisphenomenoniscalledCombinatorialexplosion.
SoaboveapproachwilltakemoretimetosolvetheTSP.
TobeattheCombinatorialexplosiontechnique,anewstrategy
knownasbranchandboundtechniquecameintoexistence.
26

27. TravelingSalesmanProblem(TSP)
BranchandBound:
Begingeneratingcompletepaths,keepingtrackoftheshortest
pathfoundsofar.
Giveupexploringanypathassoonasitspartiallengthbecomes
greaterthantheshortestpathfoundsofar.
Usingthisalgorithm,weareguaranteedtofindtheshortestpath.
Itstillrequiresexponentialtime.
Thetimeitsavesdependsontheorderinwhichpathsareexplored.
Butitisstillinadequateforsolvinglargeproblems.
27

28. HeuristicSearch
Itistechniquedesignedtosolveaproblemquickly.
AHeuristicisatechniquethatimprovestheefficiencyofasearch
process,possiblybysacrificingclaimsofcompleteness.
Heuristicsareliketourguides.
Theyaregoodtotheextentthattheypointingenerallyinteresting
directions;
Theyarebadtotheextentthattheymaymisspointsofinterestto
particularindividuals.
Ontheaverage,theyimprovethequalityofthepathsthatare
explored.
28

29. HeuristicSearch
UsingHeuristics,wecanhopetogetgood(thoughpossiblynon-
optimal)solutionstohardproblemssuchTSPinnonexponential
time.
Therearegoodgeneralpurposeheuristicsthatareusefulinawide
varietyofproblemdomains.
Specialpurposeheuristicsexploitdomainspecificknowledge.
Itgivesgoodsolution.Thesolutionmaybeoptimalbutthereisno
guarantee.
Trytosolvetheproblemfromnon-polynomialtopolynomialtime
complexity.
29

30. HeuristicSearch
Oneofthegoodpurposeheuristicthatisusefulforvarietyof
combinatorialproblemsistheNearestNeighbourHeuristicwhich
worksbyselectingthelocallysuperioralternativeateachstep.
ApplyingittoTSP;Thefollowingprocedureshouldbefollowed;
1.Arbitrarilyselectastartingcity
2.Toselectthenextcity,lookatallcitiesnotyetvisitedandselect
theoneclosesttothecurrentcity.Gotonextstep.
3.Repeatstep2untilallcitieshavebeenvisited.
ThisprocedureexecutesintimeproportionaltoN^2
Itispossibletoproveanupperboundontheerroritincurs.
Thisprovidesreassurancethatoneisnotpayingtoohighpricein
accuracyforspeed. 30

31. HeuristicFunction
Thisisafunctionthatmapsfromproblemstatedescriptionsto
measuresofdesirability,usuallyrepresentedasnumbers.
Whichaspectsoftheproblemstateareconsidered,
Howthoseaspectsareevaluated,and
Theweightsgiventoindividualaspectsarechoseninsuchaway
that
Thevalueoftheheuristicfunctionatagivennodeinthesearch
processgivesasgoodanestimateaspossibleofwhetherthatnode
isonthedesiredpathtoasolution.
Welldesignedheuristicfunctionscanplayanimportantpartin
efficientlyguidingasearchprocesstowardasolution.
31

32. Examples:SimpleHeuristicfunctions
Chess:Thematerialadvantageofoursideoveropponent.
TSP:thesumofdistancessofar.
Tic-Tac-Toe:1foreachrowinwhichwecouldwinandinwealready
haveonepieceplus2foreachsuchrowinwehavetwopieces.
32

33. ProblemCharacteristics
Inordertochoosethemostappropriatemethodforaparticular
problem,itisnecessarytoanalyzetheproblemalongseveralkey
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?
33

34. ProblemCharacteristics
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?
34

35. IstheproblemDecomposable?
Whethertheproblemcanbedecomposedintosmallerproblems?
Usingthetechniqueofproblemdecomposition,wecanoftensolve
verylargeproblemseasily.
Suppose,Wewanttosolvetheproblemofcomputingthe
expression;
35

36. BlocksWorldProblem
The blocks-world problem is known asSussman Anomaly.
Noninterleavedplanners of the early 1970swere unable to solve
this problem, hence it is considered as anomalous.
WhentwosubgoalsG1andG2aregiven,anoninterleavedplanner
produceseitheraplanforG1concatenatedwithaplanforG2,or
vice-versa.
Inblocks-worldproblem,threeblockslabeledas'A','B','C'are
allowedtorestontheflatsurface/table.Thegivenconditionisthat
onlyoneblockcanbemovedatatimetoachievethegoal.
36

37. BlocksWorldProblem
Followingoperatorsareavailable:
37

38. Can Solution Steps be ignored or undone?
Supposewearetryingtoproveamathematicaltheorem.Wecan
provealemma.Ifwefindthelemmaisnotofanyhelp,wecanstill
continue.
8-puzzleproblem.
Chess:Amovecannotbetakenback.
Importantclassesofproblems:
Ignorable ( theorem proving)
Recoverable ( 8-puzzle)
Irrecoverable ( Chess)
38

39. Can Solution Steps be ignored or undone?
Therecoverabilityofaproblemplaysanimportantrolein
determiningthecomplexityofthecontrolstructurenecessaryfor
theproblem’ssolution.
Ignorableproblemscanbesolvedusingasimplecontrol
structurethatneverbacktracks
Recoverableproblemscanbesolvedbyaslightlymore
complicatedcontrolstrategythatdoessometimesmake
mistakes
Irrecoverableproblemswillneedtobesolvedbysystemsthat
expendsagreatdealofeffortmakingeachdecisionsince
decisionmustbefinal.
39

40. Is the universe Predictable?
CertainOutcome(ex:8-puzzle).
UncertainOutcome(ex:Bridge,controllingarobotarm).
Forsolvingcertainoutcomeproblems,openloopapproach(
withoutfeedback)willworkfine.
Foruncertain-outcomeproblems,planningcanatbestgeneratea
sequenceofoperatorsthathasagoodprobabilityofleadingtoa
solution.
Weneedtoallowforaprocessofplanrevisiontotakeplace.
40

41. Is a good solution absolute or relative?
Anypathproblem
Bestpathproblem
Anypathproblemscanoftenbesolvedinareasonableamountof
timebyusingheuristicsthatsuggestgoodpathstoexplore.
Bestpathproblemsarecomputationallyharderthananypath
problems.
41

42. Is a good solution absolute or relative?
Forexample:ThesalesmanstartsfromBoston.Thefollowing
figure
42

43. Is the solution a state or a path?
Considertheproblemoffindingaconsistentinterpretationforthe
sentence;
“The bank president ate a dish of pasta salad with the fork”.
Weneedtofindtheinterpretationbutnottherecordofthe
processing.
WaterjugProblem:Hereitisnotsufficienttoreportthatwehave
solved,butthepaththatwefoundtothestate(2,0).Thusa
statementofasolutiontothisproblemmustbeasequenceof
operations(Plan)thatproducesthefinalstate.
43

44. What is the role of knowledge?
Twoexamples;Chess:Knowledgeisrequiredtoconstrainthesearch
forasolution.
Newspaperstoryunderstanding:Lotofknowledgeisrequiredevento
beabletorecognizeasolution.
Consideraproblemofscanningdailynewspaperstodecidewhichare
supportingthedemocratsandwhicharesupportingtherepublicansin
someelection.Weneedlotsofknowledgetoanswersuchquestionsas:
Thenamesofthecandidatesineachparty.
Thefactsthatifthemajorthingyouwanttoseedoneishavetaxes
lowered,youareprobablysupportingtherepublicans.
Thefactthatifthemajorthingyouwanttoseedoneisimproved
educationforminoritystudents,youareprobablysupportingthe
democrats.
44

45. Does the task require Interaction with a person?
Sometimes,itisusefultoprogramcomputerstosolveaproblems
inwaysthatthemajorityofpeoplewouldnotbeableto
understand.
Thatisfineifthelevelointeractionbetweenthecomputerandits
humanusersisproblem-insolution-out.
Butincreasingly,wearebuildingprogramsthatrequire
intermediateinteractionwithpeopleforadditionalinputsandto
providedreassurancetotheuser.
45

46. Does the task require Interaction with a person?
Thuswemustdistinguishbetweentwotypesofprograms:
•Solitary,inwhichcomputerisgivenaproblemdescriptionand
producesananswerwithnointermediatecommunicationand
withnodemandforanexplanationofthereasoningprocess.
•Conversational,inwhichthereisintermediatecommunication
betweenpersonandthecomputer,eithertoprovideadditional
assistancetothecomputerortoprovideadditionalinformation
totheuserorboth.
•Decisiononusingoneoftheseapproacheswillbeimportantinthe
choiceofproblemsolvingmethod.
46

47. Problem Classification
Thereareseveralbroadclassesintowhichtheproblemsfall.
Theseclassescaneachbeassociatedwithgenericcontrol
strategythatisappropriateforsolvingtheproblems:
Classification : medical diagnostics,diagnosis of faults in
mechanical devices.
Propose and Refine: design and planning
47

48. Production System Characteristics
Wehaveseenthattheproductionsystemsaregoodwayto
describetheoperationsthatcanbeperformedinsearchfora
solutiontoaproblem.Twoquestions,wemightreasonablyask,
are:
1.Canproductionsystems,likeproblems,bedescribedbyasetof
characteristicsthatshedsomelightonhowtheycaneasilybe
implemented?
2.Ifso,whatrelationshipsaretherebetweenproblemtypesand
thetypesofproductionsystemsbestsuitedtosolvingthe
problems?
Theanswerofthefirstquestionisyes.
48

49. Production System Characteristics
ConsiderthefollowingdefinitionsofclassesofProductionsystems:
MonotonicProductionSystem:Theapplicationofarulenever
preventsthelaterapplicationofanotherrulethatcouldalsohave
beenappliedatthetimethefirstrulewasselected.i.e.,rulesare
independent.
Non-MonotonicProductionsystemisoneinwhichthisisnottrue.
PartiallycommutativeProductionsystem:propertythatifapplication
ofaparticularsequenceofrulestransformsstatextostatey,then
permutationofthoserulesallowable,alsotransformsstatexinto
statey.
AcommutativeProductionsystemistheproductionsystemthatis
bothmonotonicandpartiallycommutative.
49

50. Production System Characteristics
PartiallyCommutative,MonotonicProductionSystems:
Theseproductionsystemsareusefulforsolvingignorable
problems.Example:TheoremProving
Theycanbeimplementedwithouttheabilitytobacktrackto
previousstateswhenitisdiscoveredthatanincorrectpathhas
beenfollowed.
Thisoftenresultsinaconsiderableincreaseinefficiency,
particularlybecausesincethedatabasewillneverhavetobe
restored
Itisnotnecessarytokeeptrackofwhereinthesearchprocess
everychangewasmade.
Theyaregoodforproblemswherethingsdonotchange;new
thingsgetcreated.
50

51. Production System Characteristics
NonMonotonic,PartiallyCommutativeProduction
Systems:
Usefulforproblemsinwhichchangesoccurbutcanbereversed
andinwhichorderofoperationsisnotcritical.
Example:RobotNavigation,8-puzzle,blocksworld
Supposetherobothasthefollowingops:goNorth(N),goEast(E),
goSouth(S),goWest(W).Toreachitsgoal,itdoesnotmatter
whethertherobotexecutestheN-N-EorN-E-N.
51

52. Production System Characteristics
NonPartiallyCommutativeProductionSystems:
Problemsinwhichirreversiblechangeoccurs.Example:chemical
synthesis.
Theopscanbe:Addchemicalxtothepot,changethetemperature
totdegrees.
Theseopsmaycauseirreversiblechangestotheportionbeing
brewed.
Theorderinwhichtheyareperformedcanbeveryimportantin
determiningthefinaloutput.
(X+y)+zisnotthesameas(z+y)+x
Nonpartiallycommutativeproductionsystemsarelesslikelyto
producethesamenodemanytimesinsearchprocess.
52

53. Production System Characteristics
NonPartiallyCommutativeProductionSystems:
Whendealingwithonesthatdescribeirreversibleprocesses,itis
partiallyimportanttomakecorrectdecisionsthefirsttime,
althoughiftheuniverseispredictable,planningcanbeusedto
makethatlessimportant.
Four Categories of Production System
53

54. Issues in the design of search programs
Thedirectioninwhichtoconductthesearch(forwardversus
backwardreasoning).
Howtoselectapplicablerules(Matching)•
Howtorepresenteachnodeofthesearchprocess(knowledge
representationproblem)
54

55. Summary
Fourstepsfordesigningaprogramtosolveaproblem:
1.Define the problem precisely.
2.Analyse the problem
3.Identify and represent the knowledge required by the task
4.Choose one or more techniques for problem solving and apply
those techniques to the problem.
55