Automated planning turns descriptions of a world, possible actions, and desired outcomes into strategies an intelligent agent can execute. This lesson introduces the basic planning problem and shows how assumptions about actions, observations, time, and agents shape different kinds of planning.
A planner synthesizes a plan whose execution reaches a goal state. In a problem with several possible initial states, the plan may need to succeed from each one. A plan is not necessarily the shortest sequence; it may also need to be safe, inexpensive, or otherwise optimized.
All flashcards
What is automated planning?
The process of synthesizing strategies or action sequences for an agent to achieve goals, often while optimizing qualities such as cost or safety.
What is a goal state?
A state that satisfies the desired goal conditions of a planning problem.
What assumptions define classical planning?
There is one known initial state, actions are deterministic and have no duration, only one action occurs at a time, and there is a single agent.
How does an MDP differ from a POMDP?
Both use probabilistic action outcomes and reward maximization; an MDP assumes full observability, while a POMDP allows only partial observability.
Why can uncertainty lead to a tree-shaped plan?
Different action outcomes or external events create different possible execution paths, so the plan may need to prescribe actions for each branch.
Quiz questions
What are the three core ingredients used to specify a basic planning problem?Answer: A description of the initial state or states, available actions, and desired goal conditions.
How does forward chaining search for a plan?Answer: It starts from the initial state and explores states reachable by applying actions.
An action may produce either of two outcomes. Why might a single fixed action sequence be inadequate?Answer: Later actions may need to differ depending on which outcome occurs.
How does a hierarchical task network represent tasks?Answer: Tasks can be performed by primitive actions or decomposed into smaller tasks.
What does SATPlan do to solve a planning problem?Answer: It reduces planning to propositional satisfiability, with a satisfying assignment corresponding to a plan.