NSF-BSF: RI: Small: Planning and Acting While Time Passes

NSF-BSF：RI：小型：随着时间的推移进行规划和行动

• 批准号: 2008594
• 负责人: Wheeler Ruml
• 金额: $ 49.98万
• 依托单位: University of New Hampshire
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008594&HistoricalAwards=false
• 关键词: NSF; BSF; RI; Small; Planning

Planning allows intelligent systems to select actions aimed towards achieving their goals. However, traditional planning methods assume that the world evolves slowly enough, or that the problems to be solved are sufficiently simple, that the world can be considered static during planning. This limitation means that most current planners are unable, for example, to realize that it might be better to quickly find a suboptimal plan to take the bus that is about to leave, rather than to carefully deliberate about optimal plans and thereby miss the bus altogether. Currently, planning representations and algorithms are laboriously manually engineered to ensure that the system responds quickly enough for the intended application, essentially ducking the issue of the passage of time while the system is planning. This project enables more robust and general-purpose intelligent systems by developing new "situated planning" methods that reason about their own reasoning enough to overcome this limitation.The project will consider two settings for situated planning. The first is the traditional batch setting, in which all decisions are made before plan execution begins. Three challenges will be addressed: 1) Formalizing a model of planning while time passes and analyzing its computational complexity, 2) Simplifying the resulting "reasoning about reasoning" problem enough that it can be approximately solved repeatedly during the planning process, including identifying tractable subclasses and greedy heuristics, and 3) Estimating the information needed for doing this reasoning on-line. The second setting is incremental planning, where execution of actions can be interleaved with additional planning. Three additional challenges will be addressed: 4) Formalizing situated planning with action costs , 5) Developing a continual situated planner that improves a plan while it is being executed, and 6) Addressing online situated planning, where actions can be dispatched for execution before a complete plan has been found. Solving these situated planning problems will result in practical and flexible planners that can smoothly interpolate their behavior in a time-aware way between batch and incremental as appropriate, thereby broadening the range of applications that can be addressed by intelligent systems. Project results will be integrated into the open source OPTIC planner and ROSPlan robot control framework.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

规划允许智能系统选择旨在实现其目标的行动。 然而，传统的规划方法假设世界发展得足够慢，或者要解决的问题足够简单，在规划过程中世界可以被认为是静态的。 这种限制意味着大多数当前的计划者无法意识到，快速找到一个次优计划来乘坐即将出发的公共汽车可能比仔细考虑最佳计划从而完全错过公共汽车更好。 。目前，规划表示和算法是费力地手动设计的，以确保系统对预期应用足够快地响应，从根本上避免了系统规划时时间流逝的问题。 该项目通过开发新的“情境规划”方法来实现更强大和通用的智能系统，这些方法可以自行推理，足以克服这一限制。该项目将考虑情境规划的两种设置。 第一种是传统的批量设置，其中所有决策都是在计划执行开始之前做出的。 将解决三个挑战：1）随着时间的推移形式化规划模型并分析其计算复杂性，2）充分简化由此产生的“关于推理的推理”问题，以便可以在规划过程中重复近似解决该问题，包括识别易于处理的子类和贪婪启发法，以及 3) 估计在线推理所需的信息。第二种设置是增量计划，其中行动的执行可以与附加计划交织在一起。 将解决三个额外的挑战：4）将情境规划与行动成本正式化，5）开发一个持续的情境规划器，在计划执行时改进计划，以及6）解决在线情境规划，可以在计划执行之前分派行动执行。完整的计划已经找到。 解决这些定位规划问题将产生实用且灵活的规划器，它们可以适当地在批量和增量之间以时间感知的方式平滑地插入其行为，从而扩大智能系统可以解决的应用范围。 项目成果将被整合到开源 OPTIC planner 和 ROSPlan 机器人控制框架中。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

A Formal Metareasoning Model of Concurrent Planning and Execution

并行计划和执行的正式元推理模型

• DOI: 10.1609/aaai.v37i10.26464
• 发表时间: 2023
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Elboher, Amihay;Bensoussan, Ava;Karpas, Erez;Ruml, Wheeler;Shperberg, Shahaf S.;Shimony, Eyal
• 通讯作者: Shimony, Eyal

A Formal Model of Concurrent Planning and Execution with Action Costs

具有行动成本的并行计划和执行的正式模型

• 发表时间: 2022
• 期刊: Proceedings of the ICAPS-22 Workshop on Heuristics and Search for Domain-independent Planning (HSDIP-22
• 作者: Bensoussan, Ava;Shimony, Eyal;Shperberg, Shahaf S.;Ruml, Wheeler
• 通讯作者: Ruml, Wheeler

Trading Monotonicity for Cost in Beam Search

在束搜索中用单调性换取成本

• 发表时间: 2022
• 期刊: Proceedings of the ICAPS-22 Workshop on Heuristics and Search for Domain-independent Planning (HSDIP-22
• 作者: Lemons, Sofia;Linares López, Carlos;Holte, Robert C.;Ruml, Wheeler
• 通讯作者: Ruml, Wheeler

Metareasoning for Interleaved Planning and Execution

• DOI: 10.1609/socs.v12i1.18572
• 发表时间: 2021-07
• 作者: Amihay Elboher;Shahaf S. Shperberg;S. E. Shimony;Wheeler Ruml

General-Purpose Planning Algorithms in the Card Game Duelyst II

卡牌游戏 Duelyst II 中的通用规划算法

• 发表时间: 2023
• 期刊: Proceedings of the IEEE Conference on Games (CoG-23
• 作者: McKenney, Bryan;Ruml, Wheeler
• 通讯作者: Ruml, Wheeler