多智能体系统:杜克大学新研究能够协调数百个机器人之间的复杂行为
近日，来自杜克大学的研究团队在「国际机器人研究国际期刊」上发表的一篇新论文提出了一种名为 STyLuS * 的新方案 ，用于大规模的最佳时态逻辑综合，可以在短时间内以数百个机器人，数万个房间和高度复杂的任务解决比当前算法所能处理的问题大得多的问题。
当控制算法使机器人在空间中移动时，机器人可以处于的每种状态都由3D图形上的点表示。随着算法探索新选择，它会发现失败和潜在的下一步行动。此图表示所探索的所有错误动作（蓝色）和一条正确路线（红色）。
要了解新方法的基础，必须首先了解线性时态逻辑，这种线性时域逻辑并不像听起来那样可怕。
假设在一个几层楼高许多房间，有数百个障碍物和数千个检查场所的建筑物中，数十个机器人作为一个有凝聚力的单元移动。他们以搜索模式展开，以彻底检查整个建筑物，同时拆分任务，以免浪费时间重复返回自己的路径或重新检查其他机器人已经去过的地方。线性时态逻辑是一种记录完成此任务所需的命令方式。线性时态逻辑可以通过使用自己的符号来做到这一点，它们对于表达复杂的控制问题非常有用。
为了找到满足此类复杂任务的机器人控制器，每个机器人的位置都映射到称为“节点”的离散数据点中。然后，从每个节点开始，存在多个其他节点，这些节点可能是机器人的下一步。
传统的控制器会搜索这些节点中的每个节点以及它们之间的潜在路径，然后才能找到最佳的导航方式。但是，随着要访问的机器人和位置数量的增加，以及要遵循的逻辑规则变得越来越复杂，解决方案空间在非常短时间内就变得非常大。
为了避开这个问题，研究人员提出了一种新方法，而不是完整地构造这些难以置信的大图形，而是使用树结构创建较小的近似值。在该过程的每个步骤中，该算法都会从大型图中随机选择一个节点，将其添加到树中，然后重新连接树中节点之间的现有路径，以找到从头到尾的更多直接路径。这意味着随着算法的发展，逐渐增长的那棵树越来越接近实际图形。由于增量图要小得多，因此很容易存储在内存中。此外，由于该图是一棵树，因此图搜索（否则它具有指数复杂性）变得非常容易，因为现在我们只需要跟踪父节点的序列回到根源以找到所需的路径。
该研究中利用STyLuS *方法能在满足基于复杂逻辑规则的同时完成任务，当前最先进的算法需要30分钟才能找到最佳解决方案，STyLuS *只需约20秒即可完成。获取更多前沿科技 研究访问：https://byteclicks.com
你可能感兴趣的文章：
