AIWiki RecentChanges Index

Planning

Planning has been a core topic in artificial intelligence research since its earliest days. It can be thought of as searching for a set of actions that can be executed to achieve a goal.

Types of planners

Planning systems and problems are sometimes divided into the two categories of planning and scheduling. Dean and Kambhampati describe the distinction as follows: “To distinguish between planning and scheduling we note that scheduling is primarily concerned with figuring out when to carry out actions while planning is concerned with what actions need to be carried out.” Roughly speaking, planners tend to focus on choosing and properly sequencing actions such that they achieve a goal without interacting in detrimental ways, while schedulers focus more on resource constraints, including timing.

A different sort of distinction can be made between the process of constructing plans and executing plans. Some problems seem straightforward if they are viewed at a high enough level of abstraction: what could be simpler than going to the store to buy groceries? But executing a plan to do this may encounter difficulties not foreseen during the planning process: the store may be closed (information not available during planning), the car may break down (an unexpected occurrence outside the control of the planner), the lines at the store may be so long to make shopping impractical (the passage of time may not have been considered earlier), and so forth.

Yet another way to think about planning is given by Weld, who identifies the dimensions of construction strategy and component size. On one end of the first dimension we find refinement, “the process of gradually adding actions and constraints; retraction eliminates previously added components from a plan.” On the other end of this dimension we find transformation, which “interleaves refinement and retraction activities.” As for component size, we see a distinction between generative planning, in which plans are built directly from primitive actions, and case-based planning, in which plans are synthesized from existing plans and partial plans recorded in a library.

Of course, there are lots of systems that fall on neither or both sides of these various dichotomies.

Some Planners

This is a list of AI planners and where they were developed, or where implementations are currently accessible. It includes representative examples of the latest research directions, including Graphplan-oriented work and planning under uncertainty, as well as pointers to planners of historical interest.

Resources for Research on Planning

Rao Kambhampati maintains the Planning List Digest, a moderated mailing list for planning, scheduling, and related topics.

One effort that has helped drive planning research forward is the International Planning Competitions, which rely on The Planning Domain Definition Language (PDDL).

Discussion

Some (such as Pat Langley) say that GamePlaying, as it is usually executed (with lots of LookAhead?), is pretty much a kind of planning (it generates conditional plans). I agree. – BayleShanks

CategoryPlanning?

AIWiki RecentChanges Index
Edit this page View other revisions Administration
Last edited 2008-02-13 16:24 UTC by nom13547cmd.nomadic.ncsu.edu (diff)