Stochastic shortest path with energy constraints in POMDPs Conference Paper

Author(s): Brázdil, Tomáš; Chatterjee, Krishnendu; Chmelík, Martin; Gupta, Anchit; Novotný, Petr
Title: Stochastic shortest path with energy constraints in POMDPs
Affiliation IST Austria
Abstract: We consider partially observable Markov decision processes (POMDPs) with a set of target states and positive integer costs associated with every transition. The traditional optimization objective (stochastic shortest path) asks to minimize the expected total cost until the target set is reached. We extend the traditional framework of POMDPs to model energy consumption, which represents a hard constraint. The energy levels may increase and decrease with transitions, and the hard constraint requires that the energy level must remain positive in all steps till the target is reached. First, we present a novel algorithm for solving POMDPs with energy levels, developing on existing POMDP solvers and using RTDP as its main method. Our second contribution is related to policy representation. For larger POMDP instances the policies computed by existing solvers are too large to be understandable. We present an automated procedure based on machine learning techniques that automatically extracts important decisions of the policy allowing us to compute succinct human readable policies. Finally, we show experimentally that our algorithm performs well and computes succinct policies on a number of POMDP instances from the literature that were naturally enhanced with energy levels.
Conference Title: AAMAS: Autonomous Agents & Multiagent Systems
Conference Dates: May 9-13, 2016
Conference Location: Singapore
ISBN: 978-1-4503-4239-1
Publisher: ACM  
Date Published: 2016-01-01
Start Page: 1465
End Page: 1466
Sponsor: Austrian Science Fund (FWF) Grant No P23499-N23, FWF NFN Grant No S11407-N23 (RiSE/SHiNE), ERC Start Grant (279307: Graph Games), Czech Science Foundation grant No. P202/12/G061, People Programme (Marie Curie Actions) FP7/2007-2013 No [291734]
Notes: Open Access available via:
Open access: yes (repository)
IST Austria Authors
  1. Martin Chmelik
    23 Chmelik
Related IST Austria Work