The Study On HTN-based Real-time Planning System And Related Algorithms

In recent years, interactive entertainment industry has got a rapiddevelopment especially the video game, and requirement for building thevirtual agent is ever increasing. More projects and studies have also startedto show great concern on it and explore how to achieve a more intelligentagent in video games. In this paper, a new artificial intelligence frameworkand algorithm in the FPS game will be introduced based on the results ofprevious studies. There are two important points in the research work, one isto optimize a real-time planner based on existing planning algorithms, andthe other is to build an artificial intelligence framework based on HTN andthe real-time planning algorithms for the FPS games.In the beginning of this paper, we will give a short description for somedesign methods in artificial intelligence, and discuss how to build areal-time planning system based on HTN, also in the discussion there aresome introduction for the significant subsystems which to support theframework. Finally, all the parts above will constitute a complete artificialintelligence system. In the end, we also verify the system that meets therequirements we proposed through the actual test.The main research works and achievements in this paper include:(1) We have improved the search algorithm in HTN planner, inorder to meet the high dynamic, high real-time characteristics in FPS games.An estimated weight function has been added to the algorithm, making thesearch algorithm give a priority to select the easy tasks which can bedecomposed in run-time. Therefore, there can be a more detailed planninghead with priority even facing an interrupt request.(2) In this paper, we design and implement a framework forreal-time decision make system in FPS game. The framework is based on HTN planner. The agents obtain current state of the world throughperception system. The input of the planner controlled by targetmanagement module and interrupt management module，then it would becomputed by the planning algorithm and finally the output will contain aseries of action sequence which can be performed in game.(3) The parts that may affect the efficiency and drain on CPUresources seriously have been optimized. Such as, using the belief functionto optimize the target selection procession, and using the time-slicetechnology to optimize A*path-finding algorithm.(4) Based on the works above, we design and achieve an artificialintelligence framework in FPS game. This game is established on the UnrealTournament2004, and the interaction between the agent and the virtualenvironment is accomplished through the middleware Pogamut2.(5) Validating the effectiveness of the planning system and thereal-time algorithm through various experiments and application tests.