Practical Development of Goal-Oriented Action Planning ai



старонка1/5
Дата24.04.2016
Памер98.25 Kb.
#23614
  1   2   3   4   5
    Рух па дадзенай старонцы:
  • CHAPTER 1

To the Graduate Faculty:

I am submitting herewith a project written by David Lindsey Pittman entitled “Practical Development of Goal-Oriented Action Planning AI.” I recommend that it be accepted in partial fulfillment of the requirements for the degree of Master of Interactive Technology in Digital Game Development, with Specialization in Software Development.

___________________________________

Jeff Wofford, Faculty Supervisor

We have read this Project

and recommend its acceptance:

____________________________________


____________________________________
____________________________________

Accepted for the Faculty:


___________________________________

Executive Director, The Guildhall at SMU

PRACTICAL DEVELOPMENT OF

GOAL-ORIENTED ACTION PLANNING AI

A Project Presented to the Graduate Faculty of

The Guildhall at Southern Methodist University

in

Partial Fulfillment of the Requirements



for the degree of

Master of Interactive Technology

in Digital Game Development

with


Specialization in Software Development

by

David L. Pittman



(BS, University of Nebraska-Lincoln, 2005)

March 21, 2007


Pittman, David L. BS, University of Nebraska-Lincoln, 2005
Practical Development of Goal-Oriented Action Planning AI
Supervisor: Professor Jeff Wofford

Master of Interactive Technology degree conferred March 23, 2007

Project completed March 21, 2007
As real-time graphics continue to approach realism and gameplay systems become increasingly complex, game AI must progress in parallel to maintain the illusion of believable characters. The decision-making architecture known as Goal-Oriented Action Planning (GOAP) offers dynamic problem solving, which is a key ingredient in crafting AIs which appear to understand their environment and react in a logical manner. This project analyzes the development of a GOAP-based AI and its application to various game genres, with consideration to the practicality of the technology. In this context, practical is defined as being able to be implemented in an interpreted scripting language at production quality in a reasonable amount of time, performing efficiently, and producing equal or better results compared to traditional AI techniques. In the context of certain game genres such as tactical shooters and strategy games, coordinated character behavior is as important as individual behavior to the success of an AI system. Prior implementations of GOAP have used informal solutions to the problem of coordinated decision-making. This project proposes a scheme for implementing command and control hierarchies which use GOAP at every level to propagate orders from a commanding unit to atomic AI agents.

ACKNOWLEDGEMENTS

In the completion of this project, I owe a debt of gratitude to the faculty at The Guildhall at SMU, including Gary Brubaker, Jeff Wofford, and Wouter van Oortmerrsen. The success of the project owes a great deal to their knowledge and guidance. My thanks also go to Jeff Orkin, who freely gave his time and wisdom to assist this project.

For their support and camaraderie, I would like to thank my literal and figurative brothers, the programmers of Cohort 5. My greatest thanks go to Kyle for always pushing me to greater heights, Kim for her love and understanding, and to my parents for their unending love and support (both emotionally and monetarily).

TABLE OF CONTENTS

ACKNOWLEDGEMENTS iii

LIST OF FIGURES vi

Chapter


1. INTRODUCTION 1

1.1. Goal-Oriented Action Planning 1

1.2. Command and Control Hierarchies 2

1.3. Motivation 4

1.4. Objectives 5

1.5. Original Proposal 5

2. FIELD REVIEW 10

2.1. Traditional Decision-Making 10

2.2. Planning 10

3. Methodology …..………. 12

3.1. Original Proposal 7 12

3.2. Overview 13

3.3. Selecting a Goal 13

3.4. Graph Search and the Planner 7 14

3.5. Debugger 7 15

3.6. Optimizations 16

3.7. Measuring Performance 7 17

3.8. Making the Planner Generic 17

3.9. Command Hierarchy 7 18

3.10. World State Representation 7 19

3.11. Designer Interface 7 19

3.12. External Evaluation 7 20

4. RESULTS AND ANALYSIS …..………. 21

4.1. Introduction 7 21

4.2. Development Costs 21

4.3. Performance 7 21

4.4. External Evaluation 23

4.5. Applicability to Genres 23

5. DISCUSSION AND CONCLUSIONS …..………. 27

5.1. Conclusion 7 27

5.2. Further Research 27

REFERENCES 28

APPENDIX: RESEARCH STUDY CODE 30

LIST OF FIGURES

Figure Page

1.1. Relationship between primary GOAP classes 2

1.2. An example of a plan formulated by GOAP 2

1.3. A command and control hierarchy implemented with GOAP 4

3.1. A theoretically infinite state-space graph 14

3.2. The relationship between the debugger classes 16

3.3. Using the Mediator design pattern 18

3.4. The UnrealEd interface for editing GOAP AI properties 20

4.1. Profiler statistics for the first demo scene 22

4.2. Squad shooter demo 24

4.3. Room clearing demo 25

4.4. RPG demo 26



CHAPTER 1


INTRODUCTION

1.1Goal-Oriented Action Planning


As game graphics become increasingly realistic and believable, character artificial intelligence must continue to progress in parallel. Using static AI techniques in a modern game with lifelike models can create a jarring effect for the user (similar to the "uncanny valley" phenomenon described in the field of robotics [Mori70]). The player's suspension of disbelief is broken when a character behaves in a highly unnatural manner. Good game AI is not just about producing systems which can solve problems, it is about the compelling simulation of a living being. The AI should behave realistically and react dynamically to the player and to situations which may or may not have been specifically anticipated by a designer. Because game AI is a feature in which programmers, designers, and artists are all invested, it is desirable to develop an AI system that allows all disciplines to configure character behaviors in an intuitive and friendly way.

The purpose of this project is to evaluate the usefulness of the game AI technique known as Goal-Oriented Action Planning (GOAP) in terms of its cost to implement and runtime performance on an interpreted scripting language and its value for various game genres. Furthermore, the project proposes the use of GOAP for military-style "command and control" hierarchies, as might be found in a squad-based shooter or real-time strategy game. GOAP is a relatively new addition to the game AI vocabulary, having been introduced by the AIISC in 2003 [AIISC]. Fundamentally, the technique involves formulating a list of actions whose outcome will satisfy a goal.

GOAP is a technique for AI decision-making that produces a sequence of actions (called a plan) to achieve a desired goal state. The primary objects in GOAP are Goals and Actions. A Goal is described by relevant world state properties. An Action is described in terms of its effects on the world state and its world state preconditions. A plan of action (literally, an ordered array of Actions) is formulated by a component called a planner.

Figure 1.1 Relationship between primary GOAP classes


The input to the planner includes a current world state, a previously selected Goal, and a set of Actions. The Goal's properties are modulated with the current world state to produce the goal world state. The plan is then formulated by searching the state space graph for a minimal ordered set of Actions which produce the goal state from the current state. For our purposes, we can generally ignore world state side effects caused by Actions. This means that we actually only need to consider those properties of the world state which the Goal or an Action precondition specifies; all the other elements of the world state are ignored in the search.

Figure 1.2 An example of a plan formulated by GOAP






Поделитесь с Вашими друзьями:
  1   2   3   4   5




База данных защищена авторским правом ©shkola.of.by 2022
звярнуцца да адміністрацыі

    Галоўная старонка