5. Ricerca di soluzioni

Dopo aver visto negli articoli precedenti come un agente percepisce e agisce nel mondo, adesso cerchiamo di comprendere come i suoi obiettivi influenzano le sue azioni. Infatti un agente, per essere definito intelligente, deve saper ragionare sulle sue capacità e sui suoi obiettivi per determinare cosa fare. Quindi, ponendoci ad esempio il problema della ricerca di un percorso in un grafo, vediamo come un agente risolve tale problema per raggiungere il suo obiettivo.

Nel caso più semplice un agente ha un modello del mondo basato sullo stato, un obiettivo da raggiungere e nessuna incertezza. Questa rappresentazione viene definita rappresentazione piatta o singolo livello di gerarchia. L'agente determina come raggiungere il suo obiettivo cercando nella sua rappresentazione dello spazio degli stati un modo per passare dal suo stato attuale a uno stato che soddisfi il suo obiettivo. In un modello completo, l'agente cerca di trovare una sequenza di azioni tramite le quali può raggiungere il suo obiettivo. Possiamo quindi astrarre il problema facendolo coincidere con quello di trovare un percorso dal nodo iniziale a un nodo obiettivo in un grafo orientato.

Trovare il percorso migliore da una posizione corrente a una destinazione è considerato un problema di ricerca. Il percorso migliore potrebbe significare trovare:

• il percorso più breve, quindi la distanza minima
• il percorso più rapido
• il percorso più adatto rispetto a determinate preferenze.

Trovare il percorso più breve è solitamente il più facile da implementare, in quanto effettuare un calcolo delle distanze è semplice. E' più difficile calcolare il tempo, in quanto un agente deve tener conto di diverse variabili. Mentre trovare il percorso migliore che tenga conto di altre preferenze è difficile a livello computazionale. Per essere più specifici, questa operazione di ricerca è diversa dalla ricerca all'interno del mondo o alla ricerca web, in quanto è un'operazione che avviene all'interno dell'agente e produce una rappresentazione interna ad esso che indica il percorso verso l'obiettivo.

La ricerca è alla base di gran parte dell'intelligenza artificiale. Quando a un agente viene assegnato un problema, di solito gli viene data solo una descrizione che gli consente di riconoscere una soluzione, non un algoritmo per risolverlo. Deve cercare una soluzione. L'esistenza di problemi NP-completi (di cui parleremo più avanti), con mezzi efficienti per riconoscere le soluzioni ma nessun metodo efficiente per trovarle, indica che la ricerca è una parte necessaria della risoluzione dei problemi. Per risolvere alcuni problemi, gli agenti fanno uso di una conoscenza extra rispetto a quella dello spazio di ricerca, denominata conoscenza euristica. La stima del costo da un nodo a un obiettivo rientra in questo obiettivo.

Ogni agente per poter agire in maniera intelligente agisce in termini di spazio degli stati, nel quale ogni stato contiene tutte le informazioni necessarie per prevedere gli effetti di un'azione e per determinare se uno stato soddisfa o meno l'obiettivo. Per effettuare una ricerca nello spazio degli stati, si presume che l'agente:

• abbia una perfetta conoscenza dello spazio degli stati e pianifichi il caso in cui osserva in quale stato si trova; (piena osservabilità)
• abbia una serie di azioni che hanno effetti deterministici noti;
• è in grado di determinare se uno stato soddisfa l'obiettivo.

Detto ciò, possiamo definire una soluzione come una sequenza di azioni che porterà l'agente dal suo stato attuale a uno stato che soddisfa l'obiettivo. Adesso abbiamo tutti gli elementi per definire formalmente un problema nello spazio degli stati. Quest'ultimo è costituito da:

• Un insieme di stati
• uno stato distinto chiamato stato iniziale
• per ogni stato, un insieme di azioni disponibili per l'agente in quello stato
• una funzione azione che, ricevendo in input uno stato e un'azione, restituisce un nuovo stato
• un obiettivo specificato come una funzione booleana, goal(S), che risulta vera quando lo stato S soddisfa l'obiettivo e in tal caso S prende il nome di stato obiettivo
• un criterio che specifica la qualità di una soluzione accettabile. In questo caso una soluzione ottima è quella soluzione che risulta migliore in base a questo criterio.

Per trovare una sequenza di azioni per raggiungere un obiettivo viene astratto come ricerca di percorsi in grafi orientati, nel quale si definisce uno spazio di ricerca sottostante e si applica ricorsivamente un algoritmo di ricerca al relativo spazio. Molti problemi della vita reale si possono ricondurre al problema di ricerca di un percorso in un grafo, perchè viene fornito un modello astratto appropriato di problem solving indipendente per ogni particolare dominio.

Un grafo orientato è costituito da un insieme di nodi e da un insieme di archi orientati tra i nodi. Bisogna quindi trovare un percorso lungo questi archi dal nodo iniziale a quello finale. Per riallacciarci a quanto detto prima, lo spazio degli stati è rappresentato dai nodi e le azioni dagli archi. Questa astrazione è fondamentale, in quanto un problema può avere diverse rappresentazioni attraverso il modello del grafo.

Definizione di grafo orientato

Un grafo orientato è costituito da:

• un set di N nodi
• un set di A archi, dove un arco è una coppia ordinata di nodi

Ovviamente un nodo potrebbe rappresentare qualsiasi cosa. All'interno di un grafo ci possono essere infiniti nodi e archi. Oltre alla definizione di grafo, abbiamo anche bisogno di definire sintatticamente l'arco, il quale può essere rappresentato attraverso la dicitura $< n_1, n_2 >$, la quale sta indicare che l'arco preso in considerazione, è un arco uscente dal nodo $n_1$ e un arco in entrata nel nodo $n_2$. Diciamo inoltre che un nodo $n_2$ è vicino di $n_1$ se c'è un arco che li collega, ovvero se $< n_1, n_2 > \in A$. Il concetto di vicinanza non è simmetrico. Inoltre gli archi possono essere etichettati in diversi modi. In generale si inserisce l'azione che porterà l'agente da un nodo all'altro, il costo di quella azione oppure entrambi.

Una volta acquisito il concetto di arco e di nodo, possiamo definire il concetto di percorso come una sequenza di nodi $<n_0, n_1, \dots, n_k >$ dal nodo s al nodo g, tale che $s = n_0$,$g = n_k$ e $< n_{i-1}, n_i > \in A$. Ciò significa che c'è un arco da $n_{i-1}$ a $n_i$ per ogni i. Inoltre può essere utile vedere un percorso come una sequenza di archi o come una sequenza di etichette (o labels). Infine definiamo un percorso come $< n_0, n_1, \dots, n_i >$ come una parte iniziale di $< n_0, n_1, \dots, n_k >$, con $i \leq k$.

Quando gli archi di un grafo hanno un costo, può essere definita una funzione di costo denotata come $cost( < n_i, n_j > )$ che indica il costo dell'arco, che per inciso è un valore non negativo. Quindi dati un percorso $p = < n_0, n_1, \dots, n_k >$, il costo del percorso p è la somma dei costi degli archi che lo compongono. Quindi $cost ( p ) = \sum_{i=1}^k cost( < n_{i-1}, n_i > ) = cost( < n_0, n_1 > ) + \dots + cost( < n_{k-1}, n_k > )$.

Una soluzione ottimale è una soluzione che ha il costo minore. Ciò signigica che all'interno di un grafo la soluzione ottimale è quel percorso p che da parte un nodo iniziale per arrivare al nodo obiettivo, tale che non vi è un percorso p' che per lo stesso nodo iniziale e per lo stesso nodo obiettivo abbia una funzione costo minore. Ovvero che $cost( p ) < cost( p\prime )$.

Vi sono altri concetti importanti da tenere in considerazione quando si effettua una ricerca di una soluzione attraverso la rappresentazione mediante grafi. Definiamo un ciclo come un percorso non vuoto dove il nodo finale coincide con quello iniziale, ovvero quel percorso $< n_0, n_1, \dots, n_k >$ in cui $n_0 = n_k$. Un grafo diretto senza nessun ciclo è chiamato grafo diretto aciclico (DAG).

Un'altra definizione è quella di albero, definito come DAG all'interno del quale esiste un nodo che non possiede nessun arco in entrata e tutti gli altri nodi hanno solo un arco in entrata. Il nodo con nessun arco in entrata prende il nome di radice o root, mentre un nodo con nessun arco in uscita è chiamato nodo foglia o leaf. I nodi vicini prendono il nome di figli o children.

In molti problemi il grafo di ricerca non è fornito esplicitamente, ma è costruito dinamicamente, secondo le diverse necessità. In questi casi viene definito il forward branching factor di un nod, oppure fattore di ramificazione in avanti, il numero di archi uscenti da quel nodo. Mentre il forward branching factor di un nodo, o fattore di ramificazione al contrario, è il numero di archi in entrata di quel nodo. Questi due fattori sono molto importanti per determinare la complessità di un algoritmo.