Title: EAI / 11_planning

Q: What is the frame problem?
A: The frame problem deals with the question how to represent things which stay unchanged after performing some action.

Q: What is the ramification problem?
A: The ramification problem deals with the representation of implicit effects.
E.g., if a car moves from one position to another, so does any person in the car, the engine of the car, etc...

Q: What is the qualification problem?
A: The qualification problem deals with the required preconditions (the "qualifications") ensuring that an action succeeds.

Q: What is the STRIPS assumption?
A: Every literala not mentioned in the effect remains unchanged.

Q: What is the difference between STRIPS and ADL?
A: ADL allows
- typing, e.g. p : plane
- equalities/ineqaulities
\(Action(Fly(p : Plane, from: Airport, to: Airport),\)
    \(PRECOND: At(p, from) \land from \neq to\)
    \(EFFECT: \lnot At(p,from) \land At(p, to))\)

Q: What cannot be represented with STRIPS and ADL?
A: Ramifications of actions
(Indirect actions, like dust particles moving with airplanes, need to be represented as direct effects)

Q: Explain progression and regression planning.
A: Progression and regression planning are state-space search methods.

Q: What is the main advantage of regression planning?
A: The main advantage of backward search is that it allows to consider only relevant actions. An action is relevant to a conjunctive goal if it achieves one of the conjuncts of the goal.

Q: What is a partial-order planner?
A: Any planning algorithm that can place two actions into a plan without specifying which comes first is called a partial-order planner.

Q: What are the components of Partial-order Plans?
A: 1. a set of actions
2. a set of ordering constraints
3. a set of causal links
4. a set of open preconditions

Q: Describe an ordering constraint.
A: An ordering constraint is a pair of actions of the form \(A \prec B\), read as "A before B".

Q: What is a contradiction in partial-order plans?
A: \((A \prec B) \land (B \prec A)\)

Q: Explain a causal link in partial-order plans.
A: A causal link between two actions A and B in the plan is an expression of form \(A \overset{p}\longrightarrow B\), read as "A achieves p for B".

Q: Define a conflict in partial-order plans.
A: An action \(C\) conflicts with \(A \overset{p}\longrightarrow B\) if
1. \(C\) has the effect \(\lnot p\) and
2. \(C\) could (according to the ordering constraints) come after \(A\) and before \(B\)

Q: What is a consistent plan?
A: A consistent plan is a plan in which
- there are no cycles in the ordering constraints
- no conflicts with the causal links

Q: What is an open precondition?
A: A precondition is open if it is not achieved by some action in the plan.

Q: When is a solution a consistent plan in partial-order plans?
A: A solution is a consistent plan with no open preconditions.

Q: Explain the POP algorithm.
A: the initial plan contains
- \(Start\) and \(Finish\),
- the ordering constraint \(Start \prec Finish\)
- no causal links
- all the preconditions in \(Finish\) as open preconditions
The successor function arbitrarily picks
- one open precondition \(p\) on action \(B\) and
- generates a successor plan for every possible consistent way of choosing an action\(A\) that achieves \(p\)

Q: How is consistency enforced in the POP algorithm?
A: The causal link \(A \overset{p} \longrightarrow B\) and the ordering constraint \(A \prec B\) are added to the plan.
- Action \(A\) may be an existig action in the plan or a new one.
- If its is new, add it to the plan and also add \(Start \prec A\) and \(A \prec Finish\)

Q: How are conflicts resolved in the POP algorithm?
A: We resolve conflicts between
1. the new causal link and all existing actions and
2. action \(A\) and all existing causal link, providing \(A\) is new.
- A conflict between \(A \overset{p}\longrightarrow B\) and \(C\) is resolved by adding \(B \prec\) C or \(C \prec A\)
- We add successor states for either or both if they result in consistent plans.

Q: What does the goal test need to check in the POP algorithm?
A: The goal test checks whether a plan is a solution to the original planning problem.
Because only consistent plans are generated, the goal test just needs to check that there are no open preconditions.