6.01, Fall Semester, 2007—Assignment 11, Issued: Tuesday, Nov. 13 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.01—Introduction to EECS IFall Semester, 2007Assignment 11, Issued: Tuesday, Nov. 13To do this week...in Tuesday software lab1. Start writing code and test cases for the numbered questions (1–6) in the software lab. Pasteall your code, including your test cases, into the box provided in the “Software Lab” problemon the on-line Tutor. What you submit to the tutor will not be graded; what you hand innext Tuesday will....before the start of lab on Thursday1. Read the lecture notes.2. Do the Pre-Lab homework problems for week 11 that are due on Thursday (Questions 7-13).3. Read through the entire description of Thursday’s lab....in Thursday robot lab1. Do the nanoquiz at the start of the lab. It will be based on the material in the lecture notesand the homework due on Thursday.2. Answer the numbered questions (Questions 14–25) in the robot lab and demonstrate theappropriate ones to your LA....before the start of lecture next Tuesday1. Do the lab writeup, providing written answers (including code and test cases) for everynumbered question in this handout.On Athena machines make sure you do:athrun 6.01 updateso that you can get the Desktop/6.01/lab11 directory which has the files mentioned inthis handout.• You need the file search.py for the software lab.During software lab, if you are using your own laptop, download the file(s) from the courseWeb site (on the Calendar page).6.01, Fall Semester, 2007—Assignment 11, Issued: Tuesday, Nov. 13 2PlanningSo 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 (at first) doesn’t seem strictly necessary, but will be animportant part of our software structure as we move forward: we are going to design our softwareso that the robot might, in fact, change its idea of where it is in the world as it is executing itsplan to get to the goal. This is very likely to happen if it is using a map to localize itself (you’veprobably all had the experience of deciding you weren’t where you thought you were as you werenavigating through a strange city). This week, the only way it can happen is if, in the simulator,a malicious person drags the robot to another part of the world as it is driving around. However,we will see later in this lab that the robot can in fact be in a similar situation if it fails to predictthe effect of its actions accurately.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.Experimenting with 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) so you canexperiment with it.6.01, Fall Semester, 2007—Assignment 11, Issued: Tuesday, Nov. 13 3A.BGFDACEB.BGFDACE21531211Figure 1: A. A simple map. B. A map with each road labeled by the time it takes to traverse it.6.01, Fall Semester, 2007—Assignment 11, Issued: Tuesday, Nov. 13 4Question 1. Consider the graph in figure 1A. Imagine it’s a road network between cities withshort names. Formulate a successor function for this domain. Problems like this don’t havea natural action space, because different states have different numbers of potential actions(roads that can be followed). If you name the roads (use numbers as the names), then thenames of the roads emanating from a city can serve as the available actions there. Formulatea goal test function.Use your successor and goal functions and the search function to find the path from Ato D using each of our four search methods (breadth and depth search, with and withoutdynamic programming). Say something interesting about the results. (Your results willvary depending on the order in which you create the successors, if this example does notproduce different paths for the different methods, pick a start and goal that do).Question 2. How big is the search space for this problem, with and without using dynamicprogramming? That is, how big can the search trees possibly get?Question 3. Now, look at the graph in figure 1B. It’s the same road network, but now the arcsare labeled with an amount of time it takes to traverse them. We’d like to make plans totraverse this network, but with the goal of arriving at a particular node at a particular time,for example, reaching node F exactly at time 8, assuming we started at node A at time 0.What is an appropriate state space for this planning problem?Question 4. Write down a successor function for this problem. Implement it. Run differentkinds of searches on it. Report the results.Question 5. How big is the search space for this problem, with an without using dynamicprogramming? That is, how big can the search trees possibly get?Question 6. What happens when you ask for a goal that is impossible, for example, leavingnode A at time 0 and arriving at node G at time 4? Is it possible to arrive at F (from A)exactly at time 3? How about exactly at time 4? How does the code deal with these cases?Go to the on-line Tutor at http://sicp.csail.mit.edu/6.01/fall07, choose PS11, andpaste the code that you wrote during lab, including your test cases, into the box providedin the “Software Lab” problem. Do this even if
View Full Document
Unlocking...