07 Planning

• use logic-based representation of knowledge

• plan efficiently based on this knowledge

Logic-based representation::

• states

• actions

• goals

Quesiton:

• how can we use search algorithms to find a plan of actions which satisfies the goal?

logical expressivness vs. computational efficiency

1. STRIPS

2. Planning methods

3. Extension of STRIPS

• simple but expressive planning language

• based on propositional logic

• list of propositions which hold true -> conjunction

• logical “and”

• all propositions which are not listed are false in this state

• list of propositions

• goal G is achieved in state s, if all propositions in G are true in s

• E.g.:

  • clean(r1) and clean(r2)

  • goal does not specifiy location of robot!

consist of:

• precondition: list of propositions (logical “and”)

• delete list: propositions to delete if action is performed

• add list: propositions to add if action is performed

• if all propositions of the precondition are true in s

Instaed of:

We can do:

• forward planning via planning graph

• backward planning

• S0: initial propositions

• A0: actions which can be executed based on S0

• S1: propositions of S0 + add list of A0

• …

• Assume Si to contain all propositions which are demanded by the goal

• then, i is said to be the level costs

• i is the lower number of actions needed to reach the goal -> shortes path towards goal

• if Si = Si+1

• if Si satisfies goal

• compute level costs for each node

• level costs are heurstics -> use A*

• suffers from huge branching factors

• usually many irrelevant actions…

  • backward panning tries to find only the relevant actions

• action is relevant for a goal G, if it has a proposition in its add list which matches a sub-goal of G

R[G,A] is precondition, s.t.

• A can be applied

• precondtion + add list of A - delete list of A => satisifes goal G

if there is no precondition, s.t. applying A yields G

• least constrained R[G,A]

• start with the goal of the search

• create further “goals” by computing R[G,A] for all goal-relevant actions

• do this until finding a goal, which is satisfied by initial state

branching factors:

• forward planning: # legal acitons

• backward planning: # goal relevant actions