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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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