METHODS AND SYSTEMS FOR AUTONOMOUS GENERATION OF SHORTEST LATERAL PATHS FOR UNMANNED AERIAL SYSTEMS

• US 20170116863A1
• Filed: 07/08/2016
• Published: 04/27/2017
• Est. Priority Date: 07/14/2015
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: QUEREJETA MASAVEU, Carlos, VALLS HERNNDEZ, Ernesto, NAVARRO FLIX, Francisco A., SNCHEZ TAMARGO, David, CUADRADO SNCHEZ, Jess
• Granted Patent: US 10,032,383 B2
• Time in Patent Office: Days
• 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: G08G 5/0052 for cruising combined instruments indicating more than one navigational value G01C23/00
• CPC Class Codes: G08G 5/006 in accordance with predefined flight zones, e.g. to avoid prohibited zones
• CPC Class Codes: G08G 5/0069 specially adapted for an unmanned aircraft

Abstract

Methods and systems for autonomous generation of shortest lateral paths for unmanned aerial systems are described. An example method includes defining an area between a source point and a target point; identifying a first no flight zone within the area; identifying a second no flight zone outside of the area; estimating a first computation time to determine a first lateral path between the source point and the target point, the estimating to consider the first no flight zone, the estimating not to consider the second no flight zone; comparing the first computation time to a reference computation time; in response to the first computation time not satisfying a threshold of the reference computation time, modifying the first no flight zone to be a third no flight zone; and estimating a second computation time to determine a second lateral path between the source point and the target point, the estimating to consider the third no flight zone.

Claims

1. A method, comprising:

accessing an initial scenario including a source point, a target point, and a no flight zone;

determining a computation time for identifying a lateral path that avoids the no flight zone, the computation time being associated with a number of vertices of the no flight zone,

determining whether the determined computation time satisfies a threshold of a reference computation time;

determining a buffer area surrounding the no flight zone, wherein the buffer area is defined by an offset distance from a perimeter of the no flight zone;

constructing a visibility graph including lateral paths between the source point and the target point, the lateral paths not passing through the no flight zone, the lateral paths connecting vertices of the no flight zone; and

identifying a first lateral path of the lateral paths, the first lateral path being shorter than others of the lateral paths.

2. The method of claim 1, wherein when the initial scenario is defined in geodetic coordinates, further including converting the geodetic coordinates to cartographic coordinates.

3. The method of claim 2, wherein converting the geodetic coordinates to cartographic coordinates includes using a scale factor.

4. The method of claim 1, wherein the no flight zone includes a first no flight zone, further including a second no flight zone, and:

defining a configuration space between the source point and target point and bounded by a first line intersecting the source point and a second line intersecting the source point; and

identifying the second no flight zone as being outside of the configuration space.

5. The method of claim 4, wherein the computation time is a first computation time, in response to identifying the second no flight zone as being outside of the configuration space, determining a second computation time for obtaining a second lateral path that avoids the first no flight zone, the determining not considering the second no flight zone.

6. The method of claim 5, wherein the buffer area is a first buffer area, the visibility graph is a first visibility graph, and the lateral paths are first lateral paths, in response to the second computation time satisfying the threshold of the reference computation time, further including:

determining a second buffer area surrounding the first no flight zone;

constructing a second visibility graph including second lateral paths between the source point and the target point, the second lateral paths avoiding the first no flight zone; and

identifying a third lateral path of the second lateral paths, the third lateral path being shorter than others of the second lateral paths.

7. The method of claim 6, wherein the first lateral path is different from the third lateral path.

8. The method of claim 1, wherein when the computation time does not satisfy the threshold of the reference computation time, decreasing the number of vertices of the no flight zone.

9. The method of claim 8, wherein decreasing the number of vertices of the no flight zone includes applying a vertex reduction algorithm to the no flight zone.

10. The method of claim 8, wherein the vertex reduction algorithm includes at least one of a minimum Bounding Box algorithm or a linear simplification algorithm.

11. The method of claim 1, wherein the buffer area includes a first buffer area, further including modifying the first buffer area to reduce the size of the first buffer area to a second buffer area after identifying an angled portion of the first buffer area satisfying a threshold.

12. The method of claim 1, wherein the no flight zone includes a first no flight zone and a second no flight zone, the first no flight zone overlapping the second no flight zone.

13. The method of claim 12, further comprising, in response to identifying the first no flight zone overlapping the second no flight zone, merging the first and second no flight zones.

14. A method comprising:

defining an area between a source point and a target point;

identifying a first no flight zone within the area;

identifying a second no flight zone outside of the area;

estimating a first computation time to determine a first lateral path between the source point and the target point, the estimating to consider the first no flight zone, the estimating not to consider the second no flight zone;

comparing the first computation time to a reference computation time;

in response to the first computation time not satisfying a threshold of the reference computation time, modifying the first no flight zone to be a third no flight zone; and

estimating a second computation time to determine a second lateral path between the source point and the target point, the estimating to consider the third no flight zone.

15. The method of claim 14, further including defining a buffer area around the third no flight zone, the estimating to consider the third no flight zone.

16. The method of claim 14, further including in response to the second computation time satisfying the threshold of the reference computation time, identifying lateral paths between the source point and the target point, the lateral paths not passing through the third no flight zone, the lateral paths connecting vertices of the third no flight zone.

17. The method of claim 16, further including processing the lateral paths to identify a third lateral path, the third lateral path being shorter than others of the lateral paths.

18. The method of claim 14, wherein the third no flight zone includes a fourth no flight zone and a fifth no flight zone, the fourth no flight zone overlapping the fifth no flight zone.

19. The method of claim 18, wherein in response to identifying the fourth no flight zone overlapping the fifth no flight zone, merging the fourth and fifth no flight zones to form the third no flight zone.

20. The method of claim 14, wherein modifying the first no flight zone to be the third no flight zone includes applying a vertex reduction algorithm to the first no flight zone.