L'applicazione dell'intelligenza artificiale alla geographic information

L’applicazione dell’intelligenza artificiale alla geographic information. M.Salvemini (*), D.Gentili (**), G.Giuffrida (***) (*) Università di Roma – La Sapienza, CAVEA - Dipartimento Caratteri dell'Architettura, Valutazione e Ambiente, Univ. di Roma, Piazza Borghese,9 – 00186 Roma, Tel: (39-6) 49918830 , Fax: (39-6) 49918873 E-mail: mauro.salvemini@uniroma1.it (**) Università di Roma – La Sapienza, E-mail: daniele.gentili@uniroma1.it (***) Computer Science Department - University Of California, Los Angeles, E-mail: giovanni@cs.ucla.edu ABSTRACT Questa paper presenta le possibili applicazioni dell’intelligenza artificiale nella risoluzione di problemi nella geographic information, quali: il controllo della correttezza e della congruenza dei dati, la soluzione di eventuali errori presenti in una cartografia e la possibilità estrapolare nuovi dati a partire dalle informazioni cartografiche. In particolare si presenta il linguaggio basato sulle regole chiamato Gclips, che permette l’implementazione di sistemi esperti orientati all’analisi spaziale, topologica e geometrica. In tale software la conoscenza degli oggetti grafici, delle loro proprietà e delle relazioni che li legano può essere facilmente codificata in un insieme di fatti e regole. Verrà illustrato un esempio di applicazione sviluppata con questo linguaggio, mostrando le regole necessarie alla sua implementazione, nonché i risultati ottenuti ed i vantaggi derivanti da questo tipo di soluzione. This paper presents some application on artificial intelligence to solve problem about the geographic information, as: check error or congruence on data, the solution of some problems on digital cartography and the extraction of new information from data existing. In particular it describe a rule based language, called G-CLIPS, for implementing intelligence application oriented to the geometrical and topological reasoning. In this software the knowledge on graphical shape with his properties, and relations are code in to a set of rules and facts. Moreover, the paper contains an example of artificial intelligence application applies to GIS, to show the effectiveness of this method. The example describe the implementation of rule and result, we have obtained. INTRODUZIONE Negli ultimi anni si è assistito ad un progressivo miglioramento delle interfacce utente nei sistemi geografici e questo sviluppo ha portato, spesso all'implementazione di meta linguaggi, con i quali operazioni complesse, come ad esempio un overlay tra due mappe, può essere eseguito con un semplice comando. Al contrario, lo stesso miglioramento non si è avuto nello sviluppo di shell per la creazione di applicazioni GIS intelligenti, in grado di emulare ragionamenti umani come il semplice riconoscimento dei differenti componenti grafici (palazzi, strade, fiumi, idranti) contenuti in una mappa. Un sistema che è in grado di riconoscere i vari modelli grafici e successivamente di elaborare le informazioni che rappresentano, può essere di aiuto in molti settori come l'interpretazione di immagini aeree (McKeown '85, Meisels '88), nel controllo della correttezza e congruenza dei dati e nella soluzione di eventuali errori presenti in una cartografia. I passi di risoluzione per questi problemi sono diversi, ma la definizione di una base di conoscenza di fatti grafici e la definizione di un linguaggio che consente l'iterazione con l'utente, permette di sviluppare le soluzione dei singoli casi in modo più semplice. In questa paper viene presentato un linguaggio basato sulle regole, G-CLIPS, che permette l'implementazione di sistemi esperti orientati ai ragionamenti geometrici, spaziali e topologici. La conoscenza grafica di figure geometriche , delle loro proprietà e delle relazioni con gli altri oggetti è rappresentata da un insieme di fatti. Il G-CLIPS rappresenta un valido supporto delle applicazioni GIS intelligenti (Salvemini '90). L'ARCHITETTURA DI FUNZIONAMENTO DEL GCLIPS Il G-CLIPS è stato sviluppato a partire da un'altro linguaggio a regole chiamato CLIPS. Quest'ultimo è stato sviluppato dalla AIS (Artificial Intelligence Section) del NASA/Johnson Space Center, come soluzione ai problemi incontrati durante l'utilizzo di altri sistemi esperti basati sul linguaggio LIPS. I maggiori problemi incontrati furono la difficoltà di interfacciare il LISP con i linguaggi con programmazione tradizionali e la scarsa disponibilità del LISP sui sistemi convenzionali. Per risolvere questi problemi l' AIS decise di sviluppare un nuovo sistema esperto completamente integrato con il linguaggio C: il 'C' Language Product System (CLIPS). Questo è estremamente portabile e risulta facilmente integrabile con il linguaggio C. Questa integrazione può avvenire tramite l'inserimento del codice CLIPS all'interno del programma C, oppure mediante la definizione di funzioni esterne da richiamare nelle regole CLIPS. Grazie a quest'ultima il G-CLIPS aggiunge nuove funzionalità al CLIPS che possono essere riassunte in : ƒ predicati grafici che sono stati aggiunti all'insieme dei predicati CLIPS, che possono essere utilizzati nella parte destra e nella parte sinistra delle regole ƒ un meccanismo basato sui fatti con il quale è possibile rappresentare una immagine, che prevede la definizione di quest'ultima mediante entità grafiche di base (punti, linee, polyline, etc...). Gli elementi vengono memorizzati e gestiti dalle regole definite dall'utente come dei normali fatti. ƒ Un motore grafico con predicati e funzioni per visualizzare le informazioni grafiche gestite dal GCLIPS. La struttura del GCLIPS può essere riassunta dallo schema di figura 1, in cui le parti in grigio rappresentano le estensioni sviluppate sul CLIPS. Figura 1: Architettura GCLIPS Il motore grafico restituisce i dati al CLIPS mediante i valori restituiti delle funzioni o mediante lo scambio di parametri. Le informazioni grafiche sono codificate mediante fatti all'interno della memoria e sono direttamente accessibili dal motore grafico in modo che i predicati grafici possono modificarne il contenuto. Ad esempio la funzione ConnectPoly che consente la connessione di due polilinee se l'angolo formato risulta maggiore di 135°, lavora accedendo direttamente ai fatti delle due polilinee, rimovendo ed inserendo nuovi fatti senza che l'utente debba specificare nessun assert o retract. LE FUNZIONI DEL GCLIPS Il GCLIPS definisce un insieme di predicati per il controllo delle proprietà geografiche e topologiche delle componenti dell'immagine. Le proprietà che possono essere controllate sono, ad esempio: due punti sono dalla stessa parte rispetto ad una linea, un punto specificato è contenuto all'interno di un poligono, un poligono è contenuto dentro un altro poligono, due linee hanno punti in comune oppure un insieme di punti può essere approssimato da linee sequenziali. E' stato previsto un insieme di funzioni per l'elaborazione grafica e la misura come ad esempio: la distanza tra due punti, la distanza tra un punto ed una polilinea oppure la lunghezza di un segmento. Per il motore grafico è previsto un insieme di funzioni con le quali è possibile definire una viewport specificando offset e fattore di ingrandimento, gestire il mouse e tracciare, punti ed archi. L'ANALISI DEGLI ERRORI ED INCONGRUENZA SU ELEMENTI LINEARI Un applicazione GIS intelligente può essere utilizzata per la rilevazione e la conseguente correzione di errori eventualmente presenti all'interno di una mappa. Per mostrare la validità del G-CLIPS come supporto alla creazione di una applicazione con le caratteristiche sopracitate, supponiamo di avere una mappa contenente isolinee di altezze differenti, in cui ciascuna è composta da una o più polilinee. Il problema che si può presentare è quello della discontinuità tra le varie polilinee. Con il GCLIPS mostreremo come è semplice costruire una applicazione di IA che rileva le discontinuità presenti e nei casi previsti dal sistema le risolve automaticamente secondo una specifica regola (vedi Figura 2 ): (x2,y2) B A (x1,y1) (x4,y4) C D (x3,y3) (caso 1) (caso 2) Figura 2: Regola di connessione Gli estremi (x1, y1) e (x2, y2) di due polilinee (caso 1) possono essere connessi SE si trovano alla stessa altezza Z, SE la distanza tra di due punti è minore di 15m e SE gli angoli A e B formati dall'unione sono maggiori di 135° . Se la connessione non può essere effettuata (caso 2) si analizzano in punti (x3,y3) e (x4,y4) precedenti agli estremi, come in precedenza fatto. Il procedimento può essere effettuato a ritroso per un massimo di 5 punti per polilinea, dopo di che la discontinuità viene considerata irrisolvibile automaticamente. L'applicazione mostrata qui cerca di emulare il ragionamento di un operatore che deve compiere lo stesso compito senza ovviamente conoscere la realtà al suolo. Le procedure che vengono eseguite sono: 1.Identificare i vertici sconnessi, segnando gli estremi delle polilinee che non sono connessi con gli estremi di altre; 2.Trovare le coppie di vertici candidate all’unione, per ciascun vertice sconnesso cerca quello a cui và collegato (il più vicino con altezza uguale) per chiudere l'isolinea; 3.Collegare le varie coppie se rispettano le regole date. Collega le due isolinee relative ai vertici, se rispettano la regole di connessione; 4.Calcolare i vertici ancora sconnessi. Segna tutte le discontinuità che non sono state risolte per comunicarle all'operatore; REGOLE GCLIPS In questa sezione viene mostrato come i passi che l'operatore esegue vengono tradotti nelle regole G-CLIPS e come queste modificano la base di conoscenza. La Figura 3 mostra l'evoluzione dei fatti prodotta da Macro-Regole, ciascuna delle quali può essere il risultato dell'applicazione di più regole: Base di conoscenza Fatti che le rappresentano isolinee Insieme delle regole Se gli estremi sono disgiunti evidenzia – assert di un fatto - Fatti delle isolinee e Fatti degli disgiunt Estremi i Fatti delle isolinee e Coppie di estremi disgiuntida risolvere Fatti delle isolinee e corrett Estremi non disgiunti risolti Se esiste un punto (x1,y1) e un punto (x2,y2) ed la distanza tra di loro è la minima possibile per (x1,y1) assert della coppia (x1,y1,x2,y2) Se la coppia (x1,y1,x2,y2) rispetta la regole di connessione allora collega gli estremi (x1,y1) (x2,y2) delle rispettive polilinee Figura 3: Evoluzione della base di conoscenza La sintassi delle regole GCLIPS è simile a quella di tutti i liguaggi a regole, in cui ogni regola è composta da due parti: la parte delle condizioni o left-hand-side (LHS) e la parte dell'azione o righthand-side (RHS). Anche le regole per istanziare le variabili sono simili a quelle degli altri RBLs. Di seguito si mostrerà l'implementazione in G-CLIPS, di alcuni passi per la soluzione del problema. Estremi disgiunti Questo passo effettua la ricerca dei punti sconnessi nell'insieme di isolinee. Ciascuna di queste è composta da una o più polilinee, rappresentate dal fatto “(poly Codice Altezza x1 y1 ... xn yn) “ dove “Codice” “ed Altezza” rappresentano rispettivamente un codice univoco per ciascuna polilinea ed la quota (Z). Un estremo viene considerato sconnesso se non esiste nessun altro estremo che coincide con quello considerato. Per controllare se un punto di una polilinea è sconnesso viene utilizzata la funzione IsConnectPoly come mostrato nel codice di seguito: (defrule CercaSconnessi (declare (salience 50)) (cmd cs) ?c1 <- (poly ?Codice ?Altezza ?ax1 ?ay1 $?poligono ?axn ?ayn) => (bind ?Upper (+ 4 (length $?poligono))) (bind ?pos (integer (/ ?Upper 2))) (if (IsConnectPoly ?Codice ?Altezza 1 ?ax1 ?ay1) then ; (printout t "true 1 " ?Codice crlf) else (assert (ppoly ?Codice ?Altezza 1 ?ax1 ?ay1)) ) (if (IsConnectPoly ?Codice ?Altezza ?pos ?axn ?ayn) then ; (printout t "true 2 " ?Codice crlf ) else (assert (ppoly ?Codice ?Altezza ?pos ?axn ?ayn)) ) ) La regola segna tutti i punti sconnessi con il fatto (ppoly Codice Altezza Posizione x y) dove Codice ed Altezza conservano il significato che avevano nel fatto poly, mentre Posizione, x ed y sono rispettivamente la Posizione dell'estremo nella polilinea ( primo o ultimo) e le sue coordinate. Dopo che tutti i punti sono stati analizzati si ottiene la situazione mostrata in Figura 4. Figura 4: Punti sconnessi Collega le coppie di punti estremi Questo passo è importante per l'applicazione perché risolve alcune discontinuità trovate secondo la regola di connessione. Durante i passi precedenti l'applicazione ha identificato tutte le coppie di punti che rappresentano discontinuità tra le isolinee. Le coppie sono rappresentate dai fatti “(Coppia Altezza Distanza Pos1 Cod1 Pos2 Cod2)” dove Altezza e Distanza sono l'altezza e la distanza tra i due punti, mentre le coppie Posx Codx identificano gli estremi mediante il codice della polilinea a cui appartengono e la posizione (il primo o l'ultimo). Il fatto MaxDistance rappresenta la distanza massima consentita per la soluzione. La regola per la soluzione è mostrata di seguito: (defrule AggiornaPoligoni (declare (salience 40)) (cmd ap) ?c1 <- (Coppia ?Altezza ?Distanza ?Pos1 ?Cod1 ?Pos2 ?Cod2) (MaxDistance ?Massimo) => (if (< ?Distanza ?Massimo) then (bind $?Coor (GetPoint ?Pos1 ?Cod1 ?Pos2 ?Cod2)) (if (ConnectPoly 135 5 ?Pos1 ?Cod1 ?Pos2 ?Cod2) then (retract ?c1) (bind ?*Risolti* (+ ?*Risolti* 2)) else (retract ?c1) (bind ?*Errore* (+ ?*Errore* 1)) ) else (bind ?*TroppoGrandi* (+ ?*TroppoGrandi* 1)) ) ) Come si può notare la LHS considera tutte le coppie trovate, mentre nella RHS viene controllata se la distanza rispetta il vincolo imposto da MaxDistance. Successivamente la connessione viene eseguita dalla funzione ConnectPoly che riceve come parametri oltre alle coppie Posx Codx per i punti , anche l'angolo minino richiesto e il numero di punti massimo che possono essere considerati. Le variabili ?*Errore* ,?*TroppoGrandi* ed ?*Errore* sono utilizzate per mantenere una statistica dei risultati ottenuti. L'elaborazione finale dell'applicazione è mostrata in Figura 5. Per mettere ancor più in evidenza il risultato ottenuto, la mappa finale è stata sovrapposta a quella iniziale, i tratti neri corrispondono alle correzioni apportate. Figura 5: Elaborazione Finale CONCLUSIONI L'esempio ci permette di evidenziare come un software di intelligenza artificiale può venire in aiuto in quelle situazioni in cui è richiesto un intervento “intelligente” sui dati. L'individuazione e la correzione degli errori sono solo un esempio delle possibilità offerte dall'intelligenza artificiale. Il G-CLIPS, ad esempio, è stato scelto come shell di intelligenza artificiale all'interno del progetto GIMMI - Geographic Information and Mathematical Models Inter-operability - avviato nell'aprile 2002. GIMMI ha come obbiettivo la creazione di una infrastruttura tecnologica, per la stima dell'impatto ambientale dei pesticidi, che funga da ponte tra gli utenti (agricoltori, ecc…), gli scienziati (geologi, chimici, università,…), i Service Provider (pubblica amministrazione, industrie chimiche, …) ed i Data Provider (esperti in pesticidi, stazioni meteorologiche, …). In tale ambito il software Gclips verrà utilizzato come un possibile strumento per lo studio (datamining, analisi della correttezza, seamless... ) delle diverse informazioni geografiche fornite dai data provider. La prima versione della shell G-CLIPS è già disponibile e ulteriori miglioramenti sono in fase di sviluppo, ad esempio si sta cercando di migliorare l'efficienza del software creando nuove strutture dati interne per le immagini. BIBLIOGRAFIA McKeown D.M., Harvey W.A., NcDermott J. 1985, “Rule Based Interpretation of Aerial Imagery”, in PAMI-7 N.5, IEEE. Meisels A., Bergman S. 1988, “Finding Object on Aerial Photographs: A Rule-Base Low Level System”, University of the Negev, ISRAEL; apparso su Proceedings of Conputer Vision and Pattern Recognition ’88, IEEE. Salvemini M. 1990, “Ambiente, Territorio ed Informatica”, Pirola Ed.,Milano