Problem Solving

Intelligenza Artificiale
Simbolica
m. ernandes, e. trentin
Problem Solving
Introduzione
Intelligenza Artificiale Problem Solving
2/102
“Risolvere problemi”
E’ uno dei processi intellettivi che secondo il
Comportamentismo richiede e definisce
l’“attività intellettuale”.
1.
2.
3.
4.
Induzione
(Apprendimento)
Sussunzione
(Riconoscimento)
Ragionamento
(Deduzione)
Problem Solving (implica tutte le precedenti)
Approccio comportamentista: Test di Turing
Intelligenza Artificiale Problem Solving
3/102
“Come” costruire un Problem Solver ?
Approccio Human-oriented (cognitivista)


Deve SIMULARE l’attività intelligente
Risolvere problemi “pensando come un uomo”
Approccio Machine-oriented (comport.)


Deve MANIFESTARE attività intelligente
Risolvere i problemi al meglio
Intelligenza Artificiale Problem Solving
4/102
Approccio Machine-Oriented
Problem Solver che MANIFESTA intelligenza

Algoritmi di Ricerca
Problem Solving = ricerca nello spazio degli stati.


Perchè?
PS = Hard Computing
Il bias della “potenza di calcolo”:


Con calcolatori sufficientemente potenti si può “attaccare”
ogni tipo di problema.
Falso: l'esplosione combinatoria rende futile la forza bruta
Intelligenza Artificiale Problem Solving
5/102
Cosa è un problema? (I)
“Problema” è un concetto non definibile, solo
esemplificabile. (Nilsson, 1982)
Alcuni esempi:
I puzzle “da tavola”  in genere NP
 “Commesso viaggiatore”
 Rompicapo come il Cubo di Rubik
 SAT, Dimostrazione teoremi
 Giochi (Dama, Scacchi, etc.)
 VLSI
Intelligenza Artificiale Problem Solving

6/102
Cosa è un problema? (II)
Formalizzazione:

5-tupla di elementi:
3
7
6
1
5
2
4
8
P={X,SCS,x0,g,t}
1
2
3
4
5
6
7
8
Formalizzare = astrarre un problema
Intelligenza Artificiale Problem Solving
7/102
Problem Solving
Ricerca nello spazio degli stati
“Blind” Search
Intelligenza Artificiale Problem Solving
8/102
Grafi e strategie
Spazio degli Stati
X
Spazio della Ricerca  (SCS(SCS(…(x0)…)))


Alberi
Nodi
Cosa vuol dire trovare una soluzione?
Cosa è una strategia di ricerca?
Intelligenza Artificiale Problem Solving
9/102
Valutare le strategie
4 criteri fondamentali:

Completezza

Ottimalità

Complessità Spaziale

Complessità Temporale
Le “regole d’oro” di J.Pearl (1984)
Non dimenticarsi di cercare sotto ogni pietra
 Non alzare due volte la stessa
Intelligenza Artificiale Problem Solving
10/102

Ricerca Cieca
Come espandere un nodo?
Coda dei nodi aperti:
CODA.insert(node);
 node = CODA.remove();

L’ordinamento dei nodi in CODA
determina la strategia di ricerca
Intelligenza Artificiale Problem Solving
11/102
Algoritmo Generale di Search
Struttura Generale
1. if (goal_test(x0)== true) return SUCCESS
2. else CODA.insert(x0)
3. do {
if (CODA.isEmpty()) return FAILURE
nodo = CODA.remove()
figli[] = SCS(nodo)
CODA.insert(figli)
} while( goal_test(nodo)== false )
4. return SUCCESS
Intelligenza Artificiale Problem Solving
12/102
“Breadth First”
Ricerca in Ampiezza
Usa una memoria FIFO
E’ un algoritmo “difensivo”
E’ completo e ottimale
Complessità spaziale: O(bd)
Complessità temporale: O(bd)
Intelligenza Artificiale Problem Solving
13/102
“Breadth First” - simulazione
GOAL
Intelligenza Artificiale Problem Solving
14/102
Alcuni numeri
depth
N° nodi
Tempo
Memoria
2
111
1 msec
11 KB
4
11111
0,1 sec
1 MB
6
>106
10 sec
>100 MB
8
>108
17 min
>10 GB
10
>1010
28 ore
>1 TB
12
>1012
116 giorni
>100 TB
14 b =10, velocità
>1014 ricerca =32
TB
100anni
mila nodi/sec.,>10000
100 byte/nodo
Korf: dagli anni ’60 la velocità di ricerca è cresciuta di 2 x 106.
Quasi il 50% del contributo va ai miglioramenti algoritmici.
Intelligenza Artificiale Problem Solving
15/102
“Depth First”
Ricerca in Profondità
Usa una memoria LIFO
E’ un algoritmo “aggressivo”
E’ non completo e non ottimale
Complessità temporale: O(bd)
Complessità spaziale: O(db)
Intelligenza Artificiale Problem Solving
16/102
“Depth First” - simulazione
GOAL
Intelligenza Artificiale Problem Solving
backtracking
17/102
Come migliorarli?
Conoscendo lo stato goal
Non ripetendo gli stati


Evitando di espandere lo stato di provenienza
 Evitando i cicli
In generale: evitando di generare nodi con stati già
visitati nella ricerca
Conoscendo il costo degli operatori
Intelligenza Artificiale Problem Solving
18/102
Ricerca Bidirezionale
(sfruttare la conoscenza dello stato goal)
Ricerca in Ampiezza


Dallo stato iniziale verso il goal
Dal goal verso lo stato iniziale
Quando termina?
Perché non usare 2 “depth first”?
E’ completa e ottimale
Complessità spaziale: O(bd/2)
Complessità temporale: O(bd/2)
Intelligenza Artificiale Problem Solving
19/102
Ricerca Bidirezionale - Simulazione
GOAL
X0
Intelligenza Artificiale Problem Solving
20/102
Ricerca a profondità limitata
(evitare di cadere in loop infiniti)
Ricerca in profondità


Si stabilisce una profondità massima l
Se la coda è vuota al raggiungimento di l si ritorna un
fallimento
Non è completa (se l<d) né ottimale
Complessità spaziale: O(bl)
Complessità temporale: O(bl)
PRO: evita loop infiniti senza usare memoria!
CON: richiede conoscenza a priori del problema
Intelligenza Artificiale Problem Solving
21/102
Iterative Deepening Search
(evitare di cadere in loop infiniti)
Ricerca a profondità limitata


Passo 1: l = 0
Passo 2:


si applica la ricerca a profondità limitata partendo da X0
se la coda è vuota al raggiungimento di l si reitera il passo 2
aumentando l
bd(b/(b-1))2
E’ ottimale e completa
Complex. temporale: (d+1)1 + (d)b + (d-1)b2 + … + (1)bd = O(bd)
Complex. spaziale: O(bd)
CONTRO: si espandono più volte gli stessi stati.
Intelligenza Artificiale Problem Solving
22/102
Iterative Deepening - sim
Iterazione: 0
Intelligenza Artificiale Problem Solving
23/102
Iterative Deepening - sim
Iterazione: 1
Intelligenza Artificiale Problem Solving
24/102
Iterative Deepening - sim
Iterazione: 2
Intelligenza Artificiale Problem Solving
25/102
Iterative Deepening - sim
Iterazione: 3
GOAL
Intelligenza Artificiale Problem Solving
26/102
Ricerca a costo uniforme
(sfruttare la conoscenza del costo degli operatori)
La “Breadth First” Search


minimizza il costo di cammino della soluzione se la funzione
di costo per ogni operatore è costante (es: 1)
funzione di costo: g(n)
La “Uniform-Cost” Search




minimizza il costo di cammino anche con operatori a costo
variabile (es: “commesso viaggiatore”)
Requisito: g(n) <= g(SCS(n)), cioè costo non negativo
Altrimenti non c’è strategia che tenga!
E’ completa e ottimale.
Intelligenza Artificiale Problem Solving
27/102
Ricerca a costo uniforme - Sim
4
6
2
2
1
4
8
6
6
5
2
6
4
3
5
1
5
6
2
GOAL
COSTO:
Intelligenza Artificiale Problem Solving
7
6
4
3
2
0
28/102
Problem Solving
Ricerca nello spazio degli stati
“Heuristic” Search
Intelligenza Artificiale Problem Solving
29/102
Cosa è un’euristica?
“Qualsiasi cosa” che serva di supporto in un
processo decisionale
E’ una conoscenza, magari imperfetta, del
dominio in cui ci troviamo
Un esempio reale: “la Carta di Mercatore”
Tipicamente nel Problem Solving:

Valutazione del costo di cammino futuro
Intelligenza Artificiale Problem Solving
30/102
Come usare un’euristica?
X0
g(n)
Actual State (n)
f(n)
h(n)
Goal State
Intelligenza Artificiale Problem Solving
31/102
Due Esempi di Euristiche
3
2
8
5
7
6
4
1
Tessere fuori posto
Distanza di Manhattan
hfp(n) = 5
hm(n) = 11
Intelligenza Artificiale Problem Solving
32/102

n
Proprietà generali delle Euristiche
Ammissibilità:

h(n) è ammissibile se h(n) ≤ h*(n)
Dominanza:

h2 domina h1 se h1(n) ≤ h2(n)
e h1 & h2 sono ammissibili
Intelligenza Artificiale Problem Solving
n
n
33/102
Proprietà generali delle Euristiche 2
n’
Consistenza:

h(n) è consistente se
h(n’)
c(n,n’)
n
h(n)
h
(
n
)

c
(
n
,'
n
)

h
(
n
'
)

(
n
,'
n
)
Monotonicità:

h(n) è monotona se
h
(
n
)

c
(
n
,
n
'
)(

h
n
'
)

n
|
n
'

S
C
S
(
n
)
Intelligenza Artificiale Problem Solving
34/102

Dim: consistenza = ammissibilità
1. Per def: h(n)  c(n,n’) + h(n’) (n,n’)
2. Allora possiamo sostituire n’ con un nodo risolvente 
3. quindi: h(n)  c(n,) + h()
4. h() = 0 e c(n,) = h*(n) per   * (percorso ottimo)
5. da 3 e 4 abbiamo che h(n)  h*(n)
Dim: monotonicità = consistenza
1. Per def: h(n)  c(n,n’) + h(n’)  n,n’  SCS(n)
2. e anche: h(n’)  c(n’,n’’) + h(n’’)  n’,n’’  SCS(n’)
3. ripetendo il punto 2 con: n’  n’’ e c(n,n’’)  c(n,n’) + c(n’,n’’)
rimane garantito che h(n)  c(n,n’’) + h(n’’)  n,n’’  SCS(…(SCS(n))…)
4. quindi: h(n)
 c(n,n’) -+ h(n’) (n,n’)
Intelligenza
Artificiale
Problem Solving
35/102
2
Esempi di Euristiche Ammissibili
3 7 4
6 1
5 8 2
A) Tessere Fuori Posto
B) Distanza di Manhattan
C) h3=hfp+ hm  non è ammissibile!
Navigazione Robot tra ostacoli
h(n) = Distanza in linea retta
(se il costo degli step è 1 per
movimento ortogonale e 2 per
movimento diagonale)
Intelligenza Artificiale Problem Solving
36/102
Euristica di Manhattan
Somma delle distanze ortogonali delle parti (le tessere
nel Puzzle di Sam-Loyd) dalle loro posizioni nel goal
state.
E’ ammissibile
E’ monotona.
Rispetta la parità di h*(n)
E’ pienamente informata quando siamo vicini
all’obiettivo
Intelligenza Artificiale Problem Solving
37/102
Algoritmi di Ricerca Euristica
Hill-Climbing
Best-First Search



Algoritmi Greedy
Algoritmi A*
Algoritmo Generale: WA*
Memory Bounded Search

IDA*, SMA*
Ricerca a miglioramenti Iterativi

Simulated Annealing
Intelligenza Artificiale Problem Solving
38/102
Hill-Climbing Search
Si usa unicamente la funzione euristica
Non c’è backtracking
Non si usa memoria
4
5
4
Non è ottimale
Non è completo

Minimi locali
3
3
5
0
GOAL
Intelligenza Artificiale Problem Solving
39/102
Best-First Ottimale: A*
(Hart, Nilsson and Raphael, 1968)
A* = un nome ambizioso
Funzione di valutazione  f(n)=g(n)+h(n)
Caratteristiche:
 Ottimale
 Completo
 Complex time & space: O(bd)
 Ottimamente efficiente
Intelligenza Artificiale Problem Solving
40/102
Algoritmo A*
1. if (goal_test(x0)== true) return SUCCESS
2. else OPEN.insert(x0, g(x0)+h(x0) )
3. do {
if (OPEN.isEmpty()) return FAILURE
nodo = OPEN.remove()
CLOSED.insert(nodo)
figli[] = SCS(nodo)
for all figli{
if (!CLOSED.contains(figlio))
OPEN.insert(figlio, g(figlio)+h(figlio))
}
} while( goal_test(nodo)== false )
4. return SUCCESS
Intelligenza Artificiale Problem Solving
41/102
Dimostrazioni
A* è un algoritmo ottimale
A* è un algoritmo completo
Intelligenza Artificiale Problem Solving
42/102
A* = algoritmo ottimale
n0
Per ASSURDO:
A* espande da OPEN 2 e 2 non è la soluzione ottima
1. per definizione g(2) > f*
2. sia n  * nodo foglia (in OPEN)
3. se h è ammissibile allora f(n) ≤ f*
n
*
4. 2 viene preferito a n quindi f(n) ≥ f(2)
5. da 3 e 4 abbiamo che f* ≥ f(2)
6. dato che 2 è finale allora h(2)=0 e f(2)= g(2)
7. da 5 e 6 abbiamo che f* ≥ g(2) che contraddice il punto 1
Intelligenza Artificiale Problem Solving
43/102

A* = algoritmo completo
Per ASSURDO: A* ritorna un insuccesso o non termina
1. A* ritorna un insuccesso se OPEN è vuota
2. OPEN si svuota se nessuna foglia ha figli
3. se esiste un  tra n0 e  allora per ogni n   esiste un figlio
4. da 2 e 3 deriva che se esiste  allora OPEN non si svuota e
A* non ritorna un insuccesso
5. se  è di lunghezza finita allora A* termina anche in grafi
infiniti grazie all’uso di g(n): perché g(n) <  n
6. due condizioni per la completezza:
- costo di un  infinito = 
- * non infinito
Intelligenza Artificiale Problem Solving
44/102
Best-First Generale: WA*
(Ira Pohl, 1970)
Funzione di valutazione  f(n) = (1-w)g(n) + wh(n)





w = 0  ricerca breadth-first
w = 0,5  ricerca A*
w = 1  ricerca Greedy
Come cambia il costo della ricerca?
w < 0,5 non ha senso, quindi:
Funzione di valutazione  f(n) = g(n) + w h(n)


Crescendo w la ricerca diventa sempre più “greedy”
Il costo delle soluzioni è limitato superiormente da: wC*
(se w > 1)
Intelligenza Artificiale Problem Solving
45/102
WA*: alcuni risultati sul 15-puzzle
w
Mosse
Nodi
1
52,7
380 x 106
1,5
56,6
500 x 103
2
63,5
79 x 103
6
103,3
10500
99
145,3
7000
Intelligenza Artificiale Problem Solving
46/102
Iterative Deepening A* (IDA*)
(Korf, 1985)
Una innovazione “attesa”
1985: prime soluzioni ottime del gioco del 15
Eredita due qualità:


linear space search: O(bd) da DFID
ottimalità da A*
E’ completo, complex. temp = O(bd)
Intelligenza Artificiale Problem Solving
47/102

Algoritmo IDA*
Come funziona:

Ha una soglia di costo: threshold.

Funzione di valutazione  f(n) = g(n) + h(n)

Ha una LISTA di nodi LIFO

SE f(n)  threshold si espande il nodo.

SE la LISTA è vuota si ricominca da capo la
ricerca aggiornando threshold
Intelligenza Artificiale Problem Solving
48/102
£
Algoritmo IDA*
1.
2.
3.
4.
if (goal_test(x0)== true) return SUCCESS
soglia = g(x0)+h(x0)
LISTA.insert(x0)
do {
nodo = LISTA.remove()
figli[] = SCS(nodo)
for all figli{
if (g(figlio)+h(figlio)  soglia)
LISTA.insert(figlio)
}
} while( goal_test(nodo)== false
and !LISTA.isEmpty())
if(goal_test(nodo)== true) return SUCCESS
else{
update(soglia)
GOTO 3
}
?
Intelligenza Artificiale Problem Solving
49/102
IDA* Simulazione
1+4
0+3
1+2
Threshold: 3
1+4
2+3 2+3
Intelligenza Artificiale Problem Solving
50/102
0+3
IDA* Simulazione
1+4
2+5
2+5
3+4
Threshold: 5
1+4
1+2
2+3 2+3
3+4
3+2
4+3
Intelligenza Artificiale Problem Solving
2+5
3+4
2+3
3+4
3+4
4+3
51/102
0+3
IDA* Simulazione
1+4
2+5
3+6
4+5
3+4
2+5
3+6
1+2
Threshold: 7
1+4
2+3 2+3
3+4
3+4
4+5
4+5 4+3
5+2 5+4
6+1 - 6+3
Intelligenza7+0
Artificiale
Problem Solving
52/102
Formalizzazione Problemi:
Il Puzzle di Sam Loyd
configurazioni
risolvibili
X = tutte
le configurazioni
operatori
(non-reversibili)
SCS(x) = tutti
gli operatori
di x
N!N!/2
= ca.3
bb
=ca.
4
x0 = configurazione random
g = unitario per ogni SCS
t = configurazione ordinata
Intelligenza Artificiale Problem Solving
53/102
Formalizzazione Problemi:
Cubo di Rubik
1) Non ha senso ruotare la stessa faccia due volte
configurazioni
risolvibili
(8!
X = tutte
le configurazioni
8! 12! 38 212 )/12
consecutive
2) Muovere due facce opposte consecutivamente equivale
operatori
utilicentrale
su xdi x
18
SCS(x)
= tutti
glidell’asse
operatori
ca.11
alla sola
mossa
3) Dopo aver mosso la faccia “A” e poi la faccia “B”, va
una delle altre random
4 facce rimanenti.
x0 = mossa
configurazione
g = unitario per ogni SCS*
t = configurazione ordinata**
* se si usa costo unitario h(n) deve essere normalizzato a 1!
** per usare manhattan si associa ad un lato il colore delle tessere centrali
Intelligenza Artificiale Problem Solving
54/102