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

This technical report contains a challenging trajectory-planning project for an undergraduate or graduate “Introduction to Artificial Intelligence” class that relates to real-time computer games. The students need to code A* and then develop a deep understanding of A* and heuristics to answer questions that are not yet covered in textbooks and require computational thinking when they extend A* to Adaptive A*, a fast trajectory replanning algorithm. Introduction The Department of Computer Science at the University of Southern California created a Bachelor’s Program in Computer Science (Games) and a Master’s Program in Computer Science (Game Development), which not only provide students with all the necessary computer science knowledge and skills for working anywhere in industry or pursuing advanced degrees but also enable them to be immediately productive in the game-development industry. They consist of regular computer science classes, game-engineering classes, game-design classes, game cross-disciplinary classes and a final game project. See Zyda and Koenig, Teaching Artificial Intelligence Playfully, Proceedings of the AAAI-08 Education Colloquium, 2008 for more information. The undergraduate and graduate versions of the “Introduction to Artificial Intelligence” class at the University of Southern California are regular computer science classes that are part of this curriculum. We are now slowly converting these classes to use games as a motivating topic in lectures and as the domain for projects because games motivate students, which we believe increases enrollment and retention and helps us to educate better computer scientists. Artificial intelligence becomes more and more important for computer games, now that games use graphics libraries that produce stunning graphics and thus no longer gain much of a competitive advantage via their graphics capabilities. Many games need trajectory-planning capabilities and thus use search algorithms. Some games already use machine learning or planning algorithms. For example, “Black and White” uses a combination of inductive learning of decision trees and reinforcement learning with neural networks, and “F.E.A.R” uses goal-oriented action planning. Thus, games can be used to illustrate many areas of artificial intelligence. 1 It was tempting for us to use a publicly available game engine throughout the class and then ask the students to perform several projects in it, such as a search project to plan the trajectories of the game characters and a machine-learning project to make them adapt to the behavior of their opponents. However, students familiar with game development already have plenty of exposure to game engines while students not interested in game development do not need the additional overhead. To put all students on the same footing and allow them to concentrate on the material taught in class, we decided to go with several small projects that do not need large code bases. This technical report describes one particular project from the undergraduate and graduate versions of the “Introduction to Artificial Intelligence” class. Heuristic search and, in particular, A* are among the important single-agent search techniques and thus good candidates for a project in artificial intelligence. We therefore developed a project where the students use a generalization of A*, Adaptive A*, to move game characters in initially unknown gridworlds to a given target. The students need to code A* and then develop a deep understanding of A* and heuristics to answer questions that are not yet covered in textbooks and require computational thinking when they extend A* to Adaptive A*. Some of the questions, such as Question 3, discuss phenomena that were initially surprising even to researchers in the area of heuristic search. Overall, the search project is versatile since it allows for theoretical questions and for implementations. We list a variety of possible project choices, including easy and difficult questions. Teachers need to select among them since we list too many of them for a project of a reasonable size and some of them are difficult research questions. (Questions tagged with asterisks are the ones that we tend to use in our own projects.) Teachers also need to provide information on which programming language(s) the students are allowed to use, how they can determine the runtime of their programs, what they need to submit for their projects (for example, whether they need to submit their programs or traces of their programs on example search problems), how they should submit their projects (for example, on paper or electronically) and by when they need to submit their projects. If you are using this assignment in your class or have any questions, comments or corrections, please send us an email at [email protected]. If you need to cite this assignment (in your own publications or to give us credit), please cite this technical report as Sven Koenig and William Yeoh, A Project on Fast Trajectory Replanning for Computer Games for “Introduction to Artificial Intelligence” Classes, Technical Report, Department of Computer Science, University of Southern California, Los Angeles (California, USA). Updates, errata and supporting material for the project (including the latex version of this document to allow teaches to customize this assignment) can be found on our webpages idm-lab.org/gameai, where we will also release additional projects in the future. If there is sufficient interest, we will create sample solutions for teachers at accredited colleges and universities. Acknowledgments This initiative was partly supported by a grant from the Fund for Innovative Undergraduate Teaching at the University of Southern California. We thank Maxim Likhachev and Xiaoxun Sun for earlier joint research that strongly influenced the creation of this project. We thank Kenny Daniel, David Furcy, Maxim Likhachev, Alex Nash, Nathan Sturtevant and Xiaoxun Sun for helpful comments that improved our project text greatly. We have updated the project text recently, which might have introduced mistakes. We are the only ones to blame for them.