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

• Author / Creator

  Santana de Lelis, Lelis H.

• 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.

• Subjects / Keywords

  • Heuristic Search
  • Stratified Sampling
  • Tree Size Prediction
  • Optimal Solution Cost Prediction
  • Planning
  • Learning Heuristic Functions
  • Active Stratified Sampling
  • Cluster-and-Conquer
  • Predicting Search Performance
  • Artificial Intelligence
  • Suboptimal Path-Planning
  • Type System

• Graduation date

  Fall 2013

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/R3668T

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.