Automated Planning and PDDL Overview

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 RESULT function updates the current state after an HLA or primitive action is run to the next step.
• HIERARCHICAL-SEARCH finds 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).

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.