INTRODUCTION

1 CHAPTER1 INTRODUCTIONCHAPTER2 INTELLIGENT AGENTS functionTABLE-DRIVEN-AGENT(percept)retur nsan actionpersistent:percepts, a sequence, initially emptytable, a table of actions, indexed by percept sequences, initially fully specifiedappendperceptto the end ofperceptsaction LOOKUP(percepts,table)returnactionFigure TABLE-DRIVEN-AGENT program is invoked for each new percept and re-turns an action each time. It retains the complete percept sequence in ([location,status])returnsan actionifstatus=Dirtythen returnSuckelse iflocation=Athen returnRightelse iflocation=Bthen returnLeftFigure agent program for a simple reflex agent in the two-location vacuum environ-ment.

2 This program implements the agent function tabulatedin Figure??.functionSIMPLE-REFLEX-AGENT(per cept)returnsan actionpersistent:rules, a set of condition action rulesstate INTERPRET-INPUT(percept)rule RULE-MATCH(state,rules)action simple reflex agent. It acts according to a rule whose condition matches thecurrent state, as defined by the (percept)returnsan actionpersistent:state, the agent s current conception of the world statetransitionmodel, a description of how the next state depends onthe current state and actionsensormodel, a description of how the current world state is reflectedin the agent s perceptsrules, a set of condition action rulesaction, the most recent action, initially nonestate UPDATE-STATE(state,action,percept,transi tionmodel,sensormodel)rule RULE-MATCH(state,rules)action model-based reflex agent.

3 It keeps track of the current state of the world,using an internal model. It then chooses an action in the sameway as the reflex PROBLEMS BY SEARCHING functionBEST-FIRST-SEARCH(problem,f)retu rnsa solution node orfailurenode NODE(STATE= ) frontier a priority queue ordered byf, withnodeas an elementreached a lookup table, with one entry with valuenodewhile notIS-EMPTY( frontier )donode POP( frontier ) ( )then returnnodefor eachchildinEXPAND(problem,node)dos not <reached[s].PATH-COST thenreached[s] childaddchildtofrontierreturnfailurefunc tionEXPAND(problem,node)yieldsnodess (s)dos (s,action)cost + (s,action,s )yieldNODE(STATE=s , PARENT=node, ACTION=action, PATH-COST=cost)Figure best-first search algorithm, and the function for expanding a node.

4 The datastructures used here are described in Section??. See Appendix B (problem)returnsa solution node orfailurenode NODE( ) ( )then returnnodefrontier a FIFO queue, withnodeas an elementreached { }while notIS-EMPTY( frontier )donode POP( frontier )for eachchildinEXPAND(problem,node)dos (s)then returnchildifsis not inreachedthenaddstoreachedaddchildtofron tierreturnfailurefunctionUNIFORM-COST-SE ARCH(problem)returnsa solution node, orfailurereturnBEST-FIRST-SEARCH(problem , PATH-COST)Figure search and uniform-cost search (problem)

5 Returnsa solution node orfailurefordepth= 0to doresult DEPTH-LIMITED-SEARCH(problem,depth)ifres ult6=cutoffthen returnresultfunctionDEPTH-LIMITED-SEARCH (problem, )returnsa node orfailureorcutofffrontier a LIFO queue (stack) with NODE( ) as an elementresult failurewhile notIS-EMPTY( frontier )donode POP( frontier ) ( )then returnnodeifDEPTH(node)> thenresult cutoffelse if notIS-CYCLE(node)dofor eachchildinEXPAND(problem,node)doaddchil dtofrontierreturnresultFigure deepening and depth-limited tree-like search.

6 Iterative deepening re-peatedly applies depth-limited search with increasing limits. It returns one of three differenttypes of values: either a solution node; orfailure, when it has exhausted all nodes and provedthere is no solution at any depth; orcutoff, to mean there might be a solution at a deeper depththan . This is a tree-like search algorithm that does not keep track ofreachedstates, andthus uses much less memory than best-first search, but runs the risk of visiting the same statemultiple times on different paths.

7 Also, if the IS-CYCLE check does not checkallcycles,then the algorithm may get caught in a 3 Solving Problems by SearchingfunctionBIBF-SEARCH(problemF,fF ,problemB,fB)returnsa solution node, orfailurenodeF NODE( )//Node for a start statenodeB NODE( )//Node for a goal statefrontierF a priority queue ordered byfF, withnodeFas an elementfrontierB a priority queue ordered byfB, withnodeBas an elementreachedF a lookup table, with one valuenodeFreachedB a lookup table, with one valuenodeBsolution failurewhile notTERMINATED(solution,frontierF,frontie rB)doiffF(TOP(frontierF))< fB(TOP(frontierB))thensolution PROCEED(F,problemFfrontierF,reachedF,rea chedB,solution)elsesolution PROCEED(B,problemB,frontierB,reachedB,re achedF,solution)

8 ReturnsolutionfunctionPROCEED(dir,proble m, frontier ,reached,reached2,solution)ret urnsa solution//Expand node on frontier ; check against the other frontier variable dir is the direction: either F for forward or Bfor POP( frontier )for eachchildinEXPAND(problem,node)dos inreachedorPATH-COST(child)<PATH-COST(re ached[s])thenreached[s] childaddchildtofrontierifsis inreached2thensolution2 JOIN-NODES(dir,child,reached2[s]))ifPATH -COST(solution2)<PATH-COST(solution)then solution solution2returnsolutionFigure best-first search keeps two frontiers and twotables of reachedstates.

9 When a path in one frontier reaches a state that was also reached in the other half ofthe search, the two paths are joined (by the function JOIN-NODES) to form a solution. Thefirst solution we get is not guaranteed to be the best; the function TERMINATED determineswhen to stop looking for new (problem)returnsa solution orfailuresolution,fvalue RBFS(problem, NODE( ), )returnsolutionfunctionRBFS(problem,node ,flimit)returnsa solution orfailure, and a newf-cost ( )then returnnodesuccessors LIST(EXPAND(node))ifsuccessorsis emptythen returnfailure, for eachsinsuccessorsdo//updatefwith value from previous max( +h(s), ))

10 Whiletruedobest the node insuccessorswith >flimitthen returnfailure, the second-lowestf-value amongsuccessorsresult, RBFS(problem,best,min(flimit,alternative ))ifresult6=failurethen returnresult, algorithm for recursive best-first IN COMPLEXENVIRONMENTS functionHILL-CLIMBING(problem)returnsa state that is a local maximumcurrent a highest-valued successor state ofcurrentifVALUE(neighbor) VALUE(current)then returncurrentcurrent neighborFigure hill-climbing search algorithm, which is the most basiclocal search tech-nique.