欢迎光临
我们一直在努力
您的位置:首页>人工智能 >

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

想象一下,你可以告诉你的手机你想从波士顿的房子开车到纽约州北部的一家酒店,你想在12点30分左右在Applebee's吃午饭,而你不想要旅行需要四个多小时。然后想象一下,你的手机告诉你,你只有66%的机会达到这些标准 - 但如果你可以等到凌晨1点吃午饭,或者如果你愿意在TGI星期五吃饭,它可以得到那个概率高达99%。

这种应用是布莱恩威廉姆斯在麻省理工学院计算机科学和人工智能实验室的小组的目标 - 虽然同样的基础框架导致了NASA和伍兹霍尔海洋研究所用于计划任务的软件。

在本月人工智能促进协会(AAAI)年会上,威廉姆斯小组的研究人员将展示算法,这些算法代表了威廉姆斯所描述的“更好的Siri”的重要步骤 - Apple中的用户协助应用程序产品。但它们对于任何计划任务都是有用的 - 例如,安排航班或公交路线。

与麻省理工学院航空航天系研究生威廉姆斯,彭宇和程芳一起,开发了一种软件,允许规划人员指定约束条件 - 例如,沿某条路线的公共汽车应每隔10分钟到达目的地 - 和可靠性阈值,例如公交车应该至少90%的时间准时到达。然后,在概率模型的基础上 - 显示诸如沿着这一英里的道路的行驶时间在2到10分钟之间波动的数据 - 系统确定是否存在解决方案:例如,公共汽车的离开可能会错开六个一天中某些时间的分钟,其他时间的12分钟。

但是,如果不存在解决方案,则软件不会放弃。相反,它提出了计划者可以放松问题限制的方式:公共汽车能否以12分钟的间隔到达目的地?如果规划人员拒绝提议的修改,该软件提供了另一种选择:您可以在路线上添加公交车吗?

短尾巴

将软件与以前的计划系统区分开来的软件的一个方面是评估风险。“它总是很难直接处理概率,因为它们总是会增加计算的复杂性,”方说。“所以我们加入了这种风险分配的想法。我们说,'这个整个任务的风险预算是多少?让我们将其划分并将其用作资源。'“

例如,遍历公交线路任何一英里的时间可以用概率分布表示 - 钟形曲线,绘制时间与概率的关系。跟踪所有这些概率并将其复合到路线的每一英里将产生巨大的计算。但是,如果系统事先知道计划者可以容忍一定程度的失败,那么它实际上可以将该失败分配给分布中的最低概率结果,从而消除它们的尾部。这使得他们在数学上更容易处理。

在AAAI,威廉姆斯和他的另一个学生安德鲁·王(Andrew Wang)有一篇论文描述了如何有效地评估这些作业,以便找到可解决的规划问题的快速解决方案。但与Yu和Fang一起出现在同一会议上的论文集中于确定那些阻止问题解决的限制因素。

有磨擦

这两个程序都植根于图论。在此上下文中,图形是由节点组成的数据表示,通常描绘为圆形和边缘,通常描绘为连接节点的线段。任何调度问题都可以表示为图形。节点表示事件,边缘表示事件必须发生的顺序。每个边缘也有一个相关的重量,表示从一个事件进入下一个事件的成本 - 例如,公交车在停靠点之间行驶的时间。

Yu,Williams和Fang的算法首先将问题表示为图形,然后开始添加表示计划者施加的约束的边缘。如果问题是可解的,则表示约束的边的权重将在任何地方都大于表示事件之间转换成本的权重。然而,现有算法可以快速回归图中的权重不平衡的循环。麻省理工学院的研究人员系统然后计算出重新平衡循环的最低成本方式,它将其作为对问题初始约束的修改呈现给计划者。

“这些论文非常有趣,”Nuance Communications的研究科学家沉嘉莹说,该公司开发了苹果Siri使用的语音识别技术。“他们有一系列关于机会限制的论文,但在最近的论文中,他们增加了不确定性,这使得它可以模拟的问题更复杂,更难以预测和更现实。”

在Nuance,“我们对约束放松非常感兴趣,包括机会限制,”Shen补充道。“如果你暴露了在规划阶段需要考虑的事项,那么你在执行计划方面的成功率要高得多。

免责声明:本网站图片,文字之类版权申明,因为网站可以由注册用户自行上传图片或文字,本网站无法鉴别所上传图片或文字的知识版权,如果侵犯,请及时通知我们,本网站将在第一时间及时删除。