Exploring centralized and distributed constraint propagation algorithms for solving constraint satisfaction problems

Publication Type:
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
01front.pdf133.87 kB
Adobe PDF
02whole.pdf1.42 MB
Adobe PDF
Constraint Satisfaction Problem (CSP) is widely used in Artificial Intelligence (AI), such as temporal planning, vehicle routing, scheduling, and spatial reasoning. Constraint propagation is central to the process of solving a CSP. It can be used to solve several large tractable classes of CSPs directly and it is also predominantly used to reduce the space of combinations that will be explored by a search algorithm. Constraint propagation, also known as local consistency enforcing, is the process of reasoning over the given explicit local constraints to discover new implicit constraints and then make them explicit. Designing efficient local consistency algorithms is a central research question in constraint processing. Another related important question is to find large tractable classes that can be solved by enforcing local consistency. This thesis extends the related works in the literature and explores centralized and distributed local consistency algorithms for solving CSPs in several dimensions. On the one hand, we explore centralized local consistency algorithms to identify more general tractable constraint subclasses and to solve tractable constraint subclasses more efficiently. On the other hand, we design more efficient distributed local consistency algorithms to solve tractable constraint classes and to filter inconsistent tuples for distributed CSP solvers.
Please use this identifier to cite or link to this item: