FLAP: Applying least-commitment in forward-chaining planning

Abstract

In this paper, we present FLAP, a partial-order planner that accurately applies the least-commitment principle that governs traditional partial-order planning. FLAP fully exploits the partial ordering among actions of a plan and hence it solves more problems than other similar approaches. The search engine of FLAP uses a combination of different state-based heuristics and applies a parallel search technique to diversify the search in different directions when a plateau is found. In the experimental evaluation, we compare FLAP with OPTIC, LPG-td and TFD, three state-of-the-art non-linear planners. The results show that FLAP outperforms these planners in terms of number of problems solved; in addition, the plans of FLAP represent a good trade-off between quality and computational time.