6 01 Fall Semester 2007 Assignment 11 Issued Tuesday Nov 13 1 MASSACHVSETTS INSTITVTE OF TECHNOLOGY Department of Electrical Engineering and Computer Science 6 01 Introduction to EECS I Fall Semester 2007 Assignment 11 Issued Tuesday Nov 13 To do this week in Tuesday software lab 1 Start writing code and test cases for the numbered questions 1 6 in the software lab Paste all your code including your test cases into the box provided in the Software Lab problem on the on line Tutor What you submit to the tutor will not be graded what you hand in next Tuesday will before the start of lab on Thursday 1 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 lab 1 Do the nanoquiz at the start of the lab It will be based on the material in the lecture notes and the homework due on Thursday 2 Answer the numbered questions Questions 14 25 in the robot lab and demonstrate the appropriate ones to your LA before the start of lecture next Tuesday 1 Do the lab writeup providing written answers including code and test cases for every numbered question in this handout On Athena machines make sure you do athrun 6 01 update so that you can get the Desktop 6 01 lab11 directory which has the files mentioned in this 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 course Web site on the Calendar page 6 01 Fall Semester 2007 Assignment 11 Issued Tuesday Nov 13 2 Planning So far our robots have always chosen actions based on a relatively short term or myopic view of 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 errands for the day by thinking through what would happen if you went to the bank after the store rather than before for example Rather than trying out a complex course of action in the real world we can think about it and as Karl Popper said let our hypotheses die in our stead We can use state space search as a formal model for planning courses of action by considering different paths through 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 to get from there to a goal Generally speaking this is not a very good assumption and we ll spend the next two weeks trying to see how to get the robot to estimate its position using a map But this 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 an important part of our software structure as we move forward we are going to design our software so that the robot might in fact change its idea of where it is in the world as it is executing its plan to get to the goal This is very likely to happen if it is using a map to localize itself you ve probably all had the experience of deciding you weren t where you thought you were as you were navigating 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 predict the 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 about later Tuesday Software Lab Please do the following programming problems Experimenting with search The code file search py contains the code for the search algorithms and the numberTest domain discussed in lecture Load this into Python not SoaR just ordinary Python in Idle so you can experiment with it 6 01 Fall Semester 2007 Assignment 11 Issued Tuesday Nov 13 3 A B C D F E G A A 1 2 B C 1 D 1 5 2 F 3 G 1 E B Figure 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 4 Question 1 Consider the graph in figure 1A Imagine it s a road network between cities with short names Formulate a successor function for this domain Problems like this don t have a 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 the names of the roads emanating from a city can serve as the available actions there Formulate a goal test function Use your successor and goal functions and the search function to find the path from A to D using each of our four search methods breadth and depth search with and without dynamic programming Say something interesting about the results Your results will vary depending on the order in which you create the successors if this example does not produce 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 dynamic programming 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 arcs are labeled with an amount of time it takes to traverse them We d like to make plans to traverse 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 different kinds of searches on it Report the results Question 5 How big is the search space for this problem with an without using dynamic programming 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 leaving node 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 and paste the code that you wrote during …
View Full Document
Unlocking...