Classical Planning

Question 1

What is classical planning?

Answer 1

A planning task with the following assumptions:
- finite state space, with initial state and goals tates
- Fully observable states: the agent can tell what state we are in
- Deterministic actions: Each action in a state has one outcome, which can be foreseen by the agent.
- Nothing changes unless the agent changes.
- Goals must be achieved.

Question 2

What are the two paradigms for planning?

Answer 2

Search and inference. The difference is state representation.

Question 3

What is inference?

Answer 3

SATPlan uses domain-independent heuristics for inference, but relies on propositional logic which may be space inefficient.

Question 4

To define a task, what do we need to specify?

Answer 4

1. states
2. Actions
3. Initial state
4. Goal state

Question 5

What is a state?

Answer 5

A state is a conjunction of ground, functionless atoms.

Question 6

What is the closed-world assumption?

Answer 6

Any atomic sentence not appearing in the state is assumed to be false.

Question 7

What is the domain-closure assumption?

Answer 7

All elements of the domain are expressed using constants.

Question 8

What does an action schema have?

Answer 8

An action schema consists of:
1. Action name
2. List of variables
3. Prconditions
4. Effects

A schema can be universally instantiated

Question 9

What is the initial state?

Answer 9

A conjunction of ground atoms. Closed-world assumption means that all literals not appearing in the state is assumed to be false.

Question 10

What is an example of PDDl domain file syntax?

Answer 10

(define (domain domain_name)
(:requirements : strips)
(:predicates (at ?thing ?place) (tire ?tr))
(action: actionName
:parameters (?tr)
:preconditions
:effect (and (not (at ?a ?b)) (not (tire ?tr)))
)
)

Question 11

What is an example of PDDL problem file?

Answer 11

(define (problem problem_name)
(:domain domain_name)
(:objects a b c d)
(:init (preda a) (predb b))
(:goal (preda b) (predb a))
)

Question 12

What is forward progression planning?

Answer 12

We start at the initial state, iteratively applying actions in the forward direction, hoping to reach a goal.

Question 13

What are complexity issues with progression planning?

Answer 13

Irrelevant actions: forward search could explore states and actions that are not relevant to the goal.
Large search space: State space becomes too large for uninformed search.

Question 14

What is backward (regression) search?

Answer 14

It starts at the goal, iteratively applying actions in the backward direction, until we find a sequence of steps that reaches the initial state.

Question 15

What is the advantage of regression planning?

Answer 15

Generally reduced branching factor. Suitable for cases where there is a large number of ground actions.

Question 16

What is SATPlan?

Answer 16

It finds a plan by converting the problem to a propositional KB. A satisfying interpretation of O: assign true to the actions that are part of a correct plan; false to others. It there is no correct plan, O is not satisfiable.

Question 17

What are the main components of SATPlan?

Answer 17

TranslateToSAT: Translate a PDDL description into a proposition KB.
SATSolver: Feed this propositions to a SATSolver.
- If the sentence is unsatisfiable, then there is not a valid plan.
- If a satisfying interpretation is found, then the goal can be achieved.
ExtractPlan: If the goal can be achieved, extract action variables at each time 1< i < t to form a plan.

Question 18

What is a bounded planning problem?

Answer 18

A pair, where
- problem is a planning problem; t is a positive integer
- A solution is a correct plan for problem that has length n.

Question 19

What is the disadvantage of TranslateToSAT?

Answer 19

A planning problem usually requires a large propositional KB.
TranslateToSAT needs to create
- (Tmax + 1) x |Obj|argsp new atomic propositions for each predicate symbol and
- Tmax x |Obj|Argsp new atomic propositions for each action schema

Question 20

What are the advantages of TranslateToSAT?

Answer 20

Speed
- Utilising efficient domain-independent heuristic for propositional logic reasoning.
- Taking advantage of mature SATSolver such as PDDL
- Fixed structure in classical planning domain and problem means that further optimisation is possible.

Question 21

What are the steps of translateToSat?

Answer 21

1. Propasitionalise actions
2. Assert propositions for initial states
3. Set variable for goal
4. Precondition axioms -ie. make propositions from actions into -> statements
5. Successor state axioms
6. Action exclusion axioms ie. Actions that are not take at the same time