Concetti generali



Scaricare 37.87 Kb.
07.12.2017
Dimensione del file37.87 Kb.




SHOP: simple Hierarchical Ordered Planner

Corso di Intelligenza Artificiale A.A. 1999/2000


Prof. Alfonso Gerevini

Daniele Armanasco

Daniele Bonassi
armdan@libero.it

danbonas@tin.it



sommario

Corso di Intelligenza Artificiale A.A. 1999/2000 1

1. Introduzione alla pianificazione gerarchica 2

2. Sintassi di shop 3

3. Semantica di shop 4

4. Funzioni supportate da SHOP 5

5. Come scrivere un semplice dominio 5

6. Definizione di problemi 7

7. Definizione di un set di problemi 8

8. Come far funzionare shop e come richiamare un set di problemi 8

9. Note conclusive. 8

1. Introduzione alla pianificazione gerarchica
Per la rappresentazione di un dominio complesso, quale potrebbe essere un dominio reale, si rende necessario l'utilizzo di un pianificatore gerarchico. Il semplice linguaggio STRIPS, infatti, porterebbe a piani dettagliati con un numero elevatissimo di passi. Uno spazio dei piani di tale lunghezza e complessità è tale da non consentire a tecniche di pianificazione strips-like di trovare una soluzione in un tempo ragionevole (si veda ad es. il pianificatore UCPOP ed i risultati comparativi ottenuti). Per ovviare a tale inconveniente si utilizza la tecnica della decomposizione gerarchica, nella quale un operatore astratto (che in SHOP si chiama Metodo), può essere decomposto in un gruppo di passi elementari (qui chiamati operatori) .

Il piano è completo quando ogni passo è un operatore primitivo, e quindi tali azioni possono essere effettuate da un agente esterno.

Shop è un sistema di pianificazione indipendente dal dominio ed è basato su un pianificatore HTN (Hierarchical Task-Network). L'algoritmo di SHOP è sound e completo per una vasta gamma di problemi.

Caratteristiche:

l'esecuzione dei piani avviene nello stesso ordine in cui i piani stessi vengono generati.

Semplice la verifica della completezza e della soundness dei risultati

espressiva rappresentazione del dominio: possibilità di inferenza con clausole di Horn, computazioni numeriche, interazioni con agenti esterni e con sorgenti esterne di informazioni.

SHOP è disponibile liberamente all'indirizzo



2.Sintassi di shop


Gli elementi fondamentali del pianificatore SHOP sono:


  • assiomi: espressioni del tipo

(:- a C1 C2 .. Cn)

L'atomo a è detto head dell'assioma, mentre la lista (C1 C2 .. Cn) è la tail dell'assioma. Il significato dell'assioma è che a è vero se C1 è vero, oppure a è vero se C1 è falso e C2 è vero, e così via fino al termine Cn.

Ad esempio, il seguente assioma dice che una località è raggiungibile a piedi se il tempo è bello e la destinazione è a meno di 2 miglia da casa, o se il tempo non è bello e la destinazione è distante meno di 1 miglio da casa.

(:- (walking-distance ?x)

((wheather-is good) (distance home ?x ?d ) (eval (<= '?d 2)))

((distance home ?x ?d) (eval (<= '?d 1))))




  • task atomici: espressioni nella forma

(s t1 t2 .. tn)

dove s è un simbolo del task e gli argomenti t1, t2, tn sono termini. Il task è detto primitivo se s è un simbolo di task primitivo preceduto da un !), composto se s è un simbolo di task composto.




  • lista di task: una lista di task atomici.




  • operatori: espressioni del tipo

(:operator h D A )

(:operator h D A c)

dove:


h (head dell'operatore) è un task atomico primitivo.

D (operatore delete list) è una lista di atomi che contengono solamente le variabili presenti in h.

A (operatore add list) è una lista di atomi contenenti solo variabili presenti in h.

c (operatore cost) è un numero (per default pari a 1) che indica il costo dell'operatore.

Un esempio di operatore che mette un blocco sul tavolo (nel dominio del mondo dei blocchi) è il seguente:

(:operator (!putdown ?block)

((holding ?block))

((ontable ?block) (handempty)))


  • metodi: liste del tipo

(:method h C1 T1 C2 T2 ... Ck Tk)

dove:


h (head del metodo) è un task atomico

ogni Ci (chiamati precondizioni) sono una lista di letterali

ogni Ti (chiamati tail del metodo) è una espressione Lisp che ritorna una lista di task

Ad esempio due metodi per liberare i blocchi nel mondo dei blocchi sono i seguenti:

(:method (make-clear ?y) ((clear ?y)) nil )

(:method (make-clear ?y)

((on ?x ?y))

((make-clear ?x) (!unstack ?x ?y) (!putdown ?x))

Il primo metodo indica che se y è già libero non dobbiamo fare niente, il secondo dice che se un altro blocco x è sul blocco y si deve liberare x e poi muovere x sul tavolo.


  • piano: una lista del tipo

(h1 c1 h2 c2 ... hn cn )

dove ogni hi e ci , rispettivamente, sono l'head ed il costo di una istanza di un operatore ground.

Per maggiori informazioni si veda il documento all'indirizzo


3.Semantica di shop
La funzione di un operatore

(:operator h D A c)

è di portare alla modifica dello stato corrente rimuovendo tutti gli atomi contenuti in D ed aggiungendo tutti gli atomi contenuti in A.


La funzione di un metodo

(:method h C T)

è di specificare che se lo stato corrente soddisfa C, allora potranno essere eseguiti i task in T nell'ordine in cui si trovano.


Un piano è una lista di head di operatori ground istanziati.

Un problema di pianificazione è una tupla P=(S,T,D) dove S è uno stato, T è una lista di task, e D è un insieme di assiomi, operatori e metodi.

Un planning domain è una lista di assiomi, operatori e metodi.
Per maggiori informazioni si veda il documento all'indirizzo



4.Funzioni supportate da SHOP
Seguono ora alcune delle più importanti funzioni supportate da SHOP. Per un elenco completo e per maggiori dettagli si veda all'indirizzo


(make-domain domain-name D)

Questa funzione dà il nome domain-name al planning domain D organizzando il dominio in una forma precisa voluta.



(make-problem problem-name domain-name S T)

Questa funzione dà il nome problem-name al problem domain (S,T,D), dove D è il planning domain il cui nome è domain-name.


(make-problem-set set-name list-of-problems)

Questa funzione da il nome set-name ad un set di problemi di pianificazione in list-of-problems.



(do-problems name-or-list &key which verbose gc pp)

name-or-list può essere sia una lista di nomi di problemi o un set di problemi. Questa funzione esegue la ricerca dei piani dei problemi inseriti. Gli altri parametri sono opzionali:

which indica il tipo di ricerca utilizzato. Alcuni valori sono:

:first - (di default) ricerca depth first, si ferma dopo che è stato trovato il primo piano.

:all - depth first per tutti i piani.

:shallowest - depth first per il piano più superficiale (o il primo piano più superficiale se ce ne sono più di uno). (In alcuni domini sono i piani meno costosi).

:all-shallowest - depth first per tutti i piani superficiali nello spazio di ricerca.

:id-first - iterative deepening che si ferma dopo il primo piano trovato.

:id-all - iterative deepening per tutti i piani superficiali.
verbose specifica il tipo di informazione da visualizzare.

Per il significato di gc e pp e per maggiori approfondimenti si rimanda alla documentazione di SHOP.


5.Come scrivere un semplice dominio
La parte iniziale di un semplice dominio è bene che inizi con la definizione di alcuni metodi ed operatori che visualizzano a prompt i goals per quel particolare problema in esecuzione.
(make-domain 'nome_dominio ;;qui verrà messo il nome del dominio

'(

(:method (achieve-goals ?goals)



()

'((assert-goals ?goals nil) (metodo_iniziale par1 par2 ...))) ;;qui verrà messo il metodo iniziale.


(:method (assert-goals (?goal . ?goals) ?out)

()

'((assert-goals ?goals ((goal ?goal) . ?out))))


(:method (assert-goals nil ?out)

()

'((!assert ?out)))


(:operator (!assert ?g)

()

?g



0 ; use a cost of 0 since this isn't an actual action

)
Si procede ora alla definizione dei metodi, degli operatori, e degli assiomi necessari per la definizione del dominio. E' bene ricordare che:



  • i metodi sono assimilabili a degli operatori strips in cui abbiamo le precondizioni e le azioni. Queste ultime sono rappresentate da altri metodi (si ricorda che è un pianificatore gerarchico), oppure da operatori, denominati operator e contraddistinti con un "!" prima del loro nome.

(:method (nome_metodo ?param1 ?param2)

((precondiz 1)(precondiz 2)(not(precondiz 3) ....) ;;AND

'((!operatore 1)(metodo 1)(!operatore 2) ....) ;;azioni

((precondiz 3)(precondiz 4) .....)

'((metodo 2)(!operatore n))


Tutte le precondizioni vengono gestite in AND in base al loro valore logico. Se il risultato è True allora vengono eseguiti gli operatori od i metodi sottostanti ciascun gruppo di precondizioni. Successivamente vengono valutate le precondizioni successive, e così via.

Spesso il metodo iniziale deve essere iterato su sé stesso. L'iterazione si rende necessaria tutte le volte che un dominio richiede la verifica ciclica di alcune condizioni, alla conclusione delle quali il piano si conclude. Questa iterazione non è necessaria se il piano si compone solamente di un metodo. Si veda ad esempio il caso del dominio del trasporto, presente come esempio assieme al sorgente SHOP. In questo esempio il piano si conclude unicamente con l'esecuzione del metodo (travel-to ?y).




  • gli operatori sono assimilabili alle azioni dei metodi.

(:operator (!nome-operatore ?param1 ?param2 ?param3 ...)

((del-list1 ?param1 ?param2)(del-list2 ?param3) ...)

((add-list1 ?paramn) (add-list2 ?paramm))).


Quando gli operatori vengono richiamati da qualche metodo, il loro nome seguito dal loro peso, vengono visualizzati a prompt. Ogni operatore possiede una lista di atomi, da cui può aggiungere liste (add-list ?param) e togliere liste (del-list ?param3). Il contenuto di questa lista è trasparente per i metodi, e può quindi essere utilizzata per formulare precondizioni.

Spesso è bene utilizzare operatori vuoti al solo fine di visualizzare a prompt lo stato attuale del pianificatore. Ad es.


(:operator (!sono_in_punto ?punto);;solo per fargli dire dove si trova

() ;; non compie alcuna azione

())

(:- (different ?x ?y) ((not (same ?x ?y))))

(:- (same ?x ?x) nil)
Il dominio si costruisce grazie alla definizione di metodi, operatori ed assiomi che soddisfino completamente tutte le varie condizioni in cui il pianificatore può trovarsi ad ogni passo. La mancanza di questa prerogativa rende incerto il funzionamento di SHOP, con un conseguente lisp overflow od una terminazione anomala; l'unico errore che SHOP riesce a rilevare è la mancanza di parentesi!. Tutte queste condizioni devono essere contemplate nelle precondizioni del metodo principale se esso è iterato su sé stesso.
6.Definizione di problemi
Per definire un problema è necessario avere definito un dominio, delle condizioni iniziali del piano, e degli obiettivi da realizzare.

Per la definizione delle condizioni iniziali è possibile utilizzare il costrutto

(defparameter *guard2*

'(

(condiz1 par1 par2)



(condiz2 par1 par2)

...


))

per non appesantire troppo la leggibilità del codice.

Gli obiettivi da raggiungere, che saranno poi visualizzati prima dell'esecuzione del piano grazie ai metodi elencati sopra, possono essere direttamente elencati in una lista dal nome achieve-goals ed utilizzati nelle precondizioni dei metodi con il costrutto (goal (controllato_punto ?punto)) .

Sotto è riportato un esempio per definire il problema guard1 del dominio guardiano, utilizzante le condizioni iniziali in *guard2* .


(make-problem 'guard1 'guardiano *guard2* '((achieve-goals (

(controlled_point ROB P1 PIANO1)

(controlled_point ROB P2 PIANO1)

(controlled_point ROB P3 PIANO1)

(controlled_point ROB P4 PIANO1)

)))

7.Definizione di un set di problemi
E' possibile definire un set di problemi. Richiamando un set di problemi, verranno eseguiti i singoli problemi in esso contenuti.
(make-problem-set 'set-guardiano '(guard1 guard2))
Nell'esempio riportato qui sopra è stato definito un set di problemi set-guardiano composto da due problemi: guard1 e guard2 . Un set di problemi solitamente si compone di problemi definiti su un unico dominio ma con condizioni di partenza e/o obiettivi diversi.

8.Come far funzionare shop e come richiamare un set di problemi

Per un utilizzo base di SHOP è sufficiente definire un dominio, un set di condizioni di partenza e di goal, ed eseguire un set di problemi composto al minimo da un problema. Per far ciò è sufficiente entrare nella directory shop-files ed eseguire dal prompt di un qualsiasi compilatore common lisp le seguenti istruzioni:
(compile-file "shop.lsp") ;;compila il codice di SHOP

(load "shop") ;;carica il codice di shop

(compile-file "mio_file.lsp") ;;compila il file testo contenente la definizione del dominio, del problema e del set di problemi.

(compile-file "mio_file") ;;carica il file

(do-problems 'mio_problem_set) ;;esegue il problem set chiamato "mio_problem_set"
E' possibile eseguire i problemi con varie tecniche di ricerca. Per default la tecnica utilizzata è la depth first con interruzione sul primo piano trovato, la più rapida ed efficiente. E' possibile utilizzare anche la ricerca iterative-deepening, con il comando
(do-problems 'guardiano :which :id-first)
Per altre modalità di esecuzione si rimanda alla manualistica ufficiale.



9.Note conclusive.
Il pianificatore SHOP presenta una buona efficienza computazionale se confrontato con altri pianificatori non gerarchici. Presenta però una complessità implementativa non indifferente, che ha però il vantaggio di poter applicare tecniche ad hoc efficienti e molto personalizzate.

Un altro grande svantaggio è una manualistica molto limitata, dalla interpretazione formale molto rigorosa e pesante, ma poco descrittiva e chiara per un uso immediato e completo.









©astratto.info 2017
invia messaggio

    Pagina principale