Sven Koenig, William Yeoh
Department of Computer Science
University of Southern California
This standalone path-planning project for an undergraduate or graduate artificial intelligence class is part of our effort to motivate students via computer games. This project allows students to implement computer game technologies without having to use complex game engines. Heuristic search and, in particular, A* are among the most widely used search techniques and thus are good candidates for artificial intelligence projects. In this project, the students need to code A* and then extend it to Adaptive A*. Adaptive A* is a fast path replanning algorithm which moves game characters in initially unknown gridworlds to a given target. Adaptive A* is an incremental version of A* that often searches faster than A*. Adaptive A* updates heuristics between searches and, by doing so, finds solutions to series of similar search problems potentially faster than repeated searches from scratch. This project requires that students develop a thorough understanding of A* and heuristics in order to answer questions that are not yet covered in textbooks. The project is versatile since it allows for both theoretical and implementation questions. We list a variety of possible project choices, including easy and hard questions. The project text and additional support material (such as a maze generator and pointers to the literature) can be found at http://idm-lab.org/gameai.
|Topics||Search; Heuristic Search; Incremental Heuristic Search; Computer Games; Path Planning|
|Audience||The intended audience of this assignment is students in an undergraduate or graduate artificial intelligence class. It is well-suited for two different kinds of audience: those who want to understand A* and those who want to learn about recently proposed extensions of A*.|
This project is versatile since it allows for both theoretical and implementation questions. The difficulty level of the implementation questions is comparable to implementing A*. The difficulty level of the theoretical questions varies from easy to hard. We recommend that instructors give the students at least two weeks to complete the assignment.
|Variants||Instructors can vary the assignment as follows: