---
_id: '1732'
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.
arxiv: 1
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. Qualitative analysis of POMDPs
    with temporal logic specifications for robotics applications. In: IEEE; 2015:325-330.
    doi:<a href="https://doi.org/10.1109/ICRA.2015.7139019">10.1109/ICRA.2015.7139019</a>'
  apa: 'Chatterjee, K., Chmelik, M., Gupta, R., &#38; Kanodia, A. (2015). Qualitative
    analysis of POMDPs with temporal logic specifications for robotics applications
    (pp. 325–330). Presented at the ICRA: International Conference on Robotics and
    Automation, Seattle, WA, United States: IEEE. <a href="https://doi.org/10.1109/ICRA.2015.7139019">https://doi.org/10.1109/ICRA.2015.7139019</a>'
  chicago: Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia.
    “Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics
    Applications,” 325–30. IEEE, 2015. <a href="https://doi.org/10.1109/ICRA.2015.7139019">https://doi.org/10.1109/ICRA.2015.7139019</a>.
  ieee: 'K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, “Qualitative analysis
    of POMDPs with temporal logic specifications for robotics applications,” presented
    at the ICRA: International Conference on Robotics and Automation, Seattle, WA,
    United States, 2015, pp. 325–330.'
  ista: 'Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2015. Qualitative analysis of
    POMDPs with temporal logic specifications for robotics applications. ICRA: International
    Conference on Robotics and Automation, 325–330.'
  mla: Chatterjee, Krishnendu, et al. <i>Qualitative Analysis of POMDPs with Temporal
    Logic Specifications for Robotics Applications</i>. IEEE, 2015, pp. 325–30, doi:<a
    href="https://doi.org/10.1109/ICRA.2015.7139019">10.1109/ICRA.2015.7139019</a>.
  short: K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, in:, IEEE, 2015, pp. 325–330.
conference:
  end_date: 2015-05-30
  location: Seattle, WA, United States
  name: 'ICRA: International Conference on Robotics and Automation'
  start_date: 2015-05-26
date_created: 2018-12-11T11:53:43Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2023-02-23T12:25:52Z
day: '01'
department:
- _id: KrCh
doi: 10.1109/ICRA.2015.7139019
ec_funded: 1
external_id:
  arxiv:
  - '1409.3360'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1409.3360
month: '01'
oa: 1
oa_version: Preprint
page: 325 - 330
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P 23499-N23
  name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
publication_status: published
publisher: IEEE
publist_id: '5394'
quality_controlled: '1'
related_material:
  record:
  - id: '5424'
    relation: earlier_version
    status: public
  - id: '5426'
    relation: earlier_version
    status: public
scopus_import: 1
status: public
title: Qualitative analysis of POMDPs with temporal logic specifications for robotics
  applications
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...