SOMMARIO INDIETRO AVANTI


Intelligenza Artificiale e Linux (2nda Edizione)


di   Anderson Silva

traduzione di   G. V. Felchero e P. Blason


[Quella che segue è una revisione dell'articolo apparso nel luglio del 1999. L'articolo conteneva infatti alcuni errori e vi era omessa la conclusione. In questa nuova versione ho corretto questi errori e ho aggiunto alcuni riferimenti per coloro che sono interessati ad approfondire la conoscenza nel campo dell'Intelligenza Artificiale. Vorrei mettere in evidenza che questo articolo copre solamente una piccolissima area dell'IA. -AS]


L'intelligenza artificiale è un argomento molto controverso, ma il modo in cui lo affronterò in questo articolo è semplice e rapido. Il modo in cui io ho affrontato l'IA non è attraverso l'aspetto filosofico o biologico, ma solamente come argomento computazionale. Quando gli uomini vogliono volare, non hanno bisogno di studiare gli uccelli per imparare come fare, ma solamente prendere l'aereo. E' questo il modo con cui intendo affrontare l'IA. Noi vogliamo risolvere puzzle e giochi con il computer senza fare confronti veramente con il modo in cui un essere umano esegue i compiti diversamente da un computer.

Per la prima volta nella storia della mia scuola, ci veniva offerto un corso di Intelligenza Artificiale (IA). Io ero particolarmente eccitato per questa novità dal momento che avevo sentito parlare molto di IA, ma sull'argomento non c'è veramente molto materiale nelle riviste o negli articoli on line.

Probabilmente l'esempio più famoso di un'applicazione di IA è il test di Turing. Il test consiste in una persona che sta in una stanza con un terminale di computer, e questa persona incomincia a parlare con il computer. Alla fine la persona dovrebbe essere in grado di capire se ha parlato con una persona reale all'altra estremità del terminale o con un programma di computer. E se l'utente confonde la persona con il computer allora noi avremmo realizzato l'IA.

Al LU abbiamo scelto Prolog come strumento di implementazione per l'IA. I nostri laboratori scolastici sono basati su Windows NT ed abbiamo solamente una macchina Linux per gli studenti. Ma io sono stato un utente Linux per quasi due anni e volevo implementare tutte le mie attività Prolog in Linux.

Ho fatto alcune ricerche sul Web e ho trovato un eccellente compilatore Prolog per Linux. Prolog è come Linux in un certo senso, ci sono diversi flavor a cui si può attingere. Quello che ho scelto è stato SWI Prolog (www.hio.hen.nl/faq/SWI-Prolog.html). Il Prolog è un linguaggio molto flessibile. Diversamente da altri linguaggi come C, C++ o Java, Prolog è basato sulla logica matematica formale, in questo caso: il calcolo dei predicati. Un programma Prolog è normalmente costituito da fatti con un insieme di regole. Per raggiungere la soluzione finale il programma deve soddisfare questo insieme di regole. L'interpretazione di queste regole consente al computer di dedurre da solo la soluzione. In Prolog i fatti sono normalmente memorizzati in un file separato chiamato base di conoscenze, e le regole in un altro file che è l'effettivo programma.

Permettetemi di mostrarvi un algoritmo di ricerca decisamente fondamentale conosciuto come ricerca in profondità (Depth First Search) (Fate click per vedere l'immagine relativa).

Questo programma vi permette di trovare un percorso di risoluzione dallo START point (punto di partenza) ad alcuni GOAL (obiettivi). L'algoritmo DFS è piuttosto semplice da implementare, dal momento che è un algoritmo ricorsivo. Ciò che DFS fa è attraversare il successore di ciascun nodo in maniera sequenziale, perciò anche se è un modo facile per implementare un algoritmo di ricerca, non è efficiente dal punto di vista temporale.

Ma perché fare una ricerca in un grafo?

I nodi di un grafo corrispondono a stati parziali della soluzione di un problema e gli archi corrispondono a passaggi in un processo di problem solving. Il grafo definisce anche una o più condizioni obiettivo (goal), che sono soluzioni all'istanza di un problema. Il processo che trova un percorso di soluzione dal punto di partenza ad un obiettivo è chiamato Ricerca nello spazio degli stati (Luger and Stubblefield 1997).

Attraverso un grafo potete trovare le soluzioni a diversi problemi che sembrano così semplici nella nostra mente. Per esempio, un'intera partita di scacchi può essere rappresentata con grafi, problemi matematici, potenzialmente qualsiasi cosa implichi prendere decisioni.


Il seguente programma è la rappresentazione del suddetto grafo in Prolog. [Versione solo testo]

=========LIST #1=============

% Name:   Anderson Silva
% Date:   March 10, 1999

% ================================
% Un grafo che sarà utilizzato per un
% algoritmo di ricerca in profondità  
% (Depth First Search Algorithm)
% nella base di conoscenze.
% ================================

% linked/2
% Un nodo e i suoi successori

linked(a, [b,c,d]).
linked(b, [e,f]).
linked(c, [g,h]).
linked(d, [i,j]).
linked(e, [k,l]).
linked(f, [l,m]).
linked(g, [n]).
linked(h, [o,p]).
linked(i, [p,q]).
linked(j, [r]).
linked(k, [s]).
linked(l, [t]).
linked(m, []).
linked(n, []).
linked(o, []).
linked(p, [u]).
linked(q, []).
linked(r, []).
linked(s, []).
linked(t, []).
linked(u, []).

% arc/2
% Una regola che controlla per vedere se 
% c'è un arco tra due nodi dati.

arc(X,Y):- linked(X,L), member(Y,L).

L'algoritmo che cerca uno specifico obiettivo nel grafo: [Versione solo testo]

=========# LIST #2=============

% Name:   Anderson Silva
% Date:   March 10, 1999
% ================================
% Questo è l'algoritmo di ricerca in 
% profondità implementato in Prolog 
% che utilizzerà la base di conoscenze
% graph.pl 
% ================================

% reverse_write/1
% Inverte l'ordine della pila.

reverse_write([]).
reverse_write([H|T]):-reverse_write(T), write(H), nl.

% solve/2
% Rappresenta il percorso in ordine
% inverso dal momento che dfs viene
% implementato come una pila

solve(INode, Solution):- consult('graph.pl'),
                         query_goal,
                         dfs([], INode, Solution),
                         reverse_write(Solution).

% query_goal/0
% Crea l'obiettivo da raggiungere
% durante l'esecuzione
% Si incomincia con abolish, così se 
% solve viene eseguito più di una volta,  
% si assicurerà che il vecchio obiettivo 
% venga trascurato e solo quello 
% nuovo venga esplorato.

query_goal :- abolish(goal(Node)),
              write('Obiettivo? [Seguito da un punto]'),
              nl,
              read(Node),
              assert(goal(Node)).


% goal/1
% Quando il programma viene eseguito
% per la prima volta query_goal richiede 
% che abolish abbia almeno un obiettivo
% ed è questo il motivo per cui viene 
% utilizzato goal(standard).

goal(standard).

% dfs/3
% L'algoritmo ricorsivo effettivo della
% ricerca in profondità

dfs(Path, Node, [Node|Path]):- goal(Node).
dfs(Path, Node, Sol):- arc(Node, Node1),
                       \+ member(Node1, Path),
                       dfs([Node|Path], Node1, Sol).

Con questo programma Prolog, sarete in grado di eseguire una Ricerca in un Grafo sul vostro computer. Notate che LIST #1 definisce il grafo, perciò potete fare modifiche in LIST #1 e fare i vostri propri grafi, e vedere se l'algoritmo troverà il nodo che state cercando.

Ci sono diversi altri algoritmi di ricerca per risolvere i problemi di IA, per esempio Breadth-First Search, Heuristic Search, Pattern-Directed Search, e altri.

Come detto, questo è solo un piccolo argomento in IA, che pensavo potrebbe essere utile per chi di voi voglia impararne di più riguardo a IA. Se volete alcune altre aree di ricerca, ma non sapete nemmeno da dove incominciare, ecco alcuni argomenti: Sistemi Esperti, Robotica, Rappresentazione della conoscenza, Logica Fuzzy, Linguaggio naturale, Ragionamento automatico, e altri.

Infine, voglio lasciarvi con tre titoli di libri sull'IA che ho utilizzato al college.

  1. Artificial Intellegence: Structures and Strategies for Complex Problem Solving. Luger, George and Stubblefield, Willian.
  2. Prolog Programming in Depth. Covington, Michael et al.
  3. Are We Unique?. Trefil, James.


Copyright, per la versione americana, © 2000 Anderson Silva
Pubblicato sul n. 50 della Linux Gazette, Febbraio 2000
Copyright, per la versione italiana, © 2000 LGEI n. 2 Anno IV
SOMMARIO INDIETRO AVANTI