Transcript DL-font-changed

74.419 Artificial Intelligence 2004
- Description Logics • Background and Motivation for DL
• Relation between DL and FOPL
(extensional Semantics)
• Example Definitions
• The horrible truth of DL
• T-Box, A-Box
• LOOM
Description Logics - Background
• Prevent flaws of Semantic Networks; provide
clear semantics of nodes and links
• Derived from Inheritance Hierarchies (IS-A
hierarchies; taxonomies; terminologies) and
Frame Systems  Concepts, Roles, Features
• Series of KR Languages starting with KL-ONE,
later KL-TWO, LOOM, CLASSIC, ...
• Relate to FOPL via extensional semantics
• Applied e.g. in Semantic Web Languages
(DAML+OIL)
Description Logics - Overview
• DL provide language constructs to define
concepts.
• Concepts are interpreted as sets of individuals
(extensional semantics).
• Concept definitions are linear expressions,
combining concepts, roles, etc. to express
constraints on the fillers of the concept.
• The IS-A hierarchy is reflected in the subsumption
relation (super-class–sub-class relation),
interpreted through set-inclusion.
Description Logics – Basic Elements
•
•
•
•
•
Concepts
Roles
Features / Attributes
Definition of concepts
e.g. father(AND (Parent Man)), Biped (AND
(Animal (exactly 2 has-legs Legs)))
• Primitive / Atomic Concepts and Roles (not
completely defined)
• Individual Concepts (define singletons)
• Instances (entities)
Description Logics – Principles
Concepts
• correspond to unary predicates or sets
Roles
• correspond to binary predicates / relations
Features
• correspond to functions
Concept-Definitions
• constrain filler-sets
• composed of concepts, roles, role restrictions
using AND, OR, min-number, max-number etc.
• (Human (AND (Animal Biped Featherless))
Concept Definitions - Example
(defconcept Person primitive-concept)
I (Person)  D
(defrole gender atomic-role)
I (gender)  DD
(defconcept Parent (AND Person (has-child.Person))
I (Parent)  I (Person)  {xD | y: (x,y) 
I (has-child)  y I (Person) }
(defconcept Man (AND Person (gender.Male))
I (Man)  I (Person)  {xD | y: (x,y)  I(gender)
 y  I (Male)}
Basic Architecture and Functions
• T-Box – terminological knowledge (definition
of concepts)
• A-Box – assertional knowledge (statements
about instances, concrete objects)
• Classification - insert concept into hierarchy
based on it's description / definition
• TELL – insert knowledge into KB, e.g. define
new concept or assert instance info
• ASK – querying KB,
e.g. ask about
existence of instance
LOOM - T-Box Example
T-Box (Concept Definitions)
(defconcept Person)
(defrelation has-child :domain Person :range
Person)
(defconcept Male)
(defconcept Person-with-Sons
:is (:and Person (:at-least 1 has-child Male)))
(defconcept Person-with-Two-Sons
:is (and Person (:exactly 2 has-child Male)))
LOOM - A-Box Example
A-Box (Assertions, Statements)
(tell (Person Fred))
(tell (has-child Fred Sandy))
(tell (Male Sandy))
LOOM - Example KB
(defconcept Person)
(defrelation has-child :domain Person :range
Person)
(defconcept Male)
(defconcept Person-with-Sons
:is (:and Person (:at-least 1 has-child Male)))
(defconcept Person-with-Two-Sons
:is (and Person (:exactly 2 has-child Male)))
(tell (Person Fred))
(tell (has-child Fred Sandy))
(tell (Male Sandy))
LOOM - Example Reasoning
(defconcept Person)
(defrelation has-child :domain Person :range
Person)
(defconcept Male)
(defconcept Person-with-Sons
:is (:and Person (:at-least 1 has-child Male)))
...
(tell (Person Fred))
(tell (has-child Fred Sandy))
(tell (Male Sandy))
(Person-with-Sons Fred)
Conclude:
LOOM - Program: definitions
> (defconcept air-base :is-primitive
(and Military-Installation
(exactly 1 name)
(at-least 1 runway-length)
(exactly 1 service-branch)))
|C|AIR-BASE
> (defrelation name :range string)
|R|NAME
> (defrelation runway-length
:domain air-base :range number)
|R|RUNWAY-LENGTH
LOOM - Program: tell
> (tellm (create ab-1 air-base)
(name ab-1 "Atlanta NAS")
(runway-length ab-1 12050)))
Recognition changes at agent time 1:
entry: AB-1 |C|MILITARY-INSTALLATION
entry: AB-1 |C|AIR-BASE
> (tellm (create ab-2 air-base)
(name ab-2 "Mainland NAS")
(runway-length ab-2 9000))
Recognition changes at agent time 2:
entry: AB-2 |C|MILITARY-INSTALLATION
entry: AB-2 |C|AIR-BASE
infered
LOOM - Program: retrieve
> (retrieve ?p (air-base ?p))
( |I| AB-1 |I| AB-2 )
Instances AB-1, AB-2
> (retrieve ?p
(and (air-base ?p)
(for-some (?l) (and (runway-length ?p ?l)
(> ?l 10000)))))
( |I| AB-1 )
Instance AB-1
LOOM - Methods and Rules
(defconcept damaged-road
:is (and road (the path-status
(or "damaged" "unusable"))))
(defmethod send-status-message (?obj ?to ?contents)
:title "Send a Message about an Object"
:response ((format t "To: <.>" ?to ?obj ?contents)))
(defproduction P1-Report-Bad-Road
:when (detects (damaged-road ?road))
:perform (send-status-message ?road
"Planning Team" "is seriously damaged"))
References
• Ian Horrocks and Ulrike Sattler: Description
Logics - Basics, Applications, and More
• J. Heinsohn et al.: An Empirical Analysis of
Terminological Representation Systems,
Artificial Intelligence 68(2):367-397, 1994
• LOOM (Bob McGregor, USC)
http://www.isi.edu/isd/LOOM/LOOM-HOME.html
see course web page for links