Idea

use logic-based representation of knowledge

plan efficiently based on this knowledge

Logic and Search

Logic-based representation::

states

actions

goals

Quesiton:

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

Fundamental logic tradeoff

logical expressivness vs. computational efficiency

Content

STRIPS

Planning methods

Extension of STRIPS

simple but expressive planning language

based on propositional logic

state

list of propositions which hold true -> conjunction

logical “and”

all propositions which are not listed are false in this state

goal

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!

acitons

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

When is an action applicable in state s?

if all propositions of the precondition are true in s

Actions simplified representation

Instaed of:

We can do:

forward planning via planning graph

backward planning

Planning graph

S0: initial propositions

A0: actions which can be executed based on S0

S1: propositions of S0 + add list of A0

…

level costs

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

stop computation

if Si = Si+1

if Si satisfies goal

Planning graph for search algorithms

compute level costs for each node

level costs are heurstics -> use A*

Evaulation

Forward planning

suffers from huge branching factors

usually many irrelevant actions…

backward panning tries to find only the relevant actions

Goal relevant action

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]

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

A can be applied

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

Empty R[G,A]

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

Regression of goal G

least constrained R[G,A]

Backward planning

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

Backward planning vs forward planning

branching factors:

forward planning: # legal acitons

backward planning: # goal relevant actions

Last changeda year ago