For operations on the battlefield, in addition to terrain information related to the operation area, dynamic information that changes in real time, such as the size and type of enemy troops, their position and time, and deployed equipment, is collected. Covert Reconnaissance, Powerful Reconnaissance, or both to collect and update on a continual basis is essential. In contrast to covert reconnaissance, which concentrates on collecting information so that the enemy does not detect it, power reconnaissance refers to the action of grasping the target's position and equipment by engaging with the enemy.
Long-term decision making in such a dynamic environment is one of the major challenges in game AI development. At the "Game Developers Conference 2021" (GDC 2021) held online from July 19th to July 24th, Mr. Kosuke Namiki and Mr. Toryoshi Mori, AI engineers of Square Enix I covered the session "A new approach to planning in a dynamic environment using
In this session, using an action game in which a giant armed robot runs around the battlefield, a new planning method for AI players to search, engage, and withdraw from power reconnaissance will be explored. Suggested. While eliminating targets that can be destroyed during reconnaissance, if the situation becomes dangerous due to the appearance of a strong enemy, a smoke screen will be set up and withdrawal will start. At that time, use a powerful weapon that serves as a trump card to destroy a formidable enemy, or force the enemy to give up pursuit. In addition, when attacking, focus on ridgeline shooting to minimize the number of bullets from the enemy. The ultimate goal is to have AI execute all of these decisions.
In recent years, game AI development has focused on finite state machines (FSMs), behavior trees, and GOAP (Goal Oriented Action Planning). , are underpinned by different kinds of decision-making models such as Hierarchical Task Networks (HTNs). Each has its advantages and disadvantages, and depending on the purpose, you can use them properly or combine multiple models to build the optimal game AI for game design.
The HTN we will be discussing in this session is self-explanatory. A task-based algorithm that creates an action plan by building a hierarchical network of multiple tasks. It is suitable for implementing long-term action plans, especially for planning in static environments such as delivery optimization problems.
All tasks are divided into two types: primitive tasks, which are the smallest unit of action, and compound tasks, which combine them. At this time, the former is hierarchically lower and the latter is higher. For example, if ``walking'' and ``shooting'' are primitive tasks, the long-term action goal ``power reconnaissance'' is considered to be a hierarchically highest compound task that combines many primitive tasks. increase.
The role of HTN is to decompose these compound tasks into multiple tasks and plan so that they can be executed in order from the lower layer tasks. Tasks that are broken down to the smallest unit during planning are arranged like a chain and then executed one by one. This task chain cannot be changed until all tasks have been executed. Therefore, if the environment changes along the way, HTN will try to create a new plan by discarding all existing plans.
In video games, where the environment is constantly changing according to the player's behavior, the more frequent replanning, the more AI loses its ability to think long-term. As a result, we end up with a responsive AI that can only make short-term decisions. Therefore, in order to realize long-term actions in a dynamic environment like video games, Square Enix has proposed a new planning method called 'ART-HTN', which is an improved version of HTN.
"ART-HTN" (Advanced Realtime Hierarchical Task Network) includes "multi-scenario plan", "simulation planner" and "plan executor". There are three characteristics. Simply put, the multi-scenario plan responds to real-time changes in the situation by assuming multiple scenarios, and the simulation planner improves the plan accuracy by generating simple simulations, and the number of times of re-planning. It is a mechanism that enables flexible plan control by reducing the number of plan executors and providing execution privileges separate from plan generation.
Multi-scenario plans function to reuse task chains that were originally discarded due to changes in the environment as sub-plans. It consists of two types of data: tasks and situations. Situations contain simplified game world information such as character position information, remaining HP, and enemy AI internal state IDs. Each situation references the situation before and after it to form a graph structure called the "Situation-Task Network" (ST-Network). As a result, intermediate states discovered during plan exploration can be included as branch points in the task chain.
ART-HTN deals with primitive tasks that have preconditions and simulated functions, as well as composite tasks that consist of multiple tasks, just like the compound tasks mentioned above. In the session, "FSM Task" and "Step Task" were introduced as examples of composite tasks. The FSM task is used by the simulation planner (described later) to predict enemy actions, and the step task is used to have a small number of loops and a limited number of branches during task execution. .
The simulation planner plays the role of generating the aforementioned ST-Network and deploying terminal nodes of situations. At this time, by simulating the enemy's behavior model, branching in each situation is also generated. When expanding terminal nodes, the decision-making system assigns each character a task that satisfies the preconditions. In addition, it was also possible to expand the current composite task if the composite task allowed it.
For example, when an FSM task in a situation transitions to "state a", "state b", and "state c", this FSM task expands to each copy instance. At this time, all data contained in the FSM task will be copied. Then the state transitions are executed, spawning three different task instances.
Since this process is performed by the decision-making system of every agent, the resulting ST-Network will have a huge number of nodes. To reduce this size, we designed it so that a probability threshold could be set for the unfolding process. Only when the random number exceeds this threshold will the task be deployed.
Character behavior is defined by tasks, but tasks themselves are not in a format that can be executed in a game environment. That's where the plan executor comes in. The plan executor selects the highest rated task from the ST-Networks situation node and then breaks it down into operators that can be run in the game. By executing them in order, the game character starts to move.
At the end of the session, a ridgeline shooting demo utilizing a hill detection algorithm based on terrain contour data and a powerful reconnaissance demo that executed all the long-term action plans described at the beginning were presented. Through this technical verification, we were able to confirm that ART-HTN can adapt to a dynamic environment. In the future, if game AI with long-term thinking ability like humans can be realized, the value of the game experience itself will change greatly.
Writer: Ritsuko Kawai