Bayesian Active Edge Evaluation on Expensive Graphs
Bayesian Active Edge Evaluation on Expensive Graphs
复制标题
昂贵图上的贝叶斯主动边评估
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
S. Scherer
中科院分区：
文献类型：
--
作者：
Sanjiban Choudhury;S. Srinivasa;S. Scherer
我们考虑了实时运动规划问题，该问题需要评估图上的最少数量的边来快速发现无碰撞路径。无论是对于机器人手臂这样几何形状复杂的机器人，还是对于像无人机这样在线感知世界的机器人来说，评估边缘都是昂贵的。到目前为止，这一挑战一直是通过懒惰来解决的，即将边缘评估推迟到绝对必要的时候，希望边缘被证明是有效的。然而，所有边缘的值并不相同-一些边缘有很多潜在的好路径流经它们，而另一些边缘编码相邻边缘有效的可能性。这导致了我们的关键洞察力--我们可以主动选择减少路径有效性不确定性的边，而不是被动的懒惰。我们证明了这相当于决策区域确定(DRD)的贝叶斯主动学习范式。然而，DRD问题不仅在组合上是困难的，而且还需要显式地列举所有可能的世界。我们提出了一种新的框架，它结合了直接和二等分两种DRD算法来克服这两个问题。我们表明，我们的方法在移动机器人、机械手和自主直升机的一系列规划问题上的表现优于几种最先进的算法。
We consider the problem of real-time motion planning that requires evaluating a minimal number of edges on a graph to quickly discover collision-free paths. Evaluating edges is expensive, both for robots with complex geometries like robot arms, and for robots sensing the world online like UAVs. Until now, this challenge has been addressed via laziness, i.e. deferring edge evaluation until absolutely necessary, with the hope that edges turn out to be valid. However, all edges are not alike in value - some have a lot of potentially good paths flowing through them, and some others encode the likelihood of neighbouring edges being valid. This leads to our key insight - instead of passive laziness, we can actively choose edges that reduce the uncertainty about the validity of paths. We show that this is equivalent to the Bayesian active learning paradigm of decision region determination (DRD). However, the DRD problem is not only combinatorially hard but also requires explicit enumeration of all possible worlds. We propose a novel framework that combines two DRD algorithms, DIRECT and BISECT, to overcome both issues. We show that our approach outperforms several state-of-the-art algorithms on a spectrum of planning problems for mobile robots, manipulators and autonomous helicopters.