MIT AAAI-17研究展示：为规划算法加入人类直觉

选自MIT

作者： Larry Hardesty

机器之心编译

整理：黄小天、蒋思源

每隔一年，自动规划与调度国际会议（International Conference on Automated Planning and Scheduling）会举行一次比赛，参会者设计的计算机系统试图找到规划问题的最佳解决方案，这些规划问题包含如安排航班或协调自主卫星组任务等。

然而，除了最简单直接的问题外，即使最好的规划算法仍然不如具有特殊解决问题才能的人类有效，例如麻省理工学院的学生。

麻省理工学院计算机科学与人工智能实验室的研究人员正通过给予自动化系统人类直觉的能力来提高系统的表现。通过以机器可读的形式编码杰出规划人员的策略，他们能够在一系列具有挑战性的问题上提高竞胜规划算法（competition-winning planning algorithms）10％至 15％的性能。

研究人员本周在 AAAI（Association for the Advancement of Artificial Intelligence）2017 的会议上展示了他们的研究成果。

MIT 航空航天学助理教授 Julie Shah 说：「在实验室和其他调查中，我们发现对于规划、调度和优化等任务，通常有一小部分人是真正杰出的人才，而我们是否可以从少数真正杰出人才那里获得洞察力和高层次策略等能力，并让一台机器利用这些杰出能力来解决问题，而不是直接通过普通大众的解决方法？」

会议论文（conference paper）的第一作者是 Joseph Kim，它是航天航空方向的研究生，且在 2016 年夏天本科时就在 Shah 的实验室担任研究实习生。

寻找规划者

在自动规划比赛（国际规划竞赛/IPC）中会提供给输入算法不同难易程度的相关问题任务。最简单的问题就只要求满足一些严格的约束条件：如给定一定数量的机场、飞机和在各个机场有确定目的地的乘客，是否可以在所有乘客都到达指定目的地且没有飞机空飞的情况下规划航班路线。

而更复杂的一类问题，即数值问题会增加一些灵活的数值参数：如你是否能找到一组飞行规划，它在满足原始问题的约束情况下，还能最小化飞机飞行的时间和燃油消耗。

最后，最为复杂的问题就是时间问题，它在数值问题的基础上添加了时序约束：即如何在最小化飞行时间与燃油消耗的同时，确保飞机可以在不同时间抵达和离开。

对于每个问题，算法有半个小时生成方案。方案的质量根据「成本函数」测量，例如将飞行总时间与燃油总消耗组合起来的方程式。

Shah、Kim 和 Banks 招募了 36 名麻省理工学院的本科生与研究生，并向他们每个人提出了两种不同比赛的规划问题，一个侧重于飞行线路，一个侧重于卫星定位。如同自动规划者，每个学生只有半个小时解决问题。Shah 说：「在这个世界上，麻省理工的学生基本是解决此类问题的专家，相信他们比绝大多数人做得更好。」

编码策略

当然，他们做得比自动规划者更好。在学生提交解决方案后，Kim 对他们用来解决问题的一般策略进行了采访。他们的答案大多是包含「飞机应该访问每个城市最多一次」和「对于每个卫星，在三次转向之内找到路线」之类的内容。

研究人员发现，大多数学生的策略可以使用称为线性时序逻辑（linear temporal logic）的形式语言来描述，并可用于向问题规范添加约束。由于不同的策略可以相互抵消，研究人员分别使用已经赢得他们各自比赛的规划算法来测试每个学生的策略。结果仅轻微变化。关于数值问题，飞行规划和卫星定位问题的平均改进分别为 13％和 16％;对时间问题的改善为 12％和 10％。

Shah 说：「当自动规划员使用人类的高级策略时，它提出的规划看起来更像是由人类制定的。「也许这个采取用户的高层次策略加入到机器算法中的方式，可以让人更容易理解规划的制定。

在正进行的工作中，Kim 和 Shah 正在使用自然语言处理技术（natural-language-processing techniques）使系统完全自动化，在无需人为干预的情况下，将用户对其高级策略的自由形式描述（free-form descriptions）转换为线性时间逻辑（natural-language-processing techniques）。