IAI Chapter 6 Planning
Questions about the lecture 'Introduction to Artificial Intelligence' of the RWTH Aachen Chapter 6 Planning
Questions about the lecture 'Introduction to Artificial Intelligence' of the RWTH Aachen Chapter 6 Planning
-
- 1 / 20
-
Lernkarten
What is the idea of planning?
Planning is looking for plan to reach goal state from initial state
What are the differences of planning towards search? [3]
1. States need to be completely specified
2. Search is interested in all successor states while planning generates some
3. Search searches for sequence of actions while planning for a plan
What are the components of a plan in planning? [3]
1. Actions or plan steps which are paritally ordered // Order
2. Set of variable assignments V(var)=const // Bindings
3. Set of causal relations Si →c Sj with Si satisfies precondition c of Sj // Links
What are different names for actions of a plan? [2]
1. Plan steps and 2. STRIPS operators
What holds for partially ordered actions?
Actions are partially ordered Si < Sj with Si must be executed before Sj
What holds for a complete plan? [2]
1. If forall c in Precond(Sj) exists Si with Si<Sj and c in Effects(Si)
2. If forall Sk with Si<Sk<Sj \neg c not in Effects(Sk)
What holds for a consistent plan? [2]
1. If Si<Sj then Sj!<Si
2. If x=A then x!=B for distinct A and B // Unique Names Assumption
When is a plan a solution?
If it is complete and consistent
What is the idea of a total order plan?
Every step after each other
What is the idea of a partial order plan? [2]
1. Parallel step sequences are found
2. Decisions about order and variable assignment are delayed
How can causal relations be protected in a partial order plan? [3]
1. Conflict is S1 →c S2 and S3 \negc→ not parallel possible
2. Demotion is first S3 \negc→ then S1 →c S2
3. Promotion is first S1 →c S2 then S3 \negc→
What are the characteristics of Standford research institute problem solver (STRIPS) operators? [2]
1. Developed in the early 70s
2. Solver not in use anymore but operators
What is the definition of an action for STRIPS operators? [3]
1. Action name with parameters
2. Preconditions as positive literals
3. Effects as positive and negative literals
What is the definition of initial states for STRIPS operators? [3]
1. Set of ground literals
2. No function symbols
3. Only constants
What is the definition of goal states for STRIPS operators? [2]
1. Set of literals
2. Possible free variables implicitly existentially quantified
What is the definition of a problem in planning? [3]
An initial plan with
1. Operator S1 Start
2. Operator S2 Finish with set of preconditions
3. S1<S2
What is the definition of the POP Algorithm? [4]
1. Make minimal plan out of initial and goal state
2. Return plan if solution else perform Select-Subgoals with Sneed and c
3. Perform Choose-Operator
4. Perform Resolve-Threats of plan and jump to 2.
What is the definition of the Select-Subgoal Algorithm?
Return a step from steps of plan with not yet achieved c
What is the definition of the Choose-Operator Algorithm? [3]
1. Choose operator Sadd with effect c and if no such operator return fail
2. Add link Sadd →c Sneed to links of plan
3. Add Sadd<Sneed to orderings of plan
What is the definition of the Resolve-Threats Algorithm? [3]
1. Forall Sthreat that contradicts Si→cSj in links of plan
2. Add Sthreat<Si OR Sj<Sthreat to orderings of plan
3. If not consistent anymore return fail
