Intelligenza Artificiale PDF

INTELLIGENZA ARTIFICIALE (Lez. 1 e 2, libro pag. 95) Una (breve) storia dell’IA 1940-1950: Primi giorni: scienze neurali e informatica si incontrano ○ 1943: McCulloch e Pitts: modello a circuiti booleani del cervello ○ 1950: "Computing Machinery and Intelligence" di Turing...

INTELLIGENZA ARTIFICIALE (Lez. 1 e 2, libro pag. 95) Una (breve) storia dell’IA 1940-1950: Primi giorni: scienze neurali e informatica si incontrano ○ 1943: McCulloch e Pitts: modello a circuiti booleani del cervello ○ 1950: "Computing Machinery and Intelligence" di Turing 1950—70: Entusiasmo! Approcci basati sulla logica ○ Anni '50: Primi programmi di IA, tra cui il programma di dama di Samuel, il Logic Theorist di Newell e Simon, il Geometry Engine di Gelernter ○ 1956: Incontro di Dartmouth: nasce il termine "Intelligenza Artificiale" ○ 1965: Algoritmo completo di Robinson per il ragionamento logico 1970—90: Approcci basati sulla conoscenza ○ 1969—79: Sviluppo iniziale dei sistemi basati sulla conoscenza ○ 1980—88: Boom dell’industria dei sistemi esperti ○ 1988—93: Crollo dell’industria dei sistemi esperti: "Inverno dell’IA" 1990—: Approcci statistici ○ Ritorno di metodi probabilistici, attenzione all’incertezza ○ Aumento della profondità tecnica ○ Sistemi di agenti e apprendimento… "Primavera dell’IA"? ○ 1996: Kasparov sconfigge Deep Blue negli scacchi ○ 1997: Deep Blue sconfigge Kasparov 2000—: Dove siamo ora? ○ Big data, potenza computazionale e reti neurali ○ Riunificazione di alcuni sottocampi ○ L’IA è usata in molte industrie ○ I motori scacchistici su normali laptop possono battere i migliori giocatori del mondo ○ Cosa può fare oggi l’IA? -Un agente è un'entità che percepisce e agisce. “Un agente è semplicemente qualcosa che agisce (il termine agente deriva dal latino agere, fare). Ovviamente, tutti i programmi informatici fanno qualcosa, ma ci si aspetta che gli agenti informatici facciano di più: operino in modo autonomo, percepiscano il loro ambiente, persistano per un periodo di tempo prolungato, si adattino ai cambiamenti e creino e perseguano obiettivi. ” -Un agente razionale seleziona le azioni che massimizzano la sua utilità (attesa). “Un agente razionale è quello che agisce in modo da ottenere il miglior risultato possibile o, in caso di incertezza, il miglior risultato atteso.” Le caratteristiche dei percetti(sono le informazioni che un agente percepisce dall'ambiente circostante attraverso i suoi sensori), dell'ambiente e dello spazio delle azioni determinano le tecniche per selezionare azioni razionali. Ricerca nello Spazio degli Stati: come trovare il miglior piano (sequenza di azioni) per risolvere un problema? Giochi Avversariali: Come imparare a reagire al meglio in un mondo con avversari? Apprendimento Supervisionato: Come apprendere un modello del mondo dai dati? Reti Neurali: Come apprendere un modello del mondo dai dati? Alla fine di questo corso sarai in grado di: Costruire e comprendere la matematica di agenti razionali e in grado di apprendere Selezionare e applicare i metodi di IA appropriati per una vasta gamma di problemi Riconoscere come questi metodi sono utilizzati nei sistemi di IA moderni Lez 2 e LIBRO P. 145 Solving Problems by Searching Un problema di ricerca consiste in: ▪ Uno spazio degli stati (un insieme di possibili stati in cui l'ambiente può trovarsi.) ▪ Una funzione di transizione (con azioni e costi) ▪ Uno stato iniziale e un test dell'obiettivo ▪ Una soluzione è una sequenza di azioni (un piano) che trasforma lo stato iniziale in uno stato obiettivo. Le azioni disponibili per l'agente. Dato uno stato, ACTIONS(s) restituisce un insieme finito di azioni che possono essere eseguite in s. Diciamo che ognuna di queste azioni è applicabile in s. EX: ACTIONS(Arad) = {ToSibiu,ToTimisoara,ToZerind}. Un modello di transizione, che descrive cosa fa ogni azione. RESULT(s,a) restituisce lo stato che risulta dall'eseguire l'azione a nello stato s. EX: RESULT(Arad,ToZerind) = Zerind Una funzione di costo dell'azione, indicata con ACTION-COST(s, a, s′) quando programmiamo o c(s, a, s′) quando facciamo matematica, che dà il costo numerico dell'applicare l'azione a nello stato s per raggiungere lo stato s′. Un agente risolutore di problemi dovrebbe utilizzare una funzione di costo che rifletta la propria misura di prestazione; ad esempio, per gli agenti che trovano percorsi, il costo di un'azione potrebbe essere la lunghezza in miglia (come visto nella Figura 3.1), oppure potrebbe essere il tempo necessario per completare l'azione. Una sequenza di azioni forma un percorso, e una soluzione è un percorso dallo stato iniziale a uno stato obiettivo. Supponiamo che i costi delle azioni siano additivi; cioè, il costo totale di un percorso è la somma dei singoli costi delle azioni. Una soluzione ottimale ha il costo del percorso più basso tra tutte le soluzioni. Lo spazio degli stati può essere rappresentato come un grafo in cui i vertici sono stati e gli archi diretti tra loro sono azioni. (*)Grafico dello spazio degli stati: una rappresentazione matematica di un problema di ricerca I nodi sono configurazioni (astratte) del mondo Gli archi rappresentano i successori (risultati delle azioni) Il test dell’obiettivo è un insieme di nodi obiettivo (magari solo uno) In un grafo dello spazio degli stati, ogni stato appare solo una volta! Raramente possiamo costruire l’intero grafo in memoria (è troppo grande), ma è un concetto utile Un albero di ricerca: Un albero dei "cosa succede se" per i piani e i loro risultati Lo stato iniziale è il nodo radice I figli corrispondono ai successori I nodi mostrano gli stati, ma corrispondono ai PIANI che raggiungono quegli stati Per la maggior parte dei problemi, non possiamo mai costruire effettivamente l’intero albero Ogni NODO nell'albero di ricerca è un intero PERCORSO nel grafo dello spazio degli stati, quindi ogni singolo nodo in un albero di ricerca rappresenta non solo un singolo stato, ma l'intera sequenza di azioni (un percorso) che è stata necessaria per arrivare a quello stato, partendo dallo stato iniziale. In pratica: Nel grafo dello spazio degli stati, ogni nodo rappresenta un singolo stato del mondo. Nell’albero di ricerca, invece, ogni nodo rappresenta il percorso completo dal punto di partenza fino a quel punto, ovvero tutte le azioni eseguite per arrivare lì. Processo di astrazione Il processo di rimozione dei dettagli da una rappresentazione si chiama astrazione. Una buona formulazione del problema ha il giusto livello di dettaglio. L'astrazione è utile se eseguire ciascuna delle azioni nella soluzione è più facile del problema originale. L’astrazione è valida se possiamo elaborare una qualsiasi soluzione astratta in una soluzione nel mondo più dettagliato. La scelta di una buona astrazione comporta quindi la rimozione di quanti più dettagli possibile, mantenendo la validità e garantendo che le azioni astratte siano facili da eseguire. Se non fosse per la capacità di costruire astrazioni utili, gli agenti intelligenti sarebbero completamente sopraffatti dal mondo reale. Esempio Dimensione dello spazio degli stati per un problema simile a quello del gioco Pac-Man, con una breve analisi delle componenti che determinano la complessità. Dettagli sullo "Stato del Mondo" Qui vengono descritti gli elementi che compongono lo stato del mondo in questo tipo di gioco: Posizioni dell'agente: 120 possibili posizioni per l'agente (presumibilmente, il giocatore). Presenza di cibo: Rappresentata da 30 variabili booleane (vero o falso), ognuna delle quali indica se c'è cibo in una specifica posizione. Posizioni dei fantasmi: 12 possibili posizioni per i fantasmi. Direzione dell'agente: Le direzioni sono quattro: Nord, Est, Sud, Ovest (NESW). Calcoli delle Dimensioni dello Spazio degli Stati La sezione "How many" esplora quanti stati totali sono possibili per diversi scenari. 1. Stati del mondo complessivi ("World states"): ○ Calcolo: 120×(2^30)×(12^2)×4 ○ Significato: Include le 120 posizioni per l'agente, le 30 variabili booleane per la presenza del cibo (ciascuna variabile ha 2 possibili valori: vero/falso, quindi 2^30), le 12 posizioni per ciascuno dei due fantasmi (per un totale di 12^2), e le 4 possibili direzioni per l'agente. 2. Stati per il percorso ("States for pathing"): ○ Valore: 120. ○ Significato: Indica che per determinare solo i percorsi (ignorando cibo e fantasmi), ci sono 120 posizioni possibili. 3. Stati per mangiare tutti i puntini ("States for eat-all-dots"): ○ Calcolo: 120×(2^30) ○ Significato: In questo caso, si considerano solo le posizioni dell'agente e la presenza/assenza di cibo, ignorando la posizione dei fantasmi e la direzione. Riassunto La diapositiva mostra quanto rapidamente cresce lo spazio degli stati quando si considerano tutte le variabili in gioco (posizioni dell’agente, fantasmi, direzione e cibo), evidenziando l'enorme complessità del problema. ESEMPI Un problema standardizzato è concepito per illustrare o mettere alla prova vari metodi di risoluzione dei problemi. Un problema del "mondo a griglia" consiste in un array bidimensionale rettangolare di celle quadrate in cui gli agenti possono muoversi da una cella all'altra. Tipicamente, l'agente può spostarsi in una cella adiacente senza ostacoli—orizzontalmente o verticalmente, e in alcuni problemi anche diagonalmente. Le celle possono contenere oggetti che l'agente può raccogliere, spingere o su cui può agire in altro modo; un muro o altro ostacolo invalicabile in una cella impedisce all'agente di spostarsi in quella cella. 1. Il mondo dell'aspirapolvere: STATI: Uno stato del mondo indica quali oggetti si trovano in quali celle. Nel mondo dell'aspirapolvere, gli oggetti sono l'agente e la sporcizia. Nella versione semplice a due celle, l'agente può trovarsi in una delle due celle, e ogni cella può contenere o meno della sporcizia, quindi ci sono 2⋅2⋅2=8 stati. In generale, un ambiente per aspirapolvere con n celle ha n⋅ 2^n stati. STATO INIZIALE: Qualsiasi stato può essere designato come stato iniziale. AZIONI: Nel mondo a due celle abbiamo definito tre azioni: Aspirare, muoversi a Sinistra e muoversi a Destra. In un mondo bidimensionale con più celle, abbiamo bisogno di più azioni di movimento. Potremmo aggiungere Su e Giù, dandoci quattro azioni di movimento assolute, oppure potremmo passare ad azioni egocentriche, definite rispetto alla prospettiva dell'agente—ad esempio, Avanti, Indietro, Girare a Destra e Girare a Sinistra. MODELLO DI TRANSIZIONE: Aspirare rimuove qualsiasi sporcizia dalla cella in cui si trova l'agente; Avanti sposta l'agente di una cella nella direzione in cui è rivolto, a meno che non colpisca un muro, nel qual caso l'azione non ha effetto. Indietro sposta l'agente nella direzione opposta, mentre Girare a Destra e Girare a Sinistra cambiano la direzione in cui è rivolto. STATI OBIETTIVO: Gli stati in cui ogni cella è pulita. COSTO DELL'AZIONE: Ogni azione costa 1.  2. Puzzle dell'8 Consiste in una griglia 3×3 con otto tasselli numerati e uno spazio vuoto, e il puzzle del 15 su una griglia 4×4. L'obiettivo è raggiungere uno stato obiettivo specificato, come quello mostrato a destra della figura. La formulazione standard dell'8 puzzle è la seguente: STATI: Una descrizione dello stato specifica la posizione di ciascun tassello. STATO INIZIALE: Qualsiasi stato può essere designato come stato iniziale. Nota che una proprietà di parità divide lo spazio degli stati—qualsiasi obiettivo può essere raggiunto esattamente dalla metà degli stati iniziali possibili. AZIONI: Anche se nel mondo fisico è un tassello che scorre, il modo più semplice di descrivere un'azione è pensare allo spazio vuoto che si muove a Sinistra, Destra, Su o Giù. Se lo spazio vuoto è sul bordo o nell'angolo, non tutte le azioni saranno applicabili. MODELLO DI TRANSIZIONE: Mappa uno stato e un'azione a uno stato risultante; ad esempio, se applichiamo Sinistra allo stato iniziale nella Figura 3.3, lo stato risultante avrà il 5 e lo spazio vuoto scambiati di posto. STATO OBIETTIVO: Anche se qualsiasi stato potrebbe essere l'obiettivo, in genere specifichiamo uno stato con i numeri in ordine, come nella Figura 3.3. COSTO DELL'AZIONE: Ogni azione costa 1. *Search Algorithms (libro pag 163) Un algoritmo di ricerca prende in input un problema di ricerca e restituisce una soluzione o un'indicazione di fallimento. Consideriamo algoritmi che sovrappongono un albero di ricerca sul grafo dello spazio degli stati, formando vari percorsi dallo stato iniziale, cercando di trovare un percorso che raggiunga uno stato obiettivo. Ogni nodo nell'albero di ricerca corrisponde a uno stato nello spazio degli stati, e i bordi nell'albero di ricerca corrispondono alle azioni. La radice dell'albero corrisponde allo stato iniziale del problema. È importante comprendere la distinzione tra lo spazio degli stati e l'albero di ricerca. Lo spazio degli stati descrive il set (potenzialmente infinito) di stati nel mondo e le azioni che permettono transizioni da uno stato all'altro. L'albero di ricerca descrive i percorsi tra questi stati, cercando di raggiungere l'obiettivo. L'albero di ricerca può avere percorsi multipli verso (e quindi più nodi per) un determinato stato, ma ogni nodo nell'albero ha un percorso unico che lo collega alla radice (come accade in tutti gli alberi). ES: L'albero di ricerca mostra i primi passi nella ricerca di un percorso da Arad a Bucarest. Il nodo radice dell'albero di ricerca si trova nello stato iniziale, Arad. Possiamo espandere il nodo considerando le ACTIONS (azioni) disponibili per quello stato, utilizzando la funzione RESULT (risultato) per vedere a quali stati portano tali azioni, e generare un nuovo nodo (chiamato nodo figlio o nodo successore) per ciascuno degli stati risultanti. Ogni nodo figlio ha Arad come nodo padre. Ora dobbiamo scegliere quale di questi tre nodi figli considerare successivamente. Questa è l'essenza della ricerca: seguire una possibilità ora e mettere da parte le altre per un momento successivo. Supponiamo di scegliere di espandere prima Sibiu. La figura 3.4 (in basso) mostra il risultato: un insieme di 6 nodi non espansi (evidenziati in grassetto). Chiamiamo questo insieme la frontiera dell'albero di ricerca. Diciamo che uno stato per il quale è stato generato un nodo è stato raggiunto (indipendentemente dal fatto che tale nodo sia stato espanso o meno). La frontiera separa due regioni del grafo dello spazio degli stati: una regione interna in cui ogni stato è stato espanso, e una regione esterna di stati che non sono ancora stati raggiunti. Ricerca: - Espandere i piani potenziali (nodi dell'albero) - Mantenere una frontiera di piani parziali in esame - Cercare di espandere il minor numero possibile di nodi dell'albero 1. Definizione della funzione La funzione TREE-SEARCH(problem, strategy) prende in ingresso un problema da risolvere e una strategia per determinare l'ordine di esplorazione dei nodi. La funzione restituisce una soluzione se trovata, altrimenti restituisce un fallimento. 2. Inizializzazione dell'albero di ricerca Viene inizializzato un albero di ricerca partendo dallo stato iniziale del problema. Questo significa che si crea il nodo radice dell’albero, che rappresenta lo stato iniziale da cui partire per esplorare. 3. Ciclo loop do La funzione entra in un ciclo (loop do), che continuerà fino a quando non viene trovata una soluzione o si determina che non esiste. 4. Verifica della presenza di candidati per l'espansione La funzione verifica se ci sono nodi candidati per l'espansione: ○ Se non ci sono nodi candidati per essere espansi, significa che non ci sono altre soluzioni possibili da esplorare, quindi la funzione ritorna "fallimento". 5. Scelta di un nodo foglia per l'espansione Viene scelto un nodo foglia per l'espansione, seguendo la strategia specificata. Una foglia è un nodo che non è ancora stato espanso. ○ La strategia di esplorazione (come la ricerca in ampiezza o in profondità) determina quale nodo foglia selezionare. 6. Verifica se il nodo contiene uno stato obiettivo Una volta scelto un nodo, la funzione controlla se questo nodo rappresenta uno stato obiettivo:  ○ Se è così, significa che la soluzione è stata trovata e viene restituita la soluzione corrispondente. 7. Espansione del nodo Se il nodo non contiene lo stato obiettivo, allora il nodo viene espanso. ○ L'espansione significa che si generano tutti i nodi successori (i "figli") di questo nodo, basati sulle possibili azioni eseguibili dallo stato attuale. ○ Questi nodi vengono quindi aggiunti all'albero di ricerca, per poter essere esplorati nei passaggi successivi del ciclo. 8. end Il ciclo continua a ripetersi fino a quando non viene trovata una soluzione o si stabilisce che il problema non ha soluzione. Riassunto La funzione TREE-SEARCH continua a esplorare i nodi dell'albero: Sceglie i nodi foglia in base alla strategia. Verifica se ogni nodo rappresenta la soluzione. Se non è una soluzione, lo espande e continua. Questo processo di espansione e verifica prosegue finché non viene trovata una soluzione (e viene restituita) oppure finché non ci sono più nodi da esplorare (e si ritorna "fallimento"). —------------------------------------------------------------------------------------------------------------------------------------ ------------ Le strategie di esplorazione nei problemi di ricerca in uno spazio di stati sono modi diversi per determinare l'ordine in cui i nodi vengono esplorati. Alcune strategie comuni sono: 1. Ricerca in Ampiezza (Breadth-First Search, BFS) Come funziona:Espandere prima il nodo più superficiale. Esplora ogni livello dell'albero prima di passare al successivo. La frontiera è una coda FIFO (First In, First Out). Vantaggi: Garantisce di trovare la soluzione più vicina al nodo radice (minimo numero di mosse). Svantaggi: Richiede molta memoria, poiché mantiene in memoria tutti i nodi di un livello prima di passare a quello successivo. 2. Ricerca in Profondità (Depth-First Search, DFS) Come funziona: Esplora un ramo dell'albero fino alla fine prima di tornare indietro e esplorare un altro ramo. La frontiera è una pila LIFO (Last In, First Out). Vantaggi: Usa meno memoria rispetto alla ricerca in ampiezza.  Svantaggi: Non garantisce di trovare la soluzione ottimale e potrebbe finire in cicli infiniti senza raggiungere la soluzione (a meno che non si imponga un limite di profondità). 3. Ricerca in Profondità Limitata (Depth-Limited Search) Come funziona: È simile alla DFS, ma limita la profondità massima dei nodi esplorati. Vantaggi: Evita di esplorare alberi infiniti e permette di controllare la profondità massima. Svantaggi: Potrebbe non trovare la soluzione se è più profonda del limite imposto. 4. Ricerca Iterativa di Profondità (Iterative Deepening Depth-First Search, IDDFS) Come funziona: Combina BFS e DFS. Esplora con una profondità limitata e aumenta il limite di uno a ogni iterazione. Vantaggi: Trova la soluzione ottimale come BFS, ma usa meno memoria. Svantaggi: Potrebbe ripetere molte operazioni, ma è spesso efficiente in termini di memoria. 5. Ricerca con Costo Uniforme (Uniform-Cost Search) Come funziona: È una ricerca in ampiezza ponderata, dove i nodi vengono esplorati in base al costo del percorso accumulato. Vantaggi: Trova sempre la soluzione a costo minimo. Svantaggi: Richiede più tempo se i costi sono molto variabili o se i percorsi sono lunghi. 6. Ricerca Greedy (Greedy Best-First Search) Come funziona: Esplora i nodi in base a una funzione euristica che stima la “vicinanza” al nodo obiettivo. Vantaggi: Può essere molto veloce in alcuni casi. Svantaggi: Non garantisce la soluzione ottimale; può restare bloccata in soluzioni locali sub-ottimali. 7. Ricerca A* (A-Star Search) Come funziona: Usa una combinazione di costo accumulato e stima euristica (somma di costo + stima di distanza all'obiettivo). Vantaggi: Trova la soluzione ottimale (se l’euristica è ammissibile, cioè non sovrastima la distanza). Svantaggi: Può essere costosa in termini di memoria, ma è tra le più efficienti per trovare soluzioni ottime. 8. Ricerca Bidirezionale Come funziona: Effettua due ricerche simultanee, una dal nodo iniziale e una dal nodo obiettivo, e si ferma quando le due ricerche si incontrano. Vantaggi: Può essere molto più veloce in alcuni casi. Svantaggi: Richiede conoscere il nodo obiettivo ed è complessa da implementare in problemi dove non c'è un chiaro obiettivo. Ogni strategia è utile in diversi tipi di problemi, a seconda delle caratteristiche dell’albero (come la profondità della soluzione, la distribuzione dei costi e la presenza di cicli). —------------------------------------------------------------------------------------------------------------------------------------ --------------- Best-first search Come decidiamo quale nodo della frontiera espandere successivamente? Un approccio molto generale è chiamato ricerca best-first, in cui scegliamo un nodo con il valore minimo di una funzione di valutazione f(n). Ad ogni iterazione, scegliamo un nodo della frontiera con il valore minimo di f(n), lo restituiamo se il suo stato è uno stato obiettivo, altrimenti applichiamo la funzione EXPAND (espansione) per generare i nodi figli. Ogni nodo figlio viene aggiunto alla frontiera se non è stato raggiunto prima, o viene reinserito se ora viene raggiunto con un percorso che ha un costo inferiore rispetto a qualsiasi percorso precedente. L'algoritmo restituisce un'indicazione di fallimento oppure un nodo che rappresenta un percorso verso un obiettivo. Strutture dati per la ricerca Gli algoritmi di ricerca richiedono una struttura dati per tenere traccia dell'albero di ricerca. Un nodo nell'albero è rappresentato da una struttura dati con quattro componenti:  node.STATE: lo stato a cui corrisponde il nodo; node.PARENT: il nodo nell'albero che ha generato questo nodo; node.ACTION: l'azione applicata allo stato del nodo padre per generare questo nodo; node.PATH-COST: il costo totale del percorso dallo stato iniziale a questo nodo. In formule matematiche, usiamo g(node) come sinonimo di PATH-COST. Seguendo i puntatori PARENT da un nodo possiamo recuperare gli stati e le azioni lungo il percorso fino a quel nodo. Fare questo partendo da un nodo obiettivo ci dà la soluzione. Abbiamo bisogno di una struttura dati per memorizzare la frontiera. La scelta appropriata è una coda di qualche tipo, poiché le operazioni su una frontiera sono: IS-EMPTY(frontier): restituisce vero solo se non ci sono nodi nella frontiera. POP(frontier): rimuove il nodo superiore dalla frontiera e lo restituisce. TOP(frontier): restituisce (ma non rimuove) il nodo superiore della frontiera. ADD(node, frontier): inserisce il nodo nel posto giusto nella coda. Tre tipi di code vengono utilizzati negli algoritmi di ricerca: 1. Coda di priorità: estrae per prima il nodo con il costo minimo secondo una funzione di valutazione f. Viene usata nella ricerca best-first. 2. Coda FIFO (First In, First Out): estrae per prima il nodo che è stato aggiunto alla coda per primo. La vedremo utilizzata nella ricerca in ampiezza (breadth-first search). 3. Coda LIFO (Last In, First Out), anche conosciuta come stack: estrae per prima il nodo più recentemente aggiunto. La vedremo utilizzata nella ricerca in profondità (depth-first search). Gli stati raggiunti possono essere memorizzati come una tabella di ricerca (ad esempio, una tabella hash), dove ogni chiave è uno stato e ogni valore è il nodo corrispondente a quello stato. CICLI Delle volte anche se lo spazio degli stati ha solo 20 stati, l'albero di ricerca completo è infinito perché non esiste un limite alla frequenza con cui si può percorrere un ciclo. Un ciclo è un caso speciale di un percorso ridondante: è solo un modo peggiore per arrivare allo stesso stato e non deve essere preso in considerazione nella nostra ricerca di percorsi ottimali. Consideriamo un agente in un mondo a griglia 10 × 10, con la possibilità di muoversi in una delle 8 caselle adiacenti. Se non ci sono ostacoli, l'agente può raggiungere una qualsiasi delle 100 caselle in 9 mosse o meno. Ma il numero di percorsi di lunghezza 9 è quasi 8^9 (un po' meno a causa dei bordi della griglia), ovvero più di 100 milioni. In altre parole, la cella media può essere raggiunta da oltre un milione di percorsi ridondanti di lunghezza 9, e se eliminiamo i percorsi ridondanti, possiamo completare una ricerca circa un milione di volte più velocemente. Come si suol dire, gli algoritmi che non riescono a ricordare il passato sono destinati a ripeterlo. Ci sono tre approcci a questo problema. 1. Ricordare tutti gli stati precedentemente raggiunti: (come fa la ricerca best-first), permettendoci di rilevare tutti i percorsi ridondanti e mantenere solo il miglior percorso per ogni stato. Questo è appropriato per spazi degli stati in cui ci sono molti percorsi ridondanti, ed è la scelta preferita quando la tabella degli stati raggiunti può essere contenuta in memoria. 2. Non preoccuparsi della ripetizione del passato: Ci sono alcune formulazioni di problemi in cui è raro o impossibile che due percorsi raggiungano lo stesso stato. Un esempio potrebbe essere un problema di assemblaggio in cui ogni azione aggiunge una parte a un assemblaggio in evoluzione, e c'è un ordinamento delle parti in modo che sia possibile aggiungere Per questi problemi, potremmo risparmiare A e poi B, ma non B e poi A. spazio in memoria se non teniamo traccia degli stati raggiunti e non controlliamo i percorsi ridondanti. Chiamiamo un algoritmo di ricerca un algoritmo di ricerca su grafi se controlla i percorsi ridondanti, e un algoritmo di ricerca ad albero se non li controlla. L'algoritmo BEST-FIRST-SEARCH è un algoritmo di ricerca su grafi; se rimuoviamo tutte le riferimenti agli stati raggiunti, otteniamo una ricerca ad albero che utilizza meno memoria, ma esaminerà percorsi ridondanti per lo stesso stato e quindi sarà più lenta. 3. Compromesso: Possiamo fare un compromesso e controllare i cicli, ma non i percorsi ridondanti in generale. Poiché ogni nodo ha una catena di puntatori ai genitori, possiamo controllare i cicli  senza bisogno di memoria aggiuntiva seguendo la catena dei genitori per vedere se lo stato alla fine del percorso è già apparso in precedenza nel percorso. Alcune implementazioni seguono tutta la catena fino in cima, eliminando così tutti i cicli; altre implementazioni seguono solo alcuni collegamenti (ad esempio, al genitore, al nonno e al bisnonno), e quindi richiedono solo una quantità di tempo costante, eliminando così tutti i cicli brevi (e facendo affidamento su altri meccanismi per gestire i cicli lunghi). Misurare le prestazioni nella risoluzione dei problemi Prima di entrare nel design dei vari algoritmi di ricerca, consideriamo i criteri utilizzati per scegliere tra di essi. Possiamo valutare le prestazioni di un algoritmo in quattro modi: 1. Completezza: L'algoritmo è garantito a trovare una soluzione quando c'è, e a riportare correttamente il fallimento quando non c'è? 2. Ottimalità del costo: L'algoritmo trova una soluzione con il costo del percorso più basso tra tutte le soluzioni? 3. Complessità temporale: Quanto tempo impiega per trovare una soluzione? Questo può essere misurato in secondi, o più astrattamente dal numero di stati e azioni considerati. 4. Complessità spaziale: Quanta memoria è necessaria per eseguire la ricerca? Per comprendere la completezza, consideriamo un problema di ricerca con un obiettivo unico. Tale obiettivo potrebbe trovarsi ovunque nello spazio degli stati; quindi, un algoritmo completo deve essere in grado di esplorare sistematicamente ogni stato raggiungibile dallo stato iniziale. Nei casi di spazi degli stati finiti, ciò è abbastanza semplice da realizzare: finché teniamo traccia dei percorsi e scartiamo quelli che sono cicli (ad esempio da Arad a Sibiu e poi di nuovo ad Arad), alla fine raggiungeremo ogni stato raggiungibile. Nei casi di spazi degli stati infiniti, è necessaria maggiore attenzione. Ad esempio, un algoritmo che applicasse ripetutamente l'operatore “fattoriale” nel problema di Knuth con il numero 4 seguirebbe un percorso infinito da 4 a 4! a (4!)!, e così via. Allo stesso modo, su una griglia infinita senza ostacoli, spostarsi ripetutamente in linea retta segue anch'esso un percorso infinito di nuovi stati. In entrambi i casi, l'algoritmo non torna mai a uno stato già raggiunto, ma è incompleto perché ampie aree dello spazio degli stati non vengono mai raggiunte. Per essere completo, un algoritmo di ricerca deve essere sistematico nel modo in cui esplora uno spazio degli stati infinito, assicurandosi di poter eventualmente raggiungere qualsiasi stato connesso allo stato iniziale. Ad esempio, su una griglia infinita, un tipo di ricerca sistematica è un percorso a spirale che copre tutte le celle che si trovano a s passi dall'origine, prima di passare a celle che si trovano s+1 passi di distanza. Sfortunatamente, in uno spazio degli stati infinito senza soluzione, un algoritmo valido deve continuare a cercare per sempre; non può terminare perché non può sapere se il prossimo stato sarà un obiettivo. La complessità temporale e spaziale vengono considerate rispetto a una qualche misura della difficoltà del problema. Nella scienza informatica teorica, la misura tipica è la dimensione del grafo dello spazio degli stati, ∣V∣+∣E∣, dove ∣V∣ è il numero di vertici (nodi degli stati) del grafo e ∣E∣ è il numero di archi (coppie distinte stato/azione). Questo è appropriato quando il grafo è una struttura dati esplicita, come la mappa della Romania. Ma in molti problemi di intelligenza artificiale, il grafo è rappresentato solo implicitamente dallo stato iniziale, dalle azioni e dal modello di transizione. Per uno spazio degli stati implicito, la complessità può essere misurata in termini di profondità o numero di azioni in una soluzione ottimale; d, il numero massimo di azioni in un qualsiasi percorso; e fattore di ramificazione m, ovvero il numero di successori di un nodo che devono essere considerati. Strategie di ricerca non informate p 175 Un algoritmo di ricerca non informata non ha alcun indizio su quanto uno stato sia vicino all'obiettivo. Ad esempio, considera il nostro agente in Arad con l'obiettivo di raggiungere Bucarest. Un agente non informato, senza alcuna conoscenza della geografia della Romania, non ha idea se andare a Zerind o a Sibiu sia un passo migliore da fare inizialmente. Al contrario, un agente informato, che conosce la posizione di ogni città, sa che Sibiu è molto più vicino a Bucarest e quindi è più probabile che faccia parte del percorso più breve. Proprietà degli Algoritmi di Ricerca Completo: Garantito di trovare una soluzione se esiste? Ottimale: Garantito di trovare il percorso di costo minimo? Complessità temporale? Complessità spaziale? Cartone del albero di ricerca: ○ b è il fattore di ramificazione  ○ m è la profondità massima, è il numero massimo di livelli nell'albero di ricerca, che rappresenta la lunghezza del percorso più lungo dalla radice (il nodo iniziale) a un nodo foglia (un nodo terminale che rappresenta una possibile soluzione o un nodo che non ha ulteriori figli). ○ soluzioni a diverse profondità Numero di nodi nell'intero albero? 1+b+b^2+…+b^m=O(b^m) Ricerca in ampiezza (Breadth-first search) Proprietà della Ricerca in Ampiezza (BFS) Quali nodi espande la BFS? ○ Elabora tutti i nodi sopra la soluzione più superficiale. ○ Sia s la profondità della soluzione più superficiale. ○ La ricerca richiede un tempo O(b^s) Quanto spazio occupa la frontiera? ○ Ha approssimativamente l'ultimo livello, quindi O(b^s). È completa? ○ s deve essere finito se esiste una soluzione, quindi sì! È ottimale? ○ Solo se i costi sono tutti 1 (ne parleremo più avanti). Quando tutte le azioni hanno lo stesso costo, una strategia appropriata è la ricerca in ampiezza (breadth-first search), in cui il nodo radice viene espanso per primo, poi vengono espansi successivamente tutti i successori del nodo radice, poi i successori di questi successori, e così via. Questa è una strategia di ricerca sistematica che è quindi completa anche in spazi degli stati infiniti. Potremmo implementare la ricerca in ampiezza come una chiamata a BEST-FIRST-SEARCH, dove la funzione di valutazione f(n) è la profondità del nodo, cioè il numero di azioni necessarie per raggiungere il nodo. Tuttavia, possiamo ottenere maggiore efficienza con qualche trucco. Una coda FIFO (first-in-first-out) sarà più veloce di una coda di priorità e ci darà l'ordine corretto dei nodi: i nuovi nodi (che sono sempre più profondi dei loro genitori) vanno in fondo alla coda, mentre i vecchi nodi, che sono più superficiali dei nuovi, vengono espansi per primi. Inoltre, lo stato raggiunto può essere memorizzato come un insieme di stati invece che come una mappatura da stati a nodi, poiché una volta che abbiamo raggiunto uno stato, non possiamo mai trovare un percorso migliore per quello stato. Questo significa anche che possiamo eseguire un test dell'obiettivo in anticipo, verificando se un nodo è una soluzione non appena viene generato, piuttosto che il test dell'obiettivo posticipato che la ricerca best-first utilizza, aspettando che un nodo venga rimosso dalla coda. La Figura 3.8 mostra il progresso di una ricerca in ampiezza su un albero binario, e la Figura 3.9 mostra l'algoritmo con gli ottimizzazioni per l'efficienza nel test dell'obiettivo. La ricerca in ampiezza trova sempre una soluzione con il numero minimo di azioni, perché quando genera nodi alla profondità d, ha già generato tutti i nodi alla profondità d-1, quindi se uno di questi fosse una soluzione, sarebbe già stato trovato. Ciò significa che è ottimale in termini di costo per i problemi in cui tutte le azioni hanno lo stesso costo, ma non per i problemi che non hanno questa proprietà. È comunque completa in entrambi i casi. In termini di tempo e spazio, immaginiamo di cercare in un albero uniforme in cui ogni stato ha b successori. La radice dell'albero di ricerca genera b nodi, ognuno dei quali genera altri b nodi, per un totale di b^2 al secondo livello. Ognuno di questi genera b^3 nodi, producendo b^3 nodi al terzo livello, e così via. Ora supponiamo che la soluzione sia alla profondità d. Il numero totale di nodi generati è: 1 + b + b^2 + b^3 +... + b^d = O(b^d) Tutti i nodi rimangono in memoria, quindi sia la complessità temporale che quella spaziale sono O(b^d). Limiti esponenziali come questi sono preoccupanti. Come esempio tipico del mondo reale, consideriamo un problema con un fattore di ramificazione b = 10, una velocità di elaborazione di 1 milione di nodi al secondo e requisiti di memoria di 1 Kbyte per nodo. Una ricerca a profondità d = 10 richiederebbe meno di 3 ore, ma richiederebbe 10 terabyte di memoria. I requisiti di memoria sono un problema maggiore per la ricerca in ampiezza rispetto al tempo di esecuzione. Ma il tempo è comunque un fattore importante. Alla profondità d = 14, anche con memoria infinita, la ricerca richiederebbe 3,5 anni. In generale, i problemi di ricerca con complessità esponenziale non possono essere risolti dalla ricerca non informata, se non per le istanze più piccole. Ricerca in profondità (Depth-first search) Proprietà della Ricerca in Profondità (DFS) Quali nodi espande la DFS? ○ Alcuni prefissi sinistri dell'albero. ○ Potrebbe elaborare l'intero albero! ○ Se m è finito, richiede un tempo O(b^m). Quanto spazio occupa la frontiera? ○ Ha solo i fratelli sul percorso verso la radice, quindi O(b^m). È completo? ○ m potrebbe essere infinito, quindi solo se preveniamo i cicli (ne parleremo più avanti). È ottimale?  ○ No, trova la soluzione "più a sinistra", indipendentemente dalla profondità o dal costo. La ricerca in profondità espande sempre prima il nodo più profondo nella frontiera. Potrebbe essere implementata come una chiamata a BEST-FIRST-SEARCH, dove la funzione di valutazione è il negativo della profondità. Tuttavia, di solito viene implementata non come una ricerca su grafi, ma come una ricerca ad albero che non mantiene una tabella degli stati raggiunti. Il progresso della ricerca è illustrato nella Figura 3.11; la ricerca procede immediatamente fino al livello più profondo dell'albero di ricerca, dove i nodi non hanno successori. La ricerca quindi "risale" al nodo più profondo successivo che ha ancora successori non espansi. La ricerca in profondità non è ottimale in termini di costi; restituisce la prima soluzione trovata, anche se non è la più economica. Per spazi di stati finiti che sono alberi, è efficiente e completa; per spazi di stati aciclici, può finire per espandere lo stesso stato più volte tramite percorsi diversi, ma esplorerà comunque l'intero spazio in modo sistematico. Negli spazi di stati ciclici, può bloccarsi in un ciclo infinito; pertanto, alcune implementazioni della ricerca in profondità controllano ogni nuovo nodo per verificare la presenza di cicli. Infine, negli spazi di stati infiniti, la ricerca in profondità non è sistematica: può bloccarsi percorrendo un cammino infinito, anche se non ci sono cicli. Perciò, la ricerca in profondità non è completa. Con tutte queste limitazioni, perché qualcuno dovrebbe considerare l'uso della ricerca in profondità anziché quella in ampiezza o la ricerca migliore (best-first)? La risposta è che, per problemi in cui una ricerca ad albero è fattibile, la ricerca in profondità richiede molta meno memoria. Non manteniamo affatto una tabella degli stati raggiunti, e la frontiera è molto piccola: pensa alla frontiera nella ricerca in ampiezza come la superficie di una sfera in espansione, mentre la frontiera nella ricerca in profondità è solo un raggio della sfera. Per uno spazio di stati a forma di albero finito, come quello nella Figura 3.11, una ricerca in profondità ad albero richiede tempo proporzionale al numero di stati, e ha una complessità di memoria di solo O(bm), dove b è il fattore di ramificazione e m è la profondità massima dell'albero. Alcuni problemi che richiederebbero exabyte di memoria con la ricerca in ampiezza possono essere gestiti con solo pochi kilobyte usando la ricerca in profondità. Grazie al suo parsimonioso utilizzo della memoria, la ricerca in profondità ad albero è stata adottata come metodo base in molte aree dell'IA, inclusa la soddisfazione dei vincoli (Capitolo 6), la soddisfazione proposizionale (Capitolo 7) e la programmazione logica (Capitolo 9). Una variante della ricerca in profondità chiamata ricerca con backtracking utilizza ancora meno memoria (vedi Capitolo 6 per maggiori dettagli). Nel backtracking, viene generato un solo successore alla volta anziché tutti i successori; ogni nodo parzialmente espanso ricorda quale successore generare successivamente. Inoltre, i successori vengono generati modificando direttamente la descrizione dello stato corrente, anziché allocare memoria per un nuovo stato. Questo riduce i requisiti di memoria a una sola descrizione di stato e a un percorso di O(m) azioni; un notevole risparmio rispetto a O(bm) stati della ricerca in profondità. Con il backtracking abbiamo anche l'opzione di mantenere una struttura dati efficiente per gli stati nel percorso corrente, permettendoci di controllare la presenza di cicli in O(1) tempo anziché O(m). Per far funzionare il backtracking, dobbiamo essere in grado di annullare ogni azione quando torniamo indietro. Il backtracking è fondamentale per il successo di molti problemi con descrizioni di stato grandi, come l'assemblaggio robotico. Iterative Deepening Idea: ottenere il vantaggio spaziale della DFS con i vantaggi temporali / di soluzione superficiale della BFS. Funziona eseguendo una DFS ripetutamente con un limite di profondità crescente, fermandosi quando trova la soluzione o quando non ci sono più nodi da esplorare. Esegui una DFS con limite di profondità 1. Se non c'è soluzione… Esegui una DFS con limite di profondità 2. Se non c'è soluzione… Esegui una DFS con limite di profondità 3. ….. Non è eccessivamente ridondante? ○ Generalmente, la maggior parte del lavoro avviene nel livello più basso cercato, quindi non è così male! Proprietà Complessità Temporale: O(b^d), dove b è il fattore di ramificazione e d è la profondità della soluzione più superficiale. Complessità Spaziale: O(b * d), come la DFS. Completezza: Sì, dato che esplora i livelli in ordine crescente di profondità. Ottimalità: Sì, ma solo se tutti i costi degli archi sono uguali. Cost-Sensitive Search La BFS trova il percorso più corto in termini di numero di azioni. Tuttavia, non trova il percorso a costo minimo. Ora tratteremo un algoritmo simile che trova il percorso a costo minimo. Ricerca ad approfondimento iterativo e limitata in profondità tipo albero. L’approfondimento iterativo applica ripetutamente la ricerca con limite di profondità(depth-limited), aumentando progressivamente il limite. Restituisce uno tra tre possibili valori: un nodo soluzione; o fallimento (failure), se ha esaurito tutti i nodi dimostrando che non esiste soluzione a nessuna profondità; oppure interruzione (cutoff), che indica che potrebbe esserci una soluzione a una profondità maggiore di quella attuale, l. Si tratta di un algoritmo di ricerca tipo albero che non tiene traccia degli stati già raggiunti e, quindi, utilizza molta meno memoria rispetto alla ricerca best-first; tuttavia, corre il rischio di visitare lo stesso stato più volte attraverso percorsi diversi. Inoltre, se il controllo dei cicli non intercetta tutti i cicli, l'algoritmo potrebbe rimanere bloccato in un loop. Uniform Cost Search (UCS) -Ricerca a Costo Uniforme- Strategia: espandere prima il nodo più economico. Uniform Cost Search (UCS) è un algoritmo di ricerca che cerca di trovare il percorso di costo minimo verso la soluzione espandendo i nodi a costo cumulativo più basso. UCS è simile alla ricerca in ampiezza (BFS), ma è sensibile ai costi: invece di esplorare i nodi per livelli di profondità, esplora i nodi ordinati per costo totale, indipendentemente dalla profondità. Per costo cumulativo si intende il costo totale accumulato lungo un percorso che parte dal nodo iniziale e arriva a un determinato nodo La frontiera è una coda di priorità (priorità: costo cumulativo). ordinandoli in base al costo cumulativo del percorso dal nodo iniziale fino al nodo corrente Proprietà della Ricerca a Costo Uniforme (UCS) Quali nodi espande l'UCS? UCS inizierà dal nodo iniziale e esplorerà i percorsi di costo più basso per primo. Man mano che esplora i nodi, accumula il costo totale del percorso fino al nodo corrente. Se raggiunge il nodo obiettivo con un certo costo e non ci sono percorsi di costo inferiore ancora da esplorare, allora ha trovato il percorso più economico. Elabora tutti i nodi con costo inferiore alla soluzione più economica! Se quella soluzione costa C* e i costi degli archi sono almeno epsilon, allora la "profondità effettiva" è approssimativamente C*/epsilon. Richiede un tempo O(b^(C*/epsilon)) (esponenziale nella profondità effettiva). b è il fattore di ramificazione (numero medio di nodi figli per ogni nodo), C* è il costo della soluzione più economica, ε è il costo minimo di qualsiasi arco. Espansione del Nodo più Economico: In ogni passo, UCS rimuove il nodo con il costo più basso dalla frangia e lo espande. Aggiunge poi i vicini alla frangia, aggiornando il costo cumulativo per ogni percorso. Aggiornamento dei Costi: Se UCS trova un percorso meno costoso per un nodo già esplorato o in frangia, aggiorna il percorso con il costo inferiore. Quanto spazio occupa la frontiera? Ha approssimativamente l'ultimo livello, quindi O(b^(C*/epsilon)). È completa? Assumendo che la migliore soluzione abbia un costo finito e che il costo minimo degli archi sia positivo, sì! UCS è completo, ossia trova una soluzione se questa esiste, a condizione che il costo degli archi sia finito e non negativo. È ottimale? Sì! (Dimostrazione nella prossima lezione tramite A*). UCS è ottimale. Trova sempre il percorso a costo minimo verso la soluzione, poiché espande i nodi in ordine crescente di costo. Proprietà Complessità Temporale: O(b^(C*/ε)), dove C* è il costo della soluzione più economica e ε è il costo minimo degli archi. Complessità Spaziale: O(b^(C*/ε)), poiché mantiene tutti i nodi in coda fino a trovare la soluzione. Completezza: Sì, se i costi sono finiti e non negativi. Ottimalità: Sì, trova sempre il percorso a costo minimo. Problemi della Ricerca a Costo Uniforme Ricorda: l'UCS esplora contorni di costo crescente. Il buono: l'UCS è completo e ottimale! Il cattivo: ○ Esplora opzioni in ogni "direzione". ○ Nessuna informazione sulla posizione dell'obiettivo. ○ Risolveremo questo problema a breve! L'Unica Coda Tutti questi algoritmi di ricerca sono uguali, tranne che per le strategie della frontiera: Concettualmente, tutti i bordi sono code di priorità (cioè collezioni di nodi con priorità associate). Praticamente, per DFS e BFS, puoi evitare l'overhead log(n) di una coda di priorità reale utilizzando pile e code. Puoi persino scrivere un'implementazione che utilizzi un oggetto di coda variabile. Strategie di Ricerca Informata (Euristica) p. 189 Questa sezione mostra come una strategia di ricerca informata — che utilizza suggerimenti specifici del dominio riguardanti la posizione degli obiettivi — possa trovare soluzioni in modo più efficiente rispetto a una strategia I suggerimenti arrivano sotto forma di una funzione euristica, non informata. indicata come: h(n)= costo stimato del percorso più economico dallo stato nel nodo n a uno stato obiettivo. Ad esempio, nei problemi di ricerca del percorso, possiamo stimare la distanza dallo stato attuale a un obiettivo calcolando la distanza in linea retta sulla mappa tra i due punti. Studiamo le euristiche e la loro origine in modo più dettagliato nella Sezione 3.6. 3.5.1 Ricerca migliore per prima (greedy best-first search) La ricerca migliore per prima è una forma di ricerca best-first che espande prima il nodo con il valore di h(n) più basso — il nodo che sembra più vicino all'obiettivo — basandosi sull'idea che questo conduca rapidamente a una soluzione. Quindi, la funzione di valutazione è f(n) = h(n). Vediamo come funziona questo metodo per i problemi di ricerca del percorso in Romania; usiamo l'euristica della distanza in linea retta, che chiameremo hSLD. Se l'obiettivo è Bucarest, dobbiamo conoscere le distanze in linea retta fino a Bucarest, che sono mostrate nella Figura 3.16. Ad esempio, hSLD(Arad) = 366. Notiamo che i valori di hSLD non possono essere calcolati dalla descrizione del problema stesso (cioè dalle funzioni ACTIONS e RESULT). Inoltre, ci vuole una certa conoscenza del mondo per sapere che questa distanza è correlata con le distanze effettive delle strade e che, quindi, è un'euristica utile. La Figura 3.17 mostra il progresso di una ricerca migliore per prima usando hSLD per trovare un percorso da Arad a Bucarest. Il primo nodo a essere espanso da Arad sarà Sibiu, perché l'euristica dice che è più vicino a Bucarest rispetto a Zerind o Timisoara. Il nodo successivo sarà Făgăraș, perché ora è il più vicino secondo l'euristica. Făgăraș, a sua volta, genera Bucarest, che è l'obiettivo. Per questo problema specifico, greedy best-first search usando hSLD trova una soluzione senza espandere mai un nodo che non si trovi sul percorso di soluzione. Tuttavia, la soluzione trovata non ha un costo ottimale: il percorso attraverso Sibiu e Făgăraș fino a Bucarest è 32 miglia più lungo rispetto al percorso tramite Râmnicu Vâlcea e Pitești. Questo è il motivo per cui l'algoritmo è chiamato "greedy" (avido): a ogni iterazione cerca di avvicinarsi il più possibile all'obiettivo, ma questa avidità può portare a risultati peggiori rispetto a essere più cauti. La ricerca migliore per prima su grafi ( Greedy best-first graph search) è completa negli spazi di stati finiti, ma non in quelli infiniti. La complessità nel caso peggiore per tempo e spazio è O(|V|). Tuttavia, con una buona funzione euristica, la complessità può essere ridotta sostanzialmente, in certi problemi raggiungendo O(bm). Ricerca A* L'algoritmo di ricerca informata più comune è la ricerca A* (pronunciato "A-star"), una ricerca best-first che utilizza la seguente funzione di valutazione: f(n) = g(n) + h(n) dove g(n) è il costo del percorso dallo stato iniziale al nodo n, e h(n) è il costo stimato del percorso più economico da n a uno stato obiettivo. Quindi: f(n) = costo stimato del miglior percorso che continua da n fino a un obiettivo. Nella Figura 3.18, vediamo il progresso di una ricerca A* con l'obiettivo di raggiungere Bucarest.  I valori di g sono calcolati dai costi delle azioni in Figura 3.1, e i valori di hSLD sono forniti in Figura 3.16. Notiamo che Bucarest appare per la prima volta sulla frontiera al passo (e), ma non viene selezionata per l'espansione (e quindi non viene rilevata come soluzione) perché f = 450 non è il nodo a costo più basso sulla frontiera: quello sarebbe Pitești, con f = 417. Un altro modo di dirlo è che potrebbe esserci una soluzione tramite Pitești con un costo di 417, quindi l'algoritmo non si accontenta di una soluzione che costa 450. Al passo (f), un percorso diverso per Bucarest diventa ora il nodo a costo più basso, con f = 418, quindi viene selezionato e rilevato come soluzione ottimale. La ricerca A* è completa. Se A* è anche ottimale in termini di costo dipende da alcune proprietà dell'euristica. Una proprietà chiave è l'ammissibilità: un'euristica ammissibile è una che non sovrastima mai il costo per raggiungere un obiettivo (un'euristica ammissibile è quindi ottimista). Con un'euristica ammissibile, A* è ottimale in termini di costo, come possiamo dimostrare con una prova per contraddizione. Supponiamo che il percorso ottimale abbia un costo C*, ma l'algoritmo restituisca un percorso con costo C > C*. Allora ci deve essere un nodo n sul percorso ottimale che non è stato espanso (perché se tutti i nodi sul percorso ottimale fossero stati espansi, allora avremmo restituito quella soluzione ottimale). Usando la notazione g*(n) per indicare il costo del percorso ottimale dall'inizio fino a n, e h*(n) per indicare il costo del percorso ottimale da n all'obiettivo più vicino, otteniamo: g*(n) + h*(n) = C* (ma anche: f(n) ≤ C*). La prima e l'ultima affermazione formano una contraddizione, quindi la supposizione che l'algoritmo possa restituire un percorso subottimale deve essere sbagliata: deve essere che A* restituisce solo percorsi ottimali in termini di costo. Una proprietà leggermente più forte è chiamata consistenza. Un'euristica h(n) è consistente se, per ogni nodo n e ogni successore n' di n generato da un'azione a, si ha: h(n) ≤ c(n, a, n') + h(n'). Questa è una forma di disuguaglianza triangolare, che stabilisce che un lato di un triangolo non può essere più lungo della somma degli altri due lati (vedi Figura 3.19). Un esempio di euristica consistente è la distanza in linea retta che abbiamo utilizzato per arrivare a Bucarest. Ogni euristica consistente è anche ammissibile (ma non viceversa), quindi con un'euristica consistente, A* è ottimale in termini di costo. Inoltre, con un'euristica consistente, la prima volta che raggiungiamo uno stato, sarà su un percorso ottimale, quindi non dobbiamo mai aggiungere nuovamente uno stato alla frontiera, né dobbiamo modificare una voce nella lista dei raggiunti. Tuttavia, con un'euristica inconsistente, potremmo ritrovarci con percorsi multipli che raggiungono lo stesso stato, e se ciascun nuovo percorso ha un costo inferiore al precedente, finiremo per avere nodi multipli per quello stato nella frontiera, aumentando il costo in termini di tempo e spazio. Per questo motivo, alcune implementazioni di A* si assicurano di inserire uno stato nella frontiera solo una volta, e se viene trovato un percorso migliore per quello stato, tutti i successori dello stato vengono aggiornati (il che richiede che i nodi abbiano puntatori verso i figli oltre che verso i genitori). Queste complicazioni hanno portato molti implementatori a evitare euristiche inconsistenti, ma Felner et al. (2011) sostengono che gli effetti peggiori si verificano raramente nella pratica e non si dovrebbe aver paura delle euristiche inconsistenti. Con un'euristica non ammissibile, A* potrebbe o non potrebbe essere ottimale in termini di costo. Ci sono due casi in cui lo è: primo, se c'è anche solo un percorso ottimale in cui h(n) è ammissibile per tutti i nodi lungo il percorso, allora quel percorso verrà trovato, indipendentemente da ciò che l'euristica dice per gli stati fuori dal percorso. Secondo, se la soluzione ottimale ha un costo C* e la seconda migliore ha un costo C2, e se h(n) sovrastima alcuni costi, ma mai di più di C2 - C*, allora A* è garantito per restituire soluzioni ottimali in termini di costo. Search contours Un modo utile per visualizzare una ricerca è disegnare contorni nello spazio degli stati, proprio come i contorni in una mappa topografica. La Figura 3.20 ne mostra un esempio. All'interno del contorno etichettato con 400, tutti i nodi hanno f(n) = g(n) + h(n) ≤ 400, e così via. Poiché A* espande il nodo frontiera con il costo più basso, possiamo vedere che una ricerca A* si espande a partire dal nodo iniziale, aggiungendo nodi in bande concentriche di costo crescente. Con la ricerca a costo uniforme, abbiamo anch'essa dei contorni, ma basati sul costo g, non su g + h. I contorni della ricerca a costo uniforme saranno "circolari" intorno allo stato iniziale, espandendosi in tutte le direzioni senza preferenza verso l'obiettivo. Con la ricerca A* che utilizza una buona euristica, le bande g + h si allungheranno verso uno stato obiettivo (come in Figura 3.20) e si concentreranno sempre di più intorno a un percorso ottimale. È chiaro che, estendendo un percorso, i costi g sono monotoni: il costo del percorso aumenta sempre man mano che si avanza lungo un percorso, perché i costi delle azioni sono sempre positivi. Pertanto, si ottengono linee di contorno concentriche che non si incrociano, e se si scelgono delle linee abbastanza sottili, è possibile tracciare una linea tra due nodi su qualsiasi percorso. Tuttavia, non è ovvio se il costo f = g + h aumenterà in modo monotono. Estendendo un percorso da n a n', il costo va da g(n) + h(n) a g(n) + c(n, a, n') + h(n'). Annullando il termine g(n), vediamo che il costo del percorso aumenterà in modo monotono se e solo se h(n) ≤ c(n, a, n') + h(n'); in altre parole, se e solo se l'euristica è consistente. Tuttavia, un percorso potrebbe contribuire con diversi nodi consecutivi con lo stesso punteggio g(n) + h(n); questo accade ogni volta che la diminuzione di h è esattamente uguale al costo dell'azione appena intrapresa (ad esempio, in un problema a griglia, quando n si trova sulla stessa riga dell'obiettivo e si fa un passo verso di esso, g aumenta di 1 e h diminuisce di 1). Se C* è il costo del percorso di soluzione ottimale, possiamo dire quanto segue: A* espande tutti i nodi raggiungibili dallo stato iniziale su un percorso in cui ogni nodo ha f(n) < C*. Chiamiamo questi "nodi sicuramente espansi". A* potrebbe quindi espandere alcuni nodi proprio sul "contorno dell'obiettivo" (dove f(n) = C*), prima di selezionare un nodo obiettivo. A non espande nodi con f(n) > C*. Diciamo che A con un'euristica consistente è ottimamente efficiente nel senso che qualsiasi algoritmo che estende i percorsi di ricerca dallo stato iniziale e utilizza le stesse informazioni euristiche deve espandere tutti i nodi che sono sicuramente espansi da A (perché ognuno di essi potrebbe far parte di una soluzione ottimale). Tra i nodi con f(n) = C*, un algoritmo potrebbe essere fortunato e scegliere subito quello ottimale, mentre un altro potrebbe essere sfortunato; non consideriamo questa differenza nella definizione di efficienza ottimale. A* è efficiente perché elimina i nodi dell'albero di ricerca non necessari per trovare una soluzione ottimale. Nella Figura 3.18(b) vediamo che Timișoara ha f = 449 e Zerind ha f = 447. Anche se sono figli della radice e sarebbero tra i primi nodi espansi dalla ricerca a costo uniforme o dalla ricerca in ampiezza, non vengono mai espansi dalla ricerca A* perché la soluzione con f = 418 viene trovata per prima. Il concetto di potatura—eliminare possibilità dalla considerazione senza doverle esaminare—è importante in molte aree dell'IA. Il fatto che la ricerca A* sia completa, ottimale in termini di costo e ottimamente efficiente tra tutti questi algoritmi è piuttosto soddisfacente. Sfortunatamente, ciò non significa che A* sia la soluzione a tutti i nostri problemi di ricerca. Il problema è che per molti problemi, il numero di nodi espansi può essere esponenziale rispetto alla lunghezza della soluzione. Ad esempio, consideriamo una versione del mondo dell'aspirapolvere con un aspirapolvere super-potente che può pulire qualsiasi quadrato con un costo di 1 unità, senza dover nemmeno visitare il quadrato; in questo scenario, i quadrati possono essere puliti in qualsiasi ordine. Con N quadrati inizialmente sporchi, ci sono 2^N stati in cui un sottoinsieme è stato pulito; tutti questi stati si trovano su un percorso di soluzione ottimale, e quindi soddisfano f(n) < C*, quindi tutti verrebbero visitati da A*. Ricerca Satisficing: euristiche inadmissibili e Weighted A* La ricerca A* ha molte qualità positive, ma espande molti nodi. Possiamo esplorare meno nodi (impiegando meno tempo e spazio) se siamo disposti ad accettare soluzioni subottimali, ma "abbastanza buone"—quelle che chiamiamo soluzioni satisficing. Se permettiamo alla ricerca A* di usare un'euristica inadmissibile—una che può sovrastimare—rischiamo di perdere la soluzione ottimale, ma l'euristica potrebbe essere più accurata, riducendo così il numero di nodi espansi. Ad esempio, gli ingegneri stradali conoscono il concetto di "indice di deviazione", un moltiplicatore applicato alla distanza in linea retta per tenere conto della curvatura tipica delle strade. Un indice di deviazione di 1.3 significa che se due città sono distanti 10 miglia in linea retta, una buona stima del miglior percorso tra loro è di 13 miglia. Nella maggior parte delle località, l'indice di deviazione varia tra 1.2 e 1.6. Possiamo applicare questa idea a qualsiasi problema, non solo a quelli che riguardano le strade, con un approccio chiamato ricerca A ponderata* ( weighted A* search), dove ponderiamo maggiormente il valore euristico, ottenendo la funzione di valutazione f(n) = g(n) + W × h(n), per un certo W > 1. La Figura 3.21 mostra un problema di ricerca in un mondo a griglia. In (a), una ricerca A* trova la soluzione ottimale, ma deve esplorare gran parte dello spazio degli stati per trovarla. In (b), una ricerca A* ponderata trova una soluzione leggermente più costosa, ma il tempo di ricerca è molto più rapido. Vediamo che la ricerca ponderata concentra il contorno degli stati raggiunti verso un obiettivo. Questo significa che vengono esplorati meno stati, ma se il percorso ottimale si trova al di fuori del contorno della ricerca ponderata (come in questo caso), allora non verrà trovato il percorso ottimale. In generale, se la soluzione ottimale costa C*, una ricerca ponderata A* troverà una soluzione che costa da qualche parte tra C* e W x C*, ma in pratica di solito otteniamo risultati molto più vicini a C* che a W x C* Abbiamo considerato ricerche che valutano gli stati combinando g e h in vari modi; la ricerca A* pesata può essere vista come una generalizzazione delle altre: Ricerca A*: g(n) + h(n) (W =1) Ricerca a costo uniforme: g(n) (W =0) Ricerca migliore-greedy: h(n) (W =∞) Ricerca A pesata*: g(n) + W × h(n) (1 < W < ∞) Potremmo chiamare la ricerca A* pesata una "ricerca alquanto-greedy": come la ricerca migliore-greedy, essa orienta la ricerca verso un obiettivo; d'altra parte, non ignorerà completamente il costo del percorso e sospenderà un percorso che sta facendo pochi progressi a un costo elevato. Esistono una varietà di algoritmi di ricerca subottimali, che possono essere caratterizzati dai criteri di ciò che è considerato “abbastanza buono”. Nella ricerca subottimale limitata, cerchiamo una soluzione che sia garantita entro un fattore costante W rispetto al costo ottimale. La ricerca A* pesata fornisce questa garanzia. Nella ricerca a costo limitato, cerchiamo una soluzione il cui costo sia inferiore a una costante C. Nella ricerca a costo illimitato, accettiamo una soluzione di qualsiasi costo, purché la troviamo rapidamente. Un esempio di un algoritmo di ricerca a costo illimitato è la "ricerca rapida" (speedy search), che è una versione della ricerca migliore-greedy che utilizza come euristica il numero stimato di azioni richieste per raggiungere un obiettivo, indipendentemente dal costo di tali azioni. Pertanto, per problemi in cui tutte le azioni hanno lo stesso costo, essa equivale alla ricerca migliore-greedy, ma quando le azioni hanno costi diversi, tende a portare la ricerca a trovare una soluzione rapidamente, anche se potrebbe avere un costo elevato. Ricerca con vincoli di memoria Il problema principale della ricerca A* è l'uso della memoria. In questa sezione, tratteremo alcuni trucchi di implementazione che permettono di risparmiare spazio e, successivamente, alcuni algoritmi completamente nuovi che sfruttano meglio lo spazio disponibile. La memoria è suddivisa tra il frontiera e gli stati raggiunti. Nella nostra implementazione della best first search, uno stato che è nella frontiera è memorizzato in due luoghi: come nodo nella frontiera (per decidere quale espandere successivamente) e come voce nella tabella degli stati raggiunti (per sapere se abbiamo già visitato lo stato). Per molti problemi (come esplorare una griglia), questa duplicazione non è un problema, perché la dimensione della frontiera è molto più piccola rispetto a quella degli stati raggiunti, quindi duplicare gli stati nella frontiera richiede una quantità di memoria relativamente irrilevante. Tuttavia, alcune implementazioni mantengono uno stato in uno solo dei due posti, risparmiando un po' di memoria, ma complicando (e forse rallentando) l'algoritmo. Un'altra possibilità è rimuovere gli stati dalla lista dei raggiunti quando possiamo dimostrare che non sono più necessari. Per alcuni problemi, possiamo usare la proprietà di separazione (Figura 3.6, pagina 72), insieme al divieto di azioni a U-turn, per garantire che tutte le azioni spostino verso l'esterno dalla frontiera o su un altro stato della frontiera. In questo caso, è necessario controllare solo la frontiera per percorsi ridondanti, e possiamo eliminare la tabella degli stati raggiunti. Per altri problemi, possiamo tenere un conteggio delle volte in cui uno stato è stato raggiunto, e rimuoverlo dalla tabella quando non ci sono più modi per raggiungerlo. Ad esempio, in un mondo a griglia in cui ogni stato può essere raggiunto solo dai suoi quattro vicini, una volta raggiunto uno stato quattro volte, possiamo rimuoverlo dalla tabella. Nuovi algoritmi per risparmiare memoria La ricerca a fascio (Beam search) limita la dimensione della frontiera. Il metodo più semplice è mantenere solo i migliori k nodi con i punteggi f più alti, scartando tutti gli altri nodi espansi. Questo rende ovviamente la ricerca incompleta e subottimale, ma possiamo scegliere k per fare un buon uso della memoria disponibile, e l'algoritmo si esegue velocemente perché espande meno nodi. Per molti problemi, può trovare buone soluzioni quasi ottimali. Si può pensare alla ricerca a costo uniforme o alla A* come a un'espansione a cerchi concentrici, mentre la ricerca a fascio esplora solo una porzione di quei cerchi, quella che contiene i k migliori candidati. Una versione alternativa della ricerca a fascio non mantiene un limite rigido sulla dimensione della frontiera, ma mantiene ogni nodo il cui punteggio f è entro δ dal miglior punteggio f. In questo modo, se ci sono pochi nodi con punteggi alti, ne verranno mantenuti solo alcuni, ma se non ci sono nodi forti, ne verranno mantenuti di più fino a quando emergerà un nodo forte. La Iterative-deepening A* search (IDA*) è per A* ciò che la ricerca iterativa-deepening è per la ricerca in profondità: IDA* ci dà i benefici di A* senza la necessità di mantenere tutti gli stati raggiunti in memoria, al costo di visitare più volte alcuni stati. È un algoritmo molto importante e comunemente usato per problemi che non rientrano nella memoria. Nella ricerca iterativa standard, il limite è la profondità, che viene aumentata di uno ad ogni iterazione. In IDA*, il limite è il costo f (g + h); a ogni iterazione, il valore limite è il costo f più piccolo di un nodo che ha superato il limite nell'iterazione precedente. In altre parole, ogni iterazione cerca esaustivamente un contorno f, trova un nodo appena oltre quel contorno e usa il costo f di quel nodo come prossimo contorno. La Recursive best-first search (RBFS) cerca di imitare il funzionamento della best-first search standard, ma usando solo uno spazio lineare. RBFS assomiglia a una ricerca in profondità ricorsiva, ma invece di continuare indefinitamente lungo il percorso corrente, usa la variabile f _limit per tenere traccia del valore f del miglior percorso alternativo disponibile da un antenato del nodo corrente. Se il nodo corrente supera questo limite, la ricorsione si interrompe tornando al percorso alternativo. RBFS è ottimale se la funzione euristica h(n) è ammissibile. ESEMPIO Fasi di una ricerca RBFS per il percorso più breve verso Bucarest. Il valore del limite f per ciascuna chiamata ricorsiva è mostrato sopra ogni nodo corrente, e ogni nodo è etichettato con il suo costo f. (a) Il percorso attraverso Rimnicu Vilcea viene seguito fino a quando la foglia corrente migliore (Pitesti) ha un valore peggiore rispetto al miglior percorso alternativo (Fagaras). (b) La ricorsione si interrompe e il valore della foglia migliore del sottoalbero dimenticato (417) viene ripristinato su Rimnicu Vilcea; quindi Fagaras viene espanso, rivelando un valore di foglia migliore pari a 450. (c) La ricorsione si interrompe e il valore della foglia migliore del sottoalbero dimenticato (450) viene ripristinato su Fagaras; quindi Rimnicu Vilcea viene espanso. Questa volta, poiché il miglior percorso alternativo (attraverso Timisoara) costa almeno 447, l'espansione prosegue fino a Bucarest. IDA* e RBFS soffrono di un utilizzo troppo limitato della memoria. Tra le iterazioni, IDA* conserva solo un singolo numero: il limite del costo f. RBFS conserva più informazioni in memoria, ma usa solo spazio lineare: anche se fosse disponibile più memoria, RBFS non avrebbe modo di utilizzarla. Poiché dimenticano la maggior parte di ciò che hanno fatto, entrambi gli algoritmi potrebbero finire per esplorare più volte gli stessi stati. Sembra quindi ragionevole determinare quanta memoria abbiamo a disposizione e consentire a un algoritmo di usarla tutta. Due algoritmi che fanno questo sono MA* (A* con vincolo di memoria) e SMA* (A* semplificato). SMA* procede esattamente come A*, espandendo il miglior nodo foglia fino a quando la memoria è piena. A questo punto, non può aggiungere un nuovo nodo all'albero di ricerca senza eliminarne uno vecchio. SMA* elimina sempre il nodo foglia peggiore, cioè quello con il valore f più alto. SMA* è completo se esiste una soluzione raggiungibile e ottimale se una soluzione ottimale è raggiungibile. Tuttavia, sui problemi molto difficili, SMA* potrebbe essere costretto a passare continuamente tra molti percorsi candidati alla soluzione, solo un piccolo sottoinsieme dei quali può entrare in memoria. Ciò rende il problema praticamente irrisolvibile in termini di tempo computazionale, anche se sarebbe risolvibile da A* con memoria illimitata.