Alcuni dei problemi più comuni risolvibili con l'uso dell'Intelligenza Artificiale consistono nel ricercare un percorso da uno stato di partenza a uno stato finale "goal", muovendosi all'interno di uno spazio di ricerca costituito dall'insieme degli stati del problema stesso.
Esistono diverse procedure per risolvere questa categoria di problemi, ognuna con pregi e difetti da valutare in funzione del problema in esame, in quanto spesso quello che può essere un vantaggio cambiando i vincoli può diventare uno svantaggio. È pertanto necessario conoscere approfonditamente le caratteristiche di ognuno degli algoritmi di ricerca delle soluzioni, in modo da saper scegliere correttamente quello più adatto al problema preso in considerazione.
La formulazione di un problema in modo che possa essere risolto efficientemente nello spazio degli stati richiede sopratutto una corretta rappresentazione degli stati stessi e la definizione di operatori in grado di agire sugli stati per produrne di nuovi.
Alcune tecniche più avanzate di risoluzione richiedono inoltre un metodo di valutazione della bontà di ogni stato, in modo da poter scegliere quelli più promettenti nel corso della ricerca.
Un esempio di problema è la soluzione del gioco dell'otto, dove si hanno otto tessere scorrevoli numerate in una griglia 3×3. Le tessere possono scorrere nelle quattro direzioni (su, giù, destra e sinistra) ma solo se vanno ad occupare la posizione lasciata vuota. Lo scopo è quello di ordinare le tessere, lasciando lo spazio vuoto in fondo.
Stato finale del gioco dell'otto
Pur esistendo 9! = 362880 possibili disposizioni dei numeri nelle caselle, gli stati raggiungibili usando gli operatori consentiti sono 181433, ovvero circa la metà, e solo uno di questi è quello vincente.
Ogni stato è rappresentato da una matrice contenente i numeri relativi alle otto tessere, con lo zero che rappresenta lo spazio libero.
Gli operatori per generare gli stati successivi sono i movimenti orizzontali e verticali (su, giù, destra, sinistra) ma, per semplicità sono stati applicati alla casella vuota invece che alle tessere.
Per valutare gli stati si usano due euristiche differenti: la prima, più semplice, prevede semplicemente di conteggiare il numero di tessere fuori posto, mentre la seconda associa un peso a ciascuna casella pari alla somma delle coordinate, privilegiando la sistemazione delle tessere in alto a sinistra.
Un problema differente è dato dalla ricerca di soluzioni per il gioco delle regine, in cui si dispongono N regine su una scacchiera N×N facendo in modo che queste non si mangino l'una con l'altra e tenendo presente che le regine dominano in orizzontale, verticale e lungo le diagonali.
Dominio di una regina sulla scacchiera
Anche se il problema viene normalmente affrontato su di una tradizionale scacchiera 8×8, per velocizzare i calcoli lo si considera su una scacchiera ridotta 6×6, passando così da 118955 stati possibili a 2635 e da 92 stati vincenti a solamente 4.
Gli stati, oltre a essere rappresentati da una lista contenente
le coordinate delle regine già posizionate, dispongono anche di
quattro indici che contengono l'elenco, rispettivamente, delle righe,
delle colonne, delle diagonali decrescenti e di quelle crescenti dominate
da una qualsiasi regina già posizionata sulla scacchiera.
Ponendo una regina in posizione (x, y) questa dominerà tutte
le caselle lungo la riga x, la colonna y, la
diagonale decrescente x-y e lungo quella crescente
x+y.
L'unico operatore disponibile è il posizionamento di una regina in una qualsiasi casella non dominata da una regina già presente.
L'euristica più semplice tra quelle usate è un banale conteggio delle caselle libere. Quella più raffinata, invece, prevede che ogni casella ottenga un punteggio tra 0 e 1 a seconda del fatto di trovarsi lungo una colonna occupata, una riga occupata, una diagonale occupata o lungo nessuna di esse. Il risultato, che tenderebbe a privilegiare gli stati con il minor numero di regine posizionate, viene compensato sottraendovi il numero di regine sulla scacchiera moltiplicato per la sua dimensione.
L'algoritmo di ricerca in ampiezza non è altro che una visita in ampiezza dell'albero degli stati generati: dallo stato iniziale si genera e si visita ogni figlio, per poi passare ai figli dei figli e così via.
Inizializzazione:
OPEN = [] OPEN.append(initial_state) CLOSED = []
L'algoritmo:
while True: if not OPEN: return None n = OPEN.pop(0) if n.is_goal(): return get_track(n) CLOSED.append(n) successors = n.generate() successors = [s for s in successors if s not in CLOSED] successors = [s for s in successors if s not in OPEN] for s in successors: set_parent(s, n) OPEN += successors
L'algoritmo di ricerca in profondità, invece, è una semplice visita in profondità dell'albero degli stati generati: dallo stato iniziale si generano i figli e se ne visita il primo. Da qui si generano i figli del primo figlio, visitandone il primo fino a che non ci siano più figli: a tal punto si risale e si visita il primo fratello non visitato, fino a che non siano stati visitati tutti gli stati o sia stata trovata la soluzione.
Inizializzazione:
OPEN = [] OPEN.append(initial_state) CLOSED = []
L'algoritmo:
while True: if not OPEN: return None n = OPEN.pop() if n.is_goal(): return get_track(n) CLOSED.append(n) successors = n.generate() successors = [s for s in successors if s not in CLOSED] successors = [s for s in successors if s not in OPEN] for s in successors: set_parent(s, n) OPEN += successors
Questo tipo di ricerca è del tutto analoga a una ricerca in profondità, ordinando però gli stati in base all'euristica fornita dal problema, quindi privilegiando quelli più promettenti.
Inizializzazione:
OPEN = [] OPEN.append(initial_state) CLOSED = []
L'algoritmo:
while True: if not OPEN: return None n = OPEN.pop() if n.is_goal(): return get_track(n) CLOSED.append(n) successors = n.generate() successors = [s for s in successors if s not in CLOSED] successors = [s for s in successors if s not in OPEN] successors.sort(lambda a,b: -cmp(a.heuristics(), b.heuristics())) for s in successors: set_parent(s, n) OPEN += successors
L'algoritmo A* è un algoritmo pensato per la ricerca su grafi pesati tenendo in considerazione i costi specificati su ogni arco del grafo e un'euristica che stimi la distanza del nodo corrente dalla destinazione.
In questo caso l'algoritmo è stato leggermente modificato per poter essere impiegato per trovare soluzioni nello spazio degli stati assumendo che il costo del passaggio da genitore a figlio sia unitario.
Come ottimizzazione, per OPEN è stata utilizzata una
coda di priorità invece di una lista, in quanto l'interesse è quello
di estrarne sempre l'elemento con il costo minore.
Inizializzazione:
OPEN = PQueue()
CLOSED = []
G = {}
G[initial_state] = 0
OPEN.add(initial_state, key=lambda x: 0)
L'algoritmo:
while True: if not OPEN: return None def f(node): return G[node] + node.heuristics() n = OPEN.pop() if n.is_goal(): return get_track(n) CLOSED.append(n) successors = n.generate() successors = [s for s in successors if s not in CLOSED] successors = [s for s in successors if s not in OPEN] for s in successors: set_parent(s, n) G[s] = G[n] + 1 OPEN.add(s, key=f)
La ricerca in ampiezza con potatura cerca di minimizzare l'esplosione esponenziale di stati in memoria che avverrebbe in una semplice ricerca in ampiezza, scartando quelli meno promettenti in base all'euristica usata.
Inizializzazione:
OPEN = [] OPEN.append(initial_state) RESERVE = [] CLOSED = []
L'algoritmo:
while True: if not OPEN: if not RESERVE: return None else: RESERVE.sort(lambda a, b: cmp(a.heuristics(), b.heuristics())) OPEN = RESERVE[:beta] + OPEN RESERVE = [] n = OPEN.pop(0) if n.is_goal(): return get_track(n) CLOSED.append(n) successors = n.generate() successors = [s for s in successors if s not in CLOSED] successors = [s for s in successors if s not in OPEN] for s in successors: set_parent(s, n) if s.is_goal(): return get_track(s) RESERVE += successors
| Algoritmo | Tempo | Soluzione trovata | Nodi analizzati | Nodi generati |
|---|---|---|---|---|
| Ampiezza | 12.936 s | sì | 7800 | 11830 |
| Profondità | 12.812 s | sì | 6575 | 11809 |
| Hill Climbing | 0.676 s | sì | 693 | 1245 |
| A* | 0.720 s | sì | 747 | 1220 |
| Ampiezza con potatura (β = 3) | 0.946 s | sì | 988 | 990 |
| Ampiezza con potatura (β = 2) | 0.435 s | no | 495 | 495 |
Dal momento che la generazione degli stati avviene semplicemente muovendo lo spazio libero in una delle quattro direzioni, non esiste una vera e propria differenza tra ricerca in profondità e ampiezza in termini di prestazioni, sia come tempistiche che come numnero di stati generati e analizzati. L'unica vera differenza è che la ricerca in ampiezza troverà sempre la soluzione con il numero minimo di mosse, mentre quella in profondità tende a presentare soluzioni molto complesse.
L'impiego di algoritmi informati migliora le prestazione di almeno un ordine di grandezza, riducendo i tempi al di sotto del secondo e diminuendo di un fattore 10 il numero di stati generati e visitati.
Le prestazioni di A* e Hill Climbing sono pressoché identiche, con A* in grado di generare meno nodi (occupando quindi meno memoria) e Hill Climbing capace di trovare la soluzione analizzando meno stati (riducendo il tempo impiegato).
Grazie alla potatura la ricerca in ampiezza con potatura è l'algoritmo con l'uso di memoria minore, conservando il minor numero di stati tra gli algoritmi provati. Ciò nonostante le sue prestazioni in termini di stati analizzati sono peggiori di A* e Hill Climbing. Si nota, inoltre, come un parametro β troppo piccolo possa potare eccessivamente l'albero di ricerca, tagliando i rami che portano alla soluzione.
| Algoritmo | Tempo | Soluzione trovata | Nodi analizzati | Nodi generati |
|---|---|---|---|---|
| Hill Climbing | 22.466 s | sì | 9461 | 16155 |
| A* | 0.418 s | sì | 340 | 553 |
| Ampiezza con potatura (β = 3) | 0.687 s | sì | 745 | 747 |
| Ampiezza con potatura (β = 2) | 1.328 s | no | 1364 | 1364 |
Impiegando una euristica più semplice Hill Climbing soffre particolarmente, presentando un rallentamento di quasi due ordini di grandezza, divenendo più lento e ingombrante persino degli algoritmi non informati. A*, al contrario, sembra beneficiare dell'euristica meno raffinata, migliorando i suoi risultati sia in termini di occupazione di memoria, sia di tempo.
Analogamente ad A*, anche la ricerca in ampiezza con potatura con β pari a 3 migliora i propri risultati, ma in misura minore. Con β pari a 2, invece, il numero di stati visitati prima di determinare che la soluzione non può essere trovata è quasi tre volte quello riscontrato precedentemente.
| Algoritmo | Tempo | Soluzione trovata | Nodi analizzati | Nodi generati |
|---|---|---|---|---|
| Ampiezza | 2.606 s | sì | 2631 | 2634 |
| Profondità | 0.155 s | sì | 250 | 318 |
| Hill Climbing | 0.306 s | sì | 321 | 385 |
| A* | 0.208 s | sì | 139 | 420 |
| Ampiezza con potatura (β = 300) | 6.746 s | sì | 944 | 1137 |
| Ampiezza con potatura (β = 40) | 1.537 s | sì | 164 | 185 |
| Ampiezza con potatura (β = 39) | 1.527 s | sì | 161 | 183 |
| Ampiezza con potatura (β = 38) | 1.492 s | sì | 158 | 178 |
| Ampiezza con potatura (β = 37) | 1.483 s | sì | 155 | 175 |
| Ampiezza con potatura (β = 36) | 1.450 s | no | 171 | 171 |
| Ampiezza con potatura (β = 35) | 1.424 s | no | 166 | 166 |
Poiché tutte le soluzioni possibili sono situate alla profondità massima del problema, la ricerca in ampiezza è fortemente svantaggiata, in quanto si trova nel caso peggiore e dovrà quindi analizzare prima tutti gli stati a profondità minore, i quali non potranno mai essere soluzione. Viceversa la ricerca in profondità tende a comportarsi in modo ottimale, muovendosi velocemente verso la soluzione.
Hill Climbing, pur generando un numero di stati molto vicino a quello della ricerca in profondità, ne analizza circa il 30% in più e, pertanto, risulta essere più lento.
A* è decisamente il migliore in termini di nodi analizzati, pur generando più nodi di Hill Climbing. Le tempistiche più alte rispetto alla ricerca in profondità sono da imputare alla maggiore semplicità algoritmica di quest'ultimo.
Usando un β molto alto (300) la potatura riduce in modo poco significativo il numero di stati in memoria rispetto alla semplice ricerca in ampiezza. Dal momento che la potatura richiede un ordinamento della lista degli stati a ogni iterazione le prestazioni sono le peggiori tra gli algoritmi provati.
Con valori β più piccoli si hanno le migliori prestazioni in termini di occupazione di memoria, ma l'uso dell'ordinamento a ogni iterazione mantiene le tempistiche abbastanza alte. Bisogna anche stare molto attenti, in quanto ridurre eccessivamente β non permette di trovare la soluzione.
| Algoritmo | Tempo | Soluzione trovata | Nodi analizzati | Nodi generati |
|---|---|---|---|---|
| Hill Climbing | 0.793 s | sì | 1024 | 1071 |
| A* | 0.823 s | sì | 1082 | 1131 |
| Ampiezza con potatura (β = 300) | 2.940 s | no | 1149 | 1149 |
| Ampiezza con potatura (β = 40) | 0.802 s | no | 181 | 181 |
| Ampiezza con potatura (β = 39) | 0.803 s | no | 178 | 178 |
| Ampiezza con potatura (β = 38) | 0.797 s | no | 174 | 174 |
| Ampiezza con potatura (β = 37) | 0.794 s | no | 170 | 170 |
| Ampiezza con potatura (β = 36) | 0.781 s | no | 167 | 167 |
| Ampiezza con potatura (β = 35) | 0.763 s | no | 163 | 163 |
Nel caso del problema delle N regine sono più evidenti i benefici di una euristica raffinata: sia A* che Hill Climbing presentano notevoli perdite prestazionali, sia in termini di memoria che di stati analizzati, dalle tre alle dieci volte peggiori.
Si nota, inoltre, come l'euristica sia fondamentale per le strategie incomplete come la ricerca con potatura: in questo caso, anche con β molto grandi la soluzione non viene affatto trovata.
Come in molti altri settori, anche nell'Intelligenza Artificiale non esistono algoritmi generalmente ottimi, ma l'efficienza della soluzione di un problema dipende da alcuni fattori:
Dal momento che gli algoritmi informati sono solitamente più complessi, per alcuni problemi è più efficiente l'utilizzo di algoritmi non informati, come nel caso del problema delle regine, in cui la scenta più conveniente era quella della semplice ricerca in profondità. Più in generale, grazie alla maggior conoscenza del problema, gli algoritmi informati hanno prestazioni notevolmente più elevate, con miglioramenti spesso di una o più grandezze sia in termini di memoria che di tempo.
La rappresentazione del problema e la scelta degli operatori in particolare influenzano fortemente il comportamento degli algoritmi: sempre nel caso del problema delle regine è soprattutto la formulazione dell'operatore usato per la generazione degli stati a favorire la ricerca in profondità rispetto agli altri algoritmi.
Nel caso si scelga di impiegare algoritmi informati è necessario fornire loro un'euristica in grado di guidarli efficientemente. Purtroppo differenti algoritmi rispondono diversamente alle euristiche, per cui è spesso difficile identificare quelle più convenienti, come è evidente nel caso del gioco dell'otto, in cui A* predilige l'euristica meno raffinata, la stessa con la quale le prestazioni di Hill Climbing decadono di quasi due ordini di grandezza.
Dopo aver affrontato la decisione tra algoritmi informati e non informati è necessario decidere quale sarà l'algoritmo effettivamente impiegato: se la soluzione deve essere trovata entro un certo tempo e non oltre è possibile usare tecniche incomplete, ma in generale la scelta può variare molto in base al problema ed è difficile, se non impossibile, effettuare la decisione senza indicazioni date da prove pratiche.
L'archivio con il codice python utilizzato per descrivere e risolvere i problemi e per raccogliere i dati per l'analisi è disponibile presso http://techn.ocracy.org/ai.
AI: A Modern Approachdi Stuart Russel e Peter Norvig: