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

2 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. 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].

3 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. 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( ) as an elementresult failurewhile notIS-EMPTY(frontier)donode POP(frontier) ( )then returnnodeifDEPTH(node)> thenresult cutoffelse if notIS-CYCLE(node)dofor eachchildinEXPAND(problem,node)

4 DoaddchildtofrontierreturnresultFigure 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. 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.

5 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(reached[s])thenreached[s] childaddchildtofrontierifsis inreached2thensolution2 JOIN-NODES(dir,child,reached2[s]))ifPATH-COST(solution2)<PATH-COST(solution)thensolution solution2returnsolutionFigure best-first search keeps two frontiers and twotables of reachedstates. 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)returnsa state that is a local maximumcurrent a highest-valued successor state ofcurrentifVALUE(neighbor) VALUE(current)

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

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

8 The agent can safelyexplore only in state spaces in which every action can be undone by some other *-AGENT(problem,s , h)returnsan actions,a, the previous state and action, initially nullpersistent:result, a table mapping(s, a)tos , initially emptyH, a table mappingsto a cost estimate, initially emptyifIS-GOAL(s )then returnstopifs is a new state (not inH)thenH[s ] h(s )ifsis not nullthenresult[s,a] s H[s] minb ACTIONS(s)LRTA*-COST(s,b,result[s,b],H)a argminb ACTIONS(s)LRTA*-COST(problem,s ,b,result[s ,b],H)s s returnafunctionLRTA*-COST(problem,s,a,s ,H)returnsa cost estimateifs is undefinedthen returnh(s)else (s, a, s ) +H[s ]Figure -AGENT selects an action according to the values of neighboring states,which are updated as the agent moves about the state SEARCH AND GAMES functionMINIMAX-SEARCH(game,state)return san actionplayer (state)value,move MAX-VALUE(game,state)returnmovefunctionM AX-VALUE(game,state)returnsa (utility,move) (state)then (state,player),nullv for (state)dov2,a2 MIN-VALUE(game, (state,a))ifv2>vthenv,move v2,areturnv,movefunctionMIN-VALUE(game,s tate)returnsa (utility,move)

9 (state)then (state,player),nullv + for (state)dov2,a2 MAX-VALUE(game, (state,a))ifv2<vthenv,move v2,areturnv,moveFigure algorithm for calculating the optimal move using minimax the move thatleads to a terminal state with maximum utility, under the assumption that the opponent playsto minimize utility. The functions MAX-VALUEand MIN-VALUEgo through the wholegame tree, all the way to the leaves, to determine the backed-up value of a state and the moveto get 5 Adversarial Search and GamesfunctionALPHA-BETA-SEARCH(game,state)returnsan actionplayer (state)value,move MAX-VALUE(game,state, ,+ )returnmovefunctionMAX-VALUE(game,state, , )returnsa (utility,move) (state)then (state,player),nullv for (state)dov2,a2 MIN-VALUE(game, (state,a), , )ifv2>vthenv,move v2,a MAX( ,v)ifv then returnv,movereturnv,movefunctionMIN-VALU E(game,state, , )returnsa (utility,move) (state)then (state,player),nullv + for (state)dov2,a2 MAX-VALUE(game, (state,a), , )ifv2<vthenv,move v2,a MIN( ,v)ifv then returnv,movereturnv,moveFigure alpha beta search algorithm.

10 Notice that these functions are the same as theMINIMAX-SEARCH functions in Figure??, except that we maintain bounds in the variables and , and use them to cut off search when a value is outside the (state)returnsan actiontree NODE(state)whileIS-TIME-REMAINING()dolea f SELECT(tree)child EXPAND(leaf)result SIMULATE(child)BACK-PROPAGATE(result,chi ld)returnthe move in ACTIONS(state) whose node has highest number of playoutsFigure Monte Carlo tree search algorithm. A game tree,tree, is initialized, andthen we repeat a cycle of SELECT/ EXPAND/ SIMULATE/ BACK-PROPAGATE until we runout of time, and return the move that led to the node with the highest number of SATISFACTIONPROBLEMS functionAC-3(csp)returnsfalse if an inconsistency is found and true otherwisequeue a queue of arcs, initially all the arcs incspwhilequeueis not emptydo(Xi, Xj) POP(queue)ifREVISE(csp,Xi, Xj)thenifsize ofDi= 0then returnfalsefor {Xj}doadd (Xk, Xi) toqueuereturntruefunctionREVISE(csp,Xi, Xj)returnstrue iff we revise the domain ofXirevised falsefor eachxinDidoifno valueyinDjallows (x,y) to satisfy the constraint betweenXiandXjthendeletexfromDirevised truereturnrevisedFigure arc-consistency algorithm AC-3.