9Planen (von Roboteraktionen)

Gebeben:	Welt (mögliche Zustände), Anfangszustand, Endzustand. Mögliche Operationen (eines Roboters), die Zustände in andere Zustände überführen.
Gesucht:	Plan, d.h. Sequenz von Operationen, die den Anfangszustand in den Endzustand überführen.

Analog zur "allgemeinen Problemlösung". Beispiel: Block World

Fig 9.1: Planen in der Blockwelt.

Beispiel für Operationen (Aktionen, Bewegungen):

`move( B, From, To)`	bewege Block `B` vom Block `From` auf Block `To`
`stack( B, To)`	bewege Block `B` vom Tisch auf Block `To`
`unstack( B, From)`	bewege Block `B` vom Block `From` auf den Tisch

Plan:

unstack( c, a), 
stack( b, c), 
stack( a, b)

Das Planungsproblem kann theoretisch direkt als Suche im Zustandsraum formuliert werden (s. Wintersemester). Praktisch stellen sich die folgenden Probleme:

Wie repräsentiert man komplexe Zustände, die während der Lösung wenig ändern?
Wie repräsentiert man Zustandsübergänge zwischen solchen Zuständen? .

Diese allgemeine Fragestellung tritt in vielen Bereichen der AI auf und wird als das "Frame-Problem" der AI bezeichnet (nicht mit Frame-Systemen zu verwechseln).

Die nun vorgestellte Wissensrepräsentation versucht das Frame-Problem teilweise zu lösen. Sie basiert auf den Ideen von Green (Formulierung in Logik, 1969), Fikes und Nilsson (Planungsprogramm STRIPS in Lisp, 1971), Kowalski (Formulierung in Logik, 1974), und Warren (Planungsprogramm WARPLAN in Prolog, 1974). Die Transitionen werden nicht durch die explizite Angabe der Zustände (S1 ⇒ S2), sondern durch Zustandsänderungen spezifiziert, womit das Problem (2) beseitigt wird. Die Zustände werden als Listen von wahren Prädikaten repräsentiert, sodass das Problem (1) nach wie vor bestehen bleibt. Ein Ansatz zur Lösung dieses Problems basiert auf der folgenden Idee:

Der Anfangszustand s₀ wird vollständig als eine Liste von wahren Prädikaten repräsentiert.
Die Nachfolgezustände sn werden symbolisch als
s_n = s₀ + a₀ + a₁ + … + a_n
repräsentiert, wobei an die Aktion ist, die im Zustand sn angewender wurde. Wenn der Zustand während der Lösung explizit gebraucht wird, muss er jedesmal berechnet werden. Damit wird die verbesserte Speichereffizienz durch erhöhte Rechenzeit und kompliziertere Implementierung erkauft.

Wissensrepräsentation und Problemlösung

1) Anfangszustand:

Liste von Prädikaten, die alle gelten und den Zustand vollständig beschreiben, z.B. (Fig. 9.1):

start( [ clear( c), clear( b), on( c, a), on( a, t), on( b, t)]).

2) Zielzustand:

Liste von Prädikaten, die alle im Zielzustand gelten, jedoch den Zustand nicht vollständig beschreiben müssen, z.B. (Fig. 9.1):

goal( Goal) :- 
    goal_list( L), 
    subset(L, Goal).
goal_list( [on( a, b), on( b, c)].

3) Aktionen:

beschreiben Transitionen und sind charakterisiert durch:

Can-List:
Liste von Prädikaten, die gelten müssen, damit die Aktion ausführbar ist
(Precondition).
Add-List:
Liste von Prädikaten, die nach der Aktion zusätzlich gelten.
Delete-List:
Liste von Prädikaten, die nach der Aktion nicht mehr gelten.

action( move( B, From, To)) :- 
    /* Move block B from block From to block To */
    block( B), 
    block( From), 
    block( To),
    From \== B, 
    To \== B, 
    From \== To.
can( move( B, From, To), 
    [clear( B), clear( To), on( B, From)]).
add( move( B, From, To), 
    [on( B, To), clear( From)]). 
del( move( B, From, To), 
    [on( B, From), clear( To)]).

Das Planungsprogramm verwendet eine allgemeine Suchmethode im Zustandsraum. Die Transitionen werden mit Hilfe von Aktionen implementiert:

t( Action, Goals1, Goals2, 1) :-
    /* Transition from Goals1 to Goals2 (used forward)
    Goals1 instantiated, Goals2 generated */ 
    action( Action),
    tt( Action, Goals1, Goals2).

tt( Goals1, Goals2, Action) :-
    can( Action, Condition),
    subset( Condition, Goals1),
    add( Action, AddList),
    del( Action, DelList),
    add_set( Goals1, AddList, NewGoals),
    del_set( NewGoals, DelList, Goals2),
    !.

/* Heuristic cost to goal: number of not yet achieved goals */
h( X, H) :-
    goal_list( GL),
    del_set( GL, X, L),
    length( L, H),
    !.    

/* add_set( X, Y, Z): Z=X+Y without duplicates
   X, Y are lists without duplicates, we add Y to X giving Z */
add_set( X, [], X).
add_set( X, [Y| Ys], Z) :-
    add_set( X, Ys, Zs),
    (member( Y, Zs) -> Z = Zs ; Z = [Y| Zs]).

/* del_set( X, Y, Z): Z=X-Y 
   X, Y are lists without duplicates, we delete Y from X giving Z
   i.e. we delete from X elements that are in Y */
del_set( [], _, []).
del_set( [X1| Xs], Y, Z) :-
    del_set( Xs, Y, Zs),
    (member( X1, Y) -> Z = Zs ;  
     Z = [X1| Zs]).

equal( S1, S2) :- /* state equivalence; takes perm. of subgoals into account - inefficient*/
    subset( S1, S2),
    subset( S2, S1).

Inhalt | Index

←zurück | vorwärts→