Emanuele Aina

Algoritmi di ricerca nello spazio delle soluzioni

Introduzione

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.

Il gioco dell'otto

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.

1 2 3
4 5 6
7 8

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.

Le N regine

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.

. . .
. . .
. . x . . .
. . .
. . .
. .

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.

Gli algoritmi di ricerca

La ricerca in ampiezza

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

La ricerca in profondità

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

La ricerca lungo la pendenza massima (hill-climbing)

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*

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

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

Confronto tra gli algoritmi

Il gioco dell'otto

Algoritmo Tempo Soluzione trovata Nodi analizzati Nodi generati
Ampiezza 12.936 s 7800 11830
Profondità 12.812 s 6575 11809
Hill Climbing 0.676 s 693 1245
A* 0.720 s 747 1220
Ampiezza con potatura (β = 3) 0.946 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.

Il gioco dell'otto con euristica semplice

Algoritmo Tempo Soluzione trovata Nodi analizzati Nodi generati
Hill Climbing 22.466 s 9461 16155
A* 0.418 s 340 553
Ampiezza con potatura (β = 3) 0.687 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.

Il gioco delle regine

Algoritmo Tempo Soluzione trovata Nodi analizzati Nodi generati
Ampiezza 2.606 s 2631 2634
Profondità 0.155 s 250 318
Hill Climbing 0.306 s 321 385
A* 0.208 s 139 420
Ampiezza con potatura (β = 300) 6.746 s 944 1137
Ampiezza con potatura (β = 40) 1.537 s 164 185
Ampiezza con potatura (β = 39) 1.527 s 161 183
Ampiezza con potatura (β = 38) 1.492 s 158 178
Ampiezza con potatura (β = 37) 1.483 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.

Il gioco delle regine con euristica semplice

Algoritmo Tempo Soluzione trovata Nodi analizzati Nodi generati
Hill Climbing 0.793 s 1024 1071
A* 0.823 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.

Conclusioni

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:

Codice

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.

Riferimenti

Descrizione del gioco delle regine:
http://en.wikipedia.org/wiki/Eight_queens_puzzle
Introduzione ai problemi nello spazio degli stati:
http://www.murrayc.com/learning/AI/statespace.shtml
Descrizione della ricerca in ampiezza:
http://en.wikipedia.org/wiki/Breadth-first_search
Descrizione della ricerca in profondità:
http://en.wikipedia.org/wiki/Depth-first_search
Implementazione di A* in python:
http://arainyday.se/projects/python/AStar/
Implementazione in python degli algoritmi usati nel libro AI: A Modern Approach di Stuart Russel e Peter Norvig:
http://aima.cs.berkeley.edu/python/readme.html
Esempi di funzionamento di A*:
http://www.geocities.com/jheyesjones/astar.html
Implementazione di una metaclasse MultiSingleton:
http://groups.google.com/group/comp.lang.python/browse_thread/thread/...