Granular Structure of State Space Search

Abstract

State space search is to find a path from start state to goal state, which is widely used in Artificial Intelligence. A state is a configuration of basic elements of a problem. For example, in chess game every legal chessboard configuration is a state, a state space consists of all the legal chessboard configurations, the start state is the beginning chessboard configuration, the goal state is the chessboard configuration that the opponent is checkmated, the search is to find a sequence of chess moves that from start state to goal state. In our research we use granular computing to construct a hierarchical structure of the state space, so that the search in the state space will be fast. Our idea is that a hierarchical structure can speed up search. For example in a supermarket all the commercial items are categorized hierarchically so that clients can easily find target items, if they want to find a Chinese food they can first search in food category, then search in oriental food category, then search in Chinese food category, then they can easily get their item. We categorize all the states in the state space in the same way so that we can quickly find a path from a start state to a goal state.