Subgoaling techniques for satisficing and optimal numeric planning
AuthorScala, E; Haslum, P; Thiébaux, S; Ramirez, M
Source TitleJournal of Artificial Intelligence Research
PublisherAI Access Foundation
University of Melbourne Author/sRamirez Javega, Miguel
AffiliationElectrical and Electronic Engineering
Document TypeJournal Article
CitationsScala, E., Haslum, P., Thiébaux, S. & Ramirez, M. (2020). Subgoaling techniques for satisficing and optimal numeric planning. Journal of Artificial Intelligence Research, 68, pp.691-752. https://doi.org/10.1613/JAIR.1.11875.
Access StatusAccess this item via the Open Access location
Open Access URLPublished version
This paper studies novel subgoaling relaxations for automated planning with propositional and numeric state variables. Subgoaling relaxations address one source of complexity of the planning problem: the requirement to satisfy conditions simultaneously. The core idea is to relax this requirement by recursively decomposing conditions into atomic subgoals that are considered in isolation. Such relaxations are typically used for pruning, or as the basis for computing admissible or inadmissible heuristic estimates to guide optimal or satisficing heuristic search planners. In the last decade or so, the subgoaling principle has underpinned the design of an abundance of relaxation-based heuristics whose formulations have greatly extended the reach of classical planning. This paper extends subgoaling relaxations to support numeric state variables and numeric conditions. We provide both theoretical and practical results, with the aim of reaching a good trade-off between accuracy and computation costs within a heuristic state-space search planner. Our experimental results validate the theoretical assumptions, and indicate that subgoaling substantially improves on the state of the art in optimal and satisficing numeric planning via forward state-space search.
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References