Structure-based search to solve constraint satisfaction problems
Item
-
Title
-
Structure-based search to solve constraint satisfaction problems
-
Identifier
-
d_2009_2013:7924d7d33735:10910
-
identifier
-
11166
-
Creator
-
Li, Xingjian,
-
Contributor
-
Susan L. Epstein
-
Date
-
2011
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer science | cluster | constraint satisfaction | contention | probing | structure
-
Abstract
-
Constraint satisfaction is a paradigm that applies to many challenging real-world tasks with direct practical relevance, such as planning and scheduling. It models these tasks as constraint satisfaction problems (CSPs) and then solves them with search. Compared to artificially-generated CSPs, real-world CSPs are more likely to have non-random structure. This dissertation shows the difficulties encountered by traditional and state-of-the-art search techniques when the structure of such a problem is overlooked. Here, a novel hybrid search algorithm for CSPs combines two fundamental search paradigms (global search and local search) to solve structured CSPs. It first uses local search to detect crucial structure (the structure identification stage ), and then applies that structural knowledge to solve the problem by global search (the search stage).;In the structure identification stage, we adapt a local search metaheuristic to find crucial structure within a CSP. This dissertation presents different structure detection methods based on different metrics. Static metrics from the original problem are sometimes available without any cost and are also straightforward to use, but they may not represent the real challenges within the problem. When dynamic metrics reveal the true crucial structure, they provide better guidance for search. On easier problems, however, this benefit does not justify the additional computational cost of the dynamic metrics.;In the search stage, the structure identified in the previous stage guides global search for a solution. This dissertation presents various approaches to exploit this structure, which is presumably the most difficult area for search. Under this premise, search can either address the identified structure earlier than other areas of the problem, or allow the structure to direct inference, a technique that reduces search space for global search.;In addition, this dissertation presents a new visualization tool for binary CSPs and the structures identified by our algorithms. The tool inspires, supports, and verifies the design and improvement of structure-based search. On benchmark and real-world CSPs, structured-based search not only improves search performance, but also provides users with direct explanations and visualization of the inherent challenges in each problem.
-
Type
-
dissertation
-
Source
-
2009_2013.csv
-
degree
-
Ph.D.
-
Program
-
Computer Science
