DAML Ontologies for Agent-Enabled Web Services Sheila A. McIlraith Knowledge Systems Laboratory (KSL) Department of Computer Science Stanford University (withTran Cao Son and Honglei Zeng) Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Background The Web is evolving from a provider of documents and images … Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Background … to a provider of services Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Background Knowledge Rep’n for the “Semantic Web” DAML-L (Logic) DAML+OIL (Ontology) RDFS (RDF Schema) RDF (Resource Description Framework) XML (Extensible Markup Language) [Fensel+others, 2000] Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Overview of Our Work Today’s Web is designed primarily for human use. Problem: The Web is not computer-interpretable Æ Precludes easy automation of tasks We are developing: • semantic markup to enable automation by making service capabilities, user constraints & procedures computer-interpretable & use-apparent. • agent technology that exploits semantic markup to support automated Web service discovery, execution, composition and interoperation. Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Goal Automation of: • Web service discovery Find me an airline service that offers flights to Tuktoyuktuk Req’d Markup: declarative advertisements • Web service execution Buy me “Harry Potter and the Sorcerer’s Stone” at www.amazon.com Req’d Markup: declarative API (inputs & outputs) • Web service selection, composition and interoperation Make the travel arrangements for my WWW10 conference Req’d Markup: declarative use spec. (preconditions & effects) Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Goal Automation of: • Web service discovery i n g Find me an airline service that offers w L)to Tuktoyuktuk roflights t s g A M f for ith D Req’d Markup: declarative advertisements e ry roving w s t I ndu re imp • Web service execution e a (w Buy me “Harry Potter and the Sorcerer’s Stone” at www.amazon.com a Are Req’d Markup: declarative API (inputs & outputs) n it y rt u p o O p • Web service selection, composition and interoperation Make the travel arrangements for my WWW10 conference Req’d Markup: declarative use spec. (preconditions & effects) Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Semantic Markup: DAML-S DAML-S**: A DARPA Agent Markup Language for Services • AI-Inspired markup language for Web services: • well-defined semantics • ontologies support reuse, mapping, succinct markup, ... • Developed by a coalition of researchers from Stanford, SRI, CMU, BBN, and Nokia, under the auspices of DARPA. • Pre-release of DAML-S version 0.5 scheduled for June,2001 • Watch http://www.daml.org/services/daml-s for details ** (initiated 02/2001 following independent research efforts) Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Layered Language Development DAML-SL DAML-S (Services) DAML-L (Logic) DAML+OIL (Ontology) RDFS (RDF Schema) RDF (Resource Description Framework) XML (Extensible Markup Language) [Fensel+others, 2000] Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Semantic Markup of Web Services Each Web site provides a set of services • information providing (e.g., flight schedules, camera views) &/or • world-altering (e.g., flight booking, home temp. adjustment) Web service sites are annotated with DAML markup. Service described as processes (sequence, if-then-else, while, iteration, …) of • inputs & outputs (function metaphor) • preconditions & effects (action metaphor) DAML-enabled web pages Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Function/Dataflow Metaphor Input: Output: • customer name • confirmation no. • flight number • ... • credit card www.acmeair.com • ... book flight service flight available Y + ? valid credit card N • failure notification •… Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 AI-inspired Action/Process Metaphor Output: • confirmation no. • ... Input: • customer name Effect: • ticket purchased • flight number • credit card debited • credit card www.acmeair.com • ... • ... book flight service flight available Y + ? Preconditions: valid credit card N • knowledge of the input • failure notification • own credit card Output: •… • ... Effect: Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Process of Processes Input & Output & www.acmetravel.com Effects Preconditions book travel service • • confirmation no. • ... • • • • • • • • customer name • location www.acmecar.com ? • • • car type book car service • dates • • credit card no. • ... • • • • • failure notification •… • • • • • • • • • • confirmation no. ? • • • • ... • • • • • confirmation no. • confirmation no. • dates www.acmehotel.com ? • • ... • • room type book hotel service • credit card no. • • customer name • ... • • • flight numbers www.acmeair.com ? • • dates book flight service • credit card no. • failure notification • •… • ... • failure notification • errror information •… Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Web Services Markup Exploits Ontologies Ontologies support sharing, reuse, succinct markup: process purchase customer-name know(customer-name) Web Service purchase-plane-ticket Ontologies flight-no credit-card know(flight-no) own(credit-card) DAML-enabled web pages purchase-UAL-plane-ticket purchase(ticket) debit(credit-card) ... Collectively markup create a distributed KB of services. Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Semantic Web Services DAML PDDL-like DAML • parameters • input • (conditional) output DAML DAML • preconditions • (conditional) effects DAML DAML within a process model DAML DAML DAML DAML DAML DAML DAML DAML DAML DAML DAML DAML Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Objective Problem: Automated Web Service Composition E.g., Make the travel arrangements for my IJCAI’01 conference Approach: I. Plan a sequences of services that realize user’s objective. (NP complete or worse) II. Customize reusable generic procedures - Define and archive reusable generic procedures - Customize with user’s constraints. (NP complete or worse in a reduced search space) Advantages: efficiency, ease of use, customization Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Generic Procedures Desiderata for Generic Procedures Generic: High degree of non-determinism to accommodate customization. Customizable: Easily customizable by individual users. (Re)Usable: Usable by agents w/ different levels of knowledge Î Self-sufficient wrt required knowledge. Claim: Golog is natural formalism for creating generic procedures Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Realizing Generic Procedures in Golog Situation Calculus [McCarthy, 68] + S0 Golog [Levesque et al, 97] rent-car get-plane-sched procedural constructs: ... ... • sequencing • if-then-else buy-plane-ticket buy-plane-ticket • nondeterministic choice rent-car rent-car • while-do, etc. ... ... ... E.g., Book-travel(origin,dest,date-d,date-r,purpose) pick-one-of Book-plane(origin,dest) | Drive(origin,dest) | Book-train(origin,dest) end pick; end Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Customizing User Constraints Generic procedures can be further constrained by DAML-defined user constraints S0 • personal constraints/preferences, rent-car get-plane-sched • group constraints, or ... ... • instance-specific constraints. buy-plane-ticket buy-plane-ticket rent-car rent-car ... ... ... E.g., • Bob would like to drive if the driving distance is less than 3 hours. • KSL business air travel should be on an American carrier. ... Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Deductive Instantiation Web Services Model & User Constraints + Generic Procedure (Situation Calculus + State Constraints) (Golog) Model-Based Program nondeterministic spectrum deterministic 9 constrains search 9 eliminates search theorem proving Sequence of Web Services Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Architecture Web Procedures Web Service Ontologies Ontologies Agent Broker DAML-enabled DAML-enabled personal/company web pages constraints and prefs E-mail ... Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 How it Works Agent’s KB is automatically constructed relative to the generic procedure and user constraints. Deductive machinery instantiates the generic procedure wrt. constraints and world state to generate Web service requests that the agent broker executes. Middle ground interpreter balances information gathering services with delayed execution of world-altering services. Agent’s KB is updated by Web service responses. Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Properties of Our System Logical-based approach enables us to enforce and/or prove properties of our system: - safety constraints - goal achievement - maintenance constraints Implementation of middle ground interpreter is sound & complete with respect to logical specification. Characterization of classes of procedures that are knowledge self-sufficient. Proved properties wrt execution termination. Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Status 9 DAML = First-order logic and some DAML+OIL (soon to be DAML-S) 9 Agent KB representation language = Situation Calculus 9 Generic procedures representation language = Golog 9 Deductive machinery = ConGolog interpreter written in Prolog 9 Agent Broker = Open Agent Architecture [SRI] Procedures Service 9 Web Service output = HTML + W4 info extraction Ontologies Ontologies (eventually DAML) Agent Broker 9 Prototype agent/agent broker constructed. Constraints & Prefs Web Services E-mail ... 9 Preliminary service ontology constructed. KB Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Demo: Dynamic UI with DAML+OIL Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Behind the Scenes Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Behind the Scenes Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Behind the Scenes Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Behind the Scenes Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Behind the Scenes Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Behind the Scenes Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Behind the Scenes Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Behind the Scenes Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Agent e-mails itinerary to customer Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Agent e-mails itinerary to customer Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Agent e-mails itinerary to customer Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Agent e-mails itinerary to customer Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Agent e-mails itinerary to customer Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Agent creates expense claim for customer Writing “DAML”! Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Summary 1) DAML Markup of Web Services, User Constraints, Agent Procedures: • Computer-interpretable, use-apparent, agent-enabled services. • Ontologies facilitate construction, sharing, reuse, and composition; support succinct web site markup. • Markup not specific to particular agent implementation. 2) Agent Technology for Automated Web Service Composition: • Theme: usability and customization • Approach: Generic procedures and customizing user constraints • Deductive machinery instantiates procedures generating web service requests that are sent to the agent broker. • Procedures & deductive machinery provide middle ground between planning & programming. • Logic-based approach enables verification wrt. certain properties, soundness and completeness guarantees. Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Related Work Industrial Initiatives • UDDI • WSDL • ebXML • XLANG • .Net, Biztalk, e-speak, etc. Academic Research (incomplete) • Golog variants [Levesque et al., 97], [de Giacomo & Levesque, 99] • SRI work on Web services [Denker et al., 01], [Waldinger, 00] • University of Washington softbot work [Etzioni et al., 94] • IBROW3 [Benjamins et al., 98] • Lark [Sycara et al., 99], • Ubiquitous Computing [Weiser, 96], etc. Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001 Want to Learn More? High-level overview: McIlraith, Son and Zeng, “Semantic Web Services”, IEEE Intelligent Systems (special issue on the semantic web), 16(2):46-53, 2001. Some composition details: McIlraith and Son, “Adapting Golog for Programming the Semantic Web”, Proceedings Symposium on Logical Formalizations of Common Sense Reasoning (Common Sense 2001), to appear, 2001. Papers: http://ksl.stanford.edu/people/sam/publications.html KSL’s DAML project: http://www.ksl.stanford.edu/Projects/DAML/ DAML-S: http://www.daml.org/services/daml-s/ DAML Program: http://www.daml.org/ Copyright © Sheila McIlraith, 2001 OAS 2001 05/29/2001