6 01 Spring Semester 2008 Course notes for weeks 10 and 11 1 MASSACHVSETTS INSTITVTE OF TECHNOLOGY Department of Electrical Engineering and Computer Science 6 01 Introduction to EECS I Spring Semester 2008 Course notes for weeks 10 and 11 Long term decision making and search Long term decision making So far in this course we have taken a couple of different approaches to action selection In the non deterministic behaviors section we considered a sets of actions that would satisfy different requirements and chose an action that satisfied as many requirements as possible When we were studying control loops we didn t have the program explicitly consider alternative courses of action but we as designers made models of the controller s behavior in the world and tried to prove whether it would behave in the way we wanted it to taking into account a longer term pattern of behavior Often we will want a system to generate complex long term patterns of behavior but we will not be able to write a simple control rule to generate those behavior patterns In that case we d like the system to evaluate alternatives for itself but instead of evaluating single actions it will have to evaluate whole sequences of actions deciding whether they re a good thing to do given the current state of the world Let s think of the problem of navigating through a city given a road map and knowing where we are We can t usually decide whether to turn left at the next intersection without deciding on a whole path As always the first step in the process will be to come up with a formal model of a real world problem that abstracts away the irrelevant detail So what exactly is a path The car we re driving will actually follow a trajectory through continuous space time but if we tried to plan at that level of detail we would fail miserably Why First because the space of possible trajectories through two dimensional space is just too enormous Second because when we re trying to decide which roads to take we don t have the information about where the other cars will be on those roads which will end up having a huge effect on the detailed trajectory we ll end up taking So we can divide the problem into two levels planning in advance which turns we ll make at which intersections but deciding dynamically exactly how to control the steering wheel and the gas to best move from intersection to intersection given the current circumstances other cars stop lights etc We can make an abstraction of the driving problem to include road intersections and the way they re connected by roads Then given a start and a goal intersection we could consider all possible paths between them and choose the one that is best What criteria might we use to evaluate a path There are all sorts of reasonable ones distance time gas mileage traffic related frustration scenery etc Generally speaking the approach we ll outline below can be extended to any criterion that is additive that is your happiness with the whole path is the sum of your happiness with each of the segments For now though we ll adopt the simple criterion of wanting to find a path with the fewest steps from intersection to intersection 6 01 Spring Semester 2008 Course notes for weeks 10 and 11 2 S sa sb A B ad ac C be bd E D cf eh dh df F H hg fg G Figure 1 Map of small city 1 Now one algorithm for deciding on the best path through a map of the road intersections in our very small world shown in figure 1 would be to enumerate all the paths evaluate each one according to our criterion and then return the best one The problem is that there are lots of paths Even in our little domain with 9 intersections there are 210 paths from the intersection labeled S to the one labeled G We can get a much better handle on this problem by formulating it as an instance of a graph search or a state space search problem for which there are simple algorithms that perform well State space search We ll model a state space search problem formally as consisting of a set possibly infinite of states the system can be in a starting state which is an element of the set of states a goal test which is a function that can be applied to any state and returns True if that state can serve as a goal1 a successor function which is a function that can be applied to a state yielding a set of actionstate pairs the actions name the different choices that can be made in the state and each has associated with it the new state that will result from taking the action in the current state The decision about what constitutes an action is a modeling decision It could be to drive to the next intersection or to drive a meter or a variety of other things depending on the domain The only requirement is that it terminate in a well defined next state and that when it is time to execute the plan we will know how to to execute the action We can think of this model as specifying a labeled graph in the computer scientist s sense in which the states are the nodes and the successor function specifies what arcs exist between the nodes where the labels are the names of the actions 1 Although in many cases we have a particular goal state such as the intersection in front of my house in other cases we may have the goal of going to any gas station which can be satisfied by many different intersections 6 01 Spring Semester 2008 Course notes for weeks 10 and 11 3 S sa sb A ad ac ac A C D cf ad bd df dh F A B B bd sa S F D A E dh bd df B S eh ad sa sb H bs be A B F sa sb be H B H A B Figure 2 Partially expanded search tree for city 1 So for the little world in figure 1 we might make a model in which The set of states is the intersections S A B C D E F G H The starting state is S The goal test is def g x return x E The successor function is defined using a dictionary map1 S A B C D E F H G sa sa sb ac ad be cf dh fg A S S A A B C D F sb ac bd cf bd eh df eh hg B C ad D be F B df H D fg E hg H D E F dh H G G def map1suc cessors x return map1 x We can think of this structure as defining a search tree as shown in figure 2 It has the starting state S at the …
View Full Document
Unlocking...