We consider the problem of coordinated motion planning for a swarm of simple, identical robots: From a given start grid configuration of robots, we need to reach a desired target configuration via a sequence of parallel, continuous, collision-free robot motions, such that the set of robots induces a connected grid graph at all integer times. The objective is to minimize the makespan of the motion schedule, i.e., to reach the new configuration in a minimum amount of time. We show that this problem is NP-hard, even for deciding whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved. On the algorithmic side, we establish simultaneous constant-factor approximation for two fundamental parameters, by achieving constant stretch for constant scale. Scaled shapes (which arise by increasing all dimensions of a given object by the same multiplicative factor) have been considered in previous seminal work on self-assembly, often with unbounded or logarithmic scale factors; we provide methods for a generalized scale factor, bounded by a constant. Moreover, our algorithm achieves a constant stretch factor: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of $d$, then the total duration of our overall schedule is $O(d)$, which is optimal up to constant factors.


翻译:我们考虑对一组简单、相同的机器人进行协调运动规划的问题:从一个特定起始的机器人网格配置中,我们需要通过一个平行、连续、无碰撞的机器人动作序列来达到一个理想的目标配置,让一组机器人在所有整数时间都产生一个连接的网格图。目标是将运动时间表的成份最小化,即在最短的时间内达到新配置。我们显示,这个问题是难以解决的,甚至是为了确定是否能够实现一个2的成份,同时有可能在多元时间内检查一个1的成份是否能够实现。在算法方面,我们为两个基本参数同时建立恒定的方位近距离,在固定的尺度上达到一个固定的伸缩缩放。在以前关于自我组合的半成份工作中已经考虑到了规模的形状(通过增加一个特定对象的方位,也就是在最小的成份上达到新的成份来达到新的配置),我们提供了一个通用的成份比例系数,由固定的成份数开始。此外,如果我们总的成份的成份是固定的成份的成份,那么,我们的成份的成份就要求一个固定不变的成份的成份的成份。

0
下载
关闭预览

相关内容

如何构建你的推荐系统?这份21页ppt教程为你讲解
专知会员服务
64+阅读 · 2021年2月12日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
已删除
将门创投
13+阅读 · 2019年4月17日
Arxiv
0+阅读 · 2021年11月11日
Arxiv
3+阅读 · 2021年6月9日
Arxiv
5+阅读 · 2021年2月8日
Arxiv
6+阅读 · 2018年4月24日
VIP会员
相关资讯
已删除
将门创投
13+阅读 · 2019年4月17日
Top
微信扫码咨询专知VIP会员