Algorithms and conditional lower bounds for planning problems

DOI10.1016/J.ARTINT.2021.103499OpenAlexW3138721759MaRDI QIDQ2238604FDOQ2238604

Authors: Krishnendu Chatterjee, Wolfgang Dvořák, Alexander Svozil, Monika R. Henzinger 

Publication date: 2 November 2021

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.07031

Recommendations

• Model and objective separation with conditional lower bounds: disjunction is harder than conjunction
• Conditionally Optimal Algorithms for Generalized B\"uchi Games
• The complexity of planning problems with simple causal graphs
• Upper and lower time and space bounds for planning
• Time and Space Bounds for Planning

zbMATH Keywords

probabilistic planninggraph gamesstrong exponential time hypothesisadversarial planningconditional lower bounds

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Planning and acting in partially observable stochastic domains
• Powers of tensors and fast matrix multiplication
• Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition
• The Complexity of Markov Decision Processes
• Title not available (Why is that?)
• Depth-First Search and Linear Graph Algorithms
• Multiplying matrices faster than coppersmith-winograd
• The computational complexity of propositional STRIPS planning
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Weak, strong, and strong cyclic planning via symbolic model checking
• Planning Algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Number of quantifiers is better than number of tape cells
• On the menbership problem for functional and multivalued dependencies in relational databases
• Plan aggregation for strong cyclic planning in nondeterministic domains
• Subcubic equivalences between path, matrix, and triangle problems
• Refining complexity analyses in planning by exploiting the exponential time hypothesis
• Graph expansion and communication costs of fast matrix multiplication
• Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
• Tight hardness for shortest cycles and paths in sparse graphs
• If the current clique algorithms are optimal, so is Valiant's parser
• AND/OR graph heuristic search methods
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• On some fine-grained questions in algorithms and complexity
• Time and Space Bounds for Planning
• Model and objective separation with conditional lower bounds: disjunction is harder than conjunction
• Title not available (Why is that?)

Cited In (8)

• Graph planning with expected finite horizon
• Model and objective separation with conditional lower bounds: disjunction is harder than conjunction
• Fine-grained complexity lower bounds for problems in computer aided verification
• Time and Space Bounds for Planning
• State-variable planning under structural restrictions: algorithms and complexity
• Title not available (Why is that?)
• FROM PLANNING TO SEARCHING FOR THE SHORTEST PLAN: AN OPTIMAL TRANSITION
• Sufficient Conditions for the Existence of Resolution Complete Planning Algorithms

This page was built for publication: Algorithms and conditional lower bounds for planning problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2238604)