协调数百个机器人之间的复杂行为

这是这部2002年大片中最令人难忘的场景之一少数派报告在这部电影中，汤姆克鲁斯(Tom Cruise)被迫躲避一群蜘蛛状的机器人，这些机器人正在一座高耸的公寓大楼里扫视。虽然大多数观众可能会被小巧敏捷的猎犬替代品惊呆，但计算机工程师可能会惊叹于它们优雅的控制系统。

在一座几层楼高的建筑里，有许多房间、数百个障碍物和数千个需要检查的地方，几十个机器人作为一个有凝聚力的单元移动。它们以搜索模式展开，以彻底检查整个建筑物，同时分散任务，以免浪费时间在自己的路径上折返或重新检查其他机器人已经访问过的地方。

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

“如果一个控制问题有三个或四个机器人生活在一个只有少数几个房间的世界里，如果协作任务由简单的逻辑规则指定，那么有最先进的工具可以计算出在合理时间内满足任务的最佳解决方案，”他说迈克尔·m·扎夫拉诺斯杜克大学机械工程和材料科学副教授。

扎夫拉诺斯说:“如果你不关心最好的解决方案，你可以在几分钟内解决几个房间和更复杂的任务，但最多也只有十几个机器人。”“除此之外，目前的算法无法克服寻找解决方案的大量可能性。”

在《国际机器人研究杂志》在线发表的一篇论文中，Zavlanos和他最近的博士研究生Yiannis Kantaros，现在是宾夕法尼亚大学的博士后研究员，提出了一种新的方法来应对这一挑战，称为STyLuS*，用于大规模最优时间逻辑综合，可以解决比现有算法处理的问题大得多的问题，有数百个机器人，数万个房间和高度复杂的任务，在很短的时间内。

线性时序逻辑，节点作为机器人运动的基础

要理解这种新方法的基础，首先必须理解线性时间逻辑，这并不像听起来那么可怕。假设你想给几个机器人编程，让它们每天从邻居那里收集邮件并送到邮局。线性时序逻辑是一种写下完成该任务所需的命令的方法。

例如，这些命令可能包括按顺序访问每个家庭，返回邮局，然后等待某人检索收集到的邮件，然后再次出发。虽然这在英语中可能很容易说出来，但在数学上却很难表达出来。线性时序逻辑可以通过使用自己的符号来做到这一点，尽管对普通观察者来说这些符号看起来像克林贡语，但它们对于表达复杂的控制问题非常有用。

坎塔罗斯说:“之所以使用线性这个术语，是因为时间点有一个基于离散线性时间模型的唯一继承者，而时态指的是使用直到、下一个、最终和总是等运算符。”“使用这种数学形式主义，我们可以构建复杂的命令，比如‘访问除第二家以外的所有房子’，‘按顺序访问第三家和第四家’，以及‘等到你去过第一家再去第五家。’”

为了找到满足这些复杂任务的机器人控制器，每个机器人的位置被映射到一个称为“节点”的离散数据点。然后，每个节点都存在多个其他节点，这些节点可能是机器人的下一步。

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

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

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

Kantaros说:“这意味着随着算法的发展，我们逐渐增长的这棵树越来越接近我们从未真正构建过的实际图。”“因为我们的增量图要小得多，所以很容易存储在内存中。此外，由于这个图是一个树，图搜索变得非常简单，因为现在我们只需要跟踪父节点的序列回到根就可以找到所需的路径。”

使用树木作为解决方案

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

研究人员表示，如果有答案，这种方法总能找到答案，而且最终总能找到可能的最佳答案。他们还表明，这种方法可以以指数速度得到答案。用10个机器人在50 * 50的网格空间中搜索——250个房子来取邮件——目前最先进的算法需要30分钟才能找到最佳解决方案。

STyLuS*在大约20秒内完成。

Zavlanos说:“我们甚至用200个生活在100 * 100网格世界中的机器人解决了问题，这对于今天的算法来说太大了。”“虽然目前还没有任何系统使用200个机器人来做递送包裹之类的事情，但未来可能会有。他们需要一个像STyLuS*这样的控制框架来满足复杂的基于逻辑的规则。”

您是否具有本内容中提到的主题的经验和专业知识?你应该考虑为我们的CFE媒体编辑团队做出贡献，并获得你和你的公司应得的认可。点击在这里开始这个过程。