4/22/2015bdi agents1 BDI AGENTS n SCOPO DEGLI AGENTI “ BELIEFS, DESIRES AND INTENTIONS” n...

04/11/23 bdi agents 2

SCOPO DEGLI AGENTI “ BELIEFS, DESIRES AND INTENTIONS”

Esigenza che si vuole risolvere:

“Costruire sistemi che sono situati in ambienti dinamici e che devono ragionare e pianificare, e agire con forti vincoli di tempo. Il sistema deve essere contemporaneamente goal directed e reattivo”

[Rao & Georgeff 1992]


SITUATEDNESS: non solo sono collocati in un ambiente in cui

agiscono, ma, soprattutto, possiedono una rappresentazione

simbolica di esso

PIANIFICARE: costruiscono e/o scelgono delle sequenze di azioni

che permettono di rendere vero un certo stato del mondo

VINCOLI TEMPORALI: tali sistemi non dispongono di risorse

infinite: “resource boundedness”

GOAL DIRECTED: devono cercare di ottenere un certo scopo

REACTIVITY: devono reagire di fronte a cambiamenti

dell’ambiente


NASA: Deep Space 1 remote agent experiment

http://rax.arc.nasa.gov/


Robocup

http://www.robocup.org/


ESEMPI DI DOMINI DI APPLICAZIONE

Automatizzazione delle procedure usate dagli astronauti sullo Space Shuttle per gestire i malfunzionamenti dei propulsion flight controllers.

PRS [Georgeff & Ingrand,1988]

Automatizzazione dei controllori di volo che coordinano l’arrivo degli aerei in aeroporto

[Rao & Georgeff, 1992]

Simulatori


HUMAN AGENTHOOD

Il modello che i bdi agents vogliono imitare e’ il comportamento umano.

In particolare il fatto che gli esseri umani siano guidati da tre “attitudini”:

Ambiguo fra il significato di scopo

e desiderio.

BELIEFS, DESIRES AND INTENTIONSCREDENZE, GOAL E INTENZIONI


Bratman: “What Is Intention?”

2 possibili interpretazioni della parola:–Azione: “l’ha ucciso intenzionalmente”–Stato mentale: “ho l’intenzione di andare a vedere Titanic”

Proprieta’:

–future directed: *“ho l’intenzione di andare al cinema ieri”

–stato mentale che influenza il comportamento futuro

–stabili (“committment”) ma revocabili: non posso prevedere cosa accadra’ in futuro, quindi devo poter cambiare idea.


“Why bother today to have an intention about tomorrow?”

Perche’ non attendere domani sera prima di formarmi (ora) l’intenzione di andare al cinema?

Perche’ sprecare risorse per formarmi delle intenzioni ora, se non so cosa accadra’ domani (ad es. Mi potrebbero invitare a cena)?

Soluzione alternativa:

utilizzare un pianificatore classico e poi scegliere fra le

opzioni che propone


Planning + Practical Reasoning?

Scelgo un obbiettivo Costruisco un piano completo che lo soddisfi Scelgo fra le alternative tramite “decision theory” (probabilita’

eventi + utility function)

Limiti: devo conoscere lo stato del mondo piu’ tempo passo a pianificare e decidere, maggiore e’ la

probabilita’ che il mondo cambi ad ogni cambiamento del mondo devo ricominciare da capo


1

2

3

4

A B C D

put(?x,?y)

INITIAL STATE:


1

2

3

GOAL:

1

2

3 1

2 2

3

4 4



Pianifico Scelgo Eseguo un passo da capo


1

2

3

put(1,A);put(3,C);put(2,1);put(3,2)

A B C D


1 2

3


put(1,A)

A B C D


1 2

3


put(1,A)


A B C D


1 2 3


put(1,A)


put(3,C)

A B C D


1 2 3


put(1,A)


put(3,C)


A B C D


1

2

3

A B C D


put(1,A)


put(3,C)


put(2,1)


1

2

3

A B C D


put(1,A)


put(3,C)


put(2,1)


put(3,2)


Corriere della Sera

“Con la Croazia non doveva far giocare Maldini in condizioni precarie. Totti era troppo arretrato ed aveva perso brillantezza. Iuliano è forse meno emotivo e più esperto di Materazzi. L’errore più grave è stato quello di non mandar dentro gente fresca verso il 20’ della ripresa. Ha perso troppi minuti a decidere. Di questo è giusto chiedergli conto, …”



Pianifico Scelgo Eseguo tutti i passi da capo


1

2

3


A B C D


1 2

3


put(1,A)

A B C D


1 2 3


put(1,A)

put(3,C)

A B C D


1

2

3


put(1,A)

put(3,C)

put(2,1)

A B C D


1

2

3


put(1,A)

put(3,C)

put(2,1)

put(3,2)

A B C D


1

2

3


A B C D


1 2

3


put(1,A)

A B C D


1 2

34


put(1,A)

A B C D


1 2 3

4


put(1,A)

put(3,C)

A B C D


1 3


put(1,A)

put(3,C)

put(2,1)

A B C D

4

2


1 23


put(1,A)

put(3,C)

put(2,1)

put(3,2)

A B C D

4



Pianifico Scelgo Eseguo un passo (1) Controllo il piano sia eseguibile: vado a (1) se il piano è finito o non eseguibile: da capo


1

2

3


A B C D


1 2

3


put(1,A)

A B C D


1 2 3


put(1,A)

put(3,C)

A B C D


1

2

3


put(1,A)

put(3,C)

put(2,1)

A B C D


1

2

3

4


put(1,A)

put(3,C)

put(2,1)

A B C D


1

2

3


put(1,A)

put(3,C)

put(2,1)

put(3,2)

A B C D

4



Pianifico Scelgo Eseguo un passo (1) Controllo il piano sia eseguibile o il goal soddisfatto: vado a (1) se il piano è finito o non eseguibile: da capo



Pianifico (e ripianifico dal piano esistente) Scelgo Eseguo un passo (1) Controllo il piano sia eseguibile o il goal soddisfatto: vado a (1) se il piano è finito o non eseguibile: da capo


1

2

3


A B C D


1 2

3


put(1,A)

A B C D


1 2

3

4


put(1,A);

A B C D


1 2 34


put(1,A)

put(1,A);put(3,D);put(2,1);put(3,2)

put(3,D)

A B C D


put(1,A)


...


1

2


put(1,A)


put(3,D)

put(2,1)

...

A B C D

34



Pianifico (e ripianifico dal piano esistente) Scelgo Eseguo un passo (1) Controllo il piano sia eseguibile o il goal soddisfatto: vado a (1)

(anche se perdo delle opportunità!)

se il piano è finito o non eseguibile: da capo


1

2

3


A B C D

4


1 2

3


put(1,A)

A B C D

4


1 2

3


put(1,A)

A B C D


put(1,A)



1 2 3


put(1,A)

put(3,D)

A B C D


1

2

A B C D

3


put(1,A)

put(3,D)

put(2,1)


1

2

3


put(1,A)

put(3,D)

put(2,1)

put(3,2)

A B C D



Pianifico Scelgo Se ci sono nuovi goal modifico la soluzione corrente (1) Eseguo un passo vado a (1)


1

2

3


A B C D


1 2

3


put(1,A)

A B C D


1 2

3


put(1,A)

put(1,A);put(5,D);put(3,C);put(2,1);put(3,2)

A B C D

GOAL:

on(5,?x)


put(1,A)

put(1,A);put(5,C);put(3,D);put(2,1);put(3,2)

...


1 2

3


put(1,A)


put(5,D)

A B C D

GOAL:

on(5,?x)

5


1 2 3


put(1,A)


put(5,D)

put(3,C)

A B C D

5


1

2

3


put(1,A)


put(5,D)

put(3,C)

put(2,1)

A B C D

5


1

2

3


put(1,A)


put(5,D)

put(3,C)

put(2,1)

put(3,2)

A B C D

5



Pianifico Scelgo (il piano migliore) Eseguo un passo da capo


1

2

3


A B C D

heavy

light


1 2

3


put(1,A)

A B C D

heavy

light


1 2 3


put(1,A)

put(3,C)

A B C D

heavy

light


1 2 3


put(1,A)

put(3,C)


A B C D

heavy

light


1

2

3


put(1,A)

put(3,C)


put(2,3)

A B C D

heavy

light


1

2

3


put(1,A)

put(3,C)


put(2,3)

put(1,A);put(3,C);put(2,3);put(2,1);put(3,2)

A B C D

heavy

light



Pianifico (in modo minimale) Scelgo Eseguo un passo (1) Controllo il piano sia eseguibile o il goal soddisfatto: vado a (1) se il piano è finito o non eseguibile: da capo


1

2

3

put(1,?x);put(3,?y);put(2,1);put(3,2)

A B C D


1 2

3

put(1,?x);put(3,?y);put(2,1);put(3,2)

put(1,A);put(3,?y);put(2,1);put(3,2)

put(1,A);

A B C D


1 2 3

put(1,?x);put(3,?y);put(2,1);put(3,2)

put(1,A);put(3,?y);put(2,1);put(3,2)

put(1,A)


put(3,C)

A B C D


1

2

3

A B C D

put(1,?x);put(3,?y);put(2,1);put(3,2)

put(1,A);put(3,?y);put(2,1);put(3,2)

put(1,A)


put(3,C)

put(2,1)


1

2

3

A B C D

put(1,?x);put(3,?y);put(2,1);put(3,2)

put(1,A);put(3,?y);put(2,1);put(3,2)

put(1,A)


put(3,C)

put(2,1)

put(3,2)


1

2

3

put(1,?x);put(3,?y);put(2,1);put(3,2)

A B C D


1 2

3

put(1,A);put(3,?y);put(2,1);put(3,2)

put(1,A);

A B C D


1 2

3

4

put(1,A);put(3,?y);put(2,1);put(3,2)

put(1,A);

A B C D


1 2 34


put(1,A)

put(3,D)

A B C D


1

2


put(1,A)

put(3,D)

put(2,1)

A B C D

34


1

2

3


put(1,A)

put(3,D)

put(2,1)

put(3,2)

A B C D

4


1

2

3

put(1,?x);put(3,?y);put(2,1);put(3,2)

A B C D

4


1 2

3

put(1,A);put(3,?y);put(2,1);put(3,2)

put(1,A);

A B C D

4


1 2

3

put(1,A);put(3,?y);put(2,1);put(3,2)

put(1,A);

A B C D


1 2 3


put(1,A)

put(3,C)

A B C D


1

2


put(1,A)

put(3,C)

put(2,1)

A B C D

3


1

2

3


put(1,A)

put(3,C)

put(2,1)

put(3,2)

A B C D


RUOLO DELLE INTENZIONI

Questi problemi sono dovuti alla “resource boundedness”: il ruolo delle intenzioni e’ di limitare lo spazio di ricerca del planning e quello della scelta fra le opzioni.

Per questo motivo le intenzioni: sono future directed e (relativamente) stabili: se stabilisco ora

una linea di azione per il futuro, le scelte successive dovranno essere compatibili con questa: limito le opzioni possibili.

Se ho l’intenzione di andare domattina a prendere un libro in biblioteca, non prendero’ in considerazione l’azione di andare a giocare a tennis

04/11/23 bdi agents 100

Riguardano piani parziali: non conoscendo in anticipo come puo’

evolvere il mondo, costruisco dei piani che sono incompleti

temporalmente (non stabilisco l’ordinamento completo delle

azioni) o strutturalmente (non scelgo come eseguire delle azioni

complesse). Esempio:

Posso avere l’intenzione di andare a prendere un libro in

biblioteca, senza aver necessariamente costruito un piano in

tutti i suoi dettagli (posso non aver ancora scelto se andare in

macchina o prendere il tram, perche’ non so se ci sara’

sciopero).

Costituiscono l’input per ulteriori fasi di pianificazione

04/11/23 bdi agents 101

PARTIAL PLANS:hierarchical organization of actions

Get-book

Buy-book Borrow-book

Go(library) Read(location) Fill(sheet,location)

Walk(library) Drive(library)

Piano completo: Walk(library);Read(location);Fill(sheet,location)...

04/11/23 bdi agents 102

HAVING A PLAN

[Pollack,1990] distingue due significati del concetto di avere un piano:

avere la conoscenza riguardo all’esecuzione di un certo compito (ad es. possedere una libreria di piani)

essere nello stato mentale di avere l’intenzione di eseguire un piano: devo credere che il piano sia eseguibile, credo che intendo eseguirlo per raggiungere un certo scopo, devo avere l’intenzione di eseguire tutti i passi del piano...

04/11/23 bdi agents 103

INTENZIONI E CREDENZE

Intendo solo cio’ che credo possibile (i.e. esiste un piano che ritengo eseguibile)

credo che eseguiro’ quello che intendo: se intendo andare al cinema domani, credo che domani saro’ al cinema e non a casa (“conduct coordinating pro-attitude”)

la stabilita’ delle intenzioni implica che, se fallisce il mio piano, ne cerchero’ un altro per raggiungere il mio scopo

controllo se l’esecuzione di un piano ha avuto successo non intendo quelle che credo essere le conseguenze indesiderate

delle mie azioni (problema dei “side effects”)

04/11/23 bdi agents 104

SIDE EFFECTS

Intend(A) Bel(AB)

Intend(B) ?Non voglio essere committed verso B: altrimenti dovrei perseguire B anche se A e’ gia’ realizzato (e quindi le mie credenze erano sbagliate).

Esempio:Strategic bomber: Intend(bombardare la fabbrica) ma Bel(bombardare la fabbrica uccidere i bimbi della scuola)

Terror bomber: Intend(uccidere i bimbi della scuola)

04/11/23 bdi agents 105

ARCHITETTURA ASTRATTA

Intentions structured into

plans

Filtering process

means-end reasoning

Deliberation process

Desires

Opportunity analyser

Beliefs

Reasoner

Plan library

perc

epti

on

action

intentions

option

04/11/23 bdi agents 106

SPECIFICHE DI AGENTI BDI

[Cohen & Levesque, 1990] propongono una formalizzazione della relazione fra credenze, goal e intenzioni per mezzo di una logica modale.

Danno una specifica di cosa e’ un agente BDI, non un formalismo per costruire sistemi.

Dichiarativita’: non solo definizione operazionale (i.e. architettura di agente) perche’ e’ necessario poter parlare delle intenzioni di un agente.

04/11/23 bdi agents 107

MODAL LOGIC

Le intenzioni sono modellate come un concetto complesso e definite in termini di belief e goal di un agente: utilizzano degli operatori modali basati su una semantica a mondi possibili.

L’oggetto di una intenzione puo’ essere un’azione: estensione della logica modale per rappresentare azioni :

Ogni mondo deve essere una sequenza di stati collegati da azioni che scandiscono il tempo

a1a0 a2 a3 a4A B A B A B A B

nn-1 n+1 n+2

04/11/23 bdi agents 108

BELIEFS and ACTIONS

a1a0 a2 a3 a4

A B AB AB AB

nn-1 n+1 n+2

a1ap a2 ak an

A B A B A B

nn-1 n+1 n+2

a1ah a2 ai am

A B A B AB AB

nn-1 n+1 n+2

Bx

A B

A B Belx(A) Belx(B)

Bx: (PN)

1

0

2

04/11/23 bdi agents 109

GOALS and ACTIONS

a1a0 a2 a3 a4

A B AB AB AB

nn-1 n+1 n+2

a1ap a2 ak an

A B AB AB

nn-1 n+1 n+2

Gx

A B Gx: (PN)

1

0

Goalx(A)

Goalx(happens(a2;B))

04/11/23 bdi agents 110

REPRESENTING ACTIONS

Bisogna poter parlare delle azioni, di cio’ che e’ (creduto) vero dopo un’azione o nel futuro:

happens(a2)happens(a2;a3)

Belx(happens(a2) done(a1))

happens(a2;A?) (test action)

Belx( B) (eventually)

where Pe|happens(e;P?)

later(A)

where later(P) P P

before(P,Q)

04/11/23 bdi agents 111

PROPRIETA’ di Bel e Goal

Realismo: non posso scegliere cio’ che credo falso: i mondi accessibili via relazione G devono essere un sottoinsieme di quelli accessibili via B

Se credo vero qualcosa non posso non volerlo: Belx(P)Goalx(P) (nello stesso istante temporale)

serialita’ di B e G (consistenza): Goalx(P) Goalx(P)

chiusura rispetto a implicazione (e side effects): (Goalx(P) Goalx(P Q)) Goalx(Q)

notare che Belx(P Q)Goalx(P Q)

if |= then Goalx()

|= Goalx(later(P)) (no infinite deferral)

04/11/23 bdi agents 112

PERMANENT GOAL

Achieavement goal (vs maintaineance):

A-Goalx(P) Goalx(later(P)) Belx(P)

Committment (fanatical): goal permanente a certe condizioni

P-Goalx(P) A-Goalx(P) Belx(P)

before[(Belx(P) Belx(P)),

Goalx(later(P))]

Relative committment:

P-R-Goalx(P,Q) A-Goalx(P) Belx(P)

before[(Belx(P) Belx(P) Belx(Q) ),

Goalx(later(P))]

04/11/23 bdi agents 113

INTENDING ACTIONS

Intend1x(a) P-Goalx[donex(Belx(happensx (a;P?))?;a;P?)]

a1... a a3 a4P P ...

nn-1 n+1 n+2

a1... a2 ... ...... ...

nn-1 n+1 n+2

a1ah a ... ...... P P ...

nn-1 n+1 n+2

Bx

P

1

0

2

..

Gx

P

04/11/23 bdi agents 114

INTENDING STATES

Intend2x(P)

P-Goalx{e |donex[Belx(e1|happensx(e1;P?))

Goalx(happensx(e;P?))]?;e;P?}

Quantificazione esterna al belief: x non sa ancora quale azione eseguira’ (forse e1 e), ma l’azione e1 effettivamente eseguita non deve essere contraria ai goal di x.

Esempio dell’uccisione dello zio: voglio uccidere mio zio, ma mentre vado a casa sua investo un pedone; il pedone e’ mio zio ma non l’ho ucciso intenzionalmente.

04/11/23 bdi agents 115

INTENTIONS FOR MULTIAGENTS

Se invece di un singolo agente si ha a che fare con un gruppo che deve eseguire un certo compito, e’ necessaria una nuova nozione di intenzione che permetta di coordinare l’attivita’ del gruppo.

L’intenzione resta uno stato mentale del singolo agente, ma include delle nuove condizioni. Cosi’ come le azioni sono sempre eseguite da un singolo agente.

In particolare, per coordinare un gruppo di agenti e’ necessaria la comunicazione fra loro, in modo che la loro azione non prenda strade divergenti.

Non e’ sufficiente avere l’intenzione di eseguire la propria parte del piano e il mutual belief che gli altri hanno tale intenzione.

04/11/23 bdi agents 116

Esempio del “convoglio” [Cohen & Levesque, 91]A non sa la strada per andare a casa ma sa che B per andare a casa

propria passa davanti alla sua. A segue B senza dirglielo ma B guida troppo veloce e A si

perde. B sa che qualcuno lo seguira’ per andare a casa: pero’, se A si

ferma per un guasto B crede che A sia arrivato e accellera. A arriva a casa e si ferma. Credendo che ci sia un guasto B si

ferma e aspetta A a meta’ strada capisce dove si trova e da quel punto puo’

procedere da solo: ma B continua voler passare davanti a casa di A e a procedere non troppo forte.

04/11/23 bdi agents 117

JOINT INTENTION

Un gruppo di agenti ha un joint persistent goal di ottenere P relativo a Q sse:

tutti i membri del gruppo credono che P e’ falso tutti mutualmente credono che tutti hanno P come goal e’ creduto mutualmente che continueranno ad avere un weak

achievement goal fino a che non sara’ conoscenza mutua fra loro che P e’ vero o che P e’ impossibile da raggiungere o che Q e’ diventato falso.

Weak achievement goal P: Un agente ha il goal P e crede che P e’ falso oppure crede che che P e’ vero, irrilevante o impossibile da raggiungere e ha il goal che tale situazione sia mutua conoscenza di tutti i membri del gruppo.

04/11/23 bdi agents 118

ARCHITETTURE PER AGENTI BDI

Non e’ possibile utilizzare una formalizzazione logica come quella di Cohen & Levesque assieme ad un theorem prover perche’ non ho garanzie sul tempo di esecuzione del theorem prover e quindi perderei la reattivita’ del sistema.

Anche le procedure di ragionamento sui beliefs e il meccanismo di decisione non puo’ essere implementato per mezzo di un theorem prover perche’ si pone lo stesso problema.

Utilizzo uno strumento uniforme: tutta la conoscenza e’ espressa sotto forma di piani (anche quella per ragionare sui beliefs e per prendere decisioni) e gestita da un interprete.

04/11/23 bdi agents 119

ARCHITETTURA di PRS (Georgeff et al.)

Unico modulo di ragionamento

04/11/23 bdi agents 120

Knowledge Areas = Plans

type: drink-cola

invocation: goal-add(thirst)

precondition:have-glass

add-list: { thirst}

body:

start

have-cola

drink

1

end

proposition action

type: drink-waterinvocation: goal-add(thirst)precondition:have-glass add-list: { thirst}body:

start

open-tap

drink

1

end

04/11/23 bdi agents 121

BDI INTERPRETER()

Initialize state();

do

options := option-generator(event-queue, B,G,I);

selected-option := deliberate(options,B,G,I);

I := update-intentions(selected-option,I);

execute(I);

event-queue := event-queue + get-new-external-events();

drop-successful-attitudes(B,G,I);

drop-impossible-attitudes(B,G,I);

until quit.

eventi interni

ed esterni

anche esito azioni

bound on reaction

timeatomic

actions

beliefs espliciti

no chiusura

04/11/23 bdi agents 122

Option-generator(event-queue,B,G,I)

options := {};

for trigger-event event-queue do

for plan plan-library do

if matches(invocation-cond(plans),trigger-event) then

options := options + plan;

return(options).

04/11/23 bdi agents 123

Deliberate(options,B,G,I)

if length(options) < 2 then return(options)

else metalevel-options := (belief-add(option-set(options)));

selected-option := deliberate(metalevel-options);

if null(selected-option) then return(random-choice(options));

else return(selected-option).

04/11/23 bdi agents 124

Meta Knowledge Areas

type: meta-selectorinvocation: lenght(options)>1 add-list: {goal-add(?x)}body:

start

Bel(cheap(?x))

end

1

Bel(?x cheap(?x))

?x := random-

choice(options)

type: prove Binvocation: goal-add(Bel(B))precondition: Bel(A)add-list: {Bel(B)}body:

end

end

2

goal-add(?x)

04/11/23 bdi agents 125

Intention structure

Beliefs Goals Intentions

cheap(drink-water) thirst have-glass thirst

option-set(drink-cola,drink-water)

meta-selector

Bel(cheap(?x))

?x=drink-water drink-water

open-tap

drink

thirst

4/22/2015bdi agents1 BDI AGENTS n SCOPO DEGLI AGENTI “ BELIEFS, DESIRES AND INTENTIONS” n...

Documents

Transcript of 4/22/2015bdi agents1 BDI AGENTS n SCOPO DEGLI AGENTI “ BELIEFS, DESIRES AND INTENTIONS” n...