System and method for asynchronous explanation and propagation-based constraint solving

摘要

Embodiments of a system and method for asynchronous explanation and explanation-based constraint problem solving are generally described herein. In one or more embodiments, an apparatus includes an asynchronous constraint satisfaction problem solving module (ACSPSM), the ACSPSM can be executable by one or more processors. The ACSPSM can be configured to propagate at least one constraint to a plurality of variables by reducing a speculative propagation range of a first variable when a first value in the speculative propagation range of the first variable is in conflict with the constraint. The ACSPSM can be configured to update an explanation for the reduction in the speculative propagation range of the first variable, or backtrack when a choice of a second value for a second variable would result in the speculative propagation range of the first variable becoming empty. The ACSPSM can be multi-threaded.

主权项

1. An apparatus comprising:
an asynchronous constraint satisfaction problem solving module, the asynchronous constraint satisfaction problem solving module executable by one or more processors, the asynchronous constraint problem solving module configured to:
assign a priority level and a rank to each variable of a plurality of variables such that no two variables include both a same priority level and a same rank;propagate at least one constraint to the plurality of variables in a first thread by reducing a speculative propagation range of a first variable of the plurality of variables when a first value in the speculative propagation range of the first variable is in conflict with the constraint; andin a second thread, (1) update an explanation for the reduction in the speculative propagation range of the first variable, and (2) backtrack when a choice of a second value for a second variable of the plurality of variables would result in the speculative propagation range of the first variable becoming the empty set, wherein backtracking includes taking back a choice associated with a variable with a lowest priority level and if two choices are associated with respective variables assigned the same priority level then backtracking includes taking back the choice associated with the variable of the respective variables assigned a lower rank.