Home » Intelligenza Artificiale » 📋 URL
I grafi AND e OR sono strumenti utilizzati nelle strategie di forward/backward chaining per rappresentare le relazioni tra i fatti, le regole e le conclusioni di un sistema di inferenza.
In un grafo AND-OR, ogni nodo rappresenta una premessa, mentre gli archi rappresentano le regole di inferenza che collegano le diverse informazioni espresse nei nodi.
Un nodo di uscita in un grafo AND-OR (per esempio Q in figura) rappresenta una conclusione che può essere dedotta dalle informazioni e dalle regole associate ad essa. Per raggiungere un nodo di uscita tutti i suoi nodi genitori devono essere soddisfatti. In altre parole, tutte le premesse devono essere vere affinché la conclusione sia vera.
Nel forward chaining si attraversano i nodi del grafo seguendo le connessioni degli archi e si generano nuove premesse e conclusioni man mano che si procede. Procedendo controllando che tutte le condizioni indicate nel nodo siano verificate nel caso di un nodo AND per poter procedere nella direzione indicata dal nodo (dunque i nodi AND rappresentano un punto di convergenza per rami diversi che vengono indirizzati di conseguenza verso un’unica direzione). Nel caso invece di un nodo OR si controlla che almeno una delle condizioni sia soddisfatta (infatti i nodi OR sono dei punti raggiungibili nel grafo da diverse direzioni, ognuna delle quali rappresenta una delle opzioni dell’OR).
Nel backward chaining, invece, si attraversano i nodi del grafo seguendo le connessioni degli archi in direzione opposta rispetto al forward chaining. Si cerca un percorso che collega le premesse al nodo di obiettivo desiderato. I nodi AND e quelli OR hanno lo stesso significato indicato sopra.
Esercizio: utilizzando il grafico riportato in figura sopra, si esprimano le diverse condizioni di AND/OR prima tramite delle implicazioni (come sono espresse nell’albero), trasformandole successivamente in forma di Horn tramite le regole riportate qui. Che valori devono assumere A e B in maniera tale da ottenere M=L=P=Q=\text{Vero}? Quali valori potrebbero assumere invece A e B per ottenere M=L=P=Q=\text{Falso}?
Soluzione
Le diverse condizioni di AND/OR nei vari nodi sono espresse di seguito:
P\Rightarrow Q\equiv \neg P\vee Q\\ L\wedge M\Rightarrow P\equiv\neg(L\wedge M)\vee P\\ B\wedge L\Rightarrow M\equiv\neg(B\wedge L)\vee M\\ A\wedge P\Rightarrow L\equiv\neg(A\wedge P)\vee L\\ A\wedge B\Rightarrow L\equiv\neg(A\wedge B)\vee L\\
I valori di M=L=P=Q=\text{Vero} si ottengono se
A=\text{Vero},\,B=\text{Vero}Mentre i valori M=L=P=Q=\text{Falso} si ottengono quando almeno una tra A e B è impostata a Falso (o eventualmente entrambe).