A Project on Fast Trajectory Replanning for Computer Games
for "Introduction to Artificial Intelligence" Classes

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.

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.

• Instructors can easily incorporate this assignment in their course syllabus since it extends a commonly taught algorithm, namely A*.
• Instructors can tailor the difficulty of this assignment by choosing questions from a pool of questions with varying levels of difficulty.
• This assignment is inspired by computer games, which we believe motivate and interest students.
• This assignment exposes students to recent research results, namely Adaptive A*.
• Students cannot search for answers to the questions in this assignment on the web since the questions are not in standard textbooks.

• Some of the implementation questions of the assignment are esssential to the project, and thus instructors unfortunately cannot tailor their difficulty.
• No sample solutions are available.

• This assignment requires that the students understand A*. The assignment briefly re-introduces A* in two pages and contains many examples to help students understand this assignment.
• This assignment requires that the students be familiar with a programming language since they need to code A* and extend it. However, it is language and platform independent.

• Choose different theoretical questions from a pool of questions with varying levels of difficulty.
• Create and use different randomly generated input files. We provide an input file generator.
• Extend the assignment by choosing one of the three extra credit questions.

• The complete assignment document is archived here. The most recent version of this document can be found at http://idm-lab.org/bib/abstracts/papers/project1.pdf.
• A random input file generator can be found here. The most recent version of this generator can be found at http://idm-lab.org/code/mazegenerator.tar.
• More material and information on this assignment can be found at http://idm-lab.org/project-m/project1.html.
• Other assignments that are inspired by computer games can be found at http://idm-lab.org/gameai/.