Near-optimal Observation Selection using Submodular Functions
Near-optimal Observation Selection using Submodular Functions
复制标题
DOI：
--
复制
发表时间：
2007-07
期刊：
影响因子：
--
通讯作者：
Andreas Krause;Carlos Guestrin
中科院分区：
文献类型：
--
作者：
Andreas Krause;Carlos Guestrin
人工智能问题，如自主机器人探索，自动诊断和活动识别，都需要在一组信息丰富但可能昂贵的观察结果中进行选择。例如，当使用传感器网络或移动的机器人监测空间现象时，我们需要决定观察哪些位置，以便以最小的成本最有效地降低不确定性。这些问题通常是NP难的。许多观测选择目标满足子模块性，这是一种直观的收益递减属性-将传感器添加到小型部署比将其添加到大型部署更有帮助。在本文中，我们调查最近的进展，系统地利用这种子模块属性，有效地实现近最佳的观察选择，在复杂的约束条件下。我们说明了我们的方法的有效性监测环境现象和水分配网络的问题。
AI problems such as autonomous robotic exploration, automatic diagnosis and activity recognition have in common the need for choosing among a set of informative but possibly expensive observations. When monitoring spatial phenomena with sensor networks or mobile robots, for example, we need to decide which locations to observe in order to most effectively decrease the uncertainty, at minimum cost. These problems usually are NP-hard. Many observation selection objectives satisfy submodularity, an intuitive diminishing returns property - adding a sensor to a small deployment helps more than adding it to a large deployment. In this paper, we survey recent advances in systematically exploiting this submodularity property to efficiently achieve near-optimal observation selections, under complex constraints. We illustrate the effectiveness of our approaches on problems of monitoring environmental phenomena and water distribution networks.