M10. Planning for Intelligent Agents
Slide: <file:///C:/UNI/Magistrale/ISE/M10 – Planning for Intelligent Agents.pdf>
Indice
Problema del Planning
Definizione
Il planning automatico e la sintesi dinamica di un piano di azioni che porta un agente da uno stato iniziale a un goal.
Un agente razionale ha un obiettivo, un repertorio di azioni, eventualmente altri agenti con cui cooperare e risorse nell’ambiente. Pianificare significa decidere una sequenza, o un ordinamento parziale, di azioni orientate al goal.
Esempio: goal: arrivare a Cesena e incontrare la classe. Stato iniziale: sono a casa, sono assonnato. Piano possibile: prendere laptop, chiavi, uscire, guidare, trovare l’aula. Se la sonnolenza rende pericoloso guidare, serve un’azione aggiuntiva come prendere caffe o un piano alternativo con bus e treno.
Note
Avere un piano dipende dall’intelligenza; eseguirlo in un ambiente reale dipende dall’autonomia e dalla capacita di reagire a imprevisti.
Il planning e una forma di search, ma non una search qualunque: l’ambiente puo cambiare mentre sto cercando, le azioni possono interferire e in sistemi cyber-physical possono esserci concorrenza, tempo e risorse.
Rappresentare Mondo, Goal e Azioni
Definizione
Un automatic planner riceve una rappresentazione dello stato iniziale, del goal e delle azioni disponibili, poi sintetizza un piano per raggiungere il goal.
La rappresentazione del mondo e spesso dichiarativa: una congiunzione di formule che descrive cio che e noto. Il formalismo scelto deve bilanciare espressivita ed efficienza.
Il goal e rappresentato come stato desiderato del mondo. In modo semplice potrei verificare E >= G come inclusione insiemistica; in modo piu espressivo verifico E |= G, cioe entailment logico.
Definizione
Un’azione e descritta da precondizioni di fattibilita e postcondizioni, cioe effetti attesi sul mondo.
Nel Blocks World:
stack(X,Y)richiedeholding(X)eclear(Y).- Produce
handempty,clear(X)eon(X,Y). unstack(X,Y)fa l’operazione inversa, se la mano e vuota eXe libero.
Osservabilita Parziale
L’agente puo non conoscere tutto: percezione rumorosa, dominio vasto, ambiente troppo rapido o limiti sensoriali rendono incompleta la rappresentazione.
Offline e Online Planning
Definizione
Nell’offline planning, il piano viene prodotto completamente prima dell’esecuzione, rispetto a uno snapshot iniziale del mondo.
Offline planning funziona bene quando l’ambiente e stabile e noto. Se pero il mondo cambia durante l’esecuzione, il piano puo diventare obsoleto.
Definizione
Nell’online planning, pianificazione, sensing ed esecuzione si alternano continuamente, anche con informazione parziale.
Esempio: un robot in un edificio sconosciuto non puo pianificare tutto prima. Avanza, percepisce, aggiorna la mappa, ricalcola e continua.
Note
Il planning diventa particolarmente utile quando servono osservabilita, accountability ed explainability: sapere prima perche un sistema fara certe azioni e spesso necessario nei sistemi socio-tecnici.
Classical Planning
Definizione
Il classical planning assume tempo atomico, effetti deterministici, conoscenza iniziale completa e assenza di cambiamenti non causati dall’agente.
In altre parole, l’ambiente e:
- pienamente osservabile;
- deterministico;
- finito;
- statico, salvo le azioni dell’agente;
- discreto in tempo, azioni, oggetti ed effetti.
Sono assunzioni forti, ma permettono di studiare algoritmi e rappresentazioni in modo pulito.
Un approccio classico e il deductive planning, dove logica rappresenta stati, azioni e goal, e il piano emerge come prova. Nel situation calculus, una situazione e uno snapshot del mondo, i fluents sono proprieta che possono cambiare, e le azioni producono nuove situazioni.
Frame Problem
Se rappresento tutto in logica, ogni azione deve dire anche cosa non cambia. In domini realistici questo diventa ingestibile.
STRIPS e State-Based Planning
Definizione
STRIPS rappresenta stati come insiemi di letterali positivi, goal come congiunzioni di letterali e operatori tramite precondizioni, add-list e delete-list.
STRIPS usa una closed-world assumption: cio che non e esplicitamente rappresentato nello stato e considerato falso. Gli effetti si calcolano con operazioni insiemistiche:
Si+1 = Si \ DEL(o) union ADD(o) se PRE(o) e incluso in Si.
Esempio Blocks World:
- Stato iniziale:
{ontable(A), clear(A), ontable(C), on(B,C), clear(B)}. - Goal:
{on(A,B), on(B,C)}. - Azione
put(A,B)applicabile percheontable(A),clear(A)eclear(B)valgono. - Dopo l’azione,
ontable(A)eclear(B)vengono rimossi,on(A,B)viene aggiunto.
Note
STRIPS riduce il frame problem trattando la persistenza come default: cio che non viene cancellato resta valido.
Il planning diventa ricerca di una sequenza di operatori che trasforma lo stato iniziale in uno stato che soddisfa il goal. Il costo e la crescita esponenziale dello spazio degli stati.
Progression, Regression e Non Linear Planning
Definizione
Il progression planning cerca in avanti dallo stato iniziale; il regression planning cerca all’indietro dal goal verso lo stato iniziale.
In progression applico azioni possibili e genero stati successori fino al goal. In regression parto dal goal e cerco quali azioni avrebbero potuto produrlo, riducendo il goal a sotto-goal precedenti.
Il linear planning risolve un goal alla volta usando uno stack. E efficiente quando i goal sono indipendenti, ma puo fallire quando interagiscono.
Esempio UPS World
Se ho un solo aereo con carburante per un viaggio e due pacchi da portare, risolvere prima un pacco e poi l’altro puo fallire: dopo il primo volo non ho carburante per tornare. Serve caricare entrambi prima di volare.
Definizione
Il non-linear planning rappresenta il piano come ordinamento parziale di azioni, evitando impegni prematuri sull’ordine dei sotto-goal.
Questo permette interleaving: carico pacco 1, carico pacco 2, volo, scarico entrambi. La ricerca e piu grande, ma puo essere sound, complete e talvolta ottimale rispetto alla lunghezza del piano.
Oltre il Planning Classico
Definizione
Il planning moderno estende il modello classico per gestire tempo, risorse, incertezza, concorrenza e benchmark standardizzati.
Le slide introducono direzioni come Graphplan, planning con tempo e risorse, planning sotto incertezza, PDDL e competizioni. Anche senza entrare nei dettagli completi, l’idea e chiara: i domini reali raramente rispettano tutte le assunzioni classiche.
In pratica:
- Graphplan compatta la ricerca costruendo un planning graph con livelli di azioni e proposizioni.
- Planning con tempo e risorse considera durata, deadline, consumo e disponibilita.
- Planning sotto incertezza ammette effetti non deterministici e osservazioni parziali.
- PDDL serve a descrivere domini e problemi in modo standard per confrontare planner.
Trade-off
Piu il modello e realistico, piu cresce il costo computazionale. L’engineering consiste nel scegliere il livello di espressivita utile senza rendere il planning impraticabile.
Prossimi Argomenti
Il modulo chiude il percorso teorico sul planning. Per applicare questi concetti conviene collegarlo a:
- Lab STRIPS - implementazione pratica di planning simbolico con stati, azioni e goal.
- Prolog Fast Track - basi operative su regole, unificazione e backtracking.
- Automated Reasoning - prerequisiti sul ragionamento automatico usato dai planner.