6.081, Spring Semester, 2007—Work for Week 11 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.081—Introduction to EECS ISpring Semester, 2007Work for Week 11Issued: Tuesday, April 24This handout contains:• Software lab for Tuesday, April 24• Pre-lab problems due April 26• Robot lab for Thursday, April 26• Post-lab due Tuesday, May 1PlanningSo far, our robots have always chosen actions based on a relatively short-term or “myopic” viewof what was happening. They haven’t explicitly considered the long-term effects of their actions.One way to select actions is to mentally simulate their consequences: you might plan your errandsfor the day by thinking through what would happen if you went to the bank after the store ratherthan before, for example. Rather than trying out a complex course of action in the real world, wecan think about it and, as Karl Popper said, “let our hypotheses die in our stead.” We can usestate-space search as a formal model for planning courses of action, by considering different pathsthrough state space until we find one that’s satisfactory.This week, we’ll assume that the robot can know exactly where it is in the world, and plan how toget from there to a goal. Generally speaking, this is not a very good assumption, and we’ll spendthe next two weeks trying to see how to get the robot to estimate its position using a map. Butthis is a fine place to start our study of robot planning.We will do one thing this week that doesn’t seem strictly necessary, but will be an important partof our software structure as we move forward: we are going to design our software so that the robotmight, in fact, change its idea of where it is in the world as it is executing its plan to get to thegoal. This is very likely to happen if it is using a map to localize itself (you’ve probably all hadthe experience of deciding you weren’t where you thought you were as you were navigating througha strange city). This week, the only way it can happen is if, in the simulator, a malicious persondrags the robot to another part of the world as it is driving around.There are still a lot of details to be ironed out before we get this all to work, which we’ll talk aboutlater.Tuesday Software LabPlease do the following programming problems.6.081, Spring Semester, 2007—Work for Week 11 2Experimenting with breadth-first searchThe code file search.py contains the code for the search algorithms and the numberTest domaindiscussed in lecture. Load this into Python (not SoaR, just ordinary Python, in Idle or Emacs) soyou can experiment with it.Try the code: Generate some paths that produce designated numbers by a sequence of doubling,adding 1, subtracting 1, squaring, or negating. For example, show how to generate 99, starting at1. As you try various numbers, take note of the number of steps in the search and the length ofthe remaining agenda. Try the search both with and without using dynamic programming.Robot on an infinite grid: Consider a robot on an infinite grid, with the squares labeled (i, j)for all integers i and j. The robot can move one square north, south, east, or west. Create amodified version of numberTest that will plan a path for the robot from an initial square to adesignated goal square. This requires only a small change to numberTest. In fact, the only thingyou need to change is the definition of successors. Try finding paths from (0, 0) to (n, n) forvarious small values of n, both with and without using dynamic programming.Forbidden squares: Modify your program to also take a list of “forbidden” squares that therobot cannot move into. Name your procedure gridTestForbidden, and have it take four argu-ments: an initial square, a goal square, a list of forbidden squares, and a boolean that says whetheror not to use a visited list. For example,gridTestForbidden((0,0), (4,4), ((1,0),(0,1)), True)should generate a path from (0, 0) to (4, 4) that does not go through either (1, 0) or (0, 1).Knight’s moves: According to the rules of chess, a knight on a chessboard can move two squaresvertically and one square horizontally, or two squares horizontally and one square vertically. Modifyyour robot program so that it finds a path of knight’s moves from a given initial square to a givengoal square on an 8 × 8 chessboard. Make sure to check that the knight remains on the board ateach step. Use your program to find a path that a knight could take to get from the lower leftcorner of the chessboard (0, 0) to the upper right (7, 7).What to turn in: For each of last three problems, include the new procedure you defined, as wellas demonstrations on a set of test cases that you think demonstrates your code is entirely correct.You will be graded on your selection of test cases, as well as on the correctness of your code.Pre-Lab problems for Thursday April 26In this week’s lab we’re going to use search algorithms to plan paths for the robot. The biggestquestion, as always, is how to take our formal model and map it onto the real world. We needto define a search problem, by specifying the state space, successor function, goal test, and initialstate. The choices of the state space and successor function typically have to be made jointly:we need to pick a discrete set of states of the world and an accompanying set of actions that canreasonably reliably move between those states.Here is one candidate state-space formulation:6.081, Spring Semester, 2007—Work for Week 11 3states: Let the states be a set of squares in the x, y coordinate space of the robot. In thisabstraction, the planner won’t care about the orientation of the robot; it will think of therobot as moving from grid square to grid square without worrying about its heading. Whenwe’re moving from grid square to grid square, we’ll think of it as moving from the center ofone square to the next; and we’ll know the real underlying coordinates of the centers of thesquares.actions: The robot’s actions will be to move North, South, East, or West from the current gridsquare, by one square, unless such a move would take it to a square that isn’t free (couldpossibly cause the robot to collide with an obstacle). The successor function returns a list ofstates that result from all actions that would not cause a collision.goal test: The goal test can be any Boolean function on the location grids. This means thatwe can specify that the robot end up in a
View Full Document
Unlocking...