CN107239078B

CN107239078B - Unmanned aerial vehicle base station site selection and patrol path optimization method and device

Info

Publication number: CN107239078B
Application number: CN201710497121.5A
Authority: CN
Inventors: 刘忠; 刘瑶; 石建迈; 陈超; 罗志浩; 张家铭; 王玥; 周天任
Original assignee: National University of Defense Technology
Current assignee: National University of Defense Technology
Priority date: 2017-06-26
Filing date: 2017-06-26
Publication date: 2020-03-27
Anticipated expiration: 2037-06-26
Also published as: CN107239078A

Abstract

Embodiments of the present invention provide a method and device for site selection and patrol path optimization of a UAV base station. The method includes: allocating target points according to a target point reconnaissance by the UAV and the Euclidean distance of the base station, and then searching for nearby points Plan the UAV flight path, limit the UAV patrol path based on the UAV endurance time constraint, and limit the upper and lower limits of the number of UAVs configured for each base station, and obtain the initial plan for the location of the UAV base station and the patrol flight path; Perform a neighborhood search on the initial plan to obtain a new plan after adjustment of the location of the UAV base station and the neighborhood search of the patrol path; calculate the total cost of the new plan for the location of the UAV base station and the patrol path; if it is determined If the total cost of the new scheme is lower than the total cost of the original scheme, the new scheme is saved, and the next iteration is performed on the basis of the new scheme, otherwise it is discarded. The above technical solution has the following beneficial effects: the cost of location selection and patrol path of the UAV base station can be minimized, the cost of UAV patrol is greatly reduced, and the solution is very time-consuming.

Description

Unmanned aerial vehicle base station site selection and patrol path optimization method and device

Technical Field

The invention relates to the technical field of unmanned aerial vehicles, in particular to an unmanned aerial vehicle base station site selection and patrol path optimization method and device.

Background

In recent years, criminal behaviors such as sneak, smuggling, terrorist activities and the like in border areas are getting more serious, and the criminal forms show diversified, intelligent and concealed trends, which all put higher requirements on monitoring capability and response speed of defense troops. And most of the land border lines in China are high mountain and desert regions, the geographical positions are complex, the environment is severe, the traditional border defense monitoring mode of standing guard and manual patrol has low efficiency, high danger and low response speed, and the requirement of the current border situation cannot be met. The monitoring mode of installing the camera is difficult to maintain due to high cost and later period, and cannot be widely applied. Therefore, with the development of unmanned aerial vehicles and air surveillance technology, the deployment of unmanned aerial vehicles for monitoring and patrol in frontier areas is an inevitable trend, and countries in the united states, italy, and the like have led to the use of unmanned aerial vehicles to assist border patrol.

Since the border lines of the United states partially pass through the areas where people do not live and are difficult to pass, devices such as ground cameras and sensors are difficult to maintain, illegal cross-border and drug-selling activities are frequent, the United states national Security agency starts to research and apply unmanned aerial vehicles to border patrol in 2003. In the same year, a high-altitude unmanned aerial vehicle 'predator B' with a long endurance is selected for investigation and patrol. In some remote areas where infrastructure is difficult to build or the remote areas are inconvenient to reach, the predator B can help the border bureau to accurately distinguish the border invasion condition, and the reaction speed of monitoring and the patrol efficiency of the border are greatly improved. However, as a large unmanned aerial vehicle, the predator B is more used for high-altitude monitoring, on one hand, the flight route of the predator B needs to be controlled and scheduled by flight, and on the other hand, in the areas such as trees and the like covered by leaves or other objects, the high-altitude monitoring is difficult to find small-scale criminal behaviors, and the patrol precision is low. In the aspect of small unmanned aerial vehicles, the police respectively uses 'sky walkers X8' and 'dranganfyer X6' to assist detection in Arizona and los Angeles, the two small unmanned aerial vehicles are light in weight, can be detachably installed in backpacks, have about 30 minutes of cruising ability and short time, and are mainly used as border monitoring assisting tools to help border personnel to enlarge the visual range of patrol monitoring.

Many european countries have also begun to apply drones for border patrols. The european union decided in 2006 that a patrol was performed using an unmanned aerial vehicle on the border lines near the mediterranean coast and the ravish strait, and thus, sneak, smuggling, terrorist activities, and the like were prevented. The department of national defense in italy has also used unmanned aerial vehicles since 2008, and 6 successive unmanned aerial vehicles were purchased with "harvesters" MQ-9 to enhance patrol efficiency and provide security for frontier troops. The russian federal safety agency has reportedly used domestic "flaps" for aerial reconnaissance. The frontier defense department indicates that the unmanned aerial system can assist frontier defense monitoring, find out activities of stealing and hunting and guide frontier duty personnel to catch offenders in the difficult traffic road sections which are difficult to reach during patrol.

In addition, countries such as Brazil, Israel and Turkish also introduce unmanned planes to assist in the frontier monitoring to complete patrol tasks.

In the aspect of domestically, the six rotor unmanned aerial vehicles of corresponding have been introduced in 2013 in Xinjiang frontier defence army, help frontier defense in mountain region complex area to be on duty, and the help officer and soldier further eliminates and observes the blind area, strengthens frontier defense control and management dynamics, ensures the safety and stability in frontier defense area. Later, the frontier defense line in the inner Mongolia province has also carried out the deployment of unmanned aerial vehicle for help officers and soldiers' more high-efficient safer completion is patrolled and is monitored in desert Gobi. In 2016, 11 months, the public security frontier in Guangdong province utilizes a plurality of unmanned aerial vehicles to patrol and monitor the frontier defense line of Guangdong harbor, and provides technical support for fighting illegal criminal activities such as smuggling and smuggling.

From the application of foreign unmanned aerial vehicle in frontier patrol, the unmanned aerial vehicle can greatly improve the frontier monitoring capability, the reaction speed and the patrol efficiency of frontier troops, well make up the defects of the traditional means, and obtain more and more important power that frontier patrol will be formed by the attention and the application of countries. In view of the border patrol condition of the domestic unmanned aerial vehicle, the unmanned aerial vehicle is still in a starting stage, and some pilot deployment and application are carried out in Xinjiang, inner Mongolia and the like, and the unmanned aerial vehicle becomes an important component force for border patrol in China along with the development, popularization and application of the unmanned aerial vehicle technology.

Determining a deployment base station of the unmanned aerial vehicle and planning a flight route for patrolling the unmanned aerial vehicle are key technical problems in applying the unmanned aerial vehicle to assist frontier patrol.

Disclosure of Invention

The embodiment of the invention provides an optimization method and device for an unmanned aerial vehicle base station address selection and patrol path, so that the cost of the unmanned aerial vehicle base station address selection and patrol path is minimized, and the patrol cost of the unmanned aerial vehicle is greatly reduced.

In one aspect, an embodiment of the present invention provides a method for optimizing an address selection and patrol path of an unmanned aerial vehicle base station, where the method includes:

distributing target points according to European distances between the target points and base stations which are detected by the unmanned aerial vehicle, then searching and planning an unmanned aerial vehicle path according to the adjacent points, limiting the patrol path of the unmanned aerial vehicle by the unmanned aerial vehicle endurance time constraint, and limiting the upper limit and the lower limit of the number of unmanned aerial vehicles configured in each base station to obtain an initial scheme of unmanned aerial vehicle base station address selection and patrol path;

performing neighborhood adjustment on the initial scheme to obtain a new scheme after the unmanned aerial vehicle base station site selection and patrol path neighborhood adjustment;

calculating the total cost of the new scheme of the unmanned aerial vehicle base station site selection and patrol path;

if the total cost of the new scheme is judged to be reduced compared with the total cost of the original scheme, the new scheme is saved, next iteration is carried out on the basis of the new scheme, and if not, the new scheme is abandoned.

On the other hand, the embodiment of the invention provides an optimization device for unmanned aerial vehicle base station address selection and patrol path, which is characterized by comprising the following components:

the initial scheme acquisition unit is used for distributing a target point according to the European distance between the target point and the base station which are detected by the unmanned aerial vehicle, and then planning the unmanned aerial vehicle path according to the near point search to obtain an initial scheme of the unmanned aerial vehicle base station address selection and patrol path;

the neighborhood adjusting unit is used for performing neighborhood adjustment on the initial scheme to obtain a new scheme after the unmanned aerial vehicle base station addressing and patrol path neighborhood adjustment;

the expense calculation unit is used for calculating the total expense of the new scheme of the unmanned aerial vehicle base station addressing and patrol path;

and the iteration judging unit is used for saving the new scheme if the total cost of the new scheme is judged to be reduced than that of the original scheme, performing the next iteration on the basis of the new scheme, and otherwise discarding the new scheme.

The technical scheme has the following beneficial effects: the unmanned aerial vehicle base station site selection and patrol route cost can be minimized, the patrol cost of the unmanned aerial vehicle is greatly reduced, and the time consumption of the scheme is lower.

Drawings

In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the drawings used in the description of the embodiments or the prior art will be briefly described below, it is obvious that the drawings in the following description are only some embodiments of the present invention, and for those skilled in the art, other drawings can be obtained according to the drawings without creative efforts.

Fig. 1 is a flowchart of an optimization method for unmanned aerial vehicle base station addressing and patrol route according to an embodiment of the present invention;

fig. 2 is a schematic structural diagram of an optimization device for unmanned aerial vehicle base station address selection and patrol path according to an embodiment of the present invention;

FIG. 3 is a diagram illustrating a structure of a neighborhood adjustment unit according to an embodiment of the present invention;

FIG. 4 is a schematic diagram of a border patrol base station site selection and flight path planning problem of an unmanned aerial vehicle according to an embodiment of the present invention;

FIG. 5 is a schematic diagram of a base station shutdown according to an embodiment of the present invention;

fig. 6 is a schematic diagram of target point switching within a route of an unmanned aerial vehicle according to an embodiment of the present invention;

FIG. 7 is a schematic diagram of candidate points and target points of a control base station under a limited condition according to an embodiment of the present invention;

FIG. 8 is a schematic diagram of an initial scheme (a) and an optimized scheme (b) of an experimental case obtained by an embodiment of the present invention;

Detailed Description

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the drawings in the embodiments of the present invention, and it is obvious that the described embodiments are only a part of the embodiments of the present invention, and not all of the embodiments. All other embodiments, which can be derived by a person skilled in the art from the embodiments given herein without making any creative effort, shall fall within the protection scope of the present invention.

The embodiment of the invention develops research aiming at the problems of deployment base station site selection and patrol route planning in frontier patrol of the unmanned aerial vehicle, establishes a mathematical planning model for integrated optimization of the base station site selection and patrol route of the unmanned aerial vehicle by relying on the existing frontier army facilities, taking a frontier sentry post as a candidate base station for deploying the unmanned aerial vehicle and taking a frontier important patrol area as a patrol and reconnaissance target, and provides technical support for the application of the unmanned aerial vehicle in the frontier patrol neighborhood based on a rapid solution algorithm of a cluster distribution and heuristic search design model.

As shown in fig. 1, a flowchart of a method for optimizing an address selection and patrol path of an unmanned aerial vehicle base station according to an embodiment of the present invention is shown, where the method includes:

101. distributing target points according to European distances between the target points and base stations which are detected by the unmanned aerial vehicle, then searching and planning an unmanned aerial vehicle path according to the adjacent points, limiting the patrol path of the unmanned aerial vehicle by the unmanned aerial vehicle endurance time constraint, and limiting the upper limit and the lower limit of the number of unmanned aerial vehicles configured in each base station to obtain an initial scheme of unmanned aerial vehicle base station address selection and patrol path;

102. performing neighborhood adjustment on the initial scheme to obtain a new scheme after the unmanned aerial vehicle base station site selection and patrol path neighborhood adjustment;

103. calculating the total cost of the new scheme of the unmanned aerial vehicle base station site selection and patrol path;

104. if the total cost of the new scheme is judged to be reduced compared with the total cost of the original scheme, the new scheme is saved, next iteration is carried out on the basis of the new scheme, and if not, the new scheme is abandoned.

Preferably, the allocating the target point according to the european distance between the target point and the base station, and then planning the unmanned aerial vehicle path according to the near point search to obtain an initial scheme of the unmanned aerial vehicle base station addressing and patrol path, includes:

step 1: after the detection target point and the base station candidate point are known, the detection target point is allocated to the base station candidate point closest to the detection target point according to the Euclidean distance;

step 2: sequencing the base stations according to the number of target points allocated to the base station points;

step 3: starting from the candidate base station with the largest number of distributed target points, judging whether the unmanned aerial vehicles dispatched by the base station exceed the upper limit number of the unmanned aerial vehicles in the base station, if not, executing Step4, otherwise, turning to Step 5;

step 4: patrolling from a target point closest to the base station, searching a next point to be patrolled closest to the current target point each time by adopting a proximity principle, and returning to the original base station after judging whether the unmanned aerial vehicle can access the next target point; if yes, the unmanned aerial vehicle continues to detect the next target point, and if the unmanned aerial vehicle cannot detect the next target point, the unmanned aerial vehicle directly returns to the base station and turns to Step 3;

step 5: when the number of the unmanned aerial vehicles dispatched by the base station reaches the upper limit which can be attached by the base station, judging whether the base station has a target point which is not detected; if not, setting the base station as started, moving out the candidate base station, turning to Step3, and performing path allocation on the next candidate base station; if yes, the incomplete detection points are distributed for the second time, the detection points are distributed to the nearest candidate base stations, then Step3 is carried out, and path planning of the candidate base stations is continued until path planning of all the base stations is completed.

Step 6: detecting the configuration number of the base station unmanned aerial vehicles, and if the configuration number of the unmanned aerial vehicles reaches the lower limit of the configuration number of the base station in the minimum number, ending the operation and giving an initial scheme; if not, the following operations are carried out:

step6.1: if the base station only has one adjacent base station and the configuration number of the unmanned aerial vehicles of the adjacent base stations is less than the upper limit, closing the base station, distributing the target to the adjacent base station, and reconstructing the patrol path of the unmanned aerial vehicles by applying the proximity search algorithm of Step4, turning to Step6 if the unmanned aerial vehicles with the configuration number of the upper limit of the base station can complete the patrol of all the targets, and turning to Step6.3 if the unmanned aerial vehicles with the configuration number of the upper limit of the base station cannot complete the patrol of all the targets;

step6.2: if the base station has two adjacent base stations, closing the base station, allocating the target to the adjacent base stations with a smaller number of unmanned aerial vehicles, reconstructing a patrol path of the unmanned aerial vehicles by using a Step4 neighbor search algorithm, if the unmanned aerial vehicles with the upper limit number allocated by the base station can complete the reconnaissance of all the targets, turning to Step6, otherwise, allocating the unmanned aerial vehicles of the adjacent base stations to the upper limit number, allocating the remaining targets which cannot be accessed to a second adjacent base station, recalculating the patrol path of the unmanned aerial vehicles of the second adjacent base station by using a Step4 neighbor search algorithm, if the unmanned aerial vehicles with the upper limit number allocated by the second adjacent base station can complete the patrol of all the targets, turning to Step6, otherwise, turning to Step 6.3;

step6.3: adding 1 unmanned aerial vehicle for the base stations with the number of unmanned aerial vehicles less than the lower limit, sequentially accessing target points distributed by one base station with the larger number of unmanned aerial vehicles in adjacent base stations by the unmanned aerial vehicle according to a recent principle, constructing a maximum access loop of the unmanned aerial vehicle, sequentially adding the unmanned aerial vehicles for the base stations until the requirement of the lower limit number of the unmanned aerial vehicles is met, then applying a Step4 approach search algorithm to the remaining target points of the adjacent base stations to reconstruct a patrol path of the unmanned aerial vehicle, and turning to Step 6;

step 7: and if the Step6 circulation times exceed the total number of the candidate base stations, stopping the algorithm, and giving an initial scheme of base station address selection and unmanned aerial vehicle patrol path.

Preferably, the following meta-operations are invoked when performing neighborhood adjustment on the initial solution: and (3) closing the base station operation: and closing one base station and redistributing the corresponding target point to ensure that the unmanned aerial vehicle controlling the base station is fully utilized so as to reduce patrol cost.

Preferably, the following meta-operations are invoked when performing neighborhood adjustment on the initial solution: exchange destination point operation: the sequence of two target points is randomly exchanged in the route of the single unmanned aerial vehicle, and the phenomenon of crossing or overlapping of routes in the route of the unmanned aerial vehicle is mainly optimized.

Preferably, the following meta-operations are invoked when performing neighborhood adjustment on the initial solution: merging routes of unmanned planes: and randomly selecting two unmanned aerial vehicle paths of one base station or two adjacent base stations to be combined under the constraint condition of meeting the cruising ability of the unmanned aerial vehicle.

As shown in fig. 2, a schematic structural diagram of an apparatus for optimizing an address selection and patrol path of an unmanned aerial vehicle base station according to an embodiment of the present invention is shown, where the apparatus includes:

the initial scheme obtaining unit 21 is configured to distribute a target point according to an euclidean distance between the target point and a base station, which are detected by the unmanned aerial vehicle, and then plan a path of the unmanned aerial vehicle according to a near point search, so as to obtain an initial scheme for addressing and patrolling the base station of the unmanned aerial vehicle;

a neighborhood adjusting unit 22, configured to perform neighborhood adjustment on the initial solution to obtain a new solution after neighborhood adjustment of base station addressing and patrol routes of the unmanned aerial vehicle;

a cost calculation unit 23, configured to calculate a total cost of the new scheme for the unmanned aerial vehicle base station addressing and patrol route;

and the iteration judging unit 24 is configured to save the new scheme and perform the next iteration on the basis of the new scheme if it is judged that the total cost of the new scheme is reduced from the total cost of the original scheme, and otherwise, discard the new scheme.

Preferably, the initial scheme obtaining unit 21 is specifically configured to allocate a target point according to a european distance between the target point and a base station that the unmanned aerial vehicle scouts, then plan a path of the unmanned aerial vehicle according to a near point search, limit a patrol path of the unmanned aerial vehicle according to a duration constraint of the unmanned aerial vehicle, and limit upper and lower limits of the number of unmanned aerial vehicles configured for each base station, so as to obtain an initial scheme of base station addressing and patrol path of the unmanned aerial vehicle, including:

As shown in fig. 3, which is a schematic structural diagram of a neighborhood adjustment unit according to an embodiment of the present invention, preferably, the neighborhood adjustment unit 22 includes:

a first meta-operation module 221, configured to invoke the following meta-operations when performing neighborhood adjustment on the initial solution: and (3) closing the base station operation: and closing the base station and redistributing the corresponding target point to make the unmanned aerial vehicle controlling the base station fully utilized so as to reduce patrol cost.

Preferably, the neighborhood adjusting unit 22 includes:

a second meta-operation module 222, configured to invoke the following meta-operations when performing neighborhood adjustment on the initial solution: exchange destination point operation: the sequence of two target points is randomly exchanged in the route of the single unmanned aerial vehicle, and the phenomenon of crossing or overlapping of routes in the route of the unmanned aerial vehicle is mainly optimized.

Preferably, the neighborhood adjusting unit 22 includes:

a third element operation module 223, configured to invoke the following element operations when performing neighborhood adjustment on the initial solution: merging routes of unmanned planes: and randomly selecting two unmanned aerial vehicle paths of one base station or two adjacent base stations to be combined under the constraint condition of meeting the cruising ability of the unmanned aerial vehicle.

The following is detailed by way of example of application:

unmanned aerial vehicle is as steerable, can carry on the unmanned aerial vehicle of multiple sensor. In recent years, unmanned aerial vehicles receive more and more attention, develop rapidly, and have wide application range and application prospect in three major neighborhoods of military affairs, scientific research and civilian use.

1. Unmanned aerial vehicle border patrol system assembly

According to the application background of border patrol, the unmanned aerial vehicle patrol system mainly comprises the following five parts: control base station, unmanned aerial vehicle, task load, transmission recovery unit, communication link.

(1) Controlling a base station

In border patrol tasks, the control base station is typically set up on the ground. The ground station system comprises a software and hardware system such as an image display, investigation information analysis and the like, and mainly sends flight instructions of the unmanned aerial vehicle, monitors the flight state of the unmanned aerial vehicle, processes real-time video information and the like.

On the one hand, the control personnel utilize communication equipment to send the instruction for unmanned aerial vehicle in the basic station, control unmanned aerial vehicle's flight and the operation of mission load. On the other hand, through the communication link, the control personnel also can obtain the information and the image that unmanned aerial vehicle returned, including the geographical position, the altitude of flight, the navigational speed of unmanned aerial vehicle, mains voltage and the real-time image that unmanned aerial vehicle returned etc..

In addition, the control base station is generally integrated with a communication system connected with the outside, and is mainly used for requesting the superior, receiving tasks issued by the superior, and acquiring outside information such as weather.

(2) Unmanned plane

In the patrol process of the unmanned aerial vehicle, the main task of the unmanned aerial vehicle is to bear corresponding task loads, take off from the base station according to instructions, complete patrol tasks near a border line and then return to the base station.

First, the unmanned aerial vehicle body needs to have sufficient load capacity, and can carry various mission loads including sensors such as a battery and a camera. Secondly, there is also a corresponding limit to the flying height of the drone. In 22000 kilometers of Chinese land border lines, parts are high mountain areas and are covered by forests, so that the unmanned aerial vehicle sometimes needs to cross over hilly forests and other obstacles, the maximum flight height of the unmanned aerial vehicle is required to be not less than 3000 meters, and the unmanned aerial vehicle can carry out flight tasks for a period of time at middle and high altitudes. However, if the flying height of the unmanned aerial vehicle is too high, illegal behaviors in mountainous areas or forests are difficult to find through pictures transmitted by the unmanned aerial vehicle, so that the identification precision is greatly reduced, and therefore the unmanned aerial vehicle is required to fly at low altitude, even at ultra-low altitude when abnormal situations are found and deep reconnaissance is required. Thirdly, border patrol also puts requirements on the flight speed and endurance time of the unmanned aerial vehicle. On one hand, the border lines of China are long, patrol tasks are complex, and only when the cruising time of the unmanned aerial vehicle is not less than 1 hour and the cruising speed is not less than 50 kilometers per hour, the positions of the base stations and the number of the unmanned aerial vehicles can be reasonably arranged, so that the cost caused by base station construction and unmanned aerial vehicle use is reduced. On the other hand, unknown abnormal conditions may occur in patrol tasks, and further detection is needed, so that the unmanned aerial vehicle is required to be capable of reducing speed and slowing flight, and even have hovering capability.

(3) Task load

The type and performance of the task load is determined according to the task being completed.

The unmanned aerial vehicle firstly needs to carry an energy unit with a certain capacity, such as a battery or fuel oil, and the capacity of the energy unit is limited. If the capacity is too low, the unmanned aerial vehicle cannot be supported for long-time flight patrol, and if the capacity is too high, the unmanned aerial vehicle cannot bear the load due to too heavy energy. Secondly, the unmanned aerial vehicle needs to bear a simple video imaging system including a camera, and control personnel in the base station can acquire clear and accurate real-time image information by adjusting the direction, the focal length and the like of the camera. In addition, unmanned aerial vehicle still need bear navigation, utilizes the satellite to fix a position, also can carry on the pilot frequency radar transceiver, and control personnel can acquire unmanned aerial vehicle's position and distance through the radar display in the basic station like this.

(4) Launching and recovering device

For the small unmanned aerial vehicle used in the patrol mission process, if a multi-rotor unmanned aerial vehicle capable of taking off vertically is adopted, a transmitting device is not needed. However, for the unmanned aerial vehicle which cannot take off vertically, a manual throwing mode can be generally adopted, or the unmanned aerial vehicle is launched by utilizing an inclined slideway through thrust, namely, a simple launching device.

Because unmanned aerial vehicle cost is higher, unmanned aerial vehicle in the patrol task need return the basic station safely under recovery unit's protection. The form of umbrella is retrieved in main adoption, when unmanned aerial vehicle accomplished the task, return near the basic station, the control personnel make the engine slow down car through sending the instruction, and unmanned aerial vehicle slows down, descends the height. After a certain time, unmanned aerial vehicle descends to suitable height and speed, makes the engine park through sending the instruction equally, retrieves the umbrella and opens to open when suitable height and retrieve the umbrella, make unmanned aerial vehicle slowly land under the umbrella, organism and task equipment's damage when reducing the landing.

(5) Communication link

The communication link is a channel for realizing real-time information exchange between the control station and the unmanned aerial vehicle and is divided into an uplink communication link and a downlink communication link.

The uplink communication link refers to a communication link from the control base station to the drone, and mainly transmits: the flight control instruction of the unmanned aerial vehicle, the operation instruction of the mission load, relevant position updating information and the like.

The downlink communication link refers to transmitting information from the unmanned aerial vehicle back to the control base station, and the transmitted information includes position information of the unmanned aerial vehicle, relevant images and data acquired by the task load, and flight parameters and state information monitored on the unmanned aerial vehicle, such as electric quantity, flight speed, flight altitude and the like.

2. Model construction for base station site selection and patrol path optimization

And performing mathematical definition on relevant factors in the collaborative planning problem of the base station site selection and patrol path of the unmanned aerial vehicle, and constructing a 0-1 integer planning model for planning the base station site selection and patrol path.

Fig. 4 is a schematic diagram illustrating the problem of location selection and flight path planning of the border patrol base station of the unmanned aerial vehicle according to the embodiment of the present invention. Given a series of base station candidate points and reconnaissance target points, a model is constructed as shown in fig. 4 by taking the total expenses such as the minimum patrol cost and the base station establishment cost as objective functions and considering the constraints such as the cruising ability of the unmanned aerial vehicles and the number of the unmanned aerial vehicles in the control base station.

2.1 base station site selection and patrol path optimization problem description

In the problems of base station site selection and patrol path optimization, the problem factors mainly comprise candidate base stations, investigation targets and unmanned aerial vehicles. This section mainly defines and constrains the analysis to three factors and defines the optimization goal of the model.

2.1.1 candidate base stations

In the border patrol task of the unmanned aerial vehicle, a series of corresponding base stations are required to be established and a corresponding unmanned aerial vehicle system is required to be equipped. Under the general condition, the unmanned aerial vehicle basic station can establish at the frontier sentry post, and the construction cost of basic station is reduced to the current facility of utilizing the company of being convenient for, also can establish near the border line that unmanned aerial vehicle patrols, more is favorable to unmanned aerial vehicle's flight scheduling. These frontier posts or candidate sites constitute the set of candidate base stations M ═ {1,2, …, M }. When the candidate base station is determined to be the unmanned aerial vehicle base station, corresponding supporting facilities such as a communication station and a take-off recovery device generally need to be established, and software and hardware systems such as unmanned aerial vehicle instruction control, flight monitoring and reconnaissance information analysis need to be configured, so that a fixed cost C for building the base station can be generated_i(i ∈ M). Also for economic cost and military organizational reasons, there is a corresponding limit to the number of drones in a base station. When the number of the unmanned aerial vehicles is too small, the value of the fixed base station cannot be fully utilized economically, and the programming is unreasonable; also limited by military codes and fixed facility capacity, the number of equipped drones cannot exceed a certain number. The lower limit of the number of the unmanned aerial vehicles configured in the base station is marked as a^LUpper limit is denoted as a^U。

2.1.2 investigation of targets

The reconnaissance target is a small area or a section of road distributed on a border line, illegal behaviors such as smuggling and stealing can occur in the area, and frequent patrol reconnaissance needs to be carried out on the illegal behaviors. These target areas or line segments are abstracted into a series of reconnaissance target points to form a reconnaissance target set, which is denoted as N ═ 1,2, L, N }. The unmanned aerial vehicle needs to hover for a certain time at each reconnaissance target i (i belongs to N) to complete the reconnaissance task of the target area, and recordsService time s for target i_i. The flight distance between any two scout targets (or the scout targets and the base station) i, j (i, j epsilon to MUN) is known and is marked as d_ij。

2.1.3 unmanned aerial vehicle

As a new high-tech means for border patrol, the unmanned aerial vehicle can complete border patrol and reconnaissance in a short time, thereby saving human resources and greatly improving patrol efficiency. Unmanned aerial vehicles in all base stations form an unmanned aerial vehicle set, and are recorded as V ═ 1,2, L and V. Because unmanned aerial vehicle all needs to carry out corresponding maintenance before and after using to can produce a fixed cost F who uses unmanned aerial vehicle_k(k. epsilon. V). Assuming that the unmanned aerial vehicle always flies at a constant speed in the patrol process, the flying distance between any two reconnaissance targets (or the reconnaissance targets and the base station) i, j (i, j belongs to MUN) is known, the flying time between any two points can be obtained and is marked as t_ij. And the unmanned aerial vehicle can receive the restriction of duration in the patrol task, namely the sum of the flight time and the service time of the unmanned aerial vehicle for accessing a plurality of targets cannot exceed the maximum duration, and is recorded as D.

2.1.4 optimization goals

1) Minimizing the overall cost of base station construction;

2) patrol of all reconnaissance targets is completed by using as few unmanned aerial vehicles as possible;

3) the overall cost of the unmanned aerial vehicle for completing one patrol on all reconnaissance targets is the minimum.

By adding the objectives of the three aspects, an overall optimization objective is determined. The overall target is optimized through the decisions of optimizing the site selection of the base station, the configuration number of each base station unmanned aerial vehicle, the flight route of each unmanned aerial vehicle and the like.

2.2 problem model construction

With the problem description in 2.1, the parameters and decision variables used in the modeling process are summarized as follows:

the mathematical model is as follows:

such that:

the objective function (2.1) minimizes the overall cost of base station construction, fixed use of the drone and flight, etc. The constraint (2.2) ensures that the in-and-out of all base stations and target points are equal, meaning that if a drone flies in (out) from a node, it must fly out (in) from that node. The constraint (2.3) indicates that each target point must be visited and can only be visited 1 time, i.e. must and can only be allocated to the flight circuit of one drone. The constraint (2.4) indicates that the flight time and service time of each drone must not exceed its endurance. Constraint (2.5) indicates that each drone is invoked up to 1 time in one plan. The constraint (2.6) indicates that the drones can only start from the construction base station, and the number of drones configured in each construction base station cannot exceed the upper limit. The constraint (2.7) indicates that the number of drones deployed cannot be less than its lower limit when building a base station at the candidate base station location. Constraint (2.8) indicates that each drone must return to the original base station from which it originated. The constraint (2.9) ensures that no sub-loops can exist in the flight path of each drone. Constraints (2.10) - (2.12) are variable value range constraints.

3. Heuristic algorithm based on target clustering and near point searching:

firstly, an initial scheme is generated by adopting a near point search algorithm, and finally the initial scheme is optimized through neighborhood search.

3.1.1 initial protocol Generation

Firstly, the target point is allocated according to the euclidean distance (euclidean metric, also called euclidean distance, which is a commonly used distance definition and refers to the real distance between two points in an m-dimensional space) between the target point and the base station, and then the unmanned aerial vehicle path is planned according to the near point search, so as to obtain an initial scheme of the problem.

The general idea of the initial solution generation is set forth below:

3.1.2 neighborhood search

After the initial scheme is obtained, corresponding neighborhood adjustment needs to be carried out on the initial scheme, and three element operations N are mainly carried out_k(k＝1,2,3)：

1) The base station operation is turned off.

In the planning process of the initial scheme, the unmanned aerial vehicle for controlling the base station is not completely utilized, so that the base station is closed and corresponding target points are redistributed, and patrol cost can be reduced at a certain probability. Fig. 5 is a schematic diagram illustrating a base station shutdown according to an embodiment of the present invention. And dispatching 2 unmanned aerial vehicles in the candidate base station a for patrol, and the unmanned aerial vehicles in the adjacent candidate base station b are also 2 unmanned aerial vehicles, so that the configuration upper limit of the unmanned aerial vehicles is not reached, closing the candidate base station a at the moment, reconfiguring 2 unmanned aerial vehicles for the candidate base station b, and patrolling 1 and 2 points originally belonging to the base station a.

2) And exchanging target point operation.

The unitary operation refers to the sequence of randomly exchanging two target points in a single unmanned aerial vehicle route, and is mainly used for optimizing the phenomenon of crossing or overlapping routes in the unmanned aerial vehicle route. Fig. 6 is a schematic diagram illustrating target point switching in routing of an unmanned aerial vehicle according to an embodiment of the present invention. Two unmanned aerial vehicles dispatched by the candidate base station form a route sequence of 1 → 3 → 2 according to an algorithm of near point search, and route intersection exists, so after the meta-operation is carried out, the two points of 2 and 3 are exchanged, the original route is adjusted to 1 → 2 → 3, and the flight cost of the unmanned aerial vehicles can be obviously reduced.

3) And merging the routes of the unmanned planes.

And randomly selecting two unmanned aerial vehicle paths of one base station or two adjacent base stations to be combined under the constraint condition of meeting the cruising ability of the unmanned aerial vehicle.

In each iteration, randomly calling any one of the three element operations, calculating the total cost of a new planning scheme, if the cost is reduced, saving the new scheme, and performing the next iteration on the basis of the new scheme, otherwise, discarding the new scheme.

4. Application example

In the experimental design process, in consideration of the specificity of the background of border patrol, a border line is patrolled, so that the investigation region is set as an irregular strip-shaped region. Fig. 7 shows an embodiment comprising 5 base stations and 20 target points whose coordinate positions are shown in table 4-1. The dotted line in fig. 7 does not represent a border line, but is a boundary line set for separating the candidate base station and the target point in the experimental design. The endurance time of the drone in this example is set to 3 hours and the patrol flight speed is set to 70 km per hour. The number of drones assigned to each base station is limited to a minimum of 2 and a maximum of 4. The reconnaissance service time for each target point was set to 0.2 hours.

TABLE 4-1 candidate base station and target Point coordinates

Fig. 8 is a schematic diagram of an initial solution (a) of an experimental case and an optimized solution (b) after a domain search according to an embodiment of the present invention. It can be seen that (b) reduces the base station construction costs compared to (a) shutting down the base station 4.

As shown in the table 4-2, the patrol cost is reduced from the original 322816 to 273855, namely, the patrol cost is reduced by 15 percent on a par, and the feasibility of the algorithm is verified.

Detailed comparison of initial and optimized protocols for the experimental cases obtained in Table 4-2

According to tests, the technical scheme of the embodiment of the invention can complete the problems of base station site selection and unmanned aerial vehicle path planning under the border patrol background, and the time consumption is lower. In addition, in the test, the initial scheme can be obviously optimized through the adjustment of neighborhood searching, and the patrol cost is greatly reduced.

It should be understood that the specific order or hierarchy of steps in the processes disclosed is an example of exemplary approaches. 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 intended 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 streamlining the disclosure. This method of disclosure is not to be interpreted as reflecting an intention that the claimed embodiments of the subject matter require more features than are expressly recited in each claim. Rather, as the following claims reflect, 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 the invention.

The previous description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present invention. To those skilled in the art; various modifications to these embodiments will be readily apparent, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the disclosure. Thus, the present disclosure is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

What has been described above includes examples of one or more embodiments. It is, of course, not possible to describe every conceivable combination of components or methodologies for purposes of describing the aforementioned embodiments, but one of ordinary skill in the art may recognize that many further combinations and permutations of various embodiments are possible. Accordingly, the embodiments described herein are intended to embrace all such alterations, modifications and variations that fall within the scope of the appended claims. Furthermore, to the extent that the term "includes" is used in either the detailed description or the claims, such term is intended to be inclusive in a manner similar to the term "comprising" as "comprising" is interpreted when employed as a transitional word in a claim. Furthermore, any use of the term "or" in the specification of the claims is intended to mean a "non-exclusive or".

Those of skill in the art will further appreciate that the various illustrative logical blocks, units, and steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. To clearly illustrate the interchangeability of hardware and software, various illustrative components, elements, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design requirements of the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present embodiments.

The various illustrative logical blocks, or elements, described in connection with the embodiments disclosed herein may be implemented or performed with a general purpose processor, a digital signal processor, an Application Specific Integrated Circuit (ASIC), a field programmable gate array or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general-purpose processor may be a microprocessor, but in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, e.g., a digital signal processor and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a digital signal processor core, or any other similar configuration.

The steps of a method or algorithm described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may be stored in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. For example, a storage medium may be coupled to the processor such the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor. The processor and the storage medium may reside in an ASIC, which may be located in a user terminal. In the alternative, the processor and the storage medium may reside in different components in a user terminal.

In one or more exemplary designs, the functions described above in connection with the embodiments of the invention may be implemented in hardware, software, firmware, or any combination of the three. If implemented in software, the functions may be stored on or transmitted over as one or more instructions or code on a computer-readable medium. Computer-readable media includes both computer storage media and communication media that facilitate transfer of a computer program from one place to another. Storage media may be any available media that can be accessed by a general purpose or special purpose computer. For example, such computer-readable media can include, but is not limited to, RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to carry or store program code in the form of instructions or data structures and which can be read by a general-purpose or special-purpose computer, or a general-purpose or special-purpose processor. Additionally, any connection is properly termed a computer-readable medium, and, thus, is included if the software is transmitted from a website, server, or other remote source via a coaxial cable, fiber optic cable, twisted pair, Digital Subscriber Line (DSL), or wirelessly, e.g., infrared, radio, and microwave. Such discs (disk) and disks (disc) include compact disks, laser disks, optical disks, DVDs, floppy disks and blu-ray disks where disks usually reproduce data magnetically, while disks usually reproduce data optically with lasers. Combinations of the above may also be included in the computer-readable medium.

The above-mentioned embodiments are intended to illustrate the objects, technical solutions and advantages of the present invention in further detail, and it should be understood that the above-mentioned embodiments are merely exemplary embodiments of the present invention, and are not intended to limit the scope of the present invention, and any modifications, equivalent substitutions, improvements and the like made within the spirit and principle of the present invention should be included in the scope of the present invention.

Claims

1. An optimization method for unmanned aerial vehicle base station site selection and patrol path is characterized by comprising the following steps:

if the total cost of the new scheme is judged to be reduced compared with the total cost of the original scheme, the new scheme is saved, next iteration is carried out on the basis of the new scheme, and if not, the new scheme is abandoned;

the method comprises the following steps of distributing target points according to European distances between the target points and base stations of unmanned aerial vehicle reconnaissance, then planning unmanned aerial vehicle paths according to near point search, limiting the upper limit and the lower limit of the number of unmanned aerial vehicles attached to each base station, and obtaining an initial scheme of unmanned aerial vehicle base station address selection and patrol paths, wherein the scheme comprises the following steps:

step 5: when the number of the unmanned aerial vehicles dispatched by the base station reaches the upper limit which can be attached by the base station, judging whether the base station has a target point which is not detected; if not, setting the base station as started, moving out the candidate base station, turning to Step3, and performing path allocation on the next candidate base station; if yes, performing secondary distribution on the incomplete detection points, distributing the detection points to the nearest candidate base stations in the rest candidate base stations, turning to Step3, and continuing path planning of the candidate base stations until path planning of all the base stations is completed;

2. The method for optimizing the location and patrol path of the base station of the unmanned aerial vehicle of claim 1, wherein the following meta-operations are invoked when performing neighborhood adjustment on the initial solution:

and (3) closing the base station operation: and closing the base station and redistributing the corresponding target point to make the unmanned aerial vehicle controlling the base station fully utilized so as to reduce patrol cost.

3. The method for optimizing the location and patrol path of the base station of the unmanned aerial vehicle of claim 1, wherein the following meta-operations are invoked when performing neighborhood adjustment on the initial solution:

exchange destination point operation: the sequence of two target points is randomly exchanged in the patrol path of the single unmanned aerial vehicle, and the cross or overlapping phenomenon of the flight routes in the path of the unmanned aerial vehicle is mainly improved and optimized.

4. The method for optimizing the location and patrol path of the base station of the unmanned aerial vehicle of claim 1, wherein the following meta-operations are invoked when performing neighborhood adjustment on the initial solution:

merging routes of unmanned planes: and randomly selecting two unmanned aerial vehicle paths of one base station or two adjacent base stations to be combined under the constraint condition of meeting the cruising ability of the unmanned aerial vehicle.

5. An unmanned aerial vehicle base station addressing and patrol route optimizing device, characterized in that the device includes:

the system comprises an initial scheme acquisition unit, a central processing unit and a central processing unit, wherein the initial scheme acquisition unit is used for allocating target points according to European distances between the target points and base stations which are detected by the unmanned aerial vehicle, then searching and planning the routes of the unmanned aerial vehicle according to the nearby points, limiting the patrol routes of the unmanned aerial vehicle according to the endurance time constraint of the unmanned aerial vehicle, and limiting the upper limit and the lower limit of the number of the unmanned aerial vehicles configured in each base station to obtain the initial schemes of the base station address selection;

the iteration judging unit is used for saving the new scheme if the total cost of the new scheme is judged to be reduced than that of the original scheme, carrying out the next iteration on the basis of the new scheme, and otherwise, abandoning the iteration;

the initial scheme obtaining unit is specifically used for distributing target points according to European distances between the target points and base stations which are detected by the unmanned aerial vehicle, then planning unmanned aerial vehicle paths according to the near points, limiting unmanned aerial vehicle patrol paths according to unmanned aerial vehicle endurance time constraints, limiting the upper and lower limits of the number of unmanned aerial vehicles configured in each base station, and obtaining an initial scheme of unmanned aerial vehicle base station addressing and patrol paths, and comprises the following steps:

6. The drone base station addressing and patrol path optimization device of claim 5, wherein the neighborhood adjustment unit comprises:

a first meta-operation module, configured to invoke the following meta-operations when performing neighborhood adjustment on the initial solution: and (3) closing the base station operation: and closing the base station and redistributing the corresponding target point to make the unmanned aerial vehicle controlling the base station fully utilized so as to reduce patrol cost.

7. The drone base station addressing and patrol path optimization device of claim 5, wherein the neighborhood adjustment unit comprises:

a second meta-operation module, configured to invoke the following meta-operations when performing neighborhood adjustment on the initial solution: exchange destination point operation: the sequence of two target points is randomly exchanged in the route of the single unmanned aerial vehicle, and the phenomenon of crossing or overlapping of routes in the route of the unmanned aerial vehicle is mainly optimized.

8. The drone base station addressing and patrol path optimization device of claim 5, wherein the neighborhood adjustment unit comprises:

a third element operation module, configured to invoke the following element operations when performing neighborhood adjustment on the initial solution: merging routes of unmanned planes: and randomly selecting two unmanned aerial vehicle paths of one base station or two adjacent base stations to be combined under the constraint condition of meeting the cruising ability of the unmanned aerial vehicle.