Cenni di pianificazione automatica Sistemi distribuiti LS Prof. Andrea Omicini A.A. 2003-2004 1 Il problema della pianificazione Gli agenti sono forniti di un goal uno o più Il goal è tipicamente espresso da un insieme di stati del mondo desiderabili es., tutti quegli stati in cui il mio libretto contiene un voto superiore a 29 in tutti gli esami del piano di studio Per raggiungerlo, l’agente ha a disposizione le risorse fornite dall’ambiente le sue capacità di azione gli altri agenti 2 La pianificazione automatica Dato uno stato del mondo in cui l’agente vive Dato l’insieme delle azioni ammissibili da parte dell’agente Dato un obbiettivo da raggiungere il goal dell’agente La pianificazione consiste nel determinare un piano ok, grazie mille :) Un piano è un insieme ordinato (totalmente o parzialmente) di azioni volto a raggiungere il goal 3 Che differenza c’è… … tra i problemi di ricerca visti prima e la pianificazione automatica? concettualmente, nessuna: ma le soluzioni viste per la ricerca non sono sufficienti per la gran parte dei problemi di pianificazione … tra la pianificazione automatica e la sintesi di algoritmi? sono ambiti storicamente diversi: ma la differenza è innanzitutto nel concetto di piano, più ampio di quello di algoritmo … tra assegnare a un agente un goal o un task? lo vediamo qui: la pianificazione è un task, il goal è il fine del task 4 Quanto serve la pianificazione? Un agente può evitare di pianificare le sue azioni? solo se è un agente particolarmente elementare e poco intelligente ma se l’attività deliberativa deve avere un senso, un orientamento, allora deve comprendere la pianificazione Quindi, un blocco di pianificazione sarà sempre presente nei nostri agenti che genere, dipenderà dall’ambito applicativo, dal goal assegnato e dalle caratteristiche designate dell’agente 5 Esempio di pianificazione Goal: andare a Cesena a fare lezione Stato: sono a casa mia e ho sonno Piano: 1. 2. 3. 4. 5. 6. 7. prendo il portatile prendo le chiavi dell’automobile esco di casa prendo l’automobile arrivo in Facoltà entro in aula ecc. 6 Osservazioni (1) “Ho sonno” è una parte irrilevante della rappresentazione del mondo? visto il piano, decisamente sì a meno che non sia pericoloso: “prendo un caffé” potrebbe essere una azione contemplata oppure potrei escludere l’automobile come risorsa in caso di sonno Posso scambiare l’azione 1 con la 2 ordinamento totale qui non serve, basta parziale 7 Osservazioni (2) Esiste un piano alternativo 1. 2. 3. 4. 5. prendo il portatile prendo i biglietti di autobus e treno esco di casa raggiungo la fermata dell’autobus ecc. Il piano alternativo potrebbe diventare l’unico quando la risorsa “automobile” non fosse disponibile o viceversa, nel caso di sciopero dei mezzi 8 Definizione Un pianificatore automatico è un (componente di un) agente intelligente che opera in un dato dominio applicativo e che, date: una rappresentazione dello stato iniziale una rappresentazione del goal una descrizione formale delle azioni eseguibili sintetizza dinamicamente il piano di azioni necessario a raggiungere il goal 9 Rappresentazione dello stato (1) Primo problema: rappresentazione dell’ambiente fornire al pianificatore il modello dell’ambiente in cui opera Tipico approccio forma dichiarativa congiunzione di formule atomiche tutte le “asserzioni” vere nel mondo Secondo problema: quale formalismo? più è ricco meglio rappresento (più “conoscenza”) più è povero meglio computo (più efficienza) 10 Rappresentazione dello stato (2) Terzo problema: l’ambiente è spesso osservabile in modo solo parziale, e non esatto perché alcuni aspetti non sono osservabili inerentemente perché alcuni aspetti possono sfuggire alla capacità percettiva dell’agente perché il dominio è troppo vasto per essere rappresentato completamente perché le percezioni sono soggette a rumore, e i sensori a errori o fallimenti perché il dominio può essere troppo dinamico per mantenere costantemente la consistenza della rappresentazione 11 Rappresentazione dello stato: esempio isbn(booktitle,1234) price(36.00,1234) available(amazon,1234) Rappresentazione parziale che ne è di ciò che non è asserito? è falso o non so? Ovviamente, lo stato iniziale è rappresentato così 12 Rappresentazione del goal Stessa rappresentazione usata per lo stato del mondo perché il goal è uno o più stati del mondo desiderabili Il formalismo tipicamente include una nozione di entailment o inclusione per cui so quando un certo stato del mondo soddisfa il goal lo include o lo implica 13 Rappresentazione delle azioni Si definiscono di solito classi (o schemi) di azioni con variabili istanziabili diversamente, a denotare molteplicità di azioni Forma dichiarativa Denotata da un nome Corredata da precondizioni condizioni per l’eseguibilità postcondizioni (effetti) effetti dell’azione sul mondo Cosa ricordano? FP e RE in FIPA ACL – perché?? 14 Esempio: mondo dei blocchi stack(X,Y) FP: holding(X) EE: handempty clear(Y) clear(X) on(X,Y) unstack(X,Y) FP: handempty EE: holding(X) clear(X) clear(Y) on(X,Y) Nota: esempio di azioni simmetriche possono essere usate per backtracking fisico ma non sempre è possibile 15 Altri aspetti rilevanti Correttezza e completezza se un piano esiste, il pianificatore lo trova completezza se il piano viene generato, effettivamente conduce al goal correttezza De-componibilità del problema può essere separato in sottoproblemi così che il piano sia costruibile come sequenza di sottopiani? non ci deve essere interazione tra i sottoproblemi Reversibilità delle scelte e delle azioni posso tornare indietro? 16 Pianificazione e esecuzione Reversibilità la pianificazione è tipicamente reversibile, l’esecuzione no Determinismo la pianificazione vede il mondo come deterministico, l’esecuzione affronta invece un mondo non deterministico In effetti, c’è uno iato tra pianificazione e esecuzione che genera molti approcci alla pianificazione 17 Cosa vediamo? Cenni di Pianificazione classica pianificazione deduttiva pianificazione con ricerca pianificazione gerarchica Pianificazione condizionale Pianificazione reattiva Poi vediamo che succede nel distribuito pianificazione multi-agente ancora per cenni… 18 Pianificazione classica Pianificazione off-line prima si produce l’intero piano, lavorando su una snapshot del mondo, poi si esegue assunzioni tempo di esecuzione delle azioni atomico determinismo degli effetti stato iniziale noto a priori esecuzione del piano come unica causa di cambiamento del mondo 19 Pianificazione reattiva Pianificazione on-line la produzione del piano è continuamente alternata all’esecuzione e alla percezione del mondo reagendo ai cambiamenti di stato il mondo è osservato sia prima sia durante la pianificazione, sia durante l’esecuzione assunzioni forse, solo il tempo atomico delle azioni 20 Pianificazione deduttiva Logica per rappresentare stati, goal e azioni Piano generato come dimostrazione di un teorema Prolog possibile strumento per noi Esempio classico: Situation Calculus (anni ’60) l’abbiamo già introdotto esempio: on(b,a,t0) ontable(a,t0) ontable(c,t0) le azioni definiscono quali fluenti saranno veri dopo l’esecuzione di un’azione costruzione di un piano come dimostrazione di goal Vantaggi: molto espressivo Problema: frame problem 21 Frame Problem Occorre specificare esplicitamente tutti i fluenti che sono veri per effetto delle azioni sia quelli che cambiano sia quelli che non cambiano Al crescere della complessità del problema, il numero degli assiomi che è necessario specificare per questo cresce a dismisura frame axioms il problema della rappresentazione della conoscenza divene praticamente intrattabile 22 Esempio: formulazione di Kowalski holds(rel,a) / holds(rel,s) indica che rel è vera nello stato s o dopo l’azione a modo di esprimere le postcondizioni poss(s) lo stato s è raggiungibile / possibile pact(a,s) nello stato s l’azione a è lecita modo di esprimere le precondizioni Meta-assioma poss(S) pact(U,S) poss(do(U,S)) 23 Esempio in Prolog (1) Stato iniziale poss(s0). holds(on(a,d),s0). holds(on(b,e),s0). holds(on(c,f),s0). holds(clear(a),s0). holds(clear(b),s0). holds(clear(c),s0). holds(clear(g),s0). 24 Esempio in Prolog (2) Azione move(X,Y,Z) EE holds(clear(Y),do(move(X,Y,Z),S)). holds(on(X,Z),do(move(X,Y,Z),S)). FP pact(move(X,Y,Z),S) :holds(clear(X),S), holds(clear(Z),S), holds(on(X,Y),S), X \= Z. Frame axiom holds(V,do(move(X,Y,Z),S)) :holds(V,S), V \= clear(Z), V \= on(X,Y). Goal ?- poss(S), holds(on(a,b),S), holds(on(b,g),S). S = do(move(a,d,b), do(move(b,e,g), s0)) 25 Pianificazione con ricerca Pianificazione non deduttiva linguaggi specialzzati per stati, goal e azioni generazione del piano come problema di ricerca che come al solito è un albero (o grafo) Tipi di ricerca nello spazio degli stati ogni nodo rappresenta uno stato e ogni arco rappresenta un’azione nello spazio dei piani ogni nodo rappresenta un piano parziale e ogni arco un raffinamento del piano 26 STRIPS Antenato degli attuali sistemi di pianificazione anni ’70 STanford Research Institute Problem Solver Linguaggio per la rappresentazione delle azioni molto più semplice del situation calculus meno espressivo, più efficiente tipo Datalog – senza funtori algoritmo per la costruzione di piani fluenti di stato nello stato, ground nel goal, con variabili 27 Azioni in STRIPS Precondizioni fluenti che devno essere veri per applicare l’azione Delete list fluenti che diventano falsi come risultato dell’azione da eliminare dallo stato Add list fluenti che diventano veri come risultato dell’azione da aggiungere allo stato Effect list sussume Add e Delete list con atomi positivi e negativi 28 Frame problem in STRIPS STRIPS assumption tutto ciò che non è specificato nella Add e Delete list (o nella Effect list) rimane immutato Ciò ovviamente risolve il frame problem 29 Pianificazione lineare Ricerca nello spazio degli stati con strategie classiche forward dallo stato iniziale al goal backward dal goal allo stato iniziale Goal regression Non c’è tempo d dire di più se non che STRIPS è basato su ricerca backward l’algoritmo è semplice Assunzione: Close World Assumption tutto ciò che non è dichiarato è falso lo stato iniziale è completamente noto 30 Pianificazione non lineare Ricerca fatta nello spazi dei piani non degli stati: non più piano generato come successione lineare ordinata totalmente di azioni Principio: Least commitment sugli ordinamenti mai imporre più vincoli del necessario sull’ordine delle azioni ciò evita molti backtracking Albero di ricerca ogni nodo un piano parziale ogni arco un suo raffinamento Sempre CWA 31 Piano non lineare Insieme di azioni istanze di operatori Start & Stop nel piano vuoto Insieme di vincoli di ordinamento tra le varie azioni non completo A≺B Start ≺ Stop Insieme di “causal link” A →p B A ottiene p per B: un suo effetto è precondizione per B, quindi p deve rimanere vera tra l’esecuzione di A e B 32 Algoritmo di POP Partial Order Planning: algoritmo intuitivo while <piano non terminato> seleziona azione N del piano corrente con pre-condizione C non soddisfatta seleziona azione S che abbia C tra i suoi effetti attesi aggiungi al piano S ≺ N (vincolo d’ordine) se S non appartiene al piano corrente Start ≺ S ≺ Stop (vincolo d’ordine) S→C N (causal link) risolvi eventuali conflitti su causal link 33 Minacce (threat) POP alterna passi di soddisfacimento precondizioni a passi di risoluzione di conflitti Esempio di conflitto su causal link (minaccia) A3 minaccia A1→C A2 se ¬C è un effetto di A3 nessun vincolo di ordinamento forza A3 prima di A1 o dopo A2 Possibili soluzioni demotion: impongo A3 ≺ A1 promotion: impongo A2 ≺ A3 Promotion e demotion non bastano per pianificatore completo 34 Modal Truth Criterion MTC 5 metodi di raffinamento del piano: establishment soddisfacimento di precondizioni con nuova azione, o vincolo di ordinamento nuovo, o assegnamento di variabili promotion, demotion scopertura inserire A2 (white knight) tra A1 e A3 se A1 minaccia la precondizione C di A3, con C effetto di A2 separazione porre vincoli di non codesignazione tra variabili (tipo X \= Y) per evitare una unificazione che minacci un causal link Così un POP è completo 35 Soluzione Il piano è consistente quando non ci sono cicli nell’ordinamento non ci sono conflitti su causal link Il piano è una soluzione (non è più un piano parziale) quando il piano è consistente non ci sono precondizioni insoddisfatte 36 Linearizzazione Dato un piano parzialmente ordinato PA, una sua linearizzazione è un totally ordered plan che contiene tutte le azioni di PA soddisfa tutti i vincoli di PA Ogni PO plan genera una molteplicità di TO plan Un esecutore sequenziale richiederà una linearizzazione prima dell’esecuzione ulteriori condizioni “esterne” potrebbero rendere preferibile una linearizzazione a un’altra 37 Pianificazione gerarchica Pianificazione complessa meglio trattata a diversi livelli di astrazione Idea a un livello un’operazione è atomica, a quello più sotto è un piano da costruire forse è anche nostra esperienza comune Linguaggio Ancora tutto fatto a precondizioni ed effetti Macro operatori parte da generare, parte pre-compilati 38 Algoritmi gerarchici Più diffusi STRIPS-like POP In generale: pianifica a meta-livello azioni come macro-operatori espande macro-operatori come goal da raggiungere pianificando a livello inferiore o espandendo piani già pre-compilati Nota: i piani precompilati introducono la conoscenza pregressa su di un dominio 39 Condizioni sul planning gerarchico (1) Vincoli sulla decomposizione se la macroazione A ha effetto X ed espansa con piano P X deve essere effetto di almeno una delle azioni di P X deve essere protetto fino alla fine di P ogni precondizione delle azioni di P deve essere garantita o da P stesso o essere precondizione di A le azioni di P non devono violare vincoli causali quando A viene sostituito da P A questo punto, il planner gerarchico può sostituire A con P 40 Condizioni sul planning gerarchico (2) Sostituzione di A con P si devono sistemare sia le relazioni d’ordine sia i link causali se first(P) è la prima azione di P, sostituisco ogni B ≺ A con B ≺ first(P) se last(P) è l’ultima azione di P, sostituisco ogni A ≺ B con last(P) ≺B e similmente per i link causali 41 Pianificazione e scheduling La pianificazione aziendale esiste ma non è esattamente quello che abbiamo visto fino a qua es. pianificazione della produzione la produzione di un pezzo richiede tempo richiede risorse (umane e materiali) deve precedere alcune attività e seguirne altre può procedere concorrentemente a altre attività Per certi versi, sembra POP per altri no tempo delle azioni risorse condivise / limitate 42 Job Shop Scheduling Dati un insieme di job ove un job è una sequenza di azioni e le azioni hanno durata data e richiedono risorse di qualche tipo Il problema è determinare uno schedule ossia una distribuzione temporale dei job in modo da minimizzare il tempo totale per completare tutti i job rispettando i vincoli sulle risorse 43 Esempio: assemblaggio auto Semplificato si parte dalla carrozzeria, si montano motore e ruote, e si ispeziona Vincoli motore prima delle ruote ispezione alla fine Si fa con POP come diventa uno scheduling problem? Aggiungo una durata a ogni azione E stabilisco quando ogni azione deve cominciare e finire 44 Da planning a scheduling Ogni cammino da Start a Stop nel POP è un piano linearizzazione Aggiungendo una durata alle azioni posso stabilire il cammino critico ossia quello che dura di più Perché è critico? perchè determina la durata totale dell’intero piano assumendo che non ci siano ritardi nell’esecuzione delle azioni in successione in ogni cammino Ciò determina automaticamente inizio e fine delle azioni del cammino critico finestre di inizio e fine delle azioni negli altri cammini Critical Path Method 45 Schedule Finestre di esecuzione tempo minimo di inizio (ES) tempo massimo di inizio (LS) Supponendo che la durata sia deterministica assegnata durata, ES e LS a ogni azione del piano definisce uno schedule Nota: le azioni “prendono corpo” non sono più atomiche Nota: questo approccio (implicitamente) è prima plan poi schedule tipico in manufacturing e logistica, scheduling “umano” quando ci sono vincoli severi sulle risorse, a volte è meglio integrare i due processi 46 I problemi dell’esecuzione Ipotesi fin qui pianificazione off-line piano affidato a un esecutore Possibili problemi di questo approccio esecuzione effettiva in condizioni diverse da quelle previste a tempo di esecuzione l’ambiente non cambia solo per effetto delle azioni dell’agente conoscenza incompleta o non corretta effetti delle azioni inattesi azioni non deterministiche errori d’esecuzione 47 Possibile approccio Percepire i problemi discrepanze, errori a tempo d’esecuzione alternando esecuzione e percezione / monitoring Rimediare ai problemi utilizzando un’azione correttiva utilizzando un piano alternativo ripianificando totalmente o parzialmente 48 Open World Assumption L’informazione non presente è non nota non falsa L’informazione non presente va raccolta quando necessario se possibile Idea azioni di sensing come azioni del piano pre-condizioni: abilitazione all’osservazione post-condizioni: informazione osservata nota 49 Pianificazione condizionale Idea prendiamo in considerazione le fonti di incertezza off-line durante la pianificazione inseriamo azioni di sensing nel piano generiamo piani alternativi per ogni fonte di incertezza del piano in fase di esecuzione, le azioni di sensing stabiliscono quale tra le varie alternative sarà il piano effettivamente eseguito 50 Possibili problemi Esplosione combinatoria dei possibili piani dovuta alla presenza di grande numero di elementi di conoscenza critica incerta Non sempre è possibile valutare a priori tutti i possibili contesti alternativi Approccio probabilistico si assegnano valori di probabilità alle varie possibilità si pianifica solo per gli scenari più probabili 51 Pianificazione reattiva Pianificazione on-line Idea base interazione continua con l’ambiente per affrontare dinamicità e non determinismo dell’ambiente Fasi in fase di pianificazione si acquisisce tutta l’informazione disponibile senza ipotesi CWA in fase di esecuzione si monitorano le azioni e i loro effetti pianificazione e esecuzione alternati con continuità reagendo così ai cambiamenti di stato 52 Sistemi reattivi puri Reagiscono direttamente allo stimolo esterno azione pre-definita entro una KB selezionata implicitamente in risposta allo stato del mondo una azione alla volta Vantaggi sistemi fortemente interattivi robusti, dinamici non necessitano di modello del mondo Svantaggi nessuna capacità di deliberazione autonoma problema in ambienti che richiedono intelligenza Problema: il termostato è un pianificatore? 53 Pianificatori ibridi Idea integrare approccio generativo e approccio reattivo per avere vantaggi di entrambi Cosa fa un pianificatore ibrido? genera un piano per raggiungere il goal eseguita un’azione ne verifica gli effetti e le precondizioni della successiva integrando esecuzione e percezione corregge i piani / ripianifica in caso di discrepanze / errori Attività di ricerca DEIS-Bologna PlanNet, vincoli / sensing per la pianificazione 54 Action vs. Plan Monitoring Action monitoring l’agente controlla le pre-condizioni di ogni azione prima di eseguirla se qualcosa non va, cerca di trovare un punto del piano da cui ricominciare pianificando eventualmente come arrivare fin lì e poi ricomincia Plan monitoring controlla le pre-condizioni di tutto il piano a quel punto vantaggi può capire un fallimento molto prima, e rimediare può approfittare della serendipità, ossia del successo accidentale 55 Spazio per il learning… Ovviamente, un agente può potenzialmente imparare da successi e (soprattutto) fallimenti Pre-requisiti rappresentazione esplicita del piano accessibile all’agente “storico” dei piani e della rappresentazione del mondo interaction history + plan state qualche algoritmo di learning Ancora ovviamente, questo rende ammissibile / potenzialmente utile integrare esplorazione e pianificazione un agente può tentare piani di azioni che non lo portano al goal, ma migliorano la sua capacità di pianificare 56 Pianificazione continua (1) Un agente potrebbe persistere indefinitamente nell’ambiente molte applicazioni contemporanee richiedono sistemi online permanenti Che senso ha separare esecuzione e pianificazione? l’agente sta perennemente agendo e deliberando agente a pianificazione continua Il goal potrebbe essere fissato e persistente nel tempo oppure l’agente potrebbe essere in grado di formulare il suo goal alla finalizzazione di ogni sua attività 57 Pianificazione continua (2) L’agente ha un goal il cui soddisfacimento viene costantemente perseguito e verificato è dotato di piano corrente che viene costantemente monitorato e riformulato / rimosso in caso di precondizioni non soddisfatte causal link minacciato azione ridondante o di cambio del goal aggiunta di goal, o rimozione di goal non più utili 58 Pianificazione multiagente Cosa succede quando l’ambiente è multiagente? possiamo modellare gli altri agenti come parte dell’ambiente e quindi usare le tecniche di pianificazione singolo agente magari usando gli approcci integrati ma il mondo è indifferente alle intenzioni di un agente gli altri agenti magari no quindi, difficile che l’approccio sia efficace… Multiagent planning tratta il problema 59 Nota generale Multiagente ≠ distribuito in linea di principio, sono due proprietà dei sistemi indipendenti quindi, perché in questo corso di DAI ci spostiamo sempre sul MAS e magari poi non diciamo altro? Agenti incapsulano il controllo ogni agente è un flusso di controllo indipendente ed è situato quindi l’astrazione agente (MAS) ci consente di astrarre dalla distribuzione logica & fisica in linea di principio 60 Premesse MAS cooperativi o competitivi o misti… La costruzione del piano da parte dell’agente è sempre rilevante ma non garantisce il successo Sono necessari meccanismi di coordinazione soggettiva e oggettiva tipicamente supportate da qualche forma di comunicazione ma non necessariamente 61 Planning cooperativo Idea agenti diversi condividono un goal joint goal si considerano le azioni di tutti i diversi agenti come azioni ammissibili, denotate dal nome dell’agente si costruisce un piano joint plan basato su tutte le azioni disponibili Coordinazione per generare il piano eseguirlo es: varie linearizzazioni di un POP 62 Multibody planning Chi genera il joint plan? se lo affidiamo a un agente pianificatore “terzo”, multibody planning in vero ambiente MAS, gli agenti accettano il piano altrimenti, autonomia? Esecuzione diversa da single agent ci possono essere joint action visto che sicuramente gli esecutori sono più d’uno e possono in linea principio agire contemporaneamente pianificatori + lista delle azioni concorrenti “positiva” o “negativa” 63 Workflow Qual è la differenza con il workflow? c’è un piano, codificato, che gli agenti più o meno liberamente s’impegnano a eseguire eseguendone le azioni elementari nei tempi richiesti In linea di principio, il multiaent planning può condurre a costruire (semi)automaticamente un workflow da usare con WfMS off-the-shelf magari modificabili dinamicamente a cura di agenti intelligenti 64 Leggi sociali Un piano condiviso è una semplice forma di social law generata ad hoc, dinamicamente Altre leggi e regole potrebbero essere meno “volatili” caratterizzare società di agenti, o sistemi, tecnologie, … le Tre Leggi della Robotica di Asimov Qua il planning multiagente sfocia completamente nella coordinazione già visto nel seminario Per saperne di più da Durfee in avanti: PGP, GPGP/TAEMS,… 65 Problemi aperti correlati Come scambiarsi i goal tra agenti fidarsi, non fidarsi mutual committment Come rappresentare piani, regole e leggi in modo che siano costruibili efficiemente attuabili efficientemente magari con la loro stessa rappresentazione condivisibili interiorizzabili modificabili dinamicamente 66