11

INTELLIGENZA ARTIFICIALE: INTELLIGENZA ARTIFICIALE: INTRODUZIONEINTRODUZIONE

22

INTELLIGENZA ARTIFICIALE: DefinizioneINTELLIGENZA ARTIFICIALE: Definizione

•• Il campo dell’Intelligenza Artificiale o AI (dall’inglese Il campo dell’Intelligenza Artificiale o AI (dall’inglese ArtificialArtificial Intelligence) tenta di capire e costruire entità Intelligence) tenta di capire e costruire entità intelligenti.intelligenti.

•• Nata nel 1956. Quale definizione di Intelligenza? Quale Nata nel 1956. Quale definizione di Intelligenza? Quale definizione di Intelligenza Artificiale?definizione di Intelligenza Artificiale?

•• Alcune definizioni:Alcune definizioni:–– È lo studio di come far fare ai calcolatori cose che, ora come oÈ lo studio di come far fare ai calcolatori cose che, ora come ora, ra,

gli esseri umani fanno megliogli esseri umani fanno meglio(definizione transitoria...., scacchi.....)(definizione transitoria...., scacchi.....)

–– È la costruzione di un manipolatore di simboliÈ la costruzione di un manipolatore di simboli che è in grado di che è in grado di soddisfare il test di soddisfare il test di TuringTuring

33

TEST DI TURINGTEST DI TURING

•• Interazione con un terminale in cui io posso fare domande e otteInterazione con un terminale in cui io posso fare domande e ottengo ngo risposte. Dall'altra parte c’è o una persona o un computer. Se drisposte. Dall'altra parte c’è o una persona o un computer. Se dopo opo 30 minuti non sono in grado di distinguere fra persona e compute30 minuti non sono in grado di distinguere fra persona e computer....r....

•• Il computer deve avere le seguenti capacità:Il computer deve avere le seguenti capacità:–– Elaborazione del linguaggio naturale;Elaborazione del linguaggio naturale;–– Rappresentazione della conoscenza;Rappresentazione della conoscenza;–– Ragionamento automatico;Ragionamento automatico;–– Apprendimento automatico.Apprendimento automatico.

•• TEST DI TURING GLOBALETEST DI TURING GLOBALE•• (interazioni fisiche dirette)(interazioni fisiche dirette)

–– Robotica.Robotica.–– Visione artificiale;Visione artificiale;

44

IA DEBOLE ED IA FORTEIA DEBOLE ED IA FORTE

AI deboleAI debole: :

è possibile costruire macchine in modo che agiscano è possibile costruire macchine in modo che agiscano come come se se fossero intelligenti?fossero intelligenti?

•• Argomenti contro:Argomenti contro:–– Ci sono cose che i computer non possono fare indipendentemente Ci sono cose che i computer non possono fare indipendentemente

da come li si programmi (incompletezza dei sistemi formali);da come li si programmi (incompletezza dei sistemi formali);

–– Fallimento nel lungo periodo (apprendimento);Fallimento nel lungo periodo (apprendimento);

–– L’effettiva costruzione di programmi appropriati non è fattibileL’effettiva costruzione di programmi appropriati non è fattibile(complessità della conoscenza).(complessità della conoscenza).

55

IA FORTEIA FORTE

•• E`E` possibile costruire macchine che pensino possibile costruire macchine che pensino intelligentemente? (che abbiano intelligentemente? (che abbiano menti coscienti realimenti coscienti reali?) ?)

•• Solleva alcuni dei problemi concettuali più difficili di tutta Solleva alcuni dei problemi concettuali più difficili di tutta la filosofia.la filosofia.

•• I fondamenti dell’IA sono:I fondamenti dell’IA sono:–– Filosofia;Filosofia;

–– Matematica (logica);Matematica (logica);

–– Psicologia;Psicologia;

–– Linguistica;Linguistica;

–– Ingegneria dei calcolatori.Ingegneria dei calcolatori.

66

STORIA DELL’IA IN PERIODISTORIA DELL’IA IN PERIODI

•• (1943(1943--1956) 1956) –– La gestazione dell’ IALa gestazione dell’ IA

–– reti neurali, programmi per il gioco degli scacchi, dimostratorireti neurali, programmi per il gioco degli scacchi, dimostratori di di teoremi;teoremi;

•• (1952(1952--1969) 1969) –– Entusiasmo Iniziale, Grandi Aspettative: prima il calcolatore erEntusiasmo Iniziale, Grandi Aspettative: prima il calcolatore era a

solo concepito come elaboratore aritmetico. solo concepito come elaboratore aritmetico. GeneralGeneral ProblemProblemSolver, Programmi per il Gioco della Dama in torneo, Reti NeuralSolver, Programmi per il Gioco della Dama in torneo, Reti Neurali, i, Il linguaggio LISP.Il linguaggio LISP.

•• Due filoni:Due filoni:–– McCarthyMcCarthy ((StanfordStanford) Logica) Logica

–– MinskyMinsky (MIT) Visione anti(MIT) Visione anti--logica, logica, MicromondiMicromondi

77

•• (1966(1966--1974) 1974) –– Una dose di realtàUna dose di realtà

–– Alcuni programmi non erano davvero Alcuni programmi non erano davvero competenticompetenti (ELIZA, (ELIZA, traduzioni puramente sintattiche), altri erano intrattabili (esptraduzioni puramente sintattiche), altri erano intrattabili (esplosione losione combinatoria). Le reti neurali erano inadeguate.combinatoria). Le reti neurali erano inadeguate.

•• (1969(1969--1979) 1979) –– Sistemi basati sulla conoscenza: la chiave del potere?Sistemi basati sulla conoscenza: la chiave del potere?

–– Conoscenza intensiva su un dominio di ampiezza limitata. SistemiConoscenza intensiva su un dominio di ampiezza limitata. SistemiEsperti.Esperti.

STORIA DELL’IA IN PERIODISTORIA DELL’IA IN PERIODI

88

•• (1980(1980--1988) 1988) –– L’AI diventa un’industriaL’AI diventa un’industria

–– Sistemi Esperti commerciali di successo;Sistemi Esperti commerciali di successo;

–– Progetto quinta generazione giapponese (1981);Progetto quinta generazione giapponese (1981);

–– Compagnie per lo sviluppo di sistemi di AI;Compagnie per lo sviluppo di sistemi di AI;

–– Fondi per la ricerca.Fondi per la ricerca.

•• (1986(1986--oggi) oggi) –– Il ritorno delle reti neuraliIl ritorno delle reti neurali

–– Algoritmo di apprendimento con propagazione all’indietro.Algoritmo di apprendimento con propagazione all’indietro.

–– Delusione sui sistemi basati sulla conoscenza.Delusione sui sistemi basati sulla conoscenza.

STORIA DELL’IA IN PERIODISTORIA DELL’IA IN PERIODI

99

EVENTI RECENTI E SVILUPPI FUTURIEVENTI RECENTI E SVILUPPI FUTURI

•• Più realismo e nuova consapevolezza.Più realismo e nuova consapevolezza.

•• Superamento dei Superamento dei micromondimicromondi;;

•• AI in molti campi pratici quali pianificazione, AI in molti campi pratici quali pianificazione, schedulingscheduling, , agenti intelligenti distribuiti;agenti intelligenti distribuiti;

•• Ulteriori aree :Ulteriori aree :–– Internet, conoscenza troppo ampia che va filtrata in modo Internet, conoscenza troppo ampia che va filtrata in modo

intelligente.intelligente.

1010

INTELLIGENZA ARTIFICIALE:INTELLIGENZA ARTIFICIALE:DUE CORRENTIDUE CORRENTI

•• MACCHINE INTELLIGENTIMACCHINE INTELLIGENTI: : –– si costruiscono programmi che raggiungono un alto livello di si costruiscono programmi che raggiungono un alto livello di

competenza nella conoscenza di problemi particolaricompetenza nella conoscenza di problemi particolari–– approccio approccio ingegneristicoingegneristico–– Non ci si occupa di simulare l'attività umana di ragionamento, mNon ci si occupa di simulare l'attività umana di ragionamento, ma a

di emularla selettivamente.di emularla selettivamente.

•• SCIENZA COGNITIVASCIENZA COGNITIVA: : –– si cerca di modellare il comportamento umano e i suoi processi dsi cerca di modellare il comportamento umano e i suoi processi di i

informazioneinformazione–– approccio di filosofi, psicologi, linguisti, biologi.approccio di filosofi, psicologi, linguisti, biologi.–– Il computer è un mezzo di sperimentazione.Il computer è un mezzo di sperimentazione.–– Siamo ancora lontani dalla costruzione della macchina Siamo ancora lontani dalla costruzione della macchina

"intelligente", per cui ci si è limitati per adesso a problemi p"intelligente", per cui ci si è limitati per adesso a problemi più iù semplici e trattabili.semplici e trattabili.

1111

CATEGORIE DI ATTIVITA’ DELLA IACATEGORIE DI ATTIVITA’ DELLA IA

•• Attività Normali (ovvero come è possibile che cose così Attività Normali (ovvero come è possibile che cose così semplici siano così complicate?):semplici siano così complicate?):

•• Processo del linguaggio naturale:Processo del linguaggio naturale:–– Comprensione;Comprensione;

–– Generazione;Generazione;

–– Traduzione.Traduzione.

•• Percezione:Percezione:–– Visione;Visione;

–– Linguaggio parlato.Linguaggio parlato.

–– Ragionamento di buon sensoRagionamento di buon senso

–– Controllo di RobotControllo di Robot

1212

•• Attività Formali:Attività Formali:–– Giochi:Giochi:–– Scacchi;Scacchi;–– Dama Dama –– Matematica e Logica:Matematica e Logica:–– Prova automatica di Teoremi;Prova automatica di Teoremi;–– Geometria;Geometria;–– Calcolo differenziale;Calcolo differenziale;–– Dimostrazione di proprietà di programmi.Dimostrazione di proprietà di programmi.

CATEGORIE DI ATTIVITA’ DELLA IACATEGORIE DI ATTIVITA’ DELLA IA

1313

•• Attività Specializzate:Attività Specializzate:–– IngegneriaIngegneria–– Progetto;Progetto;–– Ricerca di guasti (diagnosi);Ricerca di guasti (diagnosi);–– Pianificazione della produzione;Pianificazione della produzione;–– Programmazione automaticaProgrammazione automatica–– Diagnosi medicaDiagnosi medica–– Analisi finanziariaAnalisi finanziaria–– Analisi scientifica ecc.Analisi scientifica ecc.

CATEGORIE DI ATTIVITA’ DELLA IACATEGORIE DI ATTIVITA’ DELLA IA

1414

LA DISCIPLINA DELL’IALA DISCIPLINA DELL’IA

•• L'Intelligenza Artificiale è una disciplina giovane e non L'Intelligenza Artificiale è una disciplina giovane e non ancora assestata.ancora assestata.

•• Dopo una fase empirica si sono trovati alcuni Dopo una fase empirica si sono trovati alcuni principi principi astrattiastratti comuni.comuni.

•• Intelligenza Artificiale ha tre grosse aree:Intelligenza Artificiale ha tre grosse aree:–– Strategie di RicercaStrategie di Ricerca–– Rappresentazione della ConoscenzaRappresentazione della Conoscenza–– ApplicazioniApplicazioni–– Visione simbolica e dichiarativa. Visione simbolica e dichiarativa.

•• Alternative (sistemi subAlternative (sistemi sub--simbolici): simbolici): –– ConnessionismoConnessionismo, reti neurali;, reti neurali;–– BrooksBrooks e la costruzione di piccoli sistemi artificiali reattivi (insete la costruzione di piccoli sistemi artificiali reattivi (insetti).ti).

1515

•• Noi seguiremo principalmente la visione simbolica e Noi seguiremo principalmente la visione simbolica e dichiarativa (Intelligenza Artificiale "classica").dichiarativa (Intelligenza Artificiale "classica").

•• I due approcci possono essere integrati.I due approcci possono essere integrati.

•• SISTEMI BASATI SULLA CONOSCENZASISTEMI BASATI SULLA CONOSCENZA–– Un sistema di Intelligenza Artificiale generalmente esamina un Un sistema di Intelligenza Artificiale generalmente esamina un

largo numero di possibilità e costruisce dinamicamente una largo numero di possibilità e costruisce dinamicamente una soluzione.soluzione.

–– "La potenza di un programma intelligente nel risolvere un "La potenza di un programma intelligente nel risolvere un problema dipende primariamente dalla quantità e qualità di problema dipende primariamente dalla quantità e qualità di conoscenza che possiede su tale problema". (conoscenza che possiede su tale problema". (FeigenbaumFeigenbaum))

LA DISCIPLINA DELL’IALA DISCIPLINA DELL’IA

1616

SISTEMI BASATI SULLA CONOSCENZASISTEMI BASATI SULLA CONOSCENZA

•• Il programma non è un insieme di istruzioni immutabili che Il programma non è un insieme di istruzioni immutabili che rappresentano la soluzione del problema, ma un ambiente rappresentano la soluzione del problema, ma un ambiente in cui:in cui:–– rappresentarerappresentare–– utilizzareutilizzare–– modificare modificare –– una base di conoscenza.una base di conoscenza.

•• PRINCIPI ARCHITETTURALIPRINCIPI ARCHITETTURALI–– Ogni sistema basato sulla conoscenza deve riuscire ad esprimere Ogni sistema basato sulla conoscenza deve riuscire ad esprimere

due tipi di conoscenza:due tipi di conoscenza:–– Conoscenza sul dominio dell'applicazione (COSA);Conoscenza sul dominio dell'applicazione (COSA);–– Conoscenza su COME utilizzare tale conoscenza per risolvere Conoscenza su COME utilizzare tale conoscenza per risolvere

problemi problemi -- CONTROLLO. CONTROLLO.

1717

PROGRAMMA = PROGRAMMA = CONOSCENZA + CONTROLLOCONOSCENZA + CONTROLLO

•• Questi due tipi di conoscenza dovrebbero essere tenuti Questi due tipi di conoscenza dovrebbero essere tenuti SEPARATI: SEPARATI: –– ALTA MODULARITÀ ALTA MODULARITÀ –– PROGRAMMAZIONE DICHIARATIVAPROGRAMMAZIONE DICHIARATIVA

•• La conoscenza sul problema è espressa La conoscenza sul problema è espressa indipendentemente dal suo utilizzo (COSA non indipendentemente dal suo utilizzo (COSA non COME);COME);

•• Alta modularità e flessibilità;Alta modularità e flessibilità;

1818

•• I moderni linguaggi e AMBIENTI per Intelligenza Artificiale I moderni linguaggi e AMBIENTI per Intelligenza Artificiale tendono a riprodurre tale schema;tendono a riprodurre tale schema;

•• Definire un ambiente (linguaggio) in tale schema significa Definire un ambiente (linguaggio) in tale schema significa definire come il programmatore può esprimere la definire come il programmatore può esprimere la conoscenza e quale tipo di controllo può utilizzare;conoscenza e quale tipo di controllo può utilizzare;

•• Problematiche di Problematiche di rappresentazionerappresentazione della conoscenza;della conoscenza;

•• Problematiche di organizzazione del problema e Problematiche di organizzazione del problema e strategie strategie di controllodi controllo

PROGRAMMA = PROGRAMMA = CONOSCENZA + CONTROLLOCONOSCENZA + CONTROLLO

1919

DICHIARATIVO DICHIARATIVO -- PROCEDURALEPROCEDURALE•• Esempio: Tracciare una circonferenzaEsempio: Tracciare una circonferenza

–– DICHIARATIVODICHIARATIVO–– La circonferenza è l'insieme dei punti equidistanti da un dato pLa circonferenza è l'insieme dei punti equidistanti da un dato punto detto unto detto

centro.centro.–– PROCEDURALE PROCEDURALE –– Per tracciare una circonferenza ........Per tracciare una circonferenza ........

•• Esempio: Ordinamento di una lista Esempio: Ordinamento di una lista –– DICHIARATIVODICHIARATIVO–– Il risultato dell'ordinamento di una lista vuota è la lista vuotIl risultato dell'ordinamento di una lista vuota è la lista vuotaa–– Il risultato dell'ordinamento di una lista L è L' se la lista L'Il risultato dell'ordinamento di una lista L è L' se la lista L' è ordinata ed è è ordinata ed è

una permutazione di Luna permutazione di L–– PROCEDURALEPROCEDURALE–– Controlla prima se la lista è vuota; se sì dai come risultato laControlla prima se la lista è vuota; se sì dai come risultato la lista vuotalista vuota–– Altrimenti calcola una permutazione L' di L e controlla se è ordAltrimenti calcola una permutazione L' di L e controlla se è ordinata; se sì inata; se sì

termina dando come risultato L', altrimenti calcola un'altra pertermina dando come risultato L', altrimenti calcola un'altra permutazione mutazione di L di L etcetc........

2020

VANTAGGI DELL’APPROCCIO VANTAGGI DELL’APPROCCIO DICHIARATIVODICHIARATIVO

•• ALTO LIVELLO:ALTO LIVELLO:

–– è più semplice impostare il problema (catena di IF..THEN); è più semplice impostare il problema (catena di IF..THEN);

•• GENERALITÀ:GENERALITÀ:

–– posso usare la stessa conoscenza in differenti modi; posso usare la stessa conoscenza in differenti modi;

•• FLESSIBILITÀFLESSIBILITÀ

–– facile modifica, facile modifica, debuggingdebugging ecc. ecc.

–– cambio del controllocambio del controllo

2121

UNA NUOVA MACCHINA VIRTUALEUNA NUOVA MACCHINA VIRTUALE

2222

UNA NUOVA MACCHINA VIRTUALE UNA NUOVA MACCHINA VIRTUALE

ESEMPIOESEMPIO•• Semplicissimo problema di diagnostica:Semplicissimo problema di diagnostica:

–– prescrivere una medicina in base ai risultati di un esame di prescrivere una medicina in base ai risultati di un esame di laboratorio. laboratorio.

•• GOAL: GOAL: prescribeprescribe ((DrugDrug))–– cioè "prescrivere una medicina adeguata per un determinato cioè "prescrivere una medicina adeguata per un determinato

paziente".paziente".

2323

UNA NUOVA MACCHINA VIRTUALE UNA NUOVA MACCHINA VIRTUALE •• FATTI:FATTI:

gram(neggram(neg).).

not(allergic(antbnot(allergic(antb)).)).

•• REGOLE:REGOLE:–– R1: R1: gramgram ((negneg) ) →→ idid ((ecoliecoli).).

Se il risultato dell'esame è Se il risultato dell'esame è gramgram--negativonegativo allora l'identità è allora l'identità è enteriumenterium--colicoli

–– R2: R2: gramgram ((pospos) ) →→ idid ((strepstrep).).

Se il risultato dell'esame è Se il risultato dell'esame è gramgram--positivopositivo allora l'identità è allora l'identità è streptococcostreptococco

–– R3: R3: id(strepid(strep) OR ) OR id(bactid(bact) ) →→ ind(penind(pen).).

Se l'identità è streptococco o Se l'identità è streptococco o bacterobactero allora è bene indicare penicillinaallora è bene indicare penicillina

–– R4: R4: ind(Xind(X) AND not () AND not (allergic(Xallergic(X)) )) →→ prescribe(Xprescribe(X))

Se è bene indicare una certa medicina e il paziente non è allergSe è bene indicare una certa medicina e il paziente non è allergico a tale ico a tale medicina, allora si può prescrivere tale medicina al paziente medicina, allora si può prescrivere tale medicina al paziente

–– R5: R5: idid((ecoliecoli) ) →→ indind((antbantb).).

Se l'identità è Se l'identità è enteriumenterium--colicoli allora è bene indicare antibioticiallora è bene indicare antibiotici

2424

CONTROLLO BACKWARD CONTROLLO BACKWARD GRAFO AND/ORGRAFO AND/OR

Match R5 (X/antib)

Match R1

Act R1

Goal: prescribe(Drug)

prescribe(X)Match R4 (Drug/X)

ind(X) not allergic(X)

Act R4AND

Match R3 (X/pen)

SIind(pen) ind(antib)

Act R3Act R3

id(strep)

id(bact)id(strep)

Match R2

gram(pos)

Act R2

NO

NO

Act R5

id(ecoli)

id(ecoli)

gram(neg)

SI

2525

CONTROLLO FORWARD CONTROLLO FORWARD GRAFO AND/ORGRAFO AND/OR

FATTI: gram(neg) AND not allergic(antb)

gram(neg) not allergic(antb)Match R1

gram(neg)

Act R1

id(ecoli)

Match R5

id(ecoli)

Act R5

ind(antb)

Match R4

Match R4

ind(antb) AND not allergic(antb)

Act R5

prescribe(antb)

Match con goal

Drug = antb

2626

CONSIDERAZIONICONSIDERAZIONI•• I fatti iniziali sono molto numerosi e dunque è bene domandarli I fatti iniziali sono molto numerosi e dunque è bene domandarli

selettivamente all'utente quando necessario.selettivamente all'utente quando necessario.•• L'impostazione del problema preferibile è L'impostazione del problema preferibile è backwardbackward..•• askableaskable: : gramgram e e allergicallergic..

•• Esempio di sessione di lavoro:Esempio di sessione di lavoro:–– User: esecuzione User: esecuzione –– Sys: È la coltura Sys: È la coltura GramGram positiva ?positiva ?–– User: NO.User: NO.–– SysSys: È la coltura : È la coltura GramGram negativa?negativa?–– User: SI.User: SI.–– SysSys: Il paziente è allergico agli antibiotici ?: Il paziente è allergico agli antibiotici ?–– User: NO.User: NO.–– SysSys: Allora prescriverei una cura a base di antibiotici.: Allora prescriverei una cura a base di antibiotici.

2727

SESSIONE DI SPIEGAZIONESESSIONE DI SPIEGAZIONE–– SysSys: È la coltura : È la coltura GramGram positiva ?positiva ?–– User: User: WHY?WHY? < < perchèperchè è importante determinare tale informazione? è importante determinare tale informazione? –– SysSys: Tale informazione è di aiuto per determinare se (R1) l'identit: Tale informazione è di aiuto per determinare se (R1) l'identità à

dell'organismo è streptococco.dell'organismo è streptococco.–– User: User: WHY?WHY?–– Sys: Tale informazione è di aiuto Sys: Tale informazione è di aiuto perchèperchè per tale organismo è indicata la per tale organismo è indicata la

penicilinapenicilina ( R3 ).( R3 ).–– SysSys: ... Allora prescriverei una cura a base di antibiotici. : ... Allora prescriverei una cura a base di antibiotici. –– User: User: HOW?HOW? <come puoi concludere tale responso? <come puoi concludere tale responso? –– SysSys: Ho utilizzato la regola R4: ho prescritto antibiotici : Ho utilizzato la regola R4: ho prescritto antibiotici poichèpoichè sono sono

indicati per tale infezione (prem1) e il paziente non è allergicindicati per tale infezione (prem1) e il paziente non è allergico (prem2). o (prem2). –– User: User: HOW Premessa 1 ?HOW Premessa 1 ?

<come puoi concludere che sono indicati gli antibiotici? <come puoi concludere che sono indicati gli antibiotici? –– SysSys: Ho utilizzato la regola R5: sono indicati antibiotici : Ho utilizzato la regola R5: sono indicati antibiotici poichèpoichè l'organismo l'organismo

che ha causato l'infezione è che ha causato l'infezione è ecoliecoli..

2828

STRUTTURA ALGORITMICA: Parte 1aSTRUTTURA ALGORITMICA: Parte 1aprogram program prescribeprescribe(input,output);(input,output);var Answer: string[2]; var Answer: string[2]; prescpresc: : booleanboolean;;beginbeginpresc:=false;presc:=false;writewrite('e la coltura ('e la coltura GramGram Positiva?');Positiva?');read(Answerread(Answer););if Answer='if Answer='SiSi' then' thenbeginbeginwrite('il paziente è allergico alla penicillina?');write('il paziente è allergico alla penicillina?');read(Answerread(Answer););

if Answer='No' thenif Answer='No' thenbeginbeginwrite('allora prescriverei una cura a base di write('allora prescriverei una cura a base di penicillina');penicillina');

presc:=true;presc:=true;end;end;

end;end;

2929

STRUTTURA ALGORITMICA: Parte 2aSTRUTTURA ALGORITMICA: Parte 2aifif not not prescpresc thenthenbeginbeginwrite('colturawrite('coltura Gram Gram NegativaNegativa?');?');read(Answerread(Answer););

ifif Answer='Si' Answer='Si' thenthenbeginbeginwrite('il paziente è allergico write('il paziente è allergico agli antibiotici?');agli antibiotici?');read(Answer);read(Answer);

if Answer='No' thenif Answer='No' thenbeginbeginwrite('allora prescriverei una cura a base di write('allora prescriverei una cura a base di antibiotici');antibiotici');

presc:=true;presc:=true;end;end;

end;end;end;end;if not presc thenif not presc thenwrite('prescrizione write('prescrizione impossibileimpossibile'); end.'); end.

3030

Soluzione del problema come ricerca in Soluzione del problema come ricerca in uno spazio degli stati:uno spazio degli stati:

Gran parte dei problemi di Intelligenza Artificiale hanno la ricGran parte dei problemi di Intelligenza Artificiale hanno la ricerca (o erca (o controllo) come componente fondamentale.controllo) come componente fondamentale.I problemi si possono modellare come I problemi si possono modellare come Problemi diProblemi di RicercaRicerca in uno in uno spazio degli stati (spazio degli stati (StrategieStrategie di Ricercadi Ricerca).).

•• Spazio degli statiSpazio degli stati–– Lo spazio degli stati è l’insieme di tutti gli stati raggiungibiLo spazio degli stati è l’insieme di tutti gli stati raggiungibili dallo stato li dallo stato

iniziale con una qualunque sequenza di operatori.iniziale con una qualunque sequenza di operatori.

•• Lo Spazio degli Stati è Caratterizzato da:Lo Spazio degli Stati è Caratterizzato da:–– Uno Uno stato inizialestato iniziale in cui l’agente sa di trovarsi (non noto a priori);in cui l’agente sa di trovarsi (non noto a priori);

–– Un Un insieme di azioniinsieme di azioni possibili che sono disponibili da parte dell’agente possibili che sono disponibili da parte dell’agente (Operatori che trasformano uno stato in un altro o più formalmen(Operatori che trasformano uno stato in un altro o più formalmente una te una funzione successore S(X) che riceve in ingresso uno stato e restfunzione successore S(X) che riceve in ingresso uno stato e restituisce ituisce l’insieme degli stati raggiungibili).l’insieme degli stati raggiungibili).

–– Un Un camminocammino è una sequenza di azioni che conduce da uno stato a un è una sequenza di azioni che conduce da uno stato a un altro.altro.

3131

TEST: RAGGIUNGIMENTO DEL GOALTEST: RAGGIUNGIMENTO DEL GOAL•• La verifica può essere solo l’appartenenza dello stato raggiuntoLa verifica può essere solo l’appartenenza dello stato raggiunto

all’insieme dello stato (o degli stati) goal.all’insieme dello stato (o degli stati) goal.

•• A volte lo stato obiettivo può essere descritto in modo “astrattA volte lo stato obiettivo può essere descritto in modo “astratto” o” attraverso proprietà (si pensi allo stato di scacco matto).attraverso proprietà (si pensi allo stato di scacco matto).

•• Altri obiettivi (non solo raggiungere il goal, ma...):Altri obiettivi (non solo raggiungere il goal, ma...):–– trovare la sequenza di operatori che arrivano al goal;trovare la sequenza di operatori che arrivano al goal;

–– trovare tutte le soluzioni;trovare tutte le soluzioni;

–– trovare una soluzione ottima.trovare una soluzione ottima.

–– In quest’ultimo caso vuol dire che una soluzione può essere preIn quest’ultimo caso vuol dire che una soluzione può essere preferibile a feribile a un’altra.un’altra.

–– Una funzione Una funzione costo di camminocosto di cammino assegna un costo a un cammino (in assegna un costo a un cammino (in gran parte dei casi quale somma del costo delle azioni individuagran parte dei casi quale somma del costo delle azioni individuali lungo il li lungo il cammino).cammino).

3232

L’EFFICACIA DELLA RICERCAL’EFFICACIA DELLA RICERCA

•• Si riesce a trovare una soluzione?Si riesce a trovare una soluzione?

•• È una buona soluzione? (con basso costo di cammino È una buona soluzione? (con basso costo di cammino –– costo in costo in linea)linea)

•• Qual è il costo della ricerca? (tempo per trovare una soluzione Qual è il costo della ricerca? (tempo per trovare una soluzione –– costo costo fuori linea)fuori linea)

•• Costo totale di ricerca = costo di cammino + costo di ricerca.Costo totale di ricerca = costo di cammino + costo di ricerca.

•• Scegliere stati e azioni Scegliere stati e azioni L’importanza dell’astrazioneL’importanza dell’astrazione

3333

ESEMPIO: IL GIOCO DEL 8ESEMPIO: IL GIOCO DEL 8

•• Stati: posizione di ciascuna delle tessere;Stati: posizione di ciascuna delle tessere;

•• Operatori: lo spazio vuoto si sposta a destra, a sinistra, in alOperatori: lo spazio vuoto si sposta a destra, a sinistra, in alto e in to e in basso;basso;

•• Test obiettivo: descrizione dello stato finale;Test obiettivo: descrizione dello stato finale;

•• Costo di cammino: ciascun passo costa 1.Costo di cammino: ciascun passo costa 1.

3434

ESEMPIO: IL GIOCO DEL 8ESEMPIO: IL GIOCO DEL 8

I: 2 8 3 G: 1 2 3 1 6 4 8 4 7 5 7 6 5

I: 2 8 3 1 6 4 7 5

2 8 3 1 6 4 7 5

2 8 3 1 4 7 6 5

2 8 3 1 6 4

7 5

2 8 3 1 4 7 6 5

2 3 1 8 4 7 6 5

2 8 3 1 6 4 7 5

Stato iniziale Goal

3535

ESEMPIO: MISSIONARI E CANNIBALIESEMPIO: MISSIONARI E CANNIBALI

ESEMPIO:ESEMPIO:•• 3 missionari e 3 cannibali devono attraversare un fiume. C'è una3 missionari e 3 cannibali devono attraversare un fiume. C'è una sola sola

barca che può contenere al massimo due persone. Per evitare di barca che può contenere al massimo due persone. Per evitare di essere mangiati i missionari non devono mai essere meno dei essere mangiati i missionari non devono mai essere meno dei cannibali sulla stessa sponda (stati di fallimento).cannibali sulla stessa sponda (stati di fallimento).

•• Stato: sequenza ordinata di tre numeri che rappresentano il numeStato: sequenza ordinata di tre numeri che rappresentano il numero di ro di missionari, cannibali e barche sulla sponda del fiume da cui sonmissionari, cannibali e barche sulla sponda del fiume da cui sono o partiti. partiti.

•• Perciò lo stato iniziale è: (3,3,1) (nota l’importanza dell’astrPerciò lo stato iniziale è: (3,3,1) (nota l’importanza dell’astrazione).azione).

3636

ESEMPIO: MISSIONARI E CANNIBALIESEMPIO: MISSIONARI E CANNIBALI

•• Operatori: gli operatori devono portare in barca Operatori: gli operatori devono portare in barca –– 1 missionario, 1 cannibale, 1 missionario, 1 cannibale, –– 2 missionari, 2 missionari, –– 2 cannibali, 2 cannibali, –– 1 missionario 1 missionario –– 1 cannibale.1 cannibale.

•• Al più 5 operatori (grazie all’astrazione sullo stato scelta).Al più 5 operatori (grazie all’astrazione sullo stato scelta).

•• Test Obiettivo: Stato finale (0,0,0)Test Obiettivo: Stato finale (0,0,0)

•• Costo di cammino: numero di traversate.Costo di cammino: numero di traversate.

3737

SS EE NN DD ++

MM OO RR EE ==

MM OO NN EE YY

•• Operatori: sostituisci tutte le stesse lettere con una cifra cheOperatori: sostituisci tutte le stesse lettere con una cifra che non non compare nel rompicapo;compare nel rompicapo;

•• Test obiettivo: il rompicapo contiene solo cifre e rappresenta uTest obiettivo: il rompicapo contiene solo cifre e rappresenta una na somma corretta;somma corretta;

•• Costo di cammino: 0Costo di cammino: 0

ESEMPIO: CRIPTOARITMETICAESEMPIO: CRIPTOARITMETICA

3838

IL PROBLEMA DELLE N REGINEIL PROBLEMA DELLE N REGINE

•• Inserire 8 regine su una scacchiera in modo che non si mangino.Inserire 8 regine su una scacchiera in modo che non si mangino.

•• Stati: qualsiasi configurazione da 0 a N regine sulla scacchieraStati: qualsiasi configurazione da 0 a N regine sulla scacchiera;;

•• Operatori: aggiungi una regina in un qualsiasi quadrato;Operatori: aggiungi una regina in un qualsiasi quadrato;

•• Test obiettivo: N regine sulla scacchiera, nessuna minacciata;Test obiettivo: N regine sulla scacchiera, nessuna minacciata;

•• Costo di cammino: zero.Costo di cammino: zero.

3939

ESEMPIO: LA TORRE DI HANOIESEMPIO: LA TORRE DI HANOI

(1)(1) (2) (3)(2) (3)

•• Spostare i cilindri concentrici da (1) a (3) nella stessa configSpostare i cilindri concentrici da (1) a (3) nella stessa configurazione urazione di (1) utilizzando eventualmente anche (2). Un cilindro più grandi (1) utilizzando eventualmente anche (2). Un cilindro più grande non de non può essere inserito su un cilindro più piccolo.può essere inserito su un cilindro più piccolo.

4040

ALTRI ESEMPI ALTRI ESEMPI

•• Il problema del commesso viaggiatore:Il problema del commesso viaggiatore:–– Un commesso viaggiatore ha una lista di città che deve visitare Un commesso viaggiatore ha una lista di città che deve visitare

tutte una sola volta. Vi sono strade dirette fra ogni coppia di tutte una sola volta. Vi sono strade dirette fra ogni coppia di città. città. Si trovi la strada più breve che il commesso deve seguire per Si trovi la strada più breve che il commesso deve seguire per compiere un viaggio completo che inizi e termini in una qualsiascompiere un viaggio completo che inizi e termini in una qualsiasi i delle città.delle città.

–– (esplosione combinatoria, per 10 città è 10!)(esplosione combinatoria, per 10 città è 10!)

•• Il problema della scimmia e la banana:Il problema della scimmia e la banana:–– Afferrare una banana appesa al soffitto (avendo a disposizione Afferrare una banana appesa al soffitto (avendo a disposizione

una sedia e bastone).una sedia e bastone).

4141

ESEMPIO: CAPRA, LUPO E CAVOLOESEMPIO: CAPRA, LUPO E CAVOLO

•• Portare capra, lupo e cavolo dall'altra parte senza che si mangiPortare capra, lupo e cavolo dall'altra parte senza che si mangino (si no (si mangiano se rimangono assieme senza il conducente della barca). mangiano se rimangono assieme senza il conducente della barca). Nella barca se ne può trasportare uno solo alla volta.Nella barca se ne può trasportare uno solo alla volta.

•• Soluzione:Soluzione:–– Porta la capra sull'altra sponda;Porta la capra sull'altra sponda;–– Torna indietroTorna indietro–– Porta il cavolo sull'altra spondaPorta il cavolo sull'altra sponda–– Porta indietro la capraPorta indietro la capra–– Porta il lupo sull'altra spondaPorta il lupo sull'altra sponda–– Torna indietroTorna indietro–– Porta la capra sull'altra spondaPorta la capra sull'altra sponda

4242

SPAZIO DI RICERCA MOLTO AMPIOSPAZIO DI RICERCA MOLTO AMPIO

•• Giochi: scacchi Giochi: scacchi

•• Le parole crociateLe parole crociate

R R

T U O

E R A

4343

Schema Schema architetturalearchitetturale::SISTEMA DI PRODUZIONISISTEMA DI PRODUZIONI

•• Insieme di Operatori (regole);Insieme di Operatori (regole);

•• Uno o più database (Memorie di lavoro);Uno o più database (Memorie di lavoro);

•• Strategia di Controllo.Strategia di Controllo.

•• MODULARITÀ MODULARITÀ -- FLESSIBILITÀFLESSIBILITÀ

•• Operatori:Operatori:–– IF <pattern> THEN <body>IF <pattern> THEN <body>

–– non si chiamano per nome, ma si attivano in base al non si chiamano per nome, ma si attivano in base al patternpattern--matchingmatching

4444

ARCHITETTURA GENERALE:ARCHITETTURA GENERALE:

REGOLE(OPERATORI)

REGOLEAPPLICABILI

INTERPRETE O CONTROLLO

MEMORIA DI LAVORO

MatchingSelezioneEsecuzione

4545

DUE MODALITÀ DI "RAGIONAMENTO"DUE MODALITÀ DI "RAGIONAMENTO"

•• FORWARD O DATAFORWARD O DATA--DRIVEN: DRIVEN: –– La memoria di lavoro nella sua configurazione iniziale contieneLa memoria di lavoro nella sua configurazione iniziale contiene la la

conoscenza iniziale sul problema, cioè i fatti noti. conoscenza iniziale sul problema, cioè i fatti noti.

–– Le regole di produzione applicabili sono quelle il cui antecedenLe regole di produzione applicabili sono quelle il cui antecedente te può fare può fare matchingmatching con la memoria di lavoro (con la memoria di lavoro (FF--rulesrules). ).

–– Ogni volta che una regola viene selezionata ed eseguita nuovi faOgni volta che una regola viene selezionata ed eseguita nuovi fatti tti dimostrati vengono inseriti nella memoria di lavoro. dimostrati vengono inseriti nella memoria di lavoro.

–– Il procedimento termina con successo quando nella memoria di Il procedimento termina con successo quando nella memoria di lavoro viene inserito anche il goal da dimostrare (condizione dilavoro viene inserito anche il goal da dimostrare (condizione diterminazione).terminazione).

4646

DUE MODALITÀ DI "RAGIONAMENTO"DUE MODALITÀ DI "RAGIONAMENTO"

•• BACKWARD O GOALBACKWARD O GOAL--DRIVEN:DRIVEN:–– La memoria di lavoro iniziale contiene il goal (o i goal) del La memoria di lavoro iniziale contiene il goal (o i goal) del

problema. problema.

–– Le regole di produzione applicabili sono quelle il cui conseguenLe regole di produzione applicabili sono quelle il cui conseguente te può fare può fare matchingmatching con la memoria di lavoro (con la memoria di lavoro (BB--rulesrules). ).

–– Ogni volta che una regola viene selezionata ed eseguita, nuovi Ogni volta che una regola viene selezionata ed eseguita, nuovi subgoalssubgoals da dimostrare vengono inseriti nella memoria di lavoro. da dimostrare vengono inseriti nella memoria di lavoro.

–– Il procedimento termina con successo quando nella memoria di Il procedimento termina con successo quando nella memoria di lavoro vengono inseriti fatti noti (CONDIZIONE DI lavoro vengono inseriti fatti noti (CONDIZIONE DI TERMINAZIONE).TERMINAZIONE).

4747

QUANDO APPLICARE BACKWARD E QUANDO APPLICARE BACKWARD E QUANDO FORWARD ?QUANDO FORWARD ?

•• Esistono più Stati Iniziali o più Esistono più Stati Iniziali o più GoalsGoals??•• Quale è il numero medio di rami generati da un singolo nodo?Quale è il numero medio di rami generati da un singolo nodo?•• Quale è la modalità di ragionamento più naturale? (spiegazione Quale è la modalità di ragionamento più naturale? (spiegazione

all'utente) all'utente)

•• BIDIREZIONALE O MISTO:BIDIREZIONALE O MISTO:–– È la combinazione dei metodi descritti precedentemente; È la combinazione dei metodi descritti precedentemente;

–– La memoria di lavoro viene suddivisa in due parti l`una contenenLa memoria di lavoro viene suddivisa in due parti l`una contenente i fatti e te i fatti e l'altra i goals o subgoals; l'altra i goals o subgoals;

–– Si applicano simultaneamente FSi applicano simultaneamente F--rules e rules e BB--rulesrules alle due parti di memoria alle due parti di memoria di lavoro e si termina il procedimento con successo quando la padi lavoro e si termina il procedimento con successo quando la parte di rte di memoria di lavoro ricavata mediante memoria di lavoro ricavata mediante backwardbackward chainingchaining è uguale o un è uguale o un sottoinsieme di quella ricavata mediante (CONDIZIONE DI sottoinsieme di quella ricavata mediante (CONDIZIONE DI TERMINAZIONE). TERMINAZIONE).

4848

BIDIREZIONALE O MISTOBIDIREZIONALE O MISTO•• L’idea è quella di mantenere ed estendere un insieme di sequenzeL’idea è quella di mantenere ed estendere un insieme di sequenze

soluzioni parziali.soluzioni parziali.–– Un agente con diverse opzioni immediate di esito sconosciuto puòUn agente con diverse opzioni immediate di esito sconosciuto può

decidere cosa fare esaminando prima le differenti sequenze possidecidere cosa fare esaminando prima le differenti sequenze possibili di bili di azioni che conducono a stati di esito conosciuto scegliendo, poiazioni che conducono a stati di esito conosciuto scegliendo, poi, quella , quella migliore.migliore.

–– Il processo di cercare tale sequenza è chiamato Il processo di cercare tale sequenza è chiamato RICERCARICERCA..

–– È utile pensare al processo di ricerca come la costruzione di unÈ utile pensare al processo di ricerca come la costruzione di un albero di albero di ricerca i cui nodi sono stati e i cui rami sono operatori.ricerca i cui nodi sono stati e i cui rami sono operatori.

•• Un algoritmo di ricerca prende come input un problema e restituiUn algoritmo di ricerca prende come input un problema e restituisce sce una soluzione nella forma di una sequenza di azioni.una soluzione nella forma di una sequenza di azioni.

•• Una volta che viene trovata la soluzione, le azioni suggerite poUna volta che viene trovata la soluzione, le azioni suggerite possono ssono essere realizzate.essere realizzate.–– Questa fase è chiamata Questa fase è chiamata ESECUZIONEESECUZIONE..

4949

STRATEGIE DI RICERCASTRATEGIE DI RICERCA

•• I problemi che i sistemi basati sulla conoscenza devono risolverI problemi che i sistemi basati sulla conoscenza devono risolvere e sono nonsono non--deterministici (deterministici (don'don't t knowknow))

•• In un certo istante più azioni possono essere svolte (azioni: In un certo istante più azioni possono essere svolte (azioni: applicazioni di operatori)applicazioni di operatori)

•• STRATEGIA: è un'informazione sulla conoscenza che sarà applicataSTRATEGIA: è un'informazione sulla conoscenza che sarà applicatapotendone invocare molteplici. potendone invocare molteplici. Due possibilità Due possibilità –– Non utilizzare alcuna conoscenza sul dominio: applicare regole iNon utilizzare alcuna conoscenza sul dominio: applicare regole in modo n modo

arbitrario (strategie nonarbitrario (strategie non--informate) e fare una ricerca ESAUSTIVA.informate) e fare una ricerca ESAUSTIVA.–– Impraticabile per problemi di una certa complessità.Impraticabile per problemi di una certa complessità.

5050

STRATEGIE DI RICERCASTRATEGIE DI RICERCA

•• La strategia di controllo deve allora utilizzare La strategia di controllo deve allora utilizzare CONOSCENZA CONOSCENZA EURISTICAEURISTICA sul problema per la selezione degli operatori sul problema per la selezione degli operatori applicabiliapplicabili

•• Le strategie che usano tale conoscenza si dicono Le strategie che usano tale conoscenza si dicono STRATEGIE STRATEGIE INFORMATEINFORMATE

•• ESTREMO:ESTREMO:–– La conoscenza sulla strategia è così completa da selezionare ognLa conoscenza sulla strategia è così completa da selezionare ogni i

volta la regola CORRETTA volta la regola CORRETTA –– REGIME IRREVOCABILE (ALTRIMENTI PER TENTATIVI)REGIME IRREVOCABILE (ALTRIMENTI PER TENTATIVI)

5151

ALTRE CARATTERISTICHE DEL ALTRE CARATTERISTICHE DEL PROBLEMAPROBLEMA

•• IL SISTEMA È DECOMPONIBILE?IL SISTEMA È DECOMPONIBILE?

•• EsempioEsempio::

–– ∫∫X + 3X + sin X * cos X X + 3X + sin X * cos X dXdX

corrisponde alla somma degli integrali:corrisponde alla somma degli integrali:

–– ∫∫ X X dXdX + + ∫∫ 3X 3X dXdX + + ∫∫ sin X * cos X sin X * cos X dXdX

•• NON TUTTI I SISTEMI SONO DECOMPONIBILI:NON TUTTI I SISTEMI SONO DECOMPONIBILI:

–– Si possono avere sottoSi possono avere sotto--problemi interagenti, problemi interagenti,

5252

ESEMPIO: ESEMPIO: Il MONDO A BLOCCHI (planning)Il MONDO A BLOCCHI (planning)•• StatoStato InizialeIniziale::

handemptyhandempty. . clear(bclear(b).). clear(cclear(c).).

on(c,aon(c,a).). ontable(aontable(a).). ontable(bontable(b).).

•• OperatoriOperatori::clear(Xclear(X) ) →→ ontable(Xontable(X))

clear(Xclear(X) and ) and clear(Yclear(Y) ) →→ on(X,Yon(X,Y))

•• Goal:Goal:on(b,con(b,c) and ) and on(a,bon(a,b))

•• I due sottogoal I due sottogoal NON POSSONONON POSSONO ESSERE RISOLTI ESSERE RISOLTI SEPARATAMENTE perché interagiscono.SEPARATAMENTE perché interagiscono.

5353

ALTRE DOMANDEALTRE DOMANDE•• Esiste interazione con l'utente (spiegazione, conoscenza incomplEsiste interazione con l'utente (spiegazione, conoscenza incompleta)?eta)?

•• Si possono ignorare dei passi? (come nella dimostrazione di teorSi possono ignorare dei passi? (come nella dimostrazione di teoremi)emi)

•• Si possono annullare dei passi (8Si possono annullare dei passi (8--puzzle) o il sistema è puzzle) o il sistema è irricoverabileirricoverabile(scacchi)?(scacchi)?

•• SISTEMI DI PRODUZIONE MONOTONI:SISTEMI DI PRODUZIONE MONOTONI:–– L'applicazione di una regola R non invalida la possibilità di aL'applicazione di una regola R non invalida la possibilità di applicare pplicare

regole applicabili all'atto della selezione di R.regole applicabili all'atto della selezione di R.

•• NON C'È NECESSITÀ DI BACKTRCKINGNON C'È NECESSITÀ DI BACKTRCKING

5454

ESEMPIO:ESEMPIO:LOGICA DIMOSTRATORE DI TEOREMILOGICA DIMOSTRATORE DI TEOREMI

•• Fatto: Fatto: a.a.

a a →→ e. e.

a a →→ d. d.

d d →→ f.f.

•• Goal: Goal: f.f.

•• Non è il caso del mondo a blocchiNon è il caso del mondo a blocchi

•• Nota:Nota:–– Il formalismo dei sistemi di produzioni è generale (può rappreseIl formalismo dei sistemi di produzioni è generale (può rappresentare tutte ntare tutte

le funzioni computabili).le funzioni computabili).–– È possibile trasformare un sistema di produzione nonÈ possibile trasformare un sistema di produzione non--monotono in uno monotono in uno

monotono (formulazione di Green; formulazione di monotono (formulazione di Green; formulazione di KowalskiKowalski). La ). La trattazione, però, si complica notevolmente.trattazione, però, si complica notevolmente.

5555

ALTRI PROBLEMI ALTRI PROBLEMI •• Problema a stati singoli:Problema a stati singoli:

–– Lo stato è sempre accessibile.Lo stato è sempre accessibile.–– L’agente conosce esattamente che cosa produce ciascuna delle sueL’agente conosce esattamente che cosa produce ciascuna delle sue

azioni e può calcolare esattamente in quale stato sarà dopo qualazioni e può calcolare esattamente in quale stato sarà dopo qualunque unque sequenza di azioni.sequenza di azioni.

•• Problema a stati multipli:Problema a stati multipli:–– Lo stato non è completamente accessibile. L’agente deve ragionarLo stato non è completamente accessibile. L’agente deve ragionare su e su

possibili stati che potrebbe raggiungere.possibili stati che potrebbe raggiungere.–– In più: anche l’effetto delle azioni può essere sconosciuto o imIn più: anche l’effetto delle azioni può essere sconosciuto o imprevisto.previsto.–– Spesso risolvere questi problemi richiede capacità di rilevamentSpesso risolvere questi problemi richiede capacità di rilevamento durante o durante

la fase di esecuzione la fase di esecuzione →→ Agire nel mondo reale piuttosto che in un suo Agire nel mondo reale piuttosto che in un suo modello.modello.

Tratteremo estesamente solo problemi a stati singoli.Tratteremo estesamente solo problemi a stati singoli.