Gian Luca Pozzato
AgentSpeak (L)
& Jason
 AgentSpeak(L): linguaggio di programmazione per
agenti BDI introdotto da Rao nel 1996
 Si propone di colmare il gap tra specifica teorica ed
implementazione di un agente BDI
 Jason è la prima significativa implementazione di
AgentSpeak(L), realizzata in Java da Bordini e Hubner
AgentSpeak (L)
& Jason
 Gli agenti BDI vengono da sempre trattati da due punti
di vista:
- specifica teorica;
- implementazione.
 Il gap tra teoria e pratica resta eccessivo
 Causa principale: complessità del theorem proving e
del model checking delle logiche usate per formalizzare i
BDI agents
 Le implementazioni esistenti utilizzano strutture dati per
rappresentare Belief, Desires e Intentions, invece che gli
operatori modali
 [Rao96] introduce una formalizzazione alternativa degli
agenti BDI: AgentSpeak(L)
 AgentSpeak(L): architettura per agenti e linguaggio di
programmazione
 AgentSpeak(L) come estensione della programmazione
logica per supportare l’architettura BDI
IN QUESTA PRESENTAZIONE:
 Breve introduzione
 AgentSpeak(L): linguaggio e funzionamento
dell’interprete col sussidio di un esempio
 Proof theory di AgentSpeak(L)
 Jason
 Conclusioni e alcuni riferimenti utili
Introduzione
Agenti BDI:
 sistemi collocati in un ambiente dinamico, che muta nel
tempo;
 sistemi in grado di percepire informazioni provenienti
dall’ambiente;
 sistemi in grado di compiere delle azioni (ed apportare
modifiche all’ambiente) sulla base delle proprie attitudini
mentali: beliefs, desires e intentions sono le principali
attitudini.
Agente AgentSpeak(L)
Ambiente esterno
Percezione
Azione
Principali attitudini mentali di un agente BDI
 Belief
cattura
componente di informazione
 Desire
cattura
componente motivazionale
 Intention
cattura
componente decisionale
Aspetto teorico
Per formalizzare queste nozioni sono state impiegate
logiche multi-modali, temporali, dinamiche e action logics.
Tuttavia, la complessità del theorem proving e del modelchecking di tali logiche non è ancora chiara ([Rao95] e
[RaoGeo91]).
Aspetto pratico (I)
 Sono state proposte molte implementazioni di agenti BDI;
 tali implementazioni sono state impiegate con successo
in molti domini applicativi considerati critici;
 [BurSun92], [GeoLan86], [MulPisThi95] e [Sho93] sono
alcuni esempi;
 in questi sistemi, piani e programmi scritti dagli utenti
permettono di migliorare l’efficienza della computazione.
Aspetto pratico (II)
 Le implementazioni sono caratterizzate da assunzioni che
semplificano le definizioni di belief, desire e intention, in
modo da modellare tali attitudini con maggiore facilità;
 le basi teoriche che supportano tali sistemi sono deboli.
PROBLEMA: grosso gap tra teoria e pratica.
SOLUZIONE DI RAO:
AgentSpeak(L).
 Si parte da un sistema BDI implementato e si
formalizza la sua semantica operazionale;
 il sistema considerato è il PRS (Procedural Reasoning
System) e la sua evoluzione dMARS (Distributed MultiAgent Reasoning System);
 AgentSpeak(L) può essere visto come una versione
semplificata e testuale di PRS o dMARS (questi ultimi
offrono semplicemente più costrutti per facilitare la
programmazione di agenti, ma i linguaggi e le rispettive
semantiche operazionali sono simili nei loro dettagli
essenziali).
AgentSpeak(L)
 Linguaggio di programmazione basato su un linguaggio
del primordine semplificato, con eventi e azioni;
 il comportamento di un agente (ossia, le sue interazioni
con l’ambiente) è dettato dai programmi scritti in
AgentSpeak(L);
 beliefs, desires ed intentions NON sono rappresentati
esplicitamente con formule modali, bensì il progettista
attribuisce tali nozioni all’agente usando il linguaggio
AgentSpeak(L).
AgentSpeak(L)
 Current belief state dell’agente: modello di sé stesso,
dell’ambiente e degli altri agenti;
 Desires: stati che l’agente vuole raggiungere (sulla base
di stimoli interni o esterni); per la precisione, AgentSpeak(L)
fa riferimento ai Goals, che si possono intendere come
Desires adottati/scelti;
 Intentions: adozione di programmi per soddisfare certi
stimoli.
Il linguaggio
AgentSpeak(L)
 Linguaggio testuale per scrivere programmi per agenti
 Nozioni di base beliefs (analoghi ai fatti della
programmazione logica), piani, azioni, intentions, eventi,
goals
 Piani:
1. Context sensitive
2. Possono essere invocati dall’utente
3. Consentono una decomposizione gerarchica dei goals
4. Sintatticamente simili alle clausole della
programmazione logica (anche se con un diverso
comportamento)
Alfabeto del linguaggio formale
 Variabili
 Costanti
 Simboli funzionali
 Simboli predicativi
 Simboli di azione
 Connettivi
 Quantificatori
 Simboli di punteggiatura
Connettivi
 della logica del primordine:
- & (congiunzione Λ)
- not (negazione ¬)
- <- (implicazione ←)
 !
Achievement
?
Test
 ;
Sequenza
Definizioni della logica del primordine
 Termini
 Formule
 Le variabili del linguaggio sono caratterizzate dall’iniziale
maiuscola
Il linguaggio AgentSpeak(L)
Nozioni del
linguaggio
Belief atom
Def 1 [Belief atom] : sia b un simbolo predicativo e siano
t1, …, tn termini. Allora:
b(t1, …, tn)
è un belief atom e si scrive anche b(t).
 Un belief atom e la sua negazione sono detti belief literal
 Un belief atom ground (=senza variabili con occorrenze
libere) è detto base belief
Belief
Def 1b [Belief] : siano b(t) e c(s) belief atoms; allora
b(t) Λ c(s)
¬b(t)
sono beliefs.
 Istanze ground di beliefs si dicono base beliefs.
Esempio
Consideriamo la seguente simulazione di traffico urbano:




4 corsie adiacenti
Le corsie possono essere percorse da automobili
In ciascuna corsi può essere presente della spazzatura
Il robot deve raccogliere la spazzatura e depositarla nel
cestino, posizionato in una delle 4 corsie
 Mentre pulisce, il robot NON deve trovarsi in una corsia
in cui è presente un’auto, per evitare di essere distrutto
Vogliamo scrivere il programma per l’agente che guida il
robot nella sua attività.
Agente AgentSpeak(L)
Ambiente esterno
Percezione
Azione
a b c d
I beliefs rappresentano informazioni su:
 Configurazione delle corsie
 Posizionamento del robot
 Posizione delle auto nelle corsie
 Posizione del cestino per la raccolta dei rifiuti
Ad esempio:
adjacent(X,Y)
location(robot,X)
location(car,X)
I base beliefs (=istanze ground di belief atoms) sono,
ad esempio:
adjacent(a,b)
location(robot,c)
Goal
 E’ uno stato del sistema che l’agente vuole raggiungere
 2 tipi di goal:
1. Achievement goal
2. Test goal
Achievement goal:
 Della forma:
!g(t)
 L’agente vuole raggiungere uno stato in cui g(t) è un
belief VERO
Test goal:
 Della forma:
?g(t)
 L’agente vuole verificare se la formula g(t) è un belief
VERO o FALSO
Goal
Def 2 [Goal] : sia g un simbolo predicativo e siano t1, …, tn
termini. Allora:
!g(t1, …, tn)
( oppure !g(t) )
è un achievement goal;
?g(t1, …, tn)
è un test goal.
( oppure ?g(t) )
Goal
Esempio:
!cleared(b) : l’agente vuole pulire la corsia b
?location(car,b) : l’agente vuole verificare l’eventuale
presenza di un’auto nella corsia b
Triggering event
 Quando un agente acquisisce un nuovo goal oppure
nota una modifica nell’ambiente, esso può far scattare
aggiunte o cancellazioni di goals o beliefs
 Questi eventi vengono detti triggering events
 Possibili triggering events:
1. Aggiunta di un belief
2. Aggiunta di un goal
3. Rimozione di un belief
4. Rimozione di un goal
Triggering event
 L’aggiunta di un belief/goal è rappresentata
dall’operatore +
 La rimozione di un belief/goal è rappresentata
dall’operatore –
Esempi di triggering events:
 Notare la presenza di spazzatura nella corsia X è
denotato con il triggering event:
+location(waste, X)
 Acquisire il goal di ripulire una certa corsia è denotato
con il triggering event:
+!cleared(X)
Triggering event
Def 3 [Triggering event] : sia b(t) un belief atom e siano
!g(t) e ?g(t) goals. Allora:
1. +b(t)
2. -b(t)
3. +!g(t)
4. -!g(t)
5. +?g(t)
6. -?g(t)
sono triggering events.
Azione
Scopo di un agente:
Osservare l’ambiente e, sulla base di tali osservazioni
e dei propri goals, eseguire determinate azioni
Le azioni compiute dall’agente possono modificare lo
stato dell’ambiente
Azione
Esempio:
Se move è un simbolo di azione,
move(X,Y)
è un’azione e rappresenta lo spostamento del robot da X
a Y e ha l’effetto di modificare lo stato dell’ambiente. Il
robot si trova nella corsia Y e non più nella corsia X
Azione
Def 4 [Azione] : sia a un simbolo di azione e siano t1,…, tn
termini. Allora
a(t1,…, tn)
è un’azione.
Piano
 Un piano specifica il modo in cui un agente potrebbe
raggiungere un determinato obiettivo
<piano>:= <head> ← <body>
<head>:= <triggering event> : <context>
 triggering event specifica perché il piano è stato
attivato, ossia l’aggiunta/rimozione di un belief o di un
goal che tale piano si propone di gestire
 context specifica quali beliefs dovrebbero essere
soddisfatti nel set delle credenze dell’agente quando il
piano è attivato (scatta)
Piano
<piano>:= <head> ← <body>
<head>:= <triggering event> : <context>
 body è una sequenza di goals o azioni e specifica:
1. i goals che l’agente vuole raggiungere (achievement
goals) o testare (test goals);
2. le azioni che l’agente deve eseguire
 true rappresenta un componente vuoto (context o body)
Piano
Esempio: piano che scatta quando la spazzatura si viene a
trovare in una certa corsia; se il robot si trova in tale
corsia:
1. Raccoglie la spazzatura;
2. Si pone l’obiettivo (achievement goal) di raggiungere il
cestino;
3. Getta via la spazzatura.
Piano
Un possibile piano (P1):
+location(waste, X): location(robot,X) &
location(bin,Y)
<- pick(waste);
!location(robot, Y);
drop(waste).
Piano
Esempio: piano per consentire al robot di spostarsi fra le
corsie. Il robot ha l’obiettivo di raggiungere la corsia X,
senza dover fare altre operazioni. Se non si trova nella
corsia X, il robot deve individuare una corsia Z che sia:
1. Adiacente alla corsia in cui si trova attualmente
2. Non percorsa da auto
quindi, deve spostarsi in tale corsia.
Piano
Piano (P2):
+!location(robot,X):
location(robot,X) <- true.
Piano (P3):
+!location(robot,X): location(robot,Y) &
(not (X = Y)) &
adjacent(Y,Z) &
(not (location(car,Z)))
<- move(Y,Z);
+!location(robot,X).
Piano
Def 5 [Piano] : siano:
• e un triggering event;
• b1,…,bm belief literals;
• h1,…,hn goals o azioni
allora
e: b1 Λ … Λ bm ← h1; … ; hn
è un piano.
La parte a sinistra di ← è detta head, la parte a destra è
detta body. La parte a destra dei : nella head è detta
context. Un body vuoto viene riscritto per convenzione
con true.
Progetto di un agente
 Le nozioni introdotte finora completano la specifica di un
agente;
 Il progettista specifica un agente scrivendo:
1. Un insieme di base beliefs;
2. Un insieme di piani.
 Il progetto di un agente è, pertanto, del tutto simile alla
scrittura di un programma logico, con la definizione di:
1. Un insieme di fatti;
2. Un insieme di regole.
Tuttavia, ci sono delle differenze…
Programmazione logica vs progetto di un
agente in AgentSpeak(L)
 Regole vs Piani: nella programmazione logica pura non
c’è differenza tra un goal nel body o nella head di una
regola. In AgentSpeak(L), invece, la head è un triggering
event, e non un goal.
Ciò consente un’ invocazione dei piani più “espressiva”,
in quanto sono entrambe permesse:
1. Invocazione data-directed (mediante
l’aggiunta/rimozione di beliefs);
2. Invocazione goal-directed (mediante
l’aggiunta/rimozione di goals);
Programmazione logica vs progetto di un
agente in AgentSpeak(L) (2)
 Le regole non sono context-sensitive come i piani;
 Le regole eseguite con successo ritornano un binding per
le variabili non istanziate; invece, l’esecuzione di piani
genera una sequenza di azioni ground che modificano
l’ambiente;
 La prova (dimostrazione) di un goal non può essere
interrotta, mentre i piani di un programma per agenti
possono essere interrotti.
Il linguaggio AgentSpeak(L)
La semantica
operazionale
 A run-time un agente può essere visto come costituito da:
1. Un set di beliefs B;
2. Un set di piani P;
3. Un set di intentions I;
4. Un set di eventi E;
5. Un set di azioni A;
6. Un set di funzioni di selezione: Sε, SO, SI
 Descriviamo informalmente il funzionamento di un agente
AgentSpeak(L)…
Agente AgentSpeak(L)
Ambiente esterno
Percezione
Azione
a b c d
Interni
o
Esterni
Eventi
<+location(robot,b),i>
Piani
+!location(robot,X):
location(robot,X)<true.
Achievement goal
Evento
selezionato
+!goal
-!goal
+belief
-belief
Sε
a
Belief base
location(robot,b).
adjacent(a,b).
Unifica
evento
Azione
c
d
Belief
Revision
Function
Piani
rilevanti
Unifica
contesto
Esecuzione
intention
b
Piani
applicabili
Test goal
true
SI
Intentions
Evento interno: Intended
means
push
Evento esterno:
nuova intention
SO
 Viene generato un triggering event quando un agente
nota una modifica nell’ambiente circostante oppure
quando un utente esterno chiede all’agente di
raggiungere un goal
 Gli eventi possono essere:
1. Esterni (modifica dell’ambiente)
2. Interni (modifica dello stato dell’agente)
 Gli eventi vengono aggiunti al set E
 Sε seleziona in E un evento E0 da processare
 E0 viene rimosso da E e viene usato per unificare con i
triggering events dei piani del set P
 I piani i cui triggering events unificano con E0 sono detti
piani rilevanti; l’unificatore è detto unificatore rilevante
 L’unificatore rilevante è applicato al contesto dei piani
rilevanti
 Una correct answer substitution è ottenuta dal contesto
 Per alcuni piani le condizioni dei contesti risultano essere
conseguenze logiche del set dei base beliefs B: questi
piani sono detti piani applicabili mediante un unificatore
applicabile
 L’unificatore applicabile risulta dalla composizione della
correct answer substitution con l’unificatore rilevante
 Dato un evento E0, diversi piani/opzioni risultano
applicabili
 La funzione di selezione SO sceglie uno di questi
piani/opzioni che chiamiamo Po
 Applicando l’unificatore applicabile a Po si ottiene
l’intended means in risposta al triggering event
 Ogni intention è uno stack di piani parzialmente istanziati
o intention frames
 Evento esterno: l’intended means è usato per creare una
NUOVA INTENTION, che viene aggiunta al set I
 Evento interno: l’intended means è inserito in cima
all’intention ESISTENTE che ha “fatto scattare” (triggered)
l’evento interno (per raggiungere un goal)
 La funzione di selezione SI sceglie una intention da
eseguire
 Quando l’agente esegue una intention, esegue il primo
goal o azione del body del top del’intention:
 Eseguire un achievement goal equivale a generare un
evento interno per aggiungere il goal alla corrente
intention;
 Eseguire un test goal equivale a trovare una
sostituzione per il goal che lo renda una conseguenza
logica dei base beliefs; se viene trovata una
sostituzione, il test goal è rimosso dal corpo del top
dell’intention;
 Eseguire un’azione equivale ad aggiungerla al set di
azioni A e rimuoverla dal corpo del top dell’intention.
 A questo punto, l’agente torna a valutare il set degli eventi
E; il ciclo ricomincia, fino a quando:
1. il set degli eventi E è vuoto
oppure
2. Non è possibile eseguire altre intentions.
 Formalizziamo il tutto…
Stato di un agente
in ogni istante di tempo
Def 6 [Stato dell’agente] : un agente è definito come una
tupla:
< E,B,P,I,A,Sε,SO,SI >
dove:
•
•
•
•
•
E è un set di eventi
B è un set di base beliefs
P è un set di piani
I è un set di intentions
…
Stato di un agente
in ogni istante di tempo
Def 6 [Stato dell’agente] : un agente è definito come una
tupla:
< E,B,P,I,A,Sε,SO,SI >
•
•
•
•
…
A è un set di azioni
Sε seleziona un evento da E
SO seleziona un’opzione/piano applicabile (vedi Def 10
in seguito) da un set di piani applicabili
• SI seleziona una intention dal set I
Intention
Def 7 [Intention] : I è il set delle intentions; ogni intention è
uno stack di piani parzialmente istanziati, ossia piani
dove alcune variabili sono state istanziate.
Un’intention è denotata con uno stack:
[ p1 ‡ p2 ‡ … ‡ pz ]
bottom
top
stack
Intention
 Una particolare intention è la true intention
 True intention:
[ +!true: true <- true ]
 Per comodità, la denoteremo con T
Evento
Def 8 [Evento] : il set E è il set degli eventi. Ogni evento è
una coppia:
< e, i >
dove:
• e è un triggering event
• i è una intention
Se i è la true intention T, l’evento è un evento esterno,
altrimenti si dice evento interno.
Ancora sul piano
 Scelto un evento < d, i > dal set E, il triggering event d
viene unificato con i triggering event di tutti i piani
contenuti nel set P
 Il most general unifier (mgu) che unifica i due eventi è
detto relevant unifier
 L’intention i può essere:
1. La true intention T
2. Un’intention esistente che ha generato l’evento
Piano rilevante
Def 9 [Piano rilevante] : sia
Sε (E) = Є = < d, i >
e sia p definito come e : b1 Λ … Λ bm ← h1; …; hn.
p si definisce un piano rilevante rispetto all’evento Є se e
solo se esiste un mgu σ tale che
dσ=eσ
σ è detto unificatore rilevante per Є.
Piano rilevante
 Torniamo all’esempio del traffico
 Supponiamo che il triggering event d di Є (ossia l’evento
scelto in E dalla funzione di selezione) sia:
+!location(robot,b).
 Ripresentiamo i piani introdotti in precedenza per il nostro
agente
(P1)
+location(waste, X): location(robot,X) &
location(bin,Y)
<- pick(waste);
!location(robot, Y);
drop(waste).
(P2)
+!location(robot,X):
location(robot,X) <- true
(P3)
+!location(robot,X): location(robot,Y) &
(not (X = Y)) &
adjacent(Y,Z) &
(not (location(car,Z)))
<- move(Y,Z);
+!location(robot,X).
Piano rilevante
 I piani P2 e P3 sono rilevanti
(P2)
+!location(robot,X):
location(robot,X) <- true
(P3)
+!location(robot,X): location(robot,Y) &
(not (X = Y)) &
adjacent(Y,Z) &
(not (location(car,Z)))
<- move(Y,Z);
+!location(robot,X).
 L’unificatore rilevante è:
σ = { X/b }
Piano applicabile
 Un piano rilevante è anche applicabile se esiste una
sostituzione che, composta con l’unificatore rilevante ed
applicata al contesto, fa sì che quest’ultimo risulti una
conseguenza logica dei base beliefs B
 In altre parole, la condizione del contesto di un piano
rilevante DEVE essere conseguenza logica di B affinchè il
piano sia applicabile
Piano applicabile
Def 10 [Piano applicabile] : sia p il piano
e: b1 Λ … Λ bm ← h1; …; hn
p è un piano applicabile rispetto ad un evento Є se e solo
se:
1. Esiste un unificatore rilevante  per Є (ossia, p è
rilevante per Є)
2. Esiste una sostituzione  tale che (b1 Λ … Λ bm)   è
una conseguenza logica di B.
La composizione   si dice unificatore applicabile per Є e
 è la correct answer substitution.
Piano applicabile
 Vediamo ancora l’esempio del traffico
 Supponiamo che i base beliefs del nostro agente siano:
adjacent(a,b).
adjacent(b,c).
adjacent(c,d).
location(robot,a).
location(waste,b).
location(bin,d).
 Il piano P3 è il solo applicabile mediante il seguente
unificatore applicabile:
  ={X/b, Y/a, Z/b}
a b c d
adjacent(a,b).
adjacent(b,c).
adjacent(c,d).
location(robot,a).
location(waste,b).
location(bin,d).
(P3)
+!location(robot,X): location(robot,Y) &
(not (X = Y)) &
adjacent(Y,Z) &
(not (location(car,Z)))
<- move(Y,Z);
+!location(robot,X).
Unificatore applicabile:   ={X/b, Y/a, Z/b}
Intended means
 Come detto, la funzione Sε seleziona un evento < d, i >
 La natura di i determina il tipo di evento
 A seconda del tipo di evento (interno o esterno), l’agente
esegue un opportuno intended means
Intended means:
evento ESTERNO
L’intended means è ottenuto selezionando un piano
applicabile per l’evento
 Si applica l’unificatore applicabile al body del piano
 L’intended means è utilizzato per creare una nuova
intention che viene aggiunta al set I
 Vediamo la definizione formale…
Intended plan: evento ESTERNO
Def 11 [Intended plan – evento ESTERNO] : sia SO (OЄ)=p,
dove OЄ è il set di tutti i piani applicabili per l’evento
Є=< d, i > e p è:
e: b1 Λ … Λ bm ← h1; …; hn
Il piano p è un intended plan rispetto a Є, dove i è T (true
intention) se e solo se esiste un unificatore applicabile
 tale che:
[ +!true: true ← true ‡ (e: b1 Λ … Λ bm ← h1; …; hn) ]  I
Intended plan: evento ESTERNO
Proseguiamo l’esempio
Il piano applicabile P3 è un intended plan: il set I diventa:
[ +!location(robot,b): location(robot,a) &
(not (b = a)) &
adjacent(a,b) &
(not (location(car,b)))
<- move(a,b);
+!location(robot,b) ]
Intended means:
evento INTERNO
L’intended means per l’achievement goal è posto (push)
sul top del’intention esistente che ha generato (triggered)
l’evento interno
 Vediamo la definizione formale…
Intended plan: evento INTERNO
Def 12 [Intended plan – evento INTERNO] : sia SO (OЄ)=p,
dove OЄ è il set di tutti i piani applicabili per l’evento
Є=< d, i > dove i è:
[ p1 ‡ … ‡ f :c1 Λ ... Λ cy ← !g(t);h2;…;hn ]
e p è:
+!g(s): b1 Λ … Λ bm ← k1; …; kj
Il piano p è un intended plan rispetto a Є se e solo se
esiste un unificatore applicabile  tale che:
[ p1 ‡ … ‡ f :c1 Λ ... Λ cy ← !g(t); h2;…; hn ‡
(+!g(s): b1 Λ … Λ bm) ← (k1; …; kj); (h2;…;hn) ]  I
Esecuzione di intentions
 La funzione SI seleziona un’intention da eseguire
 La prima formula nel body del top dell’intention può
essere:
a) Un achievement goal
b) Un test goal
c) Un’azione
d)True
 Vediamo, in ciascuno dei casi, cosa fa il nostro agente:
sia:
SI(I)=i
Esecuzione di intentions
a) Achievement goal: il sistema esegue l’achievement goal
generando un evento. Formalmente:
i è [ p1‡…‡ f : c1 Λ … Λ cy ← !g(t);h2;…;hn ]
L’intention i si dice eseguita se e solo se
< +!g(t), i >  E
Esecuzione di intentions
b) Test goal: il sistema cerca un mgu che unifichi il goal con
il set B e, se esiste, lo applica al resto dell’intended
means. Formalmente:
i è [ p1‡…‡ f : c1 Λ … Λ cy ← ?g(t);h2;…;hn ]
L’intention i si dice eseguita se e solo se esiste una
sostituzione  tale che:
- g(t) è conseguenza logica di B;
- i è rimpiazzato (in I) dall’intention:
[ p1‡…‡ (f : c1 Λ … Λ cy) ← h2 ;…; hn ]
Esecuzione di intentions
c) Azione: il sistema aggiunge l’azione al set di azioni A.
Formalmente:
i è [ p1‡…‡ f : c1 Λ … Λ cy ← a(t);h2;…;hn ]
L’intention i si dice eseguita se e solo se:
- a(t)  A;
- i è rimpiazzato (in I) dall’intention:
[ p1‡…‡ f : c1 Λ … Λ cy ← h2 ;…; hn ]
Esecuzione di intentions
d) True: il top dell’intention e l’achievement goal soddisfatto
vengono rimossi e la sostituzione è applicata al resto del
body dell’intention. Formalmente:
i è [ p1‡…‡ pz-1 ‡ !g(t) : c1 Λ … Λ cy ← true ]
dove pz-1 è e: b1 Λ … Λ bx ← !g(s); h2;…; hn. L’intention i si
dice eseguita se e solo se:
- esiste una sostituzione  tale che g(t) =g(s) ;
- i è rimpiazzato (in I) dall’intention:
[ p1‡…‡ pz-2 ‡ (e : b1 Λ … Λ bx) ← (h2 ;…; hn) ]
<+!location(robot,b),T>
[ +!location(robot,b):
location(robot,a) &
(not (b = a)) &
adjacent(a,b) &
(not (location(car,b)))
<- move(a,b);
!location(robot,b) ].
(P2) +!location(robot,X):location(robot,X)
<- true
Sε
(P3) +!location(robot,X):location(robot,Y)
& (not (X = Y)) & adjacent(Y,Z) &
(not (location(car,Z)))
<- move(Y,Z); !location(robot,X).
a
(P1) +location(waste,X): location(robot,X)
& location(bin,Y) <- pick(waste);
!location(robot, Y); drop(waste).
adjacent(a,b).
adjacent(b,c).
adjacent(c,d).
location(robot,a).
location(waste,b).
location(bin,d).
SI
b
c
<+!location(robot,b),T>
Unifica
evento
P2 e P3 rilevanti con {X/b}
Esecuzione
intention
[ +!location(robot,b):location(robot,a)
& (not (b = a)) & adjacent(a,b) &
(not (location(car,b)))
<- move(a,b); !location(robot,b)].
Unifica
contesto
P3 applicabile con
{X/b,Y/a,Z/b}
P3
SO
d
<+location(robot,b),T>
(P2) +!location(robot,X):location(robot,X)
<- true
Sε
(P3) +!location(robot,X):location(robot,Y)
& (not (X = Y)) & adjacent(Y,Z) &
(not (location(car,Z)))
<- move(Y,Z); !location(robot,X).
a
(P1) +location(waste,X): location(robot,X)
& location(bin,Y) <- pick(waste);
!location(robot, Y); drop(waste).
adjacent(a,b).
adjacent(b,c).
adjacent(c,d).
location(robot,b).
location(waste,b).
location(bin,d).
SI
b
c
<+!location(robot,b),T>
Unifica
evento
P2 e P3 rilevanti con {X/b}
Esecuzione
intention
[ +!location(robot,b):location(robot,a)
& (not (b = a)) & adjacent(a,b) &
(not (location(car,b)))
<- !location(robot,b)].
Unifica
contesto
P3 applicabile con
{X/b,Y/a,Z/b}
P3
SO
d
<+location(robot,b),T>
<+!location(robot,b),
>
(P2) +!location(robot,X):location(robot,X)
<- true
Sε
(P3) +!location(robot,X):location(robot,Y)
& (not (X = Y)) & adjacent(Y,Z) &
(not (location(car,Z)))
<- move(Y,Z); !location(robot,X).
a
(P1) +location(waste,X): location(robot,X)
& location(bin,Y) <- pick(waste);
!location(robot, Y); drop(waste).
adjacent(a,b).
adjacent(b,c).
adjacent(c,d).
location(robot,b).
location(waste,b).
location(bin,d).
SI
b
c
<+location(robot,b),T>
Unifica
evento
Nessun piano rilevante
Esecuzione
intention
[ +!location(robot,b):location(robot,a)
& (not (b = a)) & adjacent(a,b) &
(not (location(car,b)))
<- !location(robot,b)].
Unifica
contesto
Nessun piano
applicabile
-
SO
d
<+!location(robot,b),
>
(P2) +!location(robot,X):location(robot,X)
<- true
Sε
(P3) +!location(robot,X):location(robot,Y)
& (not (X = Y)) & adjacent(Y,Z) &
(not (location(car,Z)))
<- move(Y,Z); !location(robot,X).
a
(P1) +location(waste,X): location(robot,X)
& location(bin,Y) <- pick(waste);
!location(robot, Y); drop(waste).
adjacent(a,b).
adjacent(b,c).
adjacent(c,d).
location(robot,b).
location(waste,b).
location(bin,d).
SI
<+!location(robot,b),
b
c
>
Unifica
evento
P2 e P3 rilevanti con {X/b}
Esecuzione
intention
[ +!location(robot,b):location(robot,a)
& (not (b = a)) & adjacent(a,b) &
(not (location(car,b)))
<- !location(robot,b)‡
+!location(robot,b):location(robot,b)<-true].
Unifica
contesto
P2 applicabile
con {X/b}
P2
SO
d
(P2) +!location(robot,X):location(robot,X)
<- true
Sε
(P3) +!location(robot,X):location(robot,Y)
& (not (X = Y)) & adjacent(Y,Z) &
(not (location(car,Z)))
<- move(Y,Z); !location(robot,X).
a
(P1) +location(waste,X): location(robot,X)
& location(bin,Y) <- pick(waste);
!location(robot, Y); drop(waste).
adjacent(a,b).
adjacent(b,c).
adjacent(c,d).
location(robot,b).
location(waste,b).
location(bin,d).
SI
<+!location(robot,b),
b
c
>
Unifica
evento
P2 e P3 rilevanti con {X/b}
Esecuzione
intention
[ +!location(robot,b):location(robot,a)
& (not (b = a)) & adjacent(a,b) &
(not (location(car,b)))
<- !location(robot,b)].
Unifica
contesto
P2 applicabile
con {X/b}
P2
SO
d
(P2) +!location(robot,X):location(robot,X)
<- true
Sε
(P3) +!location(robot,X):location(robot,Y)
& (not (X = Y)) & adjacent(Y,Z) &
(not (location(car,Z)))
<- move(Y,Z); !location(robot,X).
a
(P1) +location(waste,X): location(robot,X)
& location(bin,Y) <- pick(waste);
!location(robot, Y); drop(waste).
adjacent(a,b).
adjacent(b,c).
adjacent(c,d).
location(robot,b).
location(waste,b).
location(bin,d).
SI
<+!location(robot,b),
b
c
>
Unifica
evento
P2 e P3 rilevanti con {X/b}
Esecuzione
intention
[ +!location(robot,b):location(robot,a)
& (not (b = a)) & adjacent(a,b) &
(not (location(car,b)))
<-true].
Unifica
contesto
P2 applicabile
con {X/b}
P2
SO
d
Ancora l’esempio
 Alla successiva iterazione del ciclo dell’agente, dopo che
il robot si muove dalla corsia a alla corsia b, l’ambiente
invia all’agente un evento di belief update per modificare
la locazione del robot (che ora si troverà in b); in
sostanza:
- location(robot,b) viene aggiunto a B;
- l’evento +location(robot,b) viene aggiunto ad E.
 A questo punto, non vi sono piani rilevanti; il sistema
sceglie, pertanto, di ESEGUIRE l’intention mostrata nella
slide precedente.
Ancora l’esempio
 L’esecuzione dell’intention (caso a) porta ad aggiungere
un evento al set E che diventa:
{ < +!location(robot,b), i > }
dove i è l’intention considerata:
[ +!location(robot,b): location(robot,a) &
(not (b = a)) &
adjacent(a,b) &
(not (location(car,b)))
<- +!location(robot,b) ]
Ancora l’esempio
adjacent(a,b).
adjacent(b,c).
adjacent(c,d).
location(robot,b).
location(waste,b).
location(bin,d).
 A questo punto, il piano P2
+!location(robot,X):location(robot,X) <- true
risulta applicabile con l’unificatore applicabile  = { X/b }
Ancora l’esempio
 Il corpo del piano è true; pertanto, l’intention è
soddisfatta ed il set E è vuoto
 L’esecuzione dell’agente è sospesa e riprenderà nel
momento in cui un nuovo evento verrà aggiunto
all’insieme E
Proof theory
Proof theory
 Fornita come un sistema di transizione con etichette
 Le regole del metodo di prova definiscono la
transizione dell’agente da una configurazione alla
successiva
 Le transizioni fra configurazioni sono in relazione
diretta con la semantica operazionale del linguaggio
 Corrispondenza tra l’interprete AgentSpeak(L) e la
proof theory
Sistema di transizione BDI
 E’ una coppia
<
,
>
dove:
-
è un set di configurazioni BDI;
è una relazione di transizione binaria:

Configurazione BDI
 E’ una tupla:
<Ei, Bi, Ii, Ai, i>
dove:
-
Ei  E
Bi  B
Ii  I
Ai  A
i è la label della transizione
 L’insieme dei piani P è omesso in quanto costante
Regole di transizione
 Rao definisce delle regole di transizione che
definiscono il passaggio di un agente da una
configurazione alla successiva
Esempio: regola IntendEnd, che mostra la transizione per
la scelta di un piano al top level (come muta l’insieme I
dell’agente per la gestione di un evento esterno):
(IntendEnd)
< {…,<+!g(t),T>,…},Bi,Ii,Ai,i >
< {…},Bi, Ii  { [ pσ ] } ,Ai,i+1 >
Regole di transizione
(IntendEnd)
< {…,<+!g(t),T>,…},Bi,Ii,Ai,i >
< {…},Bi, Ii  { [ pσ ] } ,Ai,i+1 >
 p è +!g(s): b1 Λ … Λ bm ← h1; …; hn  P
 Sε(E)=<+!g(t),T>
 g(t)σ=g(s)σ
 (b1 Λ … Λ bm) è conseguenza logica di Bi
Derivazioni e refutazioni BDI
 Ci sono regole per l’esecuzione delle intentions, per la
gestione di eventi interni, ecc.
 Con queste regole è possibile definire formalmente
derivazioni e refutazioni
 Una derivazione BDI è una sequenza finita o infinita di
configurazioni BDI 0, …, i, …
 Refutazione di intention: la refutazione inizia con la
scelta di un’intention e si conclude quando lo stack di
tale intention è vuoto
 Con tale refutazione BDI è possibile dimostrare alcune
proprietà del comportamento di un agente [RaoGeo93]
Derivazioni e refutazioni BDI
 Corrispondenza uno-a-uno tra le regole di prova e la
semantica operazionale
 Rao indica la possibilità di estendere la semantica
operazionale e le regole di prova ad altri eventi interni,
tipo successo o fallimento di piani, azioni, goals e
intentions
 Il body dei piani considerati da Rao include
esclusivamente sequenze di goals o azioni, ma
sarebbe opportuno consentire operatori quali:
- or non deterministico
- aggiunta/rimozione di beliefs
- iterazioni
- operatori paralleli
Implementazioni di
AgentSpeak(L)
Jason
Jason
 Java-based agentSpeak interpreter used with saci for
multi-agent distribution over the net
 E’ la prima implementazione significativa di
AgentSpeak(L), dovuta a Bordini e Hubner
 Implementato in Java
 Disponibile OpenSource
 Impiegando SACI, un’infrastruttura per la comunicazione
fra agenti, è possibile distribuire un sistema multi-agente
sulla rete
Jason
 Interpreta il linguaggio AgentSpeak(L) originale
 Aggiunge alcune importanti caratteristiche:
 Gestione del fallimento dei piani
 Annotazioni sulle labels dei piani, utilizzate per definire
opportune funzioni di selezione
 Supporto per lo sviluppo di ambienti da programmare in
Java
 Possibilità di eseguire un ambiente multi-agente
utilizzando SACI
…
Jason
 …
 Possibilità di personalizzare (in Java) funzioni di
selezione, di belief-revision, di azione, di
comunicazione fra agenti
 Libreria di “azioni interne” di base
 Possibilità di aggiungere “azioni interne” definite in
Java dall’utente
 Aggiunta della negazione forte
Jason
 Costruire un agente AgentSpeak(L) con Jason è molto
semplice
 E’ sufficiente:
1. Inserire il nome dell’agente nel file di configurazione
2. Creare un file .asl contenente i piani che descrivono il
comportamento dell’agente
Jason: differenze con AgentSpeak(L)
 Come accennato in precedenza, Jason presenta una
serie di differenze rispetto al linguaggio
AgentSpeak(L) originale ([Rao])
 Illustriamo le principali differenze…
Jason: differenze con AgentSpeak(L)
Possibile uso della negazione forte
 La negazione debole è usata nel contesto dei piani
come in AgentSpeak(L), introdotta dal not
Es.: not location(car,Y).
 La negazione forte è usata per negare un
predicato/fatto:
Es: ~location(waste,b).
Jason: differenze con AgentSpeak(L)
Termini
 Possono essere:
1. Atomi
2. Strutture
3. Variabili
4. Liste (tipo Prolog)
5. Numeri (interi o floating point)
6. Stringhe (tra “”)
Jason: differenze con AgentSpeak(L)
Predicati (atomi) annotati
 Possibilità di specificare annotazioni ai predicati nella base
belief, per esempio per conservare l’origine di tale
informazione
 Annotazione: lista di termini tra parentesi quadre associata
ad un predicato
 Due annotazioni particolari:
1.[percept]: l’informazione è stata percepita
dall’ambiente;
2.[self]: l’informazione è stata aggiunta dall’agente
stesso durante l’esecuzione di un piano
Jason: differenze con AgentSpeak(L)
Piani con labels
 E’ possibile associare una label a ciascun piano
 La label può essere un qualsiasi predicato
(consigliata arietà zero), quindi anche un predicato
con annotazione
 Utili per personalizzare le funzioni di selezione
Jason: differenze con AgentSpeak(L)
Gestione del fallimento dei piani
 Sono previsti eventi per la gestione del fallimento dei
piani
 Tale evento è generato se un’azione fallisce o non vi
sono piani applicabili per un evento con aggiunta di
un goal +!g
 In tali situazioni viene generato un evento interno per
-!g associato alla stessa intention. Se il
programmatore ha previsto un piano per -!g e questo
risulta applicabile, verrà eseguito. Altrimenti, viene
eliminata l’intera intention e segnalato un warning
Jason: differenze con AgentSpeak(L)
Azioni interne
 Possono essere usate sia nel contesto che nel body
di un piano
 Introdotte dal punto:
Es: .send(…)
 Sono azioni interne, distinte dalle azioni che l’agente
compie sull’ambiente mediante gli attuatori
 Azioni interne standard (directory src/stdlib) e
definite dall’utente in Java
Jason: differenze con AgentSpeak(L)
Esempi di azioni interne standard:
.send(receiver,illocutionary_force,
propositional_content)
Usata nella comunicazione tra agenti. Receiver è il
nome del destinatario del messaggio;
illocutionary_force descrive il tipo di
messaggio (es. tell, achieve);
propositional_content è un predicato che
rappresenta l’informazione trasmessa.
Jason: differenze con AgentSpeak(L)
Esempi di azioni interne standard:
.print(…)
Scrive messaggi sulla console su cui l’agente o SACI è
in esecuzione. Ha un numero qualsiasi di parametri,
che possono essere stringhe così come termini
AgentSpeak(L).
Jason
Sistemi
multi-agente
Jason: sistemi multi-agente
 L’utente può definire un sistema di multipli agenti
AgentSpeak(L)
 Un sistema multi-agente prevede:
1. un ambiente in cui gli agenti AgentSpeak(L)
vengono collocati, programmato in Java
2. Un set di istanze di agenti AgentSpeak(L)
 La configurazione dell’intero sistema multi-agente è
data da un semplice file di testo
Jason: sistemi multi-agente
 File di configurazione di un sistema multi-agente: file
con estensione
.mas2j
 Nel file vengono indicati il nome attribuito alla società
di agenti, gli agenti AgentSpeak(L) che ne fanno
parte, l’ambiente in cui si collocano tali agenti (=la
classe Java, eventualmente ridefinita dall’utente, per
programmare l’ambiente)
 Jason offre una serie di script e un’interfaccia grafica
che rendono immediate ed intuitive la compilazione e
l’esecuzione di un sistema multi-agente
Jason
Personalizzazione
Jason: personalizzazione
 Jason consente di personalizzare:
1. Alcuni elementi di base di un agente, tipo le
funzioni di selezione;
2. I meccanismi di percezione, di azione, di
comunicazione tra agenti e la belief revision
function;
3. Le azioni interne;
4. L’ambiente in cui collocare un sistema multiagente.
 Vediamo brevemente come fare…
Jason: personalizzazione
Personalizzare un agente
 Jason offre la possibilità di modificare il codice di
funzioni quali:
1.selectEvent
2.selectOption
3.selectIntention
 Il programmatore deve semplicemente definire una
classe Java che estende la classe Agent, ridefinendo
opportunamente i metodi da personalizzare
 Infine, basta segnalare il cambiamento nel file .mas2j
Jason: personalizzazione
Personalizzare un agente
 Esempio: ridefiniamo la funzione Sε:
import jason.*;
import java.util.*;
public class MyAgent extends Agent{
public Event selectEvent(List evList){
System.out.println(“Selezione di un evento”);
return((Event)evList.remove(0));
}
}
 E’ sufficiente specificare agentClass MyAgent nella
entry del dato agente nel file di configurazione .mas2j
Jason: personalizzazione
Personalizzare l’architettura
 L’utente può creare l’architettura per l’agente, ossia è
possibile modificare i metodi:
1.perceive
2.checkMail
3.brf
4.act
 Il codice di default è presente nelle classi
SaciAgArch.java e CentralisedArch.java nella
directory src/jason
Jason: personalizzazione
Personalizzare l’architettura
 Esempio: ridefiniamo il meccanismo di percezione:
import jason.*;
public class MyAgArchitecture extends CentralisedAgArch{
public void perceive (){
/* per esempio, simulare un fallimento nella
percezione modificando le liste “percepts” e
“negPercepts” */
System.out.println(“Fase di percezione in corso”);
super.perceive();
}
}
 Specificare agentArchClass MyAgArchitecture
nella entry dell’agente nel file .mas2j
Jason: personalizzazione
Personalizzare le azioni interne
 Come detto, le azioni interne standard si trovano nella
directory src/stdlib
 Le azioni interne definite dall’utente in Java possono
essere collocate in una directory predefinita ulib,
eventualmente organizzate in librerie specifiche
 Per invocare un’azione personalizzata:
nomeLibreria.nomeAzione
Jason: personalizzazione
Personalizzare le azioni interne
 Il nome di un’azione deve iniziare con una lettera
minuscola, il suo codice deve essere contenuto in un
file con nome:
nomeAzione.java
 La classe in questione deve ridefinire il metodo
execute:
package <nomeLibreria>;
import jason.*;
public class <nomeAzione>{
public static boolean execute (…) throws Exception{
…
}
}
Jason: personalizzazione
Personalizzare l’ambiente
 Il programmatore può personalizzare l’ambiente in cui
si collocano gli agenti AgentSpeak(L)
 In particolare, è possibile descrivere come si evolve
l’ambiente in seguito all’esecuzione di un’azione da
parte di un agente, modificando il codice del metodo
executeAction
 Possibilità di simulare fallimenti nell’esecuzione delle
azioni
 Possibilità di limitare ad un sottinsieme dell’ambiente la
percezione di ciascun agente
Jason: personalizzazione
Personalizzare l’ambiente
 Il file contenente la classe dell’ambiente personalizzato
va specificato nel file di configurazione
import java.util.*;
import jason.*;
public class <nomeAmbiente> extends Environment{
…
public boolean executeAction (String ag, Term act){
…
}
}
 ag è l’agente che esegue l’azione rappresentata dal
termine act; il metodo restituisce true se l’azione è
stata eseguita con successo
Jason: riferimenti importanti
 Per scaricare gratuitamente l’ultima versione di Jason:
http://jason.sourceforge.net
 Per scaricare gratuitamente SACI:
http://www.lti.pcs.usp.br/saci/
Conclusioni
AgentSpeak(L)
 Linguaggio di programmazione per agenti BDI
 Molti lavori per estendere il linguaggio di base, che non
descrive, ad esempio, come gestire il fallimento dei piani
 Utilizzato solo di recente anche grazie a Jason
Jason
 Implementazione Java di AgentSpeak(L) esteso
 Semplice definizione di un ambiente multiagente con l’uso
di SACI
 Molteplici possibilità di personalizzazione
 Ancora molto lavoro da fare:
 Documentazione carente
 Difficile osservare l’evoluzione del sistema: opportuna
un’evoluzione dell’interfaccia e del supporto al
programmatore
 Gli autori lo hanno sviluppato a “tempo perso”
Bibliografia
BurSun92. B. Burmeister e K. Sundermeyer. Cooperative
problem-solving guided by intentions and perception. In E.
Werner and Y. Demazeau, editors, Decentralized A.I. 3,
Amsterdam, Olanda, 1992.
GeoLan86. M.P. Georgeff e A.L. Lansky. Procedural knowledge.
In Proceedings of the IEEE Special Issue on Knowledge
Representation, volume 74, 1383-1398, 1986.
IngGeoRao92. F.F. Ingrand, M.P. Georgeff e A.S. Rao. An
architecture for real-time reasoning and system control. IEEE
Expert, 7(6), 1992.
MulPisThi95. J.P. Muller, M. Pischel e M. Thiel. Modelling
reacting behaviour in vertically layered agent architectures. In
Intelligent Agents: Theories, Architectures, and Languages. LNAI
890, Heidelberg, Germania, 1995.
Rao95. A.S. Rao. Decision procedures for propositional lineartime belief-desire-intention logics. In Working notes of the IJCAI95 Workshop on Agent Theories, Architectures, and Languages,
Montreal, Canada, 1995.
Rao96. A.S. Rao. AgentSpeak(L): BDI Agents Speak Out in a
Logical Computable Language. MAAMAW 1996: 42-55, 1996.
RaoGeo91. A.S. Rao e M.P. Georgeff. Modeling rational agents
within a BDI-architecture. In J. Allen, R. Fikes, and E. Sandewall,
editors, Proceedings of the 2° International Conference on
Principles of Knowledge Representation and Reasoning, 1991.
RaoGeo93. A.S. Rao e M.P. Georgeff. A model-theoretic approach
to the verification of situated reasoning systems. In Proc. Of the
13° Intern. Joint Conf. On Artificial Intelligence (IJCAI-93),
Chambery, Francia, 1993.
Sho93. Y. Shoham. Agent-oriented programming. Artificial
Intelligence, 60(1), 51-92, 1993.
BorHub04. R.H. Bordini e J.F. Hubner. Jason: a Java-based
agentSpeak interpreter used with saci for
multi-agent distribution over the net. Disponibile all’indirizzo
jason.sourceforge.net/Jason.pdf.