Cenni d'Intelligenza Artificiale Modulo II Lezione 3 · PDF fileCenni d'Intelligenza...

Corso di Logistica dei Trasporti e della Distribuzione

Cenni d'Intelligenza Artificiale

Modulo II

Lezione 3

Data 19/06/2013

Cosa vedremo?

1. Introduzione

1. I sistemi di trasporto intelligenti

2. Comportamento intelligente

3. Agente

4. Ambiente

2. Ricerca offline

1. Ricerca non informata su albero

1. Ricerca in ampiezza

2. Ricerca in profondità

3. Ricerca di costo uniforme

2. Ricerca informata su albero

1. Ricerca greedy

3. Ricerca online

1. Ambienti reali

4. Clustering

1. Algoritmo K-means

5. Domande

ITS (1)

La definizione di ITS è contenuta nella Direttiva 2010/40/UE:

„I sistemi di trasporto intelligenti (ITS) sono applicazioni avanzate che, senza essere dotate di intelligenza in senso proprio, mirano a fornire servizi innovativi relativamente ai diversi modi di trasporto e alla gestione del traffico e consentono a vari utenti di essere meglio informati e di fare un uso più sicuro, maggiormente coordinato e più «intelligente» delle reti di trasporto.“

ITS (2)

Un sistema di trasporto può essere considerato intelligente se è capace di rispondere in modo adeguato al verificarsi di nuove situazioni mantenendo per esempio adeguate condizioni di sicurezza e di congestionamento della rete; un sistema di trasporto intelligente deve fornire opportune informazioni agli utilizzatori e gli operatori della rete di trasporto a partire dalle fonte di dati.

ITS (3)

L'introduzione di tecnologie ITS è un'azione trasversale a tutti i modi di trasporto, anche se rivolta in particolare al trasporto su strada e le interfacce di quest'ultimo con gli altri modi.

Tra gli anni '90 e i primi anni 2000 l'aumento del traffico stradale (il JIT tra le cause) ha portato la rete al congestionamento.

Si deve distribuire il traffico su altri modi, come la ferrovia e il Short Sea Shipping.

IA (1)

Una macchina può essere capace di pensare come un essere umano?

La risposta a questa domanda non è ancora stata formulata, ma sono presenti due correnti:● IA forte● IA debole

IA (2)

● IA forte: un computer correttamente programmato potrà in tutto e per tutto essere intelligente come un essere umano e quindi indistinguibile.

● IA debole: un computer potrà al massimo replicare alcuni processi cognitivi umani

Test di Turing

Il test di Turing prevede la competizione di un essere umano ed un macchina.

L'obiettivo è convincere un terzo interlocutore umano tramite una chat che l'altro è la macchina.

Comportamento Intelligente

Noi assumiamo che un comportamento sia intelligente (o razionale) se data una situazione ed una base di informazioni viene effettuata la migliore azione possibile.

Per attraversare la strada, prima guardo a sinistra, poi a destra ed attraverso...

Se mi cade un meteorite in testa mentre attraverso sono sempre intelligente? (tralasciando che sono morto!)

Modelli in IA

Partiamo dai due concetti di base:

● L'agente razionale● L'ambiente

Agente

L'agente:

● Utilizza i sensori per percepire informazioni dall'ambiente

● Utilizza gli attuatori per effettuare azioni sull'ambiente

● Sceglie un'azione da fare

Tipologie di Agente

L'agente:

● Reattivo● Con stato● Con funzione obiettivo● Con funzione d'utilità● Con apprendimento

Ambiente

L'ambiente ha le seguenti caratteristiche:● Completamente/parzialmente osservabile● Deterministico/stocastico● Episodico/Sequenziale● Noto/ignoto● Statico/dinamico● Mono/multi agente● Discreto/continuo

Assunzioni

Ambiente:

● Statico● Deterministico● Discreto● Completamente osservabile

Modello (1)

Utilizziamo i grafi ad albero per rappresentare il nostro modello.

I grafi ad albero sono caratterizzani da un nodo radice, nodi intermedi e nodi foglie.

Gli archi sono orientati, ovvero si può andare solo da un nodo padre (vicino alla radice) verso un nodo figlio (vicino alle foglie).

Modello (2)

Utilizziamo i nodi per rappresentare gli stati possibili in cui si può trovare l'agente.

La radice corrisponde allo stato iniziale.

Gli archi sono le azioni che portano da uno stato, nodo padre, ad un altro, ovvero i possibili nodi figli.

Modello (3)

Il modello è composto da:

● Gli stati● Lo stato iniziale● Lo stato goal● Le azioni

Esempio (1)

G E A

D

H B F

IC

A B C

D E F

G H I

Esempio (2)

Utilizziamo i grafi ad albero per rappresentare il nostro modello.

Ad ogni nodo corrisponde un possibile stato in cui si può trovare l'agente.

Ad ogni arco corrisponde un'azione che va da un nodo padre ad un nodo figlio.

In un albero possono esserci un numero variabile di nodi goal (obiettivo): nessuno se non ci sono soluzioni, uno o più d'uno.

Esempio (3)

G E A

D

H B F

IC

Nel modello del labirinto assumiamo di non ripetere gli stati già visitati.

Questa semplificazione può non essere necessaria a seconda dell'algoritmo che utilizziamo, ma almeno rende più facile la rappresentazione grafica.

Senza un controllo dei nodi già visitati l'albero diventa infinito.

D D D

Ricerca offline

1. Introduzione



3. Agente

4. Ambiente

2. Ricerca offline






1. Ricerca greedy

3. Ricerca online

● Ambienti reali

4. Clustering


5. Domande

Ricerca offline

La ricerca offline consiste nel effettuare la ricerca del piano, ovvero della sequenza di azioni che conduce da uno stato iniziale ad uno stato goal, prima di cominciare ad eseguire il piano.

Es.

Per andare da Carrara a Viareggio prendiamo la cartina stradale, scegliamo le strade da fare ed infine saliamo in auto e le percorriamo.

Ricerca non informata

La ricerca non informata consiste in una ricerca in cui ho le informazioni relative al grafo, ovvero nodi, stato iniziale, stati goal ed archi, ma non ho informazioni ulteriori al di là del problema stesso.

Es.

Nel problema del labirinto so solo per ogni casella, quali sono le caselle adiacenti che posso raggiungere, non ho idea di quanto dista l'uscita.

Modello

A B C

D E F

G H I

Supponiamo:

● D stato iniziale

● I stato goal

● Costo azione = 1

Un'informazione ulteriore potrebbe essere la distanza in linea d'aria tra D ed I.

Sapere questo dato rende la ricerca informata!


La ricerca consiste nell'esplorare gli stati fino a che non riusciamo a trovare uno stato goal o falliamo.

Il procedimento di base:

● Scelgo un nodo tra quelli che posso raggiungere con un'azione. Chiamiamo questo insieme di nodi frontiera.

● Espando il nodo, ovvero guardo tutti i nodi che posso raggiungere da quel nodo e li aggiungo alla frontiera.

● Controllo se nella frontiera ho trovato un goal.

● Ricomincio fino a che non ho controllato tutti i nodi o trovato un goal.


La scelta del nodo da espandere può essere:

● FIFO: First In – First Out

● LIFO: Last In – First Out

● Ordinamento per costo - Dijkstra

Ricerca in ampiezza (1)

G E A

D

H B F

IC

Utilizzo il metodo FIFO per scegliere il nodo da espandere. Espando il nodo più vecchio che ho aggiunto alla frontiera.

F={D}

Sceglo D e lo espando

F={A,E,G}


G E A

D

H B F

IC

Controllo se in F c'è un goal. Il nostro goal è I.

Scelgo il nodo più vecchio in F ={A,E,G}

A parimerito posso scegliere con un altro criterio, come l'ordine alfabetico. Espando A che però non ha nodi figli.


G E A

D

H B F

IC


Scelgo il nodo più vecchio in F ={E,G}

Espando E.

F={G,B,F}


G E A

D

H B F

IC


Scelgo il nodo più vecchio in F ={G,B,F}

Espando G.

F={B,F,H}


G E A

D

H B F

IC

La restante sequenza di espansione è:

B → F → H → C → I

Goal!

Ricerca in profondità (1)

G E A

D

H B F

IC

Utilizzo il metodo LIFO per scegliere il nodo da espandere. Espando il nodo più recente che ho aggiunto alla frontiera.

F={D}

Sceglo D e lo espando

F={A,E,G}


G E A

D

H B F

IC


Scelgo il nodo più recente in F ={A,E,G}

A parimerito posso scegliere con un altro criterio, questa volta il nodo più a destra. Espando A che però non ha nodi figli.


G E A

D

H B F

IC


Scelgo il nodo più recente in F ={E,G}

Espando E.

F={B,F,G}


G E A

D

H B F

IC


Scelgo il nodo più recente in F ={B,F,G}

Tra B ed F espando F perhé è più a destra.

F={C,I,B,G}


G E A

D

H B F

IC

Controllo se in F c'è un goal. Trovo I che è il goal.

Confronto (1)

Entrambe scelgono i nodi da espandere in funzione dell'ordine, non considerano il costo degli archi.

La ricerca in ampiezza esplora molti più stati prima di arrivare alla soluzione e tiene tutto in memoria.

La ricerca in profondità scende lungo un ramo dell'albero fino al nodo foglia. Occupa mola meno memoria di lavoro.

Confronto (2)

La ricerca in ampiezza trova sempre una soluzione, se questa esiste.

La ricerca in profondità potrebbe esplorare un ramo infinito, ovvero un ramo che non ha un nodo foglia e quindi non trovare alcuna soluzione.

Es. nel labirinto potrei non controllare gli stati già esplorati ed andare avanti ed indietro all'infinito!

Ricerca di costo uniforme

Entrambe le ricerche precedenti non tengono conto del costo delle azioni, ovvero degli archi.

La ricerca di costo uniforme invece ordina i nodi in funzione del costo del cammino per arrivare al nodo esattamente come l'algoritmo di Dijkstra!

Come abbiamo visto nella lezione precedente, riusciamo a trovare la soluzione ottima!

Nota: la condizione di ottimalità è rispettata se i costi dei cammini sono non decrescenti!

Ricerca informata

La ricerca è informata se oltre ai dati del problema della ricerca non informata ho a disposizione per ogni stato una stima della distanza della soluzione.

La funzione che associa ad ogni stato la stima della distanza dalla soluzione si chiama euristica.

Ricerca greedy

La ricerca greedy best first seleziona il successivo nodo da espandere in funzione del valore della euristica che stima.

Come dice il nome stesso sceglie le azioni che conducono verso i nodi più promettenti!

Una volta intrapresa una direzione procede senza mai guardarsi indietro fino a trovare la soluzione o fallire.

Ricerca greedy

La ricerca greedy è veloce ed occupa poca memoria di lavoro, ma può fallire nel trovare la soluzione oppure non trovare la soluzione ottima al problema.

Modello (1)

G E A

D

H

B

F

I

C

A B C

D E F

G H I

H

4 3 2

3 2 1

2 1 0

Modello (2)

Utilizziamo la distanza Manhattan come euristica: conta i passi in orizzontale e verticale senza considerare ostacoli.

4 3 2

3 2 1

2 1 0

Modello (3)

Un approccio greedy in questo caso ci porta da D=3 a E=2 o G=2 fino ad H=1, dal quale poi non possiamo più procedere.

Non troviamo la soluzione e falliamo perché il primo passo dovrebbe essere A=4, cioè andare in una direzione con una euristica peggiore!

Ricerca online

1. Introduzione



3. Agente

4. Ambiente

2. Ricerca offline






1. Ricerca greedy

3. Ricerca online

● Ambienti reali

4. Clustering


5. Domande

Ricerca online

La ricerca online diventa necessaria quando le caratteristiche dell'ambiente non consentono di preparare il piano per raggiungere il goal.

Diventa quindi necessario interagire con l'ambiente per acquisire ulteriori informazioni.

Ambiente

L'ambiente ha le seguenti caratteristiche:● Completamente/parzialmente osservabile● Deterministico/stocastico● Episodico/Sequenziale● Noto/ignoto● Statico/dinamico● Mono/multi agente● Discreto/continuo

Assunzioni

L'ambiente ha le seguenti caratteristiche:

● Parzialmente osservabile● Stocastico● Ignoto● Dinamico

Ricerca Online

Nella ricerca online l'agente sceglie un'azione, la esegue, utilizza le percezioni per acquisire informazioni e ripete questa sequenza fino al raggiungimento di uno stato goal o un fallimento.

Non è possibile preparare un piano completo prima di iniziare ad eseguire le azioni perché le caratteristiche dell'ambiente (slide precedente) non lo consentono!

Clustering

1. Introduzione



3. Agente

4. Ambiente

2. Ricerca offline






1. Ricerca greedy

3. Ricerca online

● Ambienti reali

4. Clustering


5. Domande

Clustering (1)

Il clustering è un problema in cui abbiamo un insieme di dati, composti anche da più attributi, e vogliamo cercare di classificarli senza avere un'idea dei possibili criteri utilizzabili.

L'obiettivo è creare die raggruppamenti che siano:● Il più possibile omogenei al loro interno● Il più possibile eterogenei tra gruppi diversi

Clustering (2)

Per esempio, potrei avere per ogni cliente del supermercato i dati che descrivono la persona (sesso, età, cittadinanza...) e la lista della spesa e voler vedere se esistono dei possibili criteri di raggruppamento dei clienti.

Algoritmo K-means (1)

L'algoritmo k-means raggruppa i dati di input in un numero k di gruppi. Il valore di k deve essere deciso dall'utilizzatore prima di avviare l'algoritmo.

Se non si hanno indicazioni sul possibile valore di k si può procedere iterativamente, ovvero provando diversi valori, fino a trovare una soluzione soddisfacente.


Possiamo schematizzare l'algoritmo in tre passaggi:

● Inizializzazione● Assegnazione● Calcolo baricentro


Esempio:

Ipotizziamo di avere dei dati in uno spazio bi-dimensionale e vogliamo raggrupparli.


Inizializzazione

Supponiamo di scegliere k = 2

L'algoritmo mette 2 punti, detti centroidi, a caso nello spazio.


Assegnazione

Associa ogni dato al centroide più vicino.


Calcolo baricentro

Riposiziona i centroidi in modo da minimizzare la sommatoria delle distanza rispetto ai dati assegnati a ciascun punto.


Assegnazione

Si ripete l'assegnazione dei dati ai centroidi più vicini.

L'assegnamento può, e spesso è, diverso dal precedente!


Calcolo Baricentro

I centroidi vengono posizionati di nuovo sempre minimizzando la sommatoria delle distanza dei punti assegnati!


Terminazione

L'algoritmo termina quando dopo aver calcolato la posizione dei centroidi queste sono identiche o molto simili a quelle precedenti!

Considerazioni

● La fase iniziale è casuale, quindi a parità di k, l'algoritmo su dati identici può produrre soluzioni differenti

● Modificare il k può portare a soluzioni migliori/peggiori. (Nell'esempio precedente con k=3 troviamo 3 clusters molto buoni!)

● L'algoritmo è veloce ma non ho garanzie sulla qualità della soluzione.

Domande

1. Introduzione



3. Agente

4. Ambiente

2. Ricerca offline






1. Ricerca greedy

3. Ricerca online

1. Ambienti reali

4. Clustering


5. Domande

Domande (1)

● Cosa sono gli ITS?● Perché si introducono gli ITS?● Quale modo di trasporto riguardano

maggiormente?

Domande (2)

● Quando un comportamento è intelligente?● Com'è fatto un agente?● Come possiamo descrivere l'ambiente?

Domande (3)

● Qual'è la differenza tra ricerca offline ed online?● Qual'è la differenza tra ricerca informata e non

informata?● Quali sono le caratteristiche e le differenze

della ricerca in ampiezza in profondità e di costo uniforme?

● Quali sono le caratteristiche e le differenze tra una ricerca informata greedy ad A*?

Domande (4)

● A cosa serve il clustering?● Come fa k-means a trovare cluster di dati?● Quali sono i pregi ed i difetti di k-means?

Cenni d'Intelligenza Artificiale Modulo II Lezione 3 · PDF fileCenni d'Intelligenza...

Documents

Transcript of Cenni d'Intelligenza Artificiale Modulo II Lezione 3 · PDF fileCenni d'Intelligenza...