Intelligenza Artificiale 1
Gestione della conoscenza
lezione 4
Prof. M.T. PAZIENZA
a.a. 2000-2001
Tipi di problemi
• Problemi a stato singolo (deterministico,
accessibile)
• Problemi a stati multipli (deterministico,
inaccessibile)
• Problemi di contingenza
(nondeterministico, inaccessibile)
• Problemi di esplorazione (spazio degli stati
sconosciuto)
Classi di problemi
Problemi giocattolo
(Rompicapo dell’8 – Mondo dell’aspirapolvere)
Problemi del mondo reale
(Ricerca di itinerario)
Rompicapo dell’8
Operatore: lo tessera vuota cambia posto con
la tessera alla sua sinistra
Formulazione di problemi
a stato singolo
Un tale problema è definito da 4 caratteristiche:
1. Stato iniziale
2. Operatore / funzione successore S(x)
3. Test obiettivo
4. Funzione costo cammino
Una soluzione è una sequenza di operatori che
conducono dallo stato iniziale ad uno stato obiettivo
Rompicapo dell’8
Formulazione del problema
Stati: posizione di ciascuna delle 8 tessere +
tessera vuota
Operatori: muovere la tessera vuota a sinistra,
destra, sopra, sotto (nessun salto ammesso)
Test obiettivo: configurazione finale
Costo di cammino: ciascun passo costa 1
(costo del cammino = lunghezza del
cammino)
Classi di problemi
Problemi giocattolo
(Rompicapo dell’8 – Mondo dell’aspirapolvere)
Problemi del mondo reale
(Ricerca di itinerario)
Mondo dell’aspirapolvere
Spazio degli stati
Archi/azioni: L=spostati a sn, R=spostati a dx,
S=aspira
Formulazione di problemi
a stato singolo
Un tale problema è definito da 4 caratteristiche:
1. Stato iniziale
2. Operatore / funzione successore S(x)
3. Test obiettivo
4. Funzione costo cammino
Una soluzione è una sequenza di operatori che
conducono dallo stato iniziale ad uno stato obiettivo
Mondo dell’aspirapolvere
semplificato
Agente conosce la propria posizione e le posizioni
di tutte le parti con sporcizia; aspira bene.
Stati: uno degli stati di figura
Operatori: spostati a sn, spostati a dx, aspira
Test obiettivo: non lasciare sporcizia nei quadrati
Costo di cammino: ciascuna azione costa 1
Soluzione: da un qualsiasi stato di partenza seguire
le frecce fino ad uno stato obiettivo
Formulazione di problemi
a stati multipli
Un tale problema è definito da 4 caratteristiche:
1. Insieme di stati iniziali
2. Insieme di operatori / funzione successore S(x) (per
ciascuna azione viene specificato l’insieme di stati
raggiunti da qualsiasi stato considerato. Un cammino
collega insiemi di stati)
3. Test obiettivo
4. Funzione costo cammino
Una soluzione è un cammino che conduce ad un insieme
di stati che sono tutti stati obiettivo.
Spazio dell’insieme di stati
Mondo dell’aspirapolvere senza sensori
In qualsiasi istante l’agente si trova in un insieme di
stati ma non sa in quale stato di quell’insieme sia
Mondo dell’aspirapolvere senza sensori
L’aspirapolvere non ha alcun sensore e deve
raccogliere tutta la sporcizia
Insiemi di stati: sottoinsiemi di stati della figura
Operatori: spostati a sn, spostati a dx, aspira
Test obiettivo: ogni stato dell’insieme degli stati
non contiene sporcizia
Costo di cammino: ciascuna azione costa 1
Soluzione: dall’insieme iniziale degli stati (tutti)
seguire le frecce fino a raggiungere un insieme
di stati senza sporcizia
Classi di problemi
Problemi giocattolo
(Rompicapo dell’8 – Mondo dell’aspirapolvere)
Problemi del mondo reale
(Ricerca di itinerario)
Ricerca di itinerario
Trovare un itinerario da Arad a Bucarest
Ricerca di itinerario
Costo del cammino proporzionale al numero
di miglia totali del percorso (aggiunta
logoramento )
Costo di ricerca dipende da ambiente: se
statico, costo zero (perché la misura delle
prestazioni è indipendente dal tempo), se
semidinamico (urgenza di giungere a
Bucarest) deliberazioni più lunghe
costeranno di più.
Costo totale = miglia + secondi
Ricerca di itinerario
Ricerca di itinerario
Ricerca di itinerario