Agenti risolutori di problemi: eliminazione degli stati ripetuti

Le strategie di ricerca presentate scelgono un nodo da espandere nella frontiera, senza tener conto di quelli espansi in precedenza. Quando l'algoritmo espande un nodo corrispondente ad uno stato A, potrebbe capitare che un nodo corrispondente al medesimo stato sia stato già espanso nell'albero di ricerca. In un caso di questo tipo risulta ridondante espandere il nodo corrispondente allo stato A poichè non porterebbe nessuna informazione aggiuntiva, e se tramite questo nodo si riesce ad arrivare alla soluzione, ci si arriva ugualmente tramite il nodo già espanso.
Risulta quindi opportuno modificare l'algoritmo di ricerca in modo che tenga conto degli stati visitati e non espanda più di un nodo corrispondente al medesimo stato. Si può creare una lista di questi stati; essa va sotto il nome di lista chiusa; prima di espandere un nodo viene controllato che lo stato a cui corrisponde non sia presente nella lista.
Ogni strategia di ricerca vista ha un suo corrispondente algoritmo con eliminazione degli stati ripetuti.

Agenti risolutori di problemi: ricerca informata

Un agente che ricerca una soluzione nell'albero di ricerca, non è detto che debba limitarsi a considerare i dati del problema; in astratto, può infatti valutare quanto è promettente un nodo e basarsi anche su questa informazione per scegliere i nodi da estrarre ed espandere nella frontiera. Le strategia di ricerca che utilizzano questa logica si chiamano informate o euristiche: in generale, viene valutata la "bontà" di un nodo tramite una funzione f(n) detta funzione di valutazione.

Ricerca greedy best-first
Questa ricerca espande sempre il nodo che è più vicino all'obiettivo, ipotizzando che in questo modo è probabile arrivare rapidamente ad una soluzione. Analiticamente si dice che f(n) = h(n), dove h(n) è una funzione, solitamente definita sullo stato corrispondente al nodo, detta euristica; la funzione euristica stima il costo per arrivare da n al nodo di goal. L'algoritmo sceglie dalla frontiera il nodo con la f(n) inferiore. La ricerca non è completa nei casi in cui espando stati già visitati, dato che possono continuare ad essere espansi nodi corrispondenti allo stesso gruppo di  stati; non considerando i  nodi i cui stati sono già stati espansi (vedere eliminazione stati ripetuti), la ricerca risulta completa ma non ottima. Le complessità temporale e spaziale sono  O(b^m).

Ricerca A*
La ricerca A*, a differenza di quella greedy, tiene conto del costo complessivo del cammino per arrivare dal nodo di partenza a quello di goal. Quanto detto si traduce in una funzione di valutazione f(n) = g(n)+h(n), dove g(n) è il costo di cammino del nodo n e h(n) è la funzione euristica vista per la ricerca greedy. Questa ricerca è molto importante e come tale merita di essere analizzata più in profondità di quanto fatto con gli altri metodi di ricerca visti finora.

Agenti risolutori di problemi: ricerca non informata

Si è visto che l'aspetto fondamentale per risolvere i problemi tramite l'albero di ricerca, consiste nella ricerca del nodo da espandere nella frontiera dell'albero stesso. Questa può essere effettuata utilizzando solo le informazioni contenute nella formulazione del problema (ricerca non informata) oppure tramite l'utilizzo di altre informazioni (ricerca informata).
Si illustrano ora alcune metodologie di ricerca non informata, mettendo in luce le caratteristiche di prestazione.

Ricerca in ampiezza.
In base a questo metodo si sceglie sempre il nodo meno profondo; ciò corrisponde a trattare la frontiera come una "coda" ovvero una insieme ordinato dal quale si preleva il primo elemento aggiunto (si parla di logica FIFO: First In First Out). Considerando l'albero, verranno espansi i nodi per livelli di profondità.
La ricerca in ampiezza è completa se il branching factor b non è infinito; non è ottimale dato che la ricerca non tiene conto dei costi dei cammini; ha complessità temporale e spaziale uguale poichè tutti i nodi analizzati devono rimanere comunque in memoria, e pari a O(b^(D+1)).

Ricerca a costo uniforme
La ricerca a costo uniforme sceglie dalla frontiera il nodo a minor costo di cammino. Questo garantisce ottimalità e completezza escludendo i casi in cui esistono costi di passo nulli;  la complessità temporale e spaziale dell'operazione sono uguali per un motivo analogo a prima, e sono pari a O(b^[C*/epsilon]) dove [C*/epsilon] corrisponde al valore intero maggiore e più vicino a C*/epsilon, che significa il numero di livelli che scendo nel caso peggiore (quando la soluzione è a livello epsilon).

Ricerca in profondità
A differenza dei due metodi visti, la ricerca in profondità tende a ricercare la soluzione esplorando l'albero appunto in profondità: viene scelto dalla frontiera il nodo a profondità maggiore. Si nota subito come questo tipo di ricerca potrebbe non terminare e quindi non è completa, dato che non garantisce che venga trovata una soluzione se esiste, e a maggior ragione non è ottima; la complessità temporale è O(b^m), mentre la complessità spaziale, in questo caso, è differente dato che i nodi appartenenti a cammini sondati fino in fondo possono essere eliminati dalla memoria ed è pari a O(bm).

Ricerca a profondità limitata
Un modo per far terminare il metodo di ricerca in profondità consiste nel fissare un valore naturale l e confrontare questo valore con la profondità dei nodi; i nodi che hanno profondità maggire di l non vengono espansi. Anche in questo caso la ricerca non è completa e la complessità temporale è O(b^l) mentre quella spazioale è O(bl).

Ricerca ad approfondimento iterativo
Affrontando il problema di ricerca con l'ultimo metodo visto, non è possibile raggiungere la soluzione se questa è situata a profondità maggiore del valore fissato l. Per ovviare a questo problema si può pensare dunque di provare ad aumentare il valore di l di una unità ogni volta che completiamo la ricerca con un fallimento. Quindi partendo con l=0 si procede cone nella ricerca a profondità limitata; se non viene raggiunto il nodo corrispondente allo stato di goal, si incrementa l di 1 e si continua questa procedura in modo iterativo fino a trovare il nodo corrispondente allo stato di goal. In questo modo, se la soluzione eseiste la troviamo, quindi è un algoritmo completo, ma non ottimo se i costi di passo non sono unitari, dato che non vengono considerati nella scelta del nodo da espandere. La complessità temporale risulta O(b^D) e quella spaziale O(bD).

Agenti risolutori di problemi: soluzione del problema

La fase successiva alla formulazione del problema è la ricerca della soluzione dello stesso. Per fare ciò si parte dallo spazio degli stati dal quale si costruisce l'albero di ricerca. Il procedimento è iterativo: si considera in prima istanza lo stato iniziale e si crea un nodo corrispondente, detto radice, si applica il test obiettivo al nodo in analisi, si espande il nodo se non soddisfa il test e si sceglie un altro nodo e si continua dall'applicazione del test obiettivo.
Un nodo è una struttura dati formata da cinque elementi:

• stato dello spazio degli stati a cui il nodo è associato, da notare che ad uno stesso stato possono corrispondere più nodi;
• puntatore al padre, ovvero al nodo da cui è stato generato; questo servirà per ricostruire a ritroso il cammino dal goal raggiunto fino allo stato iniziale;
• azione che porta al nodo;
• costo del cammino che porta dalla radice al nodo (questo compo si chiama g(n));
• profondità del nodo.

Per creare l'albero di ricerca è utile definire un insieme, che viene detto frontiera, dei nodi generati nell'albero stesso ma non ancora espansi. Il problema principale risulta allora ordinare l'insieme in modo che l'algoritmo di creazione dell'albero estrarrà ad ogni passo il nodo opportuno.

Agente come risolutore di problemi

Si considera inizialmente un agente che opera in ambiente statico, osservabile, discreto e deterministico. Esso deve massimizzare la sua misura di prestazione e questo viene reso più semplice se fissiamo un obiettivo da raggiungere, che consiste in un insieme di stati del mondo. L'agente allora dovrà ricercare una sequenza di stati, detti soluzione, che lo portino a soddisfare l'obiettivo. Per trovare la soluzione bisogna formulare in modo corretto il problema considerato dall'agente intelligente definendo:

• lo spazio degli stati il quale consiste in un grafo i cui nodi sono gli stati e gli archi sono le azioni. Lo spazion degli stati è a sua volta definito da:
• lo stato iniziale in cui si trova l'agente;
• la funzione successore: funzione che dato uno stato del problema, restituisce un insieme di coppie {, };
• il test obiettivo distingue gli stati di goal (o stati obiettivo) elencandoli esplicitamente o esprimendo una condizione che deve valere per tali stati;
• il costo di cammino: funzione che dato un cammino restituisce il costo associato, sommando il costo di passo relativo ad  ogni azione eseguita

 In questa ottica la soluzione è vista come un cammino dallo stato iniziale allo stato obiettivo, e la soluzione ottima è quella a costo di cammino minore.

Si nota come, la formulazione di un problema  è il risultato di un processo di astrazione tramite il quale vengono tralasciati dettagli non necessari per il raggiungimento dell'obiettivo. Più in generale un problema può essere descritto in modi differenti; per ottenere una buona formulazione si deve limitare il numero degli stati cercando di includere per quanto possibile, le regole dell'ambiente, nella funzione successore.

Programmi agente

Il programma agente è l'implementazione della funzione agente. In base a come questi si comportano nei confronti dell'ambiente si possono distinguere quattro categorie di agenti: reattivi semplici, reattivi basati su modello, basati su obiettivi e basati sull'utilità.

Agenti reattivi semplici
Gli agenti più semplici da costruire risultano quelli che si comportano considerando solo lo stato dell'ambiente nell'istante precedente l'azione; in pratica il programma sarà strutturato come una serie di if stato then azione. Il nome reattivi deriva prorio dalla caratteristica di non considerare alcuna storia dell'ambiente osservato. Agenti progettati secondo questo paradigma si comportano bene solo in ambienti completamente osservabili, ovvero i sensori percepiscono tutte le informazioni che riguardano l'ambiente. Nella Figura è schematizzato il funzionamento degli agenti reattivi semplici. Viene usato, qui ed in seguito, l'ovale per definire strutture dati, il rettangolo per le procedure.

Agenti reattivi basati su modello

Una variante degli agenti appena illustrati tiene invece conto di come potrebbe evolvere partendo da un modello dello stesso. In questo modo l'agente agisce ancora in modo reattivo, ovvero considerando aolamente lo stato dell'ambiente, ma riesce a capire cosa accadrà probabilmente nel mondo dopo che compie una determinata azione. Per questo tali agenti riescono anche a comportarsi efficacemente in ambienti parzialmente osservabili. Nella figura è illustrato il funzionamento; si nota l'introduzione del modello nel programma agente.

Agenti basati su obiettivi

L'approccio basato su obiettivo è differente dai due già visti in quanto non porta con sè l'idea di reattività. L'azione da eseguire non è definita solo vedendo lo stato attuale del mondo ma anche calcolando come può essere raggiunto un certo obiettivo cercando di instradare le decisioni verso quella considerata corretto (obiettivo o goal). Il risultato è probabilmente meno efficente dei casi visti fin'ora, ma è sicuramente più flessibile ai cambiamenti del mondo esterno. In Figura come sempre si illustra lo schema di funzionamento dell'agente basato su modello.

  

Agenti basati su utilità

L'ultimo tipo di agenti è in parte simile a quello basato su modello: l'azione da compiere viene calcolata considerando sia lo stato corrente dell'ambiente, sia un altro fattore, detto utilità. L'utilità è un parametro che viene determinato da una funzione opportunamente definita che fa corrispondere uno o più stati ad un numetro che indica ilgrado di soddisfazione ad esso associato. In questo modo l'agente cercherà  di raggiungere gli stati che lo "soddisfano" di più. Nella Figura si nota la somiglianza con lo schema precedente soprattutto per l'assenza delle regole condizione azione.

Come nota finale, si noti che, dotando uno di questi agenti di un dispositivo capace di modellizzare la conoscenza del mondo, e di un dispositivo capace di aggiornare questa conoscenza con il passare del tempo, è inoltre possibile creare un processo di apprendimento. 

Intelligenza Artificiale: agenti intelligenti

I sistemi che sono intelligenti secondo la quarta definizione vengono detti "agenti razionali". Il termine razionale deriva direttamente dalla definizione considerata; parlando di agenti si intende una qualunque entità che percepisce l'ambiente tramite sensori e agisce tramite attuatori.

L'agente razionale quindi percepisce lo stato dell'ambiente in cui opera, prendendo una decisione relativa al compito che deve eseguire per poi agire e in modo ciclico continua a percepire-decidere-agire.
Le decisioni possono essere viste come una funzione che mette in relazione un insieme, o meglio, una sequenza di percezioni con un'azione che l'agente può compiere. Questa è detta funzione agente e viene implementata tramite un programma, detto anch'esso agente. Affinché l'agente si comporti in modo razionale, la funzione deve essere progettata opportunamente.
Fin'ora si è parlato di razionalità in modo generico, ma , per proseguire nello studio bisogna definire meglio cosa si intende. Si definisce in primo luogo un criterio che renda possibile valutare il successo del comportamento di un agente, detto misura di prestazione. Risulta ,importante e allo stesso tempo complesso, definire una corretta misura di prestazione. Questa infatti è il punto di partenza per una definizione di agente razionale, ovvero:

Per ogni possibile sequenza di percezioni, un agente razionale sceglie l'azione che massimizza il valore atteso della sua misura di prestazione date le informazioni disponibili fino a quel momento.

Data questa definizione si osserva che l'agente non è onnisciente poichè non è possibile pretendere che preveda il futuro ed in particolare non può considerare tutte le incertezze che caratterizzano gli eventi nel mondo reale.