Granular State Space Search

Abstract

Granular computing is an emerging field of study that derives general principles and models from a wide range of disciplines and uses these principles and models to solve problems. One basic structure in granular computing is a granular struc- ture, which is a hierarchical multi-level structure made of granules. The granular structure implies important ways to problem solving such as hierarchical problem solving and top-down progressive processing. These ways can be used in artifi- cial intelligence. This thesis focuses on how to use granular computing to solve problems in state space search. State space search is a classical approach to problem solving in artificial in- telligence. A problem solving process is modeled by a state space and a search for a path from the start state to a goal state. One promising method for state space search is hierarchical state space search, which creates abstraction hierar- chies as representations of state spaces and uses a procedure, called refinement procedure, to find solutions with the help of abstraction hierarchies. Good ab- straction hierarchies and refinement procedures can speed up state space search while bad abstraction hierarchies and refinement procedures can slow down state space search. This thesis proposes granular computing based methods that can construct good abstraction hierarchies quickly and a new refinement procedure. We first identify two main issues in hierarchical problem solving, namely, back-tracking and incompleteness. Backtracking degrades the efficiency of state space search while incompleteness decreases the effectiveness and reliability. Based on the two issues, we propose a concept of completeness degree and give criteria for evaluating good abstraction hierarchies. We argue that a good abstraction hierarchy should have few backtrackings and a high completeness degree. To apply granular computing in state space search, we propose two new con- cepts, called an attributed graph and a granulated attributed graph, respectively. An attributed graph can be mapped into a state space and a granulated at- tributed graph can be mapped into an abstraction. We analyze characteristics of attributed graphs and granulated attributed graphs and identify an important property of granulated attributed graphs known as inner connectivity. We argue that if a granulated attributed graph satisfies the inner connectivity property, the mapped abstraction hierarchy is free of backtrackings and incompleteness. Based on the attributed graphs and granulated attributed graphs, we propose a new genre of methods for state space search called granular state space search. Granular state space search can create good abstraction hierarchies that have fewer backtrackings and a higher completeness degree. Furthermore, we improve granular state space search by applying the machine learning techniques so that good abstraction hierarchies can be generated fast. Finally, we compare our granular state space search with existing hierarchical state space search methods and demonstrate the superiority of granular state space search by experimental results.