Classical Planning Flashcards
What is classical planning?
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.
What are the two paradigms for planning?
Search and inference. The difference is state representation.
What is inference?
SATPlan uses domain-independent heuristics for inference, but relies on propositional logic which may be space inefficient.
To define a task, what do we need to specify?
- states
- Actions
- Initial state
- Goal state
What is a state?
A state is a conjunction of ground, functionless atoms.
What is the closed-world assumption?
Any atomic sentence not appearing in the state is assumed to be false.
What is the domain-closure assumption?
All elements of the domain are expressed using constants.
What does an action schema have?
An action schema consists of:
1. Action name
2. List of variables
3. Prconditions
4. Effects
A schema can be universally instantiated
What is the initial state?
A conjunction of ground atoms. Closed-world assumption means that all literals not appearing in the state is assumed to be false.
What is an example of PDDl domain file syntax?
(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)))
)
)
What is an example of PDDL problem file?
(define (problem problem_name)
(:domain domain_name)
(:objects a b c d)
(:init (preda a) (predb b))
(:goal (preda b) (predb a))
)
What is forward progression planning?
We start at the initial state, iteratively applying actions in the forward direction, hoping to reach a goal.
What are complexity issues with progression planning?
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.
What is backward (regression) search?
It starts at the goal, iteratively applying actions in the backward direction, until we find a sequence of steps that reaches the initial state.
What is the advantage of regression planning?
Generally reduced branching factor. Suitable for cases where there is a large number of ground actions.
What is SATPlan?
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.
What are the main components of SATPlan?
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.
What is a bounded planning problem?
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.
What is the disadvantage of TranslateToSAT?
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
What are the advantages of TranslateToSAT?
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.
What are the steps of translateToSat?
- Propasitionalise actions
- Assert propositions for initial states
- Set variable for goal
- Precondition axioms -ie. make propositions from actions into -> statements
- Successor state axioms
- Action exclusion axioms ie. Actions that are not take at the same time
