Podcast
Questions and Answers
Which approach uses a Planning Domain Definition Language (PDDL) to manage large state spaces?
Which approach uses a Planning Domain Definition Language (PDDL) to manage large state spaces?
What is the main purpose of using heuristics in planning algorithms?
What is the main purpose of using heuristics in planning algorithms?
In the context of action schemas, what does the precondition define?
In the context of action schemas, what does the precondition define?
What type of planning seeks to reduce complexity by using high-level actions?
What type of planning seeks to reduce complexity by using high-level actions?
Signup and view all the answers
What is the issue associated with forward state-space search in planning?
What is the issue associated with forward state-space search in planning?
Signup and view all the answers
What do you achieve by applying ignore-preconditions in heuristic planning?
What do you achieve by applying ignore-preconditions in heuristic planning?
Signup and view all the answers
In backward search (regression search), what is a key advantage?
In backward search (regression search), what is a key advantage?
Signup and view all the answers
What does the concept of serializable subgoals in planning imply?
What does the concept of serializable subgoals in planning imply?
Signup and view all the answers
What is the advantage of keeping the belief state in 1-CNF?
What is the advantage of keeping the belief state in 1-CNF?
Signup and view all the answers
Which characteristic differentiates a sensorless agent from others?
Which characteristic differentiates a sensorless agent from others?
Signup and view all the answers
In contingency planning, what issue complicates the planning process?
In contingency planning, what issue complicates the planning process?
Signup and view all the answers
How does the percept schema operate in a partially observable environment?
How does the percept schema operate in a partially observable environment?
Signup and view all the answers
What is a critical requirement for online planning to take place?
What is a critical requirement for online planning to take place?
Signup and view all the answers
Which element is crucial when representing the belief state in deterministic problems?
Which element is crucial when representing the belief state in deterministic problems?
Signup and view all the answers
What type of planning is used for handling non-deterministic problems?
What type of planning is used for handling non-deterministic problems?
Signup and view all the answers
What is a consequence of having an incorrect model of the world in planning?
What is a consequence of having an incorrect model of the world in planning?
Signup and view all the answers
What is the primary goal of an HLA with respect to implementations?
What is the primary goal of an HLA with respect to implementations?
Signup and view all the answers
What is the role of precondition-effect descriptions in searching for abstract solutions?
What is the role of precondition-effect descriptions in searching for abstract solutions?
Signup and view all the answers
What is a belief state in the context of nondeterministic environments?
What is a belief state in the context of nondeterministic environments?
Signup and view all the answers
Why is it essential to reduce the number of needed refinements in high-level actions?
Why is it essential to reduce the number of needed refinements in high-level actions?
Signup and view all the answers
In the process of planning and acting, what occurs if a refinement fails to exist?
In the process of planning and acting, what occurs if a refinement fails to exist?
Signup and view all the answers
What is the expected outcome of a sequence of HLAs in achieving a goal?
What is the expected outcome of a sequence of HLAs in achieving a goal?
Signup and view all the answers
What challenge does defining precondition-effect descriptions for HLAs present?
What challenge does defining precondition-effect descriptions for HLAs present?
Signup and view all the answers
What does the term 'reachable set' refer to concerning HLAs?
What does the term 'reachable set' refer to concerning HLAs?
Signup and view all the answers
What does plan monitoring primarily verify?
What does plan monitoring primarily verify?
Signup and view all the answers
When is it beneficial to include 'REPLAN' in contingency plans?
When is it beneficial to include 'REPLAN' in contingency plans?
Signup and view all the answers
How does hierarchical planning assist in managing complex issues?
How does hierarchical planning assist in managing complex issues?
Signup and view all the answers
Which issues can online planning with monitoring effectively address?
Which issues can online planning with monitoring effectively address?
Signup and view all the answers
What is one way online planning can make conditional plans more efficient?
What is one way online planning can make conditional plans more efficient?
Signup and view all the answers
Study Notes
Automated Planning
- Automated planning synthesizes a sequence of actions (plan) guiding an agent from an initial state to a target state (goal).
- Planning is implemented as an application and a common task in many areas (design, manufacturing, scheduling, robotics).
- Classical Planning assumes fully observable, deterministic, and static environments with a single agent.
- This is similar to problem-solving agents, but with factored/structured state representations.
Planning Domain Definition Language (PDDL)
- A state is a conjunction of fluents (ground, function-less atoms).
- Example: Poor ∧ Unknown ∧ At(Truck1, Melbourne) ∧ At(Truck2, Sydney)
- Non-fluents: typically non-ground or function-having atoms.
- Example: At(x, y) and At(Father(Fred), Sydney) .
- Actions are described by action schemas with:
- An action name
- A list of variables
- A precondition (conjunction of literals)
- An effect (aka postcondition), also a conjunction of literals.
- Preconditions define states where an action can be executed.
- Effects define the world's change upon action execution (removing and adding state properties).
- An action schema can be instantiated (ground) into action instances.
Classical Planning
- Finds actions to achieve a goal in discrete, deterministic, and fully observable environments.
- Existing methods include search with custom heuristics and propositional logic with custom code.
- A key issue is large state spaces.
- The solution is factored state representation (using a Planning Domain Definition Language (PDDL) + action schemas).
Algorithms for Classical Planning
- Forward and backward state-space searches need heuristics.
- Backward search (regression search) minimizes branching factor.
- Convert PDDL descriptions to propositional form. Use effective Boolean satisfiability solvers (SAT).
Heuristics for Planning
- Factored state representation helps define heuristics.
- A heuristic function estimates distance to the goal.
- An admissible heuristic never overestimates the actual cost to reach the goal.
- Techniques to create a heuristic:
- Ignoring preconditions (using actions without needing the associated preconditions)
- Ignoring the delete-list part of actions (ignoring potentially reversed effects/negative changes).
Hierarchical Planning
- Manages complexity using high-level actions (HLAs).
- HLAs can have several refinements into a sequence of HLAs or primitive actions.
- An HLA achieves the goal when at least one refinement achieves it.
Example Refinement
- A high-level action (HLA) to go from home to SFO airport.
- Refinement options include options like driving, using shuttle, or taking a taxi).
Search for Primitive Solutions
- The top high-level action (HLA) is often just 'Act'.
- For each primitive action use refinements with steps until a plan is fully specified/derived
- Recursively build a plan sequence until reaching stopping criteria (achieved goal).
- Finding all possible plans is computationally expensive.
Search for Primitive Implementation Solutions
- Uses a breadth-first search to plan actions to refine HLA and find an implementation.
- The
RESULTfunction updates the current state after an HLA or primitive action is run to the next step. -
HIERARCHICAL-SEARCHfinds a solution or indicates a failure.
Searching for Abstract Solutions
- Search for primitive solutions needs to define HLAs.
- Writing precondition and effect descriptions for HLAs is complex.
- This exponential search issue is reduced substantially by HLAs.
- Reachable set: collection of states reached by a sequence of HLAs
- An HLA sequence achieves a goal if its reachable set intersects the goal set.
- Optimization step includes simplified precondition and effects (optimistically), finding a plan then checking refinements of that plan.
Monitoring and Replanning
- Online planning: replan during executions.
- Agent needs to perform:
- Action monitoring - check whether preconditions are met.
- Plan monitoring - verify if the remaining plan will achieve the goal
- Goal monitoring - if better goal set becomes available.
- Contingency plans can be made simpler (when execution fails) using plans such as "REPLAN".
Example: Plan Monitoring with Repair
- Plan is expected to reach a goal (e.g., going from S to G).
- The plan is executed until a state that is a deviation from the expected state in the plan is encountered.
- Execute the plan and find alternative plans to repair the plan.
Summary
- Action schemas streamline the transition function.
- Hierarchical planning handles the state-space-size issue.
- Online planning with monitoring and replanning is highly flexible, handles various issues (e.g., unexpected failures).
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Explore the essentials of automated planning, which involves generating action sequences to achieve goals from given states. This quiz covers the basics of planning, including classical planning concepts and the Planning Domain Definition Language (PDDL) used to describe actions and states.
