Reactiveness and Navigation in Computer Games: Different Needs, Different Approaches
Inhaltsverzeichnis
Reference
Perez, D., Nicolau, M., Michael O'Neill and Anthony Brabazon (2011) Reactiveness and Navigation in Computer Games: Different Needs, Different Approaches. 2011 IEEE Conference on Computational Intelligence and Games , 31-AUG-11 - 02-SEP-11 , pp.273-280
DOI
http://dx.doi.org/10.1109/CIG.2011.6032017
Abstract
This paper presents an approach to the Mario AI Benchmark problem, using the A* algorithm for navigation, and an evolutionary process combining routines for the reactiveness of the resulting bot. The Grammatical Evolution system was used to evolve Behaviour Trees, combining both types of routines, while the highly dynamic nature of the environment required specific approaches to deal with over-fitting issues. The results obtained highlight the need for specific algorithms for the different aspects of controlling a bot in a game environment, while Behaviour Trees provided the perfect representation to combine all those algorithms.
Extended Abstract
Bibtex
Used References
Binary Decision Diagrams. IEEE Transactions on Computers, C-27(6), pp. 509-516. (1987)
P. Angeline: Subtree Crossover: Building Block Engine or Macromutation?. In: Genetic Programming 1997, Proceedings. Morgan Kaufmann (1997) pp. 9-17
S. Bandi, D. Thalmann: Space discretization for efficient human navigation. In: Computer Graphics Forum, Vol. 17, Issue 3, September 1998 pp. 195-206 http://dx.doi.org/10.1111/1467-8659.00267
K. Birdwell: The CABAL: Valve's Design Processing for Creating Half Life. In: Game Developer 6 (12) (1999) pp. 40-50
Bojarski, S.; Congdon, C.B.; REALM: A rule-based evolutionary computation agent that learns to play Mario. In: 2010 IEEE Symposium on Computational Intelligence and Games (CIG) (2010). pp. 83-90 http://dx.doi.org/10.1109/ITW.2010.5593367
Cavazza, M.; Bandi, S.; and Palmer, I.: Situated AI in Video Games: Integrating NLP, Path Planning, and 3D Animation. In: Papers from the AAAI 1999 Spring Symposium on Artificial Intelligence and Computer Games (1999) Technical Report SS-99-02. pp. 6-12
A. Champandard, M. Dawe and D. H. Cerpa: Behavior Trees: Three Ways of Cultivating Strong AI. In: Game Developers Conference, Audio Lecture. (2010)
A. Champandard: Behavior Trees for Next-Gen Game AI. In: Game Developers Conference, Audio Lecture. (2007)
R. Colvin and I. J. Hayes: A Semantics for Behavior Trees. ARC Centre for Complex Systems, tech. report ACCS-TR-07-01. (2007) http://dx.doi.org/10.1016/j.scico.2010.11.007
D. E. Goldberg: Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley (1989)
D. Isla: Managing Complexity in the Halo 2 AI System. In: Game Developers Conference, Proceedings. (2005)
J. Togelius, S. Karakovskiy and R. Baumgarten: The 2009 Mario AI Competition. In: IEEE Congress on Evolutionary Computation, Proceedings. IEEE Press (2010) pp. 1-8 http://dx.doi.org/10.1109/CEC.2010.5586133
J. R. Koza: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press (1992)
C. Lim, R. Baumgarten and S. Colton: Evolving Behaviour Trees for the Commercial Game DEFCON. In: Applications of Evolutionary Computation, EvoApplications 2010, Proceedings. (2010)
R. I. McKay, X. H. Nguyen, P. A. Whigham, Y. Shan and M. O'Neill: Grammar-Based Genetic Programming - A Survey. Genetic Programming and Evolvable Machines, 11(3-4). (2010) pp. 365-396 http://dx.doi.org/10.1007/s10710-010-9109-y
J. Meyer, D. Filliat: Map-based navigation in mobile robots: II. A review of map-learning and path-planning strategies. Cognitive Systems Research, 4(4). (2003) pp. 283-317 (Pubitemid 38647184) http://dx.doi.org/10.1016/S1389-0417(03)00007-X
L. McHugh: Three Approaches to Behavior Tree AI. In: Game Developers Conference, Proceedings. (2007)
A. M. Mora, R. Montoya, J. J. Merelo, P. G. Sánchez, P. A. Castillo, J. L. J. Laredo, A. I. Martínez and A. Espacia: Evolving Bot AI in Unreal. In: Applications of Evolutionary Computation, EvoApplications 2010, Proceedings. Springer Verlag. (2010) pp. 171-180 http://dx.doi.org/10.1007/978-3-642-12239-2_18
M. Mateas and A. Stern: Managing Intermixing Behavior Hierarchies. In: Game Developers Conference, Proceedings. (2004)
M. Nicolau and I. Dempsey: Introducing Grammar Based Extensions for Grammatical Evolution. In: IEEE Congress on Evolutionary Computation, Proceedings. IEEE Press (2006) pp. 2663-2670 http://dx.doi.org/10.1109/CEC.2006.1688372
N. J. Nilsson: Artificial Intelligence, A New Synthesis. Morgan Kaufmann Publishers. (1998)
S. Nason and J. Laird: Soar-RL: Integrating Reinforcement Learning with Soar. In: International Conference on Cognitive Modelling, Proceedings. (2004) http://dx.doi.org/10.1016/j.cogsys.2004.09.006
M. O'Neill and C. Ryan: Grammatical Evolution: Evolutionary Automatic Programming in a Arbitrary Language. Kluwer Academic Publishers (2003)
D. Perez and M. Nicolau and M. O'Neill and A. Brabazon. Evolving Behavior Trees for the Mario AI Competition Using Grammatical Evolution. In Applications of Evolutionary Computation, EvoApplications 2011, Proceedings. Springer Verlag. (2011) pp. 121-130
L. Prechelt. Early Stopping - But When?. In Neural Networks: Tricks of the Trade, Proceedings. Springer Verlag. (1997) pp. 55-69
S. Priesterjahn: Imitation-Based Evolution of Artificial Game Players. ACM SIGEVOlution, 2(4). (2009) pp. 2-13 http://dx.doi.org/10.1145/1399962.1399963
C. Ryan and R. M. A. Azad: Sensible initialisation in grammatical evolution. In: Barry, A.M. (ed.) GECCO 2003: Proceedings of the Bird of a Feather Workshops. AAAI (2003) pp. 142-145.
K. Sastry, U. O'Reilly, D. E. Goldberg and D. Hill: Building Block Supply in Genetic Programming. Genetic Programming Theory and Practice, Chapter 4. Kluwer Publishers (2003) pp. 137-154 http://dx.doi.org/10.1007/978-1-4419-8983-3_9
C. Thurau, C. Bauckhauge and G. Sagerer: Combining Self Organizing Maps and Multiplayer Perceptrons to Learn Bot-Behavior for a Comercial Game. In: GAME-ON'03 Conference, Proceedings. (2003)
J. Togelius, S. Karakovskiy and R. Baumgarten: The 2009 Mario AI Competition. In: IEEE Congress on Evolutionary Computation, Proceedings. IEEE Press (2010) http://dx.doi.org/10.1109/CEC.2010.5586133
J. Togelius, S. Karakovskiy, J. Koutnik and J. Schmidhuber: Super Mario Evolution. In: IEEE Symposium on Computational Intelligence and Games, Proceedings. IEEE Press (2009) http://dx.doi.org/10.1109/CIG.2009.5286481
S. Winkler, M. Affenzeller, and S. Wagner: Selection Pressure Driven Sliding Window Behavior in Genetic Programming Based Structure Identification. In: EUROCAST'07 Conference, Proceedings. Springer- Verlag (2007) pp. 788-795 http://dx.doi.org/10.1007/978-3-540-75867-9_99
Links
Full Text
http://cilab.sejong.ac.kr/cig2011/proceedings/CIG2011/papers/paper62.pdf
