Visa alla sidor

1.5 Automated Planning

Automated Planning

What is the planning problem?

In a classical planning environment: fully observable,
deterministic, finite, static and discrete. Then the planning problem is this:


• Find a sequence of actions that achieves a given goal when executed from a given initial world state. That is, given
• a set of action descriptions (defining the possible primitive actions by the agent),
• an initial state description, and

• a goal state description or predicate,
• compute a plan, which is
• a sequence of action instances, such that executing them in the initial state will change the world to a state
satisfying the goal-state description. 
• Goals are usually specified as a conjunction of subgoals to
be achieved

Planning and problem solving methods can often solve the same sorts of problems but ....
• Planning is more powerful because of the
representations and methods used
• States, goals, and actions are decomposed into sets of sentences (usually in first-order logic)
• Search often proceeds through plan space rather than state space 
• Subgoals can be planned independently, reducing the complexity of the planning problem

In this submodule you will learn topics such as:

Planning. Representation Language for Planning Problems. Representing actions and their effects. STRIPS and its derivatives. Examples.

Planning with State-Space Search. Forward (Progression) and Backward (Regression) search. Heuristic State-space search.

Partial Order Planning. Planning Graphs. Graph-Plan Algorithm. Planning using SAT solvers

Course Book Reference for this submodule

 Part III Knowledge Representation and Reasoning

Chapter 11 Automated Planning ... 344

Online Lectures on Automated Planning

Lecture Automated Planning Part I Links to an external site.

Lecture Automated Planning Part II Links to an external site.

Lecture Automated Planning Part III Links to an external site.

Lecture Automated Planning Part IV Links to an external site.

 

Additional Material