Automated

Planning
Classical Planning

Hierarchical Planning

Monitoring and Replanning

Classical Planning
Using Planning Domain Definition Languages
Classical Planning

• Find a sequence of actions to accomplish a goal in a discrete,

deterministic, static, fully observable environment.

• Options we have already discussed:

• Search with a custom heuristic evaluation function.
• Propositional logic with custom code.

• Issue: Large state space.

• Solution: Factored state representation using a Planning Domain

Definition Language (PDDL) + Action schemas
Planning Domain Definition
Language (PDDL) an aspect of the world that
can change over time

• State: a conjunction of ground atomic fluents (in 1-conjunctive normal form; 1-

CNF).
• Action Schema (=precondition-effect description)

PRECOND:

EFFECT:

DEL() ADD()

• Action is applicable to state if entails the precondition of .

• The effect of on is to remove the negated fluents and adds the positive fluents.

• The goal is just like a precondition. E.g.,

Example: Block World
Algorithms
• Forward state-space search: Needs heuristics* to deal with the state space.
• Backward search (= regression search): keeps the branching factor low.
Issue: How do we define heuristics?
• Convert the PDDL description into propositional form and use an efficient
solvers for the Boolean satisfiability problem (SAT).
*Heuristics for Planning Example: maze
Use the factored state description to calculate a heuristic State:
function that estimates the distance from to the goal. If it
is admissible (does not overestimate the distance) then A* Ignore-precondition that
can be used. checks for walls
Example relaxations to create a heuristic:
• Ignore-preconditions: any action can be used in any
state
• Ignore delete-list: no negative effects, problem
progresses monotonic towards the goal.
• Serializable subgoals: subgoals can be achieved
without undoing a previous subgoal.
• State abstraction to reduce the number of states. E.g.,
ignore some fluents.
Hierarchical
Planning
Manage complexity using high-level actions.
High-level Actions

• A high-level action (HLA) have one or several refinements into a

sequence of HLAs or primitive actions.

HLA

Refinement
HLA HLA HLA HLA HLA …
𝑎𝑎 𝑎𝑎𝑎 … “Implementation” with only primitive actions

• An HLA achieves the goal if at least one implementation achieves the

goal.
Example: Refinement

• Two refinements for the HLA to go from home to the SFO airport:

• The agent can choose which implementation of the HLA to use.

Search for Primitive Solutions

• The top HLA is often just “Act” and the agent needs to find an implementation that
achieves the goal.

• Classical Planning
• For each primitive action, provide a refinement of with steps .
• This can recursively build any sequence of actions.
• To stop the recursion, define:

PRECOND: goal is reached

STEPS:

• Issue: This approach has to search through all possible sequences!

• Improvement:
• Reduce the number of needed refinements + increase the number of steps in each refinement.
Search for Primitive Solutions -
Implementation
Searching for Abstract Solutions

• Search for primitive solutions has to refine all HLAs all the way to primitive
actions to determine if a plan is workable.

• Idea: Determine what HLAs do.

• Write precondition-effect descriptions for HLAs (this is difficult because of neg. effects!)
• This results in an exponential reduction of the search space.

• Reachable set: the set of states reachable with a sequence of HLAs in state .

• A sequence of HLAs achieves the goal if its reachable set intersects the goal set.
• Typical implementation:
1. Use a simplified (optimistic) version of precondition-effect descriptions to find a high-
level plan that works.
2. Check if a refinement of that plan that works really exists. If not, go back to 1.
Monitoring and
Replanning
Planning and Acting in Partially Observable, Nondeterministic, and
Unknown Environments
Determinism & Observability -
Belief States
• For nondeterministic or partially observable environments we need belief
states.

• A belief state is a set of possible physical states the agent might be in given
its current knowledge.

• The belief state concept needs to be extended to the factored state

representation.
• A belief state becomes a logical formula of fluents.
• Fluents that do not appear in the formula are unknow.

Technical note: If we manage to keep the belief state in 1-CNF (1-conjunctive normal form,
i.e., fluents are combined with ANDs), then the complexity is reduced from being
exponential in the number of fluents to linear!
Observability -
Percept Schema
• For partially observable environments we need to be able to define what
percepts the agent can get when.
• The agent uses a percept schema to reason about percepts that it can obtains
during executing a plan.
• Example: Whenever the agent sees an object, then it will perceive its color.

PRECOND:

The agent can now reason that it needs to get an object inView to see the
color.

• Percept schemata and observability

• Fully observable: Percept schemas have no preconditions.
• Partially observable: Some percepts have preconditions.
• Sensorless agent: has no percept schemas.
Observability -
Sensorless Planning (Conformant
planning)
• We assume the underlying planning problem is deterministic.

• Similar to sensorless search in Chapter 4. Differences:

• Transition model is a set of action schemata.
• Belief state is represented as a logical formula where unknown fluents are
missing.

• Update:

represents the physical transition model which adds positive and negative literals to the
state description. The state description becomes more and more complete.
Determinism & Observability -
Contingency Planning
• We can create a conditional plan for partially observable planning
problems and non-deterministic problems.
• We already have introduced conditional plans in Chapter 4 and just need
to augment it by:
• Action schemata instead of a transition function.
• Percept schemata to reason about how to get needed percepts.
• The state has a factored representation as facts in 1-CNF.

• Use AND-OR search over belief states.

• Issues:
• Contingency plans become very complicated with non-deterministic effects like
failures in actions or percepts. E.g., moving north fails 1 out of 100 times.
• Plan fails with incorrect model of the world. E.g., actions with missing
preconditions or missing effects, missing fluents, exogenous effects.
→ Online Planning
Execution Monitoring and
Replanning
• Online planning = replan during execution when necessary.
• Requires execution monitoring to determine the need for
replanning. The agent can perform:
• Action monitoring: Only execute action if the preconditions are met.
• Plan monitoring: Verify that the remaining plan will still succeed.
• Goal monitoring: Check if a better set of goals has become available.

• Contingency plans can often be made simpler by having unlikely

branches just say “REPLAN.”
• Process:

Plan Execute Check Replan Execute … Goal

Example: Plan Monitoring with
Repair
1. Initial plan

Actual
path taken

2. Failure detected: 3. Repair + Replan

Should be in E.
Remaining plan will
not work.
Summary

• Action schemata make

specifying the transition function
easier.

• Hierarchical planning lets us deal

with the exponential size of the
state space. The agent can
reason at a more abstract level of
high-level actions and the states
are typically discrete.

• Online planning with monitoring

and replanning is
• very flexible
• can deal with many types of issues
(sensor/actuator failure, imperfect
models of the environment)
• Can make conditional plans smaller
by omitting unlikely paths and
leaving them for later replanning.