[Gbbopen-list] Blackboard systems and constraint-based programming

[Dan Corkill]

> It is not that I know much about constraint-based programming in general,
> or Cells in particular, but I wondered how this would mix with a
> blackboard system such as GBBopen.
> 
> Obviously one could [trigger?] each of ones KSs from a constraints oriented
> perspective but I am here thinking more in terms of utilising a
> standalone library such as Cells directly within the blackboard
> structure.
> 
> The problem I am having problem getting the grips on is that a CB
> program has a number of rules that links objects or cells such that if
> you change one object, changes will ripple across the model absed on
> these rules. If one modifies a blackboard object, events are generated
> that will feed into the selection of the next KS.
> 
> Would the combination work? What I would expect should, if this was ot
> work, would be that a single change to a blackboard object (that was
> also a cell) would generate both one event, then a change to a dependent
> cell with would generate yet another event and so on.

OK, I'll bite.

First, consider constraint-based programming as a special case of 
method-based (or event-based) computation.  How this all relates to a 
blackboard system goes as follows: suppose some computation COMP needs to 
be done when an particular thing is done to an object (an event).  I could 
implement this in a number of ways.  I could use CLOS to add an :after 
method that would cause COMP to be done when the "thing" is done to object 
(modifying it, changing it, deleting it, whatever).  Then COMP becomes part 
of doing the "thing"--always and unconditionally.

Or, if I was using GBBopen, I could elect not to use CLOS methods to 
implement this, but instead use GBBopen's event-function mechanism to 
accomplish the same thing.  (Event functions also always happen, but 
multiple event functions can be attached/detached from the same "thing" and 
object class(es) and event functions have a dual unit/event-class 
propagation behavior rather than a strict class-inheritance behavior.) 
Again, COMP effectively becomes unconditionally part of "thing".

At the other extreme, I could make COMP be a KS.  In this case, only the 
triggering of the KS becomes part of "thing."  Whether (and when) COMP is 
done is under the deliberation of the blackboard-system control shell.  Why 
would we ever want to do this?  Suppose COMP is expensive: if not directly, 
through the transitive propagation to COMPs associated with doing "things" 
to other objects based on the "things" that it does.  Maybe we would like 
to decide to defer doing COMP (because it is not so important now or 
because we expect more "things" will be done soon that will also trigger 
COMP on the same object).  Maybe we would like to do COMP, but defer or 
stop some of the downstream "transitive" things resulting from performing 
COMP.  Maybe we only want to do the most important, state changing COMPs 
(or do them first).

All of the above assumed that the triggering of COMP was simple and 
consistent (that its invocation was a simple rule).  The more complex the 
"rule(s)" associated with triggering COMP, the harder it is to implement 
the decision in a method or instantaneous event function invocation. 
Complex conjunctive rules are particularly onerous (and can lead to lots of 
partially completed invocation patterns if a basic pattern-matching 
approach is used to implement the rule(s)... but that's another topic!)

OK, now let's get back to constraint-based programming.  The central idea 
here is to limit the various COMP(s) and rules on them to be such that 
there is always a consistent state (no infinite transitive application 
cycles) and to potentially use knowledge of the constraint relationships to 
sequence COMP application (and sometimes even make it lazy rather than 
simply automatic and more computationally optimal).

So, let's say that we have a high-quality constraint-programming library 
that we'd like to integrate with GBBopen BB objects (either with or without 
a control shell operating).  If the library is nicely integrated with CLOS, 
then this should be very doable.  The library could take care of 
propagating constraint-based value computations between objects and other 
methods.  In addition, GBBopen event-functions or KSs could be triggered 
based on some of the changes made by the constraint-programming library 
(which might change other non-constraint-based values based on these 
changes)--a kind of mixed-paradigm strategy where constraint-based actions 
are part of the "cost" of doing some "things" and, at least in the case of 
KSs, other computations are controlled separately and deliberatively by the 
control shell.

There's another form of "mixed-mode" that is also possible, depending on 
whether the constraint-programming library can have its propagation 
machinery controlled.  If it allows propagation to be "deferred," then 
performing such propagation can be made a KS.  In this way, actions by KSs 
(and external events) can be done to objects and the "deterred" 
constraint-programming machinery would record them.  Then the control shell 
can decide when it is time to have constraint propagation occur relative to 
other things.  The benefits here are that 1) if the library is maintaining 
a list of changes for deferred propagation, it can potentially better 
optimize the propagation (once it is invoked to do so) if there are a 
number of changes to individual objects and 2) minor changes can be held as 
"deferred" rather than propagated if they are not likely to change the 
applications decision-making activities.

Being able to target the "things" that should trigger KSs (versus those 
that trigger constraint-based value propagation) is key to either "mixed" 
approach.  Sometimes it can be as simple as a partitioning of object 
attributes into constraint-based and non-constraint based categories.

-- Dan

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.