CAREER: Time-Aware Heuristic Search

职业：时间感知启发式搜索

• 批准号: 1150068
• 负责人: Wheeler Ruml
• 金额: $ 49.84万
• 依托单位: University of New Hampshire
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-06-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1150068&HistoricalAwards=false
• 关键词: CAREER; Time; Aware; Heuristic; Search

Planning is a useful capability -- for instance, it enables robots to be autonomous and it helps people save money and conserve natural resources. Traditional planning methods search for perfect plans; this often requires exponential time and therefore takes too long for many problems. It is often better to promptly take a reasonable but possibly suboptimal action than it is to deliberate long enough to guarantee an 'optimal' plan. This project develops new methods for time-aware search and planning, along with an on-line handbook to help those who use search techniques choose an appropriate method.This project focuses on developing algorithms for time-aware search in four different settings. (1) In utility-based search, the algorithm optimizes a user-specified combination of planning time and plan execution time. This captures the situation in which one wishes to achieve a goal as soon as possible (e.g., minimize the sum of planning time and plan execution time). (2) In incremental search, actions can be selected and begin to be executed while planning continues. This allows the algorithm to benefit from early execution if a good first action is apparent, but deliberate carefully if the selection of the first action appears crucial. (3) In on-line continual search, new goals can arrive asynchronously during execution. This requires the algorithm to determine if it is worthwhile to re-plan from scratch or whether simple additions to the existing plan will suffice. (4) In search under a deadline, a complete plan must be found within a given bound on search time. This is the objective in many applications.This project also involves the creation and curation of an online Handbook of Search Algorithms. It will provide a comprehensive taxonomy of planning and optimization problem settings, together with the most appropriate algorithms that have been proposed for each setting. The handbook will integrate on-going research and educational activities of the PI. It will accelerate the uptake of academic research on heuristic search and draw attention to compelling settings that have traditionally received less attention, such as time-aware planning. The creation and curation of the handbook will be a long-term collaboration between the PI, students in a yearly seminar course taught by the PI, and students in the PI's research group. For graduate and advanced undergraduate students, authoring the handbook immerses them in research, while promoting fundamental skills in literature review, scientific writing, and empirical methodology.

规划是一项有用的功能——例如，它使机器人能够自主，并帮助人们省钱和保护自然资源。传统的规划方法寻求完美的计划；这通常需要指数时间，因此对于许多问题来说花费的时间太长。及时采取合理但可能不是最理想的行动通常比考虑足够长的时间以保证“最佳”计划要好。该项目开发了时间感知搜索和规划的新方法，以及在线手册来帮助那些使用搜索技术的人选择合适的方法。该项目重点开发四种不同设置下的时间感知搜索算法。 (1) 在基于效用的搜索中，算法优化用户指定的计划时间和计划执行时间的组合。这捕获了人们希望尽快实现目标的情况（例如，最小化计划时间和计划执行时间的总和）。 (2) 在增量搜索中，可以在计划继续的同时选择动作并开始执行。如果第一个动作很明显，那么算法可以从早期执行中受益，但如果第一个动作的选择显得至关重要，则需要仔细考虑。 (3)在线连续搜索中，执行过程中新的目标可以异步到达。这需要算法来确定是否值得从头开始重新计划，或者对现有计划进行简单的添加是否就足够了。 (4)限期检索，必须在规定的检索时间内找到完整的方案。这是许多应用程序的目标。该项目还涉及在线搜索算法手册的创建和管理。它将提供规划和优化问题设置的全面分类，以及为每个设置提出的最合适的算法。该手册将整合 PI 正在进行的研究和教育活动。它将加速启发式搜索学术研究的发展，并引起人们对传统上较少关注的引人注目的环境的关注，例如时间感知规划。该手册的创作和管理将是 PI、参加由 PI 教授的年度研讨会课程的学生以及 PI 研究小组的学生之间的长期合作。对于研究生和高年级本科生来说，编写这本手册可以让他们沉浸在研究中，同时提高文献综述、科学写作和实证方法论的基本技能。