Parallel Path-Consistency Algorithms for Constraint Satisfaction

TitleParallel Path-Consistency Algorithms for Constraint Satisfaction
Publication TypeTechnical Report
Year of Publication1989
AuthorsLadkin, P., & Maddux R. D.
Other Numbers544

This paper concerns heuristic algorithms used for solution of Boolean Constraint Satisfaction Problems, or CSPs [Mon74, Mac77, Fre78, Mac87]. CSPs occur particularly in areas of artificial intelligence such as vision, temporal reasoning, and truth-maintenance systems. The most common form involves binary constraints and we consider properties of binary CSPs only (we shall omit the adjective from now on). CSPs may be represented by labeled digraphs called binary constraint networks, or BCNs. Many constraint satisfaction techniques operate upon BCNs. An important property of BCNs is that of path-consistency, which is used extensively as a heuristic for solving CSPs (many classes of CSPs are NP-hard, e.g. [VilKau86]). nEvery BCN has a path-consistent reduction, and it is known that algorithms for computing it are serial O(n superscript 3) in the number of variables [Mac77, Fre78, All83, MacFre85, MohHen86].We have formulated CSPs and path-consistency computations in the framework of Tarski's relation algebra, and give a brief overview below [Tar41, LadMad88.2]. We give a parallel O((n superscript 2) log n) algorithm for achieving path-consistency. We also give a class of hard examples on which all algorithms proposed so far, and possible parallelisations of them, take time 0(n superscript 2). This effectively constrains parallel path- consistency algorithms of the most common form (which we glorify with the name of reduction-type) within a fairly narrow asymptotic range.In the next section, we introduce the relation-algebraic formulation of CSPs. We formulate some algorithms in the following section, ending with the O((n superscript 2) log n) parallel path-consistency algorithm. In the final section, we describe the class of problems on which the reduction-type algorithms take 0(n superscript 2) time.

Bibliographic Notes

ICSI Technical Report TR-89-045

Abbreviated Authors

P. B. Ladkin and R. D. Maddux

ICSI Publication Type

Technical Report