Introduction to STRIPS Planning and Applications in Video-games

We will start with a quick overview of the interaction between academic AI and video games through game-inspired AI competitions, and then focus on the decision making performed by non-player characters (NPCs) in commercial video games. We will cover some widely used techniques, namely Finite State Machines (FSMs) and Behavior Trees (BTs), as well as Goal-Oriented Action Planning (GOAP) that has recently received attention.
Goal-Oriented Action Planning is based on STRIPS planning, a fundamental academic AI technique that has advanced significally in the last decade. Given a description of an initial state, a goal condition, and a set of actions that transform states according to preconditions and effects, STRIPS planning is concerned with finding a suitable strategy that achieves the goal as a sequence of actions.
After a quick overview of some of the most influential state-based techniques for finding solutions to STRIPS problems using heuristic search, we will turn our attention to how STRIPS planning can be applied in real video games. I will discuss some preliminary results on employing STRIPS planning in two video game scenarios, and give a quick overview on how to get started with two powerful game engines: Unity3D (an emerging standard to indie game development) and Source Engine by Valve (which is used in the Half-life game series).
In the last part of the course I will discuss approaches of planning that go beyond STRIPS, and possibilities for student projects in the area of AI and video games.

Lecture 1, Wednesday May 8, 15:45-17:15, Room A7

Overview of video-game inspired competitions used for AI research. Approaches for the decision making of non-player characters (NPC) in commercial video games: Finite State Machines (FSMs), Behavior trees (BTs), and Goal Oriented Action Planning (GOAP).
Slides: part1 part2.

Lecture 2, Thursday May 9, 15:45-17:15, Room A7

Introduction to STRIPS planning. Finding solutions to STRIPS planning problems using state-space uninformed/informed search.
Slides: part1 part2.

Lecture 3, Friday May 10, 14:00-15:30, Room A3

The Planning Domain Definition Language (PDDL) and use of an award-winning PDDL planner to solve problems in the puzzle game Sokoban. Available programming resources for PDDL parsing and searching for a solution.
Slides: part1
PDDL related material: pddl.

Lecture 4, Wednesday May 16, 15:45-17:15, Room A7

Planning graphs and the GRAPHPLAN procedure for finding solutions to STRIPS planning problems. Domain independent heuristics based on a relaxed STRIPS problem: the h_add, h_max, and h^2 heuristics. Domain independent heuristics based on planning graphs: the FF heuristic.
Slides: part1 part2.

Lecture 5, Thursday May 17, 15:45-17:15, Room A7

Preliminary results on employing STRIPS planning in two video game scenarios: i) SimpleFPS: A PDDL benchmark for tactical planning in first-person shooter (FPS) games ii) SmartWorkers: A case of STRIPS planning in real-time strategy (RTS) games. Introduction to programming with Unity3D and Source Engine (Valve).
Slides: part1 part2.

Lecture 6, Friday May 18, 14:00-15:30, Room A3

Brief overview of planning beyond STRIPS: Incomplete information, nondeterministic actions, sensing, execution monitoring. Introduction to the high-level agent programming language Golog.
Slides: part1 part2.

• Planning as Heuristic Search. Blai Bonet, Hector Geffner. Artificial Intelligence, Vol. 129, 2001.
• The Computational Complexity of Propositional STRIPS Planning. Tom Bylander. Artificial Intelligence, Vol. 69, 1994.
• STRIPS: A new approach to the application of theorem proving to problem solving. Richard E. Fikes, Nils J. Nilsson. Artificial Intelligence, Vol. 2, No. 3-4. 1971.
• Admissible Heuristics for Optimal Planning. P. Haslum, H. Geffner. In Proceedings of the International Conference on AI Planning and Scheduling Systems (AIPS), 2000.
• The Fast Downward Planning System. Malte Helmert. Artificial Intelligence Research (JAIR), Vol. 26, 2006.
• The FF planning system: Fast plan generation through heuristic search. Jorg Hoffmann, Bernhard Nebel. Artificial Intelligence Research, Vol. 14, 2001.
• Unifying SAT-Based and Graph-Based Planning. Henry Kautz, Bart Selman. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1999.
• GOLOG: A Logic Programming Language for Dynamic Domains. Hector J. Levesque, Raymond Reiter, Yves Lesperance, Fangzhen Lin, Richard B. Scherl. Logic Programming, Vol. 31, No. 1-3. 1997.
• Some Philosophical Problems from the Standpoint of Artificial Intelligence. John McCarthy, Patrick J. Hayes. Machine Intelligence, Vol. 4, 1969.
• PDDL - The Planning Domain Definition Language. Drew McDermott, Malik Ghallab, Adele Howe, Craig Knoblock, Ashwin Ram, Manuela Veloso, Daniel Weld, David Wilkins. Technical report, Yale Center for Computational Vision and Control, TR-98-003, 1998.
• Artificial Intelligence for Games, Second Edition. Ian Millington, John Funge. Morgan Kaufmann Publishers Inc., 2009.
• Synthesizing plans that contain actions with context-dependent effects. E. P. D. Pednault. Computational Intelligence, Vol. 4, No. 3. 1988.
• A knowledge-based approach to planning with incomplete information and sensing. Ronald P. A. Petrick, Fahiem Bacchus. In Proceedings of the International Conference on AI Planning and Scheduling Systems (AIPS), 2002.
• Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems. Raymond Reiter. MIT Press, 2001.
• Artificial Intelligence: A Modern Approach 2nd Ed. Stuart Russell, Peter Norvig. Prentice Hall, 2003.
• iThink: A Library for Classical Planning in Video-games. Vassileios-Marios Anastassiou, Panagiotis Diamantopoulos, Vassos Stavros, Manolis Koubarakis. In Proceedings of the 7th Hellenic Conference on Artificial Intelligence (SETN), 2012<./li>
• The SimpleFPS Planning Domain: A PDDL Benchmark for Proactive NPCs. Stavros Vassos, Michail Papakonstantinou. In Proceedings of the Non-Player Character AI workshop (NPCAI-2011), 2011.
• Real-time Action Planing with Preconditions and Effects. Stavros Vassos. Game Coder Magazine, March 2012.
• Action-Based Imperative Programming with YAGI Alexander Ferrein, Gerald Steinbauer, Stavros Vassos In Proceedings of the 8th International Workshop on Cognitive Robotics, 2012.

Stavros Vassos received his B.Sc. degree from the Electrical and Computer Engineering Department of the National Technical University of Athens in Greece in 2002. He received his M.Sc. and Ph.D degree from the Computer Science Department of the University of Toronto in 2005, 2009 under the supervision of Professor Hector J. Levesque. In 2008 he recieved the AAAI Outstanding Paper Honorable Mention Award for his joint paper with Professor H. J. Levesque "On the Progression of Situation Calculus Basic Action Theories: Resolving a 10-year-old Conjecture". His research interests lie mainly in the area of Artificial Intelligence, in particular logic-based approaches for Knowledge Representation and Reasoning, Reasoning about Action and Change, as well as Intelligent Agent Design. Since 2010 he is working as a research associate at the University of Athens in Greece in projects related to the Semantic Web and applications of Artificial Intelligence in commercial games.