Two-staged scheme for subgoaling decomposition and ordering for path search problem

Problem consists of various states and solving a problem can be considered as searching the space within which these states exits. States are views of the problem and we start at the initial state and aim for the goal state with the help of ordering of the operators and searching technique. The problem space could also be viewed as a maze of states and in order to find the goal state we have to do a powerful search on this maze. We show how subgoaling strategy improves search efficiency to get desired goal fast and how it can be incorporated into conventional search methods. In order to improve search we have introduced two-staged scheme of subgoal decomposition and subgoal ordering. This scheme makes use of the guiding power of subgoaling strategies as form of augmented control knowledge in search. The implementation of A* heuristic search algorithm with subgoaling strategy called subgoaling decomposition A* (SDA*) is proposed and examined. The quantitative tradeoff between conventional A* and SDA* in solving some benchmark tasks is investigated to draw the effectiveness of the subgoaling strategies.