AI Planning and Mathematical Programming

人工智能规划与数学规划

• 批准号: RGPIN-2015-05072
• 负责人: Beck, Chris
• 金额: $ 3.64万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=613339
• 关键词: AI; Planning; Mathematical; Programming

Many of the day-to-day activities of people and organizations require planning and scheduling: deciding what actions to do to achieve a set of goals and deciding when actions should be done and with what resources. A daily commute might consist of deciding the latest time one can leave home to arrive in time for an important meeting while taking into account different ways to travel (bike, car, public transit), the time each one will take, and the interaction with other goals (e.g., if I drive I won't be able to have a drink with colleagues after work). As another example, a company such as Amazon must use labour, warehouse space, trucks, and fuel to coordinate the reception, storage, order-taking, packing, and delivery of goods. Artificial Intelligence planning has made substantial strides over the past 15 years, primarily addressing the problem of what actions to take. In contrast, the most successful technology to deal with choices about the timing and resource choices for actions arises from the mathematical programming and constraint programming disciplines. As AI planning technology is being increasingly used for real-world applications, it must increasingly make decisions about time and resources. The proposed research program attacks the challenges of reasoning about what to do, when to do it, and what resources to use. Three proposed research themes are unified under the hypothesis that mathematical programming encompasses a suite of problem solving techniques and theoretical foundations that can be extended and integrated with AI planning to address these challenges. Theme 1 will seek to unify and extend existing mixed integer linear programming (MILP) approaches to solving the AI planning problem with time and resources and to develop new planning technology based on Constraint Integer Programming (CIP). Theme 2 will focus on the fundamental AI technique of A* search and develop it to solve planning problems with resources and time in three ways: focusing on solving simple scheduling problems; using LP relaxations to compute A* heuristics; and developing the relationship among A* search, dynamic programming, and multi-valued decision diagrams. Theme 3 will take a principled approach to the application of problem decomposition to AI planning problems, focusing on the mathematical programming patterns of lazy constraint generation and column generation. This research program is focused on fundamental advances in solving AI planning problems that require reasoning about time and resources. To ground the research, the program will be conducted in parallel with an externally-funded, collaborative robotics project that is placing robots in long-term care homes. This application embodies the challenges we address in this program. While it is separate from what is being proposed here, the robot planning application will serve as an inspiration and test-bed.

人们和组织的许多日常活动都需要计划和安排：决定采取什么行动来实现一系列目标，并决定何时采取行动以及使用什么资源。每天的通勤可能包括决定一个人可以离开家及时到达重要会议的最晚时间，同时考虑不同的旅行方式（自行车，汽车，公共交通），每一个将花费的时间，以及与其他目标的相互作用（例如，如果我开车，下班后就不能和同事喝一杯了）。再举一个例子，像亚马逊这样的公司必须使用劳动力、仓库空间、卡车和燃料来协调货物的接收、存储、接单、包装和交付。 人工智能规划在过去的15年里取得了长足的进步，主要解决了采取什么行动的问题。相比之下，最成功的技术，以处理有关的时间和资源选择的选择行动产生的数学规划和约束规划学科。随着人工智能规划技术越来越多地用于现实世界的应用，它必须越来越多地做出关于时间和资源的决策。 拟议的研究计划攻击的挑战，推理做什么，什么时候做，以及使用什么资源。三个拟议的研究主题是统一的假设下，数学编程包括一套解决问题的技术和理论基础，可以扩展和集成人工智能规划，以解决这些挑战。 主题1将寻求统一和扩展现有的混合整数线性规划（MILP）方法，以解决时间和资源的人工智能规划问题，并开发基于约束优化规划（CIP）的新规划技术。 主题2将专注于A* 搜索的基本人工智能技术，并通过三种方式开发它来解决资源和时间的规划问题：专注于解决简单的调度问题;使用LP松弛来计算A* 算法;以及开发A* 搜索，动态规划和多值决策图之间的关系。 主题3将采用原则性的方法将问题分解应用于AI规划问题，重点关注惰性约束生成和列生成的数学编程模式。 该研究计划的重点是解决需要对时间和资源进行推理的人工智能规划问题的基本进展。为了使研究接地，该计划将与外部资助的协作机器人项目同时进行，该项目将机器人放置在长期护理院中。该应用程序体现了我们在该计划中解决的挑战。虽然它与这里提出的是分开的，但机器人规划应用程序将作为一个灵感和测试平台。