通过算法，计划系统可以有效地生成备份计划

规划算法广泛应用于物流和控制。他们可以帮助安排航班和公交路线，引导自主机器人并确定电网的控制策略等。

近年来，规划算法已开始考虑不确定性，例如旅行时间的变化，自主机器人之间的通信不稳定，传感器数据不完善等。这导致规划问题的规模成倍增长，但是研究人员找到了有效解决问题的巧妙方法。

现在，麻省理工学院和澳大利亚国立大学（ANU）的研究人员开发了一种计划算法，该算法还可以生成应急计划，从而使问题变得更加复杂。它还确定了条件（例如传感器读数或发生的延误），这些条件应触发切换到特定的应急计划。

尽管生成应急计划会产生额外的工作量，但该算法仍提供数学上的保证，以确保其计划的失败风险降至用户设置的某个阈值以下。

“计划意外事件的问题是，有太多事情可能出错，如果您为所有可能的意外事件制定了计划，您就会发疯了，”航空和航天学教授Brian Williams说，他的团队开发了新系统。“因此，问题最终变成了’您产生多少意外事件？’”

航空航天专业研究生Pedro Santana是描述该系统的论文的第一作者，他在上周末的人工智能进步协会年会上发表了论文。澳大利亚国立大学计算机科学教授，澳大利亚国家信息通信技术澳大利亚（NICTA）研究计划的研究员Williams和SylvieThiébaux也加入了他的行列，该计划与MIT有合作关系。

概率修剪

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

在规划系统中，图形的每个节点代表一个决策点，例如“我应该乘公共汽车还是地铁？” 可以根据图表提供的奖励（可以安全到达目的地）及其所施加的罚款来评估图表中的路径，您将迟到五分钟。最佳计划是使报酬最大化的计划。

考虑到概率，这种类型的报酬计算变得更加复杂：平均公共汽车旅行可能需要15分钟，但有可能达到35分钟；平均地铁旅行时间可能是18分钟，但几乎不会超过24分钟。在这种情况下，即使是相对简单的计划任务，制定应急计划也会非常耗时。

为了使问题更容易解决，麻省理工学院和ANU研究人员借鉴了威廉姆斯小组早期工作中的一项技术。在计划者开始构造图形之前，它会要求用户设置风险阈值。例如，研究人员试图为价值数百万美元的水下机器人制定数据收集计划，可能会对90％的概率该机器人将获得预期的所有传感器读数感到满意，但他们可能希望99.9％的概率机器人不会高速碰撞岩石表面。

研究人员的算法将这些阈值视为“风险预算”，它在探索通过图表的路径时会花费此费用。如果计划者确定图表的给定分支将超出预算，则将其关闭。

保持乐观

但是，该决定必须迅速。因此，研究人员使用一些简单的经验法则或计算机启发法来评估分支机构。例如，通过给定分支的每条路径都可能在两个点之间包含不同的汽车路线，每个点都有其可能的行驶时间概率分布。但是，如果以允许的最大速度在两点之间直线行驶仍会导致无法忍受的延误，那么评估每条路线的概率毫无意义。分支可以消除。

只要试探法是乐观的（可能会低估风险，但绝不会高估风险），计划人员就可以在不影响最终计划质量的情况下放弃分支机构。有时，这些启发式方法是特定于应用程序的，例如以几何方式评估路线的方法。但是有时候他们不是。

例如，概率分布为规划计算增加了太多复杂性的原因之一是它们是非线性的：它们的图形所具有的形状比简单的线条更复杂。在6月举行的国际自动规划和调度会议上发表的一篇论文中，桑塔纳（再次是第一作者）威廉姆斯和麻省理工学院，巴西圣保罗大学以及加州理工学院的同事描述了一种生成概率分布线性近似的方法。在数学上更容易使用。

这些近似值是乐观的：它们从不高估风险。但是计算机可以比非线性分布更快地评估它们数千倍。这种启发式方法为研究人员的计划系统可以根据新信息动态更新计划提供了希望，并可以预先生成应急计划。

NASA喷气推进实验室系统架构和行为小组技术组主管Michel Ingham说：“作者已经解决了与NASA任务高度相关的非常重要的问题，我们越来越依赖于编入航天器的自主行为。” 。

“他们的工作与小行星和彗星表面的火星探测任务，火星等行星体或对欧洲行星和土卫二的外行星冰冷卫星的不太遥远的未来任务特别相关。我们的机器人探索这些地点的航天器将面临挑战，要在自身状态和周围环境状态存在很大不确定性的情况下有效执行任务，同时要避免障碍和危险。他们将需要在实现自己的科学和探索目标与保持健康和摆脱麻烦之间取得适当的平衡。”