Taming Combinatorial Challenges in Optimal Clutter Removal Tasks
Taming Combinatorial Challenges in Optimal Clutter Removal Tasks
复制标题
克服最佳杂波去除任务中的组合挑战
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Jingjin Yu
中科院分区：
文献类型：
--
作者：
Wei N. Tang;Jingjin Yu
我们研究了一个重要的组合挑战，使用配备机械手的移动机器人清理杂乱，寻求计算一个最优的物体移除序列，以最小化任务完成时间，假设每个物体被抓住一次，然后随后被移除。在结构方面，我们确定这样的最优序列可以是NP-hard计算，即使没有两个要删除的对象有任何重叠。然后，我们构造了渐近最优和启发式的杂波去除算法。采用动态规划，我们的最优算法扩展到40个对象。另一方面，对于随机杂波，快速贪婪算法倾向于产生与最优算法产生的解相当的解。
We examine an important combinatorial challenge in clearing clutter using a mobile robot equipped with a manipulator, seeking to compute an optimal object removal sequence for minimizing the task completion time, assuming that each object is grasped once and then subsequently removed. On the structural side, we establish that such an optimal sequence can be NP-hard to compute, even when no two objects to be removed have any overlap. Then, we construct asymptotically optimal and heuristic algorithms for clutter removal. Employing dynamic programming, our optimal algorithm scales to 40 objects. On the other hand, for random clutter, fast greedy algorithms tend to produce solutions comparable to these generated by the optimal algorithm.
DOI：
10.1177/0278364918780999
发表时间：
2017-11
期刊：
The International Journal of Robotics Research
影响因子：
--
作者：
Shuai D. Han;Nicholas M. Stiffler;A. Krontiris;Kostas E. Bekris;Jingjin Yu
通讯作者：
Shuai D. Han;Nicholas M. Stiffler;A. Krontiris;Kostas E. Bekris;Jingjin Yu