Intelligenza Artificiale
Ricerca Informata
Slides Intelligenza Artificiale,
Vincenzo Cutello
1
Outline





Best-first search
Ricerca A*
Euristiche
Hill-climbing
Simulated annealing
Slides Intelligenza Artificiale,
Vincenzo Cutello
2
Richiamo: Ricerca generale
function GENERAL-SEARCH(p:problem, QUEUING-FN)
returns una soluzione o fallimento
nodi  MAKE-QUEUE(MAKE-NODE(INITIAL-STATE[p]))
loop do
if nodi è vuoto
then return fallimento
nodo  REMOVE-FRONT(nodi)
if GOAL-TEST[p] applicato a STATE(nodo) si verifica
then return nodo
nodi  QUEUING-FN(nodi, EXPAND(nodo,OPERATORS[p]))
end
Una strategia è definita stabilendo l’ordine di espansione dei nodi
Slides Intelligenza Artificiale,
Vincenzo Cutello
3
Ricerca Best-first
Idea: usare una funzione di valutazione per ogni nodo
- stima della “desiderabilità”
Espandere il nodo più desiderabile non espanso
Implementation:
QUEUEINGFN = inserisci i successori in ordine decrescente di
desiderabilità
Casi particolari:
ricerca greedy
ricerca A*
Slides Intelligenza Artificiale,
Vincenzo Cutello
4
Canada con costi in Km
Distanze in linea d’area da Ottawa
Dawson
450
2650
Whitehorse
Churchill
1600
Calgary
3100
Quèbec
400
Churchill
2100
Regina
2300
Dawson
4700
St. John’s
1850
Edmonton
3000
Toronto
400
Halifax
1000
Vancouver
3850
Montreal
150
Whitehorse
4450
Ottawa
0
Winnipeg
1800
St. John’s
1350
Edmonton
1650
1100
450
750
Vancouver
Calgary
1500
950
1250
850
Regina 500
Quèbec
Winnipeg
250
1800 Ottawa
1600
Halifax
Montreal
175
400
Slides Intelligenza Artificiale,
Vincenzo Cutello
Toronto
5
Ricerca greedy
Funzione di valutazione h(n) (euristica)
= stima del costo da n all’obiettivo
Cioè, hSLD(n) = distanza in linea d’area da n
a Ottawa
La ricerca greedy espande i nodi che
sembrano più prossimi all’obiettivo
Slides Intelligenza Artificiale,
Vincenzo Cutello
6
Esempio di ricerca greedy
Whitehorse
4450
Vancouver
3850
Dawson
4700
Calgary
3100
Regina
2300
Winnipeg
1800
Edmonton
3000
Edmonton
3000
Churchill
2100
Churchill
2100
Slides Intelligenza Artificiale,
Vincenzo Cutello
Ottawa
0
Whitehorse
4450
Toronto
400
7
Proprietà della ricerca greedy

Completa ??
– No – si può entrare in loop
– Completa in spazi finiti con il controllo per la
ripetizione degli stati

Tempo ??
– O(bm), ma una buona euristica può dare notevoli
miglioramenti

Spazio ??
– O(bm) (mantiene tutti i nodi in memoria)

Ottimalità ??
–
NO
Slides Intelligenza Artificiale,
Vincenzo Cutello
8
Ricerca A*
 Idea: Evitare l’espansione di percorsi che
– sono già costosi, e
– che costeranno ancora parecchio
 Funzione di valutazione f(n) = g(n)+h(n)
– g(n) = costo sostenuto per raggiungere n
– h(n) = costo stimato per raggiungere l’obiettivo da n
– f(n) = costo totale stimato del percorso attraverso n per
raggiungere l’obiettivo
 La ricerca A* usa una euristica ammissibile
– h (n) non sovrastima mai l’effettiva distanza
Teorema: La ricerca A* è ottima
Slides Intelligenza Artificiale,
Vincenzo Cutello
9
Esempio di ricerca A*
Whitehorse
4450
450
1650
1160
Vancouver
5500
Dawson
5150
Edmonton
4600
1600
450
1250
Winnipeg
4650
Calgary
5150
500
Regina
5650
1100
1250
Edmonton
7100
1350
Churchill
5050
1800
Churchill
6050
Slides Intelligenza Artificiale,
Vincenzo Cutello
Ottawa
4650
Whitehorse
7650
1600
Toronto
4850
10
Ottimalità di
*
A
(dim. standard)
Supponiamo che qualche obiettivo sub-ottimale G2 è stato generato ed
è nella coda. Sia n un nodo non espanso di un percorso più breve ad un
obiettivo ottimo G1
Inizio
n
G2
G
f(G2) = g(G2)
poiché h(G2) = 0
> g(G1)
poiché G2 è sub-ottimale
≥ f(n)
poiché h è ammissibile
Poiché f(G2) > f(n), A* non selezionerà mai G2 per l’espansione
Slides Intelligenza Artificiale,
Vincenzo Cutello
11
Proprietà di A*
 Completa ??
– Si, a meno che non ci siano infiniti nodi con f ≤ f(G)
 Tempo ??
– Esponenziale in [errore relativo in h * lunghezza
della soluzione]
 Spazio ??
– Mantiene tutti i nodi in memoria
 Ottimalità ??
– Si
Slides Intelligenza Artificiale,
Vincenzo Cutello
12
Lemma: Pathmax
Per qualche euristica ammissibile, f può diminuire durante il
percorso di ricerca. Cioè, supponiamo che n’ è un successore di n
n
g=5
h=4
f=9
1
n’
g’ = 6
h’ = 2 f’ = 8
Stiamo perdendo informazione !
f(n) = 9  costo reale di un percorso attraverso n è ≥ 9
Quindi anche il vero costo di un percorso attraverso n’ ≥ 9
Modifica pathmax ad A*:
Invece di f(n’) = g(n’) + h(n’), si usa f(n’) = max( g(n’) + h(n’), f(n) )
Con pathmax, f è sempre non decrescente attraverso un qualsiasi
cammino
Slides Intelligenza Artificiale,
Vincenzo Cutello
13
Euristica ammissibile
Cioè, per il puzzle a 8:
H1(n) = numero di caselle fuori posto
H2(n) = somma delle distanze di Manhattan
(cioè, il numero di caselle di distanza da quella desiderata
per ogni casella)
5
4
1
6
1
8
8
7
3
2
7
Stato iniziale
2
3
4
6
5
Stato finale
H1(S) = ??
H2(S) = ??
Slides Intelligenza Artificiale,
Vincenzo Cutello
14
Euristica ammissibile
Cioè, per il puzzle a 8:
H1(n) = numero di tessere sbagliate
H2(n) = somma delle distanze di Manhattan
(cioè, il numero di caselle da quella desiderata di ogni
tessera)
5
4
1
6
1
8
8
7
3
2
7
Stato iniziale
2
3
4
6
5
Stato finale
H1(S) = ?? 7
H2(S) = ?? 2+3+3+2+4+2+0+2 = 18
Slides Intelligenza Artificiale,
Vincenzo Cutello
15
Esercizio
 Se l’euristica h soddisfa la disuguaglianza triangolare allora
il costo della f è non decrescente:
 Dim.:
– Dis. Triangolare → h(n) ≤ k(n,n’)+ h(n’) dove k(n,n’) è il costo del
cammino più breve da n a n’.
– f non decr. vuol dire f(n) ≤ f(n’), cioè:
g(n)+h(n) ≤ g(n’)+h(n’)
se n’ è un successore di n.
– Dalla dis. tr.: h(n) + g(n) ≤ k(n,n’)+ h(n’) + g(n)
– Ma g(n) + k(n,n’) = g(n’) !
– Dim. Completa
 Vale anche il viceversa.
Slides Intelligenza Artificiale,
Vincenzo Cutello
16
Dominanza
 Che fare se abbiamo più di una euristica ?
 Se h2(n) ≥ h1(n) per tutti gli n (entrambe
ammissibili) allora h2 domina h1 ed è
migliore per la ricerca !
 Perchè ?
Slides Intelligenza Artificiale,
Vincenzo Cutello
17
Problemi rilassati
 Come facciamo a trovare buone euristiche (ammissibili)
per un problema ?
 Le euristiche ammissibili possono essere derivate dal
costo della soluzione esatta di una versione rilassata del
problema.
 Esempi:
– Se le regole del puzzle a 8 sono rilassate in maniera tale che un
quadrato può essere mosso dovunque, allora h1(n) fornisce la
soluzione più breve
– Se le regole sono rilassate in maniera tale che un quadrato può
essere mosso in una qualunque casella adiacente, allora h2(n)
fornisce la soluzione più breve
Slides Intelligenza Artificiale,
Vincenzo Cutello
18
Esercizio
 Dato un piano con
ostacoli, come fare a
trovare la distanza più
breve tra due punti ?
– Quanti stati ci sono ?
 E’ vero che il cammino più
breve tra due vertici di
poligoni, è fatto da
segmenti che uniscono
vertici di poligoni ?
Slides Intelligenza Artificiale,
Vincenzo Cutello
19
Algoritmi a miglioramenti iterativi
 In molti problemi di ottimizzazione, il percorso è irrilevante;
lo stato obiettivo è la soluzione
 spazio degli stati = insieme di configurazioni “complete”;
– trova la configurazione ottima, ad esempio, TSP o,
– trova la configurazione soddisfacente i vincoli, ad esempio, il
problema delle n-regine
 In tali casi, possono essere usati algoritmi a miglioramenti
iterativi; mantenendo un singolo stato corrente e provando a
migliorarlo
 Spazio costante, adattabile sia per ricerca online che offline
Slides Intelligenza Artificiale,
Vincenzo Cutello
20
Esempio: n-regine
 Collocare n regine su una scacchiera n*n in maniera tale che non vi
siano due regine sulla stessa riga, colonna o diagonale.
 Euristica dei “minimi conflitti”.
Slides Intelligenza Artificiale,
Vincenzo Cutello
21
Hill-climbing
…(o gradiente ascendente/discendente)
“Come scalare l’Everest con nebbia fitta quando si soffre d’amnesia”
function Hill-Climbing (problema)
returns uno stato soluzione
input: problema, un problema
variabili locali: corrente, un nodo
prossimo, un nodo
corrente  MAKE-NODE(INITIAL-STATE[problem])
loop do
next  il successore con valore maggiore del nodo corrente
if VALUE[prossimo] < VALUE[corrente] then return corrente
corrente  prossimo
end
Slides Intelligenza Artificiale,
Vincenzo Cutello
22
Hill-climbing (cont.)
Problema: in funzione dello stato iniziale ci
possiamo bloccare su un massimo locale
valore
massimo globale
massimo locale
stati
Slides Intelligenza Artificiale,
Vincenzo Cutello
23
Simulated annealing
Idea: fuga dai massimi locali permettendo qualche mossa “cattiva” ma
decrementare gradatamente la loro misura e frequenza
function SIMULATED-ANNEALING (problema, schedule)
returns uno stato soluzione
inputs: problema, un problema
schedule, una corrispondenza dal tempo alla “temperatura”
variabili locali: corrente, un nodo
prossimo, un nodo
T, una “temperatura” per controllare la probabilità di
step discendenti
corrente  MAKE-NODE(INITIAL-STATE[problem])
for t  1 to ∞ do
T  schedule[t]
if T = 0 then return corrente
successivo  un successore selezionato in maniera random del nodo corrente
∆E  Value[next] – Value[corrente]
if ∆ E > 0 then corrente  successore
else corrente  successore soltanto con probabilità e∆E/T
Slides Intelligenza Artificiale,
Vincenzo Cutello
24
Proprietà del simulated annealing
 A “temperatura” fissa T, la probabilità di
raggiungere uno stato è governata dalla
distribuzione di Boltzman
P(x) = αeE(x)/kT
 Se T decresce abbastanza lentamente  si
raggiunge sempre lo stato migliore
 Proposto nel 1953, per la modellizzazione di
processi fisici
 Ampiamente usato nella progettazione di VLSI,
programmazione di linee aeree , etc.
Slides Intelligenza Artificiale,
Vincenzo Cutello
25
Ricerca euristica a memoria
limitata
 A* is optimally efficient:
– given the information in h,no other optimal search
method can expand fewer nodes.
 Complete:
– Unless there are infinitely many nodes with f(n) < f .
Assume locally finite: (1) finite branching, (2) every
operator costs at least δ > 0.
 Complexity (time and space):
– Still exponential because of breadth-first nature. Unless
|h(n) − h | ≤ O(log(h (n)), with h true cost of getting to
goal.
Slides Intelligenza Artificiale,
Vincenzo Cutello
26
Migliorare A*: IDA*
 Memory is a problem for the A* algorithms.
 IDA* is like iterative deepening, but uses an
f-cost limit rather than a depth limit.
 At each iteration, the cutoff value is the
smallest f-cost of any node that exceeded
the cutoff on the previous iteration.
 Each iteration uses conventional depth-first
search.
Slides Intelligenza Artificiale,
Vincenzo Cutello
27
Recursive Best First Search
 Similar to a DFS, but keeps track of the fvalue of the best alternative path available
from any ancestor of the current node.
 If current node exceeds this limit, recursion
unwinds back to the alternative path,
replacing the f-value of each node along the
path with the best f-value of its children.
 RBFS remembers the f-value of the best
leaf in the forgotten subtree.
Slides Intelligenza Artificiale,
Vincenzo Cutello
28
RBFS: pseudo-code
function RECURSIVE-BEST-FIRST-SEARCH(problem) return a solution or failure
return RFBS(problem,MAKE-NODE(INITIAL-STATE[problem]),∞)
function RFBS( problem, node, f_limit) return a solution or failure and a new f-cost limit
if GOAL-TEST[problem](STATE[node]) then return node
successors  EXPAND(node, problem)
if successors is empty then return failure, ∞
for each s in successors do
f [s]  max(g(s) + h(s), f [node])
repeat
best  the lowest f-value node in successors
if f [best] > f_limit then return failure, f [best]
alternative  the second lowest f-value among successors
result, f [best]  RBFS(problem, best, min(f_limit, alternative))
if result  failure then return result
Slides Intelligenza Artificiale,
Vincenzo Cutello
29
Properties of RBFS
 Keeps track of the f-value of the best-alternative
path available.
– If current f-values exceeds this alternative f-value than
backtrack to alternative path.
– Upon backtracking change f-value to best f-value of its
children.
– Re-expansion of this result is thus still possible.
Slides Intelligenza Artificiale,
Vincenzo Cutello
30
RBFS: Ex. Romania
 Path until Rumnicu Vilcea is already expanded
 Above node; f-limit for every recursive call is
shown on top.
 Below node: f(n)
 The path is followed until Pitesti which has a fvalue worse than the f-limit.
Slides Intelligenza Artificiale,
Vincenzo Cutello
31
RBFS: Ex. Romania
 Unwind recursion and store best f-value for current best
leaf Pitesti
result, f [best]  RBFS(problem, best, min(f_limit, alternative))
 best is now Fagaras. Call RBFS for new best
– best value is now 450
Slides Intelligenza Artificiale,
Vincenzo Cutello
32
RBFS: Ex. Romania

Unwind recursion and store best f-value for current best leaf Fagaras
result, f [best]  RBFS(problem, best, min(f_limit, alternative))

best is now Rimnicu Viclea (again). Call RBFS for new best
– Subtree is again expanded.
– Best alternative subtree is now through Timisoara.

Solution is found since because 447 > 417.
Slides Intelligenza Artificiale,
Vincenzo Cutello
33
RBFS: Evaluation
 RBFS is a bit more efficient than IDA*
– Still excessive node generation (mind changes)
 Like A*, optimal if h(n) is admissible
 Space complexity is O(bd).
– IDA* retains only one single number (the current fcost limit)
 Time complexity difficult to characterize
– Depends on accuracy if h(n) and how often best path
changes.
 IDA* and RBFS suffer from too little memory
Slides Intelligenza Artificiale,
Vincenzo Cutello
34
(simplified) memory-bounded A*
 Use all available memory.
– I.e. expand best leafs until available memory is full
– When full, SMA* drops worst leaf node (highest f-value)
– Like RFBS backup forgotten node to its parent
 What if all leafs have the same f-value?
– Same node could be selected for expansion and deletion.
– SMA* solves this by expanding newest best leaf and deleting
oldest worst leaf.
 SMA* is complete if solution is reachable, optimal if optimal
solution is reachable.
Slides Intelligenza Artificiale,
Vincenzo Cutello
35