您的当前位置：首页 Reasoning about interaction protocols for web service composition

Reasoning about interaction protocols for web service composition

来源：华佗小知识

Electronic Notes in Theoretical Computer Science 105 (2004) 21–36

www.elsevier.com/locate/entcs

ReasoningAboutInteractionProtocolsfor

WebServiceComposition

MatteoBaldoni,CristinaBaroglio,AlbertoMartelli,andVivianaPatti1,2

DipartimentodiInformaticaUniversit`adegliStudidiTorino

C.soSvizzera,185,I-10149Torino(Italy)

Abstract

Inthiswork,wefacetheproblemofwebservicecomposition,arguingtheimportanceoftheinclusion,inawebservicedescription,ofthehigh-levelcommunicationprotocolusedbyaservicetointeractwithaclient.Theworkissetinthesamemulti-agentresearchareafromwhichDAML-Sisderived:reasoningaboutactionsandaboutthechangeproducedbyactionsontheworld.Inthisperspectivewebservicesareviewedasactions,eithersimpleorcomplex,characterizedbypreconditionsandeﬀects.Inourproposal,interactionisinterpretedastheeﬀectofcommunicativeactionexecution,sothatitcanbereasonedabout.

Keywords:Web-servicecomposition,reasoningaboutactions,conversationprotocols,modallogiclanguages.

1Introduction

Recentyearswitnessedarapidevolutionoftheconceptofworld-wideweb.Inlessthantenyearswepassedfromtheconceptofwebasameansforexchanging(HTML)documentstotheconceptofwebasameansforaccessingto(interactive)webservices[14].Researchinthisﬁeldisverymuchalive.Asthehugeamountofinformationontheweburgedthedevelopmentof

PartiallysupportedbyMIURCoﬁn2003“Logic-baseddevelopmentandveriﬁcationofmulti-agentsystems”nationalproject.2

Email:{baldoni,baroglio,mrt,patti}@di.unito.it

22M.Baldonietal./ElectronicNotesinTheoreticalComputerScience105(2004)21–36

standardlanguagesforrepresentingthesemanticsbehindtheHTML(e.g.RDF[21],OWL[19]),recentlysomeattempttostandardizethedescriptionofwebserviceshasbeencarriedon(DAML-S[8],WSDL[23]).Theuseofstandarddescriptionsisaimedatallowingtheautomaticdiscoveryofwebservices,theirautomaticexecutionandmonitoring,and(thetaskwewillfocusoninthispaper)automaticcomposition.WhiletheWSDLinitiativeismainlycarriedonbythecommercialworld,withtheaimofstandardizingregistration,look-upmechanismsandinteroperability,DAML-Sismoreconcernedwithprovidinggreaterexpressivenesstoservicedescriptioninawaythatcanbereasonedabout[6].Inparticular,aservicedescriptionhasthreeconceptuallevels:theproﬁle,usedforadvertisinganddiscovery,theprocessmodel,thatdescribeshowaserviceworks,andthegrounding,thatdescribeshowanagentcanaccesstheservice.Inparticular,theprocessmodeldescribesaserviceasatomic,simpleorcompositeinawayinspiredbythelanguageGologanditsextensions[12,10,15].Inthisperspective,awidevarietyofagenttechnologiesbasedupontheactionmetaphorcanbeused.Infact,wecanviewaserviceasanaction(atomicorcomplex)withpreconditionsandeﬀects,thatmodiﬁesthestateoftheworldandthestateofagentsthatworkintheworld.Theprocessmodelcan,then,beviewedasthedescriptionofsuchanaction;therefore,itispossibletodesignagents,whichapplytechniquesforreasoningaboutactionsandchangetowebserviceprocessmodelsforproducingnew,composite,andcustomizedservices.

Thisworkissetinamulti-agentframeworkinwhichthewebserviceisanagentthatcommunicateswithotheragentsinaFIPA-likeActionCom-municationLanguage(ACL);thewebservicebehaviorcanbeexpressedasaconversationprotocol,whichdescribesthecommunicationsthatcanoccurwithotheragents.Indeed,thewebservicemustfollowsomepossiblynon-deterministicprocedureaimedatgetting/supplyingallthenecessaryinforma-tion.Wealreadyprovedthatbyreasoningonthe(explicitlygiven)conversa-tionprotocolsfollowedbywebservicesweachieveabetterpersonalizationoftheservicefruition[1];inthecurrentwork,weshowthatthisistruealsointhecaseinwhichservicesaretobecomposedforsolvingthedesiredtask.Asanexample,wewilldescribearationalagent,thatisrequestedtoorganizeadayoutforagivenuser,makingareservationbothtoarestaurantandtoacinema,accordingtousergivenconstraints.

Wefacedtheproblemofdescribingandreasoningaboutconversationpro-tocolsinanagentlogicprogrammingsettingbyusingthemodalactionandbeliefframeworkofthelanguageDyLOG,introducedin[4,3].Integratedinthelanguage,acommunicationkit[20,2]allowsanagenttoreasonabouttheinteractionsthatitisgoingtoenactforprovingifthereisapossibleexecution

M.Baldonietal./ElectronicNotesinTheoreticalComputerScience105(2004)21–3623

oftheprotocol,afterwhichasetofbeliefsofinterest(orgoal)willbetrueintheagentmentalstate.Suchaformofreasoningimpliesmakingassumptionsaboutthementalstateofotheragents,theonesourswishestointeractwith.Weconsideraconversationprotocolasa(non-deterministic)procedurethatspeciﬁesthecomplexcommunicativebehaviorofasingleagent,baseduponsimpler,FIPA-likecommunicativeacts;inacommunicationprotocol,anagentcaneitherplaythepartoftheinitiatororoftheresponder.

Reasoningaboutconversationsforwebservicecom-position

Letusconsiderasoftwareagent,whosetaskistosearchforwebservices,accordingtoauser’srequirements;wewillrefertoitaspa(personalassistant).Asanoveltyw.r.t.theworkin[1],pacomposesthefoundserviceswiththeaimofsolvingcomplextasks.Forexample,letussupposethattheuserwantstospendadayoutbygoingtoarestaurantandthentoacinema.Hewantstomakeareservationatbothplacesandheisalittlerestrictiveaboutthepossiblealternatives.Hewantstoseeaspeciﬁcmovie(e.g.Nausicaa)andhewishestobeneﬁtofsomepromotiononthecinematicketbutheisnoteagertocommunicatehiscreditcardnumberontheinternet.If,ononehand,searchingforacinemaorarestaurantreservationserviceisataskthatcanbeaccomplishedonthebasisofasetofcharacteristickeywords,storedinaregistrysystemusedforadvertisement,theotherkindsofcondition(lookforpromotions,donotusecreditcard)canbeveriﬁedonlybyreasoningaboutthewayinwhichthewebserviceoperatesand,inparticular,abouttheinteractionprotocolthatitfollows.

Tocompletetheexample,supposethattworestaurantsandtwocinemasareavailable(seeFig.1andFig.2fortheAUMLgraphsrepresentingtheirprotocols),butonlyrestaurant1takesparttoapromotioncampaign,bywhichitgivestoeachcustomer,whomadeareservationbytheinternetservice,afreeticketforamovie.Onthesideofcinemas,supposethatcinema2acceptsreservationsbutnofreeticket,whereascinema1acceptstomakereservationsbyusingpromotionalticketsorbyusingthecreditcard.Fig.2(iii)isthepartofprotocolfollowedbycinema1incaseofusingpromotionaltickets,(iv)istheothercase;(v)istheprotocolfollowedbycinema2.

Inamulti-agentframework,especiallyinopenenvironments,whenacom-municationisenacted,agentsexchangetheircommunicationprotocol[13].Theadvantageofhavingaprotocolexchangeatthehigh-leveloftheinter-actionisthatbydoingsoagentscanreasonaboutthechangecausedbyaconversationtotheirownbeliefstate.Arationalmodelofcommunicativeacts

24M.Baldonietal./ElectronicNotesinTheoreticalComputerScience105(2004)21–36

CUSTOMERRESTAURANTyes_no_query(available(Time)[available(Time)]inform(reservation(Time))[available(Time)]inform(cinema_promo)[available(Time)]inform(ft_numeber)CUSTOMERRESTAURANTyes_no_query(available(Time)[available(Time)]inform(reservation(Time))(i)(ii)

Fig.1.TheAUMLgraphs[16]representthecommunicativeinteractionsoccurringbetweenthecustomer(pa)andeachofthewebservices;(i)isfollowedbyrestaurant1,(ii)byrestaurant2.

requiresalsotheagenttomakerationalassumptionsaboutthechangecausedtoitsinterlocutor’sbeliefs[5,11].So,forinstance,anagentwillcommunicateapieceofinformationonlyifitbelievesthattherecipientignoresit;aftersendingtheinformationitwillmakeassumptionsabouttheaugmentedrecip-ient’ssetofbeliefsandactconsequently.Inourexample,pashouldchoosetheﬁrstrestaurantbecauseinthiswayitcanbeneﬁtofthepromotionandobtainafreeticketforthecinema.Itshouldalsochoosetheﬁrstcinemabutcarryonaconversationinwhichthecreditcardisnotrequested.Inordertoperformthiskindofreasoning,itisnecessarytoformalize(again:atahigh-level)thecommunicativeactsandtheinteractionprotocols.WediditbyusingtheDyLOGlanguage,brieﬂyintroducedinthenextsection.

3Introductiontotheagentlanguage

DyLOGisanagentlanguagedeﬁnedinamodallogicframework,thatac-countsbothforatomicandcomplexactions,orprocedures.Inthefollowingthefundamentalsofthelanguagearebrieﬂyintroduced,foramorecompletedescriptionsee[2].Atomicactionsareeitherworldactions,aﬀectingtheworld,ormentalactions,i.e.sensingorcommunicativeactionswhichonlyaﬀecttheagentbeliefs.Foreachworldactionandforeachagentwedeﬁnethemodalities[aagi]ϕ,meaningthattheformulaϕholdsaftereveryexecutionofabyagi,and󰀉aagi󰀊ϕ,representingthepossibilitythatϕholdsaftertheac-tionexecution.WealsointroduceamodalityDone(aagi)forexpressingthata(acommunicativeactoraworldaction)hasbeenexecuted.Themodality2denotesformulasthatholdinallthepossibleagentmentalstates.

Theformalizationofcomplexactionsdrawsconsiderablyfromdynamiclogicforthedeﬁnitionofactionoperatorslikesequence,testandnon-determini-sticchoicebut,diﬀerentlythan[12],werefertoaProlog-likeparadigmand

M.Baldonietal./ElectronicNotesinTheoreticalComputerScience105(2004)21–3625

CUSTOMERyes_no_queryqueryIf(available(Film))refuseInform(available(Film))inform(~available(Film))inform(available(Film))CINEMAXCUSTOMERyes_no_query[available(Film]queryIf(cinema_promo)refuseInform(cinema_promo)inform(~cinema_promo)inform(cinema_promo)[available(Film),cinema_promo]inform(ft_number)[available(Film),cinema_promo]inform(reservation(Film))CINEMAyes_no_query(available(Film))[available(Film)]yes_no_query(cinema_promo)[available(Film),~cinema_promo]yes_no_query(pay_by(c_card))[available(Film),~cinema_promo,pay_by(c_card)]inform(cc_number)[available(Filme,~cinema_promo,pay_by(c_card)]inform(reservation(Film))X(iii)(iv)

CUSTOMERyes_no_query(available(Film))CINEMA[available(Film)]inform(pay_by(cash))[available(Filme]inform(reservation(Film))(v)

Fig.2.TheAUMLgraphs[16]representthecommunicativeinteractionsoccurringbetweenthecustomer(pa)andeachofthewebservices;(iii)and(iv)arethetwopartsoftheprotocolfollowedbycinema1;(v)isfollowedbycinema2.

proceduresaredeﬁnedasrecursiveProlog-likeclauses.Foreachprocedurep,thelanguagecontainsalsotheuniversalandexistentialmodalities[p]and󰀉p󰀊.Thementalstateofanagentisdescribedintermsofaconsistentsetofbeliefformulas.ThemodaloperatorBagimodelsthebeliefsofagiwhileMagi,deﬁnedasthedualofBagi(Magiϕ≡¬Bagi¬ϕ),intuitivelymeansthatagiconsidersϕpossible.Itispossibletodealalsowithnestedbeliefs,torepresentwhatotheragentsbelieveandreasononhowtheycanbeaﬀectedbycommunicativeactions.

Allthemodalitiesofthelanguagearenormal,2isreﬂexiveandtransitive;itsinteractionwithactionmodalitiesisruledby2ϕ⊃[aagi]ϕ.TheepistemicmodalityBagiisserial,transitiveandeuclidean.TheinteractionofDone(aagi)

26M.Baldonietal./ElectronicNotesinTheoreticalComputerScience105(2004)21–36

withothermodalitiesisruledby:ϕ⊃[aagi]Done(aagi)ϕandDone(aagj)ϕ⊃BagiDone(aagj)ϕ(awareness),withagi=agjwhenaagi∈C.Anon-monotonicsolutiontothepersistencyproblemisgiven,whichconsistsinmaximizingpersistencyassumptionsaboutﬂuentsaftertheexecutionofactionsequences,inthecontextofanabductivecharacterization(detailscanbefoundin[2]).3.1Theagenttheory

Thebehaviorofanagentisspeciﬁedbyadomaindescriptionthatincludes:(1)theagentbeliefstate;(2)actionandpreconditionlawsthatdescribetheatomicworldactionseﬀectsontheexecutor’smentalstate;(3)sensingaxiomsfordescribingatomicsensingactions;(4)procedureaxiomsfordescribingcomplexbehaviors.Inourframeworkagentsareindividuals,eachwithitssubjectiveviewofadynamicdomain.Wedonotmodeltherealworldbutonlytheinternaldynamicsofeachagentinrelationtothechangescausedbyactions.Thebeliefstateofanagentintuitivelycontainswhatit(dis)believesabouttheworldandabouttheotheragents.Itisacompleteandconsistentsetofrank1and2beliefﬂuents(abeliefﬂuentFisabeliefformulaBagiLoritsnegation;Ldenotesabeliefargument3).Abeliefstateprovides,foreachagent,athree-valuedinterpretationofallthepossiblebeliefargumentsL,thatcaneitherbetrue,false,orundeﬁned(whenboth¬BagiLand¬Bagi¬Lhold);UagiLexpressestheignoranceofagiaboutL.

Worldactionsaredescribedbytheirpreconditionsandeﬀectsontheac-tor’smentalstate;theytriggerarevisionprocessontheactor’sbeliefs.For-mally,actionlawsdescribetheconditionaleﬀectsonagi’sbeliefstateofanatomicactiona,executedbyagiitself.Preconditionlaws,instead,specifymentalconditionsthatmakeaworldaction(oracommunicativeact)exe-cutableinastate.Anagentcanexecuteawhenthepreconditionﬂuentsofaareinitsbeliefstate.SensingActionsproduceknowledgeaboutﬂuents;theyaredeﬁnedasnon-deterministicactions,withunpredictableoutcome,formallymodelledbyasetofsensingaxioms.Ifweassociatetoeachsensingactionsasetdom(s)ofliterals(domain),whenagiexecutess,itwillknowwhichofsuchliteralsistrue.Complexactionsspecifyagentcomplexbehaviorsbymeansofproceduredeﬁnitions,builtuponotheractions.Formally,acomplexactionisacollectionofinclusionaxiomschemaofourmodallogic,ofform:(1)

󰀉p0󰀊ϕ⊂󰀉p1;p2;...;pm󰀊ϕ

p0isaprocedurenameandthepi’s(i=1,...,m)areeitherprocedurenames,

i.e.aﬂuentliteral(for¬f),adoneﬂuent(Done(aagi)󰀐oritsnegation),orabeliefﬂuentofrank1(Blor¬Bl).Weuselfordenotingattitude-freeﬂuents:aﬂuentliteraloradoneﬂuent.

M.Baldonietal./ElectronicNotesinTheoreticalComputerScience105(2004)21–3627

atomicactions,ortestactions;theoperator“;”isthesequencingoperatorofdynamiclogic.Proceduredeﬁnitionsmayberecursiveandprocedureclausescanbeexecutedinagoaldirectedway,similarlytostandardlogicprograms.3.2Communication

Acommunicationtheoryhasbeenintegratedinthegeneralagenttheorybyaddingfurtheraxiomsandlawstoeachagentdomaindescription.

Speechactsareatomicactionsofformspeechact(sender,receiver,l):senderandreceiverareagentsandliseitheraﬂuentliteraloradoneﬂuent.Theycanbeseenasspecialmentalactions,aﬀectingboththesender’sandthereceiver’smentalstate.Inourmodelwefocusontheinternalrepresentation,thatagentshaveofspeechacts:agi’sbeliefchangesdependontheroleoftheagent.Speechactspeciﬁcationis,then,twofold:onedeﬁnitionholdswhentheagentisthesender,theotherwhenitisthereceiver.Theyaremodelledbygeneralizingtheactionandpreconditionlawsofworldactions,sotoenabletherepresentationoftheeﬀectsofcommunicationsthatareperformedbyotheragentsonagimentalstate.Thisrepresentationallowsagentstoreasonaboutconversationeﬀects.HereafterisanexampleofspeciﬁcationofthesemanticsoftheinformFIPA-ACLprimitivespeechact,asdeﬁnedinourframework:inform(Self,Other,l)

a)2(BSelfl∧BSelfUOtherl⊃󰀉inform(Self,Other,l)󰀊󰀐)b)2([inform(Self,Other,l)]MSelfBOtherl)

c)2(BSelfBOtherauthority(Self,l)⊃[inform(Self,Other,l)]BSelfBOtherl)d)2(󰀐⊃󰀉inform(Other,Self,l)󰀊󰀐)e)2([inform(Other,Self,l)]BSelfBOtherl)

f)2(BSelfauthority(Other,l)⊃[inform(Other,Self,l)]BSelfl)g)2(MSelfauthority(Other,l)⊃[inform(Other,Self,l)]MSelfl)

(a)saysthataninformactcanbeexecutedifthesenderbelieveslandbelievesthatthereceiverdoesnotknowl.IfSelfisthesenderitthinkspossible,butitcannotbesure-autonomyassumption(b)-,thatOtherwilladoptitsbelief.IfitbelievesthatOtherconsidersitatrustedauthorityaboutl,itisconﬁdentthatOtherwilladoptitsbelief(c).SinceexecutabilitypreconditionscanbetestedonlyontheSelfmentalstate,whenSelfisthereceiver,theactionofinformingisconsideredtobealwaysexecutable(d).MoreoverwhenSelfisthereceiver,itbelievesthatlisbelievedbythesenderOther(e)butitadoptslasanownbeliefonlyifitthinksOtherisatrustedauthority(f)-(g).

Get-messageactionsareusedforreceivingmessagesfromotheragents.Wemodelthemasaspecialkindofsensingactions,becausefromtheagentperspectivetheycorrespondtoqueriesforanexternalinput,whoseoutcomeis

28M.Baldonietal./ElectronicNotesinTheoreticalComputerScience105(2004)21–36

unpredictable.Themaindiﬀerencew.r.t.normalsensingactionsisthattheyaredeﬁnedbymeansofspeechactsperformedbytheinterlocutor.Formally,weusegetmessageactionsdeﬁnedbyanaxiomschemaoftheform:

󰀁

(2)speechact(agj,agi,l)]ϕ[getmessage(agi,agj,l)]ϕ≡[

speechact∈Cget

message

Intuitively,Cgetmessageisaﬁnitesetofspeechacts,whichareallthepossiblecommunicationsthatagiexpectsfromagjinthecontextofagivenconversa-tion.Wedonotassociatetoagetmessageactionadomainofmentalﬂuents,butwecalculatetheinformationobtainedbylookingattheeﬀectsofsuchspeechactsonagi’smentalstate.

Weassumeindividualspeechactstotakeplaceinthecontextofprede-ﬁnedconversationprotocols[13]thatspecifycommunicationpatterns.Intheagentdescription,conversationprotocolsaremodelledbymeansofprocedureaxiomshavingtheform(1).Sinceagentshaveasubjectiveperceptionofthecommunication,eachprotocolhasasmanyproceduralrepresentationsasthepossiblerolesintheconversation.

Wecandeﬁnethecommunicationkitofanagentagi,CKitagi,asthetriple(ΠC,ΠCP,ΠSget),whereΠCisthesetofsimpleactionlawsdeﬁningagi’sprimi-tivespeechacts,ΠSgetisasetofaxiomsforagi’sgetmessageactionsandΠCPisthesetofprocedureaxiomsspecifyingtheagi’sconversationprotocols.InthisextensionoftheDyLOGlanguage,wedeﬁneasDomainDescriptionforagentagi,atriple(Π,CKitagi,S0),whereCKitagiisagicommunicationkit,S0istheinitialsetofagi’sbeliefﬂuents,andΠisatuple(ΠA,ΠS,ΠP),whereΠAisthesetofagi’sworldactionandpreconditionlaws,ΠSisasetofaxiomsforagi’ssensingactions,ΠPasetofaxiomsthatdeﬁnecomplexactions.

4Reasoningaboutconversations

Givenadomaindescription,wecanreasonaboutitandformalizethetemporalprojectionandtheplanningproblembymeansofexistentialqueriesofform:(3)

󰀉p1󰀊󰀉p2󰀊...󰀉pm󰀊Fs

Eachpk,k=1,...,min(3)maybean(atomicorcomplex)actionexecutedbyagioranexternalspeechact,thatbelongstoCKitagi(byexternalwedenoteaspeechactinwhichouragentplaystheroleofthereceiver).Checkingifaqueryofform(3)succeedscorrespondstoansweringtothequestion“isthereanexecutiontraceofp1,...,pmleadingtoastatewheretheconjunctionofbeliefﬂuentsFsholdsforagi?”.SuchanexecutiontraceisaplantobringaboutFs.Theproceduredeﬁnitionconstrainsthesearchspace.

M.Baldonietal./ElectronicNotesinTheoreticalComputerScience105(2004)21–3629

Inpresenceofcommunication,theproblemofreasoningaboutconversationprotocolsisfaced(aconversationisasequenceofspeechacts);indeed,inthecaseinwhichp1,...,pmareconversationprotocols,byansweringtothequery(3)weﬁndaconversationafterwhichsomedesiredconditionFsholds.

Inthecurrentapplicationweaimatﬁndingaconversation,thatallowstoachieveadesiredgoal,whichisaninstanceofthecompositionofmanyprotocols.Conversations,however,usuallycontainget-messageactionsforreceivingmessagesfromotheragents.Sincetheiroutcomeisunknownatplanningtimebecauseagentscannotknowinadvancetheanswersthattheywillreceive,wetreatthemassensingactions.Nevertheless,theexistenceofprotocolsallowsustomakeassumptionsonsuchmessagesandﬁndoutifthereisapossibleconversationthatleadstothegoal.Dependingontheap-plication,itmaybereasonabletochooseanapproachthatallowsustoextractaconditionalplanthatleadstothegoalindependentlyfromtheanswersoftheinterlocutor,aswehavedonein[2].Inthecurrentapplication,instead,weareinterestedinﬁndingalinearplanthatleadstothegoalgivensomeas-sumptionsonthereceivedanswers.Thisweakerapproachdoesnotguaranteethatatexecutiontimetheserviceswillattaintotheplannedconversation,butallowsustoﬁndafeasablesolutionwhenaconditionalplancannotbefound.Forinstance,letusconsideragaintheexampleofSection2.Ifwecomposerestaurant1andcinema1,itispossibletoﬁndaconversationafterwhichtheuser’sdesiresaboutthecreditcardandabouttheuseofpromotionalticketsaresatisﬁed.However,thesuccessoftheplandependsoninformationthatisknownonlyatexecutiontime(availabilityofseats)andthatweassumedduringplanning.Infact,ifnoseatisavailablethegoalofmakingareserva-tionwillfail.Theadvantageisthattheinformationcontainedintheprotocolissuﬃcienttoexcludeanumberofcompositionsthatwillneversatisfythegoal(e.g.restaurant1pluscinema2doesnotpermittoexploitapromotionindependentlyfromtheavailabilityofseats).

Theproofprocedureisanaturalevolutionof[4,3]andisdescribedin[20,2];itisgoal-directedandbasedonnegationasfailure(NAF).NAFisusedtodealwiththepersistencyproblemforverifyingthatthecomplementofamentalﬂuentisnottrueinthestateresultingfromanactionexecution,whileinthemodaltheoryweadoptedanabductivecharacterization.Theproofprocedureallowsagentstoﬁndlinearplansforreachingagoalfromanincompletelyspeciﬁedinitialstate.Thesoundnesscanbeprovedundertheassumptionofe-consistency,i.e.foranyactionthesetofitseﬀectsisconsistent[9].TheextractedplansalwaysleadtoastateinwhichthegoalconditionFsholds.

30M.Baldonietal./ElectronicNotesinTheoreticalComputerScience105(2004)21–36

5Arationalpersonalassistant

Inthissectionwedescribethepersonalassistantpa.Thisagentcomposesasetofwebservicestosatisfytheuser’srequests.Weimaginethesearchandcompositionprocessasdividedintwosteps.Theﬁrststep(notdescribedinthiswork)iskeyword-basedandisaimedatrestrictingtheattentiontoalittlesetofservices,extractedfromaregistrysystem.Thesecondstepisafurtherselectionbasedonreasoning.Duringthissteptheagentpersonalizestheinteractionwiththeservicesaccordingtotherequestsoftheuseranddismissesservicesthatdonotﬁt.Tothisaim,theagentreasonsabouttheprocedurecompservices(apossibleimplementationofitisreportedbelow),thatsketchesthegeneralcomposition-by-sequencingofasetofservices,basedontheinteractionprotocols(service(TypeService,Name,Protocol)),thatwesupposeexplicitlygivenintheservicedescriptionsidentiﬁedbytheﬁrststep.

󰀉compservices([])󰀊ϕ⊃true

󰀉compservices([[TypeService,Name,Data]|Services])󰀊ϕ⊃󰀉Bpaservice(TypeService,Name,Protocol);Protocol(pa,Name,Data);compservices(Services)󰀊ϕ

Intuitively,compservicesbuildsthesequenceofprotocolstoapplyforinter-actingwithasetofservices,sothatitwillbepossibletoreasonaboutthewhole.Thepresentedimplementationisquitesimplebutissuﬃcientasanexampleandgenerallyitcouldbeanyprolog-likeprocedure.Beforeexplain-ingthekindofreasoningthatcanbeapplied,letusdescribetheprotocols,thatarefollowedbythewebservicesofourexample.Suchprotocolsallowtheinteractionoftwoagents,soeachofthemhastwocomplementaryviews:theviewofthewebserviceandtheviewofthecustomer,i.e.pa.Inthefollowingwewillreport(writteninDyLOG)theviewthatpahasoftheprotocols.(a)󰀉reservrest1C(Self,WebS,Time)󰀊ϕ⊂

󰀉yesnoqueryQ(Self,WebS,available(Time));BSelfavailable(Time)?;

getinfo(Self,WebS,reservation(Time));getinfo(Self,WebS,cinemapromo);getinfo(Self,WebS,ftnumber)󰀊ϕ(b)󰀉reservrest2C(Self,WebS,Time)󰀊ϕ⊂

󰀉yesnoqueryQ(Self,WebS,available(Time));BSelfavailable(Time)?;

getinfo(Self,WebS,reservation(Time))󰀊ϕ

M.Baldonietal./ElectronicNotesinTheoreticalComputerScience105(2004)21–3631

(c)[getinfo(Self,WebS,Fluent)]ϕ⊂[inform(WebS,Self,Fluent)]ϕProcedures(a)and(b)describethecustomer-viewoftheprotocolsfollowedbythetwoconsideredrestaurants.Thecustomerasksifatableisavailableatacertaintime,ifso,theserviceinformsthecustomerthatareservationhasbeentaken.Theﬁrstrestaurantalsoinformsthecustomerthatitgainedapromotionalfreeticketforacinema(cinemapromo)anditreturnsacodenumber(ftnumber).

(d)󰀉reservcinema1C(Self,WebS,Film)󰀊ϕ⊂

󰀉yesnoqueryQ(Self,WebS,available(Film));BSelfavailable(Film)?;

yesnoqueryI(Self,WebS,cinemapromo);¬BSelfcinemapromo?;

yesnoqueryI(Self,WebS,payby(ccard));BSelfpayby(ccard)?;

inform(Self,WebS,ccnumber);

getinfo(Self,WebS,reservation(Film))󰀊ϕ(e)󰀉reservcinema1C(Self,WebS,Film)󰀊ϕ⊂

󰀉yesnoqueryQ(Self,WebS,available(Film));BSelfavailable(Film)?;

yesnoqueryI(Self,WebS,cinemapromo);BSelfcinemapromo?;

inform(Self,WebS,ftnumber);

getinfo(Self,WebS,reservation(Film))󰀊ϕ(f)󰀉reservcinema2C(Self,WebS,Film)󰀊ϕ⊂

󰀉yesnoqueryQ(Self,WebS,available(Film));BSelfavailable(Film)?;

getinfo(Self,WebS,payby(cash));

getinfo(Self,WebS,reservation(Film))󰀊ϕ

Clauses(d)and(e)aretheprotocolfollowedbycinema1,(f)istheprotocolfollowedbycinema2.Supposingthatthedesiredmovieisavailable,cinema1alternativelyacceptscreditcardpayments(d)orpromotionaltickets(e).Cin-ema2,instead,doesnottakeparttothepromotioncampaign.Letusnowconsiderthequery:

󰀉compservices([[restaurant,R,dinner],[cinema,C,nausicaa]])󰀊(Bpacinemapromo∧Bpareservation(dinner)∧

Bpareservation(nausicaa)∧Bpa¬BCccnumber∧BpaBCftnumber)

32M.Baldonietal./ElectronicNotesinTheoreticalComputerScience105(2004)21–36

thatamountstodetermineifitispossibletocomposetheinteractionwitharestaurantwebserviceandacinemawebservice,sotoreserveatablefordinner(Bpareservation(dinner))andtobookaticketforthemovieNausi-caa(Bpareservation(nausicaa)),exploitingapromotion(Bpacinemapromo).Theuseralsospeciﬁesthatnocreditcardistobeused(Bpa¬BCccnumber),insteadtheobtainedfreeticketistobespent(BpaBCftnumber),i.e.pabe-lievesthataftertheconversationthechosencinemawillknowthenumberoftheticketgivenbytheselectedrestaurantbutitwillnotknowtheuser’screditcardnumber.Letussupposethatpahasthefollowinglistofavailableservices:

Bpaservice(restaurant,restaurant1,reservrest1C)Bpaservice(restaurant,restaurant2,reservrest2C)Bpaservice(cinema,cinema1,reservcinema1C)Bpaservice(cinema,cinema2,reservcinema2C)

thenthequerysucceedswithanswerRequaltorestaurant1andCequaltocinema1.Thismeansthatthereisﬁrstaconversationbetweenpaandrestaurant1and,then,aconversationbetweenpaandcinema1,thatareinstancesoftherespectiveconversationprotocols,afterwhichthedesiredconditionholds.Agentpaworksonbehalfofauser,thusitknowshiscreditcardnumber(Bpaccnumber)andhisdesiretoavoidusingitinthetransaction(¬Bpapayby(creditcard)).Italsobelievestobeanauthorityabouttheformofpaymentandabouttheuser’screditcardnumberanditbelievesthattheotheragentsareauthoritiesaboutwhattheycommu-nicatebyinformacts.Theinitialmentalstatewillalsocontainthefactthatpabelievesthatnoreservationfordinnernorfornausicaahasbeenbookedyet,Bpa¬reservation(dinner)eBpa¬reservation(nausicaa),thefactthatpadoesnothaveafreeticketforthecinemayet,¬Bpacinemapromo,andsomehypothesisontheinterlocutor’smentalstate,e.g.thebeliefﬂu-entBpa¬Bcinema1ccnumber,meaningthatthewebservicedoesnotalreadyknowthecreditcardnumber.Inthiscontext,theagentbuildsthefollow-ingexecutiontraceofcompservices([[restaurant,R,dinner],[cinema,C,nausicaa]]):

queryIf(pa,restaurant1,available(dinner));inform(restaurant1,pa,available(dinner));inform(restaurant1,pa,reservation(dinner));inform(restaurant1,pa,cinemapromo);inform(restaurant1,pa,ftnumber);

queryIf(pa,cinema1,available(nausicaa));inform(cinema1,pa,available(nausicaa));

M.Baldonietal./ElectronicNotesinTheoreticalComputerScience105(2004)21–3633

queryIf(cinema1,pa,cinemapromo);inform(pa,cinema1,cinemapromo);inform(pa,cinema1,ftnumber);

inform(cinema1,pa,reservation(nausicaa))

Wecaneasilyseethatthereisnootherexecutiontraceofcompservicesthatsatisﬁesthegoals.Thismeansthat,inthesearchspacedeﬁnedbythisproce-dure,itisnotpossibletousewithsuccessanyothercompositionoftheservices(e.g.restaurant1withcinema2)andthisdoesnotdependonthepossibleout-comesofconversations.Observethatarbitrarycompositionsoftheservices,i.e.compositionsthatcannotbefoundasexecutionsofcompservices,maysatisfytheuser’sgoal;inordertoﬁndthemonecoulduseageneral-purposeplanner.However,therearesituationsinwhichonehasageneralschemaforthedesiredsolution,whichishelpfulforreducingthesearchtime.

6RelatedWorks

WebservicecompositionintheDAML-Scontexthasbeenfacedalsobyotherresearchers.ThemostrelevantworkhasbeencarriedonbytheteamofSheilaMcIlraith[6],themaindiﬀerencewithoursbeingthat,whilewecomposewebservicesbyapplyingproceduralplanningtocomplexactions(i.e.proceduresthatencodeconversationprotocols),McIlraith’sservicescorrespondtoatomicactionsonlyandcompositionisbasedontheirpreconditionsandeﬀects.Inparticular,thepreconditionandeﬀect,inputandoutputlistsareﬂat;norelationamongthemcanbeexpressed,soitisimpossibletounderstandifaservicecanfollowvariousinteractions.Indeed,theadvantageofworkingattheprotocolslevelisthatbyreasoningaboutprotocolsagentscanpersonalizetheinteractionbyselectingacoursethatsatisﬁesuser-(orservice-)givenrequirements.Thisprocesscanbestartedbeforetheactualinteractiontakesplaceandcanbeexploitedforwebservicecompositionaswellasforwebservicesearch.

Theideaofworkingonconversationprotocolsderivesfromtheexperienceoftheauthorsinthemulti-agentresearcharea:oneoftheapproaches,ac-tually,consistsinmakingagentsexchangecommunicationprotocolsbeforeinteracting[13].WebasedourworkinamodalactionlogicframeworkandusedtheagentlogicprogramminglanguageDyLOG.Byexploitingnestedbe-liefswetookasubjectiverepresentationofconversationprotocols,inwhichanagentmakesrationalassumptionsonitsinterlocutor’sstateofmind.Noticethat,sinceweareonlyinterestedinreasoningaboutthelocalmentalstate’sdynamics,ourapproachdiﬀersfromotherlogic-basedapproachestocommu-nicationinmulti-agentsystems,astheonetakeninCongolog[22],where

34M.Baldonietal./ElectronicNotesinTheoreticalComputerScience105(2004)21–36

communicativeactionsaﬀecttheglobalstateofamulti-agentsystem.

Fromadiﬀerentperspective,ifweinterpretwebservicesasagents,wecanﬁndawideliteratureaboutcoordinationmodelsandlanguages,e.g.[7],thatsupplytheabstractionsnecessaryforrulingtheinteractionofagentswithacommongoal.Awell-knowncoordinationmodelisTuCSoN[17],whichexploitstuplecentersandthelogic-basedlanguageReSpecT[18]foragentcoordination.Tuplecentersarecharacterizedbyareactivebehavior,thatspeciﬁeshowthecenterrespondstoacommunicationevent.However,thechainreactionistransparenttothecommunicatingagents,whichperceiveresponsesassingle-stepstatetransitionsofthetuplecenter.Alsointhiscontextitwouldbeinterestingtohaveamechanismforreasoningaboutthebehaviorofthetuplecenter.

7Conclusionsandfuturework

Inthisworkwehaveshownsomepossiblebeneﬁtsofreasoningaboutcom-municationprotocolsinthetaskofwebservicecomposition.Inparticular,wehavefocussedonserviceswitharepresentationalaDAML-Sthat,bymakingexplicitthepreconditionsandtheeﬀectsofaservice,practicallyassimilatesittoanaction.Inthisperspectiveanapproachthatexploitsmechanismsforreasoningaboutactionsandchange,likeours,seemsparticularlysuitable.Asexplainedalongthepaper,thefactthatitispossibletoplanacon-versationthatleadstothefulﬁllmentofsomegoaldoesnotimplythatbyitsexecutionthegoalwillactuallybeachieved.Forinstance,thinktothecaseinwhichtheusergotafreeticketbutnofreeseatremainsatthese-lectedcinema.Thefactthatthecinemaisfullybookedisaninformationthatwillbeknownonlyatexecutiontime.Theplannedconversationis,actually,alinearplanthatleadstothegoalgiventhatsomeassumptionsaboutthepossibleanswersoftheinterlocutorarerespectedduringtheinteraction.Ifsuchassumptionsarenotsatisﬁedatexecutiontime,theplanfails.Itwouldbeinterestingtocontinuethepresentedworkintegratinginthisapproachtoservicecompositionamechanismfordealingwithfailureandreplanning.Thisformofreasoningisnecessaryinordertoarrivetorealapplications(e.g.arecommendationsystem)anditcouldtakeintoaccountalsopreferencecrite-riaexplicitlyexpressedbytheuser.Suchcriteriacouldbeusedtorelaxsomeoftheconstraintsincasenoplancanbefoundorwhenaplanexecutionfails.

References

[1]M.Baldoni,C.Baroglio,A.Martelli,andV.Patti.Reasoningaboutinteractionforpersonalizingwebservicefruition.InG.Armano,F.DePaoli,A.Omicini,andE.Vargiu,

M.Baldonietal./ElectronicNotesinTheoreticalComputerScience105(2004)21–3635

editors,Proc.ofWOA2003:Daglioggettiagliagenti,sistemiintelligentiecomputazionepervasiva,Villasimius(CA),Italy,September2003.PitagoraEditriceBologna.

[2]M.Baldoni,C.Baroglio,A.Martelli,andV.Patti.Reasoningaboutselfandothers:communicatingagentsinamodalactionlogic.InProc.ofICTCS’2003,volume2841ofLNCS,pages228–241.Springer,2003.[3]M.Baldoni,L.Giordano,A.Martelli,andV.Patti.ProgrammingRationalAgentsinaModalActionLogic.AnnalsofMathematicsandArtiﬁcialIntelligence,SpecialissueonLogic-BasedAgentImplementation.Toappear.[4]M.Baldoni,L.Giordano,A.Martelli,andV.Patti.ReasoningaboutComplexActionswithIncompleteKnowledge:AModalApproach.InProc.ofICTCS’2001,volume2202ofLNCS,pages405–425.Springer,2001.[5]P.BretierandD.Sadek.Arationalagentasthekernelofacooperativespokendialoguesystem:implementingalogicaltheoryofinteraction.InJ.P.M¨uller,M.Wooldridge,andN.R.Jennings,editors,IntelligentAgentsIII,proc.ofECAI-96WorkshoponAgentTheories,Architectures,andLanguages(ATAL-96),volume1193ofLNAI.Springer-Verlag,1997.[6]J.Bryson,D.Martin,S.McIlraith,andL.A.Stein.Agent-basedcompositeservicesinDAML-S:Thebehavior-orienteddesignofanintelligentsemanticweb,2002.[7]P.CiancariniandJ.Wooldridge,editors.AgentOrientedSoftwareEngeneering(AOSE2000),volume1957ofLNCS.Springer-Verlag,2000.[8]DAML-S.http://www.daml.org/services/daml-s/0.9/.version0.9,2003.

[9]M.DeneckerandD.DeSchreye.RepresentingIncompleteKnowledgeinAbductionLogicProgramming.InProc.ofILPS’93,Vancouver,1993.TheMITPress.[10]G.DeGiacomo,Y.Lesperance,andH.J.Levesque.Congolog,aconcurrentprogramming

languagebasedonthesituationcalculus.ArtiﬁcialIntelligence,121:109–169,2000.[11]A.HerzigandD.Longin.

AMSTELOGUE99,1999.

Beliefsdynamicsincooperativedialogues.

InProc.of

[12]H.J.Levesque,R.Reiter,Y.Lesp´erance,F.Lin,andR.B.Scherl.GOLOG:ALogic

ProgrammingLanguageforDynamicDomains.J.ofLogicProgramming,31:59–83,1997.[13]A.MamdaniandJ.Pitt.Communicationprotocolsinmulti-agentsystems:Adevelopment

methodandreferencearchitecture.InIssuesinAgentCommunication,volume1916ofLNCS,pages160–177.Springer,2000.[14]J.Maurer,editor.ACMQueue.ACM,march2003.

[15]S.McIlraithandT.Son.AdaptingGologforProgrammintheSemanticWeb.In5thInt.

Symp.onLogicalFormalizationofCommonsenseReasoning,pages195–202,2001.[16]JamesH.Odell,H.VanDykeParunak,andBernhardBauer.Representingagentinteraction

protocolsinUML.InAgent-OrientedSoftwareEngineering,pages121–140.Springer,2001.http://www.ﬁpa.org/docs/input/f-in-00077/.[17]A.OmiciniandF.Zambonelli.CoordinationforInternetapplicationdevelopment.Journal

ofAutonomousAgentsandMulti-AgentSystems,2(3),1999.SpecialIssueonCoordinationMechanismsandPatternsforWebAgents.[18]AndreaOmiciniandEnricoDenti.FormalReSpecT.InMariaChiaraMeo,editor,2000Joint

Conf.onDeclarativeProgramming(AGP’00),LaHabana(Cuba),4–7December2000.[19]OWL.http://www.w3c.org/tr/owl-guide/.2003.

[20]V.Patti.ProgrammingRationalAgents:aModalApproachinaLogicProgrammingSetting.

PhDthesis,DipartimentodiInformatica,Universit`adegliStudidiTorino,Torino,Italy,2002.Availableathttp://www.di.unito.it/~patti/.

36M.Baldonietal./ElectronicNotesinTheoreticalComputerScience105(2004)21–36

[21]RDF.http://www.w3c.org/tr/1999/rec-rdf-syntax-19990222/.1999.

[22]S.Shapiro,Y.Lesp´erance,andH.J.Levesque.Specifyingcommunicativemulti-agentsystems.

InAgentsandMulti-AgentSystems-Formalisms,Methodologies,andApplications,volume1441ofLNAI,pages1–14.Springer-Verlag,1998.[23]WSDL.http://www.w3c.org/tr/2003/wd-wsdl12-20030303/.version1.2,2003.

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文