Skip navigation
Skip navigation

Occupation Measure Heuristics for Probabilistic Planning

W. Trevizan, Felipe; Thiebaux, Sylvie; Haslum, Patrik

Description

For the past 25 years, heuristic search has been used to solve domain-independent probabilistic planning problems, but with heuristics that determinise the problem and ignore precious probabilistic information. To remedy this situation, we explore the use of occupation measures, which represent the expected number of times a given action will be executed in a given state of a policy. By relaxing the well-known linear program that computes them, we derive occupation measure heuristics – the...[Show more]

dc.contributor.authorW. Trevizan, Felipe
dc.contributor.authorThiebaux, Sylvie
dc.contributor.authorHaslum, Patrik
dc.coverage.spatialPittsburgh
dc.date.accessioned2021-08-23T00:50:44Z
dc.date.createdJune 18–23, 2017
dc.identifier.isbn9781577357896
dc.identifier.urihttp://hdl.handle.net/1885/244968
dc.description.abstractFor the past 25 years, heuristic search has been used to solve domain-independent probabilistic planning problems, but with heuristics that determinise the problem and ignore precious probabilistic information. To remedy this situation, we explore the use of occupation measures, which represent the expected number of times a given action will be executed in a given state of a policy. By relaxing the well-known linear program that computes them, we derive occupation measure heuristics – the first admissible heuristics for stochastic shortest path problems (SSPs) taking probabilities into account. We show that these heuristics can also be obtained by extending recent operator-counting heuristic formulations used in deterministic planning. Since the heuristics are formulated as linear programs over occupation measures, they can easily be extended to more complex probabilistic planning models, such as constrained SSPs (C-SSPs). Moreover, their formulation can be tightly integrated into i-dual, a recent LP-based heuristic search algorithm for (constrained) SSPs, resulting in a novel probabilistic planning approach in which policy update and heuristic computation work in unison. Our experiments in several domains demonstrate the benefits of these new heuristics and approach.
dc.description.sponsorshipThis research was funded by AFOSR grant FA2386-15-1- 4015.
dc.format.mimetypeapplication/pdf
dc.language.isoen_AU
dc.publisherAAAI Press
dc.relation.ispartofProceedings of the 27th International Conference on Automated Planning and Scheduling, ICAPS 2017
dc.relation.ispartofseries27th International Conference on Automated Planning and Scheduling (ICAPS 2017)
dc.rightsCopyright © 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org).
dc.source.urihttps://ojs.aaai.org/index.php/ICAPS/article/view/13840
dc.titleOccupation Measure Heuristics for Probabilistic Planning
dc.typeConference paper
local.description.notesImported from ARIES
dc.date.issued2017
local.identifier.absfor080100 - ARTIFICIAL INTELLIGENCE AND IMAGE PROCESSING
local.identifier.ariespublicationu1046907xPUB52
local.type.statusPublished Version
local.contributor.affiliationTrevizan, Felipe, College of Engineering and Computer Science, ANU
local.contributor.affiliationThiebaux, Sylvie, College of Engineering and Computer Science, ANU
local.contributor.affiliationHaslum, Patrik, College of Engineering and Computer Science, ANU
local.description.embargo2099-12-31
dc.date.updated2020-11-23T10:53:42Z
dcterms.accessRightsOpen Access via publisher website
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Trevizan_Occupation_Measure_Heuristics_2017.pdf717.35 kBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator