Class Project "Fast Trajectory Replanning" (using Variants of A*)
This stand-alone path-planning project for an undergraduate or graduate artificial intelligence class relates to video game technologies and is part of our effort to use computer games as a motivator in projects without the students having to use game engines. Heuristic search and, in particular, A* are among the important single-agent search techniques and thus good candidates for a project in artificial intelligence. In this project, the students need to code A* and then extend it to Adaptive A*, a fast trajectory replanning algorithm, to move game characters in initially unknown gridworlds to a given target. Adaptive A* is an incremental version of A* that often searches faster than A* since it updates the heuristics between searches to find solutions to series of similar search tasks potentially faster than is possible by solving each search task from scratch. This project requires students to develop a deep understanding of A* and heuristics to answer questions that are not yet covered in textbooks. The project is versatile since it allows for theoretical questions and implementations. We list a variety of possible project choices, including easy and difficult questions.
If you are using this project in your class or have any questions, comments or corrections, please send us an email at skoenig@usc.edu. We will use this webpage to post updates, errata and supporting material. If there is sufficient interest, we will create sample solutions for teachers at accredited colleges and universities.
Project Text
Latex Source of Project Text
Supporting Documents
Supporting Code
Some of this material is based upon work supported by the Fund for Innovative Undergraduate Teaching at the University of Southern California and the National Science Foundation under Grant No. 0350584. Any opinions, findings, and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.