Esame di Ingegneria della Conoscenza e Sistemi Esperti

MyClips Documentazione di sistema

Francesco Capozzo (465645) 21/05/2012

i

Sommario

1 Sistema esperto ......................................................................................................................................... 1

2 Motore inferenziale ................................................................................................................................... 1

3 CLIPS .......................................................................................................................................................... 2

3.1 Regole ................................................................................................................................................ 2

3.2 Fatti .................................................................................................................................................... 3

3.3 Algoritmo Rete ................................................................................................................................... 3

3.3.1 Composizione della Rete ........................................................................................................... 4

3.3.2 Perché Rete è efficiente ............................................................................................................ 6

3.4 Strategie ............................................................................................................................................ 8

3.5 Altre componenti non trattate .......................................................................................................... 8

3.5.1 Moduli ........................................................................................................................................ 8

3.5.2 Funzioni ..................................................................................................................................... 8

3.5.3 Variabili globali .......................................................................................................................... 8

4 MyClips ...................................................................................................................................................... 9

4.1 Il parser .............................................................................................................................................. 9

4.2 L’algoritmo di matching ..................................................................................................................... 9

4.2.1 Implementazione di Rete .......................................................................................................... 9

4.2.2 Nodi aggiunti ........................................................................................................................... 10

4.2.3 Propagazione dei fatti nella Rete............................................................................................. 10

4.2.4 I Token ..................................................................................................................................... 12

4.3 Rappresentazione dei fatti .............................................................................................................. 13

4.4 Rappresentazione delle regole ........................................................................................................ 13

4.4.2 Funzioni ................................................................................................................................... 13

4.4.3 Predicati ................................................................................................................................... 14

4.4.4 Azioni ....................................................................................................................................... 14

4.5 L’agenda........................................................................................................................................... 14

5 Dettagli sull’implementazione ................................................................................................................. 15

5.1.1 La rappresentazione dei Nodi .................................................................................................. 15

5.1.2 La rappresentazione delle WME .............................................................................................. 15

5.1.3 Rappresentazione dei Token ................................................................................................... 16

6 Confronto fra MyClips e CLIPS ................................................................................................................. 16

ii

6.1 Caratteristiche replicate .................................................................................................................. 17

6.1.1 Tipi fondamentali ..................................................................................................................... 17

6.1.2 Costrutti disponibili ................................................................................................................. 17

6.2 Vincoli rilassati e differenze ............................................................................................................. 18

6.2.1 Formato del primo campo ....................................................................................................... 18

6.2.2 Gestione del matching negativo .............................................................................................. 19

7 Interazione con il sistema ........................................................................................................................ 21

7.1 Installazione e configurazione ......................................................................................................... 21

7.1.1 Requisiti ................................................................................................................................... 21

7.1.2 Ottenere il codice sorgente ..................................................................................................... 21

7.1.3 Elementi forniti con il sistema ................................................................................................. 21

7.2 Creazione di un nuovo sistema esperto .......................................................................................... 21

7.2.1 Modularizzazione..................................................................................................................... 22

7.2.2 Caratteristiche di supporto allo sviluppo ................................................................................ 22

7.3 Estendibilità del sistema .................................................................................................................. 25

7.3.1 Aggiungere nuove Azioni ......................................................................................................... 25

7.3.2 Aggiungere nuove Funzioni e Predicati ................................................................................... 25

7.3.3 Aggiungere nuove Azioni, Predicati e Funzioni manualmente ................................................ 26

8 Formalizzazione della grammatica riconosciuta ..................................................................................... 27

9 Esempi ..................................................................................................................................................... 28

10 Bibliografia ........................................................................................................................................... 30

Introduzione

1

Introduzione

Questo documento presenta una trattazione tecnica relativa alla realizzazione di un sistema di sviluppo per

sistemi esperti in linguaggio Python. Il sistema è stato realizzato come progetto d’esame per il corso di

Ingegneria della Conoscenza e Sistemi Esperti.

Lo scopo di questa trattazione è quello di illustrare le caratteristiche principali del sistema, denominato

MyClips, e fornirne una documentazione di base.

Prima di poter approfondire le caratteristiche di MyClips è necessario però fornire alcune informazioni di

base che chiariscano meglio l’ambito in cui l’applicativo è stato sviluppato.

1 Sistema esperto Un sistema esperto è un sistema basato su conoscenza, cioè un software che, usando conoscenza e

procedure di inferenza, è in grado di risolvere problemi specifici simulando il comportamento di uno o più

esperti del dominio del problema. I sistemi esperti consentono di risolvere problematiche, altrimenti

difficilmente risolvibili, con prestazioni paragonabili a quelle umane ragionando euristicamente su una

rappresentazione parziale (o incerta) della realtà del problema. Inoltre, durante il processo di ragionamento

sono in grado di interagire con l’utente in maniera efficace fornendo indicazioni sulle modalità di

ragionamento e giustificando le scelte intraprese per giungere ad una soluzione.

Un sistema esperto è costituito da tre componenti principali:

Base di conoscenza: rappresenta in forma dichiarativa l’esperienza del sistema, l’insieme di tutte le

conoscenze formalizzate che verranno utilizzate per concretizzare un ragionamento in grado di

fornire una soluzione ad un problema appartenente al dominio del sistema esperto;

Motore inferenziale: un componente che simula il processo di ragionamento tramite il quale è

possibile trarre delle deduzioni logiche partendo dall’esperienza presente nella base di conoscenza,

ampliandola;

Modulo di interfaccia: è la componente che si occupa dell’interazione con l’utente e ha lo scopo di

agevolare l’utilizzo del sistema ad una o più categorie differenti di utenza.

2 Motore inferenziale Il motore inferenziale rappresenta il nocciolo di ragionamento alla base di un sistema esperto. Consente di

inferire nuova conoscenza sulla base di un ragionamento logico applicato all’insieme delle conoscenze

pregresse inserite e formalizzate all’interno della Knowledge base da un esperto del dominio.

Il funzionamento di un motore inferenziale può essere riassunto tramite il ciclo detto recognize-act.

Nella prima parte del ciclo, il motore inferenziale interpreta lo stato del sistema (della realtà, o meglio di

una sua rappresentazione formalizzata e parziale contenuta all’interno della memoria di lavoro)

confrontandolo con l’insieme di conoscenze a disposizione, espresse come regole di produzione. Tutte le

regole di produzione che avranno ottenuto un riscontro con lo stato del sistema (più precisamente tutte le

regole che vedranno soddisfatte tutte le condizioni di attivazione) verranno poste all’interno di una agenda

Introduzione

2

di attivazione. La componente che ha l’onere di eseguire il confronto fra la memoria di lavoro e l’insieme

delle regole di produzione è nota con il nome di pattern matcher.

Una volta ottenuta una lista di regole applicabili alla situazione, dall’agenda ne viene scelta una sulla base di

determinati principi. La strategia di risoluzione dei conflitti fornisce l’insieme di questi principi che

permettono di determinare la migliore regola da attivare, fra tutte quelle applicabili individuate.

A questo punto il motore inferenziale applica l’insieme di azioni specificate all’interno della regola di

produzione scelta che consentono di alterare lo stato della working memory ed inferire nuova conoscenza

o interagire con l’utente.

Quindi il processo ricomincia dal principio, un nuovo set di regole applicabili allo stato del sistema

modificato dall’applicazione precedente viene individuato e fra queste ne viene scelta una da attivare. Il

processo ha termine nel momento in cui, in seguito all’applicazione di una regola, il sistema si trova in uno

stato di goal o non ci sono altre regole applicabili allo stato.

Lo stato di goal può essere rappresentato sia tramite l’espressione di una specifica configurazione della

working memory, sia esprimendo un insieme di condizioni sulla working memory che verifichino il goal.

Queste condizioni sono espresse a loro volta nella forma di regole.

3 CLIPS CLIPS è un tool per lo sviluppo di sistemi esperti. Lo sviluppo del primo prototipo risale al 1985, presso il

NASA-Johnson Space Center (1). Per supportare gli ingegneri della conoscenza, CLIPS fornisce (fra le

caratteristiche inerenti a questa trattazione):

un motore inferenziale di tipo Forward Chaining che supporta l’aggiunta dinamica a runtime di

nuove regole

un set di strategie di risoluzione dei conflitti modificabili durante l’esecuzione che consente di

alterare dinamicamente l’ordine di attivazione delle regole

rappresentazione multi paradigmatica della conoscenza: programmazione a regole,

programmazione orientata ad oggetti e sviluppo procedurale.

strumenti di supporto durante lo sviluppo dei sistemi (tracciamento delle attivazioni…)

Nell’ambito di questo documento tratteremo solamente lo sviluppo di sistemi tramite regole, in modo da

poter fornire in una fase successiva un confronto più chiaro con il sistema concorrente MyClips.

3.1 Regole La conoscenza può essere espressa nella forma di insiemi di regole. Una regola corrisponde ad una

espressione di tipo Condizione-Azione. Sarà ritenuta applicabile se l’insieme di condizioni che rappresenta

vengono soddisfatte da uno o una combinazione di elementi contenuti nella working memory.

Nella parte Condizione di una regola vengono espressi i requisiti di applicabilità come congiunzione di

requisiti atomici. L’espressione di questi requisiti possono comprendere l’utilizzo di espressioni costanti,

funzioni, variabili anonime, variabili assegnate che risultino coerenti fra più condizioni differenti della stessa

regola e test su valori.

Nella parte Azione della regola vengono invece espresse tutte le azioni che verranno eseguite dal sistema

qualora la regola venisse attivata. L’elenco di azioni disponibili in CLIPS comprende sia la possibilità di

Introduzione

3

asserire o ritrattare elementi della working memory (la forma più semplice di inferenza si può

implementare in questo modo), sia di eseguire operazioni di interfaccia con l’utente fornendo o

richiedendo informazioni (nella forma più semplice, l’inserimento di testo tramite tastiera).

Inoltre CLIPS offre anche un set di operazioni per l’utilizzo di sistemi I/O, la modifica della strategia di

risoluzione dei conflitti, l’alterazione dell’agenda e l’aggiunta o la rimozione di regole a runtime.

Le regole (e gli altri elementi) vengono fornite al sistema tramite l’utilizzo di una grammatica. Un esempio

di una semplice regola espressa nella grammatica supportata da CLIPS è disponibile in Figura 1.

Figura 1 – Esempio di regola per sistema CLIPS

3.2 Fatti I fatti rappresentano le unità fondamentali con cui esprimere lo stato del sistema. I fatti sono espressi in

CLIPS come una sequenza di simboli, numeri o stringhe quotate. Una volta asseriti, i fatti vengono

memorizzati all’interno della working memory. Durante la fase di recognize-act, il pattern matcher tenterà

di effettuare un riscontro fra l’elenco di condizioni di ogni regola e un insieme di fatti memorizzati

all’interno della working memory.

CLIPS fornisce due modalità di asserzione dei fatti all’interno del sistema: attraverso l’utilizzo del costrutto

deffacts o tramite l’utilizzo dell’azione assert all’interno della parte destra di una regola attivata. Il primo

costrutto, un esempio è disponibile in Figura 2, consente di asserire durante la fase di inizializzazione del

sistema una sequenza di fatti che rappresenteranno lo stato iniziale. Il secondo costrutto viene invece

utilizzato per modificare la working memory durante l’esecuzione del sistema.

Figura 2 - Esempio di definizione deffacts in sistema CLIPS

3.3 Algoritmo Rete Come detto in precedenza, ad ogni iterazione del ciclo recognize-act, il sistema deve provvedere a

identificare le regole attivabili, selezionarne una che modifichi il sistema e quindi applicare le modifiche. Il

ciclo viene ripetuto fino ad esaurimento delle regole applicabili.

Questo implica che per ogni ciclo, ogni regola venga confrontata con ogni combinazione di fatti nella

working memory in modo da identificare quelli che soddisfino le condizioni di attivazione. Come è facile

(defrule Uguaglianza_Termini “commento alla regola”

(is-maggiore-o-uguale ?termine1 ?termine2)

(is-maggiore-o-uguale ?termine1 ?termine2)

=>

(assert (is-uguale ?termine1 ?termine2)

)

(deffacts Fatti_Iniziali “una collezione di fatti iniziali”

(componente ruota macchina)

(componente voltante macchina)

)

Introduzione

4

immaginare, il costo computazionale di questi confronti cresce esponenzialmente con l’aumento del

numero di regole e di elementi della working memory. Questo comporta l’inutilizzabilità di sistemi esperti

complessi in scenari dove il tempo di attuazione sia un fattore importante senza l’ausilio di grossi sistemi di

calcolo.

Per risolvere questo problema, Charles L. Forgy (2) propose un algoritmo di pattern matching che non

richiedesse l’iterazione sul completo spazio della working memory per individuare le regole attivabili ad

ogni iterazione.

L’algoritmo presentato da Forgy nel 1982 con il nome di Rete si basava su una semplice considerazione:

raramente l’applicazione di una regola produce modifiche tali da richiedere la rivalutazione di tutte le

regole. È infatti molto più probabile che l’attivazione di regole, e l’asserzione o ritrattazione di fatti,

produca piccoli cambiamenti che possono essere assorbiti nel sistema senza dover portare ad una

rivalutazione completa dello spazio delle regole.

Sfruttando questa considerazione e considerando anche che spesso le regole condividono porzioni di

confronti fra loro, si giunge alla strategia di matching applicata dall’algoritmo: comporre le regole in

maniera tale da creare un grafo nel quale ogni nodo rappresenterà una condizione e nel quale condizioni

simili vengano condivise fra più regole. In questo modo, la rivalutazione delle regole verrà eseguita

semplicemente rivalutando la porzione del grafo che la modifica influenza e inoltre i confronti che sarà

necessario eseguire verranno condivisi fra più regole differenti, ottimizzando ulteriormente il processo.

3.3.1 Composizione della Rete

Materialmente per realizzare questo concetto, ogni regola (la sua parte “sinistra”, quella che contiene le

condizioni di attivazione) viene scomposta nelle sue condizioni di attivazione che a loro volta vengono

ulteriormente scomposte in condizioni atomiche. Una volta scomposte, le condizioni vengono

rappresentate come fossero nodi di un grafo e le correlazioni fra condizioni come archi fra i nodi. Inoltre,

per regole che condividono condizioni atomiche o composte, i nodi verranno condivisi. Ogni regola sarà

rappresentata da un nodo foglia speciale inserito nel sistema come ultimo elemento di congiunzione delle

varie componenti che descrivono le condizioni. Le condizioni appartenenti alla regola possono quindi essere

descritte come il percorso compiuto dal nodo principale del grafo fino a giungere al nodo foglia.

Il grafo, nella formulazione proposta da R. B. Doorebas nel 1995 (3) viene realizzato utilizzando otto tipi

diversi di nodi. Nello specifico:

1. Constant Test Node: realizza un confronto fra un elemento costante e un campo di un elemento

della working memory.

2. Alpha Memory: rappresentano dei contenitori di risconti parziali nel processo di valutazione di un

elemento della working memory. Questi nodi mantengono una lista di fatti che trovano riscontro

da una sequenza di nodi Constant Test Node. Chiaramente, l’utilizzo di nodi Alpha Memory è solo a

monte di elementi Constant Test Node.

3. Join Node: sono dei nodi che realizzano i controlli di coerenza fra i valori associati ad elementi

variabili all’interno delle condizioni. Si assicurano che le variabili appartenenti a diverse condizioni

siano coerentemente collegate a sequenze di fatti che verifichino la condizione. I Join Node

rappresentano un tipo di nodo a doppio input e vengono appunto usati per riunire in un solo ramo,

due diverse diramazioni del grafo e congiungerne i risultati delle valutazioni intermedie.

4. Beta Memory: come i nodi Alpha Memory, questi nodi sono delle banche dati di risultati intermedi

e vengono utilizzati per memorizzare i risultati che avranno avuto riscontro dai testi effettuati dai

Introduzione

5

nodi di tipo Join Node. In realtà sarebbe possibile fornire una formulazione alternativa del set di

nodi che non comprenda questo tipo specifico di nodi e che al loro posto preveda l’accorpamento

delle funzionalità dei Beta Memory all’interno dei nodi Join Node. Purtroppo questa soluzione, se

pure possibile, limiterebbe la capacità di condivisione dei nodi fra le diverse regole di produzione.

5. Negative Node: verificano le condizioni negative su elementi di coerenza nel binding delle variabili

fra le diverse condizioni. Le funzionalità sono analoghe a quelle dei Join Node, con la differenza che

gli elementi della working memory verranno propagati ai nodi figlo solo se non saranno disponibili

risconti. Questo nodo include le funzionalità dei Beta Memory per memorizzare i risultati intermedi

6. Ncc Node: permettono di rappresentare la negazione di una porzione della rete. Più semplicemente

corrispondono alla negazione di una congiunzione di condizioni

7. Ncc Partner Node: sono un tipo speciale di nodi utilizzati per completare le funzionalità del nodo

Ncc Node. Di fatto, verranno trattati congiuntamente

8. Production Node: nodi foglia, terminali che rappresentano la produzione. La loro rappresentazione

è dipendente dal tipo di implementazione del sistema scelta e quindi non verranno trattati.

I nodi di tipo Alpha Memory e Constant Test Node realizzano la così detta Alpha Network. Questa porzione

del grafico di fatto esegue confronti semplici su elementi costanti dei fatti senza tenere conto delle

variabili. I risultati intermedi dei confronti, memorizzati nelle Alpha Memory, verranno poi congiunti nella

seconda porzione del grafo, appunto la Beta Network. Questa è composta dai restanti nodi della lista,

combinati in maniera tale da riunire in modo adatto i confronti elementari eseguiti nella Alpha Network.

Prendiamo ad esempio una semplice sistema di questo tipo (utilizzando la notazione adottata da CLIPS):

Figura 3 - Semplice sistema di esempio in notazione CLIPS

Le condizioni della prima (e unica) produzione possono essere scomposte in prima analisi in due condizioni

indipendenti, ma per le quali deve essere verificato che il secondo campo degli elementi della working

memory che realizzazione le due condizioni siano uguali. Inoltre la prima condizione può essere

ulteriormente scomposta in due ulteriori condizioni atomiche quali la condizione che il primo campo

dell’elemento abbia valore A e che il terzo abbia valore C. Discorso analogo può essere fatto per la seconda

condizione.

Formalizzando quanto detto, la prima condizione verrà scomposta in due Constant Test Node, a seguito dei

quali verrà aggiunto un nodo Alpha Memory. La seconda condizione verrà scomposta in un elemento di tipo

Constant Test Node seguito da uno Alpha Memory. Infine, i due rami generati dalle due condizioni verranno

(defrule Produzione_1

(A ?b C)

(A ?b)

=>

)

(deffacts Fatti_Iniziali

(A B C)

(A B)

)

Introduzione

6

riuniti da un noto Join Node che effettuerà i controlli di coerenza per fare in modo che il binding della

variabile ?b sia coerente per entrambi i due risultati delle condizioni precedenti. Infine, al Join Node verrà

aggiunto un nodo Production Node che completerà il grafo. In Figura 4 è disponibile una rappresentazione

grafica della Rete appena descritta, con l’aggiunta di alcune considerazioni che verranno approfondite in

seguito: fra i Constant Test Node e i nodi Alpha Memory è stato frapposto un tipo speciale di Constant Test

Node che verifichi la correttezza della lunghezza degli elementi della working memory. Infine, per collegare

i nodi della Alpha Network con quelli della Beta Network è stato interposto un nodo di tipo Join Node che

non effettua verifiche ma che semplicemente converte gli elementi propagati dai nodi Alpha in valori

compatibili per essere elaborati dai nodi Beta: i Token.

Figura 4 - Rete generata dal sistema in Figura 3

3.3.2 Perché Rete è efficiente

Nel momento in cui un nuovo elemento viene inserito all’interno della working memory perché asserito

dall’attivazione di una regola, l’elemento viene notificano al nodo Root della Rete che provvederà a

propagarlo a tutti i figli. Qualora un tipo di nodo figlio preveda l’esecuzione di uno o una serie di test sul

valore propagato, il test verrà eseguito e l’elemento ulteriormente propagato solo se i test avranno avuto

successo. Questo implica che qualora diverse regole condividano uno o più nodi, il risultato dei test verrà

valutato una sola volta, indipendentemente dal numero di produzioni a cui quel nodo è collegato. Se il test

avrà successo, l’elemento verrà propagato a tutti i figli fino a giungere solo ai Production Node per i quali

tutte le condizioni saranno soddisfatte.

Per capire meglio il fenomeno, supponiamo di aggiungere una nuova regola al sistema descritto in Figura 3:

la regola descritta in Figura 5Errore. L'origine riferimento non è stata trovata., condivide con Produzione_1

la prima e la seconda condizione ed introduce una ulteriore condizione. E’ lecito attendersi che la Rete

ottenuta dal sistema precedente venga estesa da questa produzione con la semplice aggiunta delle

Introduzione

7

condizioni necessarie alla verifica della terza e dei nodi necessari a congiungere e verificare la coerenza del

binding delle variabili.

La Figura 6 rappresenta esattamente quanto descritto: i vecchi nodi della Produzione_1 sono stati condivisi

e sono semplicemente stati aggiunti i nodi necessari a verificare le condizioni mancanti di Produzione_2.

Nel momento in cui un nuovo elemento dovrà essere valutato, i nodi condivisi fra le due condizioni

effettueranno una sola volta la verifica e propagheranno i risultati.

Figura 5 - Produzione aggiunta a sistema in Figura 3

Figura 6 – Rete generata dal sistema in Figura 5

E’ evidente come il beneficio derivato dall’utilizzo di questa strategia sia più evidente con l’aumento del

numero delle produzioni e degli elementi nella working memory. Bisogna però tenere in considerazione il

fatto che questa soluzione risulta ideale solo nel caso in cui l’inserimento o la rimozione di regole dal

sistema non sia frequente. L’overhead generato dalla creazione del grafo, dall’individuazione dei nodi da

condividere e di quelli da aggiungere tende ad eclissare i benefici di questa implementazione qualora la

topologia del sistema cambiasse troppo spesso.

(defrule Produzione_2

(A ?b)

(A ?b C)

(?b A ?b)

=>

)

Introduzione

8

3.4 Strategie CLIPS offre sette diverse strategie di risoluzione dei conflitti per individuare la regola più appropriata da

applicare qualora più di una fosse disponibile contemporaneamente:

Depth strategy: alle regole diventate attivabili da meno tempo viene attribuita una priorità

maggiore. Questo significa che se una esecuzione di una produzione produce le condizioni di

attivabilità di altre regole, queste ultime avranno priorità maggiore rispetto a quelle che erano gia

attivabili in precedenza

Breadth strategy: esattamente l’opposto della depth strategy. L’ordine di attivazione viene gestito

come fosse una cosa

Simplicity strategy: regole più generali (cioè con un indice inferiore di confronti e variabili) avranno

precedenza su regole più particolari

Complexity strategy: criterio inverso della Simplicity Strategy. Si suppone che regole più complesse

siano sempre più adeguate rispetto a regole più generali

Lex strategy: l’ordine viene stabilito in base a quanto siano recenti i Token che attivano la regola

Mea strategy: simile a Lex strategy, ma anzicchè confrontare per intero due Token per decidere la

priorità di una regola rispetto ad un’altra, la comparazione è effettuata solo confrontando gli

elementi più recenti dei rispettivi Token.

La modifica della strategia è consentita durante l’esecuzione tramite l’uso del costrutto set-strategy

3.5 Altre componenti non trattate CLIPS è un tool di sviluppo molto vasto e potente. Chiaramente la maggior parte delle sue componenti è

stata ignorata in questa trattazione in quanto non inerente con lo scopo della stessa. Per alcune di esse

queste mi limito ad una breve citazione perché potrebbero essere ugualmente utili a comprendere

soluzioni alternative ad esse adottate da MyClips non senza richiedere una trattazione approfondita.

3.5.1 Moduli

CLIPS offre un sistema modulare che consente di specificare porzioni differenti del sistema e racchiuderle

all’interno di unità indipendenti. Il sistema di moduli offre funzionalità di information hiding e un sistema di

priorità di attivazione fra regole di moduli differenti.

3.5.2 Funzioni

L’estensione delle funzionalità di CLIPS è garantita tramite la possibilità di specificare nuovi set di funzioni,

sia tramite chiamate a funzioni di sistema native, sia attraverso il costrutto deffunction. Quest’ultimo

consente di specificare nuove funzioni a runtime, tramite l’utilizzo di una grammatica prefissata.

3.5.3 Variabili globali

In aggiunta alle variabili istanziate durante il processo di pattern-matching e disponibili anche nella

porzione RHS della stessa regola in cui sono definite, CLIPS offre dei costrutti per dichiarare un insieme di

variabili definite globali e utilizzabili in maniera indipendente e arbitraria da qualsiasi produzione, senza

tenere conto di chi effettivamente ha istanziato la variabile.

Prima parte

9

Prima parte

Presentazione del Sistema

4 MyClips MyClips si propone come un tool per lo sviluppo di sistemi esperti simile all’ambiente CLIPS e cerca di

replicarne, dove possibile, alcune delle caratteristiche.

L’interazione con il sistema è soggetta alla creazione di uno o più file in formato clp utilizzando una

grammatica simile a quella disponibile per CLIPS. Maggiori informazioni e una formalizzazione della

grammatica accettata sono disponibili nel paragrafo 8.Nel file possono essere specificati l’insieme di regole

che realizzano il sistema, il tipo di strategia di soluzione dei conflitti da adottare, l’insieme di fatti che

rappresentano lo stato e una serie di direttive proprie di MyClips per attivare funzionalità di debug del

sistema esperto.

4.1 Il parser La lettura e l’interpretazione dei file clp è affidata ad un parser creato utilizzando la libreria PyParsing (4). A

quest’ultima ho affiancato una libreria per la conversione delle grammatiche EBNF in parser PyParsing che

mi ha consentito di specificare la grammatica accettata utilizzando la notazione EBNF, delegando la

compilazione del parser. Una definizione della grammatica accettata è disponibile in forma estesa e

notazione EBNF come appendice nel paragrafo Formalizzazione della grammatica riconosciuta

4.2 L’algoritmo di matching Una componente importante di qualsiasi motore inferenziale è, come precedentemente descritto, la

componente responsabile dell’esecuzione del matching fra lo stato del sistema (le istanze dei fatti inseriti

nella working memory) e l’insieme di regole che compongono la base di conoscenza.

Per eseguire il matching, MyClips utilizza una implementazione dell’algoritmo Rete (3), estesa per

aggiungere alcune funzionalità non coperte.

4.2.1 Implementazione di Rete

Alla formulazione di algoritmo di Rete fornita da (3) e brevemente descritta nel paragrafo 3.3, ho aggiunto

alcune variazioni per l’aggiunta di alcune funzionalità o per rilassare alcuni vincoli presenti.

Nella versione proposta in origine si poneva come ipotesi alla formulazione del sistema che l’algoritmo di

matching dovesse solamente trattare fatti espressi come triple (nome, attributo, valore), quindi con

componenti esplicite e di lunghezza fissa. Partendo da questa ipotesi, il sistema proposto si basava sulla

sostituzione della Alpha Network tramite una lista di otto dizionari nei quali sarebbero andati a convergere

le diverse istanze di fatti per attivare i nodi successori.

La necessità di rilassare questo vincolo di lunghezza, mi ha portato a preferire una soluzione basata

sull’utilizzo dei Constant Test Node per eseguire i controlli su elementi costanti dei working memory

elements, affiancati da un nuovo tipo di nodi Length Test Node in grado di filtrare le asserzioni in base alla

lunghezza delle tuple immesse nel sistema.

Prima parte

10

Sebbene questa formulazione sia più flessibile, pone un problema di prestazioni: se prima l’utilizzo dei

dizionario ci offriva un tempo di scansione e attraversamento della Alpha Network costante,

l’implementazione data-flow risulta meno prestante in quanto ogni valutazione presente nell’Alpha

Network viene eseguita fino a bloccarsi alla prima non soddisfatta o giungere ad un nodo della Beta

Network, per essere ulteriormente propagato.

Un ulteriore variazione alla formulazione originale è stata introdotta per consentire l’utilizzo di espressioni

dinamiche e risultati funzioni come componenti della LHS delle regole.

L’utilizzo di funzioni non era contemplato nella formulazione proposta da (3), che limitava i confronti solo a

operazioni di comparazione per uguaglianza.

Ancora, per offrire supporto al costrutto test disponibile in CLIPS, mi sono visto costretto ad estendere

ulteriormente il set di nodi a disposizione per consentire confronti fra variabili eseguiti da predicati

particolari.

4.2.2 Nodi aggiunti

Al set di nodi presentati nel paragrafo 3.3.1, ho aggiunto:

Length Test Node: uno speciale tipo di Constant Test Node che permette di verificare la lunghezza

di un elemento della working memory, assicurandosi che sia coerente con quanto cercato e

propagando l’elemento solo se la lunghezza coincide con quella cercata

Filter Node: un tipo di nodo che esegue dei test su una serie di variabili o costanti utilizzando un

predicato particolare, consentendo la verifica della correttezza del binding fra le variabili.

Alpha Root Node: variante di Constant Test Node, propaga qualsiasi elemento senza eseguire

verifiche ai figli. Viene utilizzato solo come nodo principale del grafo Rete

Dummy Join Node e Dummy Negative Node: rappresentano due varianti dei rispettivi nodi, ma che

vengono utilizzati per eseguire la conversione di elementi propagati dalla Alpha Network, in

elementi manipolabili dai nodi della Beta Network. Sebbene questi siano nodi appartenenti alla

Beta Network a due input, consentono di realizzare le funzionalità dei rispettivi nodi pure

ottenendo input da uno solo dei due rami in ingresso, tramite la generazione di Dummy Token.

4.2.3 Propagazione dei fatti nella Rete

Come detto, ad ogni asserzione un nuovo elemento viene inserito nella working memory e viene quindi

valutato all’interno del grafo della Rete, in modo da individuare i nodi che verranno attivati dalla presenza

della nuova asserzione.

Una volta inserito nella Alpha Network, il fatto viene incapsulato all’interno di un oggetto WME e valutato

dai nodi Alpha. Qualora tutti i test eseguiti in un ramo risultassero positivi, l’elemento verrebbe

memorizzato all’interno della Alpha Memory posta a termine del ramo.

In Figura 7 è offerta una rappresentazione grafica dell’effetto provocato dall’inserimento di un fatto (A B C)

all’interno della rete prodotta da Figura 5.

Prima parte

11

Nella figura si può ulteriormente notare come la propagazione del nodo venga bloccata una volta giunto al

Join Node, il quale non può effettuare i test di coerenza sul binding delle variabili senza la presenza di un

elemento da confrontare proveniente dall’altro ramo input.

Figura 8 - Inserimento del fatto (A B) nella Rete

Figura 7 - Inserimento del fatto (A B C) nella Rete

Prima parte

12

Supponiamo quindi che un ulteriore fatto (A B) venga asserito, come in Figura 7. Analizzandone il percorso

all’interno della Alpha Network riscontreremo un comportamento analogo a quanto avvenuto nella

precedente asserzione.

La differenza, in questo, è che la propagazione dell’elemento non è bloccata all’interno della Alpha

Network, in quanto il Dummy Join Node converte l’elemento in un Token e lo propaga ulteriormente

all’interno della Beta Network. A questo punto, verrà memorizzato nella Beta Memory e propagato dal Join

Node che, una volta confrontato il Token proveniente dal ramo Beta e l’elemento memorizzato

precedentemente nell’Alpha Memory collegata, propagherà il Token al Production Node collegato,

attivandolo. Quanto descritto è riscontrabile in Figura 9.

Figura 9 - Transito del Token nella Beta Network

4.2.4 I Token

La valutazione dei nodi della Alpha Network consiste nel confrontare singole porzioni di un singolo

elemento della working memory per volta e decidere se la condizione sia stata soddisfatta o meno.

I nodi della Beta Network hanno invece il compito di valutare se una combinazione di elementi soddisfi una

serie di condizioni differenti contemporaneamente. È facile immaginare che sia necessario fornire un modo

di rappresentazione di queste combinazioni di elementi all’interno dei nodi.

Per risolvere questa problematica viene introdotto il concetto di Token. Un Token rappresenta appunto una

sequenza di fatti che soddisfino una determinata sequenza di condizioni fino a quel punto valutate. Nel

momento in cui una nuova valutazione viene eseguita confrontando un Token con un elemento WME, il

Token viene aggiornato inserendo nella sequenza l’elemento WME che avrà generato il riscontro e

ulteriormente propagato ai nodi successivi.

Prima parte

13

Questo consente al Production Node di accedere alla completa sequenza di elementi WME che abbiano

trovato riscontro nelle singole condizioni che la produzione richiede soddisfatte.

Qualora un elemento della sequenza venisse ritrattato, l’intera sequenza rappresentata dal Token verrebbe

invalidata e quindi il Token stesso rimosso dal sistema insieme a tutte le attivazioni che il Token produce.

4.3 Rappresentazione dei fatti La rappresentazione dei fatti ammessa dal sistema è solo quella che in CLIPS prende il nome di ordered-

fact. I fatti sono rappresentati come sequenze di simboli, numeri o stringhe fra doppi apici. L’indice nella

sequenza verrà utilizzato per eseguire il confronto fra gli elementi nei campi.

Sebbene il sistema sia pronto per accettare elementi con indici non numerici e quindi per l’utilizzo della

notazione unordered-fact, il parser non comprende nella sua grammatica la possibilità di esprimere gli

elementi usando sequenze “chiave-valore”.

4.4 Rappresentazione delle regole

4.4.1.1 LHS

Come detto, la porzione LHS di una regola rappresenta l’insieme di condizioni che devono essere necessarie

per consentire l’attivazione.

Oltre al semplice matching fra porzioni di elementi della working memory, il sistema permette l’utilizzo di

funzioni e predicati come sostituzione di valori in campi del pattern. Per essere più specifici: è ammesso

l’utilizzo di funzioni in sostituzione di specifici campi del pattern.

Le funzioni verranno valutate a runtime su singoli valori o su combinazioni di valori di variabili

precedentemente individuate nella stessa LHS.

Qualora nel corpo della funzione intervenissero solo valori costanti e non sia richiesta una rivalutazione a

runtime, il sistema provvederà alla compilazione della regola sostituendo alla chiamata della funzione,

l’effettivo risultato della funzione valutata sui valori costanti.

4.4.2 Funzioni

MyClips offre un set di funzioni su simboli, numeri e stringhe derivato da quello offerto da CLIPS. Dove

possibile, ho cercato di mantenere corrispondenza esatta fra elementi in input e output fra le

implementazioni offerte da MyClips e quelle offerte da CLIPS.

Per una trattazione dettagliata del comportamento delle singole funzioni si rimanda quindi al manuale

originale di CLIPS (5). In questa trattazione mi limiterò semplicemente ad elencare l’insieme di funzioni

presenti.

Tabella 1 - Lista delle funzioni di MyClips

Funzione Comando Input Output

Valore assoluto abs Un numero Un numero positivo

Addizione + Due numeri La somma dei numeri

Divisione / Due numeri Il rapporto fra i numeri

Conversione Float float Un numero intero Conversione in Float

Divisione fra interi div Due numeri Il rapporto intero fra i numeri

Prima parte

14

Funzione Comando Input Output Max max Due o più numeri Il valore massimo

Min min Due o più numeri Il valore minimo

Modulo mod Due numeri Modulo fra i due numeri

Moltiplicazione * Due numeri Prodotto fra i numeri

Concatenazione str-cat Due o più stringhe Stringa concatenata

Ricerca in stringa str-index Due stringhe La posizione della seconda stringa all’interno della prima

Lunghezza della stringa str-length Una stringa La lunghezza della stringa

Porzione di stringa sub-string Una stringa e due interi La sottostringa della stringa

Sottrazione - Due numeri La differenza fra numeri

4.4.3 Predicati

Analogamente alle funzioni, MyClips offre un set di predicati di confronto simile a quello offerto da CLIPS.

Le stesse considerazioni fatte per quanto riguarda le funzioni possono essere estese anche al set dei

predicati.

Tabella 2 - Lista dei predicati di MyClips

Predicato Comando Predicato Comando

Uguaglianza fra stringhe eq Disuguaglianza fra stringhe neq

Uguaglianza fra numeri = Disuguaglianza fra numeri <>

Numero pari evenp Numero dispari oddp

Numero intero integerp Numero float floatp

Numero intero o float numberp Stringa stringp

Simbolo symbolp Stringa o simbolo lexemep

Minore < Maggiore >

Minore o uguale <= Maggiore o uguale >=

4.4.4 Azioni

L’elenco delle azioni disponibili in MyClips è decisamente più cospicuo. Il set comprende solamente le

azioni utili al completamento degli esempi forniti con il sistema e all’asserzione e alla ritrattazione degli

elementi della working memory. Anche se questo può sembrare un limite piuttosto grande, vedremo nel

capitolo successivo come è possibile estendere facilmente il set di azioni disponibili per integrarne di nuove.

Tabella 3 - Lista delle azioni di MyClips

Azioni

Bind Printout Assert Retract Read Refresh Set-Strategy

4.5 L’agenda L’agenda integrata in MyClips tiene traccia sia delle attivazioni disponibili, indicizzate per livello di Salience,

sia delle attivazioni ancora valide ma già eseguite. Questo consente di evitare l’attivazione consecutiva di

una stessa regola sulle stesse istanze della working memory.

Inoltre, l’agenda integrata permette di modificare sia a priori, sia a runtime eseguendo un riordinamento,

l’ordine di priorità delle attivazioni secondo le stesse strategie disponibili in CLIPS.

Seconda parte

15

Seconda parte

Dettagli di implementazione e valutazione del sistema

5 Dettagli sull’implementazione

5.1.1 La rappresentazione dei Nodi

Il grafo generato dalla compilazione delle regole è composto da differenti tipi di nodi descritti in

precedenza. Nell’implementazione offerta da MyClips, la rappresentazione dei nodi è affidata ad istanze di

classe proprie per ogni tipo di nodo. I nodi vengono distinti fra nodi appartenenti alla Alpha Network,

derivati dalla classe Alpha Node, e nodi della Beta Network, derivati dalla classe Rete Node.

La navigazione all’interno del grafi avviene sempre dall’alto (considerando il nodo Root come la radice del

grafo) verso il basso (i nodi Production Node). Quando un nuovo elemento viene asserito esso viene

valutato e propagato da nodi padre ai nodi figlio o successore. Considerato questo comportamento, ogni

nodo conserva l’elenco dei figli o successori collegati al nodo. Inoltre, il tipo di accesso che viene utilizzato

con maggior frequenza nella lettura dell’elenco è di tipo sequenziale.

Una considerazione a parte va fatta per quanto riguarda la gestione del collegamento fra nodi. Durante

l’aggiunta dei nodi, i figli vengono aggiunti alla testa della lista. In base a queste considerazioni, ho pensato

fosse ragionevole modificare il sistema per l’utilizzo di strutture dati che fornissero migliori prestazioni per

l’aggiunta in testa degli elementi.

A questo scopo ho optato per la sostituzione dell’implementazione della lista di figli e successori con

l’utilizzo di istanze della classe deque del package collections di Python. Questa struttura dati ad alte

prestazioni consente l’aggiunta degli elementi in testa e in coda senza degrado prestazionale pagato

dall’utilizzo dell’implementazione standard di lista.

Maggiori dettagli sono disponibili nella documentazione della classe (6).

5.1.2 La rappresentazione delle WME

Gli elementi WME rappresentano una astrazione dei fatti, cosi come espressi all’interno della working

memory. La classe WME incapsula le informazioni contenute in un fatto.

Una volta asserito un nuovo fatto, le informazioni vengono inserite (se non duplicate) in un nuovo oggetto

WME che viene propagato all’interno della rete. Attraversata la Alpha Network, l’oggetto verrà conservato

in una sequenza di oggetti WME rappresentanti il Token che a sua volta verrà conservato, insieme alle

informazioni riguardanti la regola, come attivazione all’interno dell’agenda.

Non appena un fatto viene ritrattato, esso deve essere rimosso da tutti i Token in cui esso è contenuto, cosi

come da tutte le Alpha Memory che ne mantengono un riferimento.

Un implementazione naÏve dell’operazione richiederebbe la rivalutazione della presenza dell’istanza della

WME all’interno della Rete ripercorrendola tutta ed eliminandone i riferimenti qualora trovati.

Seconda parte

16

Tenendo a mente queste considerazioni, l’implementazione fornita da MyClips provvede a memorizzare

all’interno dell’istanza della classe ReteNetwork un dizionario che correli il fatto rappresentato con la

relativa istanza di WME.

Per velocizzare le operazioni di ritrattazione di fatti e rimozione dell’istanza WME dalla rete e eliminare

l’overhead generato dal dover rivalutare interamente il circuito compiuto dalla WME all’atto

dell’asserzione, all’interno della classe vengono memorizzati i riferimenti di tutti gli elementi in cui la WME

conserva un ruoto: ogni riferimento ad Alpha Memory e Token in cui la WME è conservata viene

memorizzato all’interno di una lista. Questo significa che la ritrattazione di un fatto si tramuta

semplicemente in una operazione di scansione di queste liste di riferimenti per invocare la rimozione del

fatto dal nodo in cui il match è memorizzato ed invalidare eventuali oggetti dipendenti dalla WME rimossa.

5.1.3 Rappresentazione dei Token

Come detto, i Token sono l’unità di memorizzazione di sequenze di WME che abbiano ottenuto un riscontro

con una serie di condizioni.

I Token vengono manipolati nella parte Beta della Rete e ogni nodo può provvedere a crearne di nuovi sulla

base della operazione di unione fra un Token derivato da una porzione precedente della Beta Network e

una istanza di WME che provenga da una porzione della Alpha Network. Questo lascia intendere una sorta

di relazione gerarchica interna ai Token: ogni Token viene generato dall’unione fra un Token padre e un

elemento WME.

Questa considerazione pone le basi per una implementazione dei Token che sia differente dalla semplice

lista di elementi WME. L’insieme dei Token può essere immaginato come una foresta di alberi n-ari che

abbiano Dummy Token1 come radice e nei quali ogni ramo rappresenta l’unione del Token padre con un

elemento WME. Utilizzando questa configurazione è possibile ridurre il quantitativo di memoria utilizzato in

quanto tutti i Token derivati dalla stessa porzione del grafo per determinate istanze WME condivideranno

le informazioni riguardanti gli elementi WME dei livelli precedenti.

All’atto della rimozione di un elemento dalla working memory e alla conseguente ritrattazione dei Token in

cui l’elemento è contenuto, verrà eseguita una operazione di scansione ed eliminazione di tutti i Token

figlio derivati da quello invalidato. Questa operazione è possibile proprio grazie al fatto che ogni Token

conserva i riferimenti a tutti i Token derivati all’interno di una lista.

All’atto dell’attivazione di una regola, sarà necessario determinare la giusta sequenza di elementi WME che

soddisfano le condizioni di attivazione. In ogni Token quindi è presente un riferimento all’elemento padre

da cui esso è stato generato. L’operazione di linearizzazione degli elementi WME corrisponderà

all’esplorazione di una sequenza di rami dell’albero dei Token partendo da una foglia.

6 Confronto fra MyClips e CLIPS Uno dei vincoli che mi sono posto durante la realizzazione del mio sistema, era quello di rendere

compatibile un qualsiasi sistema esperto che fosse funzionante con CLIPS. Chiaramente mi era impossibile

nell’ambito di questo progetto replicare tutti le funzionalità offerte da CLIPS. Mi sono quindi concentrato

1 I Dummy Token sono un tipo particolare di Token che non conserva informazioni riguardanti alcune elemento padre

e che viene generato semplicemente incapsulando un elemento WME proveniente dall’Alpha Network.

Seconda parte

17

sulla implementazione di una serie limitata di caratteristiche, facendo in modo che il loro comportamento

risultasse coerente fra i due sistemi o quanto meno replicabile in entrambi con opportuni accorgimenti.

6.1 Caratteristiche replicate

6.1.1 Tipi fondamentali

CLIPS individua cinque tipi fondamentali di dati, la cui composizione consentirà la derivazione di tutti gli

altri tipi. Quelli proposti da CLIPS sono:

Symbol: sequenze di caratteri appartenenti all’elenco dei caratteri stampabili dello standard ASCII,

tranne che per i caratteri “, ‘, |, &, :, |, <, ~, $, ? e ;.

Number: qualsiasi sequenza di caratteri numerici, preceduti eventualmente da caratteri indicanti il

segno. Risultano validi anche numeri in notazione decimale e esponenziale.

String: una sequenza di caratteri delimitata alle due estremità dalla presenza del carattere “.

Nessuna restrizione viene applicata al tipo di carattere che è possibile inserire all’interno di una

stringa.

Instance: tipo di dato che rappresenta una istanza di classe

Pointer: puntatore ad una risorsa ottenuta come risultato della chiamata di una funzione esterna

integrata in CLIPS

Fact: rappresenta una istanza della working memory

Di questi elementi di base individuati, solo alcuni hanno una corrispondenza all’interno di MyClips: Symbol,

Number e String hanno una corrispondenza diretta con i tipi nativi presenti in Python e quindi in MyClips. Il

tipo Fact è stato implementato all’interno di MyClips come istanza della classe WME. Per i tipi Instance e

Pointer non è stato necessario trovare una corrispondenza all’interno di MyClips in quanto essi

rappresentano dati ottenibili in CLIPS solo tramite l’utilizzo di caratteristiche non replicate, come gli oggetti

e i riferimenti a funzioni espresse in linguaggio nativo di sistema.

6.1.2 Costrutti disponibili

MyClips supporta solamente l’utilizzo dei costrutti deffacts, defrule e set-strategy all’interno dei file CLP.

Inoltre la sintassi e le funzionalità dei costrutti non sono state completamente replicate in quanto non

necessarie.

Il costrutto deffacts viene utilizzato per asserire una lista di fatti all’atto dell’inizializzazione del sistema.

Sebbene la sintassi disponibile per il costrutto in sé disponibile all’interno di MyClips sia analoga a quella di

CLIPS, la composizione degli elementi asseribili all’interno del costrutto è fortemente limitata alla mancanza

di molte caratteristiche.

MyClips supporta soltanto la dichiarazione dei fatti nella forma di ordered-fact, cosi come espressa da

CLIPS. Sebbene il supporto agli unordered-fact sia parzialmente disponibile all’interno del motore

inferenziale, il parser e la grammatica non contemplano l’utilizzo di questa caratteristica. Lo stesso motore

inferenziale non è stato testato adeguatamente per verificare la correttezza di funzionamento nell’ambito

della manipolazione dei fatti di tipo unordered.

Il costrutto defrule risulta completamente replicato all’interno della sintassi disponibile in MyClips. Le

uniche eccezioni riguardano il tipo di formalismo che è possibile utilizzare per la rappresentazione dei fatti

(anche in questo caso come per il costrutto deffacts, limitato al solo uso della forma ordered-fact) e per la

rappresentazione di condizioni atomiche esprimibili sul binding delle variabili.

Seconda parte

18

La sintassi di CLIPS prevede la possibilità di valutare il binding delle variabili applicando delle restrizioni ai

valori ammissibili tramite l’utilizzo di valutazione in-place (un esempio in Figura 10).

Questa funzionalità non è stata implementata all’interno di MyClips in quanto è possibile replicarla tramite

l’aggiunta di una condizione di tipo test sulla variabile in seguito. Questo formalismo è supportato anche da

CLIPS, di conseguenza non riduce il grado di compatibilità del sistema e mantiene le potenzialità di

espressione delle regole invariata. La Figura 11 rappresenta un esempio di riscrittura equivalente della

regola precedente (Figura 10) che risulta ancora compatibile sia con MyClips che con CLIPS.

6.2 Vincoli rilassati e differenze Se da una parte il sistema MyClips espone una serie limitata di funzionalità rispetto al sistema concorrente,

dall’altra alcuni vincoli presenti nella implementazione del pattern matcher di CLIPS e della sua grammatica

sono stati rimossi.

6.2.1 Formato del primo campo

Fra i vincoli che è stato possibile rilassare ce n’è uno riguardante il primo elemento di ogni pattern di

condizione di una regola. All’interno della grammatica accettata da CLIPS non è consentito l’uso di variabili

per indicare il primo campo di una condizione, che invece deve essere sempre espressa tramite l’uso di una

costante. Nel caso in cui si tenti di utilizzare un qualsiasi elemento non costante, verrà resistito un errore

come in Errore. L'origine riferimento non è stata trovata..

Figura 12 - Errore ottenuto con l'uso di una variabile come primo campo

CLIPS>(defrule Genera_Errore (?a B C) =>)

[PRNTUTIL2] Syntax Error: Check appropriate syntax for the first field of a pattern.

ERROR: (defrule MAIN::Genera_Errore (?a

CLIPS>

(defrule Regola_con_condizione_In-Place_su_variabile-CONVERTITA

(A ?a C)

(test (> ?a 2))

=>)

(defrule Regola_con_condizione_In-Place_su_variabile

(A ?a:(> ?a 2) C)

=>)

Figura 10 - Esempio di regola con valutazione in-place di una variabile

Figura 11 - Formulazione equivalente della regola in Figura 10

Seconda parte

19

La stessa regola, nella stessa formulazione viene invece accettata dal sistema MyClips, che non espone le

stesse limitazioni riguardanti il formato del primo campo.

6.2.2 Gestione del matching negativo

La più grande differenza fra i due sistemi riguarda la gestione delle negazioni e del matching delle

negazioni.

L’interpretazione delle condizioni negate in CLIPS avviene semplicemente considerando la mancanza di un

elemento che esegua il matching, senza identificarlo con uno degli elementi presenti nella working

memory. Se non viene trovato nessun elemento corrispondente, l’attivazione della regola sarà resa

possibile utilizzando il fatto speciale initial-fact per la propagazione.

MyClips invece gestisce le condizioni di negazione in maniera differente: non solo si assicura che non ci sia

alcun elemento nella working memory in grado di creare un riscontro, ma identifica qualsiasi elemento che

non esegua riscontro come elemento risultante dal match.

Le implicazioni di queste differenze riguardano la gestione delle attivazioni: per CLIPS, una regola con una

negazione verrà resa attivabile se il match della condizione negata non sarà possibile e la regola verrà

inserita nell’agenda rappresentata da una sola attivazione, con elemento initial-fact come riscontro.

In MyClips invece, la regola verrà aggiunta fra l’elenco delle attivazioni una volta per ogni elemento della

working memory che non effettua il match.

Sarà quindi opportuno valutare durante la conversione del sistemi esperti l’impatto che questa differenza

comporta. La Figura 14 e Figura 15 rappresentano praticamente l’effetto della regola in Figura 13 nei due

sistemi.

Figura 14 - Gestione della regola in Figura 13 in CLIPS

CLIPS> (agenda) 0 negazione: f-0, For a total of 1 activation.

CLIPS> (facts) f-0 (initial fact) f-1 (A B C) f-2 (A B D) For a total of 3 facts.

Figura 13 - Regola di esempio per differenze della negazione

(deffacts iniziali (A B C) (A B D) )

(defrule negazione

(not (A C C))

=>)

Seconda parte

20

------------------- Agenda: 0 negazione: f-1 0 negazione: f-2 -------------------

Esecuzione:

-------------------- Post esecuzione: f-1 (A B C) f-2 (A B D) --------------------------------

Figura 15 - Gestione della regola in in MyClips

Terza parte

21

Terza parte

Guida all’uso e all’estensione del sistema

7 Interazione con il sistema L’interazione prevista con il sistema è attraverso l’utilizzo di una console, associandola all’uso di un editor di

testo che consentirà l’effettiva scrittura del sistema esperto.

7.1 Installazione e configurazione

7.1.1 Requisiti

Per ottenere una copia funzionante del sistema MyClips è necessario essere provvisti di alcuni software di

necessari al corretto funzionamento dell’applicativo:

Eclipse IDE, versione 3.7

PyDev plugin per Eclipse, versione 2.4

Python, versione 2.7

Libreria PyParsing, versione 1.5

Libreria MatplotLib, versione 1.1.0 (e dipendenze)

Inoltre, si consiglia l’installazione di Git per scaricare l’ultima versione del sistema direttamente dal

repository.

7.1.2 Ottenere il codice sorgente

Il codice sorgente del sistema può essere scaricato dal repository ufficiale disponibile all’indirizzo

https://github.com/ximarx/icse-ie. Il sistema può essere ottenuto sia scaricando l’archivio compresso, che

tramite l’utilizzo del software di controllo di versione Git. In entrambi i casi, la copia ottenuta sarà provvista

dei file necessari all’importazione del progetto all’interno dell’IDE Eclipse.

Una volta ottenuto il sistema, sarà possibile avviarlo eseguendo il modulo icse.ie.Main disponibile

all’interno della directory src/ del progetto.

7.1.3 Elementi forniti con il sistema

Insieme al codice necessario all’esecuzione del sistema, viene fornito un set di esempi di utilizzo di MyClips

in formato CLP, insieme ad una serie di sistemi esperti di test utili al controllo del sistema. Tutti i file

utilizzabili sono collocati all’interno della directory tests/ del progetto.

Una volta avviato, il sistema offrirà la possibilità di scegliere fra uno qualsiasi dei file presenti all’interno

della directory tests/, eseguendolo in seguito alla scelta dell’utente.

7.2 Creazione di un nuovo sistema esperto Il sistema prevede che i file relativi ad un sistema esperto, in formato CLP, siano collocati all’interno della

directory tests/, la stessa in cui risiedono gli esempi offerti a corredo di MyClips.

Le linee guida per la creazione del sistema esperto risultano le stesse utilizzate per la realizzazione in CLIPS.

Le uniche differenze riguardano (oltre che le differenti funzionalità offerte dal sistema) la gestione dei

moduli.

Terza parte

22

7.2.1 Modularizzazione

CLIPS offre la possibilità di creare un sistema esperto scomponendolo in una serie di moduli indipendenti.

Oltre a questo, viene anche fornita una serie di caratteristiche che permettono di isolare componenti

specifiche di un modulo dalle influenze degli altri, di rendere disponibili solo determinate caratteristiche.

Viene anche offerta la possibilità di decidere quali componenti di un modulo importare ed utilizzare.

MyClips offre invece un supporto differente ai moduli, decisamente più semplificato. È sempre possibile

distribuire il sistema esperto su più file differenti in modo da raggruppare fra loro funzionalità separate, ma

non viene offerta nessuna delle altre funzionalità offerte da CLIPS.

Il caricamento di un modulo all’interno di un sistema esperto avviene in due fasi: nella prima una direttiva

informa il parser, all’atto della lettura del file principale, della necessità di acquisire nuove regole e fatti

inseriti in un file differente da quello letto. In una seconda fare, successiva al termine della lettura del

modulo principale, il sistema provvederà a risolvere e caricare in serie tutti i percorsi specificati nelle

differenti direttive d’inclusione. Questo processo è ricorsivo. Il sistema provvederà ad assicurarsi, tramite

controlli sui percorsi dei file, che lo stesso file non sia incluso più di una volta. Questo risolve i problemi di

inclusione ricorsiva.

Il formato scelto per la specifica delle direttive risulta chiaramente differente da quello utilizzato da CLIPS.

Ho scelto di utilizzare una sintassi differente in modo da distinguere nettamente le due funzionalità ed

evitare che la sintassi simile potesse trarre in inganno un utilizzatore, portandolo a credere che il

comportamento di MyClips emulasse quello di CLIPS nella gestione dei moduli.

L’utilizzo del ; come primo carattere della direttiva consente inoltre di non generare errori durante l’utilizzo

del sistema esperto in CLIPS. Chiaramente sarà necessario sopperire alla mancata inclusione dei moduli

provvedendo manualmente o attuando una qualche strategia alternativa.

7.2.2 Caratteristiche di supporto allo sviluppo

MyClips offre, oltre alle direttive di inclusione, una serie di altre caratteristiche orientate al supporto allo

sviluppo del sistema esperto. L’utilizzo di queste caratteristiche può essere attivato o disattivato utilizzando

ulteriori direttive proprie di MyClips o tramite apposite azioni.

7.2.2.1 Direttiva: watch_rule_fire

Permette di abilitare la visualizzazione di messaggi di debug all’atto dell’esecuzione di regole, mostrandone

sia il nome che l’elenco di elementi della working memory che realizzano l’attivazione. Per un riscontro

delle differente comportamento del sistema all’atto dell’attivazione della direttiva vi rimando alla Figura 17.

;@include(percorso/e/nome/del/file.clp)

Figura 16 - Esempio di direttiva di inclusione

Terza parte

23

Figura 17 - Confronto fra esecuzione normale e con watch_rule_file

7.2.2.2 Direttiva: watch_fact_assert

Visualizza un messaggio ad ogni asserzione eseguita durante l’attivazione di una regola. Un messaggio

indicherà sia l’id del fatto asserito, sia la sua conformazione.

Figura 18 - Esecuzione con watch_fact_assert attivo

7.2.2.3 Direttiva: watch_fact_retract

Visualizza un messaggio ogni volta che un elemento della working memory viene ritrattato. Il formato di

visualizzazione del messaggio è analogo a quello utilizzato dalla direttiva watch_fact_assert, con la

differenza che viene utilizzato il simbolo – come alternativa al simbolo di somma per indicare la rimozione

del fatto.

7.2.2.4 Direttiva: watch_rule_activation e watch_rule_deactivation

Comunica l’inserimento o la rimozione di una regola, insieme alle relative istanze della working memory,

dalla lista di regole attivabili. Il simbolo + o – discriminano l’inserimento o la rimozione dalla lista delle

attivazioni

Figura 19 - Esecuzione con watch_rule_activation e watch_rule_deactivation attive

7.2.2.5 Direttiva: draw_graph

L’utilizzo di questa direttiva permette la visualizzazione di un grafico rappresentante l’esatta composizione

della Rete al termine della compilazione di tutte le regole. È consigliabile posizionare questa direttiva

sempre prima dell’inserimento di qualsiasi regola nella Rete, in modo da evitare l’overhead di una nuova

scansione della Rete creata fino a quel punto all’atto del riconoscimento della direttiva. L’utilizzo della

direttiva in coda alle regole è possibile anche se sconsigliato.

Terza parte

24

Il grafico viene visualizzato utilizzando la libreria matplotlib, dipendente dalle librerie pyplot, numpy e

graphviz. Qualora una di questi requisiti risultasse mancante e la generazione del grafico non fosse

possibile, la conformazione della rete verrà visualizzata utilizzando un formato testuale e inserito

nell’output di console.

Esempi dei grafici generati da questa direttiva sono quelli in Figura 4 e Figura 6. Questo strumento, seppur

molto utile, genera un consistente overhead durante la compilazione della Rete e un consumo di memoria

non indifferente. Di conseguenza se ne consiglia l’utilizzo solo per valutare porzioni limitate di una Rete

relativa a sistemi esperti molto complessi.

7.2.2.6 Azione: trace-rule

L’azione trace-rule permette di visualizzare un grafico di una porzione della Rete associata all’insieme di

nomi di regole fornite come parametri dell’azione. Il funzionamento è analogo a quello della direttiva

draw_graph illustrata nel paragrafo precedente, ma a differenza della direttiva questa azione consente di

visualizzare solo una porzione del grafico ed inoltre consente di farlo a Runtime (visto che l’azione viene

posta come parte destra di una regola e per essere eseguita l’azione deve essere attivata). In questo modo

tutte le informazioni racchiuse nel grafico (come il numero di elementi matchati presenti nelle memorie)

saranno aggiornate al momento dell’esecuzione dell’azione.

L’azione consente di specificare una lista di nomi di regole da visualizzare, in questo modo il grafico potrà

essere molto utile per rilevare quali nodi vengano condivisi e quali no.

7.2.2.7 Azione: trace-wme

L’azione permette di visualizzare un insieme di informazioni di debug relative all’oggetto WME che

rappresenta un fatto matchato nella porzione LHS della regola. La Figura 21 rappresenta un esempio delle

informazioni mostrate dall’elemento matchato dalla regola test-trace-wme nell’esempio raffigurato in

Figura 20.

(defrule test-trace-wme

?f <- (A B ?)

=>

(trace-wme ?f)

)

(deffacts statoIniziale "Stato iniziale"

(A B C)

)

Figura 20 - Esempio per l'uso di trace-wme

Terza parte

25

Figura 21 - Ouput di trace-wme nell'esempio in Figura 20

7.2.2.8 Azione: trigger-event

L’azione trigger-event consente di lanciare un messaggio a tutti i listener collegati ad un evento

dell’EventManager per consentire l’esecuzione di side-effects. L’azione accetta come primo parametro il

nome dell’evento, seguito da un elenco di parametri arbitrario sia in lunghezza che in composizione.

7.3 Estendibilità del sistema Una componente importante di MyClips è la possibilità di estendere il set di azioni, funzioni e predicati

aggiungendone di nuovi.

7.3.1 Aggiungere nuove Azioni

Il package icse.actions conserva tutte le azioni disponibili nel sistema. Ogni nuova azione può essere inserita

nel sistema estendendo la classe Action presente nel file src/icse/actions/__init__.py.

Per fare i modo che una nuova azione sia riconosciuta come tale e caricata automaticamente nel sistema, è

necessario posizionarla nella stessa sub-directory dove risiedono le altre azioni e fare in modo che nella

definizione di classe venga specificata una proprietà statica di classe di nome SIGN, che conterrà il comando

che il parser riconoscerà e associerà a questa funzione, e che venga eseguito un overriding della funzione

Action::executeImpl. Maggiori informazioni sono disponibili nei commenti in linea della classe Action.

Al caricamento del package icse.actions, il sistema automaticamente riconoscerà e caricherà l’elenco delle

azioni disponibili leggendo tutti i file con le caratteristiche descritte sopra.

7.3.2 Aggiungere nuove Funzioni e Predicati

Il package icse.functions conserva tutte le funzioni disponibili nel sistema, mentre il package icse.predicates

conserva l’insieme dei predicati. Le modalità di estensione dell’elenco delle funzioni disponibili è analogo a

quanto descritto per l’estensione delle azioni. Si rimanda quindi al paragrafo precedente e alla

documentazione in linea per maggiori informazioni

Anche in questo caso, il caricamento delle funzioni e dei predicati aggiunti è automatico e trasparente se

tutte le linee guida di preparazione delle classi saranno state rispettate

Terza parte

26

7.3.3 Aggiungere nuove Azioni, Predicati e Funzioni manualmente

Una modalità alternativa al caricamento automatico delle funzioni, predicati e azioni è disponibile. I

rispettivi package contengono una classe di nome Proxy che conserva e permette di alterare l’elenco delle

componenti disponibili nel sistema. Agendo sulla classe è possibile aggiungere anche componenti che non

posizionate all’interno della directory di caricamento automatico. Tutte le altre convenzioni, relative

all’estensione della classe base e alla overriding delle funzioni della classe di base devono comunque essere

rispettate affinchè la componente risulti utilizzabile.

Il riconoscimento delle componenti aggiunte dall’utente dal parser è del tutto trasparente: nessun

intervento aggiuntivo alla grammatica o al parser è richiesto per abilitarne l’utilizzo.

Appendici

27

Appendici

8 Formalizzazione della grammatica riconosciuta La grammatica che segue, formalizzata in formato EBNF, rappresenta l’esatto tipo di grammatica

riconosciuta dal sistema MyClips.

(************************* DEFINIZIONI DI BASE **************************) number = (integer | float); (***************** Altre definizioni base in icse.parser.__init__.py - symbol - float - integer - string - variable_symbol - variable_undef - quoted_text - action_name: [una lista di azioni supportate caricate dinamicamente] - function_name: [una lista di funzioni supportate caricate dinamicamente] - predicate_name: [una lista di predicati supportati caricati dinamicamente] ******************) (************************* DEFRULE **************************) defrule_construct = '(defrule', rule_name, [comment], [declaration], conditional_element_group, '=>', action_group, ')'; rule_name = symbol; comment = quoted_text; declaration = '(declare', (rule_property, {rule_property}), ')'; rule_property = '(', string, (number | symbol ), ')'; conditional_element_group = ({conditional_element}); conditional_element = test_CE | assigned_pattern_CE | not_CE | and_CE | pattern_CE; action_group = ({action_call}); action_call = '(', action_name, ({action_call | action_term | action_quoted_text | rhs_pattern }), ')'; action_term = action_constant | variable_symbol | term_function_call; action_constant = number | symbol; action_quoted_text = quoted_text; pattern_CE = '(', ({constraint}), ')'; constraint = not_term | term ; not_term = '~', term; term = constant | variable_undef | variable_symbol | term_function_call; constant = number | symbol; term_function_call = {(':' | '=')}, function_call; function_call = '(', function_name, (constraint, {constraint}), ')'; predicate_call = '(', predicate_name, (constraint, {constraint}), ')'; assigned_pattern_CE = variable_symbol, '<-', pattern_CE; not_CE = '(not', conditional_element, ')'; and_CE = '(and', (conditional_element, conditional_element, {conditional_element}), ')'; test_CE = '(test', predicate_call, ')';

Appendici

28

(************************* DEFFACTS **************************) deffacts_construct = '(deffacts', deffacts_name, [comment], rhs_pattern_group, ')'; rhs_pattern_group = ({rhs_pattern}); rhs_pattern = '(', (rhs_field, {rhs_field}), ')'; deffacts_name = symbol; rhs_field = number | symbol | variable_symbol | quoted_text; (*************************** SET-STRATEGY ****************************) setstrategy_construct = '(set-strategy', strategy_name, ')'; strategy_name = 'depth' | 'lex' | 'mea' | 'breadth' | 'semplicity' | 'complexity' | 'random'; CLIPS_program = ({defrule_construct | deffacts_construct | setstrategy_construct | MYCLIPS_directive });

9 Esempi Il sistema viene fornito con alcuni esempi in allegato a dimostrazione delle funzionalità di MyClips. L’elenco

degli esempi comprende:

tests/agricoltore.clp: un sistema esperto in grado di risolvere il problema dell’agricoltore. Lo stato

inziale viene fornito al sistema tramite input da tastiera da parte dell’utente;

tests/blocchi.clp: problema del mondo dei blocchi che prevede il riordino di una sequenza di blocchi

posizionandone alcuni sopra altri;

tests/diagnosi.clp: sistema esperto per la diagnosi delle malattie del fegato. L’inferenza sulla

diagnosi viene fatta attraverso l’indicazione della presenza di alcuni sintomi da parte dell’utente;

tests/secchi.clp: soluzione al problema dei secchi.

Per ognuno di questi esempi è disponibile una variante nella quale risultino attive tutte le direttive di

debug.

All’interno della directory tests/ è disponibile una sotto-directory moduli/ che comprende due moduli

d’esempio per alcuni usi comuni:

tests/moduli/domande.clp: modulo di aiuto per l’interazione con l’utente. Contiene un set di regole

che consente al sistema di porre domande all’utente e validare le risposte. Questo modulo viene

utilizzato dall’esempio diagnosi.clp. L’esempio agricoltore.clp utilizza invece una strategia

alternativa più rapida che non comprende la validazione dell’input.

tests/moduli/halt-on-end.clp: aggiunge una regola con priorità minima che consente al sistema di

attendere l’intervento dell’utente al termine dell’esecuzione di un sistema esperto, prima di

terminare l’esecuzione del programma.

Appendici

29

In aggiunta a questi esempi più complessi sono anche disponibili una serie di file che realizzano dei test su

singole caratteristiche del sistema e che possono essere utilizzati come riferimento rapido sull’uso della

grammatica. Tutti i test sono dotati delle direttive di debug abilitate.

Figura 22 - Grafico andamento sviluppo sistema nel tempo

Bibliografia

30

Bibliografia

10 Bibliografia 1. CLIPS. Wikipedia. [Online] [Riportato: 21 Maggio 2012.] http://en.wikipedia.org/wiki/CLIPS.

2. Forgy, C. L. Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem. Artificial

Intelligence. 1982, 19, p. 17-37.

3. Doorenbas, R. B. Production Matching for Large Learning System. Pittsburgh, PA : Carnegie Mellon

University, 1995. CMU-CS-95-113.

4. PyParsing Wiki Home. PyParsing Module. [Online] http://pyparsing.wikispaces.com/.

5. Section 12 Actions And Functions. CLIPS Reference Volume 1. [Online]

http://www.comp.rgu.ac.uk/staff/smc/teaching/clips/vol1/vol1-Section-12.html.

6. collections - High performace container data-type. Python documentation. [Online]

http://docs.python.org/library/collections.html#collections.deque.