Deep dive: Graphplan — planning graph, mutex, estrazione
Companion di
notes.mdsez. 6. Fonti:04_Algoritmi_di_pianificazione_ GRAPHPLAN.pdf.
1. Costruzione del grafo, livello per livello
S0: fatti iniziali
A0: azioni applicabili in S0 + no-op di S0
S1: tutti gli add di A0
A1: azioni con pre in S1 (non mutex tra loro a coppie per le pre? no:
in A1 entrano tutte, i mutex si annotano dopo)
...
Regola pratica: Si+1 = unione degli effetti add di Ai; Ai = azioni le
cui precondizioni sono tutte presenti (non mutex) in Si. Le no-op
garantiscono monotonia: Si ⊆ Si+1 come insiemi (i mutex possono invece
solo diminuire).
2. Mutex: le tre + una regole
Azioni a, b ∈ Ai mutex se:
- effetti inconsistenti:
aaggiungeP,baggiunge¬P; - interference:
acancella una precondizione o un add dib; - competing needs: precondizioni di
aebmutex inSi.
Letterali P, Q ∈ Si mutex se ogni coppia di azioni produttrici
(incluse no-op) e’ mutex (inconsistent support); se un letterale non ha
produttori non puo’ stare nel livello.
Diagramma descritto: due catene causali che convergono sullo stesso livello
con un arco ondulato “mutex” tra nodi; l’arco sparisce ai livelli successivi
quando compare una terza azione produttrice non interferente.
3. Estrazione: ricerca all’indietro con memo
Da Sk con goal G senza mutex interni:
estrai(G, k):
se k = 0: successo se G ⊆ S0
scegli g ∈ G; per ogni a ∈ A(k-1) che produce g e non mutex con le azioni
gia' scelte a questo livello: ricorri su (G ∖ eff(a)) ∪ Pre(a)
memoizza i (G, k) falliti (nogood) per non ripeterli
Se fallisce tutto, espandi a Sk+1 e riprova. La memoizzazione dei nogood
e’ cio’ che rende l’estrazione praticabile.
4. Terminazione e completezza
- Se a un livello il goal e’ senza mutex ed estrazione riesce → piano
parallelo ottimo in numero di livelli (makespan). - Se due livelli consecutivi sono identici (letterali + mutex) e il goal non
e’ estraibile → irraggiungibile: termina con fallimento. - Graphplan e’ corretto e completo per planning proposizionale; la
complessita’ resta esponenziale nel caso peggiore (l’estrazione), ma il
grafo guida e pota enormemente.
5. Eredita’: euristiche moderne
Il relaxed planning graph (senza mutex) da’ h_max (primo livello in cui
tutti i goal compaiono) e h_add/h_FF (costo del piano rilassato
estratto). FF = relaxed plan + hill-climbing: sacrifica l’ammissibilita’
per la velocita’. I landmark raffinano la stima con mete obbligate.
Vedi anche: deepdive_pddl.md, deepdive_regressione.md.