Algorithms and conditional lower bounds for planning problems

Chatterjee K, Dvořák W, Henzinger M, Svozil A. 2021. Algorithms and conditional lower bounds for planning problems. Artificial Intelligence. 297(8), 103499.

Download
No fulltext has been uploaded. References only!

Journal Article | Epub ahead of print | English

Scopus indexed
Author
Chatterjee, KrishnenduIST Austria ; Dvořák, Wolfgang; Henzinger, Monika; Svozil, Alexander
Department
Abstract
We consider planning problems for graphs, Markov Decision Processes (MDPs), and games on graphs in an explicit state space. While graphs represent the most basic planning model, MDPs represent interaction with nature and games on graphs represent interaction with an adversarial environment. We consider two planning problems with k different target sets: (a) the coverage problem asks whether there is a plan for each individual target set; and (b) the sequential target reachability problem asks whether the targets can be reached in a given sequence. For the coverage problem, we present a linear-time algorithm for graphs, and quadratic conditional lower bound for MDPs and games on graphs. For the sequential target problem, we present a linear-time algorithm for graphs, a sub-quadratic algorithm for MDPs, and a quadratic conditional lower bound for games on graphs. Our results with conditional lower bounds, based on the boolean matrix multiplication (BMM) conjecture and strong exponential time hypothesis (SETH), establish (i) model-separation results showing that for the coverage problem MDPs and games on graphs are harder than graphs, and for the sequential reachability problem games on graphs are harder than MDPs and graphs; and (ii) problem-separation results showing that for MDPs the coverage problem is harder than the sequential target problem.
Publishing Year
Date Published
2021-03-16
Journal Title
Artificial Intelligence
Volume
297
Issue
8
Article Number
103499
ISSN
IST-REx-ID

Cite this

Chatterjee K, Dvořák W, Henzinger M, Svozil A. Algorithms and conditional lower bounds for planning problems. Artificial Intelligence. 2021;297(8). doi:10.1016/j.artint.2021.103499
Chatterjee, K., Dvořák, W., Henzinger, M., & Svozil, A. (2021). Algorithms and conditional lower bounds for planning problems. Artificial Intelligence. Elsevier. https://doi.org/10.1016/j.artint.2021.103499
Chatterjee, Krishnendu, Wolfgang Dvořák, Monika Henzinger, and Alexander Svozil. “Algorithms and Conditional Lower Bounds for Planning Problems.” Artificial Intelligence. Elsevier, 2021. https://doi.org/10.1016/j.artint.2021.103499.
K. Chatterjee, W. Dvořák, M. Henzinger, and A. Svozil, “Algorithms and conditional lower bounds for planning problems,” Artificial Intelligence, vol. 297, no. 8. Elsevier, 2021.
Chatterjee K, Dvořák W, Henzinger M, Svozil A. 2021. Algorithms and conditional lower bounds for planning problems. Artificial Intelligence. 297(8), 103499.
Chatterjee, Krishnendu, et al. “Algorithms and Conditional Lower Bounds for Planning Problems.” Artificial Intelligence, vol. 297, no. 8, 103499, Elsevier, 2021, doi:10.1016/j.artint.2021.103499.

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1804.07031

Search this title in

Google Scholar