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
  • Graduation date
    Fall 2012
  • Type of Item
  • Degree
    Master of Science
  • DOI
  • 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.
  • Language
  • Institution
    University of Alberta
  • Degree level
  • Department
  • Supervisor / co-supervisor and their department(s)
  • Examining committee members and their departments
    • Holte, Robert (Computing Science)
    • Bulitko, Vadim (Computing Science)
    • Patterson, Raymond (Alberta School of Business)