CN113901630B - A method of deploying ground teams for space search and rescue based on grid technology - Google Patents
A method of deploying ground teams for space search and rescue based on grid technology Download PDFInfo
- Publication number
- CN113901630B CN113901630B CN202010639323.0A CN202010639323A CN113901630B CN 113901630 B CN113901630 B CN 113901630B CN 202010639323 A CN202010639323 A CN 202010639323A CN 113901630 B CN113901630 B CN 113901630B
- Authority
- CN
- China
- Prior art keywords
- grid
- rescue
- search
- landing
- reflector
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/20—Design optimisation, verification or simulation
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/10—Geometric CAD
- G06F30/18—Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2119/00—Details relating to the type or aim of the analysis or the optimisation
- G06F2119/14—Force analysis or force optimisation, e.g. static or dynamic forces
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Geometry (AREA)
- Computer Hardware Design (AREA)
- General Engineering & Computer Science (AREA)
- Evolutionary Computation (AREA)
- Computational Mathematics (AREA)
- Pure & Applied Mathematics (AREA)
- Mathematical Optimization (AREA)
- Mathematical Analysis (AREA)
- Computer Networks & Wireless Communication (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
本发明公开了一种基于网格技术的航天搜救地面分队布势方法，所述方法包括：以返回器的理论落点为中心确定理论着陆区，将理论着陆区划定为若干个网格并计算每个网格的着陆概率；以理论着陆区四周的搜救区域作为航天搜救地面分队的布势区域，将布势区域划分为网格并进行编号；以所有航天搜救地面分队从布势区域抵达每个航天器着陆点网格的期望时间为优化指标，建立航天搜救地面分队布势方案的最优化问题；采用模拟退火算法求解求最优化问题，输出各航天搜救地面分队的待命网格编号。通过本发明的方法能够得到最优布势方案，从而使使地面分队尽快抵达返回器着陆现场，及时展开处置工作。
The present invention discloses a method for deploying a space search and rescue ground team based on grid technology, the method comprising: determining a theoretical landing area with the theoretical landing point of the returner as the center, dividing the theoretical landing area into a number of grids and calculating the landing probability of each grid; taking the search and rescue area around the theoretical landing area as the deployment area of the space search and rescue ground team, dividing the deployment area into grids and numbering them; taking the expected time for all space search and rescue ground teams to arrive at each spacecraft landing point grid from the deployment area as the optimization index, establishing the optimization problem of the deployment plan of the space search and rescue ground team; using the simulated annealing algorithm to solve the optimization problem, and outputting the standby grid number of each space search and rescue ground team. The method of the present invention can obtain the optimal deployment plan, so that the ground team can arrive at the returner landing site as soon as possible and carry out disposal work in time.
Description
Technical Field
The invention relates to the field of spaceflight search and rescue, in particular to a grid technology-based spaceflight search and rescue ground grouping and potential distribution method.
Background
With the deep advancement of manned space projects and lunar exploration projects in China, various space search and rescue tasks show a trend of high frequency, normalization and increased emergency events, which requires space search and rescue ground teams to quickly reach a reflector landing site in a short time. The scientific and reasonable ground team distribution scheme is beneficial to ensuring the team safety, improving the team search and rescue efficiency and shortening the time for completing the task.
In the field of space search and rescue gesture distribution, the lack of a corresponding mathematical model currently leads to incapability of quantifying gesture distribution scheme efficiency and incapability of scientifically solving and obtaining gesture distribution schemes. The problem similar to the problem of deployment is the problem of deployment of forces, which requires that the force configuration scheme is formulated according to the conditions of enemy, battlefield environment and task targets, so that the task requirements are met to the maximum. At present, research on army deployment at home and abroad is basically focused on battle fields such as battle field attack and defense, air combat and the like. Li Zhigang, and the like, aiming at the problem of deployment of the attack and defense forces of the battle field, a deployment model based on two layers of integer programming is established, wherein the first layer is a construction level unit decision layer, the layer takes the capturing of points and the elimination of enemy forces as soon as possible as targets, the sum of the number of the forces is fixed as constraint, a dynamic programming algorithm is adopted to establish continuous level unit force distribution, the second layer is a continuous level unit decision layer, the layer takes the decision result of the first layer as constraint condition, the aim of destroying enemy in unit time is fulfilled at maximum, and a depth configuration scheme of the forces is formulated by adopting the dynamic programming algorithm. In the aspect of air defense deployment, ren Jiye, shen Maoxing and the like consider the fight against victory or defeat of the friend or foe as probability events, the probability of defeating the attack of the friend or foe is maximum, and the air defense deployment problem is solved by adopting a linear programming method. Kong Xiangyu introducing a game theory into the problem of regional air defense and air combat deployment, taking uncertainty factors in war into consideration on the basis of measuring the air defense and air combat capability index, introducing a random correction factor, adopting a game matrix method, establishing an air defense deployment game model, solving Nash equilibrium points of the model by using a particle swarm algorithm, and obtaining a mixed strategy of the two parties of the fighter. Xiong Zhe and the like consider the problem of deployment of the air force of the mixed-woven group, comprehensively consider the importance degree of a protection target, the probability of protection success, the constitution of mixed-woven forces and the factors of battlefield environment, take the weighted sum of the products of the battlefield effectiveness of protected areas and the importance degree of areas as an optimized objective function, take the number of forces as constraint, and adopt an improved genetic algorithm to obtain the deployment scheme of the forces.
Compared with the traditional force deployment model, the following two important differences exist in the distribution of the space search and rescue field:
First, the objects are different. The object facing the space search and rescue task is a reflector, which is different from the traditional fight object in the field of army deployment. In the traditional force deployment model, an existing reflector model is lacking, and related researches on how the reflector state influences force deployment are lacking.
The second purpose is different. The army deployment research in the battle field is to hit opponents and protect the decision process of the targets at the maximum possible under the hostile state of 'your death my alive', and the aim of spaceflight search and rescue is to lead the ground team to arrive at the landing site of the reflector as soon as possible and to develop disposal work in time.
Therefore, the problem of space search and rescue deployment is greatly different from the problem of traditional force deployment, and the existing force deployment model cannot be directly used.
At present, the research on the force deployment problem in the field of spaceflight search and rescue is still in a starting stage, and mainly has the following two problems:
Firstly, a ready-made space search and rescue mathematical model is lacking, unified modeling of a reflector, a search and rescue area and a search and rescue team is not available at present, so that a search and rescue layout problem lacks a research foundation, and solving of a search and rescue layout scheme is severely restricted.
Secondly, a quantitative description and solving method for the search and rescue gesture distribution problem is lacking, a systematic study on gesture distribution task optimization indexes and constraint conditions is lacking, a gesture distribution model is not directly available, and an existing solving algorithm can be used for obtaining the search and rescue gesture distribution scheme.
Disclosure of Invention
The invention aims to overcome the technical defects and provides a space search and rescue ground team potential distribution method based on a grid technology, which comprises the steps of completing space search and rescue area modeling based on the grid technology; establishing a reflector mathematical model based on landing spreading probability, taking the shortest time of the teams corresponding to the scheme to reach the landing points as an index, comprehensively considering the teams safety and the regional trafficability constraint, establishing a mathematical model of a ground teams distribution scheme, and solving by adopting a simulated annealing algorithm to obtain the distribution scheme.
In order to achieve the above purpose, the invention provides a grid technology-based spaceflight search and rescue ground grouping and potential distribution method, which comprises the following steps:
Determining a theoretical landing zone by taking a theoretical landing point of a reflector as a center, demarcating the theoretical landing zone into a plurality of grids, and calculating landing probability of each grid;
taking the search and rescue area around the theoretical landing area as a potential distribution area of the spaceflight search and rescue ground teams, dividing the potential distribution area into grids and numbering;
Taking the expected time of all the spaceflight search and rescue ground teams from the potential distribution areas to each spacecraft landing site grid as an optimization index, and establishing an optimization problem of a spaceflight search and rescue ground teams potential distribution scheme;
And solving an optimization problem by adopting a simulated annealing algorithm, and outputting standby grid numbers of each spaceflight search and rescue ground team.
As an improvement of the method, the method is characterized in that a theoretical landing zone is determined by taking a theoretical landing point of a reflector as a center, the theoretical landing zone is divided into a plurality of grids, and the landing probability of each grid is calculated, and the method specifically comprises the following steps:
Determining a theoretical landing zone by taking a theoretical landing point of a reflector as a center, and demarcating the theoretical landing zone into a plurality of grids U D＝{d1,…,dD, wherein D represents the total number of grids of the theoretical landing zone, D i represents the number of the ith grid, i=1, 2,;
Comprehensively considering the influence of the gravity, the air resistance and the rotation of the earth, and establishing a reflector drop point forecasting dynamic model as follows:
r is the position of the mass center of the reflector, AndFor the first and second derivatives of the reflector relative to the geocentric system, the equation of the motion dynamics of the reflector centroid isWherein m is the mass of the reflector, g is the gravitational acceleration, F D is the aerodynamic force,For traction force, F k = -mω× (ωxr) is coriolis force, ω is earth rotation angular velocity;
Generating a large number of initial positions and initial speeds of the reflector with random deviation, taking the initial positions and the initial speeds of the reflector as initial conditions of a reflector barycenter motion dynamics equation, inputting the initial conditions into a reflector falling point forecasting dynamics model, using a Dragon-Gregory tower method to numerically solve the barycenter dynamics equation, simulating a reflector landing process, and further obtaining a series of reflector landing points;
and counting the simulated landing times of the returners in each grid area to obtain the landing probability of the returners in each grid, wherein the landing probability of the returners in the grid d i is p i.
As an improvement of the method, the method takes the expected time of all the spaceflight search and rescue ground teams from the potential distribution area to each spacecraft landing site grid as an optimization index, establishes an optimization problem of a spaceflight search and rescue ground teams potential distribution scheme, and specifically comprises the following steps:
the grid number set of the distribution area is marked as omega m, and the subscript m represents the total number of grids available for distribution;
When the reflector is landed on the grid with the number of d i, the kth space search and rescue ground team starts from the initial time position P k, the time t ki required by the shortest time-consuming path to reach the grid d i is calculated, and then the shortest time for at least one space search and rescue ground team to reach the grid with the number of d i is K is the total number of space search and rescue ground teams;
traversing all possible landing situations of the reflector, the expected time for completing the search task is Therefore, solving the optimal gesture problem can be converted into solving the initial position P k of the kth search and rescue team, where P k is required to be located in the gesture area Ω m and the expected time for completing the task is the shortest, the optimization problem is:
As an improvement of the method, the method further comprises the steps of calculating the passing factors of adjacent grids in the theoretical landing zone for the kth space search and rescue ground team, and specifically comprises the following steps:
The maximum ideal speed of the kth space search and rescue ground team which can be achieved in the theoretical landing zone is V max, the maximum travelling speed of the team from the grid m to the grid n is V mn, and the passing factor gamma mn of the team from the grid m to the grid n is defined as The maximum travelling speed between two grids is determined according to the topographic and topographic data in each grid and the travelling condition of the motorcade, the central point of each grid area is abstracted into a vertex by adopting a topological graph method, the adjacent grids are connected by using directed edges, each directed edge is given a weight, and the weight represents a passing factor of the motorcade from the starting point of the directed edge to the ending point of the directed edge.
As an improvement of the method, when the reflector is landed on the grid with the number of d i, the kth space search and rescue ground team starts from the initial time position P k, and the shortest time t ki required by the time-consuming optimal path to reach the grid d i is calculated, which specifically includes:
When the returning device is landed on the grid with the number of d i, the k-th space search and rescue ground team starts from the initial time position P k, the passing factor from the two adjacent grids m to the grid n which possibly pass through is gamma mn, the speed V mn＝Vmaxγmn and the maximum speed V max of the team between the two grids are provided, and the passing time from the grid m to the grid n is provided Wherein l mn is the distance from grid m to the center point of grid n;
After the travel time of the kth space search and rescue ground team among grids is obtained, calculating an optimal path between the team and the reflector landing grid and a corresponding required shortest time t ki by using a Dijkstra algorithm in graph theory.
As an improvement of the method, the simulated annealing algorithm is adopted to solve the optimization problem and output the standby grid number of each spaceflight search and rescue ground team, and the method specifically comprises the following steps:
Step S1), the optimization objective function of the search and rescue cloth potential problem is recorded as S represents a distribution scheme, wherein the scheme gives grid numbers of all spaceflight search and rescue ground teams at the initial moment;
Step S2), setting an initial annealing temperature T, a fire stopping temperature T f and the number of internal circulation times N, and selecting one of the feasible distribution schemes as a scheme initial value S;
Step S3), setting the iteration times l to 0;
step S4) randomly generating a new set of gesture schemes S';
Step S5) calculates an annealing temperature difference delta t=t (S ') -T (S), judges whether delta T <0 is true, if so, receives S ' as the current optimal solution, and makes S equal to S ', and enters step S6), otherwise, receives S ' as the current optimal solution with the probability of exp (-delta T/T), makes S equal to S ', and enters step S6);
step S6), adding 1 to the value of l, judging whether l is smaller than N, if yes, turning to step S4), otherwise, turning to step S7);
Step S7) if the current temperature T is smaller than the fire stopping temperature T f, turning to step S3), otherwise, turning to step S8);
Step S8) updating T by using a temperature strictly less than T to enable T to trend to 0, when T is greater than the fire stopping temperature T f, turning to step S3), otherwise, turning to step S9);
Step S9) outputs S as the final gesture scheme.
The invention has the advantages that:
1. The invention establishes a gridding model of a search area, divides the ground area into a series of grids by using regular rectangular units by referring to the geographic space information grid technology, and establishes the gridding model of the search area by adopting a directed graph after endowing the grids with passing factors;
2. the method adopts a landing probability mode to replace the previous longitude and latitude drop point forecasting mode, utilizes the landing probability of the reflector in each grid obtained by the reflector drop point forecasting dynamics model, takes the landing probability as the unique attribute of the reflector, and establishes a reflector model of the spaceflight search and rescue task;
3. The invention establishes a mathematical model of a search and rescue gesture distribution problem, takes the weighted shortest time of the teams reaching the landing position of the reflector as an optimization target, takes the teams safety and the teams quantity as constraint conditions, and establishes a discrete planning model capable of solving a gesture distribution scheme;
4. According to the method, the simulated annealing algorithm is adopted to solve the search and rescue gesture distribution model, so that an optimal gesture distribution scheme is obtained, and the scheme can enable ground teams to arrive at a reflector landing site as soon as possible, and can be used for spreading disposal work in time.
Drawings
FIG. 1 is a pass factor topology of the present invention;
FIG. 2 is a flow chart of a grid technology-based method for space search and rescue ground queuing and potential distribution;
FIG. 3 is a flow chart of the optimal potential distribution scheme solving based on the simulated annealing algorithm;
FIG. 4 (a) is a schematic diagram of a theoretical landing zone and a potential zone;
FIG. 4 (b) is a schematic representation of a first gesture scheme obtained using the method of the present invention;
FIG. 4 (c) is a schematic representation of a second weave pattern obtained using the method of the invention;
FIG. 4 (d) is a schematic representation of a third potential distribution scheme obtained using the method of the present invention.
Detailed Description
The technical scheme of the invention is described in detail below with reference to the accompanying drawings.
The standby position of each team is deployed before the space search and rescue task is executed, and the standby position is called the distribution of the search and rescue team. The existing ground grouping and potential distribution scheme is formulated according to factors such as landing areas of spaceflight returners and performance of search and rescue vehicles based on historical task experience. Due to the lack of a related mathematical model of the distribution of the spaceflight search and rescue teams and a solution algorithm of the distribution scheme, the existing distribution mode has the defects that the distribution scheme is insufficient in scientificity and the search and rescue efficiency of the scheme cannot be quantified.
Therefore, the invention provides a grid technology-based spaceflight search and rescue ground queuing and distribution method, which specifically comprises the following steps:
1. Technical approach
The method comprises the steps of firstly respectively constructing element models influencing a distribution scheme, including a geographical environment model of a search and rescue area, a ground distribution model and a reflector model, so as to establish a space search and rescue mathematical model, then establishing mathematical description of the search and rescue distribution problem by taking the landing point time of the distribution to the reflector as an optimization index and ensuring the safety of the distribution as a constraint condition, and finally solving the distribution problem by using a simulated annealing algorithm to obtain the distribution scheme.
1.1 Establishing a mathematical model
1.1.1 Modeling of geographical factors for search and rescue regions
Geographical factors such as lakes, rivers, cliffs, guls, mountains, fences, roads and the like in the search and rescue area have great influence on search and rescue activities, and the geographical environment in the search and rescue area needs to be modeled first. Gridding is the basis of a geographic information system and a path planning method, and is a widely used method capable of effectively representing geographic environments. The method for meshing the geographic space information is used for referencing the geographic space information, and regular grid units are used for meshing the ground area, namely the search and rescue area is divided into regular rectangular grids with sufficiently small dimensions, and corresponding geographic attributes are given to the grids and used for approaching the real ground surface environment, so that modeling of the complex geographic environment is realized.
The size of the rectangular grid is an important parameter for grid division. If the side length of the selected grid is too large, the grid is insufficient to approach the real geographic environment, so that the environment modeling is distorted, and on the other hand, the detection range of the search and rescue team cannot cover the grid where the search and rescue team is located, so that the situation that the return can not be detected even if the team and the return are located on the same grid can occur. On the contrary, if the grid side length is too small, the calculation amount of the ground queuing scheme is greatly increased, and even the problem is caused to be insoluble. Therefore, it is necessary to select an appropriate mesh size according to task demands. In the patent model, the principle of selecting the side length parameters is that the identification distance of the search and rescue target by the detection equipment is rounded downwards.
The trafficability attribute of the grid is an index comprehensively reflecting the trafficability of the search and rescue team in the grid, and directly influences the forward route planning of the team, thereby influencing the selection of a distribution scheme. The maximum travel speeds that can be achieved by the same vehicle in different terrains are different, and in the same terrains, the travel speeds of different types of vehicles are also different. Meanwhile, the passing attribute is also related to the traveling direction of the team, if there are ravines running in east and west directions in the grid, the vehicle can pass through the grid when traveling in east and west directions, and is blocked when passing in south and north directions. The present invention describes passable attributes using a passfactor. The traffic factor is a real number between 0 and 1, and the closer to 1, the higher the traffic capacity is, the higher the forward speed which can be achieved by the teams is. The traffic factor is calculated in such a way that, assuming that the maximum ideal speed that can be achieved by a certain team in the search and rescue area is V max and the maximum travelling speed of the team from the grid numbered m to the grid numbered n is V mn, the traffic factor gamma mn of the team from the grid m to the grid n is defined asIn order to visually represent the passing factors of the teams, the center point of each grid area is abstracted into vertexes by adopting a topological graph method, the adjacent grids are connected by using directed edges, each directed edge is given a weight, and the weight represents the passing factors of the teams from the starting point of the directed edge to the end point of the directed edge. Fig. 1 is a schematic representation of a pass-factor topology of 4 grids.
The maximum travelling speed between the V max and the two grids can be determined manually by collecting the topographic data in each grid and combining the travelling condition of the actual motorcade.
1.1.2 Modeling of ground search and rescue teams
The ground search and rescue team is modeled as a point target with a location parameter, a maximum travel speed, and a detection range parameter. In the problem of potential distribution, the position and the maximum speed of the team mainly influence the planning of a search and rescue path and the calculation of the time for finally completing search and rescue, and the detection range is mainly used for determining the size of a grid.
The minimum time required for each team to reach the reflector landing site can be determined after the travel path of each team is determined, and therefore, the planning of the optimal path is the basis for solving the problem of placement. In order to obtain the shortest path between the search and rescue team and the reflector landing site, the time required for the team to travel between grid areas is calculated from the traffic factor topology. For this purpose, the maximum travel speed V max of the search and rescue team is first multiplied by the corresponding traffic factor to obtain the travel speed of the team between the two grids. For example, to obtain the time t ij required for a search and rescue team to reach grid j from grid i, the maximum speed V max is multiplied by the traffic factor γ ij of grid i and grid j to obtain the speed V ij＝Vmaxγij of the team between the two grids, and the corresponding traffic time is further obtainedWhere l ij is the distance from grid i to the center point of grid j. After the travel time of the queue between grids is obtained, the optimal path and the minimum time required between the queue and the reflector landing grid can be obtained by using Dijkstra algorithm in graph theory.
1.1.3 Return modeling
The landing information of the reflector determines the search and rescue recovery area, and has great influence on the gesture distribution scheme. The prior drop point prediction belongs to a point prediction mode, and predicts the longitude and latitude of a theoretical landing point of a reflector. Due to the existence of the prediction error, a certain deviation may exist between the actual landing point of the reflector and the theoretical landing point, and the point prediction mode cannot provide landing range information of the reflector. In order to comprehensively consider the influence of the prediction error, in the patent model, a landing probability prediction mode is used for replacing the conventional point prediction mode. The landing probability prediction mode refers to predicting landing probabilities of the returner within the respective grids. At this point, the forecasted landing sites will be replaced with the forecasted landing areas and landing probabilities. The predicted landing probability may quantitatively reflect the landing spread of the reflector.
In order to calculate the landing probability of the reflector in each grid, firstly, taking each factor influencing the landing point of the reflector as a model input parameter, comprehensively considering the influence of the gravity, the air resistance and the earth rotation, establishing a reflector landing point forecasting dynamics model as follows, marking r as the center of mass position of the reflector,AndFor the first and second derivatives of the reflector relative to the geocentric system, the equation of the motion dynamics of the reflector centroid isWherein m is the mass of the reflector, g is the gravitational acceleration, F D is the aerodynamic force,For traction force, F k = -mω× (ω×r) is coriolis force, ω is earth rotation angular velocity.
And then using a computer to generate a large number of initial positions and initial speeds of the returners with random deviation, substituting the initial positions and the initial speeds of the returners as initial conditions of a returner centroid motion dynamics equation into a drop point prediction model, and using a Longgar tower method numerical value to solve the centroid dynamics equation, so that the landing process of the returners can be simulated, and a series of returner landing points can be obtained. And finally, counting the simulated landing times of the returners in each grid area, and obtaining the landing probability of the returners in each grid. After the landing probability of the reflector is obtained, the landing range of the reflector is quantitatively described, and search and rescue target data support can be provided for subsequent potential problem solving.
1.2 Search and rescue cloth gesture
The invention describes the problem of the ground teams as follows:
The optimal placement problem based on the theoretical landing probability refers to how to determine the standby position of each team at the initial moment of the task by knowing the landing probability of each grid of the reflector in the theoretical landing zone, so that each team stands by outside the theoretical landing zone, and the expected time for completing the search and rescue task is the shortest. The shortest search and rescue time is the minimum time from the initial moment when at least one ground team arrives at the landing point of the reflector.
The flow chart of the ground search and rescue team distribution algorithm is shown in fig. 2. As can be seen from the figure, the algorithm needs to use the grid passing factor, the landing probability of the reflector in each grid, the maximum travelling speed of each team and the distribution area as input parameters, wherein the distribution area refers to the area where the search and rescue strength vehicles can be arranged at the initial moment and is defined as a search and rescue area except a theoretical landing area. The potential distribution scheme solving algorithm outputs standby grid numbers of each search and rescue team.
Let the mesh number corresponding to the theoretical landing zone be U D＝{d1,…,dD, where D represents the theoretical landing zone mesh total number, D i (i=1, 2,., D represents the number of the ith mesh). The grid number set of the distribution area is marked as omega m, and the subscript m represents that the total number of grids available for distribution is m. The probability of landing of the reflector in grid D j is p j (j=1, 2, d.). Assuming that the reflector lands on grid d j, the time required for the ith search and rescue team to reach grid d j along the shortest time-consuming path from initial time position P i is t ij, then the shortest time for at least one search and rescue team to reach the reflector landing grid isTraversing all possible landing situations, the expected time to complete the search task is known to beTherefore, solving the optimal potential problem can be converted into solving the initial position P i of the ith search and rescue team, requiring that P i be located in the potential area Ω m, and the expected time to complete the task is the shortest, that is, solving the optimal problem:
In order to overcome the difficulty of completely solving the huge calculation amount, the method solves the problem of ground formation potential distribution by using a simulation method, and obtains a reasonable potential distribution scheme which is approximately optimal in an allowable time. To use the simulated annealing algorithm, the optimization objective function of the search and rescue gesture problem is recorded as Wherein S represents a gesture distribution scheme which gives the grid number of the ith search and rescue team at the initial moment. A flowchart of an algorithm for solving the ground-based teaming potential problem using a simulated annealing algorithm is shown in fig. 3.
The optimal potential distribution scheme solving algorithm comprises the following specific steps:
(1) Setting an initial annealing temperature T, a fire stopping temperature T f and the number of internal circulation times N, and selecting one of the feasible distribution schemes as a scheme initial value S;
(2) Iterating the steps (3) to (5) for N times;
(3) Randomly generating a new set of distribution schemes S';
(4) Calculating an annealing temperature difference Δt=t (S') -t (S);
(5) If delta T is less than 0, S ' is received as the current optimal solution, namely S is enabled to be equal to S ', otherwise S ' is received as the current optimal solution with the probability of exp (-delta T/T);
(6) If the current temperature T is smaller than the fire stopping temperature T f, the step (8) is carried out, otherwise, the step (7) is carried out;
(7) Temperatures strictly less than T are used to update T, where it is required that T tends to be 0 as the number of cycling steps increases. When the T is greater than the fire stopping temperature T f, the step (2) is carried out, otherwise, the step (8) is carried out;
(8) And outputting S as a final distribution scheme obtained by an algorithm.
2. Technical effects
The invention has the technical effect of providing a gesture distribution scheme for search and rescue teams. The rationality and the display of the ground queuing distribution algorithm of the patent are verified through two groups of simulation tests.
The first calculation is shown in fig. 4 (a), assuming that the area to be deployed is a grid corresponding to the edge of the search and rescue area, the search and rescue area is divided into 9×7 square grids, each grid is 6km long, the theoretical landing zone of the reflector is divided into 7×5 grids, fig. 4 (b) is an abstract search and rescue area schematic diagram, the gray area in the figure represents a spreadable area, the white grid represents a passable grid, the black grid represents a passable grid, and the grids correspond to lakes in the figure. The numbers in the white area in the figure simulate the landing probabilities of the returners taking the area center point as the aiming point in each grid, and the landing probability of the area center point grid is maximum, and the landing probability corresponding to the grid which is farther from the center point is smaller.
The search and rescue teams are set to be 8, in order to simplify verification parameters, the travelling speed of each team in the search and rescue area is 60km/h under the assumption that the travelling speed of each team in the search and rescue area is the same, at the moment, the passing factors of each team between any two adjacent passable grids are 1, and the travelling time between the two grids can be obtained by dividing the straight line distance between the middle points of the grids by the vehicle speed.
The distribution scheme obtained by using the distribution algorithm of the invention is shown by the round dots in the figure 4 (b), the numbers below the round dots represent the team numbers, the average completion search and rescue time corresponding to the distribution scheme is 15.53min, the fastest completion task time is 12.00min, and the slowest search and rescue can be completed within 18.00 min. As can be seen from the figure, the search and rescue teams in the optimal distribution scheme are distributed in regions more dispersedly, because if the teams are concentrated in the region near the theoretical landing point at the initial moment, when the reflector has a small probability and larger landing deviation, the search and rescue teams cannot reach the landing point of the reflector in time, so that the search and rescue time is too long. The optimal distribution algorithm proposal provided by the method can automatically avoid the 'bundling' distribution of the search and rescue teams, and accords with the previous distribution experience. Meanwhile, in the gesture distribution scheme, the deployment of the teams avoids a plurality of grids at the lower right corner. This is because, if the team is disposed at the lower right, it will be blocked by the non-passable area, and the team needs to detour to go to the landing area of the reflector, increasing the time for completing the search and rescue, and reducing the search and rescue efficiency.
Under the condition that the parameters of the search and rescue area are unchanged, the parameters of the vehicle speed are changed, and an optimal distribution scheme under the condition that the team speeds are different is researched. For this reason, assuming that the travelling speeds of the search and rescue teams 1 and 2 are 80km/h, the speeds of the other search and rescue teams are 60km/h, and under the condition that other parameters are unchanged, two optimal distribution schemes as shown in fig. 4 (c) and 4 (d) can be obtained, and the average time required for completing tasks of the two schemes is 12.39min. Thus, for the optimal placement problem, the solution is not unique and there may be several different optimal solutions.
Finally, it should be noted that the above embodiments are only for illustrating the technical solution of the present invention and are not limiting. Although the present invention has been described in detail with reference to the embodiments, it should be understood by those skilled in the art that modifications and equivalents may be made thereto without departing from the spirit and scope of the present invention, which is intended to be covered by the appended claims.
Claims (5)
1. A method for spaceflight search and rescue ground grouping and distribution based on a grid technology, the method comprising:
Determining a theoretical landing zone by taking a theoretical landing point of a reflector as a center, demarcating the theoretical landing zone into a plurality of grids, and calculating landing probability of each grid;
taking the search and rescue area around the theoretical landing area as a potential distribution area of the spaceflight search and rescue ground teams, dividing the potential distribution area into grids and numbering;
Taking the expected time of all the spaceflight search and rescue ground teams from the potential distribution areas to each spacecraft landing site grid as an optimization index, and establishing an optimization problem of a spaceflight search and rescue ground teams potential distribution scheme;
Solving an optimization problem by adopting a simulated annealing algorithm, and outputting standby grid numbers of each spaceflight search and rescue ground team;
the method for determining the theoretical landing zone by taking the theoretical landing point of the reflector as the center, dividing the theoretical landing zone into a plurality of grids and calculating the landing probability of each grid comprises the following steps:
Determining a theoretical landing zone by taking a theoretical landing point of a reflector as a center, and demarcating the theoretical landing zone into a plurality of grids U D＝{d1,…,dD, wherein D represents the total number of grids of the theoretical landing zone, D i represents the number of the ith grid, i=1, 2,;
Comprehensively considering the influence of the gravity, the air resistance and the rotation of the earth, and establishing a reflector drop point forecasting dynamic model as follows:
r is the position of the mass center of the reflector, AndFor the first and second derivatives of the reflector relative to the geocentric system, the equation of the motion dynamics of the reflector centroid isWherein m is the mass of the reflector, g is the gravitational acceleration, F D is the aerodynamic force,For traction force, F k = -mω× (ωxr) is coriolis force, ω is earth rotation angular velocity;
Generating a large number of initial positions and initial speeds of the reflector with random deviation, taking the initial positions and the initial speeds of the reflector as initial conditions of a reflector barycenter motion dynamics equation, inputting the initial conditions into a reflector falling point forecasting dynamics model, using a Dragon-Gregory tower method to numerically solve the barycenter dynamics equation, simulating a reflector landing process, and further obtaining a series of reflector landing points;
and counting the simulated landing times of the returners in each grid area to obtain the landing probability of the returners in each grid, wherein the landing probability of the returners in the grid d i is p i.
2. The grid technology-based space search and rescue ground squash distribution method according to claim 1, wherein the method is characterized in that the expected time for all space search and rescue ground squash to reach each spacecraft landing site grid from a distribution area is used as an optimization index to establish an optimization problem of a space search and rescue ground squash distribution scheme, and specifically comprises the following steps:
The grid number set of the distribution area is marked as omega m, and the subscript m represents the total number of grids available for distribution;
When the reflector is landed on the grid with the number of d i, the kth space search and rescue ground team starts from the initial time position P k, the time t ki required by the shortest time-consuming path to reach the grid d i is calculated, and then the shortest time for at least one space search and rescue ground team to reach the grid with the number of d i is K is the total number of space search and rescue ground teams;
traversing all possible landing situations of the reflector, the expected time for completing the search task is Therefore, solving the optimal gesture problem can be converted into solving the initial position P k of the kth search and rescue team, where P k is required to be located in the gesture area Ω m and the expected time for completing the task is the shortest, the optimization problem is:
3. The grid technology-based space search and rescue ground queuing method according to claim 2, wherein the method further comprises the steps of calculating the passing factors of adjacent grids in a theoretical landing zone for the kth space search and rescue ground queuing, and specifically comprises the following steps:
The maximum ideal speed of the kth space search and rescue ground team which can be achieved in the theoretical landing zone is V max, the maximum travelling speed of the team from the grid m to the grid n is V mn, and the passing factor gamma mn of the team from the grid m to the grid n is defined as The maximum travelling speed between two grids is determined according to the topographic and topographic data in each grid and the travelling condition of the motorcade, the central point of each grid area is abstracted into a vertex by adopting a topological graph method, the adjacent grids are connected by using directed edges, each directed edge is given a weight, and the weight represents a passing factor of the motorcade from the starting point of the directed edge to the ending point of the directed edge.
4. The grid technology-based space search and rescue ground team placement method according to claim 3, wherein when the reflector is landed on a grid with the number of d i, the kth space search and rescue ground team starts from an initial time position P k, calculates a shortest time t ki required for a time-consuming optimal path to reach a grid d i, and specifically comprises:
When the returning device is landed on the grid with the number of d i, the k-th space search and rescue ground team starts from the initial time position P k, the passing factor from the two adjacent grids m to the grid n which possibly pass through is gamma mn, the speed V mn＝Vmaxγmn and the maximum speed V max of the team between the two grids are provided, and the passing time from the grid m to the grid n is provided Wherein l mn is the distance from grid m to the center point of grid n;
After the travel time of the kth space search and rescue ground team among grids is obtained, calculating an optimal path between the team and the reflector landing grid and a corresponding required shortest time t ki by using a Dijkstra algorithm in graph theory.
5. The method for arranging the space search and rescue ground teams according to claim 4, wherein the method for solving the optimization problem by adopting a simulated annealing algorithm and outputting the standby grid number of each space search and rescue ground teams comprises the following steps:
Step S1), the optimization objective function of the search and rescue cloth potential problem is recorded as S represents a distribution scheme, wherein the scheme gives grid numbers of all spaceflight search and rescue ground teams at the initial moment;
Step S2), setting an initial annealing temperature T, a fire stopping temperature T f and the number of internal circulation times N, and selecting one of the feasible distribution schemes as a scheme initial value S;
Step S3), setting the iteration times l to 0;
step S4) randomly generating a new set of gesture schemes S';
Step S5) calculates an annealing temperature difference delta t=t (S ') -T (S), judges whether delta T <0 is true, if so, receives S ' as the current optimal solution, and makes S equal to S ', and enters step S6), otherwise, receives S ' as the current optimal solution with the probability of exp (-delta T/T), makes S equal to S ', and enters step S6);
step S6), adding 1 to the value of l, judging whether l is smaller than N, if yes, turning to step S4), otherwise, turning to step S7);
Step S7) if the current temperature T is smaller than the fire stopping temperature T f, turning to step S3), otherwise, turning to step S8);
Step S8) updating T by using a temperature strictly less than T to enable T to trend to 0, when T is greater than the fire stopping temperature T f, turning to step S3), otherwise, turning to step S9);
Step S9) outputs S as the final gesture scheme.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010639323.0A CN113901630B (en) | 2020-07-06 | 2020-07-06 | A method of deploying ground teams for space search and rescue based on grid technology |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010639323.0A CN113901630B (en) | 2020-07-06 | 2020-07-06 | A method of deploying ground teams for space search and rescue based on grid technology |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN113901630A CN113901630A (en) | 2022-01-07 |
| CN113901630B true CN113901630B (en) | 2024-12-31 |
Family
ID=79186530
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202010639323.0A Active CN113901630B (en) | 2020-07-06 | 2020-07-06 | A method of deploying ground teams for space search and rescue based on grid technology |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN113901630B (en) |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6678395B2 (en) * | 2001-03-22 | 2004-01-13 | Robert N. Yonover | Video search and rescue device |
| EP1563348A2 (en) * | 2002-08-21 | 2005-08-17 | Neal E. Solomon | Systems, methods and apparatus for organizing groups of self-configurable mobile robotic agents in a multi-robotic system |
-
2020
- 2020-07-06 CN CN202010639323.0A patent/CN113901630B/en active Active
Also Published As
| Publication number | Publication date |
|---|---|
| CN113901630A (en) | 2022-01-07 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN106815443B (en) | Towards the three-dimensional more batches of Multiple routes planning methods of hedgehopping device of changing environment | |
| US7194353B1 (en) | Method and system for route planning of aircraft using rule-based expert system and threat assessment | |
| Ma et al. | Adaptive path planning method for UAVs in complex environments | |
| CN106979784A (en) | Non-linear track planning based on hybrid pigeon swarm algorithm | |
| US20130124089A1 (en) | Spatiotemporal survivability data compression using objective oriented constraints | |
| CN106873599A (en) | Unmanned bicycle paths planning method based on ant group algorithm and polar coordinate transform | |
| CN102929285A (en) | Multi-target distribution and flight path planning method for multiple rescue helicopters | |
| CN115795697B (en) | Method for generating field maneuvering channel under complex environment based on space grid | |
| Stodola et al. | Model of optimal maneuver used in tactical decision support system | |
| CN108762296A (en) | A kind of unmanned plane deception route planning method based on ant group algorithm | |
| Shan | Study on submarine path planning based on modified ant colony optimization algorithm | |
| Nohel | Possibilities of raster mathematical algorithmic models utilization as an information support of military decision making process | |
| CN109583628A (en) | A kind of flood personnel's dynamic evacuation path analysis method based on cellular automata | |
| CN117850471A (en) | Multi-agent collaborative trajectory planning method and planning system considering radar threats in three-dimensional environment | |
| CN119830712A (en) | Chemical industry park emergency treatment method based on digital twinning | |
| CN109870906A (en) | A path planning method for high-speed rotorcraft based on BBO optimized artificial potential field | |
| Nohel et al. | Possibilities of modelling the coordinated maneuver of units in difficult terrain conditions | |
| CN113901630B (en) | A method of deploying ground teams for space search and rescue based on grid technology | |
| Talhofer et al. | TOWARDS: EFFICIENT USE OF RESOURCES IN MILITARY: METHODS FOR EVALUATION ROUTES IN OPEN TERRAIN. | |
| Talhofer et al. | Verification of digital analytical models: Case study of the cross-country movement | |
| Nohel et al. | Utilizing the maneuver control system CZ in the course of wargaming modelling and simulation | |
| CN113268900A (en) | Battle task-oriented airborne field site selection method and device | |
| Najgebauer et al. | The automation of combat decision processes in the simulation based operational training support system | |
| Fett | Aircraft route optimization using the A-STAR algorithm | |
| Kozůbek et al. | Military factors influencing path planning |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |