研究人员将人类的直觉加入到规划算法中

每隔一年，自动化规划与调度国际会议(International Conference on Automated Planning and Scheduling)都会举办一场竞赛，由会议参与者设计的计算机系统试图找到规划问题的最佳解决方案，比如安排航班或协调自主卫星团队的任务。

然而，在除了最直接的问题之外的所有问题上，即使是最好的规划算法仍然不如具有解决问题特殊天赋的人类有效。

麻省理工学院计算机科学与人工智能实验室(CSAIL)的研究人员正试图通过赋予自动化规划者人类直觉的好处来改进它们。通过以机器可读的形式编码高绩效人类规划者的策略，他们能够在一系列具有挑战性的问题上将竞争获胜的规划算法的性能提高10%至15%。

麻省理工学院航空航天学助理教授朱莉·沙阿(Julie Shah)说:“在实验室和其他调查中，我们发现，在计划、调度和优化等方面，通常有一小部分人真的很擅长。”“我们能否从少数真正优秀的人那里获得洞察力和高水平的策略，让机器利用这些知识，比绝大多数人更好地解决问题?”

会议论文的第一作者是约瑟夫·金(Joseph Kim)，他是航空航天专业的研究生。沙阿和克里斯托弗·班克斯(Christopher Banks)也加入了他的队伍，后者是诺福克州立大学的本科生，2016年夏天在沙阿的实验室实习。

人为因素

参加自动规划竞赛(称为国际规划竞赛(IPC))的算法被赋予了不同难度的相关问题。最简单的问题需要满足一些严格的约束条件:例如，给定一定数量的机场，一定数量的飞机，每个机场有特定目的地的一定数量的人，是否有可能规划飞机的飞行路线，使所有乘客都到达目的地，但飞机永远不会空飞?

更复杂的一类问题——数值问题——增加了一些灵活的数值参数:你能否找到一组飞行计划，既满足原始问题的约束条件，又能使飞机的飞行时间和燃料消耗最小化?

最后，最复杂的问题——时间问题——在数值问题上增加了时间限制:你能否在确保飞机在特定时间到达和起飞的同时最小化飞行时间和燃料消耗?

对于每个问题，算法有半小时的时间来生成计划。飞行计划的质量是根据一些“成本函数”来衡量的，比如一个结合了总飞行时间和总燃油消耗的方程。

沙阿、金和班克斯招募了36名麻省理工学院的本科生和研究生，并让他们每人从两场不同的比赛中提出规划问题，一场侧重于飞机航路，另一场侧重于卫星定位。像自动计划者一样，学生们有半小时的时间来解决每个问题。

编码策略

在学生们提交了他们的解决方案后，金采访了他们解决问题的一般策略。他们的答案包括“飞机最多应该访问每个城市一次”和“对于每个卫星，在三次或更少的时间内找到航线”。

研究人员发现，绝大多数学生的策略都可以用一种叫做线性时间逻辑的形式语言来描述，这种语言反过来又可以用来给问题规范添加约束。由于不同的策略可能会相互抵消，研究人员分别测试了每个学生的策略，使用的是在各自的比赛中获胜的规划算法。结果有所不同，但变化不大。在数值问题上，飞行规划和卫星定位问题的平均改进率分别为13%和16%;在时间问题上，改善率分别是12%和10%

沙阿说:“当规划者使用了这个人的这些高级策略时，它提出的计划看起来更像人为的计划。”“也许有一个桥梁，可以让用户的高级策略对机器有用，通过对机器有用，也许可以让它更容易被人理解。”

在正在进行的工作中，Kim和Shah正在使用自然语言处理技术使系统完全自动化，这样它就可以在没有人为干预的情况下，将用户对其高级策略的自由形式描述转换为线性时间逻辑。

麻省理工学院

www.mit.edu

-由克里斯·瓦夫拉编辑，制作编辑，控制工程， CFE传媒，cvavra@cfemedia.com．查看更多控制工程资产管理故事。

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