Concise Planning and Filtering: Hardness and Algorithms
Concise Planning and Filtering: Hardness and Algorithms
复制标题
DOI：
10.1109/tase.2017.2701648
复制
发表时间：
2017-05
影响因子：
5.6
通讯作者：
J. O’Kane;Dylan A. Shell
中科院分区：
文献类型：
--
作者：
J. O’Kane;Dylan A. Shell
受严重计算资源限制的情况的激励（例如，设置与强大的限制内存或通信），本文解决的问题，简明表示和处理信息的估计和规划任务。在本文中，简洁性是一个明确的表示复杂性的衡量标准：对于过滤，我们关注的是保持尽可能少的状态来执行给定的任务;对于规划的情况下，我们希望生成的计划图（或策略图）具有最少的顶点是正确的，也是完整的。我们目前的硬度结果表明，过滤和规划是NP-难以执行的最佳简洁的方式，相关的决策问题是NP-完全的。我们还描述了过滤器减少和简洁的规划，这些硬度结果证明潜在的次优输出的算法。过滤器减少算法接受作为输入的任意组合过滤器，表示为一个过渡图，并输出一个等效的过滤器，使用较少的I-状态来完成相同的过滤任务。规划算法，使用的过滤器减少算法作为一个子程序，生成简洁的规划问题，可能涉及非确定性和部分可观性的计划。这两种算法都是由参数编码的计算效率和解决方案的质量之间的权衡。我们描述了这两种算法的实现，并提出了一系列的实验评估其有效性。从业者注意-本文中探索的简化过滤器和计划在几种情况下具有实际意义，包括：1）在计算能力严重有限的机器人平台上; 2）通过低带宽噪声信道进行通信; 3）前一种情况的特殊实例包括人机交互设置，其中界面限制信息传输;以及4）理解用于给定问题的简明计划或过滤器的大小和结构提供了对这些问题的洞察（例如，通过比较有或没有传感器的过滤器的大小来评估特定传感器的价值。
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.)