Download the full-sized PDF of Cluster-and-Conquer: a Paradigm for Solving State-Space ProblemsDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Graduate Studies and Research, Faculty of


This file is in the following collections:

Theses and Dissertations

Cluster-and-Conquer: a Paradigm for Solving State-Space Problems Open Access


Other title
Stratified Sampling
Type System
Active Stratified Sampling
Suboptimal Path-Planning
Tree Size Prediction
Artificial Intelligence
Optimal Solution Cost Prediction
Predicting Search Performance
Learning Heuristic Functions
Heuristic Search
Type of item
Degree grantor
University of Alberta
Author or creator
Santana de Lelis, Lelis H.
Supervisor and department
Zilles, Sandra (Computing Science)
Holte, Robert (Computing Science)
Examining committee member and department
Bowling, Michael (Computing Science)
Barbosa, Denilson (Computing Science)
Bonet, Blai (Departamento de Computación Universidad Simón Bolívar)
Mueller, Martin (Computing Science)
Department of Computing Science

Date accepted
Graduation date
Doctor of Philosophy
Degree level
Many important problems can be cast as state-space problems. In this dissertation we study a general paradigm for solving state-space problems which we name Cluster-and-Conquer (C&C). Algorithms that follow the C&C paradigm use the concept of equivalent states to reduce the number of states explored to solve the problem. The concept of equivalent states is captured by a type system, which is a partition of the states in the state space. C&C algorithms assume that states of the same type are equivalent to one another, thus only one state of each type must be explored. Although our type systems only approximate the ideal partition of states into equivalent states, the solutions found by most of our C&C algorithms are guaranteed to converge to optimal solutions. The C&C paradigm is general and can be used to solve different problems. In this dissertation we advance and develop C&C algorithms for solving different state-space problems. Namely, • we advance Conditional Distribution Prediction (CDP) and Stratified Sampling (SS), two ex- isting algorithms for predicting the search tree size of Iterative-Deepening A* (IDA*). Among other contributions, (1) we introduce different heuristic-based type systems, and (2) we apply the concept of active sampling to increase the accuracy of the predictions. Our versions of CDP and SS represent the current state of the art for predicting the IDA* search tree size; • we present Two-Step Stratified Sampling (TSS), an algorithm for predicting the search tree size of Depth-First Branch and Bound (DFBnB). TSS is the only known algorithm able to produce accurate predictions of the DFBnB search tree size in a reasonable amount of time; • we present Solution Cost Predictor (SCP) and Bidirectional Stratified Sampling (BiSS), the first algorithms designed for predicting the optimal solution cost of state-space problems. We show that one can reduce from days to minutes the time required for learning heuristic functions by using BiSS to label the training set; • we present Stratified Tree Search (STS), a search algorithm for finding suboptimal solutions of state-space problems when the only heuristics available are too weak to usefully guide existing methods.
Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.
Citation for previous publication
L. Lelis, R. Stern, A. Felner, S. Zilles, and R. C. Holte. Predicting optimal solution cost with bidirectional stratified sampling. In Proceedings of the International Conference on Automated Planning and Scheduling, pages 155–163. AAAI Press, 2012.L. Lelis, R. Stern, and S. Jabbari Arfaee. Predicting solution cost with condiditional probabili- ties. In Proceedings of the Symposium on Combinatorial Search, pages 100–107. AAAI Press, 2011.L. Lelis, S. Zilles, and R. C. Holte. Improved prediction of IDA*’s performance via ε- truncation. In Proceedings of the Symposium on Combinatorial Search, pages 108–116. AAAI Press, 2011.L. H. S. Lelis. Active stratified sampling with clustering-based type systems for predicting the search tree size of problems with real-valued heuristics. In Proceedings of the Symposium on Combinatorial Search, pages 123–131. AAAI Press, 2013.L. H. S. Lelis, L. Otten, and R. Dechter. Predicting the size of depth-first branch and bound search trees. In International Joint Conference on Artificial Intelligence, page to appear, 2013.L. H. S. Lelis, S. Zilles, and R. C. Holte. Fast and accurate predictions of IDA*’s performance. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 514–520. AAAI Press, 2012.L. H. S. Lelis, S. Zilles, and R. C. Holte. Predicting the Size of IDA*’s Search Tree. Artificial Intelligence, pages 53–76, 2013.L. H. S. Lelis, S. Zilles, and R. C. Holte. Stratified Tree Search: a novel suboptimal heuristic search algorithm. In Proceedings of the Conference on Autonomous Agents and Multiagent Systems, pages 555–562, 2013.L. H. S. Lelis, S. Jabbari Arfaee S. Zilles, and R. C. Holte. Learning heuristic functions faster by using predicted solution costs. In Proceedings of the Symposium on Combinatorial Search, pages 166–167. AAAI Press, 2012.

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 1290798
Last modified: 2015:10:12 11:54:17-06:00
Filename: thesis.pdf
Original checksum: 9bd66ebbe8fbb9f9374f329e45113151
Well formed: true
Valid: false
Status message: Invalid page tree node offset=1286987
Activity of users you follow
User Activity Date