UAV Flight Path Generating Method and Device

• US 20190145778A1
• Filed: 01/31/2018
• Published: 05/16/2019
• Est. Priority Date: 11/13/2017
• Status: Active Grant

• Current Assignee: Shenzhen University (Guangdong Education Department)
• Original Assignee: Shenzhen University (Guangdong Education Department)
• Inventors: HUANG, Hui, XIE, Ke
• Granted Patent: US 10,663,300 B2
• Time in Patent Office: Days
• CPC Class Codes: B64U 10/14 with four distinct rotor axes, e.g. quadcopters
• CPC Class Codes: B64U 2101/30 for imaging, photography or videography
• CPC Class Codes: B64U 2201/00 UAVs characterised by their flight controls
• CPC Class Codes: B64U 2201/10 autonomous, i.e. by navigating independently from ground or air stations, e.g. by using inertial navigation systems [INS]
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G05D 1/101 specially adapted for aircraft
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

This invention proposes a new method and software to generate a path with good quality for aerial video shooting in large scale scenes. Using a coarse 2.5D model of a scene, this path generation method consists of several steps: first the user is expected to specify a set of landmarks and designate a superset of key-views for each landmark; our system then automatically generates and evaluates a variety of local camera moves for observing each landmark, which are smooth and collision-free; then automatically determines the optimal order in which the landmarks should be visited, chaining the local camera moves into a single continuous trajectory. Thus, users are able to focus on specifying the visual content that should be captured by the aerial video, rather than on the difficult lower level aspects of designing and specifying the precise drone and camera motions.

Claims

1. A UAV flight path generating method, comprising:

generating at least one ordered key-view subset based on the key-views of the landmark in the scene;

generating local flight paths according to the ordered key-view subset, and defining the local cost function of the local flight paths;

constructing a generalized traveling salesman problem (STSP) based on the local flight paths, getting at least one global flight path to visit at least one landmark by solving the STSP problem, and defining the global cost function of the global flight path;

generating the final cost function based on both the local cost function and the global cost function, and generating the flight path of the UAV by selecting a local flight path and a global flight path according to the result of the solution.

2. The UAV flight path generating method according to claim 1, wherein generating local flight paths according to the ordered key-view subset, comprises:

building a generalized cylinder surface surrounding these landmarks in cylindrical coordinates;

under the constraint with that the polar radius of key-views location in the generalized cylindrical coordinate system is larger than the polar radius of the cylinder, connecting the positions of the key-views in the ordered key-view subset using a B-Spline interpolation method, and generating the local flight path of the landmark.

3. The UAV flight path generating method according to claim 2, wherein building a generalized cylinder surface surrounding these landmarks in cylindrical coordinates, comprises:

building a generalized cylindrical coordinate system with landmark as center, and constructing the boundary curve of landmarks under the plane polar coordinates of generalized cylindrical coordinate system;

extending and smoothing the boundary curve, and generating the bounding curve of the landmarks on the ground projection;

building the cylinder surface based on the bounding curve in the generalized cylindrical coordinate system.

4. The UAV flight path generating method according to claim 1, wherein constructing a generalized traveling salesman problem (STSP) based on the local flight paths, getting at least one global flight path to visit at least one landmark by solving the STSP problem, comprises:

generating all kinds of different visit order of at least one landmark;

generating two nodes with opposite directions corresponding to the landmark according to the local flight path, and generating the graph structure located outside the landmark space according to the two nodes with opposite directions and the access sequence corresponding to at least one landmark;

based on the graph structure, solving the STSP problem, and obtaining the shortest migration trajectory to visit at least one landmark;

according to the shortest migration trajectory, generating the global flight path using a B-spline.

5. The UAV flight path generating method according to claim 1, wherein before generating at least one ordered key-view subset based on the key-views of the landmark in the scene, the method further comprises:

selecting at least one key-view of one landmark in the scene for generating a set of key-views, wherein at least one key-view includes mandatory key-views and/or the optional ones.

6. The UAV flight path generating method according to claim 1, wherein before constructing a generalized traveling salesman problem (STSP) based on the local flight paths, getting at least one global flight path to visit at least one landmark by solving the STSP problem, the method further comprises:

determining a set number of local flight paths with the lowest cost by solving the local cost function of each local flight path of the landmark, so as to construct a STSP problem.

7. The UAV flight path generating method according to claim 1, wherein both the local cost function of the local flight path and the global cost function of the global flight path are related to curvature, viewport direction and the length of path.

8. A computer readable storage medium comprising computer readable instructions, wherein the computer readable instructions enable, when being executed, a processor to at least perform the operations of:

generating at least one ordered key-view subset based on the key-views of the landmark in the scene;

generating local flight paths according to the ordered key-view subset, and defining the local cost function of the local flight paths;

constructing a generalized traveling salesman problem (STSP) based on the local flight paths, getting at least one global flight path to visit at least one landmark by solving the STSP problem, and defining the global cost function of the global flight path;

generating the final cost function based on both the local cost function and the global cost function, and generating the flight path of the UAV by selecting a local flight path and a global flight path according to the result of the solution.

9. The computer readable storage medium according to claim 8, wherein when performing the step of generating local flight paths according to the ordered key-view subset, the instructions enable the processor to perform the operations of:

building a generalized cylinder surface surrounding these landmarks in cylindrical coordinates;

under the constraint with that the polar radius of key-views location in the generalized cylindrical coordinate system is larger than the polar radius of the cylinder, connecting the positions of the key-views in the ordered key-view subset using a B-Spline interpolation method, and generating the local flight path of the landmark.

10. The computer readable storage medium according to claim 9, wherein when performing the step of building a generalized cylinder surface surrounding these landmarks in cylindrical coordinates, the instructions enable the processor to perform the operations of:

building a generalized cylindrical coordinate system with landmark as center, and constructing the boundary curve of landmarks under the plane polar coordinates of generalized cylindrical coordinate system;

extending and smoothing the boundary curve, and generating the bounding curve of the landmarks on the ground projection;

building the cylinder surface based on the bounding curve in the generalized cylindrical coordinate system.

11. The computer readable storage medium according to claim 8, wherein when performing the step of constructing a generalized traveling salesman problem (STSP) based on the local flight paths, getting at least one global flight path to visit at least one landmark by solving the STSP problem, the instructions enable the processor to perform the operations of:

generating all kinds of different visit orders of at least one landmark;

generating two nodes with opposite directions corresponding to the landmark according to the local flight path, and generating the graph structure located outside the landmark space according to the two nodes with opposite directions and the access sequence corresponding to at least one landmark;

based on the graph structure, solving the STSP problem, and obtaining the shortest migration trajectory to visit at least one landmark;

according to the shortest migration trajectory, generating the global flight path using a B-spline.

12. The computer readable storage medium according to claim 8, wherein before performing the step of generating at least one ordered key-view subset based on the key-views of the landmark in the scene, the instructions further enable the processor to perform the operations of:

selecting at least one key-view of one landmark in the scene for generating a set of key-views, wherein at least one key-view includes mandatory key-views and/or the optional ones.

13. The computer readable storage medium according to claim 8, wherein before performing the step of constructing a generalized traveling salesman problem (STSP) based on the local flight paths, getting at least one global flight path to visit at least one landmark by solving the STSP problem, the instructions further enable the processor to perform the operations of:

determining a set number of local flight paths with the lowest cost by solving the local cost function of each local flight path of the landmark, so as to construct a STSP problem.

14. The computer readable storage medium according to claim 8, wherein both the local cost function of the local flight path and the global cost function of the global flight path are related to curvature, viewport direction and the length of path.

15. An computer device, comprising:

a memory comprising computer readable instructions; and

a processor configured to, when the computer readable instructions are executed, perform the operations of;

generating at least one ordered key-view subset based on the key-views of the landmark in the scene;

generating local flight paths according to the ordered key-view subset, and defining the local cost function of the local flight paths;

constructing a generalized traveling salesman problem (STSP) based on the local flight paths, getting at least one global flight path to visit at least one landmark by solving the STSP problem, and defining the global cost function of the global flight path;

generating the final cost function based on both the local cost function and the global cost function, and generating the flight path of the UAV by selecting a local flight path and a global flight path according to the result of the solution.

16. The computer device according to claim 15, wherein when performing the step of generating local flight paths according to the ordered key-view subset, the instructions enable the processor to perform the operations of:

building a generalized cylinder surface surrounding these landmarks in cylindrical coordinates;

under the constraint with that the polar radius of key-views location in the generalized cylindrical coordinate system is larger than the polar radius of the cylinder, connecting the positions of the key-views in the ordered key-view subset using a B-Spline interpolation method, and generating the local flight path of the landmark.

17. The computer device according to claim 16, wherein when performing the step of building a generalized cylinder surface surrounding these landmarks in cylindrical coordinates, the instructions enable the processor to perform the operations of:

building a generalized cylindrical coordinate system with landmark as center, and constructing the boundary curve of landmarks under the plane polar coordinates of generalized cylindrical coordinate system;

extending and smoothing the boundary curve, and generating the bounding curve of the landmarks on the ground projection;

building the cylinder surface based on the bounding curve in the generalized cylindrical coordinate system.

18. The computer device according to claim 15, wherein when performing the step of constructing a generalized traveling salesman problem (STSP) based on the local flight paths, getting at least one global flight path to visit at least one landmark by solving the STSP problem, the instructions enable the processor to perform the operations of:

generating all kinds of different visit orders of at least one landmark;

generating two nodes with opposite directions corresponding to the landmark according to the local flight path, and generating the graph structure located outside the landmark space according to the two nodes with opposite directions and the access sequence corresponding to at least one landmark;

based on the graph structure, solving the STSP problem, and obtaining the shortest migration trajectory to visit at least one landmark;

according to the shortest migration trajectory, generating the global flight path using a B-spline.

19. The computer device according to claim 15, wherein before performing the step of generating at least one ordered key-view subset based on the key-views of the landmark in the scene, the instructions further enable the processor to perform the operations of:

selecting at least one key-view of one landmark in the scene for generating a set of key-views, wherein at least one key-view includes mandatory key-views and/or the optional ones.

20. The computer device according to claim 15, wherein before performing the step of constructing a generalized traveling salesman problem (STSP) based on the local flight paths, getting at least one global flight path to visit at least one landmark by solving the STSP problem, the instructions further enable the processor to perform the operations of:

determining a set number of local flight paths with the lowest cost by solving the local cost function of each local flight path of the landmark, so as to construct a STSP problem.

21. The computer device according to claim 15, wherein both the local cost function of the local flight path and the global cost function of the global flight path are related to curvature, viewport direction and the length of path.