1Lecture 10 • 1 6.825 Techniques in Artificial Intelligence Planning • Planning vs problem solving • Situation calculus • Plan-space planning We are going to switch gears a little bit now. In the first section of the class, we talked about problem solving, and search in general, then we did logical representations. The motivation that I gave for doing the problem solving stuff was that you might have an agent that is trying to figure out what to do in the world, and problem solving would be a way to do that. And then we motivated logic by trying to do problem solving in a little bit more general way, but then we kind of really digressed off into the logic stuff, and so now what I want to do is go back to a section on planning, which will be the next four lectures. Now that we know something about search and something about logic, we can talk about how an agent really could figure out how to behave in the world. This will all be in the deterministic case. We're still going to assume that when you take an action in the world, there's only a single possible outcome. After this, we'll back off on that assumption and spend most of the rest of the term thinking about what happens when the deterministic assumption goes away.2Lecture 10 • 2 Planning as Problem Solving • Planning: •Start state (S) •Goal state (G) • Set of actions In planning, the idea is that you're given some description of a starting state or states; a goal state or states; and some set of possible actions that the agent can take. And you want to find the sequence of actions that get you from the start state to the goal state.3Lecture 10 • 3 Planning as Problem Solving • Planning: •Start state (S) •Goal state (G) • Set of actions • Can be cast as “problem-solving” problem It’s pretty clear that you can cast this as a problem solving problem. Remember when we talked about problem solving, we were given a start state, and we searched through a tree that was the sequences of actions that you could take, and we tried to find a nice short plan. So, planning problems can certainly be viewed as problem-solving problems, but it may not be the best view to take.4Lecture 10 • 4 Planning as Problem Solving • Planning: •Start state (S) •Goal state (G) • Set of actions • Can be cast as “problem-solving” problem • But, what if initial state is not known exactly? start in bottom row in 4x4 world, with goal being C. LKJI HG FE DCBA Actions: N,S,E,W E.g. Just for fun, let's think about moving around on the squares of this grid. The goal is to get to state C, but all we know initially is that the agent is in the bottom row, one of states I, J, K, and L.5Lecture 10 • 5 Planning as Problem Solving • Planning: •Start state (S) •Goal state (G) • Set of actions • Can be cast as “problem-solving” problem • But, what if initial state is not known exactly? start in bottom row in 4x4 world, with goal being C. • Do search over “sets” of underlying states to find a set of actions that will reach C for any starting state. LKJI HG FE DCBA Actions: N,S,E,W E.g. We could try to solve this using our usual problem solving search, but where our nodes would now represent sets of states, rather than single states. So, how would that go?6Lecture 10 • 6 Planning as Problem Solving • Planning: •Start state (S) •Goal state (G) • Set of actions • Can be cast as “problem-solving” problem • But, what if initial state is not known exactly? start in bottom row in 4x4 world, with goal being C. • Do search over “sets” of underlying states to find a set of actions that will reach C for any starting state. LKJI HG FE DCBA {I, J, K, L} Actions: N,S,E,W {G, J, K, H} {J, K, L} N E.g. E The agent starts in the node corresponding to states I,J,K,L, because it doesn’t know exactly where it is. Now, let’s say that it can move North, South, East, or West, but if it runs into an obstacle or the edge of the world, it just stays where it was.7Lecture 10 • 7 Planning as Problem Solving • Planning: •Start state (S) •Goal state (G) • Set of actions • Can be cast as “problem-solving” problem • But, what if initial state is not known exactly? start in bottom row in 4x4 world, with goal being C. • Do search over “sets” of underlying states. LKJI HG FE DCBA {I, J, K, L} Actions: N,S,E,W {G, J, K, H} {J, K, L} N E.g. E So, if it moves north, it could end up in states G, J, K, or H, so that gives us this result node.8Lecture 10 • 8 Planning as Problem Solving • Planning: •Start state (S) •Goal state (G) • Set of actions • Can be cast as “problem-solving” problem • But, what if initial state is not known exactly? start in bottom row in 4x4 world, with goal being C. • Do search over “sets” of underlying (atomic) states. LKJI HG FE DCBA {I, J, K, L} Actions: N,S,E,W {G, J, K, H} {J, K, L} N E.g. E And if it moves East, it could end up in J, K, or L. You can see how this process would continue. And probably the shortest plan is going to be to go east three times (so we could only possibly be in state L) and then continue north until we get to the top, and then go west to the goal.9So, we do have a way to think about planning in the case where you're not absolutely sure what your starting state is. But, it's really inefficient in any kind of a big domain because we're planning with sets of states at the nodes. Just to figure out how the state transition function works on sets of primitive states, we're having to go through each little atomic state in our set of states, and think about how it transitions to some other atomic state. And that could be really desperately inefficient. Lecture 10 • 9 Planning as Logic • The problem solving formulation in terms of sets of atomic states is incredibly inefficient because of the exponential blowup in the number of sets of atomic states.10Lecture 10 • 10 Planning as Logic • The problem solving formulation in terms of sets of atomic states is incredibly inefficient because of the exponential blowup in the number of sets of atomic states. • Logic provides us with a way of describing sets of states. One of our arguments for moving to logical representations was to be able to have a compact way of describing a set of states. You should be able to describe that set of states IJKL by saying, the proposition "bottom row" is true and you might be able to say, well,