{'fraction_non_alphanumeric': 0.030135573239021513, 'fraction_numerical': 0.005452402004126142, 'mean_word_length': 4.888503253796095, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimal location and grouping of forces against spontaneous dynamic processes with Pseudo-Boolean optimization algorithms

We propose an algorithm based on the varying probabilities method and agent model for solving problems of optimal location of the agents (forces) counteracting the spread of natural spontaneous dynamic processes, calculation of optimal localization trajectories and grouping (clustering) of such agents by localizable processes.


Introduction
Natural disasters (floods, fires, spread of insect pests etc.) are often spontaneous distributed dynamic processes on the Earth surface. To predict the dynamics of processes and decision-making support in dealing with them, authors [1][2][3][4][5][6] offer a wide variety of models and systems for strategic modeling, operational-tactical modeling, etc. The problem of evaluating the efficiency of the measures taken to suppress the process is very important. The reader can notice the commonality of methods for controlling such processes, which depend little on the physical nature of the process. One of the methods of managing such a process is a direct impact on its front, another common method is its localization [1], i.e. creating insurmountable barriers to the territorial expansion of the process.
However, in emergency situations, when multiple processes cover a significant territory, the management of the available forces and means must ensure the elimination of all processes with the least losses. In this case, the situation management moves to the operational and tactical level and requires the use of a different mathematical models associated with the optimal location (placement) and grouping of forces and means.
In this paper, we considered a situation when several processes are simultaneously developed in a controlled area, and the decision maker has a number of teams, including personnel and technical means and for stopping and eliminating such processes. The parameters of propagating processes and the performance of commands are considered known. It is required to make decisions on the starting location of teams, their assignment to certain processes (grouping or clustering), and the appointment of fighting tactics, which together provide for the elimination of all processes at minimal total cost.

Development and localization model for a separate process
The distribution and control of a separate process can be described with the use of existing mathematical models [1]. In our research, we use experimental models [5,6] are based on simplified ideas about the process propagation and the use of experimental data. These models contain two submodels: one of them describes the physics of the process, and the other model based on the moving network method allows us to predict the propagation of the process front [7]. This method was proposed by S.K. Godunov for problems of gas dynamics [7] and allows us to build both the boundaries of the area of the spontaneous process, and the reachable areas of the teams fighting against this process. This method can be used in the construction of a localization process, since both processes are based on the construction of interacting reachable areas. Thus, the theory of localization control can be considered as a branch of the theory of dynamic games [8].
In the moving network model, at each moment of time, the process contour is considered as a continuous differentiable line on the plane. The equation of this line is At each point in the contour, the continuity condition is met: . The calculation algorithm of this method is based on the numerical integration of the family of the Hamilton-Jacobi equation characteristics: is the velocity vector, is the vector normal to the contour, grad φ/|grad φ| is the unit normal vector to the contour, vn=(gradφ/|gradφ|)v is the normal velocity value. The initial conditions for this equation should be given as a set of nodes on the plane N(0), forming the initial process contour. When the algorithm runs, each node moves in the direction of the outward normal and the set of nodes N(t) changes. As a result, we get two arrays: an array of coordinates of the front points xi(t) and array of normals to the front at these points pi(t), iϵN(t). To describe the structure of the contour for each point, the indexes of adjacent points mist be indicated. The algorithm based on the moving grid method is given in [7]. This algorithm is easily adapted for modeling the localization process.
The use of the moving grid algorithm allowed us to create an agent-based model of the propagation and localization processes. The model uses two types of agents, denoted by the symbols A and B. The A-agents are designed to simulate the propagation of a dynamic process. Their behavior is based on two models: a model of a physical phenomenon causing the propagation of the process [9,10], and a model of the propagation process based on the moving grids method of S.К. Godunov. The description of this algorithm is given in [7]. B-agents simulate the action of forces opposing the process and act on A agents. Their goal is to transfer all A-agents to a passive state. For this purpose, the B-agent moves along the modeling environment to the nearest A-agent and reduces the intensity of the physical phenomenon causing the propagation of the process IA(t): IA(t+1)=IA(t)-∆IB(t), where ΔIB(t) if the decrease in the intensity of the physical phenomenon causing the propagation of the process caused by the B-agent. After deactivation of an A-agent, the B-agent moves to the nearest active A-agent.
The path of A-agents should ensure the coverage and localization of the propagating process. At the beginning of the simulation algorithm, the algorithm selects two points on the map (point 1 and point 2). These are the starting points of the process front propagation and localization process. After running the algorithm, both processes (the propagation of the dynamic process by A-agents and its localization by B-agents) are built up step by step until the processes intersect. From two points of intersection, depending on the chosen bypass direction, the algorithm selects a new starting point of the localization process. Having drawn a straight line from point 1 to point 2, we get the beginning of the localization trajectory. Then the construction of the localization process begins from point 2 and the next section of the localization trajectory is built. The algorithm works until the localization path closes or the marker number 1 is in the zone of the process propagation front. The second case means that the localization trajectory is impossible. The localization process is constructed in a simplified manner, under assumption that the speed of movement of the A-agent is taken to be equal in any direction. The orientation relative to the of the process (fire) front propagation is clockwise. In more complex cases, a larger number of agents B may be involved, starting from different initial locations.

Optimization model
In the case of simultaneously distributing several spontaneous processes, the limited human resources (agents B) make it necessary to choose solutions for process localization that are optimal in terms of Otherwise, we have a two-criteria optimization problem: minimizing the damage Kd while minimizing the resources expended R. The second version of the problem is more complicated. However, for such a problem, the front of Pareto-optimal solutions can be calculated by solving a series of problems.
At the initial stages of personnel training in the tactics of fighting the spontaneous natural processes and the distribution of available resources, we can implement the following simplified model. Let us denote the number of available B-agents (brigades) as NA. In this case, the resources are the B-agents that are available: R=NA≤Rmax.
As a criterion characterizing the damage caused by the process, we can take the area of damage after localization: Кd=S.
As a rule, the decision maker considers a limited number of possible starting points for the placement of B-agents. The possible initial positions are determined by the permanent location of brigades, possible road exits, etc. Denote the number of possible the initial points of B-agents as NP.
Knowing the initial location of the B-agents, we can construct optimal localization trajectories for each of the agents [11]. The obtained localization trajectories uniquely determine the modeled configuration of the process front at each moment of time. In such models [7], time is discrete. Thus, we have an algorithmically implemented function that reflects the set of possible initial points of location of B-agents in the number of NA (with a finite set of possible initial points for each of these agents of cardinality NP) on the set of real numbers (final square of damage S): S=F(X1,…XNA).
Here, F is a function that is algorithmically implemented by an agent-oriented simulation system; Xi are the initial points of each of the B-agents.
Let us denote the developing spontaneous processes that require localization as Ck, 1≤k≤NC, where NC is the number of such simultaneously developing processes. Simulation of each of these processes using the agent-based simulation system will be performed independently of each other. To simplify the model, we assume that if the B-agent is busy localizing one of such processes, then it does not participate in localizing the other process, regardless of the time required to localize each of the processes.
Let Pj, 1≤j≤NP be the possible points of the initial location of B-agents. We introduce the Boolean variables yijk, which are equal to 1, if the ith agent is initially located at the point Pj and is later involved in the localization of the process Ck (otherwise, yijk=0). Let these variables form a threedimensional array Y = [yijk]. Then the problem of choosing the optimal location with the simultaneous grouping of agents of type B by localizable processes can be represented as a problem of pseudo-Boolean combinatorial optimization [12]: Approaches to solving such problems are well-known [13,14]. In particular, many authors apply pseudo-Boolean optimization problem linearization [15], followed by solving the integer linear programming problem, the relaxation method, and greedy algorithms [14][15][16] both individually and as a part of various metaheuristics [14]. We can consider such a problem as a problem on the optimal production capacity scheduling with the simultaneous solution of the problem of optimal placement of the capacities. Here, our B-agents are the capacities.

Optimization algorithm
We use the following local search procedures sequentially improving the current solution y * ijk .
Procedure #2. Alternation of the process associated with the agent: for each Greedy procedure #3. Agent elimination. Assign S'=+∞; The greedy procedure #3 can be applied until constraint (3) is satisfied. The use of this procedure allows us to bring an infeasible arbitrary problem solution with an excessive number of the agents to a valid solution.
The varying probabilities method [14] is an efficient global search scheme for such pseudo-Boolean problems. This method sequentially generates random initial solutions of the pseudo-Boolean optimization problem (possibly infeasible, with an excessive number of the non-zero variables). The probability that the variable yijk takes the value 1 is denoted by pijk. To the obtained solution yijk, the proposed algorithm applies the local search procedures and greedy procedure. As a result, we obtain some feasible solution yijk, and depending on the corresponding value of S(yijk), the probabilities pijk change.
Assign xjk=r pijk. end for; Choose a pair of indexes j,k with the maximum value of xjk. Assign yijk=1. End for; Return matrix Y. Varying probability algorithm for optimal location of B-agents and grouping of agents by the localized processes.

Computational example
Let us consider an example of solving the optimal B-agent location problem. Below are the parameters of the environment and the characteristics of the B-agents (fire-fighting teams) and other data used in this example. The type of the main conductors of combustion is dry. Fire hazard class for weather conditions is 4th. The wind direction is northwest in the first 4 hours of imitation, northeast after 4 hours. Wind speed under the forest canopy is 2 m/s in the first 4 hours of imitation, and 2.5 m/s after 4 hours. Fire forces are teams of 5 people. The fire area at the time of fire detection is 0.179 ha, the time of free fire spread (from the moment of detection to the placement of commands) is 3 hours. Table 1 presents the results of computational experiments with some of the initial location options generated by the algorithm during its iterations. We can see that the options vary greatly in the size of the modeled damage. In this example, the algorithm chooses option 5 as the optimal variant of the initial placement of opposing agents according to the criterion of the minimum area.

Conclusion
This paper proposes an algorithm for solving problems of optimal location of agents that counteract the spread of natural spontaneous dynamic processes and their grouping (distribution) by localized processes. The algorithm is based on the agent model, which allows us to simulate and evaluate the consequences of the development of a spontaneous process, acting as the objective function. The operation of the algorithm is illustrated by a computational experiment.