Modeling CGF Tactical Decision Making Through Monte Carlo Tree Search

Behavior modeling of Computer Generated Forces(CGF)has long been a challenging issue in combat simulation construction.It usually requires many subject matter experts to be involved,in order to form enough domain knowledge to generate complex behavior.However,these models mainly produce reactive behaviors,which fail to show human-like intelligence in some high-level cognitive activities(e.g.situation awareness,mission planning,and decision making).The focus of this thesis is to explore the use of Monte Carlo Tree Search(MCTS)for CGF tactical decision making,aiming to enable CGFs to behave more intelligently in virtual battlefields.Specifically,it is employed to perform online planning and generate intelligent decisions,guiding corresponding troops' activities to accomplish certain missions.MCTS uses random sampling to tackle problems with huge state spaces.Also,its reasoning process considers how to respond according to opponents' strategies and makes evaluations on potential Courses of Actions.This is suitable to analyze combat environments which is usually quite complex and dynamic.This thesis presents an agent based CGF decision making architecture,where how MCTS supports the intelligent behavior generation during simulation running is described.Based on such settings,several key problems are investigated,resulting contributions as following:(1)An Hierarchical Task Network(HTN)planning guided MCTS algorithm is proposed.It takes advantage of HTN planning results to configure the MCTS process,and simultaneously alternative strategies encoded in HTN can be explored through look-ahead reasoning,thus finding the most promising one for current situations.This combination makes MCTS possible to produce high-quality decisions in real-time for complex problems.(2)A belief state based MCTS is proposed to tackle its use in problems with imperfect information.Compared with the vanilla MCTS,The presented algorithm extends the tree model by incorporating the observation history,and employs an unweighted particle filter to represent belief state as well as its update.The decision process is performed with determinized searches sampled from the belief state in order to deal with uncertainties.(3)A Chebyshev metric based MCTS is proposed for its use in problems with multiple objectives to be optimized.The presented algorithm employs a non-linear scalarization approach to guide the tree policy and the final decision selection of the MCTS.It is shown to be capable of seeking Pareto optimal solutions with defined objective preferences,regardless the shape of the targeted problem's Pareto front.(4)An Option based automatic problem abstraction is proposed,which can learn knowledge for planning applications.The presented approach constructs options though a community detection algorithm.It also employs a rule based community revision algorithm to online improve the quality of the option set.The effectiveness of the approach is evaluated through several benchmark experiments,which lays a good foundation for its use for more complex problems.The final part gives a summarization on the whole works of this thesis,and also a discussion on future research directions.