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研究小组的学生。对于研究生和高级本科生，撰写手册将其浸入研究中，同时促进文学综述，科学写作和经验方法论的基本技能。