INTRODUCTION - Artificial Intelligence: A Modern Approach

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. This program implements the agent function tabulatedin Figure?

2 ?.functionSIMPLE-REFLEX-AGENT(percept)re turnsan 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)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( )

5 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. 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.

6 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)returnsolutionfunctionPR OCEED(dir,problem,frontier,reached,reach ed2,solution)returnsa 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.

7 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), ))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)

8 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. At each step the current node is replaced by the best (problem,schedule)returnsa solution statecurrent 1to doT schedule(t)ifT= 0then returncurrentnext a randomly selected successor ofcurrent E VALUE(current) VALUE(next)if E>0thencurrent nextelsecurrent nextonly with probabilitye E/TFigure simulated annealing algorithm, a version of stochastichill climbing wheresome downhill moves are allowed. Thescheduleinput determines the value of the temper-ature Tas a function of (population,fitness)returnsan individualrepeatweights WEIGHTED-BY(population,fitness)populatio n2 empty listfori= 1toSIZE(population)doparent1,parent2 WEIGHTED-RANDOM-CHOICES(population,weigh ts,2)child REPRODUCE(parent1,parent2)if(small random probability)thenchild MUTATE(child)addchildtopopulation2popula tion population2untilsome individual is fit enough, or enough time has elapsedreturnthe best individual inpopulation, according tofitnessfunctionREPRODUCE(parent1,paren t2)returnsan individualn LENGTH(parent1)c random number from 1 tonreturnAPPEND(SUBSTRING(parent1,1,c), SUBSTRING(parent2,c+ 1,n))Figure genetic algorithm.

9 Within the function,populationis an ordered list of indi-viduals,weightsis a list of corresponding fitness values for each individual, andfitnessis afunction to compute these (problem)returnsa conditional plan, orfailurereturnOR-SEARCH(problem, ,[ ])functionOR-SEARCH(problem,state,path)r eturnsa conditional plan,or (state)then returnthe empty planifIS-CYCLE(path)then returnfailurefor (state)doplan AND-SEARCH(problem, RESULTS(state,action),[state] +path])ifplan6=failurethen return[action] +plan]returnfailurefunctionAND-SEARCH(pr oblem,states,path)returnsa conditional plan,or failurefor eachsiinstatesdoplani OR-SEARCH(problem,si,path)ifplani=failur ethen returnfailurereturn[ifs1thenplan1else ifs2thenplan2else..ifsn 1thenplann 1elseplann]Figure algorithm for searchingAND ORgraphs generated by nondeterministic en-vironments.

10 A solution is a conditional plan that considersevery nondeterministic outcomeand makes a plan for each 4 Search in Complex EnvironmentsfunctionONLINE-DFS-AGENT(pro blem,s )returnsan actions,a, the previous state and action, initially nullpersistent:result, a table mapping(s, a)tos , initially emptyuntried, a table mappingsto a list of untried actionsunbacktracked, a table mappingsto a list of states never backtracked (s )then returnstopifs is a new state (not inuntried)thenuntried[s ] (s )ifsis not nullthenresult[s,a] s addsto the front ofunbacktracked[s ]ifuntried[s ] is emptythenifunbacktracked[s ] is emptythen returnstopelsea an actionbsuch thatresult[s ,b] = POP(unbacktracked[s ])elsea POP(untried[s ])s s returnaFigure online search agent that uses depth-first exploration.