---
_id: '34'
abstract:
- lang: eng
  text: Partially observable Markov decision processes (POMDPs) are widely used in
    probabilistic planning problems in which an agent interacts with an environment
    using noisy and imprecise sensors. We study a setting in which the sensors are
    only partially defined and the goal is to synthesize “weakest” additional sensors,
    such that in the resulting POMDP, there is a small-memory policy for the agent
    that almost-surely (with probability 1) satisfies a reachability objective. We
    show that the problem is NP-complete, and present a symbolic algorithm by encoding
    the problem into SAT instances. We illustrate trade-offs between the amount of
    memory of the policy and the number of additional sensors on a simple example.
    We have implemented our approach and consider three classical POMDP examples from
    the literature, and show that in all the examples the number of sensors can be
    significantly decreased (as compared to the existing solutions in the literature)
    without increasing the complexity of the policies.
article_processing_charge: No
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: Chemlík, Martin
  last_name: Chemlík
- first_name: Ufuk
  full_name: Topcu, Ufuk
  last_name: Topcu
citation:
  ama: 'Chatterjee K, Chemlík M, Topcu U. Sensor synthesis for POMDPs with reachability
    objectives. In: <i>28th International Conference on Automated Planning and Scheduling</i>.
    Vol 2018. AAAI Press; 2018:47-55. doi:<a href="https://doi.org/10.1609/icaps.v28i1.13875">10.1609/icaps.v28i1.13875</a>'
  apa: 'Chatterjee, K., Chemlík, M., &#38; Topcu, U. (2018). Sensor synthesis for
    POMDPs with reachability objectives. In <i>28th International Conference on Automated
    Planning and Scheduling</i> (Vol. 2018, pp. 47–55). Delft, Netherlands: AAAI Press.
    <a href="https://doi.org/10.1609/icaps.v28i1.13875">https://doi.org/10.1609/icaps.v28i1.13875</a>'
  chicago: Chatterjee, Krishnendu, Martin Chemlík, and Ufuk Topcu. “Sensor Synthesis
    for POMDPs with Reachability Objectives.” In <i>28th International Conference
    on Automated Planning and Scheduling</i>, 2018:47–55. AAAI Press, 2018. <a href="https://doi.org/10.1609/icaps.v28i1.13875">https://doi.org/10.1609/icaps.v28i1.13875</a>.
  ieee: K. Chatterjee, M. Chemlík, and U. Topcu, “Sensor synthesis for POMDPs with
    reachability objectives,” in <i>28th International Conference on Automated Planning
    and Scheduling</i>, Delft, Netherlands, 2018, vol. 2018, pp. 47–55.
  ista: 'Chatterjee K, Chemlík M, Topcu U. 2018. Sensor synthesis for POMDPs with
    reachability objectives. 28th International Conference on Automated Planning and
    Scheduling. ICAPS: International Conference on Automated Planning and Scheduling
    vol. 2018, 47–55.'
  mla: Chatterjee, Krishnendu, et al. “Sensor Synthesis for POMDPs with Reachability
    Objectives.” <i>28th International Conference on Automated Planning and Scheduling</i>,
    vol. 2018, AAAI Press, 2018, pp. 47–55, doi:<a href="https://doi.org/10.1609/icaps.v28i1.13875">10.1609/icaps.v28i1.13875</a>.
  short: K. Chatterjee, M. Chemlík, U. Topcu, in:, 28th International Conference on
    Automated Planning and Scheduling, AAAI Press, 2018, pp. 47–55.
conference:
  end_date: 2018-06-29
  location: Delft, Netherlands
  name: 'ICAPS: International Conference on Automated Planning and Scheduling'
  start_date: 2018-06-24
das_tickbox: '1'
date_created: 2018-12-11T11:44:16Z
date_published: 2018-06-01T00:00:00Z
date_updated: 2026-07-07T13:35:51Z
day: '01'
department:
- _id: KrCh
doi: 10.1609/icaps.v28i1.13875
ec_funded: 1
external_id:
  arxiv:
  - '1710.00675'
  isi:
  - '000492986200006'
intvolume: '      2018'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1710.00675
month: '06'
oa: 1
oa_version: Preprint
page: 47 - 55
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P 23499-N23
  name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 2587B514-B435-11E9-9278-68D0E5697425
  name: Microsoft Research Faculty Fellowship
publication: 28th International Conference on Automated Planning and Scheduling
publication_status: published
publisher: AAAI Press
publist_id: '8021'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Sensor synthesis for POMDPs with reachability objectives
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2018
year: '2018'
...