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）解决在线定位计划，在找到完整计划之前可以派遣行动进行执行。 解决这些定位的计划问题将导致实用而灵活的计划者，可以在适当的情况下以批处理和增量之间的时间认识地平稳地插入其行为，从而扩大了智能系统可以解决的应用程序范围。 项目结果将被整合到开源视频计划师和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

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

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

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