Class Project "Any-Angle Path Planning"
This stand-along 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 Theta*, an any-angle algorithm, to plan paths for game characters in known gridworlds. Theta*, similar to A*, propagates information along the edges of the gridworld (to achieve a small runtime) but, different from A*, does not constrain the paths to the edges (to find shorter paths than A*). 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
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.