For our case, we'll explore partial-order planning in a classical planning environment. Such an environment is fully observable (as opposed to only partially so) and deterministic (as opposed to having randomness, or being stochastic). Further, the space is finite and static in nature - it does not change in the middle of deliberation. Finally, the environment is "discrete (in time, action, objects, and effects)," as opposed to continuous along any of these axes (Russell, 375. For further reading on the characteristics of environments, see Russell page 41-42).
To understand what partial-order planning entails, it might be helpful to know what planning is, and then what ordered planning entails. To that end, planning is "the task of coming up with a sequence of actions that will achieve a goal" (Russell, 375). That is a fairly straightforward - exactly as we would expect if we weren't speaking of computers and programs.
An example is simple: given a set of actions I can perform, which ones do I choose (and in what order should I apply them) in order to reach my goal? I've got to get to work this morning - what should I do to get there? I might need to wake up, turn off the alarm, shower, take off my wet pajamas and put on something suitable for doing business, and so on, until I reach work in the morning (or, afternoon if it was a late night). However, we wouldn't consider having our agent perform the actual driving of the car in a classical environment. This is because in doing so, our environment loses several of the characteristics we laid forth above - chief among these are that the new environment would become stochastic and continuous.
There are several types of algorithms that allow us to construct a plan. For instance, we briefly examine progression planning, regression planning, and our main topic, partial-order planning. Progression planning is done with a forward state-space search, which is to say that, "we start in the problem's initial state [and consider] sequences of actions until we find a sequence that reaches a goal state" (Russell, 383). This can pose major performance problems because it considers even completely irrelevant actions. As you might guess from its name, regression planning is the opposite - it works backwards from the goal state. This removes the problems associated with examining irrelevant actions, but as Russell notes, it is not without its problems: oftentimes it is not "obvious how to generate a description of the possible predecessors of the set of goal states" (Russell, 384).
What distinguishes partial-order planning from the other two is all in the name - it is not totally-ordered as we see in progression and regression planning. Instead, partial-order planning enables us to "take advantage of problem decomposition." The algorithm "works on several subgoals independently, solves them with several subplans, then combines the subplans" (Russell, 387). In addition, he notes that, "such an approach also has the advantage of flexibility in the order in which it
constructs the plan. That is, the planner can work on 'obvious' or 'important' decisions first, rather than being forced to work on steps in chronological order."
We can see a similar phenomenon in application design - we may not choose to work in any chronological order, but instead work on the parts to construct the whole. Whereas some of the most important design decisions are often made at the beginning of a project, when we know the least about it, the prudent designer may choose to work on more obvious decisions, or decide to choose to work on the most important one
at the time.
Reference:
Russell, Stuart and Norvig, Peter.
Artificial Intelligence: A Modern Approach 2nd Edition. New Jersey: Pearson Education, 2003.
----------------------------------------------
Does that make any sense? Are there areas that could be better explained, or worded? Any input is appreciated.
Hey! Why don't you make your life easier and subscribe to the full post
or short blurb RSS feed? I'm so confident you'll love my smelly pasta plate
wisdom that I'm offering a no-strings-attached, lifetime money back guarantee!
Leave a comment
There are no comments for this entry yet.
Leave a comment
