CN111811529A - A multi-region vehicle-machine cooperative reconnaissance path planning method and system - Google Patents

Abstract

Embodiments of the present invention provide a method and system for planning a multi-area vehicle-machine cooperative reconnaissance path. The method includes: determining a candidate scanning path of an unmanned aerial vehicle according to a geometric feature of a reconnaissance area; , Based on the saving algorithm, determine the driving path of the car and the flying point and recovery point of the drone in each area; use the local search algorithm to improve the determined driving path of the car and the flying point and recovery point of the drone in each area , to determine the vehicle-machine cooperative reconnaissance path. According to the technical solution, the car is used as the mobile platform of the UAV, and the UAV is carried to complete the scanning and reconnaissance tasks in multiple areas.

Description

A multi-region vehicle-machine cooperative reconnaissance path planning method and system

technical field

The invention relates to a multi-area vehicle-machine cooperative reconnaissance path planning method and system.

Background technique

In modern warfare, unmanned aircraft has the advantages of low cost, strong survivability, no risk of loss of personnel, and good maneuverability. tool.

UAV battlefield reconnaissance is an activity that uses UAVs to obtain battlefield information, and path planning is the key supporting technology for UAVs to perform reconnaissance tasks. In the current UAV area coverage research, most of them study how UAVs can cover an area. By planning the UAV flight path, the coverage scanning of the entire area can be completed at the lowest cost possible. In many cases, multiple battlefield areas need to be scanned and reconnaissance. When multiple areas are scattered in different positions on a large-scale battlefield, the low endurance of small UAVs becomes a key constraint factor for the completion of the mission.

In order to expand the scope of small UAVs to perform reconnaissance tasks to complete multi-area coverage reconnaissance tasks, this paper introduces vehicles as the mobile platform of UAVs, carrying UAVs for large-scale maneuvers on the battlefield, and constructs a vehicle-machine coordinated battlefield reconnaissance system. As the UAV's command and support platform, the car carries the UAV from one reconnaissance area to another reconnaissance area, and charges or replaces the battery of the UAV during the maneuver. When the car carries the drone to the vicinity of a target reconnaissance area, the drone takes off from the car, flies over the reconnaissance area, completes the coverage reconnaissance of the area, and returns to the car. The combination of cars and UAVs can effectively expand the mission range of small UAVs and improve the efficiency of multi-area reconnaissance on the battlefield. Automotive and small UAV collaborative systems have significant advantages in performing tasks in a variety of military and civilian domains.

The current research on vehicle-machine cooperative path planning mainly focuses on the access sequence and flight path of UAVs to point targets. The path planning of vehicle-machine coordinated multi-area reconnaissance faces more new research challenges. There are two layers of paths in the problem, in which the flight path of the drone in the air and the driving path of the car on the ground road network are connected to each other at different nodes. Due to the differences in speed, endurance and driving patterns between vehicles and drones, the interaction of the two paths needs to be considered in the planning process. The interaction of this two-layer path makes the solution space of the problem more complex and more difficult to solve than the traditional path problem.

SUMMARY OF THE INVENTION

Embodiments of the present invention provide a multi-area vehicle-machine cooperative reconnaissance path planning method and system, where a vehicle acts as a mobile platform for an unmanned aerial vehicle, and carries the unmanned aerial vehicle to complete scanning and reconnaissance tasks in multiple areas.

In order to achieve the above object, on the one hand, an embodiment of the present invention provides a multi-region vehicle-machine cooperative reconnaissance path planning method, the method includes:

According to the geometric features of the reconnaissance area, determine the candidate scanning path of the UAV;

Based on the candidate scanning path of the UAV, based on the saving algorithm, determine the driving path of the car and the flying point and recovery point of the UAV in each area;

The local search algorithm is used to improve the determined driving path of the car and the launch point and recovery point of the UAV in each area, and determine the cooperative reconnaissance path of the vehicle and the machine.

On the other hand, an embodiment of the present invention provides a multi-region vehicle-machine cooperative reconnaissance path planning system, the system includes:

Scanning path determination unit: used to determine the candidate scanning path of the UAV according to the geometric characteristics of the reconnaissance area;

Initial vehicle path unit: It is used to determine the driving path of the car and the flying point and recovery point of the UAV in each area based on the candidate scanning path of the UAV and based on the saving algorithm;

Vehicle-Machine Collaborative Reconnaissance Path Determination Unit: It is used to improve the determined vehicle's driving path and the UAV's launch point and recovery point in each area by using a local search algorithm to determine the vehicle-machine collaborative reconnaissance path.

The above technical solution has the following beneficial effects: the technical solution proposes a new mode in which the vehicle and the machine cooperate to complete the multi-area coverage reconnaissance task for the application of the small unmanned aerial vehicle in the reconnaissance of the battlefield area, and the vehicle acts as the mobile platform of the unmanned aerial vehicle, Carry drones to complete scanning and reconnaissance missions in multiple areas.

Description of drawings

In order to explain the embodiments of the present invention or the technical solutions in the prior art more clearly, the following briefly introduces the accompanying drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only These are some embodiments of the present invention. For those of ordinary skill in the art, other drawings can also be obtained according to these drawings without creative efforts.

FIG. 1 is an exemplary diagram of a path for reconnaissance of three areas by vehicle-machine cooperation according to an embodiment of the present invention;

2 is a flowchart of a method for planning a multi-area vehicle-machine cooperative reconnaissance path according to an embodiment of the present invention;

3 is a schematic diagram of a scanning path in a helical scanning mode and a mowing scanning mode in an embodiment of the present invention;

4a is a schematic diagram of a concave polygon to be decomposed in an embodiment of the present invention;

4b is a schematic diagram of decomposing a concave polygonal trapezoid into a plurality of convex polygons in an embodiment of the present invention;

4c is a schematic diagram of merging adjacent convex polygons in an embodiment of the present invention;

4d is a schematic diagram of a Boustrophedon path generated by using a mowing scanning mode in an embodiment of the present invention;

5 is a schematic structural diagram of a multi-region vehicle-machine cooperative reconnaissance path planning system according to an embodiment of the present invention;

Fig. 6 is the reconnaissance area and road network distribution diagram in the test case of the present invention;

FIG. 7 is a schematic diagram of the vehicle-machine cooperative reconnaissance path in the test case of the present invention.

Detailed ways

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only a part of the embodiments of the present invention, rather than all the embodiments. Based on the embodiments in the present invention, all other embodiments obtained by those of ordinary skill in the art without creative work fall within the protection scope of the present invention.

When the vehicle and the machine cooperate to complete the coverage reconnaissance task of multiple areas, the information such as the location and shape of the road network and the reconnaissance area are known. As a mobile platform for small UAVs, the car can charge and replace the battery of the UAV during driving, and is also the command center of the UAV. The endurance of the car is enough to carry the UAV to complete the entire reconnaissance mission, but the endurance of the UAV is limited, and it can complete the coverage reconnaissance of one area. When reconnaissance in different areas, it is necessary to charge or replace the battery. In the process of multi-area coverage reconnaissance with vehicle-machine coordination, a car carries a small drone from the base. When it travels near the area where reconnaissance is required, the drone is released, and the drone flies over the reconnaissance area for full coverage. Scan and collect information; after the drone completes the coverage scan of the target area, it returns to the car, and the car carries the drone to the next reconnaissance area, and completes the charging of the drone or replaces the battery during the driving process; this cycle , the car carries the drone to maneuver on the battlefield, and returns to the base after completing the reconnaissance of all target areas. The car can only fly and recover the drone at some specific points (called temporary stops) near the reconnaissance area. After the drone is released, the car can wait to recover the drone on the spot, or drive to other temporary stops to recover it. drone.

Figure 1 shows an example of vehicle-machine cooperative reconnaissance of three areas. It can be seen that in the process of vehicle-machine cooperative reconnaissance, the car can only drive on the ground road network, and its path planning for accessing all reconnaissance areas is a typical traveling salesman problem; the drone starts from the car and flies over the reconnaissance area. The continuous coverage scanning of the area is a typical UAV trajectory planning problem. At the same time, the path of the car needs to be closely coordinated with the path of the UAV, and the reconnaissance of all areas can be quickly completed under the constraints of the endurance capacity of the UAV. How to optimize the path of the vehicle and the UAV so that the coverage of all areas can be completed in the shortest time without exceeding the maximum endurance of the UAV, which is more efficient than simply solving the traveling salesman problem and the UAV trajectory planning problem. It is complex and needs to consider the interaction of the two types of paths.

For the convenience of model description, Table 1 gives all the symbols applied in the modeling process and their meanings.

Table 1: Symbols and their meanings

The mathematical programming model is as follows:

Min

The objective function (1) minimizes the total time to complete all area reconnaissance, where the first part is the total travel time for the car-borne UAV to transfer between all coverage areas and base stations, and the second part is the vehicle-borne UAV in Total flight time for coverage scans across all reconnaissance areas. In order to reduce the time of the first part, one of the criteria for choosing stops around different scouting areas is to choose stops with a smaller Floyd distance from each other. In order to reduce the time of the second part, on the one hand, the stops with a small Floyd distance between each other are selected in the same area; on the other hand, appropriate temporary stops are selected to make the total flight distance of the UAV shorter.

Constraint (2) ensures that the vehicle-mounted UAV must start from the base station and return to the same base station after completing all coverage tasks. Constraint (3) ensures that the out-degree of each temporary stop is equal to the in-degree, thereby ensuring the connectivity of vehicle travel routes. Constraint (4) ensures that the vehicle enters each reconnaissance area once and leaves the area once, that is, each reconnaissance area can only be visited once. Constraint (5) ensures that the UAV can only take off at the temporary stops visited by the vehicle, while Constraint (6) ensures that the UAV can only land at the temporary stops visited by the vehicle. Constraint (7) ensures that the UAV can only take off and land once in each reconnaissance area. Constraint (8) ensures the connectivity of the UAV flight path in each reconnaissance area, and together with constraint (7) ensures that only one full coverage scan is performed in each reconnaissance area. Constraint (9) ensures that the drone's flight time does not exceed its maximum endurance while scanning each reconnaissance area. Constraints (10) and (11) define the value range of the 0-1 variable.

Here, a three-stage heuristic algorithm is proposed to quickly solve the vehicle-machine cooperative multi-area coverage reconnaissance path planning problem. The first stage is to analyze the geometric features of the reconnaissance area, and calculate the coverage scanning path of the UAV; The launch and recovery points of each area; in the third stage, the local search algorithm is used to improve the feasible solution constructed in the second stage, and the optimal solution or approximate optimal solution of the problem is obtained.

表示从点i到点j的Floyd距离，由Floyd算法计算得出。Floyd算法(也称为插值方法)是一种使用动态编程的思想在给定加权图中找到多个点之间最短路径的算法，与Dijkstra的算法相似。Floyd算法的主要过程如下。As the basic input of the three-stage heuristic algorithm, the Floyd distance between any two points needs to be calculated first. make

Represents the Floyd distance from point i to point j, calculated by the Floyd algorithm. Floyd's algorithm (also called interpolation method) is an algorithm that uses the idea of dynamic programming to find the shortest path between multiple points in a given weighted graph, similar to Dijkstra's algorithm. The main process of Floyd's algorithm is as follows.

As shown in Figure 1, it is a flow chart of a multi-area vehicle-machine cooperative reconnaissance path planning method according to an embodiment of the present invention, and the method includes:

S101: Determine the candidate scanning path of the UAV according to the geometric features of the reconnaissance area;

Preferably, according to the geometric features of the reconnaissance area, the candidate scanning path of the UAV is determined, including:

According to the geometric shape of the reconnaissance area, if the circularity of the geometric shape of the reconnaissance area is greater than the set threshold, it is determined that the scanning mode of the UAV reconnaissance is the helical scanning mode;

If the roundness of the geometric shape of the reconnaissance area is not greater than the set threshold, it is determined that the scanning mode of the drone reconnaissance is the mowing scanning mode;

According to the determined scanning mode, determine the candidate scanning path of the UAV and the initial launch point and final recovery point of the UAV.

Preferably, if the scanning mode of the drone reconnaissance is the mowing scanning mode, the concave-convexity of the geometry of the reconnaissance area is judged, and if the geometry of the reconnaissance area is a concave polygon, the reconnaissance area is decomposed for multiple convex polygons;

According to the decomposed convex polygons, the candidate scanning path of the UAV and the initial launch point and the final recovery point of the UAV are determined in the mowing scanning mode.

When the drone performs coverage scanning reconnaissance on an area, it is first necessary to analyze the shape of the reconnaissance area and select a suitable scanning mode for the drone, such as mowing scanning or helical scanning; if mowing scanning is selected, it is necessary to Further check the concavity and convexity of the reconnaissance area. When the area is a concave polygon, it should be decomposed into multiple convex polygon sub-areas; finally, the scanning flight path of the coverage area is calculated according to the relevant performance parameters of the UAV.

When using a drone to cover an area, there are mainly two scanning modes, namely the mowing scanning mode and the helical scanning mode. Figure 3 shows the flight path of the UAV in the two scanning modes. In Figure 3, the polygon surrounded by a rectangular frame represents the reconnaissance mission area, the dots represent the start and end points of the scanning path, the dashed trajectory represents the UAV's flight path, and the arrows represent the UAV's flight direction. The two scan modes are specifically defined as follows.

Helical scan mode: The drone starts at the center of the reconnaissance area and gradually scans outward at a constant helical spacing until the entire area is covered. You can also start from the outermost and scan inward.

Mowing scanning mode: The UAV scans at equal intervals from the edge of the reconnaissance area in a reciprocating manner in parallel tracks until the entire area is covered.

Most of the current studies use the mowing scanning mode [20, 21], a few use the helical scanning mode, and the selection optimization of multiple scanning modes has not been studied. In actual work, when different scanning modes are used in the same area, the total length of the scanning path may vary greatly. For example, in Figure 2, the flight path generated by the helical scan mode is significantly longer than the flight path generated using the mowing scan mode. However, when the scouting area is closer to a circle, the helical scan will work better than the mowing scan mode. Therefore, different scan modes can be selected depending on how close the coverage area is to the circle.

The roundness of a polygon is defined as follows:

where S is the area of the reconnaissance area and L is its perimeter. If the region is closer to a circle, its circularity C is closer to 1.

In order to analyze and compare the scanning efficiency of two typical scanning modes for polygonal areas with different roundness, Table 2 gives the scanning time of several typical polygons using two scanning modes respectively. All polygons in Table 2 have the same area, and the value is 84 square units. The scanning width of the UAV is set to 2 units and the speed is 1 unit. It can be seen from Table 2 that when the roundness of the polygon is small, the scanning time of the mowing scanning mode is significantly shorter than that of the helical scanning mode. As the roundness of the polygons gradually becomes larger, the gap between them becomes smaller and smaller. When the polygon is a regular pentagon (C=0.86), the scan time of the two scan modes is substantially the same. As the roundness of the polygon continues to increase, the time for the helical scan mode becomes shorter than the time for the mowing scan mode. Therefore, the following approximate rules can be summarized through experimental observation: when the circularity of the reconnaissance area is less than 0.86, the mowing scanning mode is better; when the circularity is greater than 0.86, the spiral scanning mode is better.

Table 2: Scan times obtained using two scan modes for typical polygons

2.1.2 Determination and decomposition of concave polygons

When the helical scan mode is used, the unevenness of the polygon has little effect on the scan time. However, when the mowing scanning mode is used, the unevenness of the polygon has a greater impact on it. The scan path generated using the mowing scan mode needs to be planned on the premise that the reconnaissance area is a convex polygon. When the scout area is a concave polygon, the concave polygon must be decomposed into a series of convex polygon sub-areas.

(1) Judgment of polygon concavo-convex

The cross product of vectors can be used to judge the concavity and convexity of a scout area. The determination principle is as follows: the vertices with the same turn are convex points, and each vertex of the convex polygon is a convex point; the vertices with different turns are concave points, if there is more than one concave point in the polygon, it must be a concave polygon. Assuming that a polygon P has n vertices (v ₁ , v ₂ , . . . , v _n ), the convexity of P is determined by whether or not P has concave points. Let v _i be a random vertex of P, and v _i-1 and v _i+1 be two adjacent vertices of v _i . The concavity of the vertex v _i is determined by the cross product of the vectors Q.

When all vertices of P are convex, the polygon is convex, otherwise P is concave.

(2) Decomposition of concave polygons

Scan paths generated using the mowing scan mode are often referred to as Boustrophedon paths. Decomposing a concave polygon into a series of convex polygon subregions and then planning Boustrophedon paths for each convex polygon is called Boustrophedon decomposition (BCD) [22]. Li et al. proposed an accurate BCD method based on trapezoidal decomposition with an algorithmic complexity of O(n). Extending the BCD method to an external cell decomposition method using the convex hull of concave polygons effectively reduces the number of decomposed convex polygons. In this paper, a BCD method based on trapezoidal decomposition is designed. Since the effect of decomposing concave polygons along different angles is different, in order to reduce the number of decomposed convex polygons and the number of turns of the UAV, the concave polygons are decomposed along the direction parallel to the long axis of the concave polygons.

For each edge of a convex polygon, calculate the distances from other vertices that do not belong to the edge to this edge. The maximum of these distances is marked as the span of that edge. Compare the spans of all edges, and the edge corresponding to the smallest span is called the long axis of the convex polygon. In order to find the long axis of the concave polygon, a convex hull of the concave polygon is firstly generated using the convex hull generation algorithm. A convex hull is the simplest convex polygon that contains all the vertices of a concave polygon. The algorithm is summarized as follows.

(1) Find the poles in all the vertices and delete all the points that fall inside the polygon formed by the poles, and divide the remaining points into 4 regions.

(2) For regions 1 and 2, sort the points in them in ascending order, and for regions 3 and 4, sort them in descending order.

(3) For each region, find a convex path from one pole to the other.

Then, consider the long axis of the convex hull as the long axis of the concave polygon. After decomposing the concave polygonal trapezoid into a series of convex polygons along the direction parallel to the long axis, a Boustrophedon path is generated for each convex polygon by using the mowing sweep mode.

Figure 4 shows an example of the decomposition of a concave polygon. The figure surrounded by solid lines in Figure 4(a) is the concave polygon to be decomposed, and after adding the dashed lines, it becomes a convex polygon, where the blue edge represents the long axis of the convex polygon and is also the long axis of the concave polygon. Figure 4(b) shows the trapezoidal decomposition of concave polygons along the direction parallel to its long axis, and Figure 4(c) shows the process of merging a series of convex polygons after trapezoidal decomposition. Two adjacent convex polygons can be merged when one of their sides coincides with each other and their major axes are parallel to each other. This process can effectively reduce the number of convex polygons and avoid unnecessary transfer of drones between different convex polygons. Figure 4(d) shows the Boustrophedon path generated using the mowing scan pattern.

Based on the UAV scanning mode selection and polygon area segmentation method, a flight path planning algorithm for UAV to cover and scan the reconnaissance area is designed. The overall process is shown in Algorithm 2. First, given the geometric information of the reconnaissance area, the position information of the potential temporary stop point, and the flying speed of the UAV, calculate the perimeter and area of the reconnaissance area (Line 1), and then calculate the circularity of the reconnaissance area (Line 1). 2 lines). If the circularity of the area is greater than 0.86, the helical scan mode is used, and the scan path (line 4) and the start and end points of the path (line 5) are obtained. The length of the scan path is calculated in line 6. If the roundness is less than 0.86, the mowing scan mode is used. In this case, the unevenness of the region is first checked (Line 9). If the region is a concave polygon (line 10), it is decomposed into a series of convex polygons using the BCD method designed in the previous section (line 11), and then the Boustrophedon path of the scout region is planned. Starting parallel to the long axis, there are two scan paths (Line 13), corresponding to two pairs of start and end points (Line 14). Calculate the length of the two paths (Lines 15-16).

S102: On the basis of the candidate scanning path of the UAV, based on the saving algorithm, determine the driving path of the car and the flying point and recovery point of the UAV in each area;

Preferably, on the basis of the candidate scanning path according to the unmanned aerial vehicle, based on the saving algorithm, determine the driving path of the car and the flying point and the recovery point of the unmanned aerial vehicle in each area, including:

By optimizing the order in which the car visits the reconnaissance area and selecting a temporary stop near each reconnaissance area, on the one hand, the UAV's scanning path is matched to make the UAV's flight time shorter, and on the other hand, the driving distance of the car is optimized so that the car can travel throughout the entire reconnaissance area. The travel time during the mission is short, so as to determine the driving path of the car and the launch and recovery points of the drone in each area.

Vehicle path planning is to optimize the order in which the car visits the reconnaissance area and select temporary stops near each reconnaissance area. On the one hand, it cooperates with the scanning path of the UAV to make the flight time of the UAV shorter, and on the other hand optimizes the driving distance of the car. It makes the driving time of the car during the whole mission shorter. Combining these two aspects, based on the idea of saving algorithm, a path planning algorithm for vehicles is designed, as shown in Algorithm 3. First, calculate the Floyd distance matrix dis (1st row) according to the position information of all points, then select the scanning path (2nd row) for each area, and get the start and end points of the scanning path (3rd row). Two temporary stops are randomly selected near each reconnaissance area, and then the distance from one temporary stop to the start of the scanning path and the distance from the end of the scanning path to another temporary stop are calculated, where Dis is the two sum of distances (lines 4-10). In each reconnaissance area, find two temporary stops corresponding to the minimum distance Dis as the selected stops in this area (Line 12) to form the stop set goal (Line 14), and then calculate the saving matrix (Line 14) Lines 15-19), and sort them in descending order (Line 20). Starting from the maximum value, the corresponding two reconnaissance areas are connected until all the reconnaissance areas are included, resulting in a feasible solution for the path planning of cars and UAVs (Line 21).

S103: Use a local search algorithm to improve the determined driving path of the vehicle and the launch point and recovery point of the UAV in each area, and determine the vehicle-machine cooperative reconnaissance path.

Preferably, the local search algorithm includes: by randomly exchanging the access order of the two reconnaissance areas, determining a vehicle-machine cooperative reconnaissance path that improves the driving distance of the vehicle; and, randomly exchanging the vehicle to fly and recover the UAV near a certain reconnaissance area Temporary stopping point, determine the vehicle-machine cooperative reconnaissance path that reduces the UAV flying distance and/or the vehicle driving distance;

Described adopting the local search algorithm to improve the driving path of the determined vehicle and the flying point and the recovery point of the UAV in each area to determine the vehicle-machine cooperative reconnaissance path, including:

The two methods in the local search algorithm are randomly used to determine the vehicle-machine cooperative reconnaissance path, and the determined optimal vehicle-machine cooperative reconnaissance path is used as the final vehicle-machine cooperative reconnaissance path when there is no improvement for a continuous set number of times.

Through the first two stages of UAV and vehicle path planning algorithms, the optimal solution for vehicle-machine coordinated multi-area reconnaissance can be obtained, but in many cases it may not be the optimal solution to the problem, and there is still room for improvement. Therefore, local search algorithms for vehicle paths and UAV paths are further designed to improve the quality of the solution. Two types of random operators are mainly used for local search. The first type is to randomly exchange the access order of the two reconnaissance areas to search for a feasible solution to improve the driving distance of the vehicle; the second type is to randomly exchange the vehicle to fly near a reconnaissance area. and recover the temporary stopping point of the drone, and search for feasible solutions to reduce the flying distance of the drone and/or the driving distance of the car. By randomly calling these two types of operators to search for different feasible solutions, until there is no improvement for Nmax consecutive times, stop the search to get the final solution.

As shown in FIG. 5 , it is a schematic structural diagram of a multi-area vehicle-machine cooperative reconnaissance path planning system according to an embodiment of the present invention. The system includes:

Scanning path determination unit 21: for determining the candidate scanning path of the UAV according to the geometric features of the reconnaissance area;

The initial vehicle-machine path unit 22 is used to determine the driving path of the vehicle and the flying point and recovery point of the drone in each area based on the saving algorithm based on the candidate scanning path of the drone;

Vehicle-machine cooperative reconnaissance path determination unit 23: used to improve the determined vehicle's driving path and the UAV's launch point and recovery point in each area by using a local search algorithm to determine the vehicle-machine cooperative reconnaissance path.

Preferably, the scanning path determination unit 21 is specifically used for:

According to the geometric shape of the reconnaissance area, if the circularity of the geometric shape of the reconnaissance area is greater than the set threshold, it is determined that the scanning mode of the UAV reconnaissance is the helical scanning mode;

If the roundness of the geometric shape of the reconnaissance area is not greater than the set threshold, it is determined that the scanning mode of the drone reconnaissance is the mowing scanning mode;

According to the determined scanning mode, determine the candidate scanning path of the UAV and the initial launch point and final recovery point of the UAV.

Preferably, the scanning path determination unit 21 is further configured to:

If the scanning mode of the drone reconnaissance is the mowing scanning mode, then determine the concave-convexity of the geometry of the reconnaissance area, and if the geometry of the reconnaissance area is a concave polygon, decompose the reconnaissance area into multiple convex polygon;

According to the decomposed convex polygons, the candidate scanning path of the UAV and the initial launch point and the final recovery point of the UAV are determined in the mowing scanning mode.

Preferably, the initial vehicle path unit 22 is specifically used for:

By optimizing the order in which the car visits the reconnaissance area and selecting a temporary stop near each reconnaissance area, on the one hand, the UAV's scanning path is matched to make the UAV's flight time shorter, and on the other hand, the driving distance of the car is optimized so that the car can travel throughout the entire reconnaissance area. The travel time during the mission is short, so as to determine the driving path of the car and the launch and recovery points of the drone in each area.

Preferably, the local search algorithm includes: by randomly exchanging the access order of the two reconnaissance areas, determining a vehicle-machine cooperative reconnaissance path that improves the driving distance of the vehicle; and, randomly exchanging the vehicle to fly and recover the UAV near a certain reconnaissance area Temporary stopping point, determine the vehicle-machine cooperative reconnaissance path that reduces the UAV flying distance and/or the vehicle driving distance;

The vehicle-machine cooperative reconnaissance path determination unit 23 is specifically configured to: randomly use two methods in the local search algorithm to determine the vehicle-machine cooperative reconnaissance path, until there is no improvement for a continuous set number of times, to determine the optimal reconnaissance path. The vehicle-machine cooperative reconnaissance path is the final vehicle-machine cooperative reconnaissance path.

Applications

The following is a typical example to give an application example of the model and algorithm, and to illustrate the advantages of vehicle-machine cooperation for multi-area reconnaissance. All computational experiments are carried out on a Huawei laptop, which uses a Core i7 1.8GHz quad-core processor, 16GB memory, Windows 10 operating system, and uses Matlab R2018a for algorithm coding.

Generate a 7×7 road network on the plane that divides the plane into a grid of 49 squares. Set the side length of each grid to 10 units, randomly select 20 grids from the 49 grids, and generate an irregular polygon in each selected grid, as shown in Figure 6. The 20 polygonal regions are numbered from left to right, bottom to top. A random temporary stop is generated on each edge of all polygons, represented by blue asterisks and red squares representing base stations. Finally, connect the road network to the coverage area with line segments. Cars carry drones from the base station to conduct coverage reconnaissance in 20 areas, and return to the base station after completing the task. Find the best route for cars and drones to complete scanning reconnaissance of all areas.

The average speed of the vehicle is set to 0.5 units, and the flight speed of the drone is set to 1 unit. Set the scan width of the drone to 1 unit and the maximum endurance time to 140 units of time. Nmax is set to 200 in the local search algorithm. The roundness of the 20 reconnaissance areas is calculated using formula (12), as shown in Table 3.

Table 3: Roundness of 20 Scouting Areas

It can be seen from Table 3 that the circularity of areas 1, 3, 6, and 11 is obviously greater than 0.86, so the spiral scanning mode is adopted, and the mowing scanning mode is adopted for the remaining areas. Regions 2, 12, 14, 16, 17, 18 are concave polygons, they are decomposed using a previously designed trapezoidal decomposition-based BCD method, and then Boustrophedon paths are planned for them using the mowing scan mode.

If the UAV is simply used to conduct reconnaissance in these areas, considering the maximum endurance time of the UAV and the limitation that the UAV must return to the base safely, the UAV cannot fly to areas 14, 17, 19, and 20, so it is impossible to detect These areas are reconnaissance, and the remaining areas are all within the reconnaissance range of the UAV, but only areas 1, 2, 3, 5, 8, 9, 11, and 12 can be reconnaissance completed in one flight of the UAV. The rest of the area requires the drone to continuously return to the base station for charging and then go to the area for reconnaissance to complete the overall mission. Therefore, for large-scale multi-area reconnaissance problems, it is difficult for small UAVs to complete reconnaissance tasks.

If the vehicle-machine cooperative reconnaissance mode is adopted, the feasible solution calculated by the three-stage heuristic algorithm is shown in Figure 7, in which the sequence of vehicles visiting 20 areas is 2-1-3-6-4-7-10-14 -20-17-19-13-16-18-15-12-9-5-8-11 The UAV scanning path is shown in the picture, and the total time to complete all area scanning and reconnaissance is 2379.71. The three-stage heuristic algorithm takes 18 minutes and 32 seconds to solve the path planning scheme of 20 reconnaissance areas. It can be seen that the vehicle-machine coordination mode can efficiently complete the reconnaissance tasks that cannot be accomplished by simply using UAVs, and the three-stage heuristic algorithm can effectively solve the complex path planning problem brought about by the vehicle-machine cooperation and meet the practical application requirements.

It is understood that the specific order or hierarchy of steps in the disclosed processes is an example of a sample approach. Based upon design preferences, it is understood that the specific order or hierarchy of steps in the processes may be rearranged without departing from the scope of the present disclosure. The accompanying method claims present elements of the various steps in a sample order, and are not meant to be limited to the specific order or hierarchy presented.

In the foregoing Detailed Description, various features are grouped together in a single embodiment for the purpose of simplifying the disclosure. This method of disclosure should not be interpreted as reflecting an intention that embodiments of the claimed subject matter require more features than are expressly recited in each claim. Rather, as the following claims reflect, present invention lies in less than all features of a single disclosed embodiment. Thus, the following claims are hereby expressly incorporated into the Detailed Description, with each claim standing on its own as a separate preferred embodiment of this invention.

The disclosed embodiments are described above to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit and scope of this disclosure. Thus, the present disclosure is not intended to be limited to the embodiments set forth herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

The above description includes examples of one or more embodiments. Of course, it is not possible to describe all possible combinations of components or methods in order to describe the above-described embodiments, but one of ordinary skill in the art will recognize that further combinations and permutations of the various embodiments are possible. Accordingly, the embodiments described herein are intended to cover all such changes, modifications and variations that fall within the scope of the appended claims. Furthermore, with respect to the term "comprising" as used in the specification or claims, the term "comprises" is encompassed in a manner similar to the term "comprising," as if "comprising," were interpreted as a conjunction in the claims. Furthermore, any use of the term "or" in the specification of the claims is intended to mean a "non-exclusive or."

The specific embodiments described above further describe the objectives, technical solutions and beneficial effects of the present invention in detail. It should be understood that the above descriptions are only specific embodiments of the present invention, and are not intended to limit the scope of the present invention. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention shall be included within the protection scope of the present invention.

Claims (10)

1. a multi-region vehicle-machine collaborative reconnaissance path planning method, characterized in that the method comprises: According to the geometric features of the reconnaissance area, determine the candidate scanning path of the UAV; Based on the candidate scanning path of the UAV, based on the saving algorithm, determine the driving path of the car and the flying point and recovery point of the UAV in each area; The local search algorithm is used to improve the determined driving path of the car and the flying point and recovery point of the UAV in each area, and determine the cooperative reconnaissance path of the vehicle and the machine. 2. The multi-region vehicle-machine cooperative reconnaissance path planning method as claimed in claim 1, wherein the described according to the geometric feature of the reconnaissance area, determine the candidate scanning path of the unmanned aerial vehicle, comprising: According to the geometric shape of the reconnaissance area, if the circularity of the geometric shape of the reconnaissance area is greater than the set threshold, it is determined that the scanning mode of the UAV reconnaissance is the helical scanning mode; If the circularity of the geometric shape of the reconnaissance area is not greater than the set threshold, determine that the scanning mode of the drone reconnaissance is the mowing scanning mode; According to the determined scanning mode, the candidate scanning path of the UAV and the initial launch point and final recovery point of the UAV are determined. 3. The multi-area vehicle-machine collaborative reconnaissance path planning method as claimed in claim 2, wherein if the scanning mode of UAV reconnaissance is a mowing scanning mode, then the concave-convexity of the geometry of the reconnaissance area is judged , if the geometric shape of the reconnaissance area is a concave polygon, then the reconnaissance area is decomposed into a plurality of convex polygons; According to the decomposed convex polygons, the candidate scanning path of the UAV, the initial launch point and the final recovery point of the UAV are determined in the mowing scanning mode. 4. The multi-area vehicle-machine collaborative reconnaissance path planning method as claimed in claim 3, wherein, on the basis of the candidate scanning path of the unmanned aerial vehicle, based on the saving algorithm, determine the driving path of the vehicle and the unmanned aerial vehicle in the Release and recovery points in each area, including: By optimizing the order in which the car visits the reconnaissance area and selecting temporary stopping points near each reconnaissance area, on the one hand, the UAV's scanning path is matched to make the UAV's flight time shorter, and on the other hand, the driving distance of the car is optimized so that the car can travel throughout the entire reconnaissance area. The travel time during the mission is short, so as to determine the driving path of the car and the launch and recovery points of the drone in each area. 5. The multi-area vehicle-machine cooperative reconnaissance path planning method as claimed in claim 4, wherein the local search algorithm comprises: by randomly exchanging the access sequences of the two reconnaissance areas, it is determined to improve the vehicle-machine collaboration of the vehicle travel distance. Reconnaissance paths; and, randomly swapping the temporary parking spots where cars fly and recover UAVs near a certain reconnaissance area, and determine a vehicle-machine cooperative reconnaissance path that reduces the flying distance of the UAV and/or the driving distance of the car; The local search algorithm is used to improve the determined driving path of the car and the flying point and recovery point of the UAV in each area, and determine the cooperative reconnaissance path of the vehicle and the machine, including: The two methods in the local search algorithm are randomly used to determine the vehicle-machine cooperative reconnaissance path, and the determined optimal vehicle-machine cooperative reconnaissance path is used as the final vehicle-machine cooperative reconnaissance path when there is no improvement for consecutive set times. 6. A multi-region vehicle-machine cooperative reconnaissance path planning system, characterized in that the system comprises: Scanning path determination unit: used to determine the candidate scanning path of the UAV according to the geometric characteristics of the reconnaissance area; Initial vehicle path unit: based on the candidate scanning path of the UAV, based on the saving algorithm, determine the driving path of the car and the flying point and recovery point of the UAV in each area; Vehicle-machine cooperative reconnaissance path determination unit: It is used to improve the determined driving path of the car and the launch point and recovery point of the UAV in each area by using a local search algorithm to determine the vehicle-machine cooperative reconnaissance path. 7. The multi-region vehicle-machine cooperative reconnaissance path planning system according to claim 6, wherein the scanning path determination unit is specifically used for: According to the geometric shape of the reconnaissance area, if the circularity of the geometric shape of the reconnaissance area is greater than the set threshold, it is determined that the scanning mode of the UAV reconnaissance is the helical scanning mode; If the circularity of the geometric shape of the reconnaissance area is not greater than the set threshold, determine that the scanning mode of the drone reconnaissance is the mowing scanning mode; According to the determined scanning mode, the candidate scanning path of the UAV and the initial launch point and final recovery point of the UAV are determined. 8. The multi-area vehicle-machine cooperative reconnaissance path planning system according to claim 7, wherein the scanning path determination unit is specifically also used for: If the scanning mode of the UAV reconnaissance is the mowing scanning mode, the concave-convexity of the geometry of the reconnaissance area is judged, and if the geometry of the reconnaissance area is a concave polygon, the reconnaissance area is decomposed into multiple convex polygon; According to the decomposed convex polygons, the candidate scanning path of the UAV and the initial launch point and the final recovery point of the UAV are determined in the mowing scanning mode. 9. The multi-region vehicle-machine cooperative reconnaissance path planning system according to claim 8, wherein the initial vehicle-machine path unit is specifically used for: By optimizing the order in which the car visits the reconnaissance area and selecting temporary stopping points near each reconnaissance area, on the one hand, the UAV's scanning path is matched to make the UAV's flight time shorter, and on the other hand, the driving distance of the car is optimized so that the car can travel throughout the entire reconnaissance area. The travel time during the mission is short, so as to determine the driving path of the car and the launch and recovery points of the drone in each area. 10. The multi-area vehicle-machine cooperative reconnaissance path planning system according to claim 9, wherein the local search algorithm comprises: by randomly exchanging the access sequences of the two reconnaissance areas, determining the vehicle-machine collaboration for improving the vehicle travel distance Reconnaissance paths; and, randomly exchange the temporary parking spots where vehicles fly and recover UAVs near a certain reconnaissance area, and determine a vehicle-machine cooperative reconnaissance path that reduces the flying distance of the UAV and/or the driving distance of the car; The vehicle-machine cooperative reconnaissance path determination unit is specifically used for: randomly adopting two methods in the local search algorithm to determine the vehicle-machine cooperative reconnaissance path, until there is no improvement for a continuous set number of times, to determine the optimal vehicle. The vehicle-machine cooperative reconnaissance path is used as the final vehicle-machine cooperative reconnaissance path.

Images