Risoluzione di problemi e
ricerca
Slides Intelligenza Artificiale,
Vincenzo Cutello
1
Outline





Agenti risolutori di problemi
Tipi di problema
Formulazione del problema
Esempi di problemi
Algoritmi di base per la ricerca
Slides Intelligenza Artificiale,
Vincenzo Cutello
2
Agenti risolutori di problemi
Forma ristretta di un agente generale
function SIMPLE-PROBLEM-SOLVING-AGENT(p)
returns un azione
Inputs: p, una percezione
Static: s, una sequenza di azioni, inizialmente vuota
state, una qualche descrizione dello stato corrente del mondo
g, un obiettivo, inizialmente nullo
problem, una formulazione del problema
state  UPDATE-STATE(state,p)
if s è vuota then
g  FORMULATE-GOAL(state)
problem  FORMULATE-PROBLEM(state,g)
s  SEARCH(problem)
action  RECOMMENDATION(s,state)
s  REMAINDER(s,state)
Return action
Nota: questa è una risoluzione di problema offline
La risoluzione di problemi online implica azioni senza una completa conoscenza
del problema e della soluzione
Slides Intelligenza Artificiale,
Vincenzo Cutello
3
Esempio: Canada
Dawson
Whitehorse
Churchill
St. John’s
Edmonton
Quèbec
Winnipeg
Calgary
Vancouver
Regina
Slides Intelligenza Artificiale,
Vincenzo Cutello
Ottawa
Toronto
Halifax
Montreal
4
Esempio: Canada
 Vacanza in Canada; attualmente a Whitehorse.
 Il volo parte domani da Ottawa
 Formulazione dell’obiettivo:
essere ad Ottawa
 Formulazione del problema:
stati: la varie città
operatori: guidare da una città all’altra
 Trovare la soluzione:
sequenza di città, cioè, Whitehorse, Edmonton,
Winnipeg, Ottawa
Slides Intelligenza Artificiale,
Vincenzo Cutello
5
Tipi di problema
Deterministico, accessibile  problema a stato singolo
Deterministico, inaccessibile  problema a stato multiplo
Nondeterministico, inaccessibile  problema di contingenza
– è necessario l’uso di sensori durante l’esecuzione
– la soluzione è un albero
– spesso ricerca interleave, esecuzione
Spazio degli stati sconosciuto  problema di esplorazione
(“online”)
Slides Intelligenza Artificiale,
Vincenzo Cutello
6
Esempio: il mondo dell’aspirapolvere
Stato singolo, inizia al #5
Soluzione ??
Stato multiplo, inizia al
{1,2,3,4,5,6,7,8}
Cioè, Destra va al {2,4,6,8}
Soluzione ??
Contingenza, inizia al #5
Legge di Murphy: si può sporcare
un tappeto pulito
Sensori locali: presenza e
posizione della polvere.
Soluzione ??
1
2
3
4
5
6
7
8
Slides Intelligenza Artificiale,
Vincenzo Cutello
7
Formulazione del problema a stato singolo
Un problema è definito da quattro elementi:
 Stato iniziale cioè, “a Whitehorse”
 Operatori (o funzione successore S(x))
cioè, Whitehorse  Dawson Whitehorse  Vancouver
etc.
 Verifica dell’obiettivo, può essere
esplicito, cioè, x = “a Ottawa”
implicito, cioè, Non_Sporco(x)
 Costo del cammino (additivo)
cioè, somma delle distanze, numero di operatori eseguiti,
etc.
 Una soluzione è una sequenza di operatori che conduce
dallo stato iniziale allo stato obiettivo
Slides Intelligenza Artificiale,
Vincenzo Cutello
8
Selezionando uno spazio degli stati

Il mondo reale è assurdamente complesso quindi lo spazio degli stati
deve essere astratto per la risoluzione del problema



(Astratto) stato = insieme di stati reali
(Astratto) operatore = combinazione complessa di stati reali cioè,
“Whitehorse  Dawson” rappresenta un insieme complesso di rotte,
fermate, etc.
Per garantire la realizzabilità, a un qualsiasi stato reale “a
Whitehorse” deve corrispondere un qualche stato reale “a Dawson”


(Astratto) soluzione = l’insieme dei percorsi reali che sono soluzione nel
mondo reale
Ogni azione astratta dovrebbe essere più facile rispetto al problema
originale
Slides Intelligenza Artificiale,
Vincenzo Cutello
9
Esempio: Il puzzle a 8
5
4
1
6
1
8
8
7
3
2
7
Stato iniziale




2
3
4
6
5
Stato finale
Stati ??: Posizioni intere delle tessere (ignoriamo le posizioni intermedie)
Operatori ??: Muovi il bianco a sinistra, destra, sopra, sotto
Verifica dell’obiettivo ??: = stato obiettivo (dato)
Costo del cammino ??: 1 per mossa
Nota: La soluzione ottima per la famiglia dei puzzle a n è NP-hard
Slides Intelligenza Artificiale,
Vincenzo Cutello
10
Grafo dello spazio degli stati per il mondo
dell’aspirapolvere
D
S
D
S
A
S
D
A
R
S
S
A
D
D
S
A
A
A
D
S
D
A




S
A
Stati ??: Locazione dello sporco e del robot (ignoriamo la quantità di sporco)
Operatori ??: Sinistra, Destra, Aspira
Verifica dell’obiettivo ??: assenza di sporco
Costo del cammino ??: 1 per operatore
Slides Intelligenza Artificiale,
Vincenzo Cutello
11
Esempi:
 Il problema delle 8 regine;
 Criptoaritmetica undici + dieci = ventuno;
 Missionari e cannibali (capre e cavoli);
Per ognuno:
Stati – Operatori – Obiettivo Costo
Slides Intelligenza Artificiale,
Vincenzo Cutello
12
Esempio:
 Il problema delle 8 regine;
Stati ??
Operatori ??
Obiettivo ??
Costo ??
Slides Intelligenza Artificiale,
Vincenzo Cutello
13
Esempi:
 Criptoaritmetica undici + dieci = ventuno;
 Missionari e cannibali (capre e cavoli);
Per ognuno:
Stati – Operatori – Obiettivo - Costo
Slides Intelligenza Artificiale,
Vincenzo Cutello
14
Esempio:
 SOKOBAN;
Stati ??
Operatori ??
Obiettivo ??
Costo ??
Slides Intelligenza Artificiale,
Vincenzo Cutello
15
Algoritmi di ricerca
Idea di base:
offline, esplorazione simulata dello spazio degli stati tramite la
generazione di successori di stati già esplorati
function GENERAL-SEARCH(problem,strategy)
returns una soluzione, o un fallimento
inizializza l’albero di ricerca usando lo stato iniziale del problema
loop do
if non ci sono candidati per l’espansione
then return fallimento
scegli una foglia per l’espansione in accordo alla strategia
if il nodo contiene uno stato obiettivo
then return la soluzione corrispondente
else espandi il nodo, aggiungendo i nodi risultanti all’albero di ricerca
end
Slides Intelligenza Artificiale,
Vincenzo Cutello
16
Esempio di ricerca generale
Whitehorse
Dawson
Whitehorse
Regina
Edmonton
Vancouver
Winnipeg
Churchill
Calgary
Ottawa
Slides Intelligenza Artificiale,
Vincenzo Cutello
Churchill
Toronto
17
Implementazione di algoritmi di
ricerca
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
Slides Intelligenza Artificiale,
Vincenzo Cutello
18
Implementazione: stati vs. nodi
 Uno stato è una (rappresentazione di) una configurazione fisica
 Un nodo è una struttura dati che costituisce una parte dell’albero di
ricerca Include genitore, figli, profondità o costo del cammino g(x)
 Gli stati non hanno genitori, figli, profondità, o costo del cammino !
genitori
5
4
6
1
8
7
3
2
profondità = 6
g=6
stato
figli
La funzione EXPAND crea nuovi nodi, riempendo i vari campi e usando
OPERATORS (o SuccessorsFn) del problema per creare gli stati corrispondenti.
Slides Intelligenza Artificiale,
Vincenzo Cutello
19
Strategie di ricerca
 Una strategia è definita stabilendo l’ordine di espansione dei nodi.
 Le strategie sono valutate mediante i seguenti criteri:
completezza – la soluzione viene sempre trovata se questa esiste ?
complessità temporale – numero di nodi generati/espansi
complessità spaziale – massimo numero di nodi in memoria
ottimalità – viene sempre trovata la soluzione meno costosa ?
 La complessità spaziale e temporale sono misurate in termini di
b – massimo fattore di ramificazione dell’albero di ricerca
d – profondità della soluzione meno costosa
m – massima profondità dello spazio degli stati (potrebbe essere infinito)
Slides Intelligenza Artificiale,
Vincenzo Cutello
20
Strategie di ricerca non informata
Le strategie non informate usano soltanto l’informazione
disponibile nella definizione del problema





Ricerca breadth-first
Ricerca a costo uniforme
Ricerca depth-first
Ricerca depth-first limitata
Ricerca iterativa
Slides Intelligenza Artificiale,
Vincenzo Cutello
21
Ricerca breadth-first
Espandi il nodo meno profondo non espanso
Implementazione:
QUEUEINGFN = metti i nodi successori alla
fine della coda
Slides Intelligenza Artificiale,
Vincenzo Cutello
22
Ricerca breadth-first
Whitehorse
Dawson
Whitehorse Churchill
Vancouver
Edmonton
Whitehorse Calgary Whitehorse Calgary Churchill Winnipeg
Slides Intelligenza Artificiale,
Vincenzo Cutello
23
Proprietà della ricerca breadth-first
Completa ??
 Si (se b è finita)
Tempo ??
 1+b+b2+b3+…+bd =O(bd), cioè, esponenziale in d
Spazio ??
 O(bd) (mantiene ogni nodo in memoria)
Ottimalità ??
 Si (se il costo = 1 ad ogni passo); non ottimale in
generale
Lo spazio è il grande problema; si possono facilmente
generare nodi a 1MB/sec così 24hrs = 86GB
Slides Intelligenza Artificiale,
Vincenzo Cutello
24
Dawson
Canada con costi in Km
450
2650
Whitehorse
Churchill
St. John’s
1600
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
25
Ricerca a costo uniforme
Espandi il nodo meno costoso non ancora
espanso
Implementazione:
QUEUEINGFN = inserisce i nodi in ordine
crescente rispetto al costo del cammino
Slides Intelligenza Artificiale,
Vincenzo Cutello
26
Ricerca a costo uniforme
Whitehorse
450
1650
1600
Dawson
450
Whitehorse
2650
Churchill
Edmonton
1600
Calgary
450
Vancouver
1350
Winnipeg
Slides Intelligenza Artificiale,
Vincenzo Cutello
1250
Churchill
Whitehorse
27
Proprietà della ricerca a costo uniforme
Completa ??
 Si, se il costo di ogni passo è ≥ ε
Tempo ??
 # di nodi con g ≤ costo della soluzione ottima
Spazio ??
 # di nodi con g ≤ costo della soluzione ottima
Ottimalità ??
 Si
Slides Intelligenza Artificiale,
Vincenzo Cutello
28
Ricerca depth-first
Espandi il nodo più profondo non ancora
espanso
Implementazione:
QUEUEINGFN = inserisce i nodi all’inizio
della coda
Slides Intelligenza Artificiale,
Vincenzo Cutello
29
Ricerca depth-first
Whitehorse
Dawson
Whitehorse
Dawson
Edmonton
Vancouver
Churchill
Edmonton
Vancouver
Slides Intelligenza Artificiale,
Vincenzo Cutello
30
Ricerca Depth-first: Problemi
 La ricerca depth-first può eseguire percorsi
con infiniti cicli
 Necessitiamo di uno spazio di ricerca finito e
non ciclico (o un controllo sulla ripetizione
degli stati)
Slides Intelligenza Artificiale,
Vincenzo Cutello
31
Proprietà della ricerca depth-first
Completezza ??
 No: fallisce in spazi con profondità infinita, spazi con cicli
 Evitando la ripetizione degli stati attraverso il cammino 
completezza in spazi finiti
Tempo ??
 O(bm): terribile se m è molto più grande di d ma se le
soluzioni sono dense, potrebbe essere più veloce della
breadth-first
Spazio ??
 O(bm), cioè, spazio lineare !
Ottimalità ??
 No
Slides Intelligenza Artificiale,
Vincenzo Cutello
32
Ricerca a profondità limitata
= ricerca depth-first con limite di profondità l
Implementazione:
I nodi a profondità h non hanno successori
Slides Intelligenza Artificiale,
Vincenzo Cutello
33
Ricerca iterativa
function ITERATIVE-DEEPENING-SEARCH(problema)
returns una soluzione
input: problema, un problema
for h  0 to ∞ do
risultato  DEPTH-LIMITED-SEARCH(problem, h)
if P(risultato)
then return risultato
end
Slides Intelligenza Artificiale,
Vincenzo Cutello
34
Ricerca iterativa h=0
Whitehorse
Slides Intelligenza Artificiale,
Vincenzo Cutello
35
Ricerca iterativa h=1
Whitehorse
Dawson
Edmonton
Slides Intelligenza Artificiale,
Vincenzo Cutello
Vancouver
36
Ricerca iterativa h=2
Whitehorse
Dawson
Edmonton
Vancouver
Whitehorse Churchill Whitehorse Calgary Churchill Winnipeg Whitehorse Calgary
Slides Intelligenza Artificiale,
Vincenzo Cutello
37
Proprietà della ricerca iterativa
Completezza ??
 Si
Tempo ??
 (d+1)b0+db1+(d-1)b2+…+bd=O(bd)
Spazio ??
 O(bd)
Ottimalità ??
 Si, se il costo di un passo = 1
 Può essere modificata per esplorare alberi a costo
uniforme
Slides Intelligenza Artificiale,
Vincenzo Cutello
38
Riassunto
 Solitamente la formulazione del problema
richiede astrazione dai dettagli del mondo
reale per definire uno stato degli spazi che
può essere facilmente esplorato
 Varietà di strategie di ricerca non informata
 La ricerca iterativa usa spazio lineare e
non molto più tempo degli altri algoritmi di
ricerca non informata
Slides Intelligenza Artificiale,
Vincenzo Cutello
39