6.01, Spring Semester, 2008—Assignment 11, Issued: Thursday, April 24 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.01—Introduction to EECS ISpring Semester, 2008Assignment 11, Issued: Thursday, April 24Overview of this week’s workNo lecture or software labBefore the start of your design lab on Apr 24 or 25• Read the week 10/11 class notes.• Do the on-line tutor problems in section 11.1.In design lab• Do the nano-quiz.• Work through the design lab.By the beginning of your next software lab on Apr 29 or 30• Do the on-line tutor problems in section 11.2.• Submit written solutions to questions 6, 7, 8, 9, 11, and 12. All written work must conform tothe homework guidelines on the web page.Do athrun 6.01 update to get a directory lab11 that contains the relevant files. In orderto do this entire lab, it will also be important to have the latest version of SoaR. Athenamachines and lab laptops will update automatically; to update your laptop, please downloada new version of SoaRfrom the 6.01 software page.6.01, Spring Semester, 2008—Assignment 11, Issued: Thursday, April 24 2Planning in the real worldThis 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.If we’re going to use search algorithms to plan paths for the robot, the biggest question, as always,is how to represent the real world problem in our formal model. We need to define a search problem,by specifying the state space, successor function, goal test, and initial state. The choices of thestate space and successor function typically have to be made jointly: we need to pick a discrete setof states of the world and an accompanying set of actions that can move between those states.Here is one candidate abstract state-space formulation:states: Let the states be a set of grid squares described by the robot’s indices, i and j into a two-dimensional grid of square cells, overlaid on the original x, y coordinate space of the robot.In this abstraction, the planner won’t care about the orientation of the robot; it will think ofthe robot as moving from grid square to grid square without worrying about its heading, orabout its detailed position within that square.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 (thatis, that could possibly cause the robot to collide with an obstacle). The successor functionreturns a list of states that result from all actions that would not cause a collision. (We willsometimes call these abstract actions “macro-actions”.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 particular grid square, or any of a set of squares(somewhere in the top row, for instance). We cannot ask the robot to move to a particularx, y coordinate at a finer granularity than our grid, to stop with a particular orientation, orto finish with a full battery charge.initial state: The initial state can be any single grid square.The planning part of this is relatively straightforward. The harder part of making this work isbuilding up the framework for executing the plans once we have them. We still have to be ableto control the robot’s wheel velocities in a way that will allow it to move reliably from square tosquare, to support the abstraction we’ve designed.The HGBrain works roughly as follows:• It finds its current actual pose.6.01, Spring Semester, 2008—Assignment 11, Issued: Thursday, April 24 3• It converts the current world location to grid coordinates and plans a path from there to a goalgrid location.• It executes the first “macro-action” in the plan, by driving approximately one grid square tothe north, south, east, or west.• Once it finishes the macro-action, it plans again (just in case someone has kidnapped it1), andexecutes the first macro-action in the new plan.• Once it is near the goal location, it quits driving (though it keeps rechecking its location, again,just in case of kidnapping).Try it out!Question 1: Read the handout up to this point. (And be sure to read the text in the handoutas you go.)Question 2: Try out the planner and see how it works.• Start Soar• Pick Simulator, then she.py (which specifies the “She World” (named after three LAswho defined it) for the simulator).• Pick Brain, then HGBrain.py (from the 6.01/lab11/) directory.• You’ll see a new window, with a picture of the environment drawn as a grid of squares,with the occupied ones drawn in black and the free ones in white. Furthermore, it showsthe robot’s current plan. The green square is centered on the robot’s actual current pose.The gold square is the goal, and the blue squares show the rest of the steps in the plan.• Click start. The robot will drive through the world, with the plan redrawing each timea subgoal is achieved, until it gets to the goal.• While the robot is moving, drag the robot somewhere else. See what happens.GridWorld.pyIn the next couple of sections, we will walk through some of the code that makes this work, startingwith GridWorld.py. This file defines two classes. The Map class is used to specify the locations ofobstacles in the world, and the GridWorld class specifies a state-machine model of a robot movingon a grid corresponding to a map.A Map object just stores a set of “boxes” that describe where the obstacles in the world are. All ofour
View Full Document
Unlocking...