由于控制算法使机器人在空间中移动，机器人可以处于的每一种状态都用三维图形上的一个点来表示。随着算法探索新的选项，它会发现失败和潜在的下一步行动。这张图代表所有错误的移动(蓝色)和一条正确的路线(红色)。图片来源:Michael Zavlanos, Duke

　　一种设计多个机器人运动计划的新方法在搜索空间中生长“树”，以在一小部分时间内解决复杂的问题。

　　在2002年的大片《少数派报告》(Minority Report)中，有一个让人印象深刻的场景:汤姆·克鲁斯(Tom Cruise)被迫躲避一群蜘蛛般的机器人，这些机器人在一栋高耸的公寓楼里四处搜寻。当大多数观众可能被这些小巧、敏捷的“侦探犬”替代品惊呆时，计算机工程师可能会对它们优雅的控制系统感到惊叹。

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

　　这种内聚性对于人类控制器来说很难实现，更不用说人工控制器实时计算了。

　　杜克大学机械工程与材料科学副教授迈克尔·m·扎夫拉诺斯(Michael M. Zavlanos)和小哈罗德·l·尤(Harold L. Yoh Jr.)说:“如果一个控制问题需要三到四个机器人生活在一个只有几个房间的世界里，如果协作任务由简单的逻辑规则指定，那么有最先进的工具可以计算出在合理时间内满足任务的最优解决方案。”

　　扎夫拉诺斯说:“如果你不关心可能的最佳解决方案，你可以在几分钟内解决更多的房间和更复杂的任务，但最多也只有12个机器人。”“如果超过这个数值，目前的算法就无法克服找到解决方案的大量可能性。”

　　在4月29日在线发表在《国际机器人研究杂志》上的一篇新论文中，Zavlanos和他最近的博士研究生、宾夕法尼亚大学博士后研究员Yiannis Kantaros提出了一种新的方法来应对这一挑战，名为STyLuS*，用于大规模最优时间逻辑合成，它可以解决比当前算法所能处理的大得多的问题，通过数百个机器人、数万个房间和高度复杂的任务，只花了一小部分时间。

　　要理解新方法的基础，必须首先理解线性时间逻辑，它并不像听起来那么可怕。假设您想要编写一些机器人，让它们每天从附近的社区收集邮件并将其送到邮局。线性时间逻辑是记录完成此任务所需命令的一种方法。

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

　　Kantaros说:“之所以使用线性这个术语，是因为时间点在离散线性时间模型的基础上有一个独特的继承者，而时间点指的是直到、下一个、最终和总是等运算符的使用。”“使用这种数学形式，我们可以构建复杂的命令，比如‘拜访除2号之外的所有房子’，‘按顺序拜访3号和4号房子’，以及‘等到你去过1号房子再去5号房子’。’”

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

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

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

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

　　对于这类机器人控制问题，人们早就认为不能用树木来寻找可能的解决方案。但在论文中，扎夫拉诺斯和坎塔罗斯表明，他们可以通过实施两个巧妙的技巧来实现这一目标。首先，算法根据手头任务的信息选择添加的下一个节点，这使得树能够快速地逼近问题的良好解。第二，即使算法生长树，它仍然可以检测原始图空间中的循环，捕获此类时间逻辑任务的解决方案。

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

　　STyLuS*可以在20秒内完成。

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

　　# # #

　　该研究由空军科学研究办公室(FA9550?19?1?0169)和海军研究办公室(N00014?18?1?2374)支持。