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.
