Concise planning and filtering: Hardness and algorithms

Abstract Motivated by circumstances with severe computational resource limits (e.g., settings with strong constraints on memory or communication), this paper addresses the problem of concisely representing and processing information for estimation and planning tasks. In this article, conciseness is a measure of explicit representational complexity: for filtering, we are concerned with maintaining as little state as possible to perform a given task; for the planning case, we wish to generate the plan-graph (or policy-graph) with the fewest vertices that is correct and also complete. We present hardness results showing that both filtering and planning are NP-hard to perform in an optimally concise way, and that the related decision problems are NP-complete. We also describe algorithms for filter reduction and concise planning, for which these hardness results justify the potentially sub-optimal output. The filter-reduction algorithm accepts as input an arbitrary combinatorial filter, expressed as a transition graph, and outputs an equivalent filter that uses fewer information states to complete the same filtering task. The planning algorithm, using the filter-reduction algorithm as a subroutine, generates concise plans for planning problems that may involve both non-determinism and partial observability. Both algorithms are governed by parameters that encode tradeoffs between computational efficiency and solution quality. We describe implementation of both algorithms and present a series of experiments evaluating their effectiveness.

@article{OKaShe17,
  author = {Jason M. O'Kane and Dylan A. Shell},
  doi = {10.1109/TASE.2017.2701648},
  issue = {4},
  journal = {IEEE Transactions on Automation Science and Engineering},
  month = {October},
  pages = {1666--1681},
  title = {Concise planning and filtering: Hardness and algorithms},
  volume = {14},
  year = {2017}
}