Concise Planning and Filtering: Hardness and Algorithms
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
2004-2012 IEEE. 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 paper, 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 suboptimal 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 I-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 nondeterminism 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. Note to Practitioners-The reduced filters and plans explored in this paper are of practical interest in several contexts, including: 1) on robot platforms with severely limited computational power; 2) communication over low-bandwidth noisy channels; 3) a special instance of the previous case includes human-robot interaction settings where interfaces constrain information transfer; and 4) understanding the size and the structure of concise plans or filters for given problems provides insights into those problems (e.g., to assess the value of a particular sensor by comparing the size of filters with or without it.)
