CN109737967A - Unmanned plane paths planning method, device, storage medium and computer equipment - Google Patents
Unmanned plane paths planning method, device, storage medium and computer equipment Download PDFInfo
- Publication number
- CN109737967A CN109737967A CN201910151761.XA CN201910151761A CN109737967A CN 109737967 A CN109737967 A CN 109737967A CN 201910151761 A CN201910151761 A CN 201910151761A CN 109737967 A CN109737967 A CN 109737967A
- Authority
- CN
- China
- Prior art keywords
- sampled point
- point
- vertex set
- route planning
- route
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/20—Instruments for performing navigational calculations
Landscapes
- Engineering & Computer Science (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Automation & Control Theory (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
- Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
Abstract
The embodiment of the invention discloses a kind of unmanned plane route planning method, device, storage medium and computer equipments, wherein method includes: to obtain route planning information, the route planning information includes goal programming region, start point information, target point information, and the goal programming region includes area of feasible solutions and barrier zone；The first sampled point is determined in the area of feasible solutions by random uniform sampling mode, determine first sampled point and the barrier zone collisionless, calculate the corresponding field intensity value of first sampled point, it determines that the field intensity value is greater than or equal to preset field strength threshold value, first sampled point is added to vertex set；Corresponding edge collection is generated according to preset planner according to the vertex set；It is concentrated at the edge according to preset path search algorithm according to start point information, target point information and searches optimal route as target route.Using the embodiment of the present invention, the accuracy and planning efficiency for improving route planning can be improved.
Description
Technical field
The present invention relates to air vehicle technique field and field of computer technology more particularly to a kind of unmanned plane path planning sides
Method, device, storage medium and computer equipment.
Background technique
With the development of computer technology, the artificial intelligence revolution of a new round is driven, UAV Intelligent chemical conversion is trend, and
Path planning is the key link of unmanned plane autonomous flight, and the purpose is to plan that one is expired in current environment according to mission requirements
The flight path of sufficient constraint condition avoids collision unmanned plane in flight course and quickly reaches home from starting point.
Unlike 2D path planning, the difficulty of the unmanned plane path planning in 3D environment is with dynamic constrained and in finger
Number increases, and kinematic constraint becomes more complicated.In related art scheme, for the unmanned plane of 3 D complex changeable environment
Path planning mostly uses the paths planning method based on sampling, such as quick random search tree method (Rapidly-exploring
Random Tree, RRT) and probability map algorithm (Probabilistic Roadmap Method, PRM).Road based on sampling
Diameter planning algorithm is to carry out sampling in state space then carrying out collision detection, does not need to pre-process spatial model, and
Calculation amount will not change in high-dimensional environment, be well suited for higher-dimension unknown complex environment locating for unmanned plane during flying.But due to
It is in map uniform sampling, when there are completion line maps when slype to generally require construction compared with multi-point sampling in map, this is just
Result in calculation amount exponential growth therewith.That is, for the sampling in slype in existing route planning method
It puts determining and route planning and needs to improve sampled point quantity to improve the accuracy and validity of slype route planning,
That which results in calculation amounts is excessive, sampled point utilization rate is too low.
Summary of the invention
Based on this, in the present invention, a kind of unmanned plane paths planning method, device, storage medium and computer are provided
Equipment improves the quantity of sampled point in slype under lower complexity, improves the whole efficiency of route planning.
In the first aspect of the present invention, a kind of unmanned plane route planning method is provided, comprising:
Route planning information is obtained, the route planning information includes goal programming region, start point information, target point letter
Breath, the goal programming region includes area of feasible solutions and barrier zone；
Determine the first sampled point in the area of feasible solutions by random uniform sampling mode, determine first sampled point with
The barrier zone collisionless calculates the corresponding field intensity value of first sampled point, and it is pre- to determine that the field intensity value is greater than or equal to
If field strength threshold value, first sampled point is added to vertex set；
Corresponding edge collection is generated according to preset planner according to the vertex set；
It concentrates and is searched most at the edge according to preset path search algorithm according to start point information, target point information
Major path is as target route.
In an alternative embodiment, the method also includes:
In the case where the sampled point quantity that the vertex set includes is less than preset points threshold value, circulation executes described logical
It crosses random uniform sampling mode and determines the first sampled point in the area of feasible solutions, determine first sampled point and the barrier
Domain collisionless calculates the corresponding field intensity value of first sampled point, determines that the field intensity value is greater than or equal to preset field strength threshold
The step of being worth, first sampled point be added to vertex set.
In an alternative embodiment, described the step of calculating first sampled point corresponding field intensity value, comprising:
Calculate repulsive force of first sampled point relative to the barrier zone；
Attraction of first sampled point relative to the barrier zone is calculated according to the target point information；
Based on the repulsive force and the attraction, the corresponding field intensity value of first sampled point is calculated.
In an alternative embodiment, described to determine that first adopts in the area of feasible solutions by random uniform sampling mode
After the step of sampling point further include:
The first distance value between the sampled point that first sampled point and the vertex set include is calculated, determines the meter
Obtained first distance value is greater than 0.
In an alternative embodiment, described that corresponding edge is generated according to preset planner according to the vertex set
The step of collection, comprising:
The second sampled point for including in the vertex set is traversed, for the second sampled point traversed, in the vertex set
The adjoint point of middle determination default points threshold value corresponding with second sampled point；
The second sampled point and adjoint point are connected by preset planner；
In the case where successful connection, the side for connecting second sampled point and adjoint point is added to edge collection.
In an alternative embodiment, described that preset corresponding with second sampled point is determined in the vertex set
The step of adjoint point for threshold value of counting, further includes:
Calculate the second distance value between the second sampled point that second sampled point and vertex set include；
Big sequence is arrived to second distance value progress from childhood, is obtained and preceding default points threshold value second distance value pair
The second sampled point answered is as adjoint point.
In an alternative embodiment, described according to start point information, target point information, according to preset route searching
Algorithm is concentrated at the edge and searches the step of optimal route is as target route, further includes:
According to preset fast search algorithm, concentrate and search apart from shortest route at the edge, will find away from
From shortest route as target route.
In the second aspect of the present invention, a kind of unmanned plane route planning device is provided characterized by comprising
Route planning information determination module, for obtaining route planning information, the route planning information includes target rule
Partition domain, start point information, target point information, the goal programming region includes area of feasible solutions and barrier zone；
Vertex set constructing module, for determining the first sampled point in the area of feasible solutions by random uniform sampling mode,
It determines first sampled point and the barrier zone collisionless, calculates the corresponding field intensity value of first sampled point, determine institute
Field intensity value is stated more than or equal to preset field strength threshold value, first sampled point is added to vertex set；
Edge collection constructing module, for generating corresponding edge collection according to preset planner according to the vertex set；
Route planning module, for according to start point information, target point information, according to preset path search algorithm,
The edge, which is concentrated, searches optimal route as target route.
In the third aspect of the present invention, it is also proposed that a kind of computer equipment, including memory and processor, the storage
Device is stored with computer program, when the computer program is executed by the processor, so that the processor executes following step
It is rapid:
Route planning information is obtained, the route planning information includes goal programming region, start point information, target point letter
Breath, the goal programming region includes area of feasible solutions and barrier zone；
Determine the first sampled point in the area of feasible solutions by random uniform sampling mode, determine first sampled point with
The barrier zone collisionless calculates the corresponding field intensity value of first sampled point, and it is pre- to determine that the field intensity value is greater than or equal to
If field strength threshold value, first sampled point is added to vertex set；
Corresponding edge collection is generated according to preset planner according to the vertex set；
It concentrates and is searched most at the edge according to preset path search algorithm according to start point information, target point information
Major path is as target route.
In the fourth aspect of the present invention, it is also proposed that a kind of computer readable storage medium is stored with computer program, institute
When stating computer program and being executed by processor, so that the processor executes following steps:
Route planning information is obtained, the route planning information includes goal programming region, start point information, target point letter
Breath, the goal programming region includes area of feasible solutions and barrier zone；
Determine the first sampled point in the area of feasible solutions by random uniform sampling mode, determine first sampled point with
The barrier zone collisionless calculates the corresponding field intensity value of first sampled point, and it is pre- to determine that the field intensity value is greater than or equal to
If field strength threshold value, first sampled point is added to vertex set；
Corresponding edge collection is generated according to preset planner according to the vertex set；
It concentrates and is searched most at the edge according to preset path search algorithm according to start point information, target point information
Major path is as target route.
Implement the embodiment of the present invention, will have the following beneficial effects:
After above-mentioned unmanned plane paths planning method, device, storage medium and computer equipment, to unmanned plane
During route is planned, random uniform sampling is carried out in area of feasible solutions, and progress and obstacle are not only needed to sampled point
The collisionless in region detects, it is also necessary to introduce potential field and calculate the field intensity value of the sampled point, only in the field being calculated
In the case that intensity values are greater than certain value, just the sampled point is added in vertex set；Then planner is passed through according to the vertex set
Corresponding edge collection is generated, route searching is then carried out according to the undirected graph that vertex set, edge collection form, to obtain nobody
The target route of machine planning.That is, by introducing potential field, it is as much as possible to remain in area of feasible solutions in slype
Sampled point increases the par of sampled point in slype.
Do not had compared to RRT algorithm or PRM algorithm using unmanned plane route planning scheme provided in an embodiment of the present invention
Have in the case where increasing sampled point quantity, the par of sampled point in slype is improved, to improve route planning
Accuracy and whole efficiency.
Detailed description of the invention
In order to more clearly explain the embodiment of the invention or the technical proposal in the existing technology, to embodiment or will show below
There is attached drawing needed in technical description to be briefly described, it should be apparent that, the accompanying drawings in the following description is only this
Some embodiments of invention for those of ordinary skill in the art without creative efforts, can be with
It obtains other drawings based on these drawings.
Wherein:
Fig. 1 is a kind of flow diagram of unmanned plane paths planning method in one embodiment；
Fig. 2 is area of feasible solutions schematic diagram in one embodiment；
Fig. 3 is the flow diagram of vertex set construction process in one embodiment；
Fig. 4 is the flow diagram of vertex set construction process in one embodiment；
Fig. 5 is the flow diagram of vertex set construction process in one embodiment；
Fig. 6 is the flow diagram of edge collection construction process in one embodiment；
Fig. 7 is undirected graph organigram in one embodiment；
Fig. 8 is the flow diagram of unmanned plane paths planning method in one embodiment；
Fig. 9 is sampling point distributions schematic diagram in an one embodiment of the present of invention；
Figure 10 is the corresponding sampling point distributions schematic diagram of PRM algorithm of the prior art；
Figure 11 is average sample point quantity distribution schematic diagram in slype in one embodiment；
Figure 12 is a kind of structural schematic diagram of unmanned plane path planning apparatus in one embodiment；
Figure 13 is the structural schematic diagram that the computer equipment of above-mentioned unmanned plane paths planning method is run in one embodiment.
Specific embodiment
Following will be combined with the drawings in the embodiments of the present invention, and technical solution in the embodiment of the present invention carries out clear, complete
Site preparation description, it is clear that described embodiments are only a part of the embodiments of the present invention, instead of all the embodiments.It is based on
Embodiment in the present invention, it is obtained by those of ordinary skill in the art without making creative efforts every other
Embodiment shall fall within the protection scope of the present invention.
In the present embodiment, spy proposes a kind of unmanned plane paths planning method, and the realization of this method can be dependent on calculating
Machine program, the computer program can run on the computer system based on von Neumann system, which can be with
It is the application program that unmanned plane route is calculated and planned.The computer system can be the above-mentioned computer program of operation
Such as the computer equipments such as smart phone, tablet computer, PC, server.
It should be noted that in the present embodiment, the computer equipment for running above-mentioned unmanned plane route planning method is one
The computer equipment being connect with unmanned machine equipment, for example, (controller can be intelligence to the controller connecting with unmanned machine equipment
The computer equipments such as mobile phone, tablet computer, PC or server), in another embodiment, above-mentioned unmanned plane route rule
The execution for the method for drawing can also be based on a unmanned machine equipment, be provided with processor on the unmanned machine equipment, through this process device
To execute above-mentioned unmanned plane route planning method.
As shown in Figure 1, in one embodiment, providing a kind of unmanned plane paths planning method, specifically including following step
Rapid S102-S108:
Step S102: obtaining route planning information, and the route planning information includes goal programming region, starting point letter
Breath, target point information, the goal programming region includes area of feasible solutions and barrier zone.
In the case where needing the route to unmanned plane to plan, the corresponding goal programming region of route planning is determined,
The goal programming region is the region for needing to carry out layout of roads.In a specific embodiment, goal programming region can
To be to be acquired in flight course by the picture pick-up device of unmanned plane and carry out the image-region after image procossing.
In the present embodiment, goal programming region A is the image-region after image recognition/processing, is advised in target
Area of feasible solutions A1 and barrier zone A2 are contained in partition domain, wherein area of feasible solutions be route planning can favored area, barrier
Domain be barrier where region, during route planning for can not favored area, and plan route and barrier zone
There is no intersect or collide.For example, A1 is area of feasible solutions in scene as shown in Figure 2, A2 is barrier zone.
Further, the route of unmanned plane is planned, the route planning information for needing to obtain in advance further includes starting
Point information, target point information, for determining the starting point and terminal of route.
Step S104: determining the first sampled point in the area of feasible solutions by random uniform sampling mode, determines described
One sampled point and the barrier zone collisionless calculate the corresponding field intensity value of first sampled point, determine that the field intensity value is big
In or equal to preset field strength threshold value, first sampled point is added to vertex set.
It in the present embodiment, is to determine Undirected networks corresponding with goal programming region to the route planning process of unmanned plane
The process schemed (step S104, step S106), then determine optimal route in the undirected graph.
Remember that G (V, E) be the undirected graph obtained by step S104, S106, wherein V is vertex set, and E is and vertex set
Corresponding edge collection.
Specifically, above-mentioned steps S104 is the process for generating vertex set V.
In the present embodiment, the sampled point in vertex set is the point by sampling acquisition in area of feasible solutions, and to obtaining
The first sampled point got is confirmed, if meets the related request for being added to vertex set.And in a specific embodiment
In, the acquisition of the first sampled point is the sampled point that random uniform sampling acquisition is carried out in area of feasible solutions.
After getting the first sampled point q, it is also necessary to carry out collision detection to the first sampled point q, that is to say, that need
Determine the first sampled point q and barrier zone A2 be it is collisionless, vertex could be used as with the collisionless sampled point of barrier zone
Collect the vertex in V.
Under normal circumstances, first sampled point can be added after determining the first sampled point and barrier zone collisionless
It is added to vertex set.In the present embodiment, in order to improve the sampled point quantity in slype, it is also necessary to carry out sampled point into one
The judgement of step.
Specifically, introducing potential field, the corresponding field intensity value U of the first sampled point is calculated in goal programming regionq, and judge
Whether preset field strength threshold value U is greater than0, only in Uq>U0In the case where, the first sampled point is just added to vertex set V.
Further, in a specific embodiment, as shown in figure 3, above-mentioned steps S104 includes the following steps:
Step S1041: the random uniform sampling in area of feasible solutions A1 obtains sampled point q；
Step S1042: judge sampled point q whether with barrier zone A2 collisionless；
If so, executing step S1043: calculating the field intensity value U of sampled point qq；
Step S1044: judge the field intensity value U of sampled point qqWhether field strength threshold value U is greater than0；
If so, executing step S1045: sampled point q is added to vertex set V.
In the present embodiment, in order to guarantee the reasonability and accuracy of route planning, it is also necessary to guarantee adopting in vertex set
Sampling point quantity is more than certain value, for example, minimum of the one points threshold value n of setting as the sampled point quantity for including in vertex set.
Specifically, in one embodiment, as shown in figure 4, the above method further include:
In the case where the sampled point quantity that the vertex set includes is less than preset points threshold value n, circulation executes step
S104, until the sampled point quantity for including in vertex set is greater than or equal to preset points threshold value n.
Above by random uniform sampling mode after the step of area of feasible solutions determines the first sampled point further include:
The first distance value between the sampled point that first sampled point and the vertex set include is calculated, is calculated described in determination
First distance value is greater than 0.
q1、q2Two points respectively in area of feasible solutions, the calculating of distance value between the two can be by calculating public affairs as follows
Formula is calculated:
Wherein, d (q1,q2) it is point q1、q2The distance between value.
In the present embodiment, by above-mentioned distance value calculation formula, the sampling for including in sampled point q and vertex set V is calculated
First distance value between point, and determine that the first distance value being calculated is greater than 0, that is to say, that determine sampled point q not
It is existing point in vertex set, avoids duplicate sampled point calculating and determination process.
It should be noted that in the present embodiment, before step S1045, it is also necessary to judge again sampled point q whether with
Barrier zone A2 collisionless, to be reaffirmed to the sampled point for being added to vertex set.
Specifically, before above-mentioned the step of first sampled point is added to vertex set, further includes: to the first sampled point
Collision detection is carried out, determines first sampled point and the barrier zone collisionless.
As shown in figure 5, in a specific embodiment, giving the stream for generating the process of vertex set V in step S104
Journey schematic diagram.
In addition, in the present embodiment, the calculating process for introducing the field intensity value that potential field calculates sampled point can be such that
Potential field is introduced in undirected graph, calculates each repulsion from barrier of sampled point point in network
Power psWith attraction pg, the field intensity value of the sampled point is then calculated by repulsive force and attraction:
Uq=ps+pg。
Specifically, repulsive force p of the sampled point from barriersCalculating process it is as follows:
Current sampling point q (coordinate (x, y)) and barrier center (coordinate (x are calculated according to distance value calculation formula0,y0))
The distance between d:
Pre-determined distance threshold value D, if d≤D, repulsive force psCalculation formula are as follows:
Wherein, d2=d/100+1, d0=2, C=800, and wherein d0It can according to need with C and be arranged to other values.
If d > D, ps=0.
It should be noted that in the present embodiment, D=100, or can according to the actual needs, be arranged it is other away from
From threshold value.
The corresponding attraction of sampled point are as follows:
pg=α * ((x-g1)2+(y-g1)2)
Wherein, α is constant, and in one embodiment, α=1/700, (g1,g2) it is coordinate of ground point.
It should be noted that in the present embodiment, can also be calculated according to potential field function setup others field intensity value is introduced
Formula, in the present embodiment without limitation.
Step S106: corresponding edge collection is generated according to preset planner according to the vertex set.
After the construction complete of the vertex set of undirected graph, corresponding edge collection E can be constructed according to vertex set V,
The sampled point q in vertex set V is attached between each other, to generate edge collection E.
Specifically, as shown in fig. 6, step S106 includes:
Step S1061: traversing the second sampled point for including in the vertex set, for the second sampled point traversed,
The adjoint point of default points threshold value corresponding with second sampled point is determined in the vertex set；
Step S1062: the second sampled point and adjoint point are connected by preset planner；
Step S1063: in the case where successful connection, the side for connecting second sampled point and adjoint point is added to edge
Collection.
That is, determining its preset by distance value calculating for each sampled point q for including in vertex set
The adjoint point (determining k adjoint point corresponding with sampled point q) of number threshold value (k), then by preset planner (for example, local
Planner) sampled point q and adjoint point q ' are connected, if successful connection (i.e. Lothrus apterus local path), side (q, q') is added
Into edge collection E.Until all adjoint points are connected or abandon.
It should be noted that in the present embodiment, the setting of points threshold value k has been related to the number of sampled point in slype
K value can be arranged as far as possible by amount in order to improve the quantity of sampled point in slype as far as possible in the case where < n
Greatly, it but also will increase the calculation amount of edge collection E construction process simultaneously.
To each sampled point be performed both by determining above-mentioned adjoint point, planner connection, addition edge collection/discarding process it
Afterwards, that is, the building of edge collection E is completed.
For example, as shown in fig. 7, Fig. 7 gives the building example of undirected graph.
It should be noted that being to pass through meter in the process for determining k adjoint point corresponding with sampled point q in the present embodiment
The distance between other sampled points in sampled point and vertex set value is calculated to determine.That is, above-mentioned in the vertex set
The step of adjoint point of middle determination default points threshold value corresponding with second sampled point, further includes: calculate second sampling
The second distance value between the second sampled point that point and vertex set include；Big row is arrived from childhood to second distance value progress
Sequence obtains the second sampled point corresponding with preceding default points threshold value second distance value as adjoint point.
Step S108: according to start point information, target point information, according to preset path search algorithm, at the edge
It concentrates and searches optimal route as target route.
After undirected graph building is completed, unmanned plane route can be searched in the undirected graph, and can be with
Select different path search algorithms as needed to search target route of the optimal route as unmanned plane route planning.
For example, being searched in edge collection E apart from shortest route, by what is found according to preset fast search algorithm
Apart from shortest route as target route.
It should be noted that in the present embodiment, not being defined to the specific algorithm of route search, can be any
The searching algorithm that respective routes are searched in undirected graph belongs to the protection scope of the embodiment of the present invention.
As shown in figure 8, illustrating the flow diagram of above-mentioned unmanned plane route planning method.
Using above-mentioned unmanned plane route planning method, can to the greatest extent may be used in the case where not increasing sampling number and sampled point quantity
The sampled point at the reservation barrier edge more than energy, increases the sampled point quantity in slype, significantly more efficient completion route map
Building.
As shown in figure 9, Fig. 9 gives in the case where n=50, n=100, n=200, the vertex in goal programming region
The corresponding schematic diagram of collection is given at the accompanying drawings for being not introduced into the vertex set of PRM algorithm building of potential field relative to Figure 10
It says, structurally, the sampled point quantity in slype obviously increases the vertex set in Fig. 9.
Further, as shown in figure 11, under identical n value, for being put down in the slype under the selection of different k values
Equal sampling number gives the average sample points in the slype under the PRM algorithm for being not introduced into potential field in Figure 11 and adopts
The average sample in slype under the unmanned plane route planning method provided with the present invention is counted, slype of the invention
In sampled point quantity obviously increase.
After above-mentioned unmanned plane paths planning method, during planning unmanned plane route, can
Random uniform sampling is carried out in row region, sampled point is not only needed detect with the collisionless of barrier zone, it is also necessary to draw
Enter potential field to calculate the field intensity value of the sampled point, only in the case where the field intensity value being calculated is greater than certain value,
The sampled point is added in vertex set；Then corresponding edge collection is generated by planner according to the vertex set, then basis
The undirected graph progress route searching of vertex set, edge collection composition, to obtain the target route of unmanned plane planning.Namely
It says, by introducing potential field, the sampled point as much as possible remained in area of feasible solutions in slype is increased in slype
The par of sampled point.
Do not had compared to RRT algorithm or PRM algorithm using unmanned plane route planning scheme provided in an embodiment of the present invention
Have in the case where increasing sampled point quantity, the par of sampled point in slype is improved, to improve route planning
Accuracy and whole efficiency.
As shown in figure 12, the embodiment of the present invention also provides a kind of unmanned plane route planning device.Specifically, such as Figure 12 institute
Show, the unmanned plane route planning device includes:
Route planning information determination module 102, for obtaining route planning information, the route planning information includes target
Planning region, start point information, target point information, the goal programming region includes area of feasible solutions and barrier zone；
Vertex set constructing module 104, for determining the first sampling in the area of feasible solutions by random uniform sampling mode
Point determines first sampled point and the barrier zone collisionless, calculates the corresponding field intensity value of first sampled point, determines
The field intensity value is greater than or equal to preset field strength threshold value, and first sampled point is added to vertex set；
Edge collection constructing module 106, for generating corresponding edge collection according to preset planner according to the vertex set；
Route planning module 108, for according to start point information, target point information, according to preset path search algorithm,
It is concentrated at the edge and searches optimal route as target route.
In above-mentioned unmanned plane route planning device, during planning unmanned plane route, in area of feasible solutions
Random uniform sampling is carried out, sampled point is not only needed detect with the collisionless of barrier zone, it is also necessary to introduce potential field pair
The field intensity value of the sampled point is calculated, only in the case where the field intensity value being calculated is greater than certain value, just by the sampling
Point is added in vertex set；Then corresponding edge collection is generated by planner according to the vertex set, then according to vertex set, side
The undirected graph of edge collection composition carries out route searching, to obtain the target route of unmanned plane planning.That is, passing through introducing
Potential field, the sampled point as much as possible remained in area of feasible solutions in slype increase the flat of sampled point in slype
Equal quantity.
Do not had compared to RRT algorithm or PRM algorithm using unmanned plane route planning scheme provided in an embodiment of the present invention
Have in the case where increasing sampled point quantity, the par of sampled point in slype is improved, to improve route planning
Accuracy and whole efficiency.
Vertex set constructing module 104 is also used to the sampling number for including in the vertex set in one of the embodiments,
In the case that amount is less than preset points threshold value, circulation executes described true in the area of feasible solutions by random uniform sampling mode
Fixed first sampled point, determines first sampled point and the barrier zone collisionless, and it is corresponding to calculate first sampled point
Field intensity value determines that the field intensity value is greater than or equal to preset field strength threshold value, first sampled point is added to vertex set.
Vertex set constructing module 104 is also used to calculate the first sampled point relative to the barrier in one of the embodiments,
Hinder the repulsive force in region；Attraction of first sampled point relative to the barrier zone is calculated according to the target point information；Base
In the repulsive force and the attraction, the corresponding field intensity value of first sampled point is calculated.
Between the sampled point that first sampled point and the vertex set include is calculated in one of the embodiments,
One distance value, determine described in the first distance value that is calculated be greater than 0.
Edge collection constructing module 106 is also used to traverse second in the vertex set included in one of the embodiments,
Sampled point determines preset corresponding with second sampled point for the second sampled point traversed in the vertex set
The adjoint point of number threshold value；The second sampled point and adjoint point are connected by preset planner；In the case where successful connection, by connecting
The side for stating the second sampled point and adjoint point is added to edge collection.
Edge collection constructing module 106 is also used to calculate second sampled point and vertex set in one of the embodiments,
The second distance value between the second sampled point for including；Big sequence is arrived to second distance value progress from childhood, is obtained with before
Default corresponding second sampled point of threshold value second distance value of counting is as adjoint point.
Route planning module 108 is also used to according to preset fast search algorithm, described in one of the embodiments,
Edge, which is concentrated, to be searched apart from shortest route, using the shortest route of the distance found as target route.
Figure 13 shows the internal structure chart of computer equipment in one embodiment.The computer equipment specifically can be clothes
Business device.As shown in figure 13, which includes processor, memory and the network interface connected by system bus.Its
In, memory includes non-volatile memory medium and built-in storage.The non-volatile memory medium of the computer equipment is stored with
Operating system can also be stored with computer program, when which is executed by processor, processor may make to realize nobody
Machine route planning method.Computer program can also be stored in the built-in storage, it, can when which is executed by processor
So that processor executes unmanned plane route planning method.Network interface is for communication with the outside.Those skilled in the art can
To understand, structure shown in Figure 13, only the block diagram of part-structure relevant to application scheme, is not constituted to this Shen
Please the restriction of computer equipment that is applied thereon of scheme, specific computer equipment may include than as shown in the figure more or
Less component perhaps combines certain components or with different component layouts.
In one embodiment, unmanned plane route planning method provided by the present application can be implemented as a kind of computer program
Form, computer program can run in computer equipment as shown in fig. 13 that.It can be stored in the memory of computer equipment
Form each process template of unmanned plane route planning device.
A kind of computer equipment, including memory and processor, the memory are stored with computer program, the calculating
When machine program is executed by the processor, so that the processor executes following steps:
Above-mentioned computer equipment, when above-mentioned computer program is executed by the processor in one of the embodiments, also
For executing following steps:
Route planning information is obtained, the route planning information includes goal programming region, start point information, target point letter
Breath, the goal programming region includes area of feasible solutions and barrier zone；
Determine the first sampled point in the area of feasible solutions by random uniform sampling mode, determine first sampled point with
The barrier zone collisionless calculates the corresponding field intensity value of first sampled point, and it is pre- to determine that the field intensity value is greater than or equal to
If field strength threshold value, first sampled point is added to vertex set；
Corresponding edge collection is generated according to preset planner according to the vertex set；
It concentrates and is searched most at the edge according to preset path search algorithm according to start point information, target point information
Major path is as target route.
In above-mentioned computer equipment, during planning unmanned plane route, carried out in area of feasible solutions random
Uniform sampling not only needs sampled point detect with the collisionless of barrier zone, it is also necessary to introduce potential field to the sampled point
Field intensity value calculated, only the field intensity value being calculated be greater than certain value in the case where, just the sampled point is added to
In vertex set；Then corresponding edge collection is generated by planner according to the vertex set, is then formed according to vertex set, edge collection
Undirected graph carry out route searching, with obtain unmanned plane planning target route.That is, by introducing potential field, to the greatest extent
The sampled point remained in area of feasible solutions in slype more than possible, increases the par of sampled point in slype.
Do not had compared to RRT algorithm or PRM algorithm using unmanned plane route planning scheme provided in an embodiment of the present invention
Have in the case where increasing sampled point quantity, the par of sampled point in slype is improved, to improve route planning
Accuracy and whole efficiency.
A kind of computer readable storage medium is stored with computer program, when the computer program is executed by processor,
So that the processor executes following steps:
Route planning information is obtained, the route planning information includes goal programming region, start point information, target point letter
Breath, the goal programming region includes area of feasible solutions and barrier zone；
Determine the first sampled point in the area of feasible solutions by random uniform sampling mode, determine first sampled point with
The barrier zone collisionless calculates the corresponding field intensity value of first sampled point, and it is pre- to determine that the field intensity value is greater than or equal to
If field strength threshold value, first sampled point is added to vertex set；
Corresponding edge collection is generated according to preset planner according to the vertex set；
It concentrates and is searched most at the edge according to preset path search algorithm according to start point information, target point information
Major path is as target route.
In above-mentioned computer readable storage medium, during planning unmanned plane route, in area of feasible solutions
Random uniform sampling is carried out, sampled point is not only needed detect with the collisionless of barrier zone, it is also necessary to introduce potential field pair
The field intensity value of the sampled point is calculated, only in the case where the field intensity value being calculated is greater than certain value, just by the sampling
Point is added in vertex set；Then corresponding edge collection is generated by planner according to the vertex set, then according to vertex set, side
The undirected graph of edge collection composition carries out route searching, to obtain the target route of unmanned plane planning.That is, passing through introducing
Potential field, the sampled point as much as possible remained in area of feasible solutions in slype increase the flat of sampled point in slype
Equal quantity.
Do not had compared to RRT algorithm or PRM algorithm using unmanned plane route planning scheme provided in an embodiment of the present invention
Have in the case where increasing sampled point quantity, the par of sampled point in slype is improved, to improve route planning
Accuracy and whole efficiency.
It should be noted that above-mentioned unmanned plane route planning method, unmanned plane route planning device, computer equipment and meter
Calculation machine readable storage medium storing program for executing belongs to the same inventive concept, and unmanned plane route planning method, calculates unmanned plane route planning device
Content involved in machine equipment and computer readable storage medium can be mutually applicable in.
Those of ordinary skill in the art will appreciate that realizing all or part of the process in above-described embodiment method, being can be with
Relevant hardware is instructed to complete by computer program, the program can be stored in a non-volatile computer and can be read
In storage medium, the program is when being executed, it may include such as the process of the embodiment of above-mentioned each method.Wherein, provided herein
Each embodiment used in any reference to memory, storage, database or other media, may each comprise non-volatile
And/or volatile memory.Nonvolatile memory may include that read-only memory (ROM), programming ROM (PROM), electricity can be compiled
Journey ROM (EPROM), electrically erasable ROM (EEPROM) or flash memory.Volatile memory may include random access memory
(RAM) or external cache.By way of illustration and not limitation, RAM is available in many forms, such as static state RAM
(SRAM), dynamic ram (DRAM), synchronous dram (SDRAM), double data rate sdram (DDRSDRAM), enhanced SDRAM
(ESDRAM), synchronization link (Synchlink) DRAM (SLDRAM), memory bus (Rambus) directly RAM (RDRAM), straight
Connect memory bus dynamic ram (DRDRAM) and memory bus dynamic ram (RDRAM) etc..
Each technical characteristic of above embodiments can be combined arbitrarily, for simplicity of description, not to above-described embodiment
In each technical characteristic it is all possible combination be all described, as long as however, the combination of these technical characteristics be not present lance
Shield all should be considered as described in this specification.
The several embodiments of the application above described embodiment only expresses, the description thereof is more specific and detailed, but simultaneously
The limitation to the application the scope of the patents therefore cannot be interpreted as.It should be pointed out that for those of ordinary skill in the art
For, without departing from the concept of this application, various modifications and improvements can be made, these belong to the guarantor of the application
Protect range.Therefore, the scope of protection shall be subject to the appended claims for the application patent.
Claims (10)
1. a kind of unmanned plane route planning method characterized by comprising
Route planning information is obtained, the route planning information includes goal programming region, start point information, target point information,
The goal programming region includes area of feasible solutions and barrier zone；
Determine the first sampled point in the area of feasible solutions by random uniform sampling mode, determine first sampled point with it is described
Barrier zone collisionless calculates the corresponding field intensity value of first sampled point, and it is preset to determine that the field intensity value is greater than or equal to
First sampled point is added to vertex set by field strength threshold value；
Corresponding edge collection is generated according to preset planner according to the vertex set；
It is concentrated at the edge according to preset path search algorithm according to start point information, target point information and searches optimal road
Line is as target route.
2. unmanned plane route planning method according to claim 1, which is characterized in that the method also includes:
The sampled point quantity that the vertex set includes be less than preset points threshold value in the case where, circulation execute described in by with
Machine uniform sampling mode determines the first sampled point in the area of feasible solutions, determine first sampled point and the barrier zone without
Collision calculates the corresponding field intensity value of first sampled point, determines that the field intensity value is greater than or equal to preset field strength threshold value, will
The step of first sampled point is added to vertex set.
3. unmanned plane route planning method according to claim 1, which is characterized in that described to calculate first sampled point
The step of corresponding field intensity value, comprising:
Calculate repulsive force of first sampled point relative to the barrier zone；
Attraction of first sampled point relative to the barrier zone is calculated according to the target point information；
Based on the repulsive force and the attraction, the corresponding field intensity value of first sampled point is calculated.
4. unmanned plane route planning method according to claim 1, which is characterized in that described to pass through random uniform sampling side
Formula is after the step of area of feasible solutions determines the first sampled point further include:
The first distance value between the sampled point that first sampled point and the vertex set include is calculated, determines described calculate
The first distance value arrived is greater than 0.
5. unmanned plane route planning method according to claim 1, which is characterized in that it is described according to the vertex set according to
Preset planner generates the step of corresponding edge collection, comprising:
The second sampled point for including in the vertex set is traversed, for the second sampled point traversed, in the vertex set really
The adjoint point of fixed default points threshold value corresponding with second sampled point；
The second sampled point and adjoint point are connected by preset planner；
In the case where successful connection, the side for connecting second sampled point and adjoint point is added to edge collection.
6. unmanned plane route planning method according to claim 5, which is characterized in that described to be determined in the vertex set
The step of adjoint point of default points threshold value corresponding with second sampled point, further includes:
Calculate the second distance value between the second sampled point that second sampled point and vertex set include；
Big sequence is arrived to second distance value progress from childhood, is obtained corresponding with preceding default points threshold value second distance value
Second sampled point is as adjoint point.
7. unmanned plane route planning method according to claim 1, which is characterized in that described according to start point information, mesh
Pointing information is concentrated at the edge according to preset path search algorithm and searches the step of optimal route is as target route,
Further include:
According to preset fast search algorithm, concentrates and searched apart from shortest route, most by the distance found at the edge
Short route is as target route.
8. a kind of unmanned plane route planning device characterized by comprising
Route planning information determination module, for obtaining route planning information, the route planning information includes goal programming area
Domain, start point information, target point information, the goal programming region includes area of feasible solutions and barrier zone；
Vertex set constructing module is determined for determining the first sampled point in the area of feasible solutions by random uniform sampling mode
First sampled point and the barrier zone collisionless calculate the corresponding field intensity value of first sampled point, determine the field
Intensity values are greater than or equal to preset field strength threshold value, and first sampled point is added to vertex set；
Edge collection constructing module, for generating corresponding edge collection according to preset planner according to the vertex set；
Route planning module is used for according to start point information, target point information, according to preset path search algorithm, described
Edge, which is concentrated, searches optimal route as target route.
9. a kind of computer equipment, including memory and processor, the memory is stored with computer program, the computer
When program is executed by the processor, so that the processor executes the step such as any one of claims 1 to 7 the method
Suddenly.
10. a kind of computer readable storage medium is stored with computer program, when the computer program is executed by processor,
So that the processor is executed such as the step of any one of claims 1 to 7 the method.
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910151761.XA CN109737967A (en) | 2019-02-28 | 2019-02-28 | Unmanned plane paths planning method, device, storage medium and computer equipment |
| PCT/CN2019/098002 WO2020173044A1 (en) | 2019-02-28 | 2019-07-26 | Route planning method and device for unmanned aerial vehicle, storage medium and computer apparatus |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910151761.XA CN109737967A (en) | 2019-02-28 | 2019-02-28 | Unmanned plane paths planning method, device, storage medium and computer equipment |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN109737967A true CN109737967A (en) | 2019-05-10 |
Family
ID=66368690
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201910151761.XA Pending CN109737967A (en) | 2019-02-28 | 2019-02-28 | Unmanned plane paths planning method, device, storage medium and computer equipment |
Country Status (2)
| Country | Link |
|---|---|
| CN (1) | CN109737967A (en) |
| WO (1) | WO2020173044A1 (en) |
Cited By (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110262567A (en) * | 2019-06-27 | 2019-09-20 | 深圳市道通智能航空技术有限公司 | A kind of path relaying space of points generation method, device and unmanned plane |
| CN110414588A (en) * | 2019-07-23 | 2019-11-05 | 广东小天才科技有限公司 | Picture labeling method and device, computer equipment and storage medium |
| CN111060103A (en) * | 2019-12-11 | 2020-04-24 | 安徽工程大学 | Path planning method for local dynamic optimization and obstacle avoidance |
| WO2020173044A1 (en) * | 2019-02-28 | 2020-09-03 | 中国科学院深圳先进技术研究院 | Route planning method and device for unmanned aerial vehicle, storage medium and computer apparatus |
| CN112162566A (en) * | 2020-09-04 | 2021-01-01 | 深圳市创客火科技有限公司 | Route planning method, electronic device and computer-readable storage medium |
| CN112669445A (en) * | 2020-12-23 | 2021-04-16 | 中国人民武装警察部队警官学院 | Check method, system and storage medium applied to fighting simulation data |
| CN112829797A (en) * | 2021-01-05 | 2021-05-25 | 北京全路通信信号研究设计院集团有限公司 | Method, device, equipment and storage medium for acquiring parameters of line points |
| CN113148507A (en) * | 2021-03-11 | 2021-07-23 | 上海电气慧程智能系统有限公司 | Planning method and device for biological sample access path and electronic equipment |
| CN113778090A (en) * | 2021-09-13 | 2021-12-10 | 上海电机学院 | Mobile robot path planning method based on ant colony optimization and PRM algorithm |
| CN114010310A (en) * | 2021-09-15 | 2022-02-08 | 苏州中科华影健康科技有限公司 | Path planning method and device, electronic equipment and storage medium |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20110035087A1 (en) * | 2009-08-10 | 2011-02-10 | Samsung Electronics Co., Ltd. | Method and apparatus to plan motion path of robot |
| CN103760904A (en) * | 2014-02-13 | 2014-04-30 | 北京工业大学 | Voice broadcast type intelligent vehicle path planning device and implementation method |
| CN108171796A (en) * | 2017-12-25 | 2018-06-15 | 燕山大学 | A kind of inspection machine human visual system and control method based on three-dimensional point cloud |
| CN108469822A (en) * | 2018-04-04 | 2018-08-31 | 天津理工大学 | A kind of interior blind-guidance robot paths planning method in a dynamic environment |
| CN108582073A (en) * | 2018-05-02 | 2018-09-28 | 北京邮电大学 | A kind of quick barrier-avoiding method of mechanical arm based on improved random road sign Map Method |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104155998B (en) * | 2014-08-27 | 2017-08-25 | 电子科技大学 | A kind of path planning method based on potential field method |
| CN104516356B (en) * | 2015-01-08 | 2017-07-14 | 西北工业大学 | Dynamic disorder based on RRT evades algorithm |
| JP6606442B2 (en) * | 2016-02-24 | 2019-11-13 | 本田技研工業株式会社 | Mobile route plan generation device |
| CN108415461A (en) * | 2018-05-28 | 2018-08-17 | 济南大学 | A kind of trajectory planning of unmanned vehicle |
| CN109343528A (en) * | 2018-10-30 | 2019-02-15 | 杭州电子科技大学 | A kind of energy-efficient unmanned plane path planning barrier-avoiding method |
| CN109737967A (en) * | 2019-02-28 | 2019-05-10 | 中国科学院深圳先进技术研究院 | Unmanned plane paths planning method, device, storage medium and computer equipment |
-
2019
- 2019-02-28 CN CN201910151761.XA patent/CN109737967A/en active Pending
- 2019-07-26 WO PCT/CN2019/098002 patent/WO2020173044A1/en active Application Filing
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20110035087A1 (en) * | 2009-08-10 | 2011-02-10 | Samsung Electronics Co., Ltd. | Method and apparatus to plan motion path of robot |
| CN103760904A (en) * | 2014-02-13 | 2014-04-30 | 北京工业大学 | Voice broadcast type intelligent vehicle path planning device and implementation method |
| CN108171796A (en) * | 2017-12-25 | 2018-06-15 | 燕山大学 | A kind of inspection machine human visual system and control method based on three-dimensional point cloud |
| CN108469822A (en) * | 2018-04-04 | 2018-08-31 | 天津理工大学 | A kind of interior blind-guidance robot paths planning method in a dynamic environment |
| CN108582073A (en) * | 2018-05-02 | 2018-09-28 | 北京邮电大学 | A kind of quick barrier-avoiding method of mechanical arm based on improved random road sign Map Method |
Non-Patent Citations (2)
| Title |
|---|
| 盛亮，等: "《启发式方法在机器人路径规划优化中的应用综述》", 《电光与控制》 * |
| 贾庆轩，等: "《基于A*算法的空间机械臂避障路径规划》", 《机械工程学报》 * |
Cited By (15)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2020173044A1 (en) * | 2019-02-28 | 2020-09-03 | 中国科学院深圳先进技术研究院 | Route planning method and device for unmanned aerial vehicle, storage medium and computer apparatus |
| CN110262567A (en) * | 2019-06-27 | 2019-09-20 | 深圳市道通智能航空技术有限公司 | A kind of path relaying space of points generation method, device and unmanned plane |
| CN110262567B (en) * | 2019-06-27 | 2022-04-15 | 深圳市道通智能航空技术股份有限公司 | Path relay point space generation method and device and unmanned aerial vehicle |
| CN110414588A (en) * | 2019-07-23 | 2019-11-05 | 广东小天才科技有限公司 | Picture labeling method and device, computer equipment and storage medium |
| CN111060103B (en) * | 2019-12-11 | 2021-12-10 | 安徽工程大学 | Path planning method for local dynamic optimization and obstacle avoidance |
| CN111060103A (en) * | 2019-12-11 | 2020-04-24 | 安徽工程大学 | Path planning method for local dynamic optimization and obstacle avoidance |
| CN112162566A (en) * | 2020-09-04 | 2021-01-01 | 深圳市创客火科技有限公司 | Route planning method, electronic device and computer-readable storage medium |
| CN112162566B (en) * | 2020-09-04 | 2024-01-16 | 深圳市创客火科技有限公司 | Route planning method, electronic device and computer readable storage medium |
| CN112669445A (en) * | 2020-12-23 | 2021-04-16 | 中国人民武装警察部队警官学院 | Check method, system and storage medium applied to fighting simulation data |
| CN112829797A (en) * | 2021-01-05 | 2021-05-25 | 北京全路通信信号研究设计院集团有限公司 | Method, device, equipment and storage medium for acquiring parameters of line points |
| CN112829797B (en) * | 2021-01-05 | 2023-01-06 | 北京全路通信信号研究设计院集团有限公司 | Method, device, equipment and storage medium for acquiring parameters of line points |
| CN113148507A (en) * | 2021-03-11 | 2021-07-23 | 上海电气慧程智能系统有限公司 | Planning method and device for biological sample access path and electronic equipment |
| CN113778090A (en) * | 2021-09-13 | 2021-12-10 | 上海电机学院 | Mobile robot path planning method based on ant colony optimization and PRM algorithm |
| CN114010310A (en) * | 2021-09-15 | 2022-02-08 | 苏州中科华影健康科技有限公司 | Path planning method and device, electronic equipment and storage medium |
| CN114010310B (en) * | 2021-09-15 | 2023-10-13 | 苏州中科华影健康科技有限公司 | Path planning method and device, electronic equipment and storage medium |
Also Published As
| Publication number | Publication date |
|---|---|
| WO2020173044A1 (en) | 2020-09-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN109737967A (en) | Unmanned plane paths planning method, device, storage medium and computer equipment | |
| Wang et al. | Ltp: Lane-based trajectory prediction for autonomous driving | |
| Lou et al. | Map-matching for low-sampling-rate GPS trajectories | |
| Frahling et al. | Coresets in dynamic geometric data streams | |
| US11305780B2 (en) | Road condition status prediction method, device, and server, and storage medium | |
| CN113467456B (en) | Path planning method for specific target search under unknown environment | |
| Su et al. | Prioritized architecture sampling with monto-carlo tree search | |
| CN104462190B (en) | A kind of online position predicting method excavated based on magnanimity space tracking | |
| Peres et al. | Mobile geometric graphs: Detection, coverage and percolation | |
| Liu et al. | Multi-task-oriented vehicular crowdsensing: A deep learning approach | |
| CN113485429B (en) | Route optimization method and device for air-ground cooperative traffic inspection | |
| CN109271562B (en) | Current expense determines method, road-net node relational model construction method and device | |
| CN109931942A (en) | Robot path generation method, device, robot and storage medium | |
| CN112884256B (en) | Path planning method and device, computer equipment and storage medium | |
| CN105447595A (en) | Scenic spot route recommending method based on spectral clustering algorithm | |
| CN103365886A (en) | Method for querying space events in internet of vehicles and optimizing querier | |
| CN111462824B (en) | Reachable probability query method for gene regulation network | |
| CN109741227A (en) | One kind is based on nearest neighbor algorithm prediction people room consistency processing method and system | |
| Ai et al. | DRVAT: Exploring RSSI series representation and attention model for indoor positioning | |
| CN106289281A (en) | A kind of double mode map-matching method theoretical based on three evidence DS | |
| CN109558518A (en) | The method, apparatus and storage medium of community discovery in a kind of determining social networks | |
| CN104023392B (en) | The method and apparatus for determining the position of WAP | |
| Comets et al. | Two-dimensional Brownian random interlacements | |
| CN108683599B (en) | Preprocessing-based method and system for determining maximum flow of flow network | |
| Kim et al. | Distributed tracking in a large-scale network of smart cameras |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| RJ01 | Rejection of invention patent application after publication |
Application publication date: 20190510 |
|
| RJ01 | Rejection of invention patent application after publication |