Gennaio – Aprile 2007
Intelligenza Artificiale
marco ernandes
email: [email protected]
Problem Solving
Introduzione
Intelligenza Artificiale - Problem Solving
1/105
Intelligenza Artificiale - Problem Solving
2/105
“Risolvere problemi”
E’ uno dei processi intellettivi che secondo il
Comportamentismo richiede e definisce
l’“attività intellettuale”.
1.
2.
3.
4.
Induzione
Sussunzione
Ragionamento
Problem Solving
(Apprendimento)
(Riconoscimento)
(Deduzione)
(implica tutte le precedenti)
Approccio comportamentista: Test di Turing
Intelligenza Artificiale - Problem Solving
3/105
PS: uomo & macchina
Il PS è un’attività tipicamente definita come “razionale”.
Razionale = ciò che si basa su procedimenti esprimibili
in formula chiusa (algoritmi)
L’AI ha dimostrato che più un task richiede “razionalità”
in senso stretto più l’uomo perde il confronto con la
macchina.
Hard Computing vs. Soft Computing
Intelligenza Artificiale - Problem Solving
4/105
“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
5/105
A cosa “serve” un Problem Solver?
Spiegare in maniera computazionale
come l’uomo risolve i problemi
Fornire all’uomo uno strumento di
supporto
Intelligenza Artificiale - Problem Solving
6/105
GPS: General Problem Solver
(Newell, Simon e Shaw - 1958)
Risultato dell’approccio cognitivo
Esperienza previa con “Logic Theorist”
Uso di resoconti di PS umano
Analisi mezzi-fini
Intelligenza Artificiale - Problem Solving
7/105
Analisi Mezzi-Fini
a) Identificare la più grande differenza tra stato attuale e stato
desiderato.
b) Creare un sotto-obiettivo che cancelli questa differenza.
c) Selezionare un operatore che raggiunga questo sotto-obiettivo
d) SE l’operatore può essere applicato ALLORA lo si applica e,
arrivati nello stato successivo, si riapplica l’A-M-F.
e) SE l’operatore non può essere applicato ALLORA si usa l’A-MF in modo ricorsivo per rimuovere la condizione di blocco.
Intelligenza Artificiale - Problem Solving
8/105
“Bias” della razionalità
Aristotele e l’ “animale razionale”
3 limiti della razionalità



Informativi
Cognitivi
Deliberativi
Uomo “irrazionale” nella presa di decisioni


Paradosso di Allais
Ragionamento non Bayesiano
Per “irrazionalità” si intende contradditorietà diacronica nella presa di
decisioni
Intelligenza Artificiale - Problem Solving
9/105
Paradosso di Allais (’53)
Tra 2 scommesse, quale preferite?


A) vincere 30 Euro con probabilità 100%
B) vincere 45 Euro con probabilità 80%
Il 78% degli intervistati risponde A!
Eppure… l’utilità attesa è:


A = 30 x 1,0 = 30 Euro
B = 45 x 0,8 = 36 Euro
Intelligenza Artificiale - Problem Solving
10/105
Kahneman & Tversky (’78)
Cosa preferite?


A) vincere 120 Euro con probabilità 25%
B) vincere 180 Euro con probabilità 20%
Oltre il 50% risponde B!
Eppure… l’utilità attesa è sempre la stessa:


A = 120 x 0,25 = 30 Euro
B = 180 x 0,20 = 36 Euro
Intelligenza Artificiale - Problem Solving
11/105
Cap. 14
Ragionamento non-bayesiano
A Siena si è diffusa una malattia che interessa un soggetto su 1000. Se
una persona ammalata si sottopone al test diagnostico la malattia viene
rilevata nel 99% dei casi. Se una persona sana si sottopone allo stesso
test vengono rilevati un 2% di falsi positivi.
Mario si sottopone al test e risulta positivo. E’ più probabile che
sia malato o che sia sano?
Secondo il Teorema di Bayes:

P(M|T) = P(T|M) x P(M) / P(T)

P (M+ | T+) = 0.99 x 0.001 =0.00099 (0,1%)  Malato

P (M- | T+ ) = 0.02 x 0.999 =0.01998 (2%)
Intelligenza Artificiale - Problem Solving
 Sano
12/105
Alcune Conclusioni
Perde credito l’ipotesi simulativa su basi razionali.
Il ragionamento umano (PS e decisioni) non è
simulabile “razionalmente”

E’ studiato dalla Psicologia Cognitiva
Può avere più senso usare le macchine:


Sfruttando le loro potenzialità
Come supporto per l’uomo

(es: Problem Solving attuale, Sistemi Esperti)
Intelligenza Artificiale - Problem Solving
13/105
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
14/105
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
15/105
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
Ha senso quindi pensare ad un GPS?
Intelligenza Artificiale - Problem Solving
16/105
I giochi nell’IA e non solo
M. Minsky (1968):
“i giochi non vengono scelti perché sono chiari e semplici, ma
perché ci danno la massima complessità con le minime strutture
iniziali”
Pungolo Scientifico



Matematica: teoria dei grafi e complessità
Computer Science: database e calcolo parallelo
Economia: teoria dei giochi
Intelligenza Artificiale - Problem Solving
17/105
Teoria dei Giochi
Von Neumann & Morgenstern (1944)
Teoria della Decisione
Analizzare il comportamento
Individuale le cui azioni hanno
effetto diretto
Scommesse &
Mondo dei Puzzle
Intelligenza Artificiale - Problem Solving
Teoria dei Giochi
Analizzare il comportamento
Individuale le cui azioni hanno effetto
che dipende dalle scelte degli altri
Mondo dei Giochi
a + giocatori
18/105
Problem Solving
Ricerca nello spazio degli stati
“Blind” Search
Intelligenza Artificiale - Problem Solving
19/105
Ruolo del Search nell’AI
Anni ’60 – ‘80: cuore dell’AI

“Tutto” è Search o Knowledge
Recentemente… nei textbooks




Nilsson (1980):
Rich (1983):
Norvig & Russel (1995):
Pool, Mackworth & Goebel (1998):
Intelligenza Artificiale - Problem Solving
17%
31%
13 %
10%
20/105
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
21/105
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
22/105
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
23/105
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
24/105
“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
25/105
“Breadth First” - simulazione
GOAL
Intelligenza Artificiale - Problem Solving
26/105
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
>1014
32 anni
>10000 TB
b =10, velocità ricerca = 100 mila nodi/sec., 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
27/105
“Depth First”
Ricerca in Profondità
Usa una memoria LIFO
E’ un algoritmo “aggressivo”
E’ non completo e non ottimale
Complessità temporale: O(bm)
Complessità spaziale: O(mb)
Intelligenza Artificiale - Problem Solving
28/105
“Depth First” - simulazione
GOAL
Intelligenza Artificiale - Problem Solving
backtracking
29/105
Come migliorarli?
Conoscendo lo stato goal
Non ripetendo gli stati

Evitando di espandere lo stato di provenienza



Che effetto ha sui costi di ricerca?
Evitando i cicli
In generale: evitando di generare nodi con stati
già visitati nella ricerca
Conoscendo il costo degli operatori
Intelligenza Artificiale - Problem Solving
30/105
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
31/105
Intelligenza Artificiale - Problem Solving
GOAL
X0
Ricerca Bidirezionale - Simulazione
32/105
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
33/105
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
E’ ottimale e completa
bd(b/(b-1))2
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. Quanto?
Intelligenza Artificiale - Problem Solving
34/105
Iterative Deepening - sim
Iterazione: 1
Intelligenza Artificiale - Problem Solving
35/105
Iterative Deepening - sim
Iterazione: 2
Intelligenza Artificiale - Problem Solving
36/105
Iterative Deepening - sim
Iterazione: 3
GOAL
Intelligenza Artificiale - Problem Solving
37/105
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
38/105
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
39/105
Dijkstra?
Sì. Ricerca Uniforme = Algoritmo Dijkstra
E’ il progenitore degli algoritmi Best-First
Ricerca Operativa  Ricerca Cieca (AI)
Complex temp. Dijkstra = O(X2)
Complex temp. Unif-cost = O(bd)
Perché due stime diverse?FF
Intelligenza Artificiale - Problem Solving
40/105
Branching Factor
3
7
6
1
5
2
1
2
4
5
Branching Factor Naive
Branching Factor Asintotico
Branching Factor Effettivo
4
8
3
C
S
C
C
S
C
CS
SS
CC
SC
1 = fcc+fcs+fss+fsc
bfcc = fsc
bfcs = fcc
bfss=fcs
bfsc= 2fss+fcs
b4 - b - 2 = 0
Intelligenza Artificiale - Problem Solving
41/105
Confronto tra bnaive e basyn
bnaive
basyn
5-Puzzle
1,33
1,35
8-Puzzle
1,67
1,6722=8 x 104
1,73
1,7322=1,7 x 105
15-Puzzle 2
253=9 x 1015
24-Puzzle 2,2
2,2100=1,7 x 1034
Intelligenza Artificiale - Problem Solving
2,13
2,1353=2,5 x 1017
2,37
2,37100=3 x 1037
42/105
Branching factor effettivo b*
Fattore di ramificazione reale di un processo di ricerca.
E’ valutabile solo a posteriori! Quando conosci il numero
di nodi visitati (N).
N = 1 + b* + b*2 + ... + b*d = (b*d+1-1)/(b*-1).
(approx. b*  d N ) .
b* è utile per testare la efficienza di un algoritmo (o di
una euristica)
es: trovare sol a profondità 5 in 52 nodi, b* = 1,92
Intelligenza Artificiale - Problem Solving
43/105
Problem Solving
Ricerca nello spazio degli stati
“Heuristic” Search
Intelligenza Artificiale - Problem Solving
44/105
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
45/105
Come usare un’euristica?
X0
g(n)
Actual State (n)
f(n)
h(n)
Goal State
Intelligenza Artificiale - Problem Solving
46/105
Ricerca Informata
3 pilastri
1
Strategia di ricerca
Intelligenza Artificiale - Problem Solving
2
Euristica
3
Politica f(n)= g(n) e h(n)
47/105
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
48/105
Proprietà generali delle Euristiche
Ammissibilità:

h(n) è ammissibile se h(n) ≤ h*(n) n
Dominanza:

h2 domina h1 se h1(n) ≤ h2(n) n
e h1 & h2 sono ammissibili
Intelligenza Artificiale - Problem Solving
49/105
Proprietà generali delle Euristiche 2
n’
h(n’)
c(n,n’)
Consistenza:

n
h(n) è consistente se
h(n)  c(n,n’) + h(n’) (n,n’)
h(n)
Monotonicità:

h(n) è monotona se
h(n)  c(n,n’) + h(n’)  n,n’  SCS(n)
Intelligenza Artificiale - Problem Solving
50/105

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
51/105
Proprietà generali delle Euristiche 3
Ammissibilità e Ottimalità:

SE h(n) è ammissibile
SE l’algoritmo usato è Best-First
SE h(n) non viene MAI pesato più di g(n)

ALLORA la Ricerca è ottimale


Formalmente:
Intelligenza Artificiale - Problem Solving
f (n )  f * n
52/105
Proprietà generali delle Euristiche 4
Altre conseguenze:

se un’euristica è monotona allora è ammissibile

se un’euristica è monotona allora f(.) non decresce
(per cui vale f(n)  f* n)

se h è non ammissibile la si può rendere ammissibile
garantendone il vincolo di monotonicità!

se h1 domina h2 tutti i nodi espansi usando BEST-FIRST
e h1 sono espansi usando h2

Ogni nodo n’ espanso da un algoritmo BEST-FIRST con
h ammissibile costruisce un percorso ottimo tra n0 e n’
Intelligenza Artificiale - Problem Solving
53/105
Come ottenere un’euristica
ammissibile?
Heuristic generation
Analisi dei vincoli sugli operatori
Per muovere una tessera da A a B:
3
7
6
1
5
8
4
by Abstraction
ABSOLVER
(Prieditis ‘93)
1) A e B devono invertire le proprie posizioni
2) B deve essere una casella vuota
3) A e B devono essere confinanti
2
4) Un solo movimento per volta
Rilassando 1,2,3,4:
Rilassando 1,2,3:
h(n) = 1  non c’è informazione
h1(n) = 7  hfp(n)
Rilassando 1,2:
Non rilassando:
h2(n) = 17  hm(n)
si deve risolvere il problema stesso!
Intelligenza Artificiale - Problem Solving
54/105
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
55/105
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
56/105
Pattern Databases
(Culberson&Schaeffer 1996)
Pattern Database è la prima euristica memory-based.
1
2
3
4
5
6
7
8
9
10 11 12
13 14 15
Per ogni permutazione delle tessere “fringe”
si risolve il sottoproblema, considerando il
pivot e le altre tessere. Si memorizza in un
DB il numero di mosse.
Si fa lo stesso per l’altro Pattern.
Vi sono N! / (N!-n!) permutazioni delle tessere fringe compreso il
pivot. Fringe del 15-puzzle = 519 milioni (495 MB memoria).
Usando solo il fringe: speedup* su hm = 6, nodi = 1/346
Usando il doppio Pattern: speedup = 12, nodi = 1/2000
Grandi miglioramenti con Disjoint Pattern DB (Korf & Taylor, ‘02)
Intelligenza Artificiale - Problem Solving
57/105
Effetti delle euristiche
Nella pratica: migliorano i tempi della ricerca.
In teoria: solo un’euristica “oracolare” elimina la
complessità esponenziale!


Constant Absolute Error:
h*(n)-h(n) = costante  costo di ricerca lineare b*d
Constant Relative Error:
h*(n)-h(n) = dipende da h*  costo di ricerca bd
La ricerca è asintoticamente cieca.
Intelligenza Artificiale - Problem Solving
58/105
Algoritmi di Ricerca Euristica
Hill-Climbing
Best-First Search



Algoritmi Greedy
Algoritmi A*
Algoritmo Generale: WA*
Memory Bounded Search

Linear search (IDA*), mem-bounded A* (SMA*)
Bidirectional Heuristic Search


Front-to-end (BHPA*),
Front-to-front (perimeter search: BIDA*)
Intelligenza Artificiale - Problem Solving
59/105
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
5
3
0
GOAL
Intelligenza Artificiale - Problem Solving
60/105
“Greedy” Search
Ricerca Best-First che minimizza f(n) = h(n)
Memorizza tutti i nodi frontiera
1. if (goal_test(x0)== true) return SUCCESS
2. else CODA.insert(x0, h(x0) )
3. do {
if (CODA.isEmpty()) return FAILURE
nodo = CODA.remove(0)
figli[] = SCS(nodo)
CODA.insert(figli, h(figli))
} while( goal_test(nodo)== false )
4. return SUCCESS
Intelligenza Artificiale - Problem Solving
61/105
“Greedy” Search 2
Proprietà:



Non Ottimale
Non Completo (senza l’Hash)
Complex time & space: O(bm)
Miglioramenti per non ripetere stati:




check sulla CODA dei nodi da espandere
aggiunta di tabella HASH per nodi già espansi
lista dei nodi espansi  CLOSED
lista dei nodi da espandere  OPEN
Intelligenza Artificiale - Problem Solving
62/105
“Greedy Search” - simulazione
3
3
7
8
5
5
8
7
4
6
7
3
0
7
2
8
7
8
GOAL
Intelligenza Artificiale - Problem Solving
63/105
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 (anche senza l’Hash!!)
 Complex time & space: O(bd)
 Ottimamente efficiente
Intelligenza Artificiale - Problem Solving
64/105
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
Se “figlio” è in nodo = OPEN.remove()
OPEN e ha f() CLOSED.insert(nodo)
figli[] = SCS(nodo)
minore, la si for all figli{
aggiorna!
if (!OPEN.contains(figlio))
AND if (!CLOSED.contains(figlio))
OPEN.insert(figlio, g(figlio)+h(figlio))
}
} while( goal_test(nodo)== false )
4. return SUCCESS
Intelligenza Artificiale - Problem Solving
65/105
Dimostrazioni
A* è un algoritmo ottimale
A* è un algoritmo completo
Intelligenza Artificiale - Problem Solving
66/105
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
*
2
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
67/105
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
68/105
Confronto tra Greedy e A*
Robot Navigation
h(n) = Distanza Manhattan
g(n,SCS(n)) = 1
Intelligenza Artificiale - Problem Solving
69/105
g=4, h=4
g=1, h=7
1
5
4 3 6
7 2 8
g=2, h=4
g=1, h=5
g=0, h=6
1 3 5
4 2 6
7
8
1 3 5
4
6
7 2 8
1 3 5
4 6
7 2 8
1 3 5
4 2
7 8 6
g=2, h=6
1 3 5
4 2Simulazione
6
7 8
g=2, h=6
g=1, h=7
g=1, h=7
1 3 5
4 2 6
7 8
g=3, h=5
1 3 5
4 6
7 2 8
1 3
4 6 5
7 2 8
g=2, h=8
1 3 5
4 6 8
7 2
Intelligenza Artificiale - Problem Solving
1 3
4 2 5
7 8 6
g=5, h=3
1 3
4 2 5
7 8 6
g=4, h=6
1 3 5
4
2
7 8 6
di A*
g=6, h=2
g=6, h=4
1 2 3
4
5
7 8 6
1 3
4 2 5
7 8 6
g=4, h=6
g=3, h=5
1
3
4 6 5
7 2 8
1 3
4 6 5
7 2 8
g=4, h=6
goal
1 6 3
4
5
7 2 8
70/105
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*
Intelligenza Artificiale - Problem Solving
71/105
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
72/105
WA* Esempio: maze problem
w=1
w=2
w=5
X
O
Intelligenza Artificiale - Problem Solving
73/105
WA* Esempio: maze problem
15+9
w=1
X
17+7
23+1
21+1 22+2
20+2
19+3
0+10
18+4
5+15 4+14 3+13 2+12 1+11
17+5
6+16 7+15 8+14 9+13 10+12 11+11 12+10 13+9 14+8 15+7 16+6
Intelligenza Artificiale - Problem Solving
74/105
WA* Esempio: maze problem
11+22 12+20 15+18 16+16 19+14 20+12 21+10
w=2
10+20 13+18 14+16 17+14 18+12
22+8
9+18 8+16
23+6 24+4 25+2
24+12
X
31+2
6+20 7+18
26+4 29+2 30+4
5+22
27+6 28+4
4+24 3+22
2+24 1+22
O
5+30
Intelligenza Artificiale - Problem Solving
75/105
WA* Esempio: maze problem
24+20
w=5
17+35 18+30 19+25 20+20 21+15 22+10 23+5
X
29+5
16+40 15+35 14+30 13+25 12+20 11+15 24+10 27+5 28+10
5+35 6+30 7+25 10+20 25+15 26+10
4+40 3+35 8+30 9+25
1+55
Intelligenza Artificiale - Problem Solving
O
1+45 2+40
76/105
WA* Esempio: maze problem
X
X
O
w=1
CLOSED=41
OPEN=18
d = 24
wC* = 24
O
w=2
CLOSED=66
OPEN=18
d = 32
wC* = 48
Intelligenza Artificiale - Problem Solving
X
O
w=5
CLOSED=37
OPEN=16
d = 30
wC* = 120
77/105
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
78/105

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
79/105
£
Algoritmo IDA*
1.
2.
3.
4.
if (goal_test(x0)== true) return SUCCESS
soglia = g(x0)+h(x0)
LISTA.insert(x0)
La nuova soglia
do {
è data dal
nodo = LISTA.remove()
minore f(n) fuori
figli[] = SCS(nodo)
for all figli{
soglia nella
if (g(figlio)+h(figlio)  soglia)
iterazione
LISTA.insert(figlio)
precedente
}
} while( goal_test(nodo)== false
and !LISTA.isEmpty())
if(goal_test(nodo)== true) return SUCCESS
else{
update(soglia)
GOTO 3
}
?
Intelligenza Artificiale - Problem Solving
80/105
IDA* Simulazione
1+4
0+3
1+2
0
Threshold: 3
1+4
2+3 2+3
Intelligenza Artificiale - Problem Solving
81/105
0+3
IDA* Simulazione
1+4
2+5
2+5
3+4
Threshold: 5
1+4
1+2
2+5
2+3 2+3
3+4
3+2
4+3
Intelligenza Artificiale - Problem Solving
3+4
2+3
3+4
3+4
4+3
82/105
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
7+0
6+1
6+3
Intelligenza Artificiale - Problem Solving
83/105
IDA*:difetti
Non è ottimamente efficiente:


Ripete i nodi delle iterazioni precedenti (incide
bd(b/(b-1))2
poco, specie se b è grande)
Ripete nodi nella stessa iterazione (d+1)1 + (d)b + (d-1)b2 + … + (1)bd
Funziona solo se:



costo degli operatori del problema hanno
valore discreto e (quasi) costante
le valutazioni euristiche hanno valore discreto
altrimenti…
bd
/
i = O(b2d )
i= 0
Intelligenza Artificiale - Problem Solving
84/105
Miglioramenti ad A* e IDA*
A*


A parità di f(n): si deve preferire min(h(n))
Implementare OPEN con Array di Hashtable

Si prelevano i nodi da OPEN[min f(n)]
IDA*

Sfruttare l’informazione delle iterazioni precedenti


Espansione nodi: ordinamento dei figli
Tenere in memoria una transposition table dei nodi
già visitati per evitare ripetizioni

-40% visite sul 15-puzzle
Intelligenza Artificiale - Problem Solving
85/105
Simplified Memory-Bounded A* (SMA*)
(Russel, ’92)
SMA* è un A* che adatta la ricerca alla quantità di
memoria disponibile.
Se la mem è esaurita si “dimenticano” dei nodi n
della frontiera e più in alto nell’albero si fa backup del
minimo f(n) dei nodi dimenticati.
Completata l’espansione di n si aggiorna f(n) al
minimo f(.) osservato tra i nodi successori di n
E’ ottimale se c’è mem sufficiente per il cammino
risolutivo ottimale
Se c’è mem per tutto l’albero SMA* coincide con A*
Rispetto ad IDA*: quando conviene e quando no?
Intelligenza Artificiale - Problem Solving
86/105
Simplified Memory-Bounded A* (SMA*)
15
25
35
30
18
24
15
15
13
20
13
12
12
12
(15) 13
24
13
(15) 15
(∞)
13
29
24
∞
ES:
MAX num nodi = 3
In giallo i nodi GOAL
I valori sono gli f(n)
24
15 (24)
15 (24)
15
15
15
24
∞
Intelligenza Artificiale - Problem Solving
(∞)
20
20
87/105
BHPA* - Bidirectional A*(Pohl ‘71)
Bi-directional Heuristic Path Algorithm compie due
ricerche A* “simultanee” in direzioni opposte usando 2
euristiche: una forward (hf ) e una backward (hb).
Ad ogni espansione la direzione è scelta con il criterio
della cardinalità:
 if |OPENf| < |OPENb| then dir = f else dir = b
L’algoritmo termina se la migliore soluzione trovata Lmin:
L min # max [ n !min
f f (n),n !min
fb (n)]
OP EN
OP EN
f
Questo vincolo di terminazione
rende BHPA* poco efficiente!
b
n’
hf(n’)
s
t
hb(n’’)
n’’
front-to-end heuristics
Intelligenza Artificiale - Problem Solving
88/105
Il problema della ricerca front-to-end
A* è più efficiente di BHPA*! Perchè?

#(BHPA) ≈ 2(#A*) e non #(BHPA) ≈ √#(A*) come dovrebbe risultare
dalla blind search theory.
“Metafora del Missile”?


Le due ricerche si sorpassano
senza toccarsi, come due missili?
Questa congettura (Pohl, Nilsson) è falsa!
Le due ricerche vanno una attraverso l’altra.
Il vero problema è la garanzia di ottimalità.
QuickTime™ e un
decompressore TIFF (Non compresso)
sono necessari per visualizzare quest'immagine.
QuickTime™ e un
decompressore TIFF (Non compresso)
sono necessari per visualizzare quest'immagine.
Intelligenza Artificiale - Problem Solving
QuickTime™ e un
decompressore TIFF (Non compresso)
sono necessari per visualizzare quest'immagine.
89/105
Front-to-front perimeter search
(BIDA*, Manzini ‘95)
BIDA* si basa su due step distinti:


una ricerca breadth-first visita tutti i nodi attorno al target e
poi vengono memorizzati i nodi della frontiera (perimeter)
con i loro valori di h* value (k nella figura sotto)
ricerca IDA* forward usando front-to-front evaluations
front-to-front evaluations sono calcolate così:
max (h 1 (A),i ! min
(h (A, B i) + k (B i))
fr ontier

Per maggior velocità i
nodi “non necessari”
possono essere rimossi
Intelligenza Artificiale - Problem Solving
QuickTime™ e un
decompressore TIFF (Non compresso)
sono necessari per visualizzare quest'immagine.
90/105
Perimeter search: valutazione
La perimeter search è efficiente solo in 2 casi:


quando IDA* è “feasible” (operatori a costo unitario)
quando la soluzione ottima non è molto profonda
(altrimenti il perimetro contiene troppo poco del percorso)
Ottimi risultati con i puzzle, pessimi nel path-finding
15-puzzle: avg. d = 52,7
(un perimetro di 15 copre
quasi il 30% della distanza)
QuickTime™ e un
decompressore TIFF (Non compresso)
sono necessari per visualizzare quest'immagine.
Intelligenza Artificiale - Problem Solving
2000x2000 path
finding: avg. d = ca.
3000, un perimetro di 50
copre solo l’1,7%
QuickTime™ e un
decompressore TIFF (Non compresso)
sono necessari per visualizzare quest'immagine.
91/105
Problem Solving
Ricerca nello spazio degli stati
Online Search
Intelligenza Artificiale - Problem Solving
92/105
Online Search
La differenza rispetto alla offline search è che l’agente conosce
SCS(n) (e i suoi costi) solo quando SI TROVA in n.
Nell’esempio sotto l’agente (senza lookahead) scopre che l’operatore
UP porta da (1,1) a (2,1) solo dopo averlo applicato!
L’agente deve muoversi con 2 scopi:


esplorare lo spazio
arrivare allo stato finale
Il costo è dato dalla somma degli operatori
applicati in tutta l’esplorazione
Intelligenza Artificiale - Problem Solving
93/105
Online Search
VALUTAZIONE ALGORITMI:
Competitive Ratio (CR) = g cammino percorso / g cammino ottimo
(E’ molto difficile riuscire a porre bound su CR!)
PROBLEMI:

DEAD END: se gli operatori sono irreversibili allora non è possibile
garantire completezza (spazio non “safely explorable”)  CR unbounded

BLOCCO AVVERSARIO: (ambiente dinamico) un avversario potrebbe
porci degli ostacoli in modo da rendere il cammino altamente inefficiente
VANTAGGI:

La ricerca online può attaccare problemi in un
ambiente dinamico (non avverso!)
(es: aggirare ostacoli che si muovono)
Intelligenza Artificiale - Problem Solving
94/105
Algoritmi Online (Real Time)
Hill-Climbing:
dato che è una ricerca locale può essere usata come algoritmo online
(ha il difetto di bloccarsi in un minimo locale, perchè ?)
Online Depth First Search (Online-DFS):
usa il principio della ricerca in profondità con backtracking. Se ad
ogni stato tutte le azioni sono state provate: backtracking fisico allo
stato predecessore!

Richiede di mappare lo spazio “visitato” in una tabella:
result[A,S1]  S2

Richiede di monitorare le zone dello spazio “da esplorare” con un
tabella indicizzata per ogni stato unexplored[S].

Richiede di monitorare le zone dello spazio in cui poter fare
backtracking con una tabella unbacktracked[S].
Intelligenza Artificiale - Problem Solving
95/105
Online Depth First Search
> action = ONLINE-DFS(S)
ONLINE-DFS(sa)
if (goal_test(sa)== true) return STOP
if (UNEXPLORED[sa] == null) {
figli[] = SCS(sa)
for all (figli != sp) UNEXPLORED[sa].add(figlio)
}
RESULT[ap,sp]  sa
if (UNEXPLORED[sp].is_empty()==false)
UNBACKTRACKED[sa].add(sp)
if (UNEXPLORED[sa].is_empty()==true) {
if (UNBACKTRACKED[sa].is_empty()==true) return STOP
back_state  UNBACKTRACKED[sa].pop()
for all (actions of sa)
if (RESULT[action,sa] == back_state)
new_action  action
}
else new_action  UNEXPLORED[sa].pop()
sp = sa / ap = new_action
return new_action
Intelligenza Artificiale - Problem Solving
96/105
Algoritmi Online “informati”
LRTA* (Learning Real-Time A*, Korf ‘90):


E’ dato da: Hill-Climbing + Memoria + aggiornamento funzione
euristica
Possiede una tabella H[S] dei costi aggiornati per ogni stato.
Il criterio di aggiornamento è dato dal classico f(n) = g(n)+h(n)
Funzionamento (l’agente entra in uno stato sa)


1) se H[sa] è null allora H[sa]  h(sa)
2) se sa ha un predecessore allora



result[ap,sp ]  sa
H[sp]  min g(s) + H[s]  a  action[sp] e s = result[a,sp ] (update)
3) scegli l’azione a che porta allo stato s vicino con min g(s)+H[s]
(se è null allora si prende h(s)), aggiorna sp  sa e ricomincia
Intelligenza Artificiale - Problem Solving
97/105
LRTA*: un esempio
Spazio monodimensionale
I valori all’interno dei cerchi corrispondono a H[S]
QuickTime™ e un
decompressore TIFF (Non compresso)
sono necessari per visualizzare quest'immagine.
QuickTime™ e un
decompressore TIFF (Non compresso)
sono necessari per visualizzare quest'immagine.
QuickTime™ e un
decompressore TIFF (Non compresso)
sono necessari per visualizzare quest'immagine.
QuickTime™ e un
decompressore TIFF (Non compresso)
sono necessari per visualizzare quest'immagine.
QuickTime™ e un
decompressore TIFF (Non compresso)
sono necessari per visualizzare quest'immagine.
Intelligenza Artificiale - Problem Solving
98/105
LRTA*: proprietà
In spazi “sicuri” trova una soluzione in tempo finito
Complessità = O(n2)
Non è completo in spazi infiniti (a differenza di A*)
E’ possibile dimostrare che il valore di H[s] converge
ad h*(s) durante il cammino.
Se aumento il lookahead migliora il cammino, ma
aumenta il costo computazionale per passo. Bisogna
fare una scelta nel TRADEOFF:
costo simulazione / costo esecuzione
Intelligenza Artificiale - Problem Solving
99/105
Riassumendo…
Formalizzazione dei problemi
Risolvere problemi = cercare un percorso in un albero di scelte
Metodi di valutazione della ricerca
Algoritmi di ricerca cieca
Cosa è un’euristica
Proprietà delle euristiche ed effetti sul costo di ricerca
Come generare un’euristica ammissibile
Componenti degli algoritmi di ricerca informata
Algoritmo Hill-Climbing
Algoritmi Best-First (Greedy ed A*)
Proprietà dell’algoritmo A*
WA*: generalizzazione della ricerca informata
Algoritmi Memory-Bounded (IDA*, SMA*)
Ricerca informata bidirezionale (BHPA*, BIDA*)
Algoritmi Real-Time (OnlineDFS, LRTA*)
Intelligenza Artificiale - Problem Solving
100/105
Formalizzazione Problemi:
Il Puzzle di Sam Loyd
configurazioni
risolvibili
X = tutte
le configurazioni
N!N!/2
operatori
(non-reversibili)
SCS(x) = tutti
gli operatori
di x
= ca.3
bb
=ca.
4
x0 = configurazione random
g = unitario per ogni SCS
t = configurazione ordinata
Intelligenza Artificiale - Problem Solving
101/105
Formalizzazione Problemi:
Cubo di Rubik
1) Non ha senso ruotare la stessa faccia due volte
12)/12
configurazioni
risolvibili
(8!
X = tutte
le configurazioni
8! 12! 388 212
consecutive
2) Muovere due facce opposte consecutivamente equivale
operatori
utilicentrale
su xdi x
SCS(x)
= tutti
glidell’asse
operatori
18
ca.11
alla sola
mossa
3) Dopo aver mosso la faccia “A” e poi la faccia “B”, va
x0 = mossa
configurazione
una delle altre random
4 facce rimanenti.
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
102/105
Formalizzazione Problemi:
Robot Navigation
X = le coordinate possibili del robot
SCS(x) = tutti gli spostamenti da x
x0 = posizione random del robot
g = lunghezza spostamento
sup. totale – ostacoli
= ca. 105 pixel
molto variabile:
< 105 spostamenti
Variabile tra
1 e b2 + h2
t = (coord. Robot == coord. GOAL)
Intelligenza Artificiale - Problem Solving
103/105
Robot Navigation
Spazio degli stati ed operatori
Intelligenza Artificiale - Problem Solving
104/105
Formalizzazione Problemi:
Robot Navigation
X = i vertici dei poligoni + x0 e goal
Lineare con il
numero di poligoni
SCS(x) = tutti gli spostamenti da x
pochissimi
x0 = posizione random del robot
g = lunghezza spostamento
Variabile tra
1 e b2 + h2
t = (coord. Robot == coord. GOAL)
Intelligenza Artificiale - Problem Solving
105/105