Efficient touch based localization through submodularity
Efficient touch based localization through submodularity
复制标题
通过子模块实现基于触摸的高效定位
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
S. Srinivasa
中科院分区：
文献类型：
--
作者：
Shervin Javdani;Matthew Klingensmith;Drew Bagnell;N. Pollard;S. Srinivasa
许多机器人系统通过执行一系列信息收集动作来处理不确定性。在这项工作中，我们关注的问题是通过绘制明确的连接到子模块来有效地构造这样一个序列。理想情况下，我们希望有一种方法能够找到最优序列，在提供足够信息的同时花费最少的时间。然而，找到这个序列通常是棘手的。因此，许多已建立的方法会贪婪地选择行动。令人惊讶的是，这通常效果很好。我们的工作首先解释了这种高性能-我们注意到一个常用的度量，Shannon熵的减少，在某些假设下是子模的，使得贪婪解决方案可以与离线设置中的最优方案相比较。然而，对观察结果进行在线反应可以提高性能。最近发展的自适应子模块化概念为这种在线设置下的贪婪算法提供了保证。在这项工作中，我们开发了基于自适应子模块化的新方法来选择在线信息收集动作序列。除了提供保证之外，我们还可以利用子模块化来获得额外的计算速度。我们在仿真和机器人上验证了这些方法的有效性。
Many robotic systems deal with uncertainty by performing a sequence of information gathering actions. In this work, we focus on the problem of efficiently constructing such a sequence by drawing an explicit connection to submodularity. Ideally, we would like a method that finds the optimal sequence, taking the minimum amount of time while providing sufficient information. Finding this sequence, however, is generally intractable. As a result, many well-established methods select actions greedily. Surprisingly, this often performs well. Our work first explains this high performance - we note a commonly used metric, reduction of Shannon entropy, is submodular under certain assumptions, rendering the greedy solution comparable to the optimal plan in the offline setting. However, reacting online to observations can increase performance. Recently developed notions of adaptive submodularity provide guarantees for a greedy algorithm in this online setting. In this work, we develop new methods based on adaptive submodularity for selecting a sequence of information gathering actions online. In addition to providing guarantees, we can capitalize on submodularity to attain additional computational speedups. We demonstrate the effectiveness of these methods in simulation and on a robot.