- 266 views
- 215 downloads
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
- Thesis
-
- Degree
- Master of Science
-
- 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.