Multimapping Abstraction and State-set Search Theory

• Author / Creator

  Pang, Bo

• This thesis consists of two parts. First, we invented an abstraction
  framework called multimapping which allows multiple admissible
  heuristic values to be extracted from one abstract space. The key idea
  of this technique is to design a multimapping function which maps one
  state in the original space to multiple states in the abstract space.
  The fundamental differences between this new technique and other
  existing ones is that this technique is completely domain independent
  and can be implemented without increasing the size of the abstract
  space. Based on this multimapping framework, we have implemented
  multimapping domain abstraction for the HIDA* algorithm. To benchmark
  its performance, extensive experiments have been run on the Sliding
  Tile Puzzle, Pancake, Topspin and Blocks World domains. The results
  show that the new technique outperforms existing domain abstraction
  with a single or multiple abstract spaces in terms of CPU time and
  memory usage.

  The second part of this thesis is focused on the theory of state-set
  search. This theory investigates the scenario that a set of states are
  manipulated as a single state-set by a search algorithm. This scenario
  occurs frequently in abstraction and planning system and we are the
  first to formally define and analyze it. Based on this theory, we have
  found a path-based distance, dww, which is the maximum admissible
  distance between two state-sets.

• Subjects / Keywords

  • State-set
  • Abstractions
  • Heuristic search

• Graduation date

  Fall 2012

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/R3DW6T

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