皮皮虾科普网

皮皮虾科普网
分享国内外科学知识
皮皮虾科普网-国内外科学-科技-科普

新的算法在短时间内协调数百个机器人之间的复

更新时间:2020-07-17 00:47点击:

一种设计多机器人生长树运动方案的新方法在搜索空间中解决复杂问题的时间很短。

2002年轰动的电影《少数派报告》中有一个令人难忘的场景,汤姆·克鲁斯被迫躲避一群蜘蛛一样的机器人,它们在一幢高耸的公寓大楼里搜索。当大多数观众被小巧敏捷的猎犬替代品惊呆时,计算机工程师可能会对它们优雅的控制系统惊叹不已。

在一栋几层楼高、有许多房间、数百个障碍物和数千个检查场所的建筑里,几十个机器人作为一个整体移动。它们以搜索模式分散开来,彻底检查整个建筑,同时分散任务,以免浪费时间沿自己的路径重复搜索,或重新检查其他机器人已经访问过的地方。

这样的内聚对人类控制器来说很难实现,更不用说人工控制器的实时计算了。

“;如果有三个或四个机器人控制问题,生活在这样一个世界,只有少量的房间,如果指定的协作任务是简单的逻辑规则,有最先进的工具,可以计算出一个最优解,在合理的时间内满足任务,”;杜克大学机械工程和材料科学副教授Michael M. Zavlanos, Mary Milus Yoh和Harold L. Yoh Jr说。

如果你不关心可能的最佳解决方案,你可以在几分钟内解决更多的房间和更复杂的任务,但仍然只有十几个机器人最优秀,Zavlanos说。除此之外,现有的算法无法克服寻找解决方案的巨大可能性。

在4月29日在网上发表的一篇新论文机器人研究的国际期刊,Zavlanos最近和他的博士研究生,Yiannis Kantaros,现在是宾夕法尼亚大学的博士后研究员,提出一个新方法这一挑战叫做笔*,对大规模优化时序逻辑综合,可以解决问题大大超过目前的算法可以处理什么,成百上千的机器人,成千上万的房间和高度复杂的任务,在很短的时间内。

要理解这种新方法的基础,首先必须理解线性时序逻辑,它并不像听起来那么可怕。假设你想让几个机器人每天从一个社区收集邮件并把它送到邮局。线性时态逻辑是记录完成此任务所需命令的一种方法。

例如,这些命令可能包括按顺序访问每家每户,返回邮局,然后在再次出发前等待某人取回收集到的邮件。虽然用英语说这很容易,但用数学表达就难了。线性时态逻辑可以通过使用它自己的符号来做到这一点,虽然在一般观察者看来它们可能像克林贡语,但它们在表达复杂的控制问题时非常有用。

使用“线性”一词是因为时间点在离散线性时间模型的基础上有一个独特的后继,而“时间”指的是使用诸如“直到”、“下一个”、“最终”和“始终”等运算符。Kantaros说。利用这种数学形式,我们可以建立复杂的命令,例如参观除2号房屋外的所有房屋,按顺序参观第三和第四所房子,在你去过第一家之前,先去第五家。”;

传统控制器在找出最佳导航方式之前,会搜索每个节点以及它们之间的可能路径。但是随着机器人数量和访问地点的增加,以及需要遵循的逻辑规则变得更加复杂,解决方案空间在非常短的时间内变得难以置信的大。

一个简单的问题是,5个机器人生活在一个有10个房子的世界里,可能包含数百万个节点,捕捉所有可能的机器人位置和行为来完成任务。这需要大量内存来存储,并需要强大的搜索处理能力。

为了绕开这个问题,研究人员提出了一种新的方法,即使用树形结构创建更小的近似,而不是将这些难以置信的大图完整地构建出来。在该过程的每一步,算法都从大图中随机选择一个节点,将其添加到树中,并重新连接树中节点之间的现有路径,以找到从开始到结束的更多直接路径。

这意味着,随着算法的进展,我们逐渐增长的这棵树会越来越接近实际的图,而实际上我们从未构建过这个图。Kantaros说。因为我们的增量图要小得多,所以很容易存储在内存中。此外,由于这个图是一个树,本来具有指数复杂度的图搜索就变得非常简单了,因为现在我们只需要跟踪父节点序列到根节点,以找到所需的路径。

长期以来,人们一直认为,生长的树木不能用来为这些类型的机器人控制问题寻找可能的解决方案。但在论文中,Zavlanos和Kantaros表明,他们可以通过实施两个聪明的技巧来实现。首先,算法根据手头任务的信息选择下一个要添加的节点,这使得树能够快速地近似出问题的一个好的解决方案。其次,即使该算法生长了树,它仍然可以检测原始图空间中的循环,从而捕获这些时序逻辑任务的解决方案。

研究人员表示,如果有答案,这种方法总会找到,而且最终总会找到可能的最佳答案。它们还表明,这种方法可以以指数速度得到答案。处理一个由10个机器人在50乘50的网格空间中搜索的问题。250间房屋收取邮件目前最先进的算法需要30分钟来找到最优解决方案。

手写笔*在20秒内完成。

我们甚至已经解决了生活在100乘100网格世界中的200个机器人的问题,这对于今天的算法来说太大了,无法处理。Zavlanos说。目前还没有一个系统可以使用200个机器人来做递送包裹之类的事情,但未来可能会出现这种情况。他们需要一个像STyLuS*这样的控制框架,才能在满足复杂的基于逻辑的规则的同时交付它们。

# # #

参考:大型多机器人系统的时间逻辑最优控制综合算法作者:Yiannis Kantaros和Michael M Zavlanos, 2020年4月29日,国际机器人研究杂志。

2 f0278364920913922 DOI: 10.1177%

这项研究得到了空军科研办公室(fa9550 - 19 - 1−0169)和海军研究办公室(n00014 - 18 - 1−2374)的支持。