Volume 8 Number 6 (Jun. 2013)
Home > Archive > 2013 > Volume 8 Number 6 (Jun. 2013) >
JCP 2013 Vol.8(6): 1385-1393 ISSN: 1796-203X
doi: 10.4304/jcp.8.6.1385-1393

A Novel Heuristic Usage of Helpful Actions for Conformant-FF System

Wei Wei, Dantong Ouyang, Tingting Zou, and Shuai Lu
College of Computer Science and Technology, Jilin University, Changchun, China Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun, China

Abstract—Conformant planning is usually transformed into a search problem in the space of belief states, where the combinatorial explosion of search space has been one of the most intractable problems. In this paper, we present a novel usage of the helpful action pruning technique in the Conformant-FF planner. The key idea is to change the way it deals with helpful actions and first consider actions from the so-called implication path which was used by Conformant-FF for concluding which subgoal would be considered known to be true in the relaxed planning graph. We first point out the semantics of solving by cases, indicated by the implication paths of the relaxed planning process. In line with the semantics, we then propose our heuristic idea of using these implication paths further by attempting to collect certain groups of helpful actions such that executing all actions within a group can achieve some subgoal while executing an individual action in the group cannot due to incomplete information. This technique usually leads to the goal faster and cuts down the search space dramatically. We evaluate the idea experimentally. In a number of conformant benchmarks, our heuristic pruning technique outperforms helpful actions pruning in both planning efficiency and the size of search space.

Index Terms—Helpful actions, Conformant-FF, Heuristic Pruning, Belief state

[PDF]

Cite: Wei Wei, Dantong Ouyang, Tingting Zou, and Shuai Lu, " A Novel Heuristic Usage of Helpful Actions for Conformant-FF System," Journal of Computers vol. 8, no. 6, pp. 1385-1393, 2013.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Monthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, CNKI,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Jul 19, 2019 News!

    Vol 14, No 7 has been published with online version   [Click]

  • Jun 21, 2019 News!

    Vol 14, No 6 has been published with online version   [Click]

  • Read more>>