Exact Learning of Qualitative Constraint Networks from Membership
  Queries
  A Qualitative Constraint Network (QCN) is a constraint graph for representing
problems under qualitative temporal and spatial relations, among others. More
formally, a QCN includes a set of entities, and a list of qualitative
constraints defining the possible scenarios between these entities. These
latter constraints are expressed as disjunctions of binary relations capturing
the (incomplete) knowledge between the involved entities. QCNs are very
effective in representing a wide variety of real-world applications, including
scheduling and planning, configuration and Geographic Information Systems
(GIS). It is however challenging to elicit, from the user, the QCN representing
a given problem. To overcome this difficulty in practice, we propose a new
algorithm for learning, through membership queries, a QCN from a non expert. In
this paper, membership queries are asked in order to elicit temporal or spatial
relationships between pairs of temporal or spatial entities. In order to
improve the time performance of our learning algorithm in practice, constraint
propagation, through transitive closure, as well as ordering heuristics, are
enforced. The goal here is to reduce the number of membership queries needed to
reach the target QCN. In order to assess the practical effect of constraint
propagation and ordering heuristics, we conducted several experiments on
randomly generated temporal and spatial constraint network instances. The
results of the experiments are very encouraging and promising.
