Aplicatii Web bazate pe semantica, agenti si servicii

Universitatea Politehnica Bucuresti

Anul universitar 2008-2009, MasterAdina Magda Florea

http://turing.cs.pub.ro/webs_07

Curs 5

Agenti si arhitecturi agenti Sisteme multi-agent (SMA) Comunicare in SMA

1. Structura conceptuala a agentilor

Rationalitatea unui agent Ce inseamna rationalitatea unui agent Cum putem masura rationalitatea unui

agent? Sa gasim o masura a performantei

3

Un agent este situat in mediu Perpece mediul prin sensori si actioneaza asupra lui prin

efectori

Scop: proiectarea unui program – functie care realizeaza corespondenta sensori - efectori

Agent = architectura + program

Mediu accesibil vs. inaccesibil determinist vs. non-determinist static vs. dinamic discret vs. continu

4

Modelare agent

E = {e1, .., e, ..}P = {p1, .., p, ..}A = {a1, .., a, ..}

Agent reactivsee : E Paction : P Aenv : E x A E(env : E x A P(E))

Mediuenv (E)

Componentadecizie

action

Componentaexecutie

action

Componentaperceptie

see

Agent

5

P A

Modelare agentMai multi agenti reactivi

seei : E Pi

actioni : Pi Ai

env : E x A1 x … An P(E)

Mediuenv

Componentadecizie

action

Componentaexecutie

action

Componentaperceptie

see

Agent (A1)

Agent (A2)

Agent (A3)

6

A1,…, Ai,..P1,…, Pi,..(de obicei identice)

Unitati simple de prelucrare care percep mediul si reactioneaza la schimbarile din mediu

Nu folosesc reprezentari simbolice sau rationament

Inteligenta nu este situata la nivel individual ci distribuita in sistem, rezulta din interactiunea entitatilor cu mediu – “emergence”

7

Modelare agent

E = {e1, .., e, ..}P = {p1, .., p, ..}A = {a1, .., a, ..}S = {s1, .., s, ..}

Agent cu staresee : E Pnext : S x P Saction : S Aenv : E x A P(E)Mediu

env (E)

Componentadecizie

action, next

Componentaexecutie

action

Componentaperceptie

see

Agent

8

P A

S

Mai multi agenti cognitiviseei : E Pi

nexti : Si x P Si

actioni : Si x I Ai

interi : Si I env : E x A1 x … An P(E)

Mediuenv

Componentadecizie

action, next

Componentaexecutie

action

Componentaperceptie

see

Agent (A1)

Agent (A2)

Agent (A3)

Componentainteractiune

inter

9

S1,…, Si,..A1,…, Ai,..P1,…, Pi,..(nu intotdeauna identice)

I = {i1, .., ik,…}

Modelare agent

Agenti cu stare si scopuri

goal : E {0, 1}

Agenti cu utilitate

utility : E R

Mediu nedeterminist

env : E x A P(E)

Probabilitatea estimata de un agent ca rezultatul unei actiuni (a) executata in e sa fie noua stare e’

prob(ex(a, e) e') 1e'env( e,a)

10

Modelare agent

Agenti cu utilitate

Utilitatea estimata (expected utility) a unei actiuni a intr-o stare e, dpv al agentului

Principiul utilitatii estimate maximeMaximum Expected Utility (MEU)

),('

)'(*)'),((),(aeenve

eutilityeeaexprobeaU

11

Modelare agent

Cum modelam? Curatirea unei camere

Agent reactiv

Agent cognitiv

Agent cognitiv cu utilitate

Ce actiuni selectez?

Ce se face daca rezultatul actiunilor nu este cunoscut/sigur?

12

Modelul uman al perspectivei asupra lumii caracterizare agent utilizand reprezentari simbolice si notiuni mentale

knowledge - cunostinte beliefs - convingeri desires, goals – dorinte, scopuri intentions - intentii commitments - angajamente obligations - obligatii

De ce se utilizeaza aceste notiuni? 13

Agenti cognitivi

Arhitecturi pentru agenti cognitivi Arhitecturi pentru agenti reactivi

14

2. Arhitecturi de agenti

Specificatii de nivel inalt Means-end analysis Beliefs (convingeri) = informatii pe care agentul le

are despre lume Desires (dorinte) = stari pe care agentul ar vrea sa le

vada realizate Intentions (intentii) = dorinte (sau actiuni) pe care

agentul s-a angajat sa le indeplineasca

Rolul intentiilor 15

Arhitectura BDI

16

Arhitectura BDIBelief revision

BeliefsKnowledge

Deliberation process

percepts

DesiresOpportunityanalyzer

Intentions

Filter

Means-endreasonner

Intentions structured in partial plans

PlansLibrary of plans

Executor

B = brf(B, p)

D = options(B, D, I)

I = filter(B, D, I)

= plan(B, I)

actions

Bucla de control a agentuluiB = B0 I = I0 D = D0

while true doget next perceipt pB = brf(B,p)D = options(B, D, I)I = filter(B, D, I) = plan(B, I)execute()

end while 17

Strategii de angajare Optiune aleasa de agent ca intentie – agentul s-a

angajat pentru acea optiune Persistenta intentiilor

Interbare: Cat timp se angajeaza un agent fata de o inetntie?

Angajare oarba (Blind commitment) Angajare limitata (Single minded

commitment) Angajare deschisa (Open minded commitment)

18

B = B0

I = I0 D = D0

while true doget next perceipt pB = brf(B,p)D = options(B, D, I)I = filter(B, D, I) = plan(B, I)while not (empty() or succeeded (I, B)) do

= head()execute()

= tail()get next perceipt pB = brf(B,p)if not sound(, I, B) then = plan(B, I)

end whileend while 19

Bucla de control BDIBucla de control BDIangajare oarba

B = B0

I = I0 D = D0

while true doget next perceipt pB = brf(B,p)D = options(B, D, I)I = filter(B, D, I) = plan(B, I)while not (empty() or succeeded (I, B) or impossible(I,

B)) do = head()execute()

= tail()get next perceipt pB = brf(B,p)if not sound(, I, B) then = plan(B, I)

end whileend while 20

Bucla de control BDIBucla de control BDIangajare limitata

B = B0

I = I0 D = D0

while true doget next perceipt pB = brf(B,p)D = options(B, D, I)I = filter(B, D, I) = plan(B, I)while not (empty() or succeeded (I, B) or impossible(I, B))

do = head()execute()

= tail()get next perceipt pB = brf(B,p)

D = options(B, D, I) I = filter(B, D, I)

= plan(B, I)end while

end while 21

Replan

if reconsider(I, B) then

Bucla de control BDIBucla de control BDIangajare deschisa

Nu exista o unica arhitectura BDI

PRS - Procedural Reasoning System (Georgeff)

UMPRS si JAM – arhitecturi BDI (http://www.marcush.net/IRS/irs_downloads.html)

JACK – platforma de dezvoltare C-BDI – BDI – nucleu Jack

(http://www.aosgrp.com/index.html)

JASON – arhitectura BDI (http://jason.sourceforge.net/JasonWebSite/Jason%20Home.php)

22

Arhitectura de subsumare - Brooks, 1986 (1) Luarea deciziilor = {Task Accomplishing

Behaviours} Fiecare comportare (behaviour) = o functie ce

realizeaza o actiune TAB – automate finite Implementare: situation action

(2) Mai multe comportari pot fi activate in paralel

23

Arhitectura reactiva

Arhitectura de subsumare

Un TAB este reprezentat de un modul de competenta (c.m.)

Fiecarte c.m. executa un task simplu c.m. opereaza in paralel Nivele inferioare au prioritate fata de cele

superioare c.m. la nivel inferior monitorizeaza si influenteaza

intrarile si iesirile c.m. la nivel superior

subsumtion architecture

24

25

CompetenceModule (1)Move around

CompetenceModule (0)Avoid obstacles

Inhibitor nodeSupressor node

Sensors

CompetenceModule (2)Explore environ

CompetenceModule (0)Avoid obstacles

EffectorsCompetenceModule (1)Move around

Input(percepts)

Output(actions)

(c, a) – conditie-actiune; descrie comportarea

R = { (c, a) | c P, a A} - multimea reguli de comportare

R x R – relatie binara totala de inhibare

function action( p: P)var fired: P(R), selected: Abegin

fired = {(c, a) | (c, a) R and p c}for each (c, a) fired doif (c', a') fired such that (c', a') (c, a) then return areturn null

end26

Comportare arhitectura subsumare

Ne aflam pe o planeta necunoscuta care contine aur. Mostre de teren trebuie aduse la nava. Exista mai multi agenti autonomi care nu pot comunica intre ei. Nava transmite semnale radio: gradient al campului

Comportare

(1) Daca detectez obstacol atunci schimb directia

(2) Daca am mostre si sunt la baza atunci depune mostre

(3) Daca am mostre si nu sunt la baza atunci urmez directia baza

(4) Daca gasesc mostre atunci le iau

(5) Daca adevarat atunci ma misc in mediu

(1) (2) (3) (4) (5)27

Agentii pot comunica indirect:- Depun si culeg boabe radiocative- Pot seziza aceste boabe radioactive

(1) Daca detectez obstacol atunci schimb directia(2) Daca am mostre si sunt la baza atunci depune mostre(3) Daca am mostre si nu sunt la baza atunci depun boaba

radioactiva si urmez directia baza(4) Daca gasesc mostre atunci le iau(5) Daca gasesc boabe radioactive atunci iau una si urmez

directia baza(6) Daca adevarat atunci ma misc in mediu

(1) (2) (3) (4) (5) (6)28

Swarm intelligence – comportarea colectiva a sistemelor descentralizate si cu auto-organizare

Agenti reactivi, emergenta comportarii colective furnici pasari vaci

Swarm robotics ACO = at colony optimization = algoritm de optimizare

– furnici artificiale care construiesc solutia prin miscarea pe graful problemei: depun feromoni artificiali

Proiectul Swarm http://www.swarms.org/29

Swarms

Comunicare indirecta Comunicare directa Specificarea protocolului

30

3. Comunicare in SMA

In general pt agenti reactivi Comunicare prin semnale

V(x)=V(x0)/dist(x,x0)

Comunicare prin "urme" lasate in mediu

31

Comunicare indirecta

x0

SS - stimulus

Agent A(stimulus genreazacomportare P)

Agent B(stimulus genreazacomportare P)

Comunicare in sisteme tip "blackboard"

32

Comunicare indirecta

KS

KS

KS

KS

KSAR

Control

Blackboard

SMA – limbaje de nivel inalt Presupun in general agenti BDI

ACL = Agent Communication Languages Comunica cunostinte RC Intelegerea mesajului in context ontologii Comunicare vazuta ca o actiune – acte de

vorbire (de comunicare)33

Comunicare directa

J. Austin - How to do things with words, 1962, J. Searle - Speech acts, 1969

Un act de comunicare: locutie = fraza spusa de locutor illocution = intelesul dorit spre a fi comunicat de locutor (performativa) prelocution = actiunea care rezulta din locutie

Maria i-a spus lui Gigel: "Te rog inchide usa"locution illocutie continut

prelocutie: usa inchisa

Categorii ilocutionale Asertive Directive Comisive Permisive Prohibitive Declarative Expresive 34

Acte de vorbire

35

3 straturi ale comunicarii

ACL

Content language

Ontology

Primitive si protocol Limbaje pentru continut

KIF Prolog Clips SQL DL FIPA-SL, FIPA-KIF

Ontologii DAML OWL

36

KIF

Knowledge Interchange Format (KIF)

Facts(salary 015-46-3946 john 72000)(salary 026-40-9152 michael 36000)(salary 415-32-4707 sam 42000)

Asserted relation (> (* (width chip1) (length chip1)) (* (width chip2) (length chip2)))

Rule(=> (and (real-number ?x) (even-number ?n)) (> (expt ?x ?n) 0))

Procedure(progn (fresh-line t)

(print "Hello!")(fresh-line t))

37

ACL

Cele 3 straturi separa: continutul si semantica mesajului semantica comunicarii (acte vorbire) – independenta

de domeniu Un ACL are o semantica formala bazata pe un

formalism logic 2 ACL-uri care s-au impus:

KQML FIPA-ACL

ACL

Content language

Ontology

38

KQML

Tpuri de performative Queries - ask-one, ask-all, ask-if, stream-all,... Generative - standby, ready, next, rest, discard,

generate,... Response - reply, sorry ... Informational - tell, untell, insert, delete, ... Capability definition - advartise, subscribe, recommend... Networking - register, unregister, forward, route, ...

Content

Communication

Message

Parametrii comunicarii- identitate emitator si receptor- identificator unic asociat comunicarii

KQML de baza- protocol retea- act de vorbire

Optional- limbajul continutului- ontologie

(ask-one :sender joe:receiver ibm-stock:reply-with ibm-stock:language PROLOG:ontology NYSE-TICKS:content (price ibm ?price) )

(tell :sender willie:receiver joe:reply-with block1:language KIF:ontology BlockWorld:content (AND (Block A) (Block B) (On A B)) )

39

KQML - exemple

ask-one(P)

tell(P)

tell(P1)

stream-all(P)

tell(P2)eos

tell(P1,P2,...)

ask-all(P)

B

B

B

A

A

A

40

Agent facilitator

tell(P)

ask(P)

subscribe(ask(P)) tell(P)

tell(P)

advertise(ask(P))

tell(P)

recruit(ask(P))

reply(A)

recommend(ask(P)) advertise(ask(P))

tell(P)

ask(P)

reply(B)

A

A

A

A

B

B

B

B

point-to-point

Logica modalaBel(A,P) Know(A,S) Want(A,S) Int(A,S) Preconditii: starea agentului emitator si a celui receptor pt a trimite si

receptiona un mesaj (error or sorry daca nu sunt) Postconditii – statrea emitatorului si receptorului dupa primirea cu succes a

unui mesaj Conditie de finalizare – dupa incheierea mesajului si realizarea intentiei

asociate

tell(A,B,X)Pre(A): Bel(A,X) Know(A, Want(B, Know(B, Bel(A,X))))Pre(B): Int(B, Know(B, Bel(A,X)))

Post(A): Know(A, Know(B, Bel(A,X))) Post(B): Know(B, Bel(A,X))Completion: Know(B, Bel(A,X)) 41

Semantica KQML

• Asemanator cu KQML• Primitive oarecum diferite• Semantica semnificativ diferita

(inform  :sender (agent-identifier :name i)   :receiver (set (agent-identifier :name j))  :content    "weather (today, raining)"  :language Prolog)

42

FIPA ACL

(request :sender (agent-identifier :name i) :receiver (set (agent-identifer :name j)

:content ((action (agent-identifier :name j)(deliver box7 (loc 10 15))))

:protocol fipa-request :language fipa-sl :reply-with order56 )

(agree sender (agent-identifier :name j) :receiver (set (agent-identifer :name i)

:content ((action (agent-identifier :name j)(deliver box7 (loc 10 15))) (priority order56

low)) :protocol fipa-request :language fipa-sl :in-reply-to order56 ) 43

FIPA - exemple

FIPA – acte de comunicare

Informative - query_if, subscribe, inform, inform_if, confirm,

disconfirm, not_understood

Distributie taskuri - request, request_whenever, cancel, agree, refuse, failure

Negociere - cfp, propose, accept_proposal, reject_proposal

44

FIPA - primitive

SL (Semantic Language)B - belief C - desire U - uncertain beliefBif = B V B~ Preconditii – conditiile necesare pt agentul

emitator; nu neaparat trimite mesaj Rational effect – efectul sperat la receptor; nu

neaparat realizat

<A, inform(B, )>Pre: BA BA (BifB UifB )

Post: BB

45

FIPA ACL

46

FIPA ACL

Inform indicates that the sending agent:  holds that some proposition is true,  intends that the receiving agent also comes to believe that the proposition is true, and,  does not already believe that the receiver has any knowledge of the truth of the

proposition.

From the receiver’s viewpoint, receiving an inform message entitles it to believe that:

 the sender believes the proposition that is the content of the message, and,  the sender wishes the receiver to believe that proposition also.

 Whether or not the receiver does, indeed, adopt belief in the proposition will be a function of the receiver's trust in the sincerity and reliability of the sender.

<A, inform(B, )>Pre: BA BA (BifB UifB )Post: BB

47

FIPA - Protocoale

Defineste o serie de protocoale standard FIPA-query, FIPA-request, FIPA-

contract-net, ...

48

FIPA - Request

49

Contract netInitiator si contractori (potentiali)

50

FIPA - Contract net