CAPITOLO 0

CAPITOLO 0

INTRODUZIONE

Negli ultimi anni si è avuto l’avvento del paradigma degli agenti come modello di riferimento in molti campi della ricerca, non solo in quello dell’intelligenza artificiale e dei sistemi distribuiti.

Il nostro scopo è quello di fornire (le basi di) un linguaggio di coordinamento tra agenti che utilizzano come fo rma di ragionamento l’abduzione, partendo da un altro linguaggio: LAILA (Language for AbductIve Logic Agents).

L’idea da cui nasce questa tesi è quella di utilizzare l’abduzione per modellare la conoscenza incompleta e quindi di studiare le interazioni tra gli agenti per risolvere i problemi derivanti dall’incompletezza delle loro basi di conoscenza.

La scelta di utilizzare l’abduzione come forma di ragionamento è stata fatta perché anch’essa, negli ultimi anni, ha trovato ampi sbocchi nella programmazione logica.

Il nostro linguaggio sarà dunque un’estensione di LAILA in quanto presenterà due differenze, una relativa alla consistenza e l’altra relativa al passaggio di abducibili nella comunicazione tra agenti.

Sempre a proposito dell’abduzione, ricordiamo che i primi ad applicare questo tipo di ragionamento nell’ambito della programmazione logica sono stati Eshghi e Kowalski, con la procedura NAF per il trattamento della negazione come fallimento [7].

Dopo di loro vale la pena ricordare Kakas e Mancarella, la cui procedura (estensione della precedente) è quella che è più usata (come vedremo è utilizzata anche in LAILA e quindi anche da noi).

La struttura della tesi sarà la seguente:

- nel primo capitolo, oltre alle motivazioni che ci hanno condotto a sviluppare questo lavoro, forniremo alcuni elementi fondamentali di teoria (sugli agenti, sulla programmazione logica e sull’abduzione);

- nel secondo capitolo presenteremo la sintassi e la semantica del nostro linguaggio ed alcuni semplici esempi per capire gli operatori;

- nel terzo capitolo forniremo degli esempi più esplicativi all’interno di due campi in cui il nostro lavoro può trovare applicazioni;

CAPITOLO 1

INTRODUZIONE E MOTIVAZIONI

In un sistema multiagente possiamo pensare di dotare ogni agente abduttivo di un programma logico-abduttivo distinto dagli altri; in questo modo ogni singolo agente può ragionare sulla propria base di conoscenza e trovare “spiegazioni” (insiemi di predicati) abduttive al goal. Possiamo però immaginare che gli agenti formino dei gruppi (dinamici o meno) per collaborare alla ricerca di una soluzione per un goal, e quindi unire le loro conoscenze per produrre una “risposta collettiva” al loro problema.

Il Language for AbduttIve Logic Agents (LAILA) ([3, 4]) modella azioni e interazioni tra agenti intelligenti che usano il ragionamento abduttivo come principale forma di ragiona mento. In particolare questo linguaggio si focalizza sul “comportamento sociale” degli agenti, specialmente su come ogni agente può chiedere ad altri agenti del sistema una dimostrazione per il proprio goal.

Come abbiamo accennato nelle pagine precedenti, utilizzeremo il ragionamento abduttivo per modellare la conoscenza incompleta (vedremo di che si tratta con un esempio classico [1]), e permetterà agli agenti di accrescere il loro sapere attraverso le interazioni. Esso può essere usato, per esempio e come faremo vedere nel capitolo 3, per generare spiegazioni per le diagnosi. In questo caso le ipotesi candidate sono le possibili cause (malattie) e le osservazioni sono i sintomi.

Questo processo di interazione passa anche attraverso lo sfruttamento delle diversità delle basi di conoscenza.

Vediamo l’esempio cui abbiamo accennato poco sopra.

Esempio

animale ← uccello, struzzo animale ← uccello, struzzo KBA1 : animale ← uccello, falco KBA2 :

uccello, ¬ vola →⊥ uccello, ¬vola, ¬struzzo →⊥

con A = {struzzo, falco, uccello, vola} l’insieme dei predicati abduttivi.

In base alla conoscenza dell’agente A1, gli animali sono uccelli, e possono essere o struzzi

o falchi, mentre l’agente A2 riconosce come animali gli struzzi, che sono uccelli.

In KBA1 c’è un vincolo che dice che gli uccelli devono volare (uccello, ¬ vola → ⊥),

mentre in KBA2 ce n’è uno che dice che gli uccelli che non sono struzzi non volano

(uccello, ¬vola, ¬struzzo →⊥).

Supponiamo che ed un certo punto, l’agente A1 osservi un animale, che è un uccello e che

non vola. A1 è INCAPACE di classificare come animale ciò che sta osservando, in quanto

viola il vincolo per cui gli uccelli devono volare.

L’idea è quindi di sfruttare la distribuzione e la molteplicità della conoscenza all’interno del sistema e a questo scopo, per esempio, possiamo assumere che A1 chieda ad A2 se può

accadere che un uccello non voli e A2 risponda che uno struzzo, che non vola, è un uccello

e quindi classificabile come animale.

Questo è proprio il caso in cui la molteplicità delle conoscenze può trovare soluzioni/spiegazioni ad osservazioni che altrimenti un singolo agente, da solo, non riuscirebbe a trovare e per far questo gli agenti appartene nti al sistema devono poter usare un linguaggio di coordinamento per comunicare tra loro e per sfruttare ognuno la conoscenza degli altri. Questo linguaggio deve essere dotato anche di un meccanismo di verifica della consistenza dei vincoli degli agenti coinvolti in una computazione/dimostrazione affinché per esempio, una spiegazione fornita da un agente ad un altro non violi i vincoli contenuti nella base di conoscenza di quest’ultimo.

Cercheremo quindi di fornire le basi di un linguaggio che renda possibili queste interazioni.

Vediamo prima un po’ di nozioni tecniche e nel capitolo successivo vedremo in dettaglio il linguaggio e a tal proposito il presente capitolo è così organizzato:

1.1 gli agenti e i sistemi multiagente: forniremo le definizioni di agenti intelligenti e di sistema multiagente e le loro proprietà;

1.2 conoscenza distribuita, interazione e comunicazione tra agenti: definiremo le base di conoscenza, diremo cosa si intende per interazione e comunicazioni tra agenti;

1.3 ragionamento abduttivo e background tecnico: spigheremo cosa è, in generale, il ragionamento abduttivo per poi passare alla definizione di programma logico abduttivo;

1.4 il linguaggio LAILA: illustreremo il linguaggio LAILA, di cui questa tesi fornirà un’estensione.

1.1 Gli agenti e i sistemi multiagente

Secondo la Knowlegde Management, che è la disciplina che studia come raccogliere, organizzare e rendere disponibile la conoscenza e le informazioni all’interno di un sistema, le comunità organizzate creano conoscenza all’interno di un gruppo; in altre parole le informazioni vengono condivise e diventano a loro volta conoscenza e questa viene a sua volta condivisa da tutta la comunità e quindi abbiamo un incremento dello sviluppo di altra conoscenza.

La condivisione di conoscenza avviene secondo dei processi di scambio, per esempio un gruppo può contattarne un altro per avere informazioni e/o nuova conoscenza.

Possiamo pensare che queste comunità siano formate da agenti intelligenti.

Definizione 1: un agente è un sistema computazionale capace di azioni indipendenti.

Definizione 2: un sistema multiagente consiste in un insieme di agenti che interagiscono uni con gli altri, tipicamente scambiandosi messaggi attraverso una rete. Al proprio interno, ogni agente ha un proprio “comportamento”, obiettivi e “motivazioni” ([25]).

Per le interazioni “funzionali” gli agenti devono cooperare, negoziare e coordinarsi gli uni con gli altri come fanno le persone ogni giorno.

L'abilità di imparare dalle esperienze per un agente è un parametro importante. Possiamo dare quindi la seguente definizione di agente.

Definizione 3 (Wooldridge & Jennings (1995)): un agente è un computer system che può essere situato in un qualsiasi ambiente e che è capace di azioni autonome in questo ambiente per raggiungere gli obiettivi prefissi.

Il comportamento guidato non è molto difficile da costruire/implementare, infatti, lo facciamo tutte le volte che scriviamo una procedura, una funzione o un metodo. Quando scriviamo una procedura, la descriviamo in termini di assunzioni (precondizioni) e di effetti prodotti se le assunzioni sono valide (postcondizioni). Una volta che invochiamo la procedura, con delle precondizioni, ci aspettiamo che venga eseguita correttamente e che le postcond izioni risultino vere una volta terminata.

L'agente, attraverso i sensori di input, acquisisce informazioni dall'ambiente e produce come output delle azioni che si ripercuotono sull'ambiente stesso, come si può schematizzare con la figura sottostante.

Figura 1

Nella maggior parte dei domini un agente non ha completa conoscenza dell’ambiente e completo controllo su di esso.

L’ambiente può evolvere dinamicamente indipendentemente dall’agente, e le sue azioni possono fallire. In generale, si assume che l’ambiente sia non-deterministico, ovvero eseguendo due volte una stessa azio ne, in circostanze apparentemente identiche, può accadere di avere diversi risultati e in particolare potrebbero non dare l'effetto desiderato. E' da notare inoltre, che non tutte le azioni possono essere utilizzate in tutte le situazioni,

AGENTE AMBIENTE Azioni di output Sensori di input

quindi le azioni hanno associate delle precondizioni che definiscono le possibili situazioni in cui possono essere usate.

Il problema principale per un agente è quello di decidere quale delle sue azioni dovrà eseguire per meglio soddisfare i propri obiettivi.

Un agente intelligente deve avere un comportamento flessibile per riuscire a soddisfare i propri obiettivi. Con “flessibile” intendiamo che un agente deve possedere le seguenti caratteristiche principali:

1. l’autonomia, ovvero la capacità di operare in modo autonomo senza l’intervento di utenti o di altri agenti esterni;

2. l’abilità sociale, ovvero la capacità di comunicare e di suddividere i compiti tra i vari agenti;

3. la reattività, ovvero la capacità di percepire i cambiamenti nell’ambiente e di reagire di conseguenza, questo perché come già detto è in grado di percepire gli stimoli derivanti dall’esterno;

4. la proattività, perché il gruppo è in grado di costruire i propri piani sulla base della propria conoscenza ed esperienza, perseguendo obiettivi che ha scelto di seguire o che gli sono stati da altri, a seconda del suo grado di autonomia;

5. le nozioni mentali, ovvero la capacità dell’agente di avere proprie conoscenze, ricordare esperienze, avere visioni proprie dell’ambiente che lo circonda e sugli altri gruppi con cui collabora; inoltre essere in grado di apprendere dalle sue esperienze, interagendo con l’ambiente e con gli altri tramite rapporti sociali.

Un'altra caratteristica importante è la capacità di comunicare (vedi paragrafo1.2), infatti per poter interagire, gli agenti di un sistema multiagente devono comunicare tra loro.

Spesso gli agenti vengono modellati anche per mezzo di concetti cognitivi basati su stati mentali, quali credenze (beliefs), conoscenze (knowledge), desideri, intenzioni. I modelli più noti sono quelli basati su belief-desire-intention, dove:

- beliefs corrispondono all’informa zione che l’agente ha sul mondo e può essere incompleta o non corretta;

- intentions rappresentano i desideri che l’agente si è impegnato (committed) a realizzare.

Abbiamo accennato, tra le caratteristiche scritte sopra, al grado di autonomia: una possibile idea è che tra due agenti esista una relazione di dipendenza se uno degli agenti richiede all'altro di aiutarlo con il proprio goal. Vediamo quali sono queste relazioni di dipendenza:

1. indipendenza: non esiste dipendenza tra gli agenti;

2. dipendenza unilaterale: un agente dipende da un altro, ma non viceversa;

3. mutua dipendenza: entrambi gli agenti dipendono uno dall'altro perseguendo lo stesso goal;

4. dipendenza reciproca: il primo agente dipende dall'altro per un dato goal, mentre il secondo dipende dal primo per lo stesso goal (i due goal non necessariamente sono gli stessi). Nota: la mutua dipendenza implica la dipendenza reciproca.

Nel sistema implementato attraverso LAILA, e quindi anche nel nostro, avremo questi due ultimi tipi di relazione tra agenti.

1.2 Conoscenza distribuita, interazione e comunicazione tra agenti

L’applicazione software alla base di un sistema di intelligenza artificiale è un ambiente in cui rappresentare, utilizzare e modificare una base di conoscenza. Ogni sistema si compone di una base di conoscenza e un motore inferenziale.

Definizione 1: la base di conoscenza è il modulo che raccoglie la conoscenza sul “dominio”. Si divide in:

1. asserzioni o fatti (memoria temporanea o a breve termine): sono informazioni che riguardano la particolare situazione;

2. relazioni e regole (memoria a lungo termine): formulano i comportamenti di base.

Quindi una base di conoscenza è la rappresentazione delle conoscenze sul mondo, ovvero sul problema da affrontare.

Le implicazioni (conseguenze) della base di conoscenza vengono calcolate da un meccanismo inferenziale (motore inferenziale).

Definizione 2: il motore inferenziale è il modulo che utilizza la base di conoscenza per giungere alla soluzione proposta e per fornire spiegazioni. Al motore inferenziale è delegata la scelta di quale conoscenza è opportuno utilizzare nel processo risolutivo. E’ questo modulo che seleziona le regole che possono essere applicate nella particolare situazione (matching), ne sceglie una e la applica (esecuzione).

Il motore inferenziale sia basa sull’applicazione di metodi deduttivi, come accade nei sistemi esperti, noi però utilizzeremo una procedura abduttiva per fornire spiegazioni a ciò che viene osservato.

I sistemi esperti differiscono dagli agenti in quanto generalmente non sono reattivi, non hanno un comportamento proattivo, non sono né collaborativi gli uni con gli altri, né sanno

coordinarsi gli uni con gli altri, né sono capaci di negoziare gli uni con gli altri (non hanno cioè una capacità sociale).

Come accennato nell’introduzione di questo capitolo e come definiremo meglio nel capitolo 2 al paragrafo 2.1, ogni agente del sistema è munito di una propria base di conoscenza. Ognuna di queste però può non essere uguale ad un’altra presente nel sistema, cioè un agente può avere delle regole comuni ad un altro e delle altre che possiede solo lui. Questa cosa la troviamo presente anche nel mondo di tutti i giorni, ad esempio, nel campo medico abbiamo il medico generico che ha una infarinatura base di tutto e poi troviamo gli specialisti in alcune aree della medicina (ad esempio i neurologi, i cardiologi); un altro esempio può essere preso dalla giurisprudenza, dove troviamo i giudici, gli avvocati penalisti, civili, fiscalisti e così via.

Abbiamo quindi un sistema con conoscenza distribuita: ogni agente può agire in un ambiente e differenti agenti possono avere “sfere di influenza diverse”, nel senso che possono avere il controllo sopra differenti parti dell’ambiente [25].

Un sistema multiagente è composto da un certo numero di agenti che interagiscono tra loro attraverso la comunicazione; infatti per scambiarsi conoscenza gli agenti sono capaci di interagire/comunicare tra loro, come abbiamo accennato brevemente nel paragrafo precedente.

Il meccanismo di comunicazione normalmente usato è quello dello scambio di messaggi, vedendo l’invio e/o la ricezione di un messaggio come una azione eseguita da un agente.

Sono stati sviluppati diversi linguaggi di comunicazione tra agenti, in cui le azioni comunicative sono modellate basandosi sulla teoria filosofica delle azioni (inform, request, query- if, ask, tell).

Nei primi anni ’90 è stato fondato il Knowledge Sharing Effort (KSE) con lo scopo di sviluppare protocolli per lo scambio di conoscenza tra sistemi autonomi di informazione [25].

Il KSE generò:

1. il Knowledge Query and Manipulation Language (KQML): è un linguaggio “esterno” per la comunicazione tra agenti. Esso definisce un formalismo per i messaggi;

2. il Knowledge Interchange Format (KIF): è un linguaggio con l’intenzione esplicita di permettere la rappresentazione di conoscenza su un particolare “dominio del discorso”.

Nel 1995, la Foundation for Intelligent Physical Agents (FIPA) iniziò il proprio lavoro sullo sviluppo di standard per sistemi di agenti. Il punto focale di que sta iniziativa fu lo sviluppo dell’Agent Comunication Language (ACL) che è simile al KQML [25].

Uno dei più importanti precursori dello sviluppo dei sistemi multiagente era il modello blackboard; esso proponeva che un gruppo di risolutori procedeva attraverso un gruppo di sorgenti di conoscenza (agenti) osservando una struttura di dati condivisi detta blackboard. Negli anni ’80 fu sviluppata una interessante variazione in cui il modello blackboard era incapsulato in un linguaggio di programmazione; questa variazione era chiamata Linda [25].

1.3 Ragionamento abduttivo e background tecnico

Cosa è il ragionamento abduttivo?

Il filosofo Pierce fu il primo ad introdurre la nozione di abduzione e in [16] ha identificato tre distinte forme di ragionamento:

1. deduzione: un processo analitico basato sull’applicazione di regole generali a casi particolari, con l’inferenza di un risultato;

2. induzione: una forma di ragionamento sintetico che inferisce le regole generali dai casi particolari e da regole generali;

3. abduzione: forma di ragionamento sintetico che inferisce i casi particolari dai loro risultati e da regole generali (può anche essere caratterizzata come “l’adozione probazionale di ipotesi”; rimane in ogni caso una forma debole di inferenza, in quanto non possiamo dire che la spiegazione sia vera, ma che PUO’ essere vera).

In altri termini, l’abduzione può essere vista come l’inversa della deduzione infatti, mentre la deduzione trae le conclusioni di un insieme di premesse date, l’abduzione dati:

1. un asserto da spiegare o giustificare;

2. un insieme di fatti accertati e di vincoli da rispettare; 3. un insieme di ipotesi possibili,

individua gruppi di ipotesi compatibili con i fatti e con i vincoli in grado di derivare l’asserto dato.

Passando da un “Closed World Assumption” comunemente usato in programmazione logica ad un mondo “aperto”, l’abduzione è stata riconosciuta come un potente meccanismo per ragionamenti ipotetici in presenza di conoscenza incompleta.

L’abduzione è anche conosciuta come “ragionamento dagli effetti alla causa”.

Esempio

Consideriamo il seguente insieme di clausole (è quello che in seguito verrà chiamato teoria).

prato_bagnato ← la_notte_ha_piovuto prato_bagnato ← irrigatore_acceso scarpe_bagnate ← prato_bagnato

Se osserviamo che le nostre scarpe sono bagnate e vogliamo sapere il perché, {la_notte_ha_piovuto} è una possibile spiegazione. Questo è dunque un insieme di ipotesi che, unito alla conoscenza esplicita espressa dalle tre clausole scritte sopra, implica l’osservazione. Però questa non è l’unica, infatti anche {irrigatore_acceso} è una possibile spiegazione.

In sostanza, l’abduzione consiste nell’elaborazione di spiegazioni per osservazioni date nel contesto di una determinata teoria.

Vediamo come formalizzare questo ragionamento, dando le definizioni prima di programma logico e poi di programma logico abduttivo.

Definizione 1: una clausola di programma è una clausola della forma A ← B1, …, Bn.

L’atomo A è chiamato testa della clausola, mentre l’insieme delle premesse B1, …, Bn è detto corpo della clausola.

Definizione 2: un programma definito è un insieme finito di clausole di programma.

Definizione 3: sia T una teoria e G una formula (una osservazione), possiamo caratterizzare in modo molto semplice il problema abduttivo come il problema di trovare un insieme di formule ? (sottoinsieme delle formule abducibili) tali che:

1. T ∪ ? |= G

Le spiegazioni contenute in ∆ sono, generalmente, un insieme speciale e predefinito di formule chiamate abducibili e che indicheremo con A.

Per restringere l’insieme ? utilizziamo il metodo dei vincoli di integrità; quindi dato un insieme IC di vincoli di integrità la condizione (2) può essere così riscritta: T ∪ ? soddisfa IC.

I vincoli di integrità sono utilizzati per rifiutare le spiegazioni abduttive che si presentano nel corso di una computazione e che sono in contrasto con i suddetti vincoli.

Definizione 4: un programma logico abduttivo (ALP) è una tripla <P, A, IC>, dove P è un programma logico (la teoria _{T della definizione 3), possibilmente con} atomi abducibili nel corpo; A è un insieme di abducibili e IC è un

insieme di vincoli di integrità.

Gli abducibili appartenenti all’insieme A non devono avere definizione in P (o in T) e inoltre non devono comparire nelle conclusioni (testa) delle regole. Si utilizza anche la convezione di scrivere solo gli abducibili “positivi”, mentre le negazioni vengono sottointese cioè, ad esempio A = {a, b, c}≡A = {a, b, c, ¬a, ¬b, ¬c}.

Dato un programma abduttivo e una formula G, lo scopo dell’abduzione è trovare un insieme ? che insieme a P provi (soddisfi) G (cioè P ∪ ? |= G) e tale che P ∪ ? sia consistente rispetto ad IC.

Kakas e Mancarella [12] hanno sviluppato una semantica per i programmi logici abduttivi generalizzando i modelli stabili per LP.

Definizione 5: dato un framework abduttivo <P, A, IC> e dato ? ⊆ A, allora M(?) è un modello stabile generalizzato di <P, A, IC> SE E SOLO SE:

1. M(?) è un modello stabile di P ∪ ? ; 2. M(?) |= _IC.

1.4 Il linguaggio LAILA

Il linguaggio LAILA (Language for AbductIve Logic Agents) è stato sviluppato presso il DEIS dell’Università di Bologna [3, 4].

Come già detto LAILA è un linguaggio che può essere usato da agenti logici capaci di usare il ragionamento abduttivo. Gli agenti possono collaborare o competere per la soluzione di problemi.

Un esempio collaborativo si ha, ad esempio, considerando un gruppo di medici ognuno esperto in un’area particolare, che devono collaborare per formulare diagnosi per un dato insieme di sintomi.

Ogni esperto può essere modellato attraverso un agente abduttivo che cerca una spiegazione considerando solo un sottoinsieme dei sintomi, quelli rilevanti per la sua specializzazione.

Gli operatori previsti da questo linguaggio sono principalmente due operatori di composizione e sono quello collaborativo (&) e quello competitivo (;), che possono essere usati da ogni agente per formulare e coordinare query abduttive ad un insieme di agenti presenti nel sistema. Prevede inoltre l’operatore di comunicazione (>) che è utilizzato per passare le query agli altri agenti, e un operatore di “down-reflection” (↓) per scatenare una derivazione abduttiva locale.

Un programma in LAILA è un insieme di clausole così definite [4]:

L-Clause :: = Atom :- L-Body. L-Body ::= L-Expr , L-Body | L-Expr

L-Expr ::= L-Fact & L-Expr | L-Fact ; L-Expr | L-Fact

L-Fact ::= ↓LiteralList | Agent > LiteralList | Literal | (L-Body) LiteralList ::= Literal | (Literals)

Lterals ::= Literal , Literals | Literal Agent ::= Atom

dove Atom è un simbolo di predicato n-ario seguito da una lista di n termini p(t1, …,tn) o

vero o falso; un Literal è un atomo o la negazione di un atomo e un termine è una costante, una variabile o la composizione di termini.

Una computazione inizia attraverso una query definita come Query ::= ? L-Body.

Il meta-interprete di LAILA è scritto in un sottolinguaggio di Prolog chiamato Jinni, che è un linguaggio di programmazione logica esteso con primitive Linda-like per programmi concorrenti.

Le regole semantiche di LAILA sono le seguenti [3, 4], sapendo che con la scrittura

A |-Bδ q viene indicato il fatto che l’agente A, collaborando con l’insieme di agenti B, riesce a provare la query q, assumendo come ipotesi δ:

Formula per la down-reflection:

A |-abdδ G

(L-1) --- A |-Aδ↓G

dove:

- A è un agente appartenente al sistema (quello in apice rappresenta l’agente che può dimostrare G ed è uguale a quello che appare nella precondizione della regola ed è quello che utilizza la procedura abduttiva );

- G è il Goal da dimostrare;

- δ è l’insieme delle ipotesi abduttive che devono essere assunte per dimostrare G; questo insieme è restituito sia come output dalla procedura abduttiva che viene chiamata/attivata dall’agente A sulla propria base di conoscenza sia come output della computazione fatta dalla regola.

Formula per la comunicazione:

Y |-Bδ1 G ∧ B ∪ X |-consδδ1

(L-2) --- X |-B ∪ X_δ Y > G

dove, X e Y sono due agenti distinti; l’agente X chiede a Y di dimostrare G.

Con B ∪ X |-consδ δ1 si richiede che gli agenti coinvolti nella computazione siano consistenti tra loro.

Formula per la competizione:

A |-Bδ f A |-Bδ F

(L-3.1) --- (L-3.2) --- A |-Bδ f ; F A |-Bδ f ; F

dove f è un L-Fact, F è un L-Expr e B è l’insieme degli agenti che sono coinvolti nella computazione. Si deve operare una scelta non-deterministica tra le due regole.

Ad esempio, la query seguente, fatta da A0:

? A1 > (q1) ; A2 > (q2)

significa che A0 chiede all’agente A1 di dimostrare q1 e all’agente A2 di dimostrare q2.

Come abbiamo appena detto la scelta della regola da applicare è non deterministica. Se entrambe le dimostrazioni falliscono, tutta la query fallisce.

Formula per la collaborazione:

A |-B’δ’ f ∧ A |-B’’δ’’ F ∧ B’ ∪ B’’ |-consδδ’ ∪δ’’

(L-4) --- A |-B’ ∪ B’’_δ f & F

dove f è un L-Fact, F è un L-Expr e B’ , B’’ sono due insiemi (dis tinti o meno) di agenti coinvolti nella computazione ed è richiesto che siamo consistenti.

Ad esempio, la query formulata dall’agente A0:

? A1 > (q1) & A2 > (q2)

significa che A0 chiede all’agente A1 di dimostrare q1 e all’agente A2 di dimostrare q2. E’

importante sottolineare il fatto che se una delle due dimostrazioni fallisce, allora l’intera query fallisce.

Formule per il Goal :

A |-B’δ’ h ∧ A |-B’’δ’’ G (L-5.1) --- A |-B’ ∪ B’’_δ’ ∪δ’’ h, G ∃ h :- G ∈ ABM(A) ∧ A |-Bδ G (L-5.2) --- A |-Bδ h (L-5.3) --- A |-A∅ true

dove con ABM(A) è indicato il modulo ABM dell’agente A.

Formule per la consistenza:

∀ Ai∈ B Ai |-abdδiδ ∧ δ ⊂∪Aj ∈ Bδ ∧ B |-consδ’∪Ai ∈ Bδi (L-6.1) --- B |-consδ’δ ∀ Ai∈ B Ai |-abdδδ (L-6.2) --- B |-cons_δδ

Il controllo di consistenza di δ è fatto prima individualmente da ogni agente attraverso derivazioni abduttive che possono dare un δ “allargato”, ovvero l’insieme di partenza a cui sono state aggiunte nuove ipotesi. In questo caso si deve fare un altro controllo di

consistenza per queste ipotesi aggiunte. Si continua ricorsivamente fino a quando non vengono aggiunte altre ipotesi e quindi possiamo usare la seconda regola.

Questo linguaggio è implementato su un’architettura chiamata ALIAS (Abductive LogIc Agent System), in cui gli agenti sono situati su una rete distribuita di computer con interprete Java.

La struttura interna di ogni agente, mostrata nella figura 2 qui sotto, è composta sostanzialmente da due moduli: l’Abductive Reasoning Module (ARM), che comprende la base di conoscenza abduttiva dell’agente, e l’Agent Behavior Module (ABM), che include la base di conoscenza dell’agente relativa al comportamento.

Figura 2: struttura di un agente ALIAS

La base di conoscenza abduttiva è rappresentata da un programma logico abduttivo (paragrafo 1.3), che descrive la conoscenza locale di ogni agente ed è usata per il ragionamento abduttivo.

La base di conoscenza che modella il comportamento è un insieme di clausole di LAILA, usate appunto per descrivere le azioni e le interazioni degli agenti con l’ambiente. In particolare, come già accennato sopra, il comportamento sociale è espresso all’interno del modulo ABM, attraverso “domande” collaborative/competitive che possono essere rivolte agli altri agenti. Alcune volte il comportamento dell’agente può richiedere una spiegazione abduttiva di un’osservazione: questa situazione richiede una interazione tra il modulo ABM e il modulo ARM in modo da fare iniziare una computazione abduttiva locale.

Un agente in ALIAS, come è mostrato nella figura 3, è implementato tramite due metainterpreti, il primo supporta l’esecuzione dei programmi in LAILA, il secondo supporta il ragionamento abduttivo, raffinato dalla procedura Kakas-Mancarella. Abbiamo quindi l’utilizzo di un algoritmo con 2 fasi: la prima coinvolge derivazioni abduttive all’interno della base di conoscenza locale (tramite appunto la Kakas-Mancarella), mentre

KB ABM KB ARM KB ABM KB ARM KB ABM KB ARM KB ABM KB ARM KB ABM KB ARM KB ABM KB ARM Altri agenti

la seconda calcola/controlla la consistenza, al fine di trovare un insieme di ipotesi che risulti consistente con tutti i vincoli di integrità presenti nelle basi di conoscenza ti tutti gli agenti coinvolti nella computazione.

Figura 3: implementazione dei moduli di un agente ALIAS

La procedura Kakas-Mancarella [10, 11, 12] come già detto, è una estensione della procedura proposta da Eshghi K. e Kowalski R. A. per la programmazione logica [7]. Entrambe le procedure estendono il meccanismo base di risoluzione adottato in SLD e SLDNF per la programmazione logica, attraverso l’introduzione delle nozioni di derivazione abduttiva e derivazione per consistenza.

Gli agenti in ALIAS stanno su differenti macchine collegate tra loro e comunicano tra loro, come detto sopra, attraverso primitive scritte in un linguaggio Linda- like, attraverso il deposito e il prelievo di tuple in uno spazio condiviso detto blackboard.

KB ABM KB ARM KB ABM abm(Head,Body) KB ARM abducibles([…]) arm(Head,Body) ic([…]) LAILA metainterprete Kakas-Macarella blackboard

Vediamo infine un esempio di utilizzazione degli operatori di LAILA [4] e di formalizzazione degli agenti.

Esempio

Consideriamo tre agenti, chiamati a, b, e c così formalizzati.

Agente_a:

ABM

obain([R|Tail]) :- b > get(a, b, R) & obtain(Tail). Obtain([]) :- true. --- ARM I_am(a). have(picture). have(hammer). max_price(nail, 8). :- max_price(R, M), sell(-, a, R, M1), M1 > M. Agente_b: ABM

get(X, Y, R) :- ↓req(X, Y, R) ; c > (get(X, Y,R), get(Y, c, R)). --- ARM

I_am(b). friend(a). have(nail).

:- req(X, Y, R), I_am(Y), have(R), friend(X), friend(X), not_sell(b, X, R, 0).

Agente_c: ABM get(X, Y, R) :- ↓req(X, Y, R). --- ARM I_am(c). have(nail). cost(nail, 6).

:- req(X, Y, R), I_am(Y), have(R), cost(R, P), not_sell(Y, X, R, P)

L’insie me degli abducibili è A = {req(a, b, nail), req(b, c, nail), sell(c, b, nail, 5), sell(b, a, nail, 6), sell(b, a, nail, 0),}∪ negazione_dei_letterali.

Il predicato max_price(Item, Price) rappresenta il prezzo massimo che un agente è disposto a pagare per avere l’oggetto Item; cost(Item, Price) è il predicato che rappresenta il prezzo a cui un agente vende l’oggetto Item, mentre con il predicato get(Buyer, Seller, Item) si rappresenta la richiesta del comp ratore (Buyer) al venditore (Seller) per ottenere l’oggetto Item.

L’agente a possiede un quadro e un martello, ma ha bisogno anche di un chiodo per poter appendere il quadro e per ottenerlo lo deve chiedere all’agente b.

Supponiamo che la query fatta per iniziare la computazione totale sia ?obtain([nail]) fatta all’agente a e accenniamo la costruzione dell’albero di derivazione.

Applichiamo la regola per il Goal (L-5.2).

(A)

--- ∃ obtain([R|Tail]) :- b > get(a, b, R) & ∧ a |-Bδ b > get(a, b, nail) & obtain([]) obtain(Tail) ∈ ABM(a)

(L-5.2) --- a |-Bδ obtain([nail])

(A):

applichiamo la regola (L-4) per la collaborazione.

(B) (C) (D)

--- --- --- a |-B1δ1 b > get(a, b, nail) ∧ a |-B2δ2 obtain([]) ∧ B1∪ B2 |-consδδ1 ∪δ2

(L-4) --- a |-B1 ∪ B2δ b > get(a, b, nail) & obtain([])

Con B = B1∪ B2.

(B):

applichiamo la regola (L-2) per la comunicazione.

(E)

---

b |-B3δ3 get(a, b, nail) ∧ B3∪ a |-consδ1δ3

(L-2) --- a |-B1δ1 b > get(a, b, nail)

(E):

applichiamo la regola (L-5.2) per il Goal.

∃ get(X, Y, R) :- ↓req(X, Y, R) ; c > (get(X, Y,R), get(Y, c, R)) ∈ ABM (b) ∧ (F)

∧ --- b |- B3δ3↓req(a, b, nail) ; c > (get(a, b, nail), get(b, c, nail))

(L-5.2) --- b |-B3δ3 get(a, b, nail)

(F):

applichiamo le regole (L-3.1) e (L-3.2) per la competizione. Con questa regola vengono creati due alberi di derivazione. Il primo è il seguente:

(G)

--- b |- B3δ3↓req(a, b, nail)

(L-3.1) --- b |- B3_δ3↓req(a, b, nail) ; c > (get(a, b, nail), get(b, c, nail))

Mentre il secondo è:

(H)

--- b |- B3_δ3 c > (get(a, b, nail), get(b, c, nail))

(L-3.2) --- b |- B3δ3↓req(a, b, nail) ; c > (get(a, b, nail), get(b, c, nail))

(G):

applichiamo la regola (L-1) per la down-reflection.

b |- abdδ3 req(a, b, nail)

(L-1) --- b |- B3δ3↓req(a, b, nail)

Alla fine di questo ramo abbiamo che B3 = {b} e δ3 = {req(a, b, nail), sell(b, a, nail)}.

(H):

applichiamo la regola (L-2) per la comunicazione.

…. …

--- --- c |-B4δ4 (get(a, b, nail), get(b, c, nail)) ∧ B4∪ b |-consδ3δ4

(L-2) --- b |- B3δ3 c > (get(a, b, nail), get(b, c, nail))

Con B3 = B4∪{c}.

Alla fine di questo ramo otteniamo che B4 = {c}, δ4 = {req(a, b, nail), req(b, c, nail), sell(c,

b, nail, 5)}, ment re quando andiamo a fare il controllo di consistenza tra l’agente b e l’agente c otteniamo δ3 = {req(a, b, nail), req(b, c, nail), sell(c, b, nail, 5), sell(b, a, nail,6)}.

Come abbiamo già detto nel momento in cui abbiamo presentato le regole semantiche, LAILA non specifica quale insieme tra i due δ3 viene restituito dall’operatore competitivo.

Tornando al sottoalbero (A), abbiamo :

(C):

applichiamo due delle regole per il Goal: la (L-5.2) e la (L-5.3).

--- (L-5.3) ∃ Obtain([]) :- true ∈ ABM(a) ∧ a |-A∅ true

(L-5.2) --- a |-B2δ2 obtain([])

Con B2 = {a} e δ2 = ∅.

Il sottoalbero etichettato con (D) è quello in cui viene verificata la consistenza tra gli agenti coinvolti nella computazione.

A seconda di quale scelta si opera nella regola competitiva avremo B = {a, b}, con δ3 = {req(a, b, nail), sell(b, a, nail)} e δ2 = ∅, oppure B = {a, c} con δ3 = {req(a, b, nail), req(b, c, nail), sell(c, b, nail, 5), sell(b, a, nail,6)} e δ2 = ∅.

CAPITOLO 2

LINGUAGGIO

In questo capitolo descriveremo il nostro linguaggio, più precisamente i suoi operatori.

Come è logico, di essi forniremo sintassi e semantica ed è proprio per questo che abbiamo organizzato il capitolo nei seguenti paragrafi:

2.1 sistema: descriveremo brevemente il sistema in cui opereremo;

2.2 sintassi: descriveremo la sintassi degli operatori e delle clausole usate per modellare ogni agente del sistema; vengono introdotti i concetti di consistenza e gerarchia (per poi riprenderli nel paragrafo seguente). Inoltre verranno presentati piccoli esempi per aiutarci a capire il funzionamento degli operatori;

2.3 considerazioni sulla gerarchia : riprendendo quanto detto nel paragrafo precedente, spiegheremo il significato di consistenza e gerarchia tra gli agenti (a differenza di LAILA in cui è

presente un’unica definizione di consistenza, noi ne avremo due: la consistenza verticale e la consistenza orizzontale);

2.4 semantica: descriveremo, in stile operazionale, le regole per la semantica degli operatori del linguaggio e inoltre, riprendendo gli esempi usati nel paragrafo 2.2, mostreremo l’applicazione di tali regole.

2.1 Sistema

Il nostro linguaggio è un’estensione di LAILA, in quanto introdurremo due differenze sostanziali:

1. la presenza di due tipi di consistenza anziché uno solo;

2. la possibilità di passare, nella comunicazione, un insieme di abucibili.

Cercheremo di far vedere, con gli esempi trattati nel capitolo 3, come queste estensioni aumentino l’espressività del linguaggio originale.

Come in ALIAS (capitolo 1 paragrafo 1.4) ognuno dei nostri agenti ha due componenti, una in cui è modellata la base di conoscenza locale (in ALIAS si chiama Abductive Reasoning Module, o più semplicemente ARM, mentre qui sarà chiamato Knowledge Base (o Kb)) e una in cui è modellato il comportamento dell’agente verso altri agenti, cioè è il modulo per la comunicazione tra agenti (in ALIAS si chiama Agent Behavior Module (o ABM), mentre noi l’abbiamo chiamato Regole per Comunicare (o Rc)).

Dato quindi un agente Ai (detto agente mittente), all’interno del suo modulo Rc troviamo

delle regole che gli consentono di demandare ad un altro agente (detto agente ricevente) la dimostrazione di un Goal che altrimenti, utilizzando solo le regole espresse nella sua base di conoscenza, non riuscirebbe a portare a termine.

Ogni base di conoscenza locale Kb è rappresentata dalla tripla <T, A, IC>.

Definizione 1: un agente Ai è rappresentato mediante una quadrupla <RcAi, TAi, A, ICAi>,

dove :

- RcAi modella le comunicazioni dell’agente Ai verso gli altri agenti

presenti nel sistema, ed è una teoria Logic Programming; - TAi, A, ICAi modella la base locale dell’agente Ai, dove TAi è

l’insieme di clausole, detto teoria; A è l’insieme degli abducibili del sistema (e ipotizziamo che è lo stesso insieme per ogni agente presente nel sistema); ICAi è l’insieme dei vincoli di integrità.

Quindi questo è un programma logico abduttivo (capitolo 1, paragrafo 1.3).

Definizione 2: un agente mittente è un agente, definito come sopra, che chiede ad un altro agente del sistema, detto agente ricevente, e anch’esso definito in base alla definizione 1, di dimostrare un determinato Goal.

Ogni agente risiede su un terminale e ognuno è collegato agli altri, e questo perché si prevede che ognuno possa comunicare con gli altri, attraverso gli opportuni operatori che introdurremo nel paragrafo successivo, per riuscire nella dimostrazione di un Goal che non riesce a dimostrare utilizzando solamente la propria base di conoscenza locale. Esiste un collegamento tra l’agente A e l’agente B se in RcA esiste almeno una regola di

comunicazione tra loro, per la dimostrazione di un predicato.

L’utente del sistema può comunicare con qualsiasi agente attraverso una query per dimostrare un Goal.

2.2 Sintassi

Per prima cosa mostriamo gli operatori di comunicazione presenti nel nostro linguaggio e poi passeremo alla formalizzazione sintattica delle clausole che modellano ogni agente presente nel sistema.

Gli operatori previsti per la comunicazione sono principalmente tre:

1. l’operatore di comunicazione 1:1: un agente mittente per dimostrare un Goal chiede aiuto ad un altro agente (questo operatore è indicato con il simbolo >O

oppure >V a seconda del tipo di consistenza richiesto);

2. l’operatore di comunicazione collaborativa: un agente mittente chiede aiuto a più agenti per la dimostrazione di un Goal; affinché la dimostrazione vada a buon fine deve accadere che TUTTI gli agenti riceventi coinvolti nella computazione riescano nella dimostrazione che gli viene richiesta (l’operatore è indicato attraverso i simboli >O … &… oppure >V … &…, anche qui si utilizza uno o l’altro a seconda

del tipo di consistenza) ;

3. l’operatore di comunicazione competitiva: un agente mittente chiede aiuto per una dimostrazione a più agenti; in questo caso per il buon esito della dimostrazione è sufficiente che ALMENO UNO degli agenti riceventi porti a buon fine la dimostrazione che gli viene richiesta (questo operatore è indicato attraverso i simboli >O … || …).

Per capire meglio la differenza tra comunicazione collaborativa e comunicazione competitiva prendiamo spunto dal campo medico.

Supponiamo di avere un gruppo di medici, ognuno dei quali esperti in una particolare area (ad esempio, gastroenterologia, ematologia ecc.). Ogni esperto può essere modellato come un agente abduttivo il quale ha come obiettivo di trovare una possibile causa come spiegazione dei sintomi presenti nel paziente. Nel caso collaborativo l’équipe medica lavora insieme per formulare un’unica diagnosi; ogni esperto ha come obiettivo di trovare una possibile spiegazione all’insieme dei sintomi (oppure ad un sottoinsieme di essi, quelli relativi alla propria specializzazione) accusati dal paziente.

Nel caso competitivo ogni medico appartenente all’équipe formula una propria diagnosi per i sintomi accusati dal paziente, dopo di che viene scelta, per esempio, quella che meglio si adatta all’anamnesi del paziente.

Vediamo adesso la formalizzazione delle clausole che modellano ogni agente.

Ogni agente è definito come una quadrupla <Rc, T, A, IC>, dove Rc rappresenta le clausole per la comunicazione con gli altri agenti (possono essere considerate come il comportamento verso l’esterno, cioè il comportamento che ogni singolo agente ha nei confronti degli altri agenti presenti nel sistema) e le altre tre componenti rappresentano la conoscenza locale propria di ogni agente.

Vediamo la sintassi delle clausole di Rc, che hanno la forma Testa ← Corpo, dove

Testa ::= Atomo

Corpo ::= Letterale | ↓Letterale | Comunica | Letterale, Corpo | ↓Letterale, Corpo | Comunica, Corpo

Comunica ::= Agente_Mittente Com_Orizzontale | Age nte_Mittente Com_Verticale Com_Orizzontale :: = >O Body & Body | >O Body || Body

Com_Verticale ::= >V Body

Body ::= Agente_Ricevente ({∆in}, Goal) | Body & Body | Body || Body

Letterale ::= Atomo | ¬ Atomo

Atomo ::= predicato(t1, …, tn) (i termini possono essere costanti, variabili, composti

tramite funzioni).

La produzione che definisce Corpo è cosiffatta poiché prevediamo la possibilità che per dimostrare un Goal, che è una lista di letterali, l’agente possa risolvere degli atomi da sé (↓Letterale) e alcuni li possa dimostrare con la comunicazione (infatti, in Rc ci saranno delle regole per la comunicazione verso altri agenti del sistema e/o delle regole che rimandano la dimostrazione, attraverso proprio l’operatore di autodimostrazione (↓), all’utilizzo di regole o di abducibili presenti nella base di conoscenza locale).

Con {∆in} intendiamo un insieme di abducibili (può anche essere vuoto) che viene passato

dal mittente al ricevente per dimostrare Goal, che è una lista di letterali. Risulta quindi che questo insieme deve essere presente anche nella Testa della clausola. Questo insieme sarà rappresentato mediante una opportuna struttura dati.

La presenza e il passaggio di questo insieme di abducibili è la PRIMA differenza che abbiamo rispetto a LAILA, infatti nelle sue regole per la comunicazione non è previsto il passaggio di un insieme di abducibili.

E’ da sottolineare il fatto che Agente_Mittente deve essere diverso da Agente_Ricevente. Inoltre se in una comunicazione si hanno più insiemi {∆in}, questi possono essere sia

diversi che uguali tra loro. La stessa cosa vale se è presente più di un Goal.

Passiamo ora alla sintassi delle clausole della teoria T, che sono della forma Testa ← Corpo, dove

Testa ::= Atomo

Corpo ::= Letterale | Letterale, Corpo Letterale ::= Atomo | ¬ Atomo

Atomo ::= predicato(t1, …, tn) (i termini possono essere costanti, variabili, composti

tramite funzioni).

Assumiamo il fatto che l’atomo che costituisce Testa NON appare nell’insieme A di abducibili.

Passiamo adesso alle clausole dell’insieme A, che è l’insieme dei predicati abducibli e che non hanno definizione nell’insieme _T:

Letterale ::= Atomo | ¬ Atomo

Atomo ::= predicato(t1, …, tn) (i termini sono ground).

Infine l’insieme IC dei vincoli di integrità:

ic ::= Corpo →⊥

Corpo ::= Letterale | Letterale, Corpo Letterale ::= Atomo | ¬ Atomo

Atomo ::= predicato(t1, …, tn) (i termini possono essere costanti, variabili, composti

tramite funzioni).

Le variabili presenti nelle clausole, siano esse della teoria T che dell’insieme IC, si assumono universalmente quantificate.

Una computazione inizia con una query, definita come Query ::= ? Goal, posta ad uno degli agenti del sistema.

Per spiegare la differenza tra l’operatore “>O” e l’operatore “>V”, accenniamo brevemente,

per poi parlarne in modo più ampio e completo nel paragrafo che seguirà, ai concetti di consistenza e gerarchia.

Per quanto riguarda la gerarchia, gli agenti possono essere organizzati appunto in modo gerarchico, cioè ci saranno degli agenti_capo e degli agenti_subordinati (ad esempio in campo medico, il dottore e i tirocinanti, mentre in un processo legale il giudice è il “capo” e gli avvocati, sia il difensore che l’accusa, sono i “subordinati”).

In quest’ottica si viene a creare la necessità di una consistenza tra gli agenti/attori. Avremo due tipi di consistenza:

1. consistenza orizzontale: si utilizza nella comunicazione collaborativa: gli agenti a cui viene richiesto di provare qualcosa devono essere consistenti tra loro e tutti insieme devono essere consistenti con l’agente richiedente (cioè con l’agente_mittente);

2. consistenza verticale: si utilizza in tutti e tre i tipi di comunicazione: nel caso della comunicazione 1:1 gli agenti coinvolti sono soltanto 2 e quindi devono essere

agenti_riceventi siano consistenti tra loro, ma si richiede che quello che riesce a dimostrare quanto gli viene richiesto sia consistente con l’agente_mittente; nella comunicazione collaborativa, a differenza di LAILA, tutti gli agenti_riceventi devono essere consistenti con l’agente_mittente MA NON tra loro.

Quindi abbiamo che il mittente viene visto come il capo e chi riceve/dimostra come il subordinato; come si vede, i ruoli sono interscambiabili e non fissi ed è il mittente che decide quale tipo di consistenza volere.

Oltre alla presenza di abducibili nella comunicazione, la presenza di questi due tipi di consistenza è la SECONDA differenza con LAILA, che ne possiede solamente una di tipo globale/orizzontale.

Vediamo ora alcuni semplici esempi per capire il funzionamento di tutto quello che fino ad ora abbiamo definito.

(Per la semantica di questi esempi, si rimanda il lettore al paragrafo 2.4 in cui vengono introdotte le regole semantiche degli operatori.).

Esempio N. 1

In questo primo esempio mostriamo come può avvenire una comunicazione 1:1 tra due agenti. Supponiamo di avere un sistema nel quale sono presenti i seguenti agenti:

A0 = { Rc0 = {e ← A0 >V A1 ({}, e)}

a ←↓a}

T0 = {a ← b, c}

IC0 = {b, m →⊥} } A1 = { Rc1 = {a ← A1 >V A0 ({}, a)} e ←↓e f ←↓f} T1 = {e ← b, f f ← g} A = {b, d, m, g} IC1 = {f, m →⊥} }

Supponiamo ora che all’agente A0 venga richiesto di eseguire la segue nte query: ? e.

L’agente A0 cerca una regola, tra quelle appartenenti a Rc0, per dimostrare il Goal

richiesto. In Rc0 c’è una regola di comunicazione per la dimostrazione del predicato “e”

che è la seguente:

e ← A0 >V A1 ({}, e),

con la quale l’agente A0 fa richiesta all’agente A1 di dimostrare il Goal per suo conto.

Abbiamo così la seguente comunicazione tra A0 (agente_mittente) e A1 (agente_ricevente).

A0 >V A1 ({}, e).

La consistenza è verticale: entrambi gli agenti coinvolti nella computazione devo no essere consistenti tra loro. Da notare che l’insieme ∆in di abducibili passati da A0 ad A1 per la

Esempio N. 2

Supponiamo di avere un sistema nel quale siano presenti 3 agenti, definiti qui sotto, e vediamo come può avvenire una comunicazione collaborativa con consistenza orizzontale. Siano: A0 = { Rc0 = { a ← A0 >O A1 ({f, s}, b) & A2 ({f, m, s}, c) h ←↓p, A0 >V A2 ({}, z) p ←↓p} T0 = {p ← d} A = {d, f, m, s} IC0 = {b, m, d →⊥} } A1 = { Rc1 = {b ←↓b h←↓h} T1 = {b ←h, f h ← m} A = {d, f, m, s} IC1 = {d →⊥} } A2 = { Rc2 = {p ← A2 >V A0 ({}, p) z ←↓z c ←↓c}

T2 = {z ←f

c ← s}

A = {d, f, m, s}

IC2 = {m, d →⊥}

}

All’agente A0 viene chiesto di dimostrare il predicato “a”, tramite la query: ? a; in Rc0 è

definita una regola per questa dimostrazione:

a ← A0 >O A1 ({f, s}, b) & A2 ({f, m, s}, c)

L’agente A0 per dimostrare il predicato “a” deve comunicare con gli agenti A1 e A2,

chiedendo loro di dimostrare rispettivamente i predicati “b” e “c”. Affinché il predicato della query sia dimostrato deve accadere che entrambi gli agenti riceventi riescano a dimostrare quello che viene loro richiesto, dato che la comunicazione è collaborativa, ed entrambi gli agenti collaborano affinché il predicato principale possa essere dimostrato. Gli insiemi ∆in passati ai riceventi sono, in questo caso, diversi tra loro ma devono

comunque essere un sottoinsieme dell’insieme A di abducibili, che ricordiamo essere lo stesso per tutti gli agenti presenti nel sistema. Questa possibilità può servire quando, per le diagnosi, un medico chiede un consulto a due specialisti in aree diverse per passargli i sintomi competenti al loro campo per meglio diagnosticare la malattia del suo paziente.

Esempio N. 3

A differenza del precedente, in questo esempio vedremo una comunicazione collaborativa con consistenza verticale. Supponiamo di avere il sistema seguente:

A0 = { Rc0 = { p ← A0 >V A1 ({b, f, m, g}, e) & A2 ({m, g}, q) c ←↓c} T0 = {c ← d} A = {d, b, f, m, g} IC0 = {m, d →⊥} } A1 = { Rc1 = {e ←↓e h ←↓h} T1 = {e ←b, f h ← g} A = {d, b, f, m, g} IC1 = {f, h →⊥} } A2 = { Rc2 = {h ← A2 >V A1 ({b}, h) r ←↓r q ←↓q}

T2 = {r ← f

q ← m}

A = {d, b, f, m, g}

IC2 = {g, r →⊥}

}

All’agente A0 viene passata la query: ? p.

Perché la query vada a buon fine, A0 cerca una regola del tipo “p ← Corpo”. Ne trova una

in Rc0 che è una regola di comunicazione collaborativa, che dice che affinché il predicato

“p” venga dimostrato occorre che entrambi gli agenti riceventi A1 e A2 dimostrino,

rispettivamente, i predicati “e” e “q”:

p ← A0 >V A1 ({b, f, m, g}, e) & A2 ({m, g}, q)

A differenza dell’esempio precedente, qui viene richiesta una consistenza verticale, cioè A1

e A2 devono essere consistenti con A0 ma non lo devono essere tra loro, in altre parole

ognuno dei riceventi può calcolare assunzioni/ipotesi che potrebbero violare i vincoli dell’altro me ntre non violeranno i vincoli del mittente A0.

Esempio N. 4

Infine vediamo la comunicazione competitiva. Supponiamo di avere il seguente sistema con:

A0 = { Rc0 = { a ← A0 >V A1 ({f, g}, d) || A2 ({f, g}, b)

T0 = {b ← g} A = {f, m, g, s} IC0 = {b, s →⊥} } A1 = { Rc1 = {b ← A1 >V A2 ({}, b) d ←↓d h ←↓h } T1 = {d ← f h ← b} A = {f, m, g, s} IC1 = {f, m →⊥} } A2 = { Rc2 = {h ← A2 >V A1 ({b}, h) b ←↓b q ←↓q} T2 = {b ← r q ← m} A = {f, m, g, s} IC2 = {g, r →⊥} }

All’agente A0 viene chiesto di provare a dimostrare la query: ? a.

In Rc0 c’è una regola di comunicazione utile alla dimostrazione che è:

a ← A0 >V A1 ({f, g}, d) || A2 ({f, g}, b)

In questo caso la comunicazione è competitiva, basta cioè che almeno uno dei due agenti riceventi riesca nella propria dimostrazione.

La consistenza richiesta è verticale, in pratica solo il ricevente che riesce nella propria dimostrazione dovrà essere consistente con il mittente.

Nel paragrafo 2.4 utilizzeremo ancora questi quattro esempi per mostrare come vengono applicate le regole semantiche, mentre nel capitolo 3 vedremo degli esempi ritenuti da noi più significativi e completi nei due campi in cui riteniamo utile il nostro lavoro, ovvero nel campo medico e nel campo giuridico.

2.3 Considerazioni sulla gerarchia

Come abbiamo già accennato nel paragrafo sulla sintassi, nel nostro linguaggio, a differenza di LAILA, esistono due tipi di consistenza indotta dalle comunicazioni.

Sempre nel solito paragrafo, abbiamo detto che ogni agente può giocare indistintamente il ruolo di “capo” e di “subordinato”, cioè una volta può chiedere una dimostrazione (facendo quindi il ruolo del capo) e la volta successiva invece potrebbe dimostrare un predicato su richiesta di un altro agente (in questo caso è un subordinato).

L’ idea di avere una gerarchia può trovare applicazione in vari campi. A titolo di esempio discutiamo il caso giuridico, dove forme di ragionamento automatico sono già state utilizzate, soprattutto nei paesi anglosassoni. Vediamo di cosa si tratta [18].

Nei paesi anglosassoni vige un ordinamento di common law, il quale trae origine proprio dall’esperienza giuridica inglese, in cui le sentenze sono fonti del diritto e vincolano i giudici dei casi successivi. Negli ordinamenti di civil law, come il nostro, invece le sentenze non hanno valore giuridico al di fuori del caso deciso.

Definizione 1: un precedente, in termini molto generali, è costituito da due componenti: 1. un caso, inteso come una specifica situazione problematica individuale; 2. la soluzione data al problema espresso dal caso, in seguito alla

considerazione e alla valutazione delle caratteristiche del caso stesso.

Il precedente giudiziale ha, negli ordinamenti di common law, un valore istituzionale e questo deriva anche dal fatto che si possono strutturare gli organi giudiziali. Infatti, gli organi giudiziali sono strutturati in una gerarchia funzionale, nella quale un giudice X è superiore ad un giudice Y, se X è competente a decidere sui ricorsi contro la decisione di Y

Figura 4: albero giudiziario

La decisione di un certo giudice X è un precedente gerarchicamente superiore per un giudice Y, se X è un predecessore di Y nell’albero giudiziario (cioè se attraverso uno o più passaggi è possibile discendere da X a Y). Ad esempio, la decisione del giudice supremo A è un precedente gerarchicamente superiore per tutti gli altri giudici, mentre la decisione di B è un precedente gerarchicamente superiore per E ed F ma non per G.

Il precedente gerarchicamente superiore è quello che normalmente ha maggiore efficacia, anche perché, se il giudice gerarchicamente inferiore decide in difformità dal giudice gerarchicamente superiore, questo ultimo può revocare la decisione del primo.

La decisione di un giudice X è un precedente gerarchicamente inferiore per un giudice successivo Y, se X è un successore di Y nell’albero giudiziario (vale a dire se è possibile discendere da Y a X attraverso uno o più passaggi). Ad esempio sempre con riferimento all’albero qui sopra riportato, la decisione di E è un precedente gerarchicamente inferiore per B, mentre non lo è per G.

Il giudice superiore normalmente non si sentirà vincolato ad uniformarsi alla decisione del giudice inferiore.

I grado E F G H I L M

II grado B C D

Esiste anche quello che si chiama precedente gerarchicamente irrelato, ed è quello deciso da un giudice che non sia né predecessore né successore rispetto al giudice del nuovo caso. Un caso particolare è il cosiddetto precedente orizzontale, adottato cioè da un diverso giudice dello stesso livello. Ad esempio, rispetto al giudice E, tanto il precedente di C che il precedente di G sono gerarchicamente irrelati, mentre solo il precedente di G è un precedente orizzontale.

Si ha un conflitto tra precedenti quando vi siano più precedenti tutti pertinenti ad un nuovo caso. Per risolvere questo conflitto la dottrina common law utilizza i seguenti criteri:

1. principio gerarchico: nel caso di conflitto prevale il precedente emanato dal giudice gerarchicamente superiore;

2. principio di specialità: nel caso in cui uno dei precedenti sia maggiormente specifico rispetto ai fatti del caso, allora il precedente più generico, o comunque meno pertinente, può essere distinto e tralasciato;

3. principio cronologico: prevale il più recente dei precedenti in conflitto.

Associando tutte queste idee e definizioni alle idee di operatore collaborativo e operatore competitivo, abbiamo ritenuto che fosse necessario avere due tipi di consistenza (a differenza di LAILA in cui ne compare una sola ):

1. consistenza orizzontale: si utilizza nella comunicazione collaborativa: gli agenti a cui viene richiesto di provare qualcosa DEVONO essere consistenti tra loro e tutti insieme devono essere consistenti con l’agente richiedente (corrisponde al precedente orizzontale);

2. consistenza verticale: si utilizza in tutti e tre i tipi di comunicazione: nel caso della comunicazione 1:1 gli agenti coinvolti sono soltanto 2 e quindi, per ovvie ragioni, devono essere consistenti tra loro; nella comunicazione competitiva non ha importanza che gli agenti_riceventi siano consistenti tra di loro, è necessario che quello che riesce a dimostrare quanto gli viene richiesto sia consistente con l’agente_mittente; nella comunicazione collaborativa, infine, tutti gli agenti_riceventi DEVONO essere consistenti con l’agente_mittente MA NON tra loro (corrisponde ai precedenti superiore e inferiore).

Un’altra possibilità di consistenza per la comunicazione 1:1, è quella di non prevederla, cioè non occorre che i due agenti implicati nella dimostrazione siano consistenti tra loro. In questo modo quindi sarebbero ammesse violazioni degli IC del mittente da parte del ricevente e viceversa. Nel nostro lavoro non la presentiamo in quanto non la riteniamo di grande interesse, in quanto, essendo ammesse le violazioni ai vincoli di integrità, è inutile porsi il problema della consistenza, visto che questo controllo è attuato proprio al fine di evitare di avere simili comportamenti.

Come si vede da questo capitolo, abbiamo preso numerosi spunti sia dal campo medico che da quello giuridico e quindi nel capitolo successivo mostreremo degli esempi più significativi rispetto a quelli fino a qui presentati, proprio riferendoci al mondo medico e al mondo giuridico.

2.4 Semantica

In questo paragrafo illustreremo le regole semantiche degli operatori e poi passeremo a mostrare il loro uso facendo riferimento agli esempi introdotti già nel paragrafo della sintassi.

Indichiamo con A |-Bδ q, il fatto che l’agente A, collaborando con l’insieme di agenti B, riesce a provare la query q, assumendo come ipotesi δ. Quindi con B si indica l’insieme degli agenti coinvolti nella computazione e con δ l’insieme delle ipotesi da assumere; quest’ultimo insieme è il parametro di output del processo computazionale. E’ da evidenziare che l’insieme δ di output può essere sia un sovrainsieme dell’insieme ∆in

passato come input insieme al predicato da dimostrare sia ∆in stesso.

Definizione 1: sia A un agente e G una lista di letterali;

la scrittura A |-abdδ G denota la dimostrazione abduttiva locale fatta dall’agente A che restituisce come output l’insieme δ delle ipotesi da assumere per concludere positivamente la dimostrazione.

Adotteremo inoltre la seguente notazione per la consistenza.

Definizione 2: la scrittura B |-consδδ ’, dove δ’ è l’insieme di abducibili che servono per la dimostrazione di un Goal attraverso un operatore, denota il fatto che gli agenti appartenenti all’insieme B sono consistenti tra loro, cioè l’insieme dei loro vincoli di integrità è rispettato dall’insieme di abducibili δ, che è l’insieme finale restituito come output. La sua semantica dichiarativa è definita nel modo seguente,

indicando con I ⊆{1, …, n} e ricordando che B = {Ai| i ∈ I}:

∀ Ai∈ B, Ti∪δ “soddisfa” ∪j ∈ IICj

Definizione 3: regole per Goal. ∃ h ← C ∈ RcA , A |-Bδ C (3.1) --- A |-B_δ h A |-B1δ1 h , A |-B2δ2 C , A ∪ B1∪ B2 |-consδδ1 ∪δ2 (3.2) --- A |-B1 ∪ B2δ h, C

Nella regola 3.1, per effettuare la dimostrazione l’agente A ricerca tra le proprie regole, una la cui testa corrisponda a ciò che deve dimostrare. Dopo di che si richiede la dimostrazione, sempre da parte dell’agente A, del corpo della regola.

La regola 3.2 serve per la composizione dei predicati, quando cioè il Corpo è composto da più parti. A differenza della corrispondente regola in LAILA, qui viene richiesto un controllo di consistenza tra gli agenti che partecipano alla computazione/dimostrazione.

Per semplicità, come accade nelle regole semantiche di LAILA (capitolo 1, paragrafo 1.4) si astrae dai dettagli di unificazione, che funziona in modo standard come in Logic Programming. Ricordiamo che l’unificazione è quel processo che determina se due espressioni possono essere rese identiche applicando ad esse opportune sostituzioni. Infatti una sostituzione Θ è un insieme finito della forma {v1/t1, …, vn/tn}, dove v1, …, vn sono n

variabili distinte e t1, …, tn sono termini diversi dalle vi. Una sostituzione opera su termini,

letterali oppure congiunzioni o disgiunzioni di letterali. Ricordiamo che l’unificazione è alla base della deduzione automatica e dell’uso dell’inferenza logica nell’intelligenza artificiale.

Definizione 4: regola per l’autodimostrazione (in LAILA tale operatore si chiama down-reflection). A |-abdδ G (4.1) --- A |-Aδ↓G A |-abd_δ{∆in} (4.2) --- A |-Aδ↓{∆in}

Nella regola (4.1) l’agente A dimostra, con la procedura di abduzione, G grazie alla sua base di conoscenza locale.

Come si può vedere sempre al paragrafo 1.4 del capitolo precedente, la seconda regola non compare nel linguaggio originale. In questa regola, l’insieme {∆in} è un insieme formato da

abducibili che l’agente A dimostra con la procedura di abduzione grazie alla propria base di conoscenza locale.

Definizione 5: regola per la comunicazione 1:1.

A1 |-Bδ1 ↓{∆in}, G , A0 ∪ B |- consδδ1

(5) --- A0 |- A0 ∪ BδA0 >V A1 ({∆in}, G)

Come già detto quando abbiamo presentato la sintassi, A0 è l’agente_mittente e A1 è quello

ricevente e inoltre A0≠ A1.

La consistenza è verticale: A0 è consistente con gli agenti appartenenti all’insieme B.

Inoltre l’insieme δ restituito come output contiene l’insieme ∆in, questo perché affinché gli

La differenza con la regola-LAILA è la presenza dell’insieme di abducibili ∆in passato dal

mittente al ricevente affinché venga da esso usato nella dimostrazione che gli viene richiesta.

Definizione 6: regole per la comunicazione collaborativa.

Le regole sono due, una per ogni tipo di consistenza.

Consistenza orizzontale:

A1 |-B1δ1 ↓{∆1-in}, G1 , A2 |-B2δ2 ↓{∆2-in}, G2 , …, An |-Bnδn ↓{∆n-in}, Gn ,

A0∪ B1∪…∪ Bn |-consδδ1 ∪…∪δn

(6.1) --- A0 |-A0∪Bδ A0 >O A1 ({∆1-in}, G1) & A2 ({∆2-in}, G2) & … & An ({∆n-in}, Gn)

E’ da notare che δi⊇∆i-in, per lo stesso motivo della regola precedente.

Consistenza orizzontale : tutti gli agenti coinvolti nella computazione sono consistenti tra loro e tutti sono consistenti con l’agente mittente A0 (nella regola sopra abbiamo quindi

A0 ∪ B1 ∪…∪ Bn |-consδδ1 ∪…∪δn). L’output restituito è δ.

E’ da ricordare che sia i Gi che i ∆i-in possono essere uguali o diversi e inoltre, che l’agente

mittente deve essere diverso dai riceventi mentre i riceventi possono essere sia uguali che diversi.

Consistenza verticale:

A1 |-B1δ1 ↓{∆1-in}, G1 , A2 |-B2δ2 ↓{∆2-in}, G2 , …, An |-Bnδn ↓{∆n-in}, Gn ,

A0 ∪ B1 |-consδ1’δ1 ,…, A0 ∪ Bn |-consδn’ δn , A0 |-consδ* δ1’ ∪ … ∪δn’

Consistenza verticale: ogni agente coinvolto nella computazione è consistente con l’agente mittente ma allo stesso tempo non sono consistenti tra loro, come mostra la regola:

(A0∪ B1 |-consδ1’δ1 ,…, A0∪ Bn |-consδn’ δn).

Come nella regola 6.1, sia i Gi che i ∆i-in possono essere uguali o diversi e inoltre, l’agente

mittente deve essere diverso dai riceventi mentre i riceventi possono essere sia uguali che diversi, e infine, come nelle precedenti regole, δi⊇∆i-in.

Rispetto a LAILA abbiamo due regole collaborative proprio perché abbiamo due tipi di consistenza tra gli agenti coinvolti nella computazione e in entrambe sono presenti gli insiemi ∆in.

Definizione 7: regola per la comunicazione competitiva.

Ricordiamo che con questo tipo di comunicazione è sufficiente che almeno uno dei riceventi riesca a portare a buon fine la sua dimostrazione affinché la comunicazione abbia successo.

A1 |-B1δ1 ↓{∆1-in}, G1, , A0∪ B1 |-consδδ1

(7.1) --- A0 |-A0∪B1δA0 >V A1 ({∆1-in}, G1) || A2 ({∆2-in}, G2) || … || An ({∆n-in}, Gn)

A2 |-B2δ2 ↓{∆2-in}, G2, , A0∪ B2 |-consδδ2

(7.2) --- A0 |-A0∪B2δA0 >V A1 ({∆1-in}, G1) || A2 ({∆2-in}, G2) || … || An ({∆n-in}, Gn)

… … …

An |-Bnδn ↓{∆n-in}, Gn, , A0∪ Bn |-consδδn

(7.n) --- A0 |-A0∪BnδA0 >V A1 ({∆1-in}, G1) || A2 ({∆2-in}, G2) || … || An ({∆n-in}, Gn)

La consistenza in questo caso è solo verticale: l’agente ricevente che dimostra il suo G deve essere consiste con l’agente mittente.

Come per le regole di comunicazione collaborativa, sia i Gi che i ∆i-in possono essere

uguali o diversi e inoltre, che l’agente mittente deve essere diverso dai riceventi mentre i riceventi possono essere sia uguali che diversi e che, come per tutte le regole precedenti, δi⊇∆i-in.

Come nelle regole precedenti, anche qui abbiamo l’introduzione degli insiemi ∆in, uno per ogni ricevente, che serviranno nelle singole dimostrazioni.

Definizione 8: regole di consistenza.

∀Ai∈ B Ai |-abdδδ (8.1) --- B |-consδδ ∀Ai∈ B Ai |-abdδiδ , δ ⊂∪Aj ∈ Bδj , B |-consδ1∪Ai ∈ Bδi (8.2) --- B |-consδ1δ

Nella regola 8.1 all’insieme di abducibili δ, per il quale tutti gli agenti coinvolti nella computazione (quindi appartenenti a B) devono essere consistenti, non vengono aggiunti nuovi abducibili.

Nella regola 8.2, dato un insieme di abducibili δ, per il quale tutti gli agenti appartenenti a B devono essere consistenti, possono essere aggiunti nuovi abducibili da uno o più agenti coinvolti e, ricorsivamente, si deve provare la consistenza per il nuovo insieme di abducibili fino a che non sarà più necessario aggiungerne di nuovi e quindi poter applicare la regola 8.1 e l’insieme restituito come output è δ1.