Causal Action Network Heuristic-Based Action Space Search for Automated Planning

There is a growing interest in automated planning as a promising technique for autonomous agents, such as robots, to achieve a given goal (mission) by devising their own action plans. Recently, search-based planning using state-of-the-art heuristics has made remarkable progress compared to the past, mostly achieved by using a combination of multiple heuristics. In this paper, we introduce a novel quantitative notion called the “causal action network heuristics” and propose a way to exploit this notion within heuristic search, specifically through action space search tree pruning and action cost estimation. The paper discusses how to construct the causal action network and how to compute the causal involvement between the current node and the new nodes when expanding the front nodes of the action space search tree. Experiments show that the causal action network heuristics improve the performance of the GBFS algorithm.