---
_id: '7402'
abstract:
- lang: eng
  text: Graph planning gives rise to fundamental algorithmic questions such as shortest
    path, traveling salesman problem, etc. A classical problem in discrete planning
    is to consider a weighted graph and construct a path that maximizes the sum of
    weights for a given time horizon T. However, in many scenarios, the time horizon
    is not fixed, but the stopping time is chosen according to some distribution such
    that the expected stopping time is T. If the stopping time distribution is not
    known, then to ensure robustness, the distribution is chosen by an adversary,
    to represent the worst-case scenario. A stationary plan for every vertex always
    chooses the same outgoing edge. For fixed horizon or fixed stopping-time distribution,
    stationary plans are not sufficient for optimality. Quite surprisingly we show
    that when an adversary chooses the stopping-time distribution with expected stopping
    time T, then stationary plans are sufficient. While computing optimal stationary
    plans for fixed horizon is NP-complete, we show that computing optimal stationary
    plans under adversarial stopping-time distribution can be achieved in polynomial
    time. Consequently, our polynomial-time algorithm for adversarial stopping time
    also computes an optimal plan among all possible plans.
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: Laurent
  full_name: Doyen, Laurent
  last_name: Doyen
citation:
  ama: 'Chatterjee K, Doyen L. Graph planning with expected finite horizon. In: <i>34th
    Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE; 2019:1-13. doi:<a
    href="https://doi.org/10.1109/lics.2019.8785706">10.1109/lics.2019.8785706</a>'
  apa: 'Chatterjee, K., &#38; Doyen, L. (2019). Graph planning with expected finite
    horizon. In <i>34th Annual ACM/IEEE Symposium on Logic in Computer Science</i>
    (pp. 1–13). Vancouver, BC, Canada: IEEE. <a href="https://doi.org/10.1109/lics.2019.8785706">https://doi.org/10.1109/lics.2019.8785706</a>'
  chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Graph Planning with Expected
    Finite Horizon.” In <i>34th Annual ACM/IEEE Symposium on Logic in Computer Science</i>,
    1–13. IEEE, 2019. <a href="https://doi.org/10.1109/lics.2019.8785706">https://doi.org/10.1109/lics.2019.8785706</a>.
  ieee: K. Chatterjee and L. Doyen, “Graph planning with expected finite horizon,”
    in <i>34th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Vancouver,
    BC, Canada, 2019, pp. 1–13.
  ista: 'Chatterjee K, Doyen L. 2019. Graph planning with expected finite horizon.
    34th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Symposium on
    Logic in Computer Science, 1–13.'
  mla: Chatterjee, Krishnendu, and Laurent Doyen. “Graph Planning with Expected Finite
    Horizon.” <i>34th Annual ACM/IEEE Symposium on Logic in Computer Science</i>,
    IEEE, 2019, pp. 1–13, doi:<a href="https://doi.org/10.1109/lics.2019.8785706">10.1109/lics.2019.8785706</a>.
  short: K. Chatterjee, L. Doyen, in:, 34th Annual ACM/IEEE Symposium on Logic in
    Computer Science, IEEE, 2019, pp. 1–13.
conference:
  end_date: 2019-06-27
  location: Vancouver, BC, Canada
  name: 'LICS: Symposium on Logic in Computer Science'
  start_date: 2019-06-24
date_created: 2020-01-29T16:18:33Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2025-07-14T09:09:54Z
day: '01'
department:
- _id: KrCh
doi: 10.1109/lics.2019.8785706
external_id:
  arxiv:
  - '1802.03642'
  isi:
  - '000805002800001'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1802.03642
month: '06'
oa: 1
oa_version: Preprint
page: 1-13
publication: 34th Annual ACM/IEEE Symposium on Logic in Computer Science
publication_identifier:
  isbn:
  - '9781728136080'
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
  record:
  - id: '11402'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Graph planning with expected finite horizon
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2019'
...