Intelligenza Artificiale - Parte A

Artificial Intelligence - Parte A

Riccardo La Marca

25 Febbraio 2020

Contents

1 Agenti Intelligenti 3

1.1 Agenti e ambienti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Comportarsi correttamente: il concetto di razionalità . . . . . . . . . . . . . . . . . . . . . 3

1.2.1 Razionalità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2.2 Onniscenza, apprendimento e autonomia . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 La natura degli ambienti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.1 Specificare un ambiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.2 Proprietà degli ambienti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.4 La struttura degli agenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.4.1 Programmi agente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.4.2 Agenti reattivi semplici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4.3 Agenti reattivi models-based . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4.4 Agenti goals-based . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.4.5 Agenti utility-based . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4.6 Agenti capaci di apprendere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Esplorazione degli spazi degli stati 12

2.1 Agenti risolutori di problemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.1.1 Problemi ben definiti e soluzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.2 La formulazione dei problemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2 Cercare soluzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2.1 Strutture dati per algoritmi di ricerca . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2.2 Misurare le prestazioni nella risoluzione di problemi . . . . . . . . . . . . . . . . . 17

2.3 Strategie di ricerca non informata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3.1 BFS - Breadth First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3.2 MinCost - Ricerca a costo uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3.3 DFS - Depth First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3.4 Ricerca a profondità limitata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3.5 Ricerca ad approfondimento iterativo . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3.6 Confronto tra le strategie di ricerca non informata . . . . . . . . . . . . . . . . . . 21

2.4 Strategie di ricerca informata o euristica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.4.1 Ricerca best-first greedy o golosa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.4.2 Ricerca A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.5 Funzioni euristiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.5.1 Effetto dell’accuratezza euristica sulle prestazioni . . . . . . . . . . . . . . . . . . . 28

2.5.2 Generare euristiche ammissibili da problemi rilassati . . . . . . . . . . . . . . . . . 30

3 Algoritmi a miglioramento iterativo 31

3.1 Algoritmi di ricerca locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.1.1 Steepest Ascent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.1.2 Varianti di SA: Hill Climbing con prima scelta e riavvio casuale . . . . . . . . . . . 33

1

3.1.3 Simulated annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.2 Algoritmi a ricerca evolutiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.2.1 Ricerca local beam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.2.2 Algoritmi genetici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4 Problemi di soddisfacimento dei vincoli 39

4.1 Definizione dei CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.1.1 Colorazione di una mappa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4.1.2 Job-shop scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.1.3 Varianti del formalismo CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.2 Ricerca con backtracking per CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.2.1 Propagazione dei vincoli: inferenza nei CSP . . . . . . . . . . . . . . . . . . . . . . 45

4.2.2 Backtracking con propagazione dei vincoli . . . . . . . . . . . . . . . . . . . . . . . 47

4.2.3 Backjumping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.3 Ricerca locale per problemi di soddisfacimento di vincoli . . . . . . . . . . . . . . . . . . . 50

5 Agenti logici 51

5.1 Agenti basati sulla conoscenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.2 Il mondo del wumpus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.3 Logica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.4 Logica proposizionale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.4.1 Sintassi della logica proposizionale . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.4.2 Semantica della logica proposizionale . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.4.3 Una semplice knowledge base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.4.4 Una semplice procedura di inferenza . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.5 Dimostrazione di teoremi nella logica proposizionale . . . . . . . . . . . . . . . . . . . . . 61

5.5.1 Inferenze e dimostrazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.5.2 Dimostrazione per risoluzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5.5.3 Clausole di Horn e clausole definite . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5.5.4 Forward e backward chaning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.6 Model checking proposizionale efficiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5.6.1 Algoritmi di backtracking per SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5.6.2 Algoritmi di ricerca locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

2

Chapter 1

Agenti Intelligenti

1.1 Agenti e ambienti

Un agent è qualunque cosa che possa essere vista come un sistema che percepisce il suo ambiente

mediante dei sensori e che agisce su di esso tramite degli attuatori (i.e. un esempio di agent potrebbe

essere l’umano). Useremo il termine percezione per indicare gli input percettivi dell’agent in un dato

istante di tempo. La sequenza (storico) di tutte le percezione, dalla nascita dell’agent fino ad un punto

nel tempo, viene chiamata sequenza percettiva.

In genere diremo che, la scelta dell’azione di un agente in un qualsiasi istante può dipendere

dal’intera sequenza percettiva osservata fino a quel momento, ma non da qualcosa che non

abbia percepito.

In termini matematici diciamo quindi che il comportamento di un agent è descritto mediante la funzione

agente, che descrive la corrispondenza tra una qualsiasi sequenza percettiva ed una specifica azione.

∗ →

f : P A

ˆ P l’alfabeto delle percezioni

∗

ˆ P l’insieme delle stringhe sulle percezioni

ˆ A l’insieme delle possibili azioni

Volendo analizzare un agent, in via di principio è possibile ricostruire la sua tabella provando tutte le

possibili tutte le possibili sequenze percettive e registrando l’azione prescelta come risposta alle percezioni.

La tabella naturalmente è una definizione esterna dell’agent.Internamente la funzione agente di un agente

1

artificiale sarà implementata da un programma agente .

1.2 Comportarsi correttamente: il concetto di razionalità

Un rational agent è un agent che fa la cosa giusta: dal punto di vista teorico si potrebbe dire che ogni

riga nella tabella della funzione agent è scritta correttamente. Cosa significa precisamente?

Consideriamo le conseguenza del comportamento dell’agent. Quando un agent viene inserito in un

ambiente, genera una sequenza di azioni in base alle percezioni che riceve. Questa sequenza di azioni

porta l’ambiente ad attraversare un determinato path di stati: se tale sequenza è desiderabile, significa

che l’agent si è comportato bene.

1 Un programma agente solitamente prence in input l’ultima percezione della sequenza dell’agent

3 2

Questa nozione di desiderabilità è catturata da una misura di prestazione che valuta una sequenza

di stati dell’ambiente. Notare che si è parlato di stati dell’ambiente e non di stati dell’agent.Questo perchè

se definissimo il successo riferendoci all’opinione dell’agent circa la sua stessa prestazione, questo potrebbe

ottenere la razionalità perfetta semplicemente illudendosi che la propria prestazione sia stata perfetta.

Come regola generale, è meglio progettare le misure di prestazione in base all’effetto che si

desidera ottenere sull’ambiente piuttosto che su come si pensa che debba comportarsi l’agent.

1.2.1 Razionalità

In una dato momento, ciò che è razionale dipende da quattro fattori

ˆ la misura di prestazione che definisce il criterio di successo

ˆ la conoscenza pregressa dell’ambiente da parte dell’agent

ˆ le azioni che l’agent può effettuare

ˆ la sequenza percettiva dell’agente fino all’istante corrente

Questo porta alla seguente definizione di agente razionale

per ogni possibile sequenza di percezioni, un agente razionale dovrebbe scegliere un’azione che

massimizzi il valore atteso della sua misura di prestazione, date le informazioni fornite dalla

sequenza percettiva e da ogni ulteriore conoscenza dell’agente.

1.2.2 Onniscenza, apprendimento e autonomia

Dobbiamo distinguere accuratamente il concetto di onniscenza da quello di razionalità. Un agent onnis-

cente conosce ili risultato effettivo delle sue azioni e può agire di conseguenza, ma nella realtà l’onniscenza

è impossibile. La razionalità non significa perfezione, in quanto essa massimizza il risultato atteso, mentre

la perfezione quello reale.

La nostra definizione di razionalità non richiede quindi l’onniscenza, perchè la scelta razionale dipende

solo dalla sequenza percettiva fino al momento corrente. Intraprendere azioni mirate a modificare le

percezioni future - in inglese information gathering - è una parte importante della razionalità. Un

secondo esempio di information gathering è rappresentato dall’esplorazione che dev’essere intrapresa da

un agent posto in un ambiente inizialmente sconosciuto.

La nostra definizione richiede che un rational agent non si limiti solo a raccogliere informazioni, ma che

sia anche in grado di apprendere il più possibile sulla base delle proprie percezioni. La sua configurazione

iniziale potrebbe riflettere una conoscenza pregressa, che però può modificarsi ed aumentare a mano a

mano che l’agent accumula esperienza. Quando un agente si appoggia alla conoscenza pregressa invece che

alle proprie percezioni, diciamo che manca di autonomia. Un agent razionale dovrebbe essere autonomo,

e apprendere il più possibile per compesare la presenza di conoscenza parziale o erronea.

2 Ovviamente di questa misura di prestazione non ne esiste un’unica fissata per tutti i compiti e per tutti gli agent.

4

1.3 La natura degli ambienti

Gli ambienti sono essenzialmente i ”problemi” di cui gli agenti razionali rappresentano le ”soluzioni”.

1.3.1 Specificare un ambiente

Per dare una specifica, quanto più precisa possibile, bisogna definire il task environment che racchiude:

le misure di prestazione, l’ambiente, gli attuatori e i sensori di un agent. Se questo task environment non

è definito in modo chiaro allora l’agent non sarà razionale. Questa descrizione prende anche il nome di

PEAS (Performance, Environment, Actuators, Sensors).

1.3.2 Proprietà degli ambienti

3

La varietà di ambienti operativi nell’IA è naturalmente molto vasta. Queste dimensioni determinano

in gran parte la progettazione di agenti appropriati e l’applicabilità delle principali tecniche alla loro

implementazione. Possiamo dividere gli ambienti in:

ˆ Completamente osservabile/parzialmente osservabile/inosservabile

Se i sensori di un agente gli danno accesso allo stato completo dell’ambiente in ogni momento, allora

diciamo che l’ambiente operativo è completamente osservabile, o in poche parole, basta che i sensori

misurino tutti gli aspetti rilevanti per la scelta dell’azione. Si dice, invece, parzialmente osservabile

nel momento in cui i sensori dell’agent sono inaccurati, o per la presenza di rumore, o semplicemente

perchè una parte di dati non viene rilevata da essi. Se l’agent non dispone di sensori, l’ambiente

si dice inosservabile. Si potrebbe pensare che in questo caso la condizione dell’agente sia senza

speranza, invece i suoi obiettivi potrebbero risultare ancora raggiungibili, talvolta con certezza.

ˆ Mono-/Multi-agent

In un ambiente con agente singolo è presente un solo agent che esegue delle azioni sull’ambiente

lavorando in singolo a differenza di uno multiagente, in cui sono presenti più agent. Come è possibile

che in un ambiente multi-agent un’agente A riconosca B come agente e non come oggetto? La

distinzione chiave tra agente ed oggetto dell’ambiente sta nella descrizione del comportamento di B

come il tentativo di massimizzare una misura di prestazione il cui valore dipende dal comportamente

dell’agent A. Si dice competitivo, un ambiente multiagente in cui B tenta di massimizzare una

misura di prestazione che minimizza quella dell’agent A, mentre diciamo cooperativo, quello in cui

si va a massimizzare la misura di prestazione di tutti gli agent. In un ambiente multiagente molto

importanti sono la comunicazione e la randomizzazione del comportamento, quest’ultima

cosa fa sı̀ che si ottengano dei comportamenti non predicibili dagli altri agent.

ˆ Deterministico/Non-deterministico/Stocastico

Se lo stato successivo dell’ambiente è completamente determinato dallo stato corrente e dall’azione

eseguita dall’agente, allora si può dire che l’ambiente è deterministico. Diremo invece che è non-

deterministico nel momento in cui la sua evoluzione è incerta dopo una sequenza di azioni. Un

ambiente si dice incerto quando non è completamente osservabile o non-deterministico. L’uso del

termine stocastico implica, generalmente, che l’incertezza sui risultati è quantificata in termini di

probabilità. Le descrizioni di ambienti non-deterministici sono solitamente associate a misure di

prestazioni che richiedono che l’agent abbia successo per tutti i possibili risultati delle sue azioni.

ˆ Episodico/Sequenziale

In un ambiente episodico, l’esperienza dell’agent è divisa in episodi atomici. L’aspetto fondamentale

è che un episodio non dipende dalle azioni intraprese in quelli precedenti. Negli ambienti sequenziali,

al contrario, ogni decisione può influenzare tutte quelle successive (i.e. scacchi).

3 Intelligenza Artificiale 5

ˆ Statico/Dinamico

Se l’ambiente può cambiare mentre l’agent sta ”pensando”, allora diciamo che è dinamico per

quell’agent; in caso contrario diciamo che è statico. Gli ambienti statici sono più facili da trattare

in quanto l’agent non deve continuare ad osservare il mondo mentre decide l’azione successiva e non

si deve preoccupare del passaggio del tempo. Se l’ambiente stesso non cambia al passare del tempo,

ma la valutazione della prestazione dell’agent sı̀, allora diciamo che l’ambiente è semidinamico (i.e.

gli scacchi sono semidinamici se giocati con il tempo).

ˆ Discreto/Continuo

La distinzione tra discreto e continuo si applica allo stato dell’ambiente, al modo in cui è gestito il

tempo, alle percezioni e azioni dell’agent. Inoltre un ambiente discreto tratta con i numeri interi, a

differenza di quello continuo che tratta con quelli reali.

ˆ Noto/Ignoto

Questa distinzione non si riferisce prettamente all’ambiente, ma bensı̀ della conoscenza che l’agent

ha delle leggi che lo regolano. In un ambiente noto, sono conosciuti i risultati (o le corrispondenti

probabilità, se l’ambiente è stocastico) per tutte le azioni. Ovviamente se l’ambiente è ignoto, l’agent

dovrà apprenderne il funzionamento per poter prendere buone decisioni.

1.4 La struttura degli agenti

Qual’è il funzionamento interno di un agent? Il compito dell’IA è progettare il programma agente che

implementa la funzione agente. Diamo per scontato che questo programma sarà eseguito da un computer

dotato di sensori fisici e attuatori; questa prende il nome di architettura:

agente = architettura + programma

In generale l’architettura si occupa di rendere le percezioni disponibili al programma, eseguire il pro-

gramma stesso e passare le azioni da esso prescelte agli attuatori a mano a mano che vengono generate.

1.4.1 Programmi agente

I programmi agente prendono come input la percezione corrente dei sensori e restituiscono un’azione agli

4

attuatori . Il programma agente prende in input la sola percezione corrente in quanto l’ambiente non gli

può fornire nulla di più; se le sue azioni devono dipendere dalla sequenza percettiva precedente, l’agente

stesso dovrà preoccuparsi di memorizzarla. 5

Esistono quattro tipi di programmi agente che sono alla base di tutti i sistemi intelligenti :

ˆ agenti reattivi semplici;

ˆ agenti reattivi basati sui modelli;

ˆ agenti basati sugli obiettivi;

ˆ agenti basati sull’utilità;

4 Mentre la funzione agente prende in input l’intera sequenza percettiva, il programma agente prende s