Pianificazione: STRIPS, il mondo dei blocchi, euristiche dal rilassamento e pianificazione negli agenti IA

Il linguaggio STRIPS e PDDL, pianificazione in avanti e all’indietro, le euristiche hmax e hadd, l’anomalia di Sussman, la pianificazione gerarchica e la ripianificazione — dal robot Shakey agli agenti IA che si scrivono la lista delle cose da fare.

14 minuti Matěj Žalmánek 2026-10-15

Serie Basi di IA Parte 25 di 52

1. Mappa dell’intelligenza artificiale: che cos’è ciascuna cosa e come si incastra tutto
2. Breve storia dell’intelligenza artificiale: da Turing ai modelli linguistici
3. Dati, modello, addestramento, inferenza: i concetti di base su un unico esempio
4. Come leggere la notazione matematica: simboli, indici, sommatorie e quantificatori
5. Insiemi e relazioni: i mattoncini con cui si costruiscono le definizioni nell’IA
6. Funzioni e applicazioni: perché ogni modello di IA è una funzione
7. Logica e dimostrazioni: le regole con cui si ragiona nell’IA
8. Grafi e alberi: la struttura su cui poggiano la ricerca e le reti neurali
9. Algebra lineare per l’apprendimento automatico: vettori, matrici e perché l’IA soprattutto moltiplica
10. Derivate, gradiente e regola della catena: come un modello capisce in quale direzione imparare
11. Discesa del gradiente: come impara un modello
12. Che cos’è la probabilità: dal lancio di un dado agli assiomi di Kolmogorov
13. Probabilità condizionata e teorema di Bayes: come cambiare una stima quando scopri qualcosa di nuovo
14. Variabile aleatoria e funzione di ripartizione: una sola funzione che dice tutto sulla distribuzione
15. Funzione di densità e funzione di massa: perché una variabile continua ha probabilità zero in un punto
16. Valore atteso, varianza e covarianza: dove si trova una distribuzione, quanto è larga e che cosa è legato a che cosa
17. Panoramica delle distribuzioni di probabilità: Bernoulli, binomiale, Poisson, uniforme, normale ed esponenziale
18. Legge dei grandi numeri e teorema del limite centrale: perché le medie si comportano in modo così prevedibile
19. Statistica e stima dei parametri: massima verosimiglianza, MAP e intervalli di confidenza
20. Teoria dell’informazione: entropia, entropia incrociata e divergenza KL — da dove vengono le funzioni di perdita
21. Ricerca nello spazio degli stati: BFS, DFS, UCS e A* con animazioni
22. Giochi e avversari: minimax, potatura alfa-beta e Monte Carlo tree search
23. Soddisfacimento di vincoli: backtracking, propagazione dei vincoli e AC-3 su un sudoku e una mappa delle regioni ceche
24. Logica e sistemi basati sulla conoscenza: concatenazione in avanti e all’indietro, risoluzione e sistemi esperti
25. Pianificazione: STRIPS, il mondo dei blocchi, euristiche dal rilassamento e pianificazione negli agenti IA
26. Ricerca locale e ricottura simulata: un commesso viaggiatore tra i capoluoghi di regione cechi
27. Algoritmi genetici: popolazione, incrocio, mutazione e selezione su uno zaino per l’escursione
28. Strategie evolutive e programmazione genetica: dalla regola di un quinto alla legge di Keplero
29. Ottimizzazione con colonie di formiche: come una traccia di feromone trova un percorso breve
30. Ottimizzazione a sciame di particelle: inerzia, esperienza propria ed esperienza dello sciame
31. Neuroevoluzione: evoluzione dei pesi e della forma delle reti neurali e l’algoritmo NEAT
32. Insiemi fuzzy e funzioni di appartenenza: come scrivere «un po’ caldo»
33. Logica fuzzy e probabilità: perché «un po’ caldo» non significa «probabilmente caldo»
34. Logica fuzzy: t-norme, implicazioni e regole SE–ALLORA
35. Controllo fuzzy: Mamdani e Sugeno, dal ventilatore al pendolo inverso su un carrello
36. Clustering fuzzy: l’algoritmo fuzzy c-means e i punti tra i cluster
37. Sistemi neuro-fuzzy (ANFIS): regole fuzzy che imparano dai dati
38. Catene di Markov: matrice di transizione, distribuzione stazionaria e PageRank
39. Modelli di Markov nascosti: l’algoritmo di Viterbi e il casinò disonesto
40. Reti bayesiane: perché l’erba è bagnata e che cosa significa per l’irrigatore
41. Filtro di Kalman: come stimare da misure imprecise dove si trova un’auto e a che velocità va
42. Tipi di apprendimento automatico: supervisionato, non supervisionato, semi-supervisionato e altri
43. Prompt, contesto e RAG: come dare a un modello le informazioni giuste
44. Autoencoder variazionali (VAE): immagini nuove da uno spazio latente continuo
45. Reti generative avversarie (GAN): il falsario contro il detective
46. Modelli di diffusione: come il rumore puro diventa un’immagine
47. Processi decisionali di Markov: stati, azioni, ricompense ed equazioni di Bellman
48. Q-learning e DQN: imparare il valore delle azioni, dalla tabella alla rete neurale
49. Policy gradient e PPO: imparare direttamente la politica
50. Come funziona un agente IA: un modello linguistico in un ciclo con strumenti
51. Programmare con agenti IA: incarico, test e controllo
52. Valutazione e sicurezza dei sistemi di IA: come misurare e come sorvegliare

Programma completo della serie 52 di 83 argomenti pubblicati

Alla fine degli anni Sessanta il robot Shakey dello Stanford Research Institute girava per alcune stanze, spingeva scatole e spegneva le luci. Fu il primo robot a ragionare sulle proprie azioni: riceveva un obiettivo («porta la scatola nella stanza accanto») e capiva da solo quali azioni, e in quale ordine, lo avrebbero raggiunto. Il linguaggio con cui lo faceva si chiama STRIPS — e le sue idee oggi le trovi nella logistica, nei videogiochi e nel ciclo dell’agente IA che ti scrive il codice.

Riprende le parti Ricerca nello spazio degli stati e Logica e sistemi basati sulla conoscenza.

1. Pianificazione: una ricerca che vede dentro

Pianificare significa cercare una sequenza di azioni che porti all’obiettivo — esattamente come nella parte sulla ricerca. La differenza sta nel modo in cui il problema è descritto. Nel labirinto lo stato era una scatola nera e l’algoritmo ne sapeva solo dove portano le azioni. Il pianificatore invece vede dentro: lo stato è un elenco di fatti sul mondo e un’azione dice di quali fatti ha bisogno e quali cambia. Grazie a questo il pianificatore sa ricavare da solo una stima di quanto sia lontano l’obiettivo — non devi scrivergli a mano nessuna euristica.

2. Il linguaggio STRIPS

Definizione — problema di pianificazione STRIPS

È dato un insieme finito di atomi F (proposizioni sul mondo). Uno stato è un sottoinsieme s ⊆ F — gli atomi che in esso sono veri; ciò che non è in s è falso.

Un’azione a è una terna (pre(a), add(a), del(a)) di sottoinsiemi di F: precondizioni, atomi aggiunti e atomi rimossi. L’azione è applicabile in s se pre(a) ⊆ s, e lo stato risultante è

T(s, a) = (s ∖ del(a)) ∪ add(a)

T(s, a)

lo stato dopo l’esecuzione dell’azione — la funzione di transizione che nella parte sulla ricerca forniva il programmatore; qui il pianificatore la ricava da solo dalla descrizione dell’azione

s

lo stato di partenza: tutto ciò che l’azione non menziona passa invariato nel nuovo stato (l’ipotesi di STRIPS che risolve il problema del frame — non serve elencare ciò che non cambia)

del(a)

gli atomi che l’azione rende falsi; si sottraggono con la differenza insiemistica ∖

add(a)

gli atomi che l’azione rende veri; si aggiungono con l’unione solo dopo la rimozione, quindi un atomo presente in entrambe le liste alla fine è vero

Un problema è una quaterna (F, A, s₀, G), dove G ⊆ F è l’obiettivo. Un piano è una sequenza di azioni a₁, …, a_k, ciascuna applicabile nello stato prodotto dalle precedenti, tale che nell’ultimo stato s_k valga G ⊆ s_k.

Esempio — un’azione passo per passo

Il blocco C sta su A, B è accanto. L’azione sul tavolo(C, A) ha pre = {su(C, A), libero(C)}, add = {tavolo(C), libero(A)}, del = {su(C, A)} (la descrizione completa delle azioni è nella sezione successiva).

s = {su(C, A), tavolo(A), tavolo(B), libero(B), libero(C)}

pre ⊆ s?   su(C, A) ∈ s, libero(C) ∈ s → l’azione è applicabile

s ∖ del = {tavolo(A), tavolo(B), libero(B), libero(C)}

(s ∖ del) ∪ add = {tavolo(A), tavolo(B), tavolo(C), libero(A), libero(B), libero(C)} — tutti e tre i blocchi sul tavolo

STRIPS nacque nel 1971 (Fikes e Nilsson) proprio per Shakey. Il suo erede di oggi è il linguaggio PDDL, in cui dal 1998 si formulano i problemi per le competizioni internazionali di pianificatori. Un’azione vi si scrive come schema con variabili:

(:action sul-tavolo
  :parameters (?a ?b)
  :precondition (and (su ?a ?b) (libero ?a))
  :effect (and (tavolo ?a) (libero ?b) (not (su ?a ?b))))

3. Il mondo dei blocchi

Il classico problema di prova della pianificazione: sul tavolo ci sono dei blocchi, alcuni impilati. Con un’azione prendi un blocco su cui non c’è niente e lo posi sul tavolo o su un altro blocco libero. Gli atomi sono di tre tipi: su(A, B) — A sta su B, tavolo(A) e libero(A).

Azioni nel mondo dei blocchi

• sul tavolo(A, B): pre = {su(A, B), libero(A)}, add = {tavolo(A), libero(B)}, del = {su(A, B)}
• dal tavolo(A, C): pre = {tavolo(A), libero(A), libero(C)}, add = {su(A, C)}, del = {tavolo(A), libero(C)}
• sposta(A, B, C): pre = {su(A, B), libero(A), libero(C)}, add = {su(A, C), libero(B)}, del = {su(A, B), libero(C)}

Lo schema con variabili il pianificatore prima lo istanzia (grounding): sostituisce alle variabili tutte le combinazioni di blocchi. Per n blocchi ci sono n(n − 1) azioni «sul tavolo», altrettante «dal tavolo» e n(n − 1)(n − 2) spostamenti, in totale n²(n − 1). Per tre blocchi sono 9 · 2 = 18 azioni, per sei 36 · 5 = 180. In ogni stato però ne sono applicabili solo poche — i blocchi su cui non c’è niente sono pochi.

Il mondo sembra un giocattolo, ma cresce in fretta. Tre blocchi si possono disporre in 13 modi, quattro in 73, cinque in 501 e sei già in 4 051. Da dove vengono questi numeri:

numero di stati = ∑_k=1ⁿ n! · C(n − 1, k − 1) / k!

n!

mettiamo tutti i blocchi in un’unica fila — ogni ordine è un candidato; le torri le otteniamo tagliandolo

C(n − 1, k − 1)

tagliamo la fila in k torri non vuote: scegliamo k − 1 degli n − 1 spazi tra i blocchi. L’ordine dentro una torre conta (A su B non è B su A), per questo tagliamo un ordine e non un insieme

k!

l’ordine delle torri sul tavolo non conta — due torri affiancate sono lo stesso stato, in qualunque ordine le elenchiamo. Ogni stato è stato quindi contato k! volte

Il pianificatore li ha contati in un altro modo — ha percorso tutti gli stati raggiungibili — e gli è venuto lo stesso risultato. Proviamo due problemi. Nel più grande sul tavolo ci sono due torri A–B–C e D–E–F (scritte dal basso) e l’obiettivo è un’unica torre F–E–D–C–B–A:

4. Pianificazione in avanti

Definizione — pianificazione in avanti (progressione)

Ricerca nello spazio degli stati a partire dallo stato s₀: i successori dello stato s sono gli stati T(s, a) per tutte le azioni a applicabili in s. Test dell’obiettivo: G ⊆ s.

from collections import deque

def proved(stav, akce):
    return (stav - akce.odeber) | akce.pridej

def planuj(start, cil, akce):
    okraj, rodic = deque([start]), {start: None}
    while okraj:
        stav = okraj.popleft()
        if cil <= stav:                      # tutti gli atomi dell'obiettivo sono veri
            return plan_z(rodic, stav)
        for a in akce:
            if a.predpoklady <= stav:
                dalsi = proved(stav, a)
                if dalsi not in rodic:
                    rodic[dalsi] = (stav, a)
                    okraj.append(dalsi)

Sul problema della torre la ricerca in ampiezza trova il piano più corto di 6 azioni, ma nel farlo espande 2 132 stati — più della metà di tutti i 4 051. Non sa infatti nulla della direzione in cui si trova l’obiettivo.

5. Euristiche dal rilassamento

Nella parte sulla ricerca l’euristica per il labirinto ce la siamo inventata noi. Il pianificatore sa calcolarla dalla descrizione delle azioni — semplificando il problema, risolvendolo e usando il costo della soluzione semplificata come stima.

Definizione — rilassamento senza rimozioni

Il problema rilassato si ottiene ponendo del(a) = ∅ per tutte le azioni. Un atomo che diventa vero resta allora vero per sempre.

Il costo di un atomo p a partire dallo stato s nel problema rilassato si stima ricorsivamente: c(p) = 0 per p ∈ s, altrimenti c(p) = il minimo, sulle azioni a con p ∈ add(a), del valore 1 + c(pre(a)), dove il costo di un insieme di atomi è

• per h_max il massimo dei costi dei suoi atomi — l’euristica è ammissibile,
• per h_add la somma dei costi dei suoi atomi — una guida più precisa, ma può sovrastimare.

L’euristica dello stato s è il costo dell’insieme obiettivo G.

c(p) = min_{a : p ∈ add(a)} [ 1 + c(pre(a)) ]

c(p)

la stima di quante azioni servono perché l’atomo p diventi vero (per gli atomi già veri è 0)

min sulle azioni con p ∈ add(a)

un atomo può essere introdotto da più azioni; scegliamo la più economica, perché la strada il pianificatore la sceglie da sé

1

il costo dell’azione stessa che alla fine aggiunge p

c(pre(a))

il costo di rendere l’azione applicabile — soddisfare tutte le sue precondizioni. Qui h_max e h_add differiscono: il massimo presuppone che le precondizioni si soddisfino «insieme» e che la loro preparazione si sovrapponga, la somma che ognuna richieda un lavoro a parte

def ceny(stav, akce, agreguj):             # agreguj = max (hmax) oppure sum (hadd)
    c = {p: 0 for p in stav}
    zmena = True
    while zmena:                             # ripeti finché qualche costo migliora
        zmena = False
        for a in akce:
            if all(p in c for p in a.predpoklady):
                nova = 1 + agreguj(c[p] for p in a.predpoklady)
                for p in a.pridej:           # a.odeber si ignora — rilassamento
                    if nova < c.get(p, float("inf")):
                        c[p], zmena = nova, True
    return c

def h(stav, cil, akce, agreguj):
    c = ceny(stav, akce, agreguj)
    return agreguj(c[g] for g in cil)        # obiettivo irraggiungibile: h = ∞

Esempio — h_max e h_add per l’anomalia di Sussman

Inizio: C sta su A, B è accanto; obiettivo G = {su(A, B), su(B, C)} (il problema lo analizziamo più avanti). Costi degli atomi per strati:

costo 0 (veri): tavolo(A), tavolo(B), su(C, A), libero(B), libero(C)

costo 1: sul tavolo(C, A) → tavolo(C), libero(A);   dal tavolo(B, C) → su(B, C);   sposta(C, A, B) → su(C, B)

costo 2: dal tavolo(A, B) richiede tavolo(A), libero(A), libero(B) con costi 0, 1, 0

   h_max: 1 + max(0, 1, 0) = 2,   h_add: 1 + (0 + 1 + 0) = 2 → su(A, B) ha costo 2

h_max(s₀) = max(2, 1) = 2,   h_add(s₀) = 2 + 1 = 3,   davvero necessario: h* = 3

h_max sottostima, perché conta solo l’obiettivo più costoso: su(A, B) costa due azioni, ma su(B, C) ne richiede una terza tutta sua, e il massimo la ingoia. La somma la conta e qui centra il valore esatto. Sul problema della torre l’effetto è più marcato: dalla partenza h* = 6, h_max = 3, il numero di obiettivi non soddisfatti è 5 e h_add = 15 — la somma conta la preparazione comune (scoprire i blocchi) di nuovo per ogni obiettivo e sovrastima il costo reale di due volte e mezzo.

Teorema — h_max e il numero di obiettivi non soddisfatti sono ammissibili

Ammissibilità dalla parte sulla ricerca: h(s) ≤ h*(s), dove h*(s) è la lunghezza del piano più corto da s.

h_max. Prendiamo un piano più corto a₁, …, a_k del problema reale. È un piano anche per il problema rilassato (senza rimozioni a ogni passo sono veri almeno gli stessi atomi, quindi le precondizioni restano soddisfatte). Per induzione su i: ogni atomo vero dopo i azioni ha c_max ≤ i — o era vero già prima, oppure l’ha aggiunto l’azione a_i, le cui precondizioni erano vere dopo i − 1 azioni e hanno quindi costo ≤ i − 1, perciò 1 + max ≤ i. Tutti gli atomi dell’obiettivo sono veri dopo k azioni, quindi h_max(s) = max_{g ∈ G} c(g) ≤ k = h*(s).

Numero di obiettivi non soddisfatti. Gli obiettivi del mondo dei blocchi sono atomi su(·, ·) e ogni azione aggiunge al massimo uno di questi atomi. Per soddisfare m obiettivi mancanti servono quindi almeno m azioni.

Per h_add la dimostrazione fallisce all’ultimo passo: la somma dei costi può superare k, perché le stesse azioni del piano vengono contate per più obiettivi.

Tre euristiche sul problema della torre, tutte con l’algoritmo A*:

L’ammissibile h_max trova l’ottimo e risparmia oltre il 90 % del lavoro. Anche il numero di obiettivi non soddisfatti nel nostro mondo è ammissibile (ogni azione posa un solo blocco, quindi soddisfa al massimo un obiettivo) e qui funziona ancora meglio. h_add espande meno di tutte, ma lo paga: il piano ha un passo in più del necessario. Nessuna euristica vince sempre — e i pianificatori reali come FF o Fast Downward hanno interi insiemi di euristiche che combinano.

Come lavora A* con h_max si vede meglio su un problema piccolo — l’anomalia di Sussman, che analizzeremo due sezioni più avanti. Ogni riga è uno stato espanso (torri dal basso); A* prende sempre lo stato con il minimo f = g + h, dove g è il numero di azioni dall’inizio, e a parità quello scoperto per primo:

La ricerca in ampiezza sullo stesso problema espande tutti i 13 stati, A* con h_max solo 5. Al terzo passo prende la strada sbagliata — mette C su B — perché quello stato ha f = 3 come il percorso giusto ed è stato scoperto prima. Il passo successivo rimedia subito. Il primo stato obiettivo espanso ha il piano più corto — A* lo garantisce quando l’euristica è ammissibile (e h_max è addirittura consistente, quindi non deve tornare agli stati chiusi).

6. Pianificazione all’indietro

Definizione — pianificazione all’indietro (regressione)

Cerca a partire dall’obiettivo: lo stato della ricerca è un insieme di atomi g che devono ancora essere veri (all’inizio g = G). Un’azione a è rilevante per g se add(a) ∩ g ≠ ∅ e del(a) ∩ g = ∅. La regressione dell’obiettivo attraverso a è

g′ = (g ∖ add(a)) ∪ pre(a)

g′

ciò che deve essere vero prima dell’azione a perché dopo di essa sia vero g — un nuovo sotto-obiettivo, precedente

g

il sotto-obiettivo attuale; gli atomi che l’azione non menziona devono essere veri già prima, perché l’azione da sola non li introduce (e grazie alla condizione di rilevanza nemmeno li distrugge)

add(a)

li sottraiamo, perché a questi atomi provvede l’azione stessa — prima non devono essere veri

pre(a)

li aggiungiamo, perché senza precondizioni l’azione non si può eseguire — diventano nuovi sotto-obiettivi

La ricerca termina quando g′ ⊆ s₀; il piano sono le azioni trovate in ordine inverso.

Esempio — regressione dell’obiettivo dell’anomalia di Sussman

Obiettivo g = {su(A, B), su(B, C)}, inizio s₀ = {su(C, A), tavolo(A), tavolo(B), libero(B), libero(C)}. Prendiamo le azioni a partire dall’ultima:

dal tavolo(A, B): add = {su(A, B)} tocca g, del = {tavolo(A), libero(B)} no → rilevante

   g′ = {su(B, C)} ∪ {tavolo(A), libero(A), libero(B)}

dal tavolo(B, C): add = {su(B, C)}, del = {tavolo(B), libero(C)} → rilevante

   g″ = {tavolo(A), libero(A), libero(B)} ∪ {tavolo(B), libero(B), libero(C)} = {tavolo(A), tavolo(B), libero(A), libero(B), libero(C)}

sul tavolo(C, A): add = {tavolo(C), libero(A)}, del = {su(C, A)} → rilevante

   g‴ = {tavolo(A), tavolo(B), libero(B), libero(C)} ∪ {su(C, A), libero(C)} = {su(C, A), tavolo(A), tavolo(B), libero(B), libero(C)} ⊆ s₀ ✓

Il piano letto al contrario: sul tavolo(C, A), dal tavolo(B, C), dal tavolo(A, B). Se però come ultima azione provassimo dal tavolo(B, C), otterremmo il sotto-obiettivo {su(A, B), tavolo(B), libero(B), libero(C)} — A sta su B e B è allo stesso tempo libero. Uno stato così non esiste, ma la regressione da sola non se ne accorge; i pianificatori all’indietro hanno quindi bisogno di regole aggiuntive che smascherino le combinazioni impossibili.

7. L’anomalia di Sussman

L’idea più semplice per pianificare: dividere l’obiettivo in parti e soddisfarle una dopo l’altra. Funziona spesso — e fallisce già con tre blocchi. Il problema porta il nome di Gerald Sussman, che lo analizzò negli anni Settanta: C sta su A, B è accanto, l’obiettivo è A su B e insieme B su C.

Il piano più corto per «A su B» toglie C e mette A su B. Ma a quel punto B sta sotto A, e portare B su C significa togliere di nuovo A. Alla fine vale solo il secondo obiettivo, e ci sono voluti 4 passi. L’ordine opposto va a finire allo stesso modo: mettiamo B su C, ma così seppelliamo A sotto C e B — e liberarlo distrugge di nuovo il primo obiettivo. Gli obiettivi si ostacolano a vicenda, da qualunque parte cominci.

La soluzione richiede di intercalare i passi dei due obiettivi: prima liberare A (passo per il primo obiettivo), poi B su C (secondo obiettivo), e solo dopo A su B (primo obiettivo). Un pianificatore che cerca nello spazio degli stati completi lo trova da solo — qui ha percorso tutti i 13 stati del mondo a tre blocchi. Un pianificatore che compone piani parziali deve saperli sbrogliare e ricongiungere. È il tema di tutta la famiglia della «pianificazione nello spazio dei piani».

8. Pianificazione gerarchica

Definizione — HTN

In una rete gerarchica di compiti (hierarchical task network, HTN) oltre alle azioni primitive ci sono anche compiti composti. Ogni compito composto ha uno o più metodi — sequenze di sotto-compiti in cui lo si può scomporre. La pianificazione parte da un unico compito di livello più alto e lo scompone finché non restano solo azioni primitive.

def rozloz(ukoly, stav):                   # ukoly: lista dei compiti rimanenti
    if not ukoly:
        return []                            # tutto scomposto
    u, zbytek = ukoly[0], ukoly[1:]
    if u.primitivni:                         # normale azione STRIPS
        if not u.predpoklady <= stav:
            return None
        plan = rozloz(zbytek, proved(stav, u))
        return None if plan is None else [u] + plan
    for metoda in u.metody:                  # prova le ricette una dopo l'altra
        if metoda.podminka <= stav:
            plan = rozloz(metoda.podukoly + zbytek, stav)
            if plan is not None:
                return plan
    return None                              # nessun metodo è riuscito — backtracking

Qui si cerca nello spazio delle scomposizioni, non degli stati: si ramifica solo in base a quale metodo scegliere per un compito composto. I compiti si scompongono nell’ordine in cui verranno eseguiti, così il pianificatore conosce sempre lo stato attuale — allo stesso modo procede per esempio il pianificatore SHOP2.

La pianificazione gerarchica si usa dove gli esperti hanno procedure collaudate: nella logistica, nel controllo della produzione e molto nei videogiochi. Lo sparatutto F.E.A.R. (2005) divenne famoso per i soldati che pianificavano la tattica al volo con un linguaggio in stile STRIPS — e dalla stessa idea partono i pianificatori di molti altri giochi.

9. Pianificare in un mondo incerto

STRIPS presuppone che il mondo sia esattamente come pensiamo e che le azioni vadano esattamente come descritto. Ma un robot vero fa cadere il blocco e un server vero non risponde. Le risposte più comuni sono tre:

• Monitoraggio e ripianificazione. Dopo ogni azione controlla se il mondo è come il piano si aspettava. Se no, pianifica di nuovo da ciò che c’è. Semplice e sorprendentemente efficace (il ciclo è qui sotto).
• I piani condizionali hanno diramazioni: «se la porta si apre, prosegui, altrimenti usa l’altro ingresso».
• Pianificazione probabilistica. Quando un’azione ha più esiti possibili con probabilità date, non cerchiamo una sequenza di azioni ma una strategia per ogni situazione — i processi decisionali di Markov hanno nel programma una parte tutta loro.

def proved_s_dohledem(cil, akce, svet):
    plan = planuj(svet.pozoruj(), cil, akce)
    while plan:
        a = plan.pop(0)
        cekany = proved(svet.pozoruj(), a)   # cosa dovrebbe valere secondo il modello
        svet.udelej(a)
        skutecny = svet.pozoruj()
        if cil <= skutecny:
            return True
        if skutecny != cekany:               # il mondo si è comportato diversamente
            plan = planuj(skutecny, cil, akce)   # ripianifica da ciò che c'è
    return cil <= svet.pozoruj()

Basta poi sorvegliare solo ciò da cui dipende il resto del piano: se cambia un atomo che non è precondizione di nessuna azione successiva né parte dell’obiettivo, il piano resta valido. Questo risparmio lo introdusse già il sistema PLANEX, che eseguiva i piani di Shakey (Fikes, Hart e Nilsson, 1972).

10. La pianificazione negli agenti IA

Anche un agente linguistico che corregge un bug nel codice pianifica: scompone il compito in un elenco di passi, dopo ogni passo guarda il risultato (i test sono passati? il file esiste?) e di conseguenza aggiusta il piano. È monitoraggio e ripianificazione, solo che le azioni sono comandi nel terminale e precondizioni ed effetti non sono scritti formalmente da nessuna parte — il modello li stima dal testo.

Proprio qui sta il punto debole. Le ricerche su problemi del mondo dei blocchi (per esempio la raccolta PlanBench) hanno mostrato che i modelli linguistici nella pianificazione classica sbagliano spesso, soprattutto quando i blocchi vengono rinominati con parole senza senso, così che il modello non può attingere a esempi imparati. I modelli più recenti con un ragionamento più lungo se la cavano molto meglio, ma non danno garanzie di correttezza. Si rivela quindi utile una divisione del lavoro: il modello traduce il problema in PDDL o propone un piano e un pianificatore o un validatore classico lo verifica — ognuno fa ciò che sa fare.

11. Riepilogo

• Pianificare è cercare una sequenza di azioni verso un obiettivo; STRIPS descrive lo stato come un insieme di atomi e l’azione con precondizioni, atomi aggiunti e atomi rimossi.
• La pianificazione in avanti è una ricerca negli stati; quella all’indietro fa regredire l’obiettivo attraverso le azioni rilevanti.
• Il pianificatore calcola da solo l’euristica dal problema rilassato senza rimozioni: h_max è ammissibile, h_add più veloce, ma può portare a un piano più lungo.
• L’anomalia di Sussman mostra che i sotto-obiettivi non si possono sempre soddisfare uno dopo l’altro — i passi vanno intercalati.
• La pianificazione gerarchica scompone i compiti secondo metodi collaudati; in un mondo incerto il piano si monitora e si ripianifica — esattamente ciò che fanno gli agenti IA di oggi.

Vuoi provarlo con mano? Fai scrivere a un agente IA il mondo dei blocchi in PDDL e fagli lanciare il pianificatore liberamente disponibile Fast Downward — e poi prova quanti blocchi riesce a gestire il modello da solo, senza di esso.

La vedi diversamente? Scrivi a support@coden-app.com.