研究人员开发了一种规划算法,如果初始计划被证明风险太大,则生成应急计划。
技术

规划算法在物流与控制中得到了广泛的应用。他们可以帮助安排航班和公交路线,引导自主机器人,以及确定电网的控制策略,除此之外。

近年来,规划算法已经开始考虑不确定性——旅行时间的变化,自主机器人之间不稳定的通信,不完美的传感器数据,诸如此类。这使得规划问题的规模成指数增长,但研究人员发现聪明的方法以有效地解决它。

现在,麻省理工学院和澳大利亚国立大学(ANU)的研究人员已经使这个问题更加复杂,通过开发同样生成应急计划的规划算法,如果最初的计划证明风险太大。它还识别条件,例如,传感器读数或延迟-这应该触发切换到特定的应急计划。

尽管由于制定应急计划而增加了额外的劳动力,该算法仍然提供数学保证,其计划的失败风险低于某个阈值,用户设置的。

“计划意外事件的问题在于,有太多事情可能出错,如果针对所有可能的意外情况生成计划,你会发疯的,“布莱恩·威廉姆斯说,航空和航天学教授,其研究小组开发了新系统。“那么问题就结束了,你会产生多少意外情况?““

Pedro Santana航空航天研究生,是描述该系统的论文的第一作者,在上周末的人工智能发展协会的年会上,他提出了这个问题。威廉姆斯和西尔维·蒂包也加入了他的行列,澳大利亚国立大学计算机科学教授,澳大利亚国家信息通信技术(NICTA)研究项目的研究员,它与麻省理工学院有合作关系。

概率修剪


正如威廉姆斯解释的,规划人员面临的可能决策的范围可以表示为名为图表.一个图由节点组成,通常用圆表示,和边,它们表示为连接节点的线段。网络图和流程图是图的常见示例。

在计划系统中,图的每个节点表示决策点,比如,“我应该坐公共汽车还是地铁?“通过图表的路径可以根据它提供的奖励来评估——你安全到达目的地——以及它所施加的惩罚——你会迟到5分钟。最佳计划是最大化报酬的计划。

将概率因素考虑进来使得这种奖励计算更加复杂:平均公交出行时间可能是15分钟,但是有可能是35岁;地铁的平均行程可能是18分钟,但是几乎不会超过24岁。在这方面,即使是相对简单的计划任务,草拟应急计划可能非常耗时。

使问题变得容易处理,麻省理工学院和非国立大学的研究人员从一些人那里借用了一种技术。前期工作来自威廉姆斯集团。在计划者开始构造图之前,它要求用户设置风险阈值。一位研究人员试图开发一个数百万美元的数据收集计划。水下机器人,例如,他们可能对机器人接受所有传感器读数的90%概率感到满意,但他们可能希望99.9%概率机器人不会高速与岩石表面碰撞。

研究人员的算法将这些阈值视为风险预算它在探索通过图表的路径时花费。如果规划者确定图的给定分支将超过预算,它把它关掉了。

保持乐观


这种决心必须迅速,然而。所以研究人员使用一些简单的经验法则——或者,用计算机来说,启发式-评估分支。穿过给定分支的每条路径,例如,可能包括两个点之间不同的汽车路线,每个都有它自己的可能旅行时间的概率分布。但是如果在点之间穿过一条直线,以最大允许的速度,仍然会招致无法忍受的延误,评估每条路线的概率是没有意义的。这个分支可以消除。

只要启发式方法是乐观的-可能低估风险,但不要高估风险-规划者可以切断分支而不损害最终计划的质量。有时这些启发式是特定于应用程序的,就像对路径进行几何评估一样。但是有时候不是。

例如,概率分布给规划计算增加如此复杂性的原因之一是它们是非线性的:它们的图呈现出比简单线更复杂的形状。在6月份的自动规划和调度国际会议上提出的一份文件中,桑塔纳-又是第一作者-威廉姆斯,麻省理工学院的同事们,巴西圣保罗大学,Caltech描述了一种生成概率分布的线性近似的方法,这种方法在数学上更容易处理。

这些近似值是乐观的:它们从不高估风险。但是计算机可以比非线性分布更快地评估它们。这些启发式方法为研究人员的规划系统能实时更新计划提供了希望,根据新的信息,以及提前生成应急计划。

http://www.engineersjou..ie/wp-content/uploads/2016/02/aaaalgor.jpghttp://www.engineersjou..ie/wp-content/uploads/2016/02/aaaalgor-300x300.jpg戴维奥里奥登技术ICT,麻省理工学院研究
规划算法在物流与控制中得到了广泛的应用。他们可以帮助安排航班和公交路线,引导自主机器人,以及确定电网的控制策略,近年来,规划算法已经开始考虑不确定性——旅行时间的变化,…之间不稳定的通信