Incremental Heuristic Search

本项目将开发增量启发式搜索方法，通过分析和实验研究它们的特性，并展示它们在不同人工智能应用中的适用性和优势，包括符号规划问题，学习问题和控制问题。 启发式搜索方法在人工智能中有着广泛的应用。他们发现图搜索问题的最短路径比不知情的搜索方法快得多。另一方面，增量搜索方法在人工智能中几乎是未知的。他们为一系列类似的图搜索问题找到最短路径，比从头开始解决每个图搜索问题要快得多。 增量式启发式搜索方法有四个优点：1。增量启发式搜索技术大大加快了重新规划，因为它们结合了联合收割机两种不同的原则来加速搜索。与从头开始重新规划相比，它们可以将重新规划的速度提高一到两个数量级。这一点很重要，因为重新规划问题通常是时间关键的，并且具有很大的状态空间。用增量启发式搜索技术重新规划的计划的质量与从头开始规划的计划的质量一样好。这个属性是许多传统的重新规划方法（例如基于案例的规划、类比规划、规划适应、转换规划、解决方案重放规划和基于修复的规划）的重要区别，这些方法通常不能保证最终的规划质量。 增量式启发式搜索技术是非常通用的，适用于，例如，符号规划问题，路径规划问题，协同学习问题，和控制问题. 启发式增量搜索技术有坚实的理论基础，因此很好地理解的属性。它们的简单性允许人们证明它们的许多属性，包括它们的终止性，正确性，效率和与A* 的相似性，这使得它们易于理解，易于分析，易于编程，易于优化效率，易于扩展。增量启发式搜索方法有可能改善各种人工智能应用，例如，在海洋石油泄漏等危机情况下，可能会导致决策支持系统的响应时间更短，但计划质量更高。研究结果将通过在会议上、在网页上和通过教程向广大受众展示。该项目将改善研究生、本科生、高中生和少数民族学生的教育（主要是通过志愿参加教育活动）。 例如，感兴趣的本科生将非常积极地参与研究。

This project will develop incremental heuristic search methods, study their properties analytically and experimentally, and demonstrate their applicability and advantages for different artificial intelligence applications, including symbolic planning problems, reinforcement-learning problems, and control problems. Heuristic search methods are widely used in artificial intelligence. They find shortest paths for graph search problems much faster than uninformed search methods. Incremental search methods, on the other hand, are almost unknown in artificial intelligence. They find shortest paths for series of similar graph search problems much faster than is possible by solving each graph search problem from scratch. Incremental heuristic search methods have four advantageous properties:1. Incremental heuristic search techniques speed up replanning substantially since they combine two different principles for speeding up the search. They can speed up replanning by one to two orders of magnitude compared to replanning from scratch. This is important because replanning problems are often time critical and have large state spaces.2. The quality of the plans that result from replanning with incremental heuristic search techniques is as good as the quality of the plans that result from planning from scratch. This property is an important difference to many conventional replanning methods (such as case-based planning, planning by analogy, plan adaptation, transformational planning, planning by solution replay, and repair-based planning) that usually cannot make guarantees about the resulting plan quality.3. Incremental heuristic search techniques are very versatile and apply, for example, to symbolic planning problems, path-planning problems, reinforcement-learning problems, and control problems.4. Heuristic incremental search techniques have a solid theoretical foundation and thus well-understood properties. Their simplicity allows one to prove a number of properties about them, including their termination, correctness, efficiency, and similarity to A*, which makes them easy to understand, easy to analyze, easy to program, easy to optimize for efficiency, and easy to extend. Incremental heuristic search methods have the potential to improve a variety of artificial intelligence applications, that might, for example, result in decision-support systems with smaller response times but higher quality plans than is possible today, in crisis situations such as marine oil spills. The research results will be made available to a broad audience by presenting them at conferences, on web pages, and via tutorials. The project will improve the education of graduate students, undergraduate students, high-school students, and minority students (mostly by volunteering for educational activities). For example, interested undergraduate students will be very actively involved in the research.