Figure 2: An ambiguous map yields two CSP problems.
There are many types of problems which can be solved by using CSP in a more or less direct fashion. There are also problems which might benefit from the CSP approach, but which are difficult to represent with a single CSP. This is the class of problems our paper addresses. For example, suppose the map represented in Figure 1 is scanned by a noisy computer vision system, with a resulting uncertainty as to whether the line between regions 1 and 2 is really a border or an artifact of the noise. This situation would yield two CSP problems as depicted in Figure 2. A brute-force approach would be to solve both of the problems, which would be reasonable for scenes containing only a few ambiguous borders. However, as the number of ambiguous borders increases, the number of CSP networks would grow in a combinatorially explosive fashion. In the case of ambiguous segmentation, it can be more efficient to merge the constraint networks into a single network which would compactly represent all of the instances simultaneously, as shown in Figure 3. Notice that the CSP instances are combined into a directed acyclic graph where the paths through the DAG from start to end correspond to those CSPs that were combined. In this paper, we develop an extension to CSP called MUSE CSP ( MUltiply SEgmented Constraint Satisfaction Problem), which represents multiple instances of a CSP problem as a DAG.
Figure 2: An ambiguous map yields two CSP problems.
Figure 3: How the two CSP problems of Figure 2 can be captured by a
single instance of MUSE CSP.
The directed edges form a DAG such that the directed paths through the DAG
correspond to instances of those CSPs that were combined.
If there are multiple, similar instances of a CSP, then separately applying constraints for each instance can result in much duplicated work. To avoid this duplication, we have provided a way to combine the multiple instances of CSP into a MUSE CSP, and we have developed the concepts of MUSE node consistency, MUSE arc consistency, and MUSE path consistency. Formally, we define MUSE CSP as follows:
The segments in 
are the different sets of nodes
representing CSP instances which are combined to form a MUSE
CSP. A solution to a MUSE CSP is defined to be a solution
to any one of its segments:
Depending on the application, the solution for a MUSE CSP could also be the set of all consistent labels for a single path through the MUSE CSP, a single set of labels for each of the paths (or CSPs), or all compatible sets of labels for each of the paths.
A MUSE CSP can be solved with a modified backtracking algorithm which finds a consistent label assignment for a segment. However, when the constraints are sufficiently tight, the search space can be pruned by enforcing local consistency conditions, such as node, arc, and path consistency. To gain the efficiency resulting from enforcing local consistency conditions before backtracking, node, arc, and path consistency must be modified for MUSE CSP. The definitions for MUSE CSP node consistency, arc consistency, and path consistency appear in Definitions 7, 8, and 9, respectively.
A MUSE CSP is node consistent if all of its segments are node
consistent. Unfortunately, MUSE CSP arc consistency requires more
attention. When enforcing arc consistency in a CSP, a label 
can be eliminated from node i whenever any other domain
has no labels which together with a satisfy the binary
constraints. However, in a MUSE CSP, before a label can be eliminated
from a node, it must be unsupported by the arcs of every segment in
which it appears, as required by the definition of MUSE arc
consistency shown in Definition 8.
Notice that Definition 8 reduces to
Definition 3 when the number of segments is
one.
To demonstrate how MUSE arc consistency applies to a MUSE CSP,
consider the MUSE CSP in Figure 4a. Notice that label 
is not supported by any of the labels in 
and
, but does receive support from the labels in 
. Should
this label be considered to be MUSE arc consistent? The answer is no
because node 2 is only a member of paths through the DAG which
contain node 3 or node 4, and neither of them support the label
c. Because there is no segment such that all of its nodes have some
label which supports c, c should be eliminated from 
. Once
c is eliminated from , a will also be eliminated from
. This is because the elimination of c from causes
a to loose the support of node 2. Since node 2 is a member of
every path, no other segment provides support for a. The MUSE arc
consistent DAG is depicted in Figure 4b. Note that MUSE
arc consistency does not ensure that the individual segments are arc
consistent as CSPs.
For example, Figure
5 is MUSE arc consistent even though its segments
are not CSP arc consistent. This is because c receives arc support
(which is a very local computation) from the arcs of at least one of
the paths. We cannot ensure that the values that support a label are
themselves mutually consistent by considering MUSE arc consistency
alone. For this case, MUSE path consistency together with MUSE arc
consistency would be needed to eliminate the illegal labels c and a.
Figure 4: a. A MUSE CSP before MUSE arc consistency is achieved; b. A MUSE CSP
after MUSE arc consistency is achieved.
Figure 5: A MUSE CSP which is MUSE arc consistent, but not arc
consistent for each segment.
When enforcing path consistency in a CSP, 
becomes false if, for any third node k, there is no label
such that 
and 
are true. In MUSE CSP, if a binary constraint becomes path inconsistent
in one segment, it could still be allowed in another. Therefore, the
definition of MUSE path consistency is modified as shown in Definition
9.
Enforcement of MUSE arc and path consistency requires modification of the traditional CSP algorithms. These algorithms will be described after we introduce several applications for which MUSE CSP has proven useful.
