DL & Configuration (2)

From: Robert Weida 
To: configuration@lia.di.epfl.ch
Subject: Re: WS Summary 
Date: Thu, 21 Nov 1996 08:41:45 -0500

I'll take a shot at answering the question:  

	Why is description logic (DL) good for configuration problems?

First, I should emphasize that DL is not monolithic.  The DL community
has studied and implemented an assortment of description logics
which make different tradeoffs between the expressiveness of their
description language and the ease of reasoning with that
language. (Complexity results are known for a wide variety of DL
languages.)  The "best" tradeoff depends on the application, e.g.,
what aspects of a configuration do you want to describe, and what kind
of performance is required?  In addition, many special-purpose
extensions to description logics have been investigated.  For example,
explicit handling of part/part-of reasoning is currently receiving a
great deal of attention from DL researchers.

Regarding the utility of DL, I like to distinguish between the
knowledge engineering and problem solving phases.  As Dave Brown
suggested, DL provides considerable support for knowledge acquisition
and knowledge engineering.  For example:

   - DL is a useful tool for describing systems, components,
     functionality, etc.  Descriptions encompass a "terminology"
     composed of concepts (classes) as well as individuals.  Generic
     DL language constructs which are quite handy for configuration
     include role hierarchies, inverse roles, disjointness classes,
     and so on. 

   - A classification facility automatically organizes descriptions of
     systems, components, etc., into an explicit taxonomy based on
     subsumption inferences.  Therefore, the taxonomy is known to be
     internally consistent.  Consistency is maintained over time as new
     descriptions are classified, and existing descriptions are
     modified and reclassified (along with their dependents) as needed. 
     DL implementations are optimized to do this work efficiently. 
  
   - Redundant, incoherent, and vacuous descriptions are automatically
     identified.

   - The taxonomy's subsumption-based organization enables efficient
     retrieval of descriptions through formulation and incremental
     reformulation of "query" concepts.  It also ensures that
     descriptions will be found in predictable locations when browsing
     via navigation of taxonomic links.

   - The strict nature of the taxonomy fosters sound knowledge
     engineering practices (in my opinion). 

   - The taxonomy constitutes a so-called "conceptual coat rack" for
     hierarchical organization of rules, compatibility relations, etc.
     Importantly, the taxonomy's subsumption-based organization
     enables the system to locate these things, reason about their
     consistency, and so on.
	
All of these knowledge engineering benefits are independent of the
chosen problem solving strategy.  In addition, DL has much to
offer during the problem solving phase.  There are several
possibilities.  One is for a generic DL system to solve the entire
configuration problem.  The HiFi application described by Deb
exemplifies (I believe) this approach, where data-driven rules attached
to concepts at the appropriate level of abstraction can extend and
refine the description of an individual configuration as required.
In some cases, a domain-specific control mechanism external to the DL
system may be used for efficiency.  For example, it has been 
reported that AT&T's Prose system employs a search strategy which
"appears to be related to iterative deepening."  The advantages and
disadvantages of rule-based systems are well known; in any case, using
DL for configuration problem solving does not necessarily imply using
rule-based reasoning.

Since DL systems are customized for efficient taxonomic reasoning
about descriptions, they are quite useful during problem solving to
reason with (partial descriptions of) systems, components,
functionality, etc. at varying levels of abstraction.  Thus they can
provide run-time support for many (all?) kinds of configuration
engines.  In particular, DL integrates rather nicely with CSP when
DL concepts are identified with CSP variables.


My paper in the proceedings attempts to present some additional ways
in which a DL system can help during problem solving with respect to
an individual configuration.  They include (1) efficiently tracking
the types of systems, components, etc., that are consistent with
current choices, (2) inferring constraints that follow from current
choices and the terminology's specific contents, (3) appropriately
restricting future choices, (4) characterizing the most general
choices available for refining a particular individual's description,
and (5) deciding if an individual's current description can be
considered finished in the sense of being fully and concretely
specified.  Of course, this last determination is valid to the extent
that the descriptions capture the essential aspects of a
configuration.  Speaking to one of Dave's specific questions, DL
systems can certainly handle location relationships such as placement
of boards into slots.  On the other hand, a special purpose extension 
might be required for (say) complex spatial reasoning.  Some DL
systems have been carefully designed to provide clean interfaces for
extensions like that.


Concerning another topic which Dave raised, it is important to
distinguish between general-purpose DL systems and their use as part
of a configuration application.  A DL system may not not completely by
itself "suggest what was wrong or what was missing" in a configuration
specification, but it can provide substantial assistance for doing so,
e.g., detection of incoherent descriptions, built-in explanation
services, and "difference" inferences. 

If we set aside for a moment the rule-based reasoning capabilities of
DL systems, I would roughly agree that a lot of the power of DL for
configuration problem solving is 'obtained by the "fit" between the
existing template (the configuration concept node), and DL's ability
to recognize correct and complete instances of that template.'


As for Dave's "worst possible case -- with parameterized components,
where not all need be used, and there is no existing template", there
is no problem in DL with omission of optional components.  When
there is no existing template for the overall configuration, I imagine
that there will still be templates for (at least some of) the
subsystems and/or base components, where the power of DL applies.  In
the extreme case, if there are no existing templates for anything,
then of course the problem is truly hard.  Then, I suppose a great
deal of knowledge acquisition and knowledge engineering would have to
be incorporated into the problem solving process.  I have tried to
argue above that DL is valuable for those activities, but haven't
thought much about using DL for design problems.


In conclusion, I would certainly not say that DL is a total solution
for every configuration problem, but rather that DL systems can play a
crucial role in many kinds of configuration systems, such as CSP-based
systems, both during knowledge engineering and during problem solving.

Regards, 
Tony Weida