From Serial to Massively Parallel Constraint Satisfaction

Abstract

Local propagation algorithms such as Waltz filtering and Mackworth’s AC-x algorithms have been successfully applied in AI for solving constraint satisfaction problems (CSPs). It has been shown that they can be implemented in parallel very easily. However, algorithms like Waltz filtering and AC-x are not complete. In general, they can only be used as preprocessing methods as they do not compute a globally consistent solution for a CSP; they result in local consistency also known as arc consistency. In this paper, we introduce extensions of local constraint propagation to overcome this drawback, i.e. to compute globally consistent solutions for a CSP. The idea is to associate additional information with the values during the propagation process so that global relationships among the values are maintained. The result are algorithms that are complete and for which there are straightforward, parallel and massively parallel implementations.