Introduction
In fields such as robotics and engineering design, researchers frequently encounter Numerical Constraint Satisfaction Problems (NCSPs)—systems of equations and inequalities where variables are defined by continuous intervals. Solving these problems typically requires the Branch and Prune Algorithm (BPA), which systematically partitions the search space into smaller "boxes" and prunes those that cannot contain solutions.
The ultimate goal of a BPA is often a "paving," a dense collection of tiny boxes covering the entire solution set. However, as the dimensionality of the problem increases (beyond 4 or 5 variables), the number of boxes required grows exponentially, making exhaustive computation impossible. This creates a critical need for "anytime" algorithms: strategies that can be stopped at any moment while still providing a useful, representative overview of the solution space.
The Branch and Prune Framework
The standard BPA alternates between branching (splitting a box) and pruning (filtering using consistency techniques). The order in which boxes are processed determines the algorithm's effectiveness in an anytime context.
Standard search strategies struggle with anytime requirements:
- Depth-First Search (DFS): Finds solutions quickly but clusters them in a single corner of the search space.
- Breadth-First Search (BFS): Spreads effort across the space but may take an impractical amount of time to reach the depth required to find any actual solutions.
Proposed Search Strategies: MDFS and DMDFS
To bridge the gap between speed and diversity, the authors propose two new strategies:
Most Distant-First Strategy (MDFS)
MDFS prioritizes the exploration of boxes that are geographically furthest from the solutions already discovered. While mathematically elegant and guaranteed to eventually cover the space uniformly, it is computationally expensive because it treats every new box selection as a global optimization problem.
Depth and Most Distant-First Strategy (DMDFS)
The paper's primary contribution is DMDFS, a hybrid of DFS and MDFS. It uses a LIFO (Last-In, First-Out) stack to maintain search depth, ensuring the algorithm "dives" to find solutions rapidly. When choosing between branches at a given depth, it greedily picks the one furthest from currently known solutions. This allows the algorithm to find solutions fast (like DFS) while ensuring they are spread out across the entire set (like BFS).
Experimental Evaluation
The authors evaluated DMDFS using synthetic benchmarks designed to test specific geometric properties, such as the "Flower" set—a 2D NCSP defined by a complex polynomial inequality.
Key Results
- Speed and Distribution: On the "Flower" benchmark, DMDFS found 200 well-distributed solutions in just 5 seconds, whereas the more complex MDFS took 27 seconds.
- High-Dimensional Performance: In tests involving $n$-dimensional non-overlapping balls, DMDFS successfully located all disconnected components even as $n$ increased to 14.
- Reliability: Compared to standard local search optimizers like Knitro, which often get "stuck" or fail to find all components, DMDFS reliably mapped the entire solution structure significantly faster as dimensionality grew.
Conclusion and Future Work
DMDFS effectively turns the BPA into a tool that provides a "low-resolution" map of the entire solution set almost immediately, which then gains resolution the longer it runs. This "anytime" philosophy is highly valuable for engineers who need a diverse set of representative solutions rather than a dense cluster in one region. Future research will focus on applying these strategies to mixed discrete-continuous CSPs, which are prevalent in real-world embodiment design problems.
Summary updated