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

Solution:

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

Block World

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?

Initial state:

Actions: contains only virtual Start and Finish

Ordering constraints: Start > Finish

Causal links: no causal links

Preconditions: all in Finsh are open

Succesor function

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

Last changeda year ago