METHOD AND APPARATUS FOR DETECTING UNMANNED AERIAL VEHICLE CONFLICT BASED ON AIRSPACE DIGITAL RASTER, AND STORAGE MEDIUM

Abstract

The present invention provides a method and an apparatus for detecting unmanned aerial vehicle conflict based on an airspace digital raster, and a storage medium, wherein the method comprises: establishing an airspace discrete subdivision raster model; constructing a conversion relationship between a raster code rule and longitude and latitude coordinates and grid codes; establishing an unmanned aerial vehicle safety protection area, and performing gridding expression on the unmanned aerial vehicle in the airspace; establishing a coordinate system to convert the grid codes of the unmanned aerial vehicle into coordinates; calculating the Minkowski difference set of two blocks using the GJK algorithm; and determining whether the unmanned aerial vehicle conflicts or not according to the Minkowski difference set. Through combining an airspace raster code and the GJK algorithm, compare with traditional coordinate operation in pairs, the present invention can effectively reduce the complexity of conflict detection, save a lot of calculation time, and effectively improve the efficiency of detecting unmanned aerial vehicle conflict to meet the rapid and real-time conflict detection requirements of unmanned aerial vehicles in the airspace.

Claims

1. A method for detecting unmanned aerial vehicle conflict based on an airspace digital raster, comprising the following steps: establishing an airspace discrete subdivision raster model; constructing a conversion relationship between a raster code rule and longitude and latitude coordinates and grid codes; establishing an unmanned aerial vehicle safety protection area, and performing gridding expression on the unmanned aerial vehicle in the airspace; establishing a coordinate system to convert the grid codes of the unmanned aerial vehicle into coordinates; calculating the Minkowski difference set of two blocks using the GJK distance algorithm; and determining whether the unmanned aerial vehicle conflicts or not according to the Minkowski difference set.

2. The method according to claim 1, wherein the establishing an airspace discrete subdivision raster model comprises the following steps: step 1: expanding the latitude and longitude space of the earth three times, namely expanding a geographic space into 512 east-west and 512 north-south, expanding 1 to 64, and expanding 1 to 64; step 2: performing spherical recursive grid division based on the longitude and latitude of the geographic space, performing subdivision on a plane into three levels of degree, minute, and second level by level, dividing the earth spherical surface into 8-level recursive grids, and dividing into blocks with a minimum side length of 1; and step 3: performing altitude expression according to different altitude reference surfaces with the altitude being independent of spherical surface division, and performing upward expansion by taking X.sub.1 as granularity.

3. The method according to claim 2, wherein the constructing a conversion relationship between a raster code rule and longitude and latitude coordinates and grid codes comprises: dividing the code into a plane code and an altitude code, wherein the plane code and the altitude code all adopt a Z-shaped code, degree-level block code is represented by d, minute-level block code is represented by m, and second-level block code is represented by s, and combining the plane code and the altitude code to form the three-dimensional code of an airspace grid system.

4. The method according to claim 3, wherein the establishing an unmanned aerial vehicle safety protection area comprises: establishing the unmanned aerial vehicle safety protection area according to the operation performance of the unmanned aerial vehicle, wherein a horizontal interval and a longitudinal interval of the protection area is D.sub.hor, and a vertical interval is D.sub.ver, and selecting a grid with proper granularity according to a size of the protection area.

5. The method according to claim 4, wherein the performing gridding expression on the unmanned aerial vehicle in the airspace comprises: firstly, representing the unmanned aerial vehicle by only one cube, wherein Point represents cube information, and establishing the following point object expression model: $\mathrm{Point}=\left(,,h\right)=V_{\mathrm{layer}=n,\left(,,h\right)};$ wherein , , h represent the latitude, longitude and altitude of a location where the point object is located, respectively; V.sub.layer=n,(,,h) represents a block with subdivision level of n at the latitude and longitude altitude where , , h is located; Code.sub.layer=n,(,,h) represents the point object; then using continuous cubes to represent a path of the unmanned aerial vehicle, wherein Line represents a flight trajectory of the unmanned aerial vehicle, and establishing the following line object expression model: $\mathrm{Line}=\left(,,h\right)=V_{\mathrm{layer}=n,\left(,,h\right)};$ wherein when the unmanned aerial vehicle or an obstacle object cannot be represented by one cube, more than two small grids that are stacked are used to represent an irregular-shaped object, Space represents an object formed by stacking more than two cubes, and the following body object expression model is established: $\mathrm{Space}=\left(,,h\right)=V_{\mathrm{layer}=n,\left(,,h\right)}$ aiming at the current unmanned aerial vehicle detection object, performing code conversion on the flight latitude and longitude and the altitude information acquired from an airborne ADS-B equipment or a ground station, wherein the formula is as follows: ${\mathrm{Code}}_{\mathrm{Lon}}=\{\begin{array}{cc}{\mathrm{Lon}}_d/{\mathrm{gridsize}}_n,& \begin{array}{ccc}1& n& 2\end{array}\\ \left(\begin{array}{ccc}{\mathrm{Lon}}_d& 64& {\mathrm{Lon}}_m\end{array}\right)/{\mathrm{gridsize}}_n,& \begin{array}{ccc}3& n& 5\end{array}\\ \left(\begin{array}{ccccc}{\mathrm{Lon}}_d& 64& 64+{\mathrm{Lon}}_m& 64& {\mathrm{Lon}}_s\end{array}\right)/{\mathrm{gridsize}}_n,& \begin{array}{ccc}6& n& 8\end{array}\end{array}$ ${\mathrm{Code}}_{\mathrm{Lat}}=\{\begin{array}{cc}{\mathrm{Lat}}_d/{\mathrm{gridsize}}_n,& \begin{array}{ccc}1& n& 2\end{array}\\ \left(\begin{array}{ccc}{\mathrm{Lat}}_d& 64& {\mathrm{Lat}}_m\end{array}\right)/{\mathrm{gridsize}}_n,& \begin{array}{ccc}3& n& 5\end{array}\\ \left(\begin{array}{ccccc}{\mathrm{Lat}}_d& 64& 64+{\mathrm{Lat}}_m& 64& {\mathrm{Lat}}_s\end{array}\right)/{\mathrm{gridsize}}_n,& \begin{array}{ccc}6& n& 8\end{array}\end{array}$ ${\mathrm{Code}}_{\mathrm{Alt}}=\mathrm{Alt}/x_1$ wherein Code.sub.Lon, Code.sub.Lat, and Code.sub.Alt represent longitude code, latitude code, and altitude code, respectively, n represents code level, gridsize.sub.n represents a size of granularity of the grid at the n.sup.th level, Lon.sub.d, Lon.sub.m, and Lon.sub.s represent degree, minute, and second in longitude coordinates, respectively, and altitude level extends a separate code for the granularity according to x.sub.1.

6. The method according to claim 5, wherein the establishing a coordinate system to convert the grid codes of the unmanned aerial vehicle into coordinates comprises: after gridding expression is performed on the unmanned aerial vehicle in the airspace, placing the unmanned aerial vehicle and a track point thereof in a grid coordinate system, and converting the longitude and latitude coordinates into Cartesian coordinate integer operation.

7. The method according to claim 6, wherein the calculating the Minkowski difference set of two blocks using the GJK algorithm comprises: calculating a distance between two convexities by using the GJK algorithm, wherein a distance between object A and object B is represented by d(A, B), and is expressed by the following formula: $d\left(A,B\right)=\min \left\{.Math.x-y.Math.:xA,yB\right\};$ wherein x and y represent a point in the object A and a point in the object B, respectively; two points aA and bB with the shortest distance between the object A and the object B meet ab=d(A, B); the Minkowski difference set is a set of points formed by the difference between all points of the object A and all points of the object B, and is represented as follows: $M\left(A,B\right)=\left\{x-y:xA,yB\right\};$ M(A, B) represents the Minkowski difference set of cube A and cube B; the distance between object A and object B is represented by the Minkowski difference set and is described as follows: $d\left(A,B\right)=\min .Math.M\left(A,B\right).Math.=\min \left\{.Math.x-y.Math.:xA,yB\right\}.$

8. The method according to claim 7, wherein the determining whether the unmanned aerial vehicle conflicts or not according to the Minkowski difference set comprises: converting a distance between unmanned aerial vehicles into a Minkowski difference between the unmanned aerial vehicles, and determining whether two objects collide or not by determining whether a difference set contains an origin point or not.

9. An apparatus for detecting unmanned aerial vehicle conflict based on an airspace digital raster, comprising: an airspace discrete subdivision raster model establishment module configured to establish an airspace discrete subdivision raster model; a conversion relationship construction module configured to construct a conversion relationship between a raster code rule and longitude and latitude coordinates and grid codes; a gridding expression module configured to establish an unmanned aerial vehicle safety protection area, and perform gridding expression on the unmanned aerial vehicle in the airspace; a coordinate conversion module configured to establish a coordinate system to convert the grid codes of the unmanned aerial vehicle into coordinates; a Minkowski difference set calculation module configured to calculate the Minkowski difference set of two blocks using the GJK distance algorithm; and an unmanned aerial vehicle conflict determination module configured to determine whether the unmanned aerial vehicle conflicts or not according to the Minkowski difference set.

10. A storage medium, wherein the storage medium stores a computer program or instructions, and when the computer program or the instructions are executed, the method according to any one of claims 1 to 8 is implemented.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0047] The present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments, and the advantages of the above and/or other aspects of the present invention will become more apparent.

[0048] FIG. 1 is a flowchart of a method for detecting unmanned aerial vehicle conflict based on an airspace digital raster according to the present invention.

[0049] FIG. 2 is a schematic diagram of grid expansion.

[0050] FIG. 3 is a schematic diagram of subdivision level division.

[0051] FIG. 4 is a schematic diagram of the Minkowski difference set distance conversion.

[0052] FIG. 5 is a schematic diagram of three unmanned aerial vehicles A, B, C of the same type represented as three 8.sup.th level grid-sized cubes.

[0053] FIG. 6 is a schematic diagram of the Minkowski difference results of A and B.

[0054] FIG. 7 is a schematic diagram of the Minkowski difference results of A and C.

[0055] FIG. 8 shows the comparison of conflict detection time.

DETAILED DESCRIPTION OF THE EMBODIMENTS

Embodiment

[0056] As shown in FIG. 1, the present invention provides a method for detecting unmanned aerial vehicle conflict based on an airspace digital raster. An air-traffic area division method based on the fuzzy C-means clustering comprises the following steps: [0057] S110: establishing an airspace discrete subdivision raster model; [0058] S120: constructing a conversion relationship between a raster code rule and longitude and latitude coordinates and grid codes; [0059] S130: establishing an unmanned aerial vehicle safety protection area, and performing gridding expression on the unmanned aerial vehicle in the airspace; [0060] S140: establishing a coordinate system to convert the grid codes of the unmanned aerial vehicle into coordinates; [0061] S150: calculating the Minkowski difference set of two blocks using the GJK algorithm, and [0062] S160: determining whether the unmanned aerial vehicle conflicts or not according to the Minkowski difference set.

[0063] In this embodiment, step S110 comprises: performing spherical surface subdivision and altitude subdivision on the earth, performing recursive grid division, analyzing the requirement of an airspace gridding method according to the operation characteristics of a low-altitude airspace, constructing a discretized gridding airspace and establishing the grid subdivision of a digital model. [0064] S111: expanding the latitude and longitude space of the earth three times, namely expanding a geographic space into 512 east-west and 512 north-south, expanding 1 to 64, and expanding 1 to 64, as shown in FIG. 2; [0065] S112: performing spherical recursive grid division based on the longitude and latitude of the geographic space, performing subdivision on a plane into three levels of degree, minute, and second level by level, dividing the earth spherical surface into 8-level recursive grids, and dividing into blocks with a minimum side length of 1, as shown in Table 1; and [0066] S113: performing altitude expression under conditions that the altitude is independent of spherical surface division, and can be divided into true altitude, surface pressure altitude, corrected sea level pressure altitude, and standard atmospheric pressure altitude according to different altitude reference surfaces, and performing upward expansion by taking 30 m as granularity.

[0067] In this embodiment, step S120 comprises the following steps: dividing the code into a plane code and an altitude code, wherein the plane code and the altitude code all adopt a Z-shaped code, degree-level block code is represented by d, minute-level block code is represented by m, and second-level block code is represented by s, and combining the plane code and the altitude code to form the three-dimensional code of an airspace grid system.

TABLE-US-00001 TABLE 1 Approximate scale Subdivision level Grid size around the equator First level 15 15 1669 km Second level 1 1 111 km Third level 30 30 56 km Fourth level 10 10 9 km Fifth level 1 1 1 km Sixth level 6 6 0.2 km Seventh level 3 3 0.1 km Eighth level 1 1 0.03 km

[0068] In this embodiment, the step S130 comprises the following steps: [0069] S131: Establishing the unmanned aerial vehicle safety protection area according to the operation performance of the unmanned aerial vehicle, wherein a horizontal interval and a longitudinal interval of the protection area is D.sub.hor or, and a vertical interval is D.sub.ver, and selecting a grid with proper granularity according to a size of the protection area. [0070] S132: Establishing a point object expression model:

Point=(,,h)=V.sub.laver=n,(,,h), [0071] wherein (, , h) represent the latitude, longitude and altitude of a location where the point object is located, respectively; V.sub.layer=n,(,,h) represents a block with subdivision level of n at the latitude and longitude altitude, as shown in FIG. 3. According to the classification standards of unmanned aerial vehicles, general civilian consumer unmanned aerial vehicles belong to micro unmanned aerial vehicles, corresponding to the 8.sup.th level grid granularity. The 6.sup.th and 7.sup.th level grids correspond to the sizes of medium and small unmanned aerial vehicles, respectively. Therefore, the 6.sup.th, 7.sup.th, and 8.sup.th level grids can represent the vast majority of unmanned aerial vehicles. If some unmanned aerial vehicles have special sizes and cannot be directly represented by one grid, a plurality of grids can be used for combined expression.

[0072] In the process of computer storage and operation, Code.sub.layer=n,(,,h) represents a point object; [0073] S133: establishing a line object expression model:

Line=(,,h)=V.sub.layer=n,(,,h); [0074] S134: establishing a body object expression model:

Space=(,,h)=V.sub.layer=n,(,,h).

[0075] Aiming at the current unmanned aerial vehicle detection object, performing code conversion on the flight latitude and longitude and the altitude information acquired from an airborne ADS-B equipment or a ground station, wherein the formula is as follows:

[00004]${\mathrm{Code}}_{\mathrm{Lon}}=\{\begin{array}{cc}{\mathrm{Lon}}_d/{\mathrm{gridsize}}_n,& \begin{array}{ccc}1& n& 2\end{array}\\ \left(\begin{array}{ccc}{\mathrm{Lon}}_d& 64& {\mathrm{Lon}}_m\end{array}\right)/{\mathrm{gridsize}}_n,& \begin{array}{ccc}3& n& 5\end{array}\\ \left(\begin{array}{ccccc}{\mathrm{Lon}}_d& 64& 64+{\mathrm{Lon}}_m& 64& {\mathrm{Lon}}_s\end{array}\right)/{\mathrm{gridsize}}_n,& \begin{array}{ccc}6& n& 8\end{array}\end{array}$${\mathrm{Code}}_{\mathrm{Lat}}=\{\begin{array}{cc}{\mathrm{Lat}}_d/{\mathrm{gridsize}}_n,& \begin{array}{ccc}1& n& 2\end{array}\\ \left(\begin{array}{ccc}{\mathrm{Lat}}_d& 64& {\mathrm{Lat}}_m\end{array}\right)/{\mathrm{gridsize}}_n,& \begin{array}{ccc}3& n& 5\end{array}\\ \left(\begin{array}{ccccc}{\mathrm{Lat}}_d& 64& 64+{\mathrm{Lat}}_m& 64& {\mathrm{Lat}}_s\end{array}\right)/{\mathrm{gridsize}}_n,& \begin{array}{ccc}6& n& 8\end{array}\end{array}$${\mathrm{Code}}_{\mathrm{Alt}}=\mathrm{Alt}/x_1$ [0076] wherein Code.sub.Lon, Code.sub.Lat, and Code.sub.Alt represent longitude code, latitude code, and altitude code, respectively, n represents code level, gridsize.sub.n represents a size of granularity of the grid at the n.sup.th level, Lon.sub.d, Lon.sub.m, and Lon.sub.s represent degree, minute, and second in longitude coordinates, respectively, and altitude level extends a separate code for the granularity according to x.sub.1.

[0077] In this embodiment, the step S140 comprises: after the airspace is subjected to gridding expression, placing the unmanned aerial vehicle and a track point thereof in a grid coordinate system, and converting the longitude and latitude coordinates into Cartesian coordinate integer operation.

[0078] In this embodiment, the step S150 comprises: [0079] S151: calculating a distance between two convexities by using the GJK algorithm, wherein a distance between object A and object B is represented by d(A, B), and is expressed by the following formula:

[00005]$d\left(A,B\right)=\min \left\{.Math.x-y.Math.:xA,yB\right\}$ [0080] two points aA and bB with the shortest distance between the object A and the object B meet ab=d(A, B); [0081] S152: the Minkowski difference set is a set of points formed by the difference between all points of the object A and all points of the object B, and can be represented as follows:

[00006]$M\left(A,B\right)=\left\{x-y:xA,yB\right\};$ [0082] S153: the distance between objects A and B can be represented by the Minkowski difference set, as shown in FIG. 4, and is described as follows:

[00007]$d\left(A,B\right)=\min .Math.M\left(A,B\right).Math.=\min \left\{.Math.x-y.Math.:xA,yB\right\}.$

[0083] In this embodiment, the step S160 comprises: converting a distance between unmanned aerial vehicles into a Minkowski difference between the unmanned aerial vehicles, and determining whether two objects collide or not by determining whether a difference set contains an origin point or not, wherein a distance between two unmanned aerial vehicles is greater, then the central point of difference set is farther away from the origin point, otherwise, the central point of difference set is closer to the origin point. If the unmanned aerial vehicle blocks collide, the difference set polygon will contain the origin point. The unmanned aerial vehicles A and B collide if and only if the Minkowski difference set M(A, B) of the two cubes contains the origin point. Three unmanned aerial vehicles A, B, C of the same type are expressed as three 8.sup.th level grid sized cubes, as shown in FIG. 5, wherein A is in contact with B, and C is far away from A and B; the number of algorithm iterations is set to 5000, so the resulting the Minkowski difference set contains 5000 points, these element points are displayed in coordinates, and the Minkowski difference results for A and B, and A and C are shown in FIGS. 6 and 7, which intuitively shows the relationship between the Minkowski difference set and the origin point. As shown in FIG. 6, the origin point is located inside the Minkowski difference set generated by cubes A and B, and the origin point is located inside the difference set, indicating that the two conflict; however, if there is no conflict between cubes A and C, the origin point is located outside the Minkowski difference set between A and C, as shown in FIG. 7. The conflict detection time of the method of the present invention is analyzed, three unmanned aerial vehicles with different sizes are used, the 6.sup.th, 7.sup.th and 8.sup.th level grid granularity are used as the cube representation of the three unmanned aerial vehicles with different types, 20 unmanned aerial vehicles including 3 medium unmanned aerial vehicles, 3 small unmanned aerial vehicles and 14 micro unmanned aerial vehicles are selected in the experiment, the 8.sup.th level code is also used to generate the 1 km 1 km 0.6 km gridding airspace environment for the experiment, the average conflict detection time of two algorithms in a period of time is recorded, and the result is shown in FIG. 8. With the increase in the number of the unmanned aerial vehicles, the conflict detection time of the Euclidean distance conflict detection method for calculating the distance between the unmanned aerial vehicles in pairs under the traditional three-dimensional coordinate system increases approximately exponentially, the conflict detection method based on GJK increases linearly with a low increase trend, which shows the high efficiency of the method.

[0084] This embodiment further provides an apparatus for detecting unmanned aerial vehicle conflict based on an airspace digital raster, which comprises: [0085] an airspace discrete subdivision raster model establishment module configured to establish an airspace discrete subdivision raster model; [0086] a conversion relationship construction module configured to construct a conversion relationship between a raster code rule and longitude and latitude coordinates and grid codes; [0087] a gridding expression module configured to establish an unmanned aerial vehicle safety protection area, and perform gridding expression on the unmanned aerial vehicle in the airspace; [0088] a coordinate conversion module configured to establish a coordinate system to convert the grid codes of the unmanned aerial vehicle into coordinates; [0089] a Minkowski difference set calculation module configured to calculate the Minkowski difference set of two blocks using the GJK distance algorithm; and [0090] an unmanned aerial vehicle conflict determination module configured to determine whether the unmanned aerial vehicle conflicts or not according to the Minkowski difference set.

[0091] This embodiment further provides a storage medium, wherein the storage medium stores a computer program or instructions, and when the computer program or the instructions are executed, the method for detecting unmanned aerial vehicle conflict based on the airspace digital raster is implemented.

[0092] As described above, the apparatus according to the embodiment of the present application may be implemented in various terminal devices, such as a server of a distributed computing system. In one example, the apparatus according to the embodiment of the present application may be integrated into the terminal device as a software module and/or a hardware module. For example, the apparatus may be a software module in an operating system of the terminal device, or may be an application developed for the terminal device; of course, the apparatus may also be one of many hardware modules of the terminal device.

[0093] Alternatively, in another example, the apparatus and the terminal device may be separate terminal devices, and the apparatus may be connected to the terminal device through a wired and/or wireless network and transmit the interaction information according to an agreed data format.

[0094] In summary, the present invention provides a method for detecting unmanned aerial vehicle conflict based on an airspace digital raster, which comprises: establishing an airspace discrete subdivision raster model; constructing a conversion relationship between a raster code rule and longitude and latitude coordinates and grid codes; establishing an unmanned aerial vehicle safety protection area, and performing gridding expression on the unmanned aerial vehicle in the airspace; establishing a coordinate system to convert the grid codes of the unmanned aerial vehicle into coordinates; calculating the Minkowski difference set of two blocks using the GJK algorithm; and determining whether the unmanned aerial vehicle conflicts or not according to the Minkowski difference set. Through combining an airspace raster code and the GJK algorithm, compare with traditional coordinate operation in pairs, the present invention can effectively reduce the complexity of conflict detection, save a lot of calculation time, and effectively improve the efficiency of detecting unmanned aerial vehicle conflict to meet the rapid and real-time conflict detection requirements of unmanned aerial vehicles in the airspace.

[0095] The present invention provides a method and an apparatus for detecting unmanned aerial vehicle conflict based on an airspace digital raster, and a storage medium, and the technical solution is specifically implemented in many methods and approaches. The above descriptions are only preferred examples of the present invention. It should be noted that those of ordinary skill in the art can also make several improvements and modifications without departing from the principle of the present invention, and such improvements and modifications shall fall within the protection scope of the present invention. All components not specified in this embodiment can be implemented by the prior art.