What is planning?
Planning is the task of coming up with a sequence of actions that will achieve a goal starting from an initial state
What differantiates planning from searching?
In planning actions and states are described with properties
How can planning be representated?
Planning works with explicit representations of actions,
states, and goals
It combines problem solving and logical representation
What are the key problems of planning?
Which actions are relevant?
What is a good heuristic function?
How to decompose a problem?
What is the situation calculus?
literals receive additional arguments that specify in which state they are true –> e..g. I’m currently at the grovery store, when I am buying milk
What is the frame problem and how can it be solved?
action rules only specify what aspects change when an action is performed, but it is also relevant what does not change
representational problem: we don’t want to represent each possible combination
inferential problem: most of the work is spent on things that actually will not change
we restrict the language and use a special algorithm/a planner
What is the progression algorithm and what is it problem?
The progression algorithm is formulated as a state space problem
1. With an initial state all applicable actions are performed
t is then checked, if the current state matches the Goal
If not, other actions are performed
It is not very efficient since it mostly performs irrelevant actions
What is the regression algorithm?
The regression algorithm is formulated as a state space problem:
The intial state is the Goal
Actions are performed, if their add-list satisfy the current state
It is then checked if the current state matches the initial state of the planning problem
Actions can be applied backwards with the Inverse Appliction Action
What is the inverse action application?
Given a goal description G and let A be an action that is relevant and consistent (does not destroy any other already achieved subgoal)
The predecessor state is determined as follows:
What is the STRIPS language, how does it work and what is a common application example?
The STRIPS language represents knowledge
It works as the following:
States: It decomposes the world in logical conditions and represents a state as a conjuction of literals. It assumes that, what is not known to be true is actually false
Goals: A goal is satisfied, if a state contains all literals as in the goal
Actions: to perform an action certain preconditions must be fulfilled. When performing an action two things happen, STRIPS assumes that every literal which is not affected remains unchanged:
Add: facts that become true after executing the action
Delete: facts that become false after executing the action
What are (nearly) decomposable problems?
Goals are often given as a conjuction of subgoals
To reach the goal, we must solve the different subgoals
But not every problem is easily decompasable, it may be that additional work is required to bring the different subgoals together
What is the Sussman Anomaly?
The Sussman Anomaly states that subgoals are not independent from each other
What is Partial Order Planning and what is a common example?
Progression and regression algorithms are in total order, that means that they try to tackle all of the subproblems on the same time
But since a lot of problems are decomposable, a lot of work can be spared if we try to solve different subproblems at the same time
If actions do not interfere with each other partial order planning can be applied
Shoe example –> putting on both socks and shoes
That means that each plan has two special actions, namely start and finish
What is the difference between state space and plan space search?
In state space search, the search goes through all possible states–> total order
In plan space search, the search goes through all possible plans –> partial order
What are possible heuristics for plan space search?
Heuristics for plan space search are not as well understood as those for state space search
To count the number of distinct open preconditions
Select an open condition than can be satisfied in the fewest number of ways
Which four components has every plan?
Set of actions –> steps of the plan, putting sock on and putting shoe on
Set of ordering constraints –> first put your sock on and then your shoe
Set of causal links –> your sock must be on your foot if you want to put your shoe on
open preconditions –> shoe is not yet put on
How can we search through a plan-space?
Actions: contains only virtual Start and Finish
Ordering constraints: Start > Finish
Causal links: no causal links
Preconditions: all in Finsh are open
picks an open precondition
generates a consistent plan (no conflicts with the causal links)
Goal –>if a consistent plan with no open preconditions is reached
If a an open condition is not achievable or a conflict is not resolvable, we should backtrack
What is the problem with using pure logic for planning (as in the situation calculus)?
The key problem is how to represent change.
What domain-independent heuristics can be used in each case?
Heuristics for State-Space Search (two approaches to find an admissible search heuristic)
The optimal solution to a relaxed problem:
remove all preconditions from actions
remove only the delete-list and find a (minimal) set of actions that collectively achieve the goals
The subgoal independence assumption:
The cost of solving a conjucntion of subgoals is approximated by the sum of the costs of solving them idependently
only admissible if co-ordination causes additional complexity
Heuristics for Plan-Space Search
general heuristics: number of distinct open preconditions
choosing good precondition to refine has also a strong impact