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

当控制算法使机器人在空间中移动时，机器人可以处于的每种状态都由3D图形上的点表示。随着算法探索新的选择，它会发现失败和潜在的下一步行动。此图表示所探索的所有错误动作（蓝色）和一条正确的路线（红色）。

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

在2002年大片《少数派报告》中最令人难忘的一幕中，汤姆·克鲁斯（Tom Cruise）被迫躲藏在一群蜘蛛般的机器人中，他们搜寻着高耸的公寓大楼。虽然大多数观众可能会因小型敏捷猎犬的替代而感到困惑，但计算机工程师可能会对他们优雅的控制系统感到惊讶。

在一个有几层楼高的建筑物中，其中有无数的房间，数百个障碍物和数千个要检查的地方，数十个机器人作为一个有凝聚力的单元移动。他们以搜索模式展开，以彻底检查整个建筑物，同时拆分任务，以免浪费时间加倍返回自己的路径或重新检查其他机器人已经去过的地方。

对于人类控制器而言，这种凝聚力将很难实现，更不用说人工控制器实时计算了。

“如果控制问题在一个只有几个房间的世界中生活着三到四个机器人，并且如果通过简单的逻辑规则指定了协作任务，那么可以使用最先进的工具来计算出最佳解决方案“这可以在合理的时间内满足任务要求。”杜克大学机械工程与材料科学副教授Mary Milus Yoh和小Harold L. Yoh表示：“ Michael M. Zavlanos

Zavlanos说：“而且，如果您不关心最佳解决方案，则可以在几分钟之内解决更多房间和更复杂的任务，但仍然只有十几个机器人顶。”“除此之外，当前的算法无法克服寻找解决方案的巨大可能性。”

Zavlanos及其博士研究生Yiannis Kantaros在4月29日在线发表在《国际机器人研究国际期刊》上的新论文中，他现在是宾夕法尼亚大学的博士后研究员，他提出了应对这一挑战的新方法，即STyLuS * ，用于大规模的最佳时间逻辑综合，可以在短时间内以数百个机器人，数万个房间和高度复杂的任务解决比当前算法所能处理的问题大得多的问题。

要了解这种新方法的基础，必须首先了解线性时态逻辑，它并不像听起来那样可怕。假设您要对少数几个机器人进行编程，以便每天从附近收集邮件并将其发送到邮局。线性时序逻辑是一种记录完成此任务所需的命令的方式。

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

Kantaros说：“使用线性一词是因为时间点具有基于离散线性时间模型的唯一后继，而时间是指使用运算符，例如直到，下一个，最终和始终。”“使用这种数学形式主义，我们可以构建复杂的命令，例如'参观除二号房屋之外的所有房屋'，'依次参观三号和四号房屋'和'等到您住过一所房屋后再进入五号房屋。 。”

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

一个简单的问题是，有五个机器人生活在一个有十个房屋的世界中，可能包含数百万个节点，捕获了所有可能的机器人位置和行为以实现任务。这需要大量内存来存储和处理能力以进行搜索。

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

Kantaros说：“这意味着随着算法的发展，我们逐渐增长的树将越来越接近我们从未真正构造的实际图形。”“由于我们的增量图要小得多，因此很容易存储在内存中。而且，由于该图是一棵树，因此图搜索变得非常容易，否则它将具有指数复杂性，因为现在我们只需要将父节点的序列追溯到根即可找到所需的路径。”

长期以来，人们一直接受不能将生长的树木用于搜索这类机器人控制问题的可能解决方案的空间。但是在论文中，Zavlanos和Kantaros表明，他们可以通过实施两个巧妙的技巧使它起作用。首先，该算法根据有关手头任务的信息选择要添加的下一个节点，这使得树可以快速地近似解决该问题。其次，即使该算法种植了树木，它仍然可以检测原始图空间中捕获此类时间逻辑任务解决方案的周期。

研究人员表明，如果有答案，这种方法将总能找到答案，并且最终总会找到最佳答案。他们还表明，该方法可以指数级快速到达该答案。遇到10个机器人在50×50的网格空间中搜索的问题（需要250个房屋来取邮件），当前最先进的算法需要30分钟才能找到最佳解决方案。

STyLuS *只需约20秒即可完成。

Zavlanos说：“我们甚至用200个机器人解决了问题，这些机器人生活在100 x 100的网格环境中，对于当今的算法而言，它太大了。”“虽然目前没有任何系统使用200个机器人来完成诸如交付包裹之类的工作，但将来可能会出现。他们将需要像STyLuS *这样的控制框架，才能在满足复杂的基于逻辑的规则的同时交付它们。”

###

参考：“ STYLUS *：大型多机器人系统的时间逻辑最优控制综合算法”，作者：Yiannis Kantaros和Michael M Zavlanos，2020年4月29日，国际机器人研究杂志。DOI：
10.1177％2F0278364920913922

这项研究得到了空军科研办公室（FA95501910169）和海军−研−究−办公室（N000141812374）的支持。−−−