自动应急规划的规划算法

规划算法广泛应用于物流和控制领域。它们可以帮助安排航班和巴士路线，指导自主机器人，并确定电网的控制政策等等。

近年来，规划算法已经开始考虑不确定性因素——旅行时间的变化、自主机器人之间不稳定的通信、不完善的传感器数据等等。这导致规划问题的规模呈指数级增长，但研究人员已经找到了有效解决这个问题的聪明方法。

麻省理工学院和澳大利亚国立大学(ANU)的研究人员开发了一种规划算法，如果最初的计划被证明风险太大，该算法也会生成应急计划，从而使问题变得更加复杂。它还可以识别应该触发切换到特定应急计划的条件，比如传感器读数或发生的延迟。

尽管生成应急计划会带来额外的劳动，但该算法仍然提供了数学上的保证，确保其计划的失败风险低于用户设置的某个阈值。

“制定应急计划的问题在于，有太多事情可能会出错，如果你为所有可能的突发事件制定计划，你会发疯的，”布莱恩·威廉姆斯(Brian Williams)说，他是航空航天学教授，他的团队开发了这个新系统。“所以问题就变成了，‘你能产生多少偶发事件?’”

佩德罗·桑塔纳(Pedro Santana)是航空航天专业的研究生，他是描述该系统的论文的第一作者，他在上周末的人工智能发展协会(Association for the Advancement of Artificial Intelligence)年会上发表了这篇论文。Williams和Sylvie Thiébaux(澳大利亚国立大学计算机科学教授，澳大利亚国家信息通信技术澳大利亚(NICTA)研究项目的研究员，该项目与麻省理工学院有合作关系)也加入了他的队伍。

概率修剪

正如Williams解释的那样，计划者可能面临的决策范围可以表示为一种称为图的数据结构。图由节点(通常用圆表示)和边(用连接节点的线段表示)组成。网络图和流程图是我们熟悉的图形示例。

在规划系统中，图的每个节点代表一个决策点，例如，“我应该乘公共汽车还是地铁?”通过图表的路径可以根据它提供的奖励(你安全到达目的地)和它施加的惩罚(你将迟到五分钟)来评估。最优的计划是奖励最大化的计划。

考虑到概率因素，这类奖励计算就变得更加复杂:乘坐公交的平均时间可能是15分钟，但也有可能是35分钟;坐地铁的平均时间可能是18分钟，但几乎不会超过24分钟。在这种情况下，即使是相对简单的计划任务，仔细研究应急计划也会耗费大量时间。

为了解决这个问题，麻省理工学院和澳大利亚国立大学的研究人员借鉴了威廉姆斯团队早期工作中的一项技术。在规划器开始构建图形之前，它要求用户设置风险阈值。例如，一个研究人员试图为一个价值数百万美元的水下机器人制定一个数据收集计划，他可能会满足于机器人有90%的概率获得它应该得到的所有传感器读数，但他们可能想要99.9%的概率机器人不会高速撞击岩石表面。

研究人员的算法将这些阈值视为在图中探索路径时所花费的“风险预算”。如果规划器确定图的某个分支将超出预算，则将其删除。

保持乐观

然而，这种决定必须迅速做出。因此，研究人员使用一些简单的经验法则——或者用计算机术语来说，启发式法则——来评估分支。例如，通过给定分支的每条路径可能包括两点之间的不同汽车路线，每条路线都有自己的可能行驶时间的概率分布。但是，如果以允许的最大速度在两点之间穿越直线，仍然会导致无法忍受的延迟，那么就没有必要评估每条路线的概率。分支可以消除。

只要启发式是乐观的——可能低估了风险，但绝不会高估它——计划者就可以在不影响最终计划质量的情况下砍掉分支。有时，这些启发式是特定于应用程序的，比如以几何方式评估路由的启发式。但有时并非如此。

例如，概率分布给规划计算增加如此多复杂性的原因之一是它们是非线性的:它们的图形比简单的线条更复杂。在今年6月的自动化规划与调度国际会议上发表的一篇论文中，桑塔纳(同样是第一作者)威廉姆斯和麻省理工学院(MIT)、巴西São保罗大学(University of Paulo)以及加州理工学院(Caltech)的同事们描述了一种生成概率分布线性近似的方法，这种方法在数学上更容易处理。

这些近似是乐观的:他们从不高估风险。但是计算机计算它们的速度要比非线性分布快几千倍。这样的启发式提供了希望，研究人员的计划系统可以根据新的信息实时更新计划，并提前生成应急计划。

麻省理工学院

www.mit.edu

编辑克里斯·瓦夫拉，制作编辑，控制工程， CFE传媒，cvavra@cfemedia.com．看到额外的控制工程制造业IT故事．

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