Home » Intelligenza Artificiale » 📋 URL
In questa sezione parleremo di un tipo specifico di agenti appartenenti alla categoria goal-based che utilizzano delle rappresentazioni atomiche del mondo per navigare in esso. Sono degli agenti che hanno bisogno di pianificare in anticipo le azioni che andranno a svolgere.
Partiamo però dalle due diverse tipologie di ricerca che un agente può svolgere:
- Ricerca informata: vengono date all’agente delle linee guida iniziali per riuscire a navigare il mondo in maniera più avanzata ed efficiente sin dall’inizio
- Ricerca non-informata: all’agente non viene data alcuna informazione sul mondo oltre alla definizione del problema stesso
Nota bene: quando un algoritmo di ricerca sta eseguendo una sequenza di azioni risolutiva per il problema ignora eventuali nuovi percepts che il mondo gli comunica. Questo tipo di agente esegue dunque le azioni che ha pianificato senza controllare cosa sta succedendo nel mondo durante la loro messa in pratica. Si tratta dunque di un tipo di controllo open-loop.
Di cosa si compone un problema
Un problema può essere scomposto in cinque diverse componenti:
- Stato iniziale: lo stato nel quale l’agente viene inizialmente posto
- Possibili azioni: denotate dalla funzione \texttt{ACTIONS}(s) che rappresenta la lista di azioni che possono essere svolte nello stato s
- Transition model: descrizione di ciò che ogni azione fa. Viene denotato dalla funzione \texttt{RESULT}(s, a)—che restituisce lo stato risultante s' partendo dallo stato s tramite l’azione a
- Goal test: determina se un dato stato coincide con lo stato obiettivo che risolve il problema
- Path cost function: funzione per assegnare un costo numerico a ogni percorso che può essere seguito nella risoluzione del problema. Il costo per passare da uno stato s a uno stato s' tramite l’azione a è indicato tramite
c(s, \, a, \, s') - Soluzione: sequenza di azioni che parte dello stato iniziale e arriva fino allo stato obiettivo. La migliore soluzione è denotata da un costo del percorso che è minore rispetto a quello delle altre soluzioni
Esempio (vacuum world): il vacuum world è un semplice ambiente virtuale utilizzato per valutare dei primi, semplici, algoritmi di intelligenza artificiale.
Nel Vacuum World, l’obiettivo dell’agente è quello di navigare in uno spazio bidimensionale che contiene una griglia composta da due celle. Ogni cella può essere pulita (vuota) oppure sporca.
Possiamo descrivere il problema tramite le seguenti caratteristiche:
- Stato iniziale: qualunque stato in cui il robot è nella cella di destra o di sinistra, caratterizzato da \texttt{Dirt}(\cdot) e \texttt{Location}(\cdot) che indicano, rispettivamente, se in tale cella è presente qualcosa da pulire e la posizione (destra o sinistra) in cui si trova
- Possibili azioni: \texttt{Left}(\cdot),\,\texttt{Right}(\cdot),\,\texttt{Suck}(\cdot),\,\texttt{NoOp}(\cdot), dove, rispettivamente, si dice all’agente di spostarsi a destra/sinistra, aspirare lo sporco oppure rimanere fermo
- Transition model: riportato in figura sotto, è rappresentato da tutte le possibili combinazioni di azioni/stati che possono essere ottenuti durante la soluzione del problema, o che possono essere utilizzate come stato iniziale del mondo
- Goal test: avere entrambe le celle pulite
- Path cost: 1 per ogni azione, 0 per il \texttt{NoOp}(\cdot)
Ricerca ad albero e nodi-frontiera
Spesso, nella risoluzione di un problema, può essere utile esprimere le possibili soluzioni in una struttura ad albero, in cui ogni nodo rappresenta uno stato del problema e i collegamenti tra essi rappresentano le relative transizioni per passare da uno stato all’altro.
Tratteremo alcuni algoritmi di ricerca ad albero nella relativa pagina, ma un’importante nozione che useremo nell’analisi dei diversi algoritmi è quella dei nodi frontiera, i quali rappresentano degli stati che sono stati generati ma non ancora esplorati.
Sono dei nodi che devono ancora essere espansi per determinare quali saranno i successivi stati da esplorare, ma sono già stati selezionati per l’espansione.
I nodi frontiera vengono gestiti mediante una struttura dati come una coda (FIFO, LIFO, di priorità, ecc.), che determina l’ordine in cui i nodi vengono poi esplorati.
Valutare le performance degli algoritmi di ricerca
Per valutare le performance di un algoritmo di ricerca sono necessarie quattro diverse metriche:
- Completezza: se esiste una soluzione, l’algoritmo riesce a trovarla?
- Ottimalità: se l’algoritmo trova una soluzione, è la soluzione migliore?
- Complessità temporale: numero di nodi generati/espansi
- Complessità spaziale: massimo numero di nodi mantenuti in memoria
In poche parole
✅ La ricerca può essere “informata” o “non informata”. Nella ricerca non informata, l’agente non dispone di informazioni aggiuntive oltre alla definizione del problema stesso. Deve esplorare lo spazio delle possibili azioni per trovare una soluzione. Nella ricerca informata, l’agente riceve invece delle informazioni iniziali che lo guidano nel processo di ricerca, consentendo una navigazione più efficiente.
✅ Un problema di ricerca si compone di diverse componenti:
- stato iniziale
- possibili azioni
- modello di transizione
- test obiettivo
- funzione di costo
✅ Gli algoritmi di planning analizzano le componenti di un problema e generano una sequenza di azioni che guida l’agente nella risoluzione del problema postogli dallo stato iniziale fino al raggiungimento dello stato obiettivo.
✅ I nodi frontiera sono dei nodi che devono ancora essere espansi ma sono già stati selezionati per l’espansione.
✅ Per valutare le performance degli algoritmi di ricerca e planning bisogna considerare le seguenti metriche:
- completezza
- ottimalità
- complessità temporale
- complessità spaziale