Planning

- In this lecture, we're going to talk about automated planning. Eric Nyberg joins me again to help. Planning in artificial intelligence means automatically devising a plan of action to achieve goals, given a description of the initial state, the desired goal, and the list of actions that are possible. An example might be the goal of getting from Times Square to the Bronx Zoo. Plan would be a set of directions, including modes of transportation. Let's describe how planning works at a high level. Planning systems have a way of representing a state of the world and a list of permissible actions, which may have preconditions and effects. To take the subway from Times Square to the Bronx, precondition is being in Times Square. The effect of this action is being in the Bronx and not being in Times Square anymore. A planner finds the sequence of actions that will transform the current state into the goal state. In the example of getting from Times Square to the Bronx Zoo, the initial state is, "I'm in Times Square" and the goal state is, "Be in the Bronx Zoo." Eric, can you talk us through how a planner works? - So a planner has to apply all of the rules that it has to the current state, and to find a sequence of actions that can take you from where you are right now, to the goal state, like the one that you mentioned with the Bronx Zoo. Now, the real challenge here of course, is that I might not be able to take the subway from one stop to the next. So there might be several ways to get to the Bronx Zoo and what the planner has to do is try to find one that works for you, and then it might get very close to the goal but then it might have to backtrack. For example, it might take you very close to the Bronx Zoo geographically, but then find that you would have to walk too long from the stop to get to the zoo. So it might backtrack to find another route that would get you to a station that's closer to the zoo. Now of course, depending on how many possible rules you have, or ways of applying them, there could be many, many different plans. So one of the things we need to think about is the efficiency of a planner like this, because obviously we don't want it thinking for three hours before it comes back to us with the right set of steps in the subway map. - So, the planning task can get really complex the more states, preconditions, and greater the complexity of the goal. - [Eric] Yes, that's right. - So that's one of the big challenges of planning, is managing that complexity. - Yes, exactly. - So, in terms of applications of planning, what are some major ones that we might see in our every day life? - Well, if you think about things like unmanned vehicles, which have to operate on their own, but in uncertain environments, we can't tell them in advance exactly what to do. They're going to have to measure the current situation and determine what's the next step to take that actually makes the most sense. And they have to be able to re-plan. So if I have a robot that's going through a burning building, and then a timber crashes down right in front of it, it has to stop and then re-plan its route. It can't just say, "Oh, my route is no longer valid, I'm done." So planning is very important when you have situations that are likely to change while you're trying to execute a solution, because you have to have the ability to re-plan. - [David] So applications, robotics, unmanned vehicles, even spacecraft. - [Eric] Yeah. - [David] And one that many of us are familiar with by now is Google Maps and its navigation capability. - Exactly. - That also uses planning, doesn't it? Great. So, planning systems automatically devise a plan of action to achieve goals, given a description of an initial state, desired goal, and possible actions. Planning is an exercise in combinatorial explosion and controlling combinatorial explosion. Key applications include unmanned vehicles and robotics.