Ricerca di soluzioni a problemi Prof. M.T. PAZIENZA a.a. 2014-2015.

Ricerca di soluzioni a problemi

Prof. M.T. PAZIENZA

a.a. 2014-2015

Agenti reattivi

Gli agenti reattivi non possono operare bene in ambienti ove la

corrispondenza tra stati ed azioni diventa troppo corrispondenza tra stati ed azioni diventa troppo grande per essere memorizzata e troppo grande per essere memorizzata e troppo

complessa da apprendere.complessa da apprendere.

Agenti basati su obiettivi

Conoscere lo stato attualeattuale dell’ambiente non sempre è sufficiente per decidere cosa fare

Bisogna avere un obiettivoBisogna avere un obiettivo

Ricerca di una soluzione al problema di una soluzione al problema

Pianificazione

Agenti risolutore di problemi (agente basato su obiettivi)

L’agente risolutore di problemi è un tipo particolare di agente basato su obiettivi;

decide cosa fare decide cosa fare ricercandoricercando sequenze di azioni sequenze di azioni che conducono a stati desiderabili: gli obiettivi che conducono a stati desiderabili: gli obiettivi aiutano a selezionare le sequenze.aiutano a selezionare le sequenze.

Quindi cerca di massimizzare la misura delle prestazioni

Formulazione di un problema

Processo che porta a decidere, dato un Processo che porta a decidere, dato un obiettivo, quali azioni e stati considerare.obiettivo, quali azioni e stati considerare.

Ricerca di una soluzione

La ricerca è l’enumerazione di un insieme di potenziali soluzioni parziali di un problema che possono essere testate per identificare quelle che sono soluzioni reali o che potrebbero condurre a soluzioni reali del problema. Per sviluppare una ricerca è necessario definire:

• una soluzione potenziale• un metodo chiaro per la generazione di soluzioni

potenziali• un metodo per verificare quale soluzione potenziale

costituisca una soluzione reale


Il meccanismo generale della ricerca si può esprimere in termini di ricerca di cammini in un grafo

Per risolvere un problema si deve esplicitare il sottostante spazio di ricerca ed applicare a tale spazio un algoritmo di ricerca


Gli umani usano spesso l’intuizione per risolvere problemi di difficile soluzione; ciò porta a ricercare soluzioni ad hoc e non generali.

Analogamente un agente potrebbe accedere a conoscenza specifica per trovare una soluzione. Tale conoscenza extra al di là dello spazio di ricerca è la cosiddetta conoscenza euristica.

Agente risolutore di problemi(basato su obiettivi)

PROBLEMAObiettivo + Mezzi per raggiungere l’obiettivo

RICERCAProcesso di esplorazione Cosa possono fare i mezzi a disposizione

La ricerca è una parte necessaria per la risoluzione di un problema


Gli obiettivi aiutano l’agente ad organizzare il comportamento limitando gli scopi che l’agente sta cercando di raggiungere.

• Un obiettivo è l’ insieme di tutti e soli gli stati del mondo in cui è soddisfatto l’obiettivo stesso.

• Le azioni sono causa di transizioni tra stati del mondo.

• L’agente deve scegliere (tra tutte quelle possibili) una sequenza di azioni che lo conduca ad uno stato obiettivo.


1. Formulazione dell’obiettivo (basata sulla situazione corrente e sulla misura di prestazione dell’agente)

2. Formulazione del problema (processo di decisione di quali azioni e stati della risoluzione del problema considerare,successivamente alla formulazione dell’obiettivo)


Ove esistano più alternative (sequenze di azioni che raggiungono l’obiettivo), l’agente

Senon conosce lo stato risultante dopo aver compiuto

ciascuna azione, né altre informazioni addizionali, potrà SOLO scegliere a casoSe 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

Quando non è noto a priori quale sia la migliore azione immediata da compiere,

nell’ipotesi che esistano possibili sequenze di azioni per raggiungere l’obiettivo,

l’agente può analizzare diverse sequenze per ricercare la soluzione migliore (cosiddetto processo di ricerca).

Prima di cominciare a ricercare soluzioni, è necessario formulare un obiettivo e poi usare tale obiettivo per formulare un problema.

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 di ricerca

• Formulazione dell’obiettivo (basata sulla situazione attuale). Obiettivo = Insieme degli stati del mondo che soddisfano l’obiettivo

• Formulazione del problema (processo di scelta in base alla collezione di informazioni dell’agente di azioni e stati da considerare)

• Ricerca (esaminare differenti sequenze di possibili azioni e poi scegliere la migliore)

• Esecuzione della sequenza di azioni

Algoritmo di risoluzione / ricerca

1. INPUT = problema

2. OUTPUT = soluzione nella forma di sequenze di azioni

3. ESECUZIONE = realizzazione/implementazione delle sequenze di azioni

Algoritmo generale di ricerca

Dato un problema, una strategia ed un insieme di candidati

Ripeti fino ad esaurimento dei candidati/nodi:

Se non esistono candidati/nodi da espandere,

Allora non c’è soluzione al problema

Altrimenti scegli un nodo da espandere secondo strategia

Se il nodo contiene stato obiettivo: soluzione trovata

Altrimenti espandi nodo secondo strategia

Aggiungi all’ albero di ricerca i nodi risultanti

Algoritmo generale di ricerca

L’output di un algoritmo di ricerca è una soluzione,

ovvero

un cammino dallo stato iniziale allo stato che soddisfa il test obiettivo

Agente risolutore di problemi

Soluzione di problema offline-si considera che l’ambiente non cambi durante la soluzione (una soluzione online richiede l’agire senza una completa conoscenza del problema e della soluzione)

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; dato uno stato x, funzione successore(x) produce un insieme di coppie ordinate <azione,successore> dove successore è lo stato che può essere raggiunto da x eseguendo azione

Un cammino nello spazio degli stati è una qualsiasi sequenza di azioni che conduce da uno stato ad un altro (funzione costo di cammino g)

Il test obiettivo è applicato dall’agente alla descrizione di un singolo stato per determinare se è in uno stato obiettivo.

Agente risolutore di problemi

Elementi fondamentali nella definizione di un problema sono gli stati e le azioni

La conoscenza che l’agente ha sulle sue azioni e sugli stati del mondo dipende da come è connesso al suo ambiente, tramite “percezioni e azioni”.

Conoscenza e Tipi di problemi

Problemi a stato singolo (mondo accessibile, l’agente conosce l’effetto delle azioni; può calcolare lo stato dopo la sequenza delle azioni)

Problemi a stati multipli (mondo non accessibile (no sensori), l’agente conosce l’effetto delle azioni, ragiona su insiemi di stati raggiungibili dopo la sequenza di azioni)

Problemi di contingenza (ignoranza dell’agente sulla sequenza di azioni, quindi definizione alberi di azioni = pianificazione)

Problemi di esplorazione (nessuna conoscenza sugli effetti delle proprie azioni, attraverso la sperimentazione scoprire gradualmente effetti delle azioni e stati esistenti)

Problemi a stato singoloCaso più semplice

Agente riceve dai sensori informazioni sufficienti sullo stato in cui si trova (mondo accessibile)

Conosce esattamente le conseguenze di ciascuna azione

Quindi l’agente può calcolare esattamente in quale stato sarà dopo qualsiasi sequenza di azioni

Formulazione di problemia stato singolo

Un tale problema è definito da :

1. Stato iniziale x2. Operatore / funzione successore S(x)3. Test obiettivo4. 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 problemia stati multipli

Un tale problema è definito da :1. Insieme di stati iniziali2. 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 obiettivo4. 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 contingenzapianificazione

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 contingenzapianificazione

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 il 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: rappresentazione

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

Rappresentazione

Un nodo dell’albero di ricerca può essere rappresentato da una struttura dati a cinque componenti:

1. Stato nello spazio degli stati a cui corrisponde il nodo

2. Nodo genitore di quello corrente

3. Operatore applicato per generare il nodo

4. Numero nodi del cammino dalla radice (profondità)

5. Costo del cammino dallo stato iniziale

Struttura dati di un Nodo

datatype NODOcomponents: STATO, NODO-GENITORE, OPER.,

PROFONDITA’, COSTO-CAMMINO

Evitare ripetizioni di stati:Non ritornare allo stato da cui si proviene

(NO successore=padre)Non creare cammini che abbiano cicli

(NO successore=antenato)Non generare nessuno stato già generato prima

(NO successore=any prima)

Classi di problemi

Problemi giocattolo

(Rompicapo dell’8 – Mondo dell’aspirapolvere)

Problemi del mondo reale

(Ricerca di itinerario)

Rompicapo dell’8

Operatore: la tessera vuotatessera vuota cambia posto

Rompicapo dell’8Formulazione del problema

Stati: specifica della posizione di ciascuna delle 8 tessere + tessera vuotatessera vuota

Operatori: : muovere la tessera vuota a sinistra, destra, sopra, sotto (nessun salto ammesso)

Test obiettivo: verifica della configurazione finale

Costo di cammino: ciascun passo costa 1 (costo del cammino = lunghezza del cammino)

Mondo dell’aspirapolvere semplificato

Spazio degli statiArchi/azioni: L=spostati a sn, R=spostati a dx,

S=aspira

Mondo dell’aspirapolveresemplificato

Agente conosce la propria posizione e le posizioni di tutte le parti con sporcizia; aspira bene.

Stati: uno degli stati di figuraOperatori: spostati a sn, spostati a dx, aspiraTest obiettivo: non lasciare sporcizia nei quadratiCosto 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 figuraOperatori: spostati a sn, spostati a dx, aspiraTest obiettivo: ogni stato dell’insieme degli stati non

contiene sporciziaCosto 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

Strategia di ricerca

Il problema determina il grafo di rappresentazione degli stati e l’obiettivo (ovvero ciò che rappresentano i vicini di un nodo) ma non definisce la modalità di selezione di un nodo o come aggiungere un nodo alla frontiera dell’esplorazione.

Un unico algoritmo di ricerca può essere usato per risolvere qualsiasi problema; specifiche varianti dell’algoritmo realizzano strategie differenti.

Una strategia di ricerca specifica quali elementi devono essere selezionati nella frontiera; strategie diverse di ricerca si differenziano per le modalità di selezione e di aggiunta di un nodo alla frontiera.

Strategia di ricerca

Criteri di valutazione della strategia :

• Completezza (se esiste una soluzione viene trovata sempre)

• Complessità temporale

• Complessità spaziale

• Ottimalità

Strategie di ricerca

1. Ricerca non informata ( o cieca)

Non si ha alcuna informazione sul numero di passi o sul costo di cammino dallo stato attuale all’obiettivo; tutto quello che si può fare è generare successori e distinguere gli stati obiettivo dagli altri

2. Ricerca informata ( euristica)

Si hanno informazioni di preferenze tra gli stati

Ricerca informata più efficace di quella non informata

Ricerca in ampiezza

Tutti i nodi di profondità d nell’albero si espandono prima dei nodi di profondità d+1

Strategia sistematica (esaminati prima i cammini di lunghezza i, poi i+1,poi i+2,…); si assume che ciascun arco pesi 1.

Ricerca in ampiezza

Se esiste una sola soluzione, la ricerca in ampiezza la trova (completezza)

Se esistono più soluzioni, viene trovato per prima lo stato obiettivo più alto/superficiale - quindi a costo minimo (ottimalità) (tutti gli archi hanno uguale peso 1)

Valutazione: ricerca completa ed ottimale

Ricerca in ampiezza (complessità)

Se fattore di ramificazione = b

al livello i si avrà ramificazione =

Se la soluzione si trova dopo un cammino di lunghezza d, il numero massimo (soluzione peggiore) di nodi espansi è

(l’obiettivo non viene espanso)

ib

)()1(...1 32 dd bObbbb

Ricerca a costo uniforme

Quando si hanno archi di costo non unitario, esiste l’interesse a trovare la soluzione che minimizzi il costo totale del cammino.

Costi possono essere le distanze tra i punti rappresentati dai nodi, oppure costi possono essere le risorse richieste dall’agente per realizzare il task associato ad un nodo; e si vuole minimizzare i costi.


Il più semplice algoritmo che garantisce di trovare un cammino minimo è di tipo ricerca in ampiezza con la selezione del cammino a costo minimo.

La ricerca a costo uniforme modifica la strategia in ampiezza espandendo sempre il nodo sul confine con il costo più basso (misurato con il costo del cammino g(n) dal nodo origine a quello corrente – non c’è conoscenza sul prosieguo del cammino), invece del nodo di profondità minima


La ricerca a costo uniforme si implementa gestendo i nodi di frontiera con una coda a priorità ed ordinandola tramite la funzione g(n);

Si trovatrova sempre la soluzione più economica se si verifica la soluzione più economica se si verifica che il costo del cammino non decresce mai quando lo che il costo del cammino non decresce mai quando lo percorriamo. Se ci fosse un operatore con costo negativo percorriamo. Se ci fosse un operatore con costo negativo dovremmo applicare una ricerca esaustiva per trovare la dovremmo applicare una ricerca esaustiva per trovare la soluzione ottimale.soluzione ottimale.

Il costo del cammino di un nodo è somma dei costi degli operatori che determinano il cammino

)())(( ngnSuccessoreg

Ricerca a costo uniforme: andare da S a G

Ricerca in profondità

La ricerca in profondità espande sempre il primo dei nodi fino a raggiungere il livello più profondo dell’albero.

La ricerca torna indietro (backtracking) ed espande nodi a livelli più superficiali solo quando arriva ad un nodo foglia non obiettivo.

La funzione di ricerca userà un meccanismo di inserimento in un pila (l’elemento estratto è sempre l’ultimo che era stato inserito)


Occupazione di memoria modesta (memorizza un solo cammino dalla radice al nodo foglia, oltre ai nodi fratelli di ciascun nodo del cammino che rimangono non espansi)

Con uno spazio degli stati con fattore di ramificazione b e profondità massima m, la ricerca in profondità memorizza bm nodi

Complessità temporale della ricerca in profondità :

La ricerca in profondità può rimanere bloccata in un cammino sbagliato di lunghezza infinita.

Valutazione: né completa, né ottimale

)( mbO

Ricerca a profondità limitata

Si migliora la ricerca in profondità imponendo un taglio/limite (scelto in base alla conoscenza del problema) alla profondità massima di un cammino, ovvero non si espandono ulteriormente i nodi al limite di profondità imposto

Suggerimento:

Taglio = profondità obiettivo più superficiale

Ricerca bidirezionale

Le strategie di ricerca di soluzione di un problema sono simmetriche nel senso che non c’è alcuna preferenza a cominciare dallo stato iniziale per giungere allo stato obiettivo, o cominciare dallo stato obiettivo e giungere a quello iniziale (ove possibile)

Nei casi in cui l’obiettivo è esplicito, può essere più efficiente cominciare da questo.

Principio generale: si ricerca in avanti o in indietro a seconda del costo di ramificazione


Per ridurre i tempi della ricerca, la ricerca bidirezionale ricerca contemporaneamente sia in avanti (dallo stato iniziale), sia all’indietro (dall’obiettivo), fermandosi quando le due ricerche si incontrano.

Con fattore di ramificazione pari a b in entrambe le direzioni e soluzione a profondità d, allora la soluzione verrà trovata in )()2( 2/2/ dd bObO


Problemi:

• Definire predecessori di un nodo n (quei nodi che abbiano n come successore)

• Gli operatori in genere non sono reversibili, per cui il calcolo dei predecessori in genere risulta complesso.

• Cosa succede quando si hanno più stati obiettivo?

Ripetizioni di stati

Si possono semplificare alberi di ricerca infiniti dovuti a ripetizioni di stati, generando solo la porzione di albero che ricopre il grafo dello spazio degli stati.

Suggerimenti: • Non ritornare allo stato da cui si proviene• Non creare cammini che abbiano cicli• Non generare alcuno stato già generato prima

Argomenti trattati in questa lezione

• Struttura e funzionalità degli agenti risolutori di problemi

• Processo di ricerca• Tipologie di problemi da risolvere• Informazioni necessarie a definire un

problema• Tipologie di strategie di ricerca e metodologie

per la loro valutazione

Ricerca di soluzioni a problemi Prof. M.T. PAZIENZA a.a. 2014-2015.

Documents

Transcript of Ricerca di soluzioni a problemi Prof. M.T. PAZIENZA a.a. 2014-2015.