DL & Configuration

From: David Brown 
To: configuration@lia.di.epfl.ch
Date: Tue, 19 Nov 1996 20:42:58 -0500


	* We had nice tutorials on Description Logics (DL) and
	  Constraint Satisfaction Problems (CSPs), and I remember Dave
	  Brown trying to find out where the "real" difference between
	  DL an CSPs for configuration comes from? Perhaps Dave has
	  the answer meanwhile??

	  Rainer Weigel, Mon, 18 Nov 1996 14:06:36 +0100


My concern, which Im still not sure I communicated well enough, was to
try to establish why, as claimed, DL was "good for configuration
problems".  

This is obviously very important, as we want to use appropriate tools
for the job -- especially if they make the job `easier'.  

My understanding of the responses to my questions about DL was that
they were of two kinds (Deborah, and other DL folks, please correct me
here, as I'm certainly no DL expert!):

1. that DL provides all sorts of Kn.Acq. advantages, such as automatic
categorizing of new concepts, completeness checking, places to hang
rules, and other "neatness" support.  

2. that DL provides some reasoning actions that "fit" the
configuration problem-solving process.  

Now 1 above sounds great to me, but probably applies equally well to
diagnosis, or interpretation knowledge.  It's clearly a strong point
of DL, and would be useful for configuration systems as well. 

Wrt 2, if I remember correctly, the claim was that DL was able to
"recognize" that a description of a configuration was both correct and
complete, and maybe also suggest what was wrong or what was missing.

Correctness would, in general, be the compatability of each component
with the others, as well as the ability of the configuration to
satisfy the requirements (perhaps including fnl reqs).

Completeness would be concerned with satisfying the requirements
introduced by the components included in the configuration -- i.e.,
each component added to the configuration has things it requires
(e.g., inputs, space, connections) that must be satisfied for the
configuration to be complete. It would also be concerned with ensuring
that ALL the requirements have been satisfied (especially if there is
a required functionality). 

Suggesting what is wrong or what is missing is obviously an important
ingredient of the process.  If DL does this _in general_ then it
provides a large amount of power in the configuration process. 

In my talk I tried to suggest that the configuration process varied
enormously depending on what was known in advance about the process or
the answer.  If a Template of associations between component types is
known in advance, then much of the determination of compatibility
between types is removed from the problem.  The search space for
finding the configurations is reduced.  The problem reduces to finding
instances of the component types, and finding arrangement relations
that refine the association relations from the template. (Im not
suggesting this is necessarily trivial).

In the talk Robert Weida gave he described the ubiquitous HiFi example
of configuration.  In that talk the configuration process appeared to
be one of finding an instance for a concept, where that concept
described what types of components were present in the configuration,
and what the associations were between them -- associations because it
didnt appear as though they were described in terms of location,
merely attachment (or did I imagine that?).

Hence, the power was being 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. 

So that's a nice property.

An issue is how many configurations problems are like that.
I'm not claiming to know. 

Suppose one were faced with the worst possible case -- with
parameterized components, where not all need be used, and there is no
existing template.  This could probably be characterized as the
"general configuration problem".  (Do people agree?)

In that case does DL assist in any way other than described in "1"
above?


Regards,
	Dave Brown