Research On Key Technologies Of CGF-Oriented Battlefield Spatial Representation And Reasoning

In the study of computer generated forces(CGF), battlefield spatial reasoning is an important research area. Many spatial tasks contains recognition procedures about the executor’s surrounding space, thus it is significant for the CGF units to perform realistic spatial reasoning behavior. In the community of game AI and CGF behavior modeling, existing methods that are widely used can’t satisfy the needs issued by future simulation systems, especially in the aspects of creditability and efficiency. The main reason that causes these drawbacks is that, the methods on hand rarely possess descriptions as well as reasoning mechanisms for high-level, abstract spatial information, consequently, some certain requirements, such as human-machine interaction, layered spatial planning, and large terrain representation & reasoning, will be difficult to get solved only by purely quantitative methods. Aiming to tackle the above mentioned problems, we in this paper take human behavior modeling(HBM) as the application background, trying to construct human-level spatial reasoning models. In order to achieve this goal, key techniques on CGF oriented battle space representation and reasoning(SR&R) are studied.At the beginning we discuss SR&R’s application background as well as its future usage. By studying the state-of-art we also analyze the disadvantages that existing methods commonly have, accordingly our study context and plan are introduced.The first issue in this paper is the research of topological spatial representation and reasoning. For CGF units, tactical path planning is one of the most time-consuming spatial tasks, while existing planning algorithms commonly use grids as their underlying search space. However, grid-based path planning does not contain information about the space topologies, thus they can’t provide a sparse skeleton to enhance the search efficiency. In this paper we introduce GVD(Generalized Voronoi Diagram) as the battlefield’s topological representation model, making use of its sparse structure to facilitate the building of an efficient tactical pathplaning algorithm.To abstract a GVD, we proposed an algorithm named DTD(Dynamic Topology Detector). Different from its counterparts, DTD not only can build or rebuild the GVD from underlying battle space, but also can take a further step to detect spatial relations among GVD elements, and these relations are the knowledge base for multi-layered pathplanning. In order to meet the requirements of multi-precision planning and parallel computing, we further modify DTD via applying pointer-less quadtree as the data structure. After taking approximation, GVDs built upon pointer-less quadtree can provide CGF units with search spaces represented in different precisions.To the application of GVDs, we proposed an off-line pathplanning method which takes GVDs as its abstract spatial descriptions. Different from traditional off-line pathplanning methods, we further introduce some dynamic factors into consideration and build local on-line planning model to evaluate how much these factors would affect the planning procedure. With the integration of on-line and off-line methods, the resulting algorithm gets ahead both in computation efficiency and dynamical adaptability.The second issue we focus on in the paper is the representation and reasoning on binary relations among spatial objects, which is the underlying theory of TPS(Tactical Position Selection), another important behavior which CGF need to simulate. The study of this issue is divided into two aspects: the formulation and the reasoning strategy.Existing formulation methods do not take future spatial change into account. Such an information absence will cause CGF units to re-plan in high frequency, thus the robustness of the results will not meet requirements. To solve this problem we integrate both dynamic and weighted constraint satisfaction techniques to propose a novel formulation procedure for evaluating the spatial change. This procedure can accordingly transform dynamic a TPS into corresponding WCSP.To solve a dynamic TPS, we introduce B&B(Branch and Bound) as the basic strategy to build a deep-first searching algorithm. Since the WCSP belongs is NP difficult, we further discussed how to speed up the search when solving a dynamic TPS. The discussion mainly includes: 1) how to optimize the data structure; 2) how to determine the order of assignments of variables; 3) how to design a pretreatment process to reduce search space.At the end of this paper we conclude our work and give comments about future study trends and topics.