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.