16-731/15-780 Midterm, Spring 2002Tuesday Mar 12, 2002Name: ________________________________ Andrew Id (Block Capitals): __________________1. Place your name and your andrew email address on the front page.2. You may use any and all notes, as well as the class textbook. Keep in mind, however, that this midterm wasdesigned in full awareness of such.3. The maximum possible score on this exam is 100. You have 80 minutes.4. Good luck!11 Search Algorithm Comparison (15 points)Let’s define the INFGRID problem. In this problem, we have a robot in an infinitely large 2D grid world, and wewish to plan a path from the start location (xs, ys) to the goal location (xg, yg) that is a finite distance away. Possiblemoves are one step moves in any of the cardinal directions {North, South, East, W est}, except that certain of thegrid cells are obstacle cells that the robot cannot move into.Assumptions:• For each algorithm, assume that the successors function always generates successor states by applying moves inthe same order {North, South, East, W est}. We are not using backwards search, and there is no randomizedcomponent in any of the algorithms.• Best-first search and A∗search both use the Manhattan distance heuristic. The heuristic value of a cell at position(x, y) ish(x, y) = |x − xg| + |y − yg|Questions:(a) Is the heuristic h admissible? Just answer yes or no.(b) Fill in the table below with properties of some of our favorite search algorithms, when they are applied toINFGRID.Instructions:• The Complete? and Optimal? columns are yes or no questions. Mark them Y or N based on whether thealgorithm has that property or not, when applied to INFGRID. Note: We say an incomplete algorithm isoptimal iff it returns an optimal solution whenever it returns any solution (this is not necessarily a standarddefinition, but use it to fill out the Optimal? column for this question).• For the Memory usage column, mark an algorithm Low if it uses memory O(d), where d is the maximumdepth of the search tree, and High if its memory usage is greater than O(d). Of course, Low may still beinfinite if d is not bounded, but don’t worry about that.Algorithm Complete? Optimal? Memory usageBreadth-first searchDepth-first searchDepth-first iterative deepeningBest-first searchA∗22 A∗Search (15 points)The following is a graph that we are searching with A∗. Nodes are labeled with letters. Edges are the thick shadedlines. The number above each node is its heuristic value (e.g., h(A) = 2). The number above each edge is thetransition cost (e.g., cost(C, D) = 3). You will see that the optimal path is marked for you with arrows.BACDEFG240010021132131Questions:(a) Oops! Alice has implemented A∗, but her version has a mistake. It is identical to the correct A∗, except thatwhen it visits a node n that has already been expanded, it immediately skips n instead of checking if it needs toreinsert n into the priority queue. Mark the path found by Alice’s version of A∗in the graph below. Use arrowslike the ones that show the optimal path above.BACDEFG240010021132131(b) Bob has also made a mistake. His version of A∗is identical to the correct A∗, except that it declares completionwhen it first visits the goal node G instead of waiting until G is popped off the priority queue. Mark the pathfound by Bob’s version of A∗in the graph below:BACDEFG240010021132131(c) Carmen has implemented the same algorithm as Alice, but not by mistake. In addition to changing the algorithm,she changed the heuristic h so that it generates the values that you see in the graph below. With Carmen’s newheuristic, Alice’s algorithm is optimal, because the new heuristic has a special property we have discussed inclass. What is the property?BACDEFG02113213101223133 Robot Motion Planning (10 points)In the following configuration space, let• d0= distance from robot to closest point on the obstacle in centimeters.• dg= distance from robot to the goal in centimeters.Suppose the robot uses the potential field method of path planning, with the field value defined as dg+ 1/do.(a) Draw (roughly) the path the the robot would take starting from point A on the diagram.(b) Draw (roughly) the path the the robot would take starting from point B on the diagram.(c) Draw (roughly) the path the the robot would take starting from point C on the
View Full Document
Unlocking...