[1-13] Constraints and Rule-Based (Production) Systems

Milind Tambe <tambe@isi.edu> writes: Many researchers have explored
the possible integration of constraint satisfaction techniques/methods
and production (rule-based) systems. The integration has been explored
in the context of both backward chaining[1] and forward-chaining
systems (see below).

This short note focuses on one aspect of this integration: constraints
and forward-chaining production systems. These forward chaining systems
execute tasks by going through recognize-act cycles: in the recognize
or match phase, productions or rules match with working memory (a
database of facts) and in the act phase, the matched productions are
fired, causing changes to working memory, in turn causing the system to
execute the next recognize act cycle. Integration of constraints with
such systems is possible at multiple levels. At a higher level, the
integration with constraints may involve a shift in the recognize-act
cycle. For instance, constraint-satisfaction techniques may be used in
addition to the recognize-act cycle to define values in working
memory[2]. At this higher level, constraints do not change the
recognize-act cycle itself. At a lower level, however, the integration
with constraints may involve a change in the recognition procedure,
i.e., the procedure used to match productions with working memory. More
specifically, the problem of matching conditions of productions with
working memory can be mapped over onto constraint satisfaction
problems. Techniques such as arc-consistency, path-consistency or
others may then be used either to reduce the match cost of productions
by quickly eliminating easily detectably inconsistencies, or
alternatively even to substitute for the matching procedure[3].

1. "Concurrent constraint programming languages", V. Saraswat, PhD
Thesis, 1989, School of Computer Science, Carnegie Mellon University,
Pittsburgh, PA.

2. "Constrained heuristic search" M. Fox, N. Zadeh & C. Baykan,
IJCAI-89, pp 309-315.

3. "Investigation production system representations for non-
combinatorial match" M. Tambe & P. Rosenbloom, Artificial Intel.,
Volume 68, Number 1, 1994.