规划算法评估成功的概率，建议低风险的替代方案

想象一下，你可以告诉你的手机，你想从波士顿的家开车到纽约北部的一家酒店，你想在12:30左右在Applebee 's吃午饭，而且你不希望旅途花费超过4个小时。然后想象一下，你的手机告诉你，你只有66%的机会达到这些标准，但如果你能等到1点吃午饭，或者如果你愿意在TGI Friday 's吃饭，它可以把这个概率提高到99%。

这种应用是麻省理工学院计算机科学和人工智能实验室布莱恩·威廉姆斯团队的目标——尽管相同的底层框架已经导致了美国宇航局和伍兹霍尔海洋研究所用于计划任务的软件。

在本月举行的人工智能发展协会(AAAI)年会上，威廉姆斯团队的研究人员将展示一些算法，这些算法代表着朝着威廉姆斯所说的“更好的Siri”(苹果产品中的用户辅助应用程序)迈出的重要一步。但它们对任何计划任务都一样有用，比如安排航班或巴士路线。

与威廉姆斯一起，麻省理工学院航空航天系的研究生彭宇和方成开发了一种软件，可以让规划者指定约束条件和可靠性阈值，比如公交车应该至少有90%的时间准点。然后，在概率模型的基础上——该模型揭示了一些数据，比如沿着这条公路行驶的时间在2到10分钟之间波动——系统决定是否存在解决方案:例如，也许公共汽车的发车时间应该在一天中的某些时候错开6分钟，在其他时候错开12分钟。

然而，如果解决方案不存在，软件也不会放弃。相反，它提出了规划者可以放松问题约束的方法:公交车能否以12分钟的间隔到达目的地?如果规划者拒绝了提议的修正案，软件会提供另一种选择:你能在路线上增加一辆公交车吗?

短短的尾巴

该软件与以前的规划系统不同的一个方面是它可以评估风险。“直接处理概率总是很困难，因为它们总是给你的计算增加复杂性，”方舟子说。“所以我们增加了风险分配的想法。我们说，‘整个任务的风险预算是多少?让我们把它分了，把它作为一种资源来使用。’”

例如，在公共汽车路线上行驶一英里所花费的时间可以用概率分布表示，即钟形曲线，将时间与概率画出来。跟踪所有这些概率，并将它们组合到路线的每一英里，将产生巨大的计算量。但是，如果系统事先知道规划者可以容忍一定数量的失败，实际上，它可以将这种失败分配给分布中概率最低的结果，砍掉它们的尾巴。这使得它们在数学上更容易处理。

在AAAI，威廉姆斯和他的另一个学生安德鲁·王(Andrew Wang)发表了一篇论文，描述了如何有效地评估这些作业，以便为可解决的规划问题找到快速解决方案。但是Yu和fang在同一会议上发表的论文集中于识别那些阻碍问题解决的限制因素。

这就是问题所在

这两个程序都植根于图论。在这种情况下，图是一种数据表示，它由节点(通常表示为圆)和边(通常表示为连接节点的线段)组成。任何调度问题都可以用图来表示。节点表示事件，边表示事件必须发生的顺序。每条边也有一个相关的权重，表示从一个事件到下一个事件的花费——例如，公共汽车在站点之间行驶所花费的时间。

Yu、Williams和Fang的算法首先将一个问题表示为一个图，然后开始添加表示规划者施加的约束的边。如果问题是可解决的，表示约束的边的权值将处处大于表示事件之间转换代价的权值。然而，现有的算法可以快速定位图中权重不平衡的on循环。然后，麻省理工学院研究人员的系统计算出重新平衡循环的最低成本方法，并将其作为对问题初始约束的修改提交给规划者。

麻省理工学院

web.mit.edu

- CFE传媒编辑。查看更多控制工程制造IT和MES的故事．

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