Intelligenza Artificiale 1 Gestione della conoscenza lezione 3 Prof. M.T. PAZIENZA a.a. 2000-2001 Agente risolutore di problemi (basato su obiettivi) Definire come un agente possa decidere cosa fare considerando sistematicamente il risultato di varie sequenze di azioni che potrebbero essere attivate Individuazione della sequenza di azioni che conducono a stati desiderabili. Agente risolutore di problemi (basato su obiettivi) Gli obiettivi aiutano l’agente ad organizzare il comportamento limitando gli scopi che l’agente sta cercando di raggiungere. Un obiettivo è l’ insieme degli stati del mondo in cui è soddisfatto l’obiettivo stesso. Le azioni sono causa di transizioni tra stati del mondo. L’agente deve scegliere una sequenza di azioni (tra tutte quelle possibili) che lo conduce ad uno stato obiettivo. Agente risolutore di problemi (basato su obiettivi) Formulazione dell’obiettivo (basata sulla situazione attuale) Formulazione del problema (processo di decisione di quali azioni e stati della risoluzione del problema considerare, susseguentemente alla formulazione dell’obiettivo) Agente risolutore di problemi (basato su obiettivi) Ove esistono più alternative (sequenze di azioni che raggiungono l’obiettivo), l’agente Se non conosce lo stato risultante dopo aver compiuto ciascuna azione, né altre informazioni addizionali, potrà solo scegliere a caso Se possiede informazioni sugli stati nei quali potrebbe portarsi e sulle azioni che potrebbe compiere, userà queste informazioni per scegliere la sequenza di azioni da intraprendere. Ricerca Ricerca è il processo per l’individuazione / scelta della migliore sequenza di azioni che conducono a stati di esito conosciuto effettuata da parte di un agente che abbia diverse opzioni immediate di esito sconosciuto La soluzione di un problema proposta da un algoritmo di ricerca è quella sequenza di azioni individuata a fronte di un particolare input L’esecuzione coincide con la realizzazione delle azioni suggerite dalla soluzione Agente risolutore di problemi (basato su obiettivi) Formulato un obiettivo ed un problema da risolvere, l’agente attiva una procedura di ricerca per risolverlo, quindi usa la soluzione per guidare le proprie azioni Eseguita la soluzione, l’agente individuerà un nuovo obiettivo Agente risolutore di problemi Soluzione di problema offline; una soluzione di problema online richiede l’agire senza una completa conoscenza del problema e della soluzione Processo di formulazione di problemi Conoscenza che l’agente ha sulle sue azioni e sugli stati Ciò dipende da come l’agente è connesso al suo ambiente, attraverso le percezioni e le azioni. Quindi elementi fondamentali nella definizione di un problema sono gli stati e le azioni Formulazione di problemi Spazio degli stati del problema ( insieme di tutti gli stati raggiungibili dallo stato iniziale attraverso qualsiasi sequenza di azioni) (operatore / funzione successore S) Un cammino nello spazio degli stati è una qualsiasi sequenza di azioni che conduce da uno stato ad un altro (costo di cammino g) Il test obiettivo è applicato dall’agente alla descrizione di un singolo stato per determinare se è in uno stato obiettivo. Formulazione di problemi L’output di un algoritmo di ricerca è una soluzione, ovvero un cammino dallo stato iniziale allo stato che soddisfa il test obiettivo Tipi di problemi • Problemi a stato singolo (deterministico, accessibile) • Problemi a stati multipli (deterministico, inaccessibile) • Problemi di contingenza (nondeterministico, inaccessibile) • Problemi di esplorazione (spazio degli stati sconosciuto) Problemi a stato singolo Caso più semplice Agente riceve dai sensori informazioni sufficienti sullo stato in cui si trova (mondo accessibile) e Conosce esattamente le conseguenze di ciascuna azione Quindi l’agente può calcolare esattamente in quale stato sarà dopo qualsiasi sequenza di azioni Formulazione di problemi a stato singolo Un tale problema è definito da 4 caratteristiche: 1. 2. 3. 4. Stato iniziale Operatore / funzione successore S(x) Test obiettivo Funzione costo cammino Una soluzione è una sequenza di operatori che conducono dallo stato iniziale ad uno stato obiettivo Problemi a stati multipli L’agente conosce tutti gli effetti delle sue azioni, ma Ha un accesso limitato allo stato del mondo (per esempio può non avere sensori – sa solo che il suo stato iniziale appartiene all’insieme degli stati) L’agente deve ragionare su insiemi di stati in cui potrebbe giungere invece che su stati singoli, in quanto il mondo non è completamente accessibile Formulazione di problemi a stati multipli Un tale problema è definito da 4 caratteristiche: 1. Insieme di stati iniziali 2. Insieme di operatori / funzione successore S(x) (per ciascuna azione viene specificato l’insieme di stati raggiunti da qualsiasi stato considerato. Un cammino collega insiemi di stati) 3. Test obiettivo 4. Funzione costo cammino Una soluzione è un cammino che conduce ad un insieme di stati che sono tutti stati obiettivo. Spazio dell’insieme di stati Problemi di contingenza pianificazione Talvolta l’ignoranza impedisce all’agente di trovare una sequenza di azioni che garantisca di arrivare alla soluzione Capacità di rilevamento durante la fase di esecuzione L’agente deve calcolare un intero albero di azioni piuttosto che una singola sequenza di azioni (un ramo dell’albero tratta una situazione contingente possibile che si potrebbe verificare) Nel mondo reale si incontrano molti problemi di contingenza poiché la predizione esatta è impossibile Problemi di contingenza pianificazione Necessari algoritmi complessi L’agente può agire prima di aver trovato un piano garantito (comincia effettivamente l’esecuzione e vede quali soluzioni contingenti si verificano veramente) Date le informazioni supplementari l’agente può poi continuare a risolvere il problema Problemi di esplorazione L’agente non ha alcuna informazioni sugli effetti delle proprie azioni L’agente deve sperimentare scoprendo gradualmente cosa produrranno le sue azioni e quali tipi di stati esistono. La ricerca si svolge nel mondo reale e non in un modello: agire può comportare danni significativi per un agente privo di conoscenza Se sopravvive, acquisisce conoscenza che può riusare per problemi successivi Efficacia della ricerca Misura dell’efficacia 1. Si trova almeno una soluzione? 2. E’ una buona soluzione (con un costo di cammino basso)? 3. Qual è il costo della ricerca associato al tempo ed alla memoria richiesti per trovare una soluzione? Costo totale = costo di cammino + costo di ricerca Costo della ricerca L’agente deve decidere quali risorse dedicare alla ricerca e quali all’esecuzione. Per spazi degli stati piccoli, si considera il costo di cammino più basso Per problemi complessi trovare punto di equilibrio (l’agente può cercare per un tempo molto lungo di ottenere una soluzione ottimale, oppure può cercare per un tempo più breve ed ottenere una soluzione con costo di cammino lievemente maggiore) Risoluzione di problemi Decidere cosa inserire nella descrizione degli stati e degli operatori e cosa tralasciare (rappresentazione) Il processo di eliminare dettagli da una rappresentazione viene chiamato astrazione (astrazione nella descrizione dello stato e delle azioni) Una buona astrazione comporta l’eliminazione di più dettagli possibili mantenendo la validità ed assicurando che le azioni astratte siano facili da realizzare Classi di problemi Problemi giocattolo (Rompicapo dell’8 – Mondo dell’aspirapolvere) Problemi del mondo reale (Ricerca di itinerario) Rompicapo dell’8 Operatore: lo tessera vuota cambia posto con la tessera alla sua sinistra Rompicapo dell’8 Formulazione del problema Stati: posizione di ciascuna delle 8 tessere + tessera vuota Operatori: muovere la tessera vuota a sinistra, destra, sopra, sotto (nessun salto ammesso) Test obiettivo: configurazione finale Costo di cammino: ciascun passo costa 1 (costo del cammino = lunghezza del cammino) Mondo dell’aspirapolvere Spazio degli stati Archi/azioni: L=spostati a sn, R=spostati a dx, S=aspira Mondo dell’aspirapolvere semplificato Agente conosce la propria posizione e le posizioni di tutte le parti con sporcizia; aspira bene. Stati: uno degli stati di figura Operatori: spostati a sn, spostati a dx, aspira Test obiettivo: non lasciare sporcizia nei quadrati Costo di cammino: ciascuna azione costa 1 Soluzione: da un qualsiasi stato di partenza seguire le frecce fino ad uno stato obiettivo Mondo dell’aspirapolvere senza sensori In qualsiasi istante l’agente si trova in un insieme di stati ma non sa in quale stato di quell’insieme sia Mondo dell’aspirapolvere senza sensori L’aspirapolvere non ha alcun sensore e deve raccogliere tutta la sporcizia Insiemi di stati: sottoinsiemi di stati della figura Operatori: spostati a sn, spostati a dx, aspira Test obiettivo: ogni stato dell’insieme degli stati non contiene sporcizia Costo di cammino: ciascuna azione costa 1 Soluzione: dall’insieme iniziale degli stati (tutti) seguire le frecce fino a raggiungere un insieme di stati senza sporcizia