Class Note for CMPSCI 683 at UMass(9)
Class Note for CMPSCI 683 at UMass(9)
Popular in Course
Popular in Department
This 12 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 24 views.
Reviews for Class Note for CMPSCI 683 at UMass(9)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 02/06/15
Victor R Lesser CMPSCI 683 Fall 2004 Why is search the key problemsolving technique in Al Formulating and solving search problems Understanding and comparing several blind search techniques Overview of Material You Should Know You should have read material in Chapters 13 vtmswi m u The state space model provides a formal definition ofa problem and what constitutes a solutionto a problem Complete and Partial Solutions A solution is found by searching through the state space until a lgoall state with specific properties is found Local and Global Properties Asolution is asequence oioperatorsthat Will change an initial state to a goal state the attributes of a state that has certain properties 39 Search involves expiorhg lexplicitly generatingl parts ofthe statespace until a solution is found lorthe entire space is exploredl The point of search isto find a solution Without exploring the entire state space WilliULtl generatingthe complete state space vvmamim Puzzles such as the 8puzzle mm W M E EEE II BEE mm lmnl ma Cryptarithmetic problems SEND M MONEY vtmswi m u A popular benchmark for Al search Solved for n up to 500000 Hoffman Loessi and Moore 1969 If n is even but not ofthe form 6k2 Forj 12 nl2 place queens on elements 1 mi Mufti If n is even but not ofthe form 6k Forj 12 nl2 place queens on elements 0 claw n2e imod n n1 nemel n2e i mod n lfn is odd Use case A or B on n1 and extend with a queen at nn Is this a good benchmark problem for testing search techniques v uxxlcssmrmm e Signal interpretation eg speech understanding Theorem proving eg resolutiontechniques Combinatorial optimization eg VLSI layout Robot navigation eg path planning Factory scheduling eg flexible manufacturing Symbolic computation eg symbolic integration Can we find closed form solutions to these problems States and state spaces Operators representing possible actions Successor function Initial state and goal test Path cost function Examples 8puzzle 8queen path planning map coloring What are the corresponding states operators initial state goal test and path cost v uxxlcssmrmm e r V EJC39ELNU p 8 3 1 6 7 8 Egg Start Slate Goal State States realvalued coordinates of robot joint States integer locations of tiles angles parts of the object to be assembled Actions move blank left right up down Actions continuous motion of robot joints Goal test goal state given Goal test complete assembly Path cost 1 per move Path cost time to execute Note Solving npuzzle problems optimally is NPhard v LesserCSBEClFZEIm a v Lessevcss a qum ll Initial state is Arad Goal state is Bucharest State space representation pamanmhm a The initial slate Arad There is a state corresponding to each Wevexpandinwad A39a city Initial state is the start city state Goal state is the destination city state c Anew expanding smiu Operators correspond to roads there is an operator citya gtcityb ff there is a road from citya to cityb Mad Fagaras madea mmmcuwcea Sibiu Timisoara Zerind Arad Sibiu Timisoara Zerind The nal search tree shows six partial solutions open search nodes v Lesseycssaanum m v Lessevcss a qum 12 A solution to a search problem is a sequence of operators that generate a path from the initial state to a goal state An optimal solution is a minimal cost solution Solution cost versus search cost State space a graph ofthe set of states reachable from the initial states via some operator sequence The state space is sometimes also called the problem space or the search space Path a sequence of operators from one state to some other state Solution a path from an initial state to a goal state Partial solution a path from an initial state to a nondeadend intermediate state 7 Encompasses ramily orpossible solutions Goal test predicate that tests if a state is a goal state goal states may be explicitly listed orspecified by a property Path cost function that assigns a cost to a path often denoted 9 It is the Sum of costs of the operatorsactions of the path is y uxxlcssmrmm i4 Search tree tree or graph of states really nodes explored by the search process 7 search tree orsearch graph is a subgraph orthe state space Search involves maintaining and incrementally extending a set of partial solutions We refer to these partial solutions as search nodes nodes in the search tree The process of extending a partial solution is called expanding a node 7 Basically expanding a node involves Using all7 operators applicable to the latest state orthe node to identiry reachable states and so generate new partial solutions nodes 7 lt is common to referto nodes by tneii39latest states but a node really represents a partial solution operatorsequence Key issues in de ning states 7 which obiectsrelations to represent 7 which conrigurations need to be mapped into separate states Key issues in de ning operators 7 may haye to make explicit unstated assumptions in the problem descriptioni a how staterspecl cgeneral should operators be 7 how much domainrspecific knowledge should be compiled into the operators Developing an effective state space representation of a problem is choosing an appropriate abstraction 7 Without abstraction agents Would be swamped by the details of the i39ealrWorld is y uxxlcssmrmm la 39 There are two main aspects 0 abstraction a iemiwing unneLessaiy detail liom tne state desuimiuns and so tne opeiatois a ramming legal opeiatms tnat aie useless oi inainriani loi athWlng goals A goori abstraction a iemwesas nuLn detail aspossibleto mite il eas enoughtonno a soibtion a maintainsthavaiirihy oltne solutions loitne LonLeptual goals An absiractsolution rabrasants a large number oi bataiiari paths Ollen thara is a trariaoii batwaan sinnriichy anri generality itha repmentation bacornas sospecilicto tha given problem that it cannot ba usari ior avan vary similar problemsl Two stanriarri Aisaarch problems can ba usabto explore tha concept oi abstraction W Three nrissionarias anri thraa cannibais ara on onesiile oia riverTliere is a boat avaiiabiathat can holil upto two people and can ba usari to cross tha rivar iitha cannibais avar outnurnbar tha nrissionarias in any iocationthan a rnissionary will gat aatan oatarrnina howtha boat can ba usedtosalely carry aiitha nrissionarias anri cannibais across tha rivar Tripmule Planning oatarrnina howto get irorn ona iocation to anothar Assume that you knowwhat chy you ara in and hava a map and a car in onionsmin is Straightfoniirard representation of states boatlocm1ocm2locc3loc loc E side1side2riverlboat Results in 37 2181 states Can you simplify by abstraction Abstraction Simpli cation tne particular missionaries and oannibals on eacn side do not matter only numbers do not nave to nave explicit states Witn people in tne boat once in boat Will only Want to cross to otner side now once know number of a type on one side know number on tne otner side Abstract states boatside1m39sside1c39sside1 Results in 2 x 4 x 4 32 states to onionsmin m State abstraction also usually reduces the number of operators move 1 m and 1 c from side1 to side2quot vs the previous move m1 and c1 from side1 to side2quot move m1 and c2 from side1 to side2quot etc Useless operators can also be removed 1mC 2im 16 single missionary goes to goal side in boat The abstract solution using move number of people operators is still a valid solution to the conceptual goal simply have to randomly select particular people when executing y texxlcssmrmnt 22 in its full generality states for this problem would be very complex since they would describe complete con gurations of the world at latitude and longitude xy time is t radio on raining car 1 meters ahead etc To simplify we focus on the problem of nding a sequence of city to city traversals that accomplish the goal in this case our abstract states simply become in city x We can further simplify by identifying important cities ie major cities and cities with roadlunctions and identifying the subset of relevant cities we don39t need to include Amherst in the state space irwe are trying to get to Boston from Worcester Likewise in its full generality there would be a very large number of operators to be considered and it would take a very large number of operators to achieve a solution 7 e 9 go heading h at speed 5 turn radio on etc Mth the abstract states operators are of the form go from city a to city bquot where there is a road from city a to city b A solution to the abstract problem solves the basic goal but does not give us the detail required for say a robot vehicle to actually navigate the trip Still the abstract problem solution allows us to see ifa solution is even possible and tojudge its approximate cost y texxlcssmrmnt 24 Search control strategies Order in which the search space is explored The extent to which partial solutions are kept and used to guide the search process The degree to which the search process is guided by domain knowledge The degree to which control decisions are made dynamically at runtime Choose states to expand next Choose operators to expand the states Execute the set of state operator pairs Update the search graph with some of the new states created Decide if search should be terminated Finding an acceptable solution There are no solutions to the problem Wtth resource constraints v uxxm mfmm 23 A key issue in search is limiting the portion of the state space that must be explored to find a solution The portion of the search space explored can be affected by the order in which states and thus solutions are examined The search strategy determines this order by determining which node partial solution will be expanded next 0 The extent to which partial solutions are kept and used to guide the search process 0 The degree to which the search process is guided by domain knowledge 0 The degree to which control decisions are made dynamically at runtime v uxxm mfmm 23 Completeness does it guarantee to nd a A search tree is a graph representing solution when there is one the search process Time complexity hnwlnng does take Nodes are the data structures from nd a solution which the search tree is constructed Implicit graphs and explicit graphs Branching factor and solution depth Generating and expanding states Optimality does it return the best solution open and closed lists of nodes when there are many Space complexity how much memory does it require Mummy 2 mnmslmlm an defstructure node state parentinode operator Q pathicost m m Am 1w 0 HM h n r m 5 ltElEl mummy m mnmslmlm 2 Basic idea o line simulate exploration of state space by generating successors of already explored states function Imgnmcnt nnalrztnn stmiwy returns a solution or tailiite initialize tio search tree llslng the initial state of pmblnm loop do it39tncre are no candidates tor expansion then return tarlnre image a leaf node rat Expansion attaining tn innmy irtna node cntzills a goal State then return the mrresponding solution else expand the node and add tile faulting ncda to the saattn tree end Search strategies can be classified in the following general way Uninformedblind search Informedheuristic search Multilevelmultidimensionalmultidirection GameAdversarial search Gamesearch deals With tne presence of an opponent tnat takes actions tnat diminish an agent s performance see AlMA cnapters v uxxlossmrmm 34 Blind or uninformed strategies use only the information available in the problem definition Breadthfirst search open list is FIFO queue Uniformcost search shallowest node first Depthfirst search open list is a LIFO queue Depthlimited search DFS with cutoff Iterativedeepening search incrementing cutoff Bidirectional search forward and backward defun dfs nodes goalp successors cond null nodes nil funcall goalp first nodes first nodes t dfs append funcall successors first nodes rest nodes goalp successors Time and space complexity v uxxlossmrmm 3a defun bfs nodes goalp successors cond null nodes nil funcall goalp first nodes first nodes t bfs append rest nodew funcall successors first nodes goalp successors Time and space complexity Breadth Depth Depth Iterative Bi first first Iirrited deepening directionai mg mg m 0M ow 0a ow 5M 5M 0bm baai 5am 5be Failure to detect repeated states can turn a linear problem into an exponential one mm mm mm mm W Yes No No Yes Yes C mm W m mm W mm W mm W D Yes No Yes Yes Yes NM Do not regenerate the state you just came from Do not create paths with cycles Do not generate any state that was generated before using a hash table to store all generated nodes v uxxlcssmrmm 41 There are four phases to problem solving 1 Goal formulation 7 based on current World state deterrnlne an appropnate goal 7 oescnoes deslraole states ortne World 7 goal rorrnulatlon may ll39lvolve general goals or speclrlc goals 2 Problem formulation 7 rorrnallze tne problem ln terrns or states and actlons 7 state space representation 3 Problem solution via search e nnd 5equence5 or actlons thatlead to goal stales e posslbly select oest ortne sequences 4 Execution phase 7 carry out actlons ln selected sequence v uxxlcssmrmm A completely autonomous agent would have to carry out all four phases Often goal and problem formulation are carried out prior to agent design and the agent is given speci c goal instances agents perform only search and execution general goal formulation problem formulation speci c goal formulation etc For nonagentquot problem solving a solution may be simply a speci c goal that is achievable reachable there may be no execution phase The execution phase for a realworld agent can be complex since the agent must deal with uncertainty and errors v uxxlcssmrmm a Adopting goals and using them to direct problem solving can simplify agent design lntelligentJrational agent means selecting best actions relative to a PM but PMs may be complex multiple attributes with tradeoffs Goals simplify reasoning by li ting agent objectives but still organize Irect behavior Optimal vs satis cing behavior best performance vs goal achieved May use both goals to identify acceptable states plus PM to differentiate among goals and their possible solutions v uxxlcssmrmm Complete searchbased problem solving involves both the search process and the execution of the selected action sequence 7 Total cost of searcn7based problem Solvlng is tne sum of tne searcn costs and tne patn costs operatorseguence cost Dealing with total cost may require 7 Comblnlng apples and oranges e g travel miles and CPU time 7 Havlng to make a tradeoff between Searcn tlme and SOlthlOl l cost optimality resource allocation 7 Tnese lSSUeS must be nandled ln the performance measure Problems can vary in a number ofways that can affect the details of how problemsolving search agents are bul t One categor39 ation is presented in AIMA related to accessi ity and determinism 7 Single7state problems Agent knows initial state and exact effect of each actlon Searcn overslngle states 7 Multiple7state problems Agent cannot know ltS exact lnltlal State andortne exact effect of ltS actlorlS Must searcn over state sets May or may notbe able to flnd a guaranteed Solution v uxxlcssmrmm 43 Contingency problems Exact prediction is impossible but states may be determined during execution via sensing Must calculate tree of actions for every contingency lnterleaving search and execution may be better Exploration problems Agent may have no information about the effects of its actions and must experiment and learn Search in real world vs model Continuation of Simple Search 7 How to use neunstics domain knowledge in order to accelerate Search 7 Readan Sectlons 414 2 Characteristics ofMore Complex Search Subproblem interaction More complex View of operatorcontrol costs Uncertainty in search Nonmonotonic domains Search redundancy v uxxlcssmrmm za