Research and implementation based on bidirectional-paralleled graphplan algorithm
Wen-Xiang Gu, Xu Li, Xinmei Zhang, Xiaofeng Li, Fei Ren · 2005
Nowadays, intelligent planning is a very hot branch in AI because of its wide application. This paper proposes two new concepts: same-effect actions and same-effect propositions, and applies an intelligent planning algorithm which expands the planning graph backwards from the goal set and forwards from the initial state at the same time. The algorithm sufficiently demonstrates the idea of parallel, eliminates the redundant proposition levels, and makes the planning graph be much smaller than the classical one. Therefore, the algorithm has excellent performance in terms of time and space. In addition, the algorithm handles the mutual exclusion relationships (mutex) by adopting a novel idea, and the paper have proved that there are no mutex in the planning graph, namely, the algorithm makes the idea of constructing a planning graph without mutex come true. Lastly the experiments show the algorithm facilitates the process of the problem-solving in artificial intelligence system plan.