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