Object rearrangement is a widely-applicable and challenging task for robots. Geometric constraints must be carefully examined to avoid collisions and combinatorial issues arise as the number of objects increases. This work studies the algorithmic structure of rearranging uniform objects, where robot-object collisions do not occur but object-object collisions have to be avoided. The objective is minimizing the number of object transfers under the assumption that the robot can manipulate one object at a time. An efficiently computable decomposition of the configuration space is used to create a "region graph", which classifies all continuous paths of equivalent collision possibilities. Based on this compact but rich representation, a complete dynamic programming primitive DFSDP performs a recursive depth first search to solve monotone problems quickly, i.e., those instances that do not require objects to be moved first to an intermediate buffer. DFSDP is extended to solve single-buffer, non-monotone instances, given a choice of an object and a buffer. This work utilizes these primitives as local planners in an informed search framework for more general, non-monotone instances. The search utilizes partial solutions from the primitives to identify the most promising choice of objects and buffers. Experiments demonstrate that the proposed solution returns near-optimal paths with higher success rate, even for challenging non-monotone instances, than other leading alternatives.


翻译:对机器人来说,天体重新布局是一项广泛适用且具有挑战性的任务。 几何限制必须仔细研究, 以避免碰撞, 并随着物体数量的增加而出现组合问题。 这项工作研究的是重新排列统一物体的算法结构, 即机器人- 物体碰撞不会发生, 但物体- 物体碰撞必须避免。 目标是在假设机器人可以一次操纵一个物体的情况下, 尽量减少物体转移的数量。 配置空间的高效可比较分解用于创建“ 区域图 ”, 将所有相近碰撞可能性的连续路径分类。 基于这一紧凑但内容丰富的代表性, 完整的动态原始 DFSPDP 进行循环深度的首次搜索, 以快速解决单调问题, 即不要求物体首先移动到中间缓冲的情景。 DFSP 将扩展为解决单一缓冲、 非单调和缓冲的情景。 这项工作利用这些原始点作为本地规划者, 用于为更一般、非运动式的情景进行知情的搜索框架。 一个完整的动态原始程序, 一个循环的原始程序首先进行循环的深度搜索, 以显示最有挑战性的方法返回。

0
下载
关闭预览

相关内容

《计算机信息》杂志发表高质量的论文,扩大了运筹学和计算的范围,寻求有关理论、方法、实验、系统和应用方面的原创研究论文、新颖的调查和教程论文,以及描述新的和有用的软件工具的论文。官网链接:https://pubsonline.informs.org/journal/ijoc
专知会员服务
53+阅读 · 2020年3月16日
专知会员服务
109+阅读 · 2020年3月12日
Diganta Misra等人提出新激活函数Mish,在一些任务上超越RuLU
专知会员服务
14+阅读 · 2019年10月15日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
计算机类 | PLDI 2020等国际会议信息6条
Call4Papers
3+阅读 · 2019年7月8日
谷歌足球游戏环境使用介绍
CreateAMind
33+阅读 · 2019年6月27日
CVPR 2019 | 重磅!34篇 CVPR2019 论文实现代码
AI研习社
11+阅读 · 2019年6月21日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2021年3月21日
Arxiv
0+阅读 · 2021年3月17日
VIP会员
相关VIP内容
专知会员服务
53+阅读 · 2020年3月16日
专知会员服务
109+阅读 · 2020年3月12日
Diganta Misra等人提出新激活函数Mish,在一些任务上超越RuLU
专知会员服务
14+阅读 · 2019年10月15日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
计算机类 | PLDI 2020等国际会议信息6条
Call4Papers
3+阅读 · 2019年7月8日
谷歌足球游戏环境使用介绍
CreateAMind
33+阅读 · 2019年6月27日
CVPR 2019 | 重磅!34篇 CVPR2019 论文实现代码
AI研习社
11+阅读 · 2019年6月21日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员