Appunti di Intelligenza artificiale

Intelligenza artificiale

Introduzione

• L'Intelligenza artificiale studia l'analisi e la sintesi di agenti computazionali che agiscono. Campo e soluzioni: possono esistere problemi che ammettono verifica in tempo polinomiale e problemi che non possono essere detti deterministici in tempo polinomiale.

NP-completi: problemi che sono non in P, ovvero problemi polinomiali, dato il problema v. La classe P rappresenta l'insieme dei problemi che possono essere risolti in tempo polinomiale, ovvero: trovare un algoritmo che risolva il problema in tempo polinomiale. Mentre la classe NP rappresenta l'insieme di tutti i problemi che possono essere verificati in tempo polinomiale, cioè dato il problema e la soluzione, possiamo verificare se una soluzione soddisfa il problema in tempo polinomiale.

Si dice che il problema B è risolvibile in tempo polinomiale. Tempo di "risoluzione": se n = 0, ammette soluzione in tempo polinomiale. Un problema intrattabile si dice che non è in P. Si dimostra che P e NP sono diverse? Consideriamo la classe NP-completo: B è nella classe NP-completo se qualsiasi problema si risolve in tempo polinomiale. Se P ed NP sono classi equivalenti allora otterremmo che questa questione è ancora non risolta.

Ad esempio, SAT è il problema che, data una stringa di bit, restituisce il valore vero o falso. SAT è un problema NP-completo. In particolare qualsiasi problema NP-completo può essere ricondotto a un problema SAT.

L'agente è un'entità astratta che interagisce con l'ambiente tramite dei sensori per raccogliere informazioni e con degli attuatori. I sensori sono canali dell'ambiente che permettono di percepire informazioni di input e forniscono percezioni. Gli attuatori sono canali di output all'ambiente che forniscono azioni.

Funzione agente: ad esempio consideriamo una macchina autonoma come agente. I sensori possono essere camera, GPS, sensori di prossimità, che danno alla macchina informazioni riguardo alla sua posizione e all'ambiente circostante. Mentre gli attuatori possono essere acceleratore e freno, che controllano la velocità della macchina.

Le informazioni raccolte dai sensori, percezioni, vengono elaborate tramite segnali sull'ambiente. Perciò gli agenti ricevono informazioni dai sensori e compiono azioni tramite attuatori. Questa attività compiuta dall'agente è detta funzione agente.

Quindi la funzione agente definisce, sulla base della sequenza di percezioni catturate, una sequenza di azioni. Perciò l'agente computazionale deve soddisfare una condizione fondamentale: la funzione agente deve essere esprimibile tramite un programma.

Lo stato di agente permette di memorizzare le possibili sequenze di percezioni che possono essere elaborate dall'agente. Lo stato dell'agente aggiorna, sulla base degli input rilevati dai sensori, una funzione di transizione di stato. Le informazioni contenute nell'agente non sono queste.

Per valutare se un agente è intelligente dobbiamo analizzare la performance della funzione agente. Un agente razionale si dice quando il valore atteso massimizza la performance, ovvero quando seleziona l'azione da eseguire massimizzando il valore della performance per ogni sequenza di percezioni.

Per realizzare la funzione agente è necessario effettuare delle assunzioni sull'ambiente:

• Ambiente deterministico o stocastico: un ambiente deterministico è quando lo stato successivo dell'ambiente è determinato dallo stato attuale dell'agente e dalla sua azione. Mentre un ambiente stocastico si ha quando sono presenti delle variabili non osservabili, per cui non possiamo determinare lo stato successivo a partire dallo stato attuale o dall'azione eseguita dall'agente.
• Nella realtà si possono verificare situazioni possibili nelle quali non è possibile riconoscere, dal sistema, situazioni. Ad esempio possiamo definire stocastico un ambiente, se nella situazione di macchina autonoma, il futuro non si può determinare poiché la vista gli ostacoli è più oscura. In questo caso si dice ambiente parzialmente osservabile.
• Ambiente episodico e sequenziale: un ambiente episodico è quando è necessaria una singola azione. Un ambiente sequenziale è quando è necessaria una sequenza di azioni.
• Ambiente statico o dinamico: un ambiente statico è se non cambia mentre l'agente calcola la funzione; un ambiente dinamico è se cambia nel momento in cui l'agente calcola la funzione.
• Ambiente continuo e discreto: un ambiente continuo può effettuare una serie infinita di possibili azioni, quindi misurabile e non misurabile. Mentre un ambiente discreto può effettuare un numero finito di azioni.
• Ambiente agente singolo oppure agenti multipli: possiamo lavorare con un agente oppure con più agenti.

Ricerca di problema

• Si tratta di trovare, in un problema, una sequenza finita di azioni con cui un agente deve portare da uno stato iniziale a uno stato obiettivo, detto goal, tramite attuatori. Goal rappresenta un sottoinsieme degli stati.

Dobbiamo effettuare delle ipotesi:

• L'ambiente è discreto e l'insieme degli stati è numerabile.
• L'ambiente è completamente osservabile; perciò l'agente è in grado di conoscere sempre lo stato attuale dell'ambiente.
• Le azioni hanno effetto deterministico; cioè, se un agente compie un'azione, allora questa viene realmente eseguita.
• L'ambiente è statico.
• L'agente è guidato dagli obiettivi, goal driven agents.

Sliding tiles puzzle: si tratta di un puzzle composto da tessere numerate scorrevoli, stato iniziale 3×3. Il problema consiste nell'eseguire un numero finito di mosse per portare il puzzle da uno stato iniziale disordinato a uno stato goal in cui il puzzle risulta ordinato. Un'azione è il movimento della tessera vuota rappresentata.

Poiché il puzzle è composto da 9 tessere, allora il numero possibile di stati in cui può trovarsi il puzzle è 9!. Congettura di Knuth: partendo dallo stato iniziale possiamo applicare una sequenza di operazioni e ottenere qualsiasi stato possibile. Il numero di operazioni è pari alla parte intera inferiore della radice quadrata di n. Ad esempio 5 = 14, 1. In questo caso le azioni che possiamo eseguire sono rappresentate dalle operazioni.

Robot che si muove su 2 celle che possono essere sporche. In questo esempio abbiamo un robot che può muoversi nelle 2 celle su cui lo sporco è presente. I possibili stati sono rappresentati da azioni: spostamento a destra, spostamento a sinistra e aspirare sporco. Perciò possiamo avere 2³ = 8 stati possibili. In questo caso lo stato goal è rappresentato da 2 celle pulite e stati possibili: robot a destra oppure robot a sinistra.

Problema delle 8 regine: abbiamo 8 regine che possono essere disposte su una scacchiera. L'obiettivo è trovare quello stato in cui nessuna regina possa essere sotto attacco. In questo caso l'azione è rappresentata dallo spostamento di una regina in un qualsiasi quadrato della scacchiera.

Se consideriamo una scacchiera di dimensione n×n, allora vogliamo disporre K regine, avremo K = n. Perciò disporremo le regine sulla scacchiera. Questo valore risulta troppo elevato; però, se n = 3, il numero degli stati sarà dell'ordine 10%. Possiamo semplificare questo risultato effettuando delle assunzioni e ottenendo n! come numero degli stati possibili.

Perciò, per un problema di ricerca, dobbiamo definire le seguenti componenti:

• S: insieme degli stati.
• A: insieme delle azioni.
• Lo spazio degli stati può essere rappresentato dal grafo in cui gli stati sono i vertici e le azioni sono gli archi.
• SO ∈ S: stato iniziale.
• ST ∈ S: stato goal.
• Action: S → 2A, funzione che ritorna il numero di azioni che può compiere uno stato agente.
• Result: S × A → S, funzione detta modello di transizione. Ritorna lo stato raggiunto ed è detta funzione Result, ovvero con s, a, s'. Quando, nello stato attuale s, si esegue l'azione a.
• Goal: S → {0,1}, funzione booleana che ritorna 1 se lo stato è goal, 0 altrimenti. Ovvero vero oppure falso.
• Step cost: C, funzione che ritorna il costo comportato ed eseguita sull'azione, ovvero con s, a.
• Path cost: funzione detta cost che ritorna il costo totale dovuto a una sequenza di azioni, ovvero State, a, dove t = 1. La somma di tutti gli step cost eseguiti sugli stati dall'insieme delle azioni.

Soluzione: rappresenta un cammino path dallo stato iniziale allo stato goal.

Albero di ricerca

• L'albero di ricerca rappresenta una struttura dati matematica di dimensione infinita, perciò non può essere memorizzato.

La radice dell'albero contiene lo stato iniziale, mentre ogni nodo dell'albero rappresenta uno stato. Il nodo può rappresentare path, cioè un cammino o una sequenza di azioni.

Perciò, il nodo dell'albero è una struttura dati che contiene alcune informazioni come:

• State: l'attributo stato, indicato con vi.
• Parent: l'attributo padre, puntatore al nodo padre definito con n.
• Action: l'attributo azione applicata al nodo padre che ha generato questo nodo.
• Path cost: l'attributo del costo totale del cammino dallo stato iniziale fino a questo nodo, indicato con n.
• Path cost viene definito con una funzione: gcn.

Applicando la funzione Result a un determinato nodo dell'albero, ovvero eseguendo un'azione ad uno stato, possiamo passare da un nodo a un nodo figlio. Questa operazione può essere definita come espansione del nodo.

Perciò, l'operazione di espansione di un nodo permette di generare tutti i possibili nodi figli applicando le azioni al nodo determinato dell'albero.

Definiamo anche la frontiera come una struttura dati detta list, che possiede le seguenti operazioni:

• Empty: ritorna vero se la frontiera è vuota, falso altrimenti.
• Pop: estrae i nodi dalla frontiera.
• Push: inserisce i nodi nella frontiera.

N.B. La frontiera rappresenta una coda ordinata secondo diverse tecniche, spesso FIFO, LIFO o priorità.

Proprietà della frontiera: separazione tra nodo già esplorato e nodo ancora non esplorato. Ogni cammino che connette un nodo esplorato con un nodo non esplorato deve intersecare la frontiera.

Es: nodi esplorati, frontiera, nodi non esplorati. La frontiera contiene i candidati all'espansione: i nodi frontiera. Nodi non aspirati, nodi non esplorati, frontiera esplorati.

Algoritmo di ricerca

Un algoritmo di ricerca permette di trovare una soluzione di un particolare problema di ricerca oppure una indicazione di fallimento, se non riesce a trovare soluzione.

Proprietà di un algoritmo di ricerca:

• Completezza: se esiste una soluzione, l'algoritmo garantisce di trovarla.
• Ottimalità: l'algoritmo garantisce di trovare la soluzione con costo minimo.
• Tempo e spazio: l'algoritmo richiede un certo tempo di esecuzione e un certo spazio di memorizzazione.

Definiamo:

• d: valore della profondità della soluzione meno profonda, solution depth.
• b: valore del fattore di ramificazione, branding factor, ovvero il numero di figli generati da un nodo soluzione.
• m: valore della lunghezza massima di un cammino di ricerca.

N.B. b e d.