Parallel Path-Consistency Algorithms for Constraint Satisfaction
Title | Parallel Path-Consistency Algorithms for Constraint Satisfaction |
Publication Type | Technical Report |
Year of Publication | 1989 |
Authors | Ladkin, P., & Maddux R. D. |
Other Numbers | 544 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-89-45.pdf |
Bibliographic Notes | ICSI Technical Report TR-89-045 |
Abbreviated Authors | P. B. Ladkin and R. D. Maddux |
ICSI Publication Type | Technical Report |