CAREER: Time-Aware Heuristic Search

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

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.