---
_id: '5426'
abstract:
- lang: eng
  text: We consider partially observable Markov decision processes (POMDPs), that
    are a standard framework for robotics applications to model uncertainties present
    in the real world, with temporal logic specifications. All temporal logic specifications
    in linear-time temporal logic (LTL) can be expressed as parity objectives. We
    study the qualitative analysis problem for POMDPs with parity objectives that
    asks whether there is a controller (policy) to ensure that the objective holds
    with probability 1 (almost-surely). While the qualitative analysis of POMDPs with
    parity objectives is undecidable, recent results show that when restricted to
    finite-memory policies the problem is EXPTIME-complete. While the problem is intractable
    in theory, we present a practical approach to solve the qualitative analysis problem.
    We designed several heuristics to deal with the exponential complexity, and have
    used our implementation on a number of well-known POMDP examples for robotics
    applications. Our results provide the first practical approach to solve the qualitative
    analysis of robot motion planning with LTL properties in the presence of uncertainty.
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Martin
  full_name: Chmelik, Martin
  id: 3624234E-F248-11E8-B48F-1D18A9856A87
  last_name: Chmelik
- first_name: Raghav
  full_name: Gupta, Raghav
  last_name: Gupta
- first_name: Ayush
  full_name: Kanodia, Ayush
  last_name: Kanodia
citation:
  ama: Chatterjee K, Chmelik M, Gupta R, Kanodia A. <i>Qualitative Analysis of POMDPs
    with Temporal Logic Specifications for Robotics Applications</i>. IST Austria;
    2014. doi:<a href="https://doi.org/10.15479/AT:IST-2014-305-v2-1">10.15479/AT:IST-2014-305-v2-1</a>
  apa: Chatterjee, K., Chmelik, M., Gupta, R., &#38; Kanodia, A. (2014). <i>Qualitative
    analysis of POMDPs with temporal logic specifications for robotics applications</i>.
    IST Austria. <a href="https://doi.org/10.15479/AT:IST-2014-305-v2-1">https://doi.org/10.15479/AT:IST-2014-305-v2-1</a>
  chicago: Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia.
    <i>Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics
    Applications</i>. IST Austria, 2014. <a href="https://doi.org/10.15479/AT:IST-2014-305-v2-1">https://doi.org/10.15479/AT:IST-2014-305-v2-1</a>.
  ieee: K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, <i>Qualitative analysis
    of POMDPs with temporal logic specifications for robotics applications</i>. IST
    Austria, 2014.
  ista: Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2014. Qualitative analysis of
    POMDPs with temporal logic specifications for robotics applications, IST Austria,
    10p.
  mla: Chatterjee, Krishnendu, et al. <i>Qualitative Analysis of POMDPs with Temporal
    Logic Specifications for Robotics Applications</i>. IST Austria, 2014, doi:<a
    href="https://doi.org/10.15479/AT:IST-2014-305-v2-1">10.15479/AT:IST-2014-305-v2-1</a>.
  short: K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, Qualitative Analysis of
    POMDPs with Temporal Logic Specifications for Robotics Applications, IST Austria,
    2014.
date_created: 2018-12-12T11:39:16Z
date_published: 2014-09-29T00:00:00Z
date_updated: 2025-04-15T07:55:41Z
day: '29'
ddc:
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-305-v2-1
file:
- access_level: open_access
  checksum: 730c0a8e97cf2712a884b2cc423f3919
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T11:54:15Z
  date_updated: 2020-07-14T12:46:51Z
  file_id: '5537'
  file_name: IST-2014-305-v2+1_main2.pdf
  file_size: 656019
  relation: main_file
file_date_updated: 2020-07-14T12:46:51Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: '10'
publication_identifier:
  issn:
  - 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '311'
related_material:
  record:
  - id: '5424'
    relation: earlier_version
    status: public
  - id: '1732'
    relation: later_version
    status: public
status: public
title: Qualitative analysis of POMDPs with temporal logic specifications for robotics
  applications
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...