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

Field	Value	Language
dc.contributor.author	Kong, Shufeng
dc.date.accessioned	2019-01-09T21:26:03Z
dc.date.available	2019-01-09T21:26:03Z
dc.date.issued	2018
dc.identifier.uri	http://hdl.handle.net/10453/129397
dc.description	University of Technology Sydney. Faculty of Engineering and Information Technology.	en_AU
dc.description.abstract	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.	en_AU
dc.format	Thesis (PhD)
dc.language.iso	en_AU	en_AU
dc.relation	https://opus.lib.uts.edu.au/bitstream/10453/129397/2/02whole.pdf
dc.relation	https://opus.lib.uts.edu.au/bitstream/10453/129397/6/16DD6E13-FAD2-4CB4-BD35-3F29A01DDA08 AM.pdf
dc.rights	au.edu.uts.lib/ppc
dc.rights	The author owns the copyright in this thesis including all reproduction and reuse rights for the work. The work may not be altered without the permission of the copyright owner. Attribution is essential when quoting or paraphrasing from this thesis.
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Constraint satisfaction problem.
dc.subject	Constraint propagation.
dc.subject	Artificial Intelligence.
dc.subject	AI.
dc.subject	Algorithms.
dc.subject	Constraint processing.
dc.title	Exploring centralized and distributed constraint propagation algorithms for solving constraint satisfaction problems	en_AU
dc.type	Thesis	en_AU
utslib.copyright.status	open_access

Abstract:

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:

http://hdl.handle.net/10453/129397