Planning

Planning is the task of coming up with a sequence of actions that will achieve a goal starting from an initial state

In planning actions and states are described with properties

Planning works with explicit representations of actions,

states, and goals

It combines problem solving and logical representation

Which actions are relevant?

What is a good heuristic function?

How to decompose a problem?

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

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

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

The regression algorithm is formulated as a state space problem:

1. The intial state is the Goal

2. Actions are performed, if their add-list satisfy the current state

3. 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

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:

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

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

The Sussman Anomaly states that subgoals are not independent from each other

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

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

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

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

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

The key problem is how to represent change.

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