We consider evacuation from a finite two-dimensional (2D) square grid field by a metamorphic robotic system (MRS). An MRS is composed of anonymous memoryless modules. Each module of an MRS executes an identical distributed algorithm and moves autonomously while keeping the connectivity of modules. Since the modules are memoryless, an MRS utilizes its shape to remember the progress of execution. The number of available shapes that an MRS can form depends on the number of modules, which is thus an important complexity measure for a behavior of an MRS. In this paper, we investigate the minimum number of modules required to solve the evacuation problem with several conditions. First, we consider a rectangular field surrounded by walls with at least one exit and show that two modules are necessary and sufficient for evacuation from any rectangular field if the modules are equipped with a global compass, which allows the modules to have a common sense of direction. Then, we focus on the case where modules do not have a global compass and show that four (resp. seven) modules are necessary and sufficient for restricted (resp. any) initial states of an MRS. We also show that two modules are sufficient in the special case where an MRS is on a wall in an initial configuration. Finally, we extend these results to another type of fields, that is, mazes.


翻译:我们考虑用一个变形机器人系统(MRS)从一个有限的二维(2D)平方格场进行疏散。MRS由匿名的不记忆模块组成。MRS的每个模块在保持模块连接的同时,执行一个相同的分布算法并自动移动。由于模块没有记忆,MRS利用其形状来回忆执行进度。MRS能够形成的可用形状数量取决于模块数量,因此,这是MRS行为的一个重要复杂度量。在本文中,我们用几种条件调查解决疏散问题所需的模块最低数量。首先,我们考虑一个由至少一个出口的墙环绕的矩形字段,并显示如果模块配备了全球指南,两个模块就足够地从任何矩形字段进行疏散,从而使模块具有共同方向感。然后,我们侧重于模块没有全球指南且显示四个(重复的七)模块是必要且足够限制(重复的)MRS初始状态。我们还认为,两个模块对于任何磁盘的初始状态都足够。我们最后显示,两个模块对于从任何矩形场都是必要的,这些磁盘在另一个特殊的字段中,这些磁盘是另一个磁场。

0
下载
关闭预览

相关内容

【图与几何深度学习】Graph and geometric deep learning,49页ppt
专知会员服务
41+阅读 · 2021年4月2日
专知会员服务
17+阅读 · 2020年9月6日
最新《几何深度学习》教程,100页ppt,Geometric Deep Learning
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
76+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
96+阅读 · 2019年10月9日
已删除
将门创投
3+阅读 · 2020年8月3日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
14+阅读 · 2017年11月16日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年6月1日
Arxiv
0+阅读 · 2021年6月1日
Arxiv
0+阅读 · 2021年5月28日
VIP会员
相关VIP内容
【图与几何深度学习】Graph and geometric deep learning,49页ppt
专知会员服务
41+阅读 · 2021年4月2日
专知会员服务
17+阅读 · 2020年9月6日
最新《几何深度学习》教程,100页ppt,Geometric Deep Learning
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
76+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
96+阅读 · 2019年10月9日
相关资讯
已删除
将门创投
3+阅读 · 2020年8月3日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
14+阅读 · 2017年11月16日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员