FLAP: Applying least-commitment in forward-chaining planning

Issue title: Artificial Intelligence in the Catalan Association for AI

Article type: Research Article

Authors: Sapena, Oscar^; | Onaindia, Eva | Torreño, Alejandro

Affiliations: Departamento Sistemas Informáticos y Computación, Universitat Politècnica de València, Spain

Note: [] Corresponding author. E-mail: osapena@dsic.upv.es

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.

Keywords: Planning, partial-order plan, least commitment, forward-chaining search, heuristics

DOI: 10.3233/AIC-140613

Journal: AI Communications, vol. 28, no. 1, pp. 5-20, 2015