Overview

Random Solution Sampling is described as a distinguishing requirement of constraint satisfaction problems arising in stimuli generation. In this setting, a design model together with a test template defines a single Soft-CSP, but the intended use is to obtain many different tests from that same template. The desired behavior is for those tests to be distributed as uniformly as possible among all tests that conform to the template.

Operationally, this means the solver should reach a significantly different solution each time it is run on the same CSP.

Solver strategy

The cited approach achieves random sampling by randomizing all decisions in the search path of a maintain-arc-consistency (MAC) algorithm. This is reported to produce reasonably disperse solutions.

The consequence is that ordinary variable-ordering and value-ordering heuristics cannot be used, because variable and value choices must be random. This makes the solver differ substantially from regular MAC-based techniques, which may rely heavily on such heuristics to find a solution in reasonable time.

Context in constraint-based stimuli generation

The broader solver framework is based on CSP technology because CSPs are declarative: rules can be stated and then enforced by the underlying CSP algorithm. CSPs also support prioritization of expert-knowledge rules through Soft-CSP methods.

Stimuli-generation CSPs are described as different from more typical CSP applications such as job-shop scheduling or rostering. The solver framework uses MAC, and in rare cases where constraint propagation is computationally hard, stochastic search is used.

Interaction with soft constraints

Random solution sampling can conflict with constraint hierarchies. Expert knowledge may be represented as soft constraints organized in a multi-tiered hierarchy according to importance. If the maximum number of soft constraints can be satisfied by only one assignment, a pure hierarchy-based objective would return that same assignment every time, contradicting the goal of diverse tests.

The cited approach resolves this by using a local metric for the soft-constraint hierarchy: if a partial solution can be extended to satisfy additional soft constraints, it must be extended, but the solver drops the requirement to satisfy the maximum possible number of soft constraints over the entire search space.

Practical implications

Random Solution Sampling prioritizes diversity and approximate uniformity of generated tests over deterministic search guidance. This makes it well suited to the cited stimuli-generation use case, where many tests are expected from one template, but it also removes common MAC heuristics that are often important for efficient search.