NAME: ________________________________ CS3361 Exam 1 5 1) Suppose that instead of planning routes for the Georgia Tech campus your program had to plan routes for the entire Atlanta metropolitan area. a) (6 points) If you simply expanded your current representation scheme to include more streets and intersections: i) Would it work? YES ii) What would be the advantages and disadvantages? ADVANTAGES: Simple. No additional programming. DISADVANTAGES: The size of the representation would make searches computationally intractable. Imagine a street such as Peachtree. It may have 100 intersections. Also acceptable: Imagine a CASE in this system. What would be the likelihood that one case would match another? There are thousands of intersections and you would have to match one to the other. b) (14 points) Present an alternative representational scheme for planning routes through the Atlanta Metropolitan area. Also answer the following: i) What are the advantages and disadvantages of this scheme? ii) What type of reasoning strategy would you use to plan a route with this new scheme? NEW REPRESENTATIONAL SCHEME: For this question I was looking for a hierarchical scheme. Imagine that the city is divided into regions, e.g. Buckhead, Emory Area, Georgia Tech, Midtown, HomePark, etc. (Hmm. perhaps you don't have to imagine) For each region of the city you could represent the road segments in that region. The entire Metropolitan Area could then be represented by only the largest roads which serve to connect the regions. Each road segment is represented by a name, a region, and a list of intersections. REASONING STRATEGY: Given this new representational scheme you would use a problem decomposition strategy to get from one intersection to another. The highest level goal is to get from region to region. The two lower goals are to get to the main road within the starting region, and to get to the intersection within the goal region. ADVANTAGES: The advantages are that you have reduced the space of the search. You no longer have to search through all the small streets. You have also provided a means for better CASE retrieval. DISADVANTAGES: Increased complexity of the system. 2) (10 points) Suppose that instead of planning routes from one intersection to another you wanted to plan routes from one street address to another. a) How would you represent this additional knowledge? One method for doing this is to assign a number to each intersection along the street. Example to represent Techwood: (Techwood (North-avenue 200) (3rd 300) (4th 400) .) This can be an assoc list. To get to an address in the 200's you just find an address north of North- avenue. b) How would it affect the efficiency of the program? It should not effect the efficiency of the program. You should be able to carry out the search from intersection to intersection until you reach the desired street at which point you proceed to the apropriate address. 3) (30 points) Consider the following search tree. Each box represents a state where the integer value is an estimated cost for finding a solution from that state (a cost of 0 indicates a goal state). For the following search algorithms trace out the progression of the algorithm by showing the elements of the queue (i.e. successors) just before the search picks the next state to work on at each iteration. Note: the first element of each list are the nodes visited. a) Depth First Search d) Beam Search (N=2) (EXAMPLE: 5 free points) Because their are only 2 children this should look like one of the other searches. Iteration Successor Queue 1 (A) (A) 2 (B C) (B C) 3 (D E C) (D E C) 4 (H I E C) (H I E C) 5 (I E C) (I E C) 6 (E C) (E C) 7 (J K C) (J K C) b) Breadth First Search e) Hill Climbing (A) (A) (I J K L M N (C) P) (B C) (J K L M N P) (F) (C D E) no solution (D E F G) (E F G H I) (F G H I J K) (G H I J K L M) (H I J K L M N P) a) Best First Search (I f) Why is uniform cost search SORTED THE LISTS YOU DIDN"T not possible for this HAVE TO) example? (A) (J K D G M L) (C B) There are no costs only estimated costs. (F B G) In other words, there are no edge weights. (B G M L) (E D G M L) 4) (8 points) Artificial Intelligence deals with both knowledge and process. a) Characterize knowledge. Knowledge consists of CONTENT and FORM. Where content is the stuff that you want to represent including facts, heuristics, associations, procedures, etc. And the FORM is how the various types of knowledge are represented. b) Characterize process. A process is characterized by the SUBTASKS it sets up and the CONTROL it exercises over the subtasks (i.e. how it orders and sequences the subtasks) Also acceptable: Process consists of TASKS and METHODS. Or it consists of GOALS and OPERATORS. 5) (6 points) In Artificial Intelligence we also talk about knowledge representation languages. List 3 reasons why natural languages such as English are bad knowledge representation languages? AMBIGUOUS VAGUE ELLIPTICAL METAPHORICAL 6) (2 point) Write a Lisp symbol known only to you which you can identify when I post the grades. Hint: These are 2 free points. APPLE-PIE 7) (24 points) Fozzie is an intelligent Forklift. Fozzie is instructed to stack boxes such that A is on B, B is on C, and C is on the floor. Below is a picture of the room in which Fozzie finds himself. a) Specify the initial state of the world. Be sure to include the height and contents of Fozzie's lift. LOCATION-FOZZIE (P2) LOCATION-BOX (A, P1) CONTENTS-OF-LIFT(none) LOCATION-BOX (B, P3) HEIGHT-OF-LIFT(h1) LOCATION-BOX (C, P4) HEIGHT-OF-BOX(A, h1) ON-TOP-OF (A, none) HEIGHT-OF-BOX(B, h1) ON-TOP-OF (B, none) HEIGHT-OF-BOX(C, h1) ON-TOP-OF (C, none) b) Specify the goal state. LOCATION-BOX (A, x) ON-TOP-OF (A, B) LOCATION-BOX (B, x) ON-TOP-OF (B, C) LOCATION-BOX (C, x) c) List the operators Fozzie should have to achieve this goal. Be sure to include the preconditions and actions for the operators. OP1: MOVE PRECOND: CONTENTS-OF-LIFT(none) ACTION: LOCATION-FOZZIE(y) OP2: ADJUST-LIFT PRECOND: CONTENTS-OF-LIFT(none) ACTION: HEIGHT-OF-LIFT(h) OP3: PICKUP-BOX PRECOND: x,b,h: (POSITION(x) AND BOX(b) AND HEIGHT(h) AND LOCATION(b,x) AND LOCATION- FOZZIE(x) AND HEIGHT-OF-LIFT(h) AND CONTENTS-OF-LIFT(none) AND HEIGHT-OF- BOX(b,h)) ACTION: CONTENTS-OF-LIFT(y) OP4: LIFT-BOX PRECOND: b,h : (BOX(b) AND HEIGHT(h) AND CONTENTS-OF-LIFT(b)) ACTION: HEIGHT-OF-BOX(h+1) OP5: MOVE-BOX PRECOND: w,z: (BOX(w) AND POSITION(z) AND CONTENTS-OF- LIFT(w)) ACTION: LOCATION-FOZZIE(z) AND LOCATION- BOX(w, z) OP6: PUT-BOX PRECOND: b,c,h : (BOX(b) AND BOX(c) AND CONTENTS-OF-LIFT(b) AND HEIGHT-OF-BOX(c,h) AND HEIGHT-OF- LIFT(h+1)) ACTION: CONTENTS-OF-LIFT(none) AND ON- TOP-OF(b,c) d) Consider a Means-Ends Analysis approach to solving the problem. Specify an operator difference table using the operators you have chosen in (c). D1 = contents of lift D2 = height of box D3 = height of lift D4 = location of box D5 = location of fozzie D6 = on top of Differences Operators D1 D2 D3 D4 D5 D6 MOVE X ADJUST-LIFT X PICKUP-BOX X LIFT-BOX X X MOVE-BOX X X PUT-BOX X