Planning with Multistep Forward Search with Forced Goal‐Ordering Constraints. (17th October 2013)

• Record Type: Journal Article
• Authors: Luo, Jiangfeng; Zhu, Cheng; Zhang, Weiming; Liu, Zhong
• Is Part Of: Computational intelligence. Volume 31:Number 2(2015:May)
• Page Start: 233
• Page End: 255
• Publication Date: 2013-10-17
• Subjects: Artificial intelligence -- Periodicals; Computational linguistics -- Periodicals; 006.3
• DOI: 10.1111/coin.12019
• Languages: English
• ISSNs: 0824-7935

Abstract

<abstract abstract-type="main" id="coin12019-abs-0001"> <title> <x xml:space="preserve">Abstract</x> </title> <p id="coin12019-para-0001">To solve a real‐world planning problem with interfering subgoals, it is essential to perform early detection of subgoal dependencies and achieve the subgoals in the correct order. This is also the case for planning problems with forced goal‐ordering (FGO) constraints. In automated planning, forward search with FGO constraints has been proposed many times over the years, but there are still major difficulties in realizing these FGOs in plan generation. Many existing methods such as goal agenda manager and ordered landmarks cannot detect the FGOs accurately, and thus, the undiscovered ordering relationship may cause the forward search to suffer from deadlocks. In this article, we put forward an approach via an effective search heuristic to constrain a planner to satisfy the FGOs. We make use of an atomic goal‐achievement graph in a look‐ahead search under the FGO constraints. This allows a forward search strategy to plan forward efficiently in multiple steps toward a goal state along a search path. Experimental results illustrate that, by avoiding deadlocks, we can solve more benchmark planning problems more efficiently than previous approaches. We also prove several formal properties for search that are related to FGO detection.</p> </abstract>