Methods and systems for autonomous generation of shortest lateral paths for unmanned aerial systems

• US 10,467,914 B2
• Filed: 04/03/2018
• Issued: 11/05/2019
• Est. Priority Date: 07/14/2015
• Status: Expired due to Fees

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Valls Hernandez, Ernesto, Navarro Felix, Francisco A., Sanchez Tamargo, David, Querejeta Masaveu, Carlos, Cuadrado Sanchez, Jesus
• Primary Examiner(s): Heinle, Courtney D
• Assistant Examiner(s): Martinez Borrero, Luis A
• Application Number:
  US15/944,545
• Publication Number:
  US 20180233050A1
• Time in Patent Office: 581 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 system includes memory storing code and at least one processor to execute the code to cause the at least one processor to access an initial scenario including a source point, a target point, and a no flight zone, determine a computation time for identifying a lateral path for an aircraft to traverse that avoids the no flight zone, determine whether the determined computation time satisfies a threshold of a reference computation time, change the first number of vertices to a second number of vertices when the reference computation time is not satisfied, determine a buffer area surrounding the no flight zone, construct a visibility graph including lateral paths, and identify one of the lateral paths as being shorter than others of the lateral paths.

Claims

1. A system, comprising:

memory storing computer readable code; and

at least one processor to execute the computer readable code to cause the at least one processor to;

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

determine a computation time for identifying a lateral path for an aircraft to traverse that avoids the no flight zone, the computation time being associated with a first number of vertices of the no flight zone;

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

when the computation time does not satisfy the threshold of the reference computation time, change the first number of vertices of the no flight zone to a second number of vertices of the no flight zone to enable a subsequently determined computation time to satisfy the threshold;

determine 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;

construct 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 the first number of vertices or the second number of vertices of the no flight zone, the first number of vertices or the second number of vertices taking into account the buffer area; and

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

2. The system of claim 1, wherein when the initial scenario is defined in geodetic coordinates, and the computer readable code, when executed, causes the at least one processor to convert the geodetic coordinates to cartographic coordinates.

3. The system of claim 2, wherein the computer readable code, when executed, causes the at least one processor to convert the geodetic coordinates to cartographic coordinates by using a scale factor.

4. The system of claim 1, wherein the no flight zone includes a first no flight zone, further including a second no flight zone, and the computer readable code, when executed, causes the at least one processor to:

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

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

5. The system of claim 4, wherein the computation time is a first computation time, and the computer readable code, when executed, causes the at least one processor to, in response to identifying the second no flight zone as being outside of the configuration space, determine 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 system 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, and the computer readable code, when executed, causes the at least one processor to, in response to the second computation time satisfying the threshold of the reference computation time:

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

construct 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

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

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

8. The system of claim 1, wherein the computer readable code, when executed, causes the at least one processor to change the first number of vertices of the no flight zone by applying a vertex reduction algorithm to the no flight zone.

9. The system of claim 8, wherein the computer readable code, when executed, causes the at least one processor to apply the vertex reduction algorithm by applying at least one of a minimum Bounding Box algorithm or a linear simplification algorithm.

10. The system of claim 1, wherein the buffer area includes a first buffer area, and the computer readable code, when executed, causes the at least one processor to modify the first buffer area to reduce a size of the first buffer area to a second buffer area after identifying an angled portion of the first buffer area satisfying a threshold.

11. The system 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.

12. The system of claim 11, wherein the computer readable code, when executed, causes the at least one processor to merge the first and second no flight zones when the first no flight zone overlaps the second no flight zone.

13. A system, comprising:

memory storing computer readable code; and

at least one processor to execute the computer readable code to cause the at least one processor to;

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

identify a first no flight zone within the area;

identify a second no flight zone outside of the area;

estimate a first computation time to determine a first lateral path for an aircraft to traverse 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;

compare the first computation time to a reference computation time;

modify the first no flight zone to be a third no flight zone when the first computation time does not satisfy a threshold of the reference computation time; and

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

14. The system of claim 13, wherein the computer readable code, when executed, causes the at least one processor to define a buffer area around the third no flight zone, the estimating to consider the third no flight zone.

15. The system of claim 14, wherein the computer readable code, when executed, causes the at least one processor to identify lateral paths between the source point and the target point when the second computation time satisfies the threshold of the reference computation time, the lateral paths not passing through the third no flight zone, the lateral paths connecting vertices of the third no flight zone.

16. The system of claim 15, wherein the computer readable code, when executed, causes the at least one processor to process the lateral paths to identify a third lateral path, the third lateral path being shorter than others of the lateral paths.

17. The system of claim 13, 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.

18. The system of claim 17, wherein the computer readable code, when executed, causes the at least one processor to merge the fourth and fifth no flight zones to form the third no flight zone when the fourth no flight zone overlaps the fifth no flight zone.

19. The system of claim 13, wherein the computer readable code, when executed, modifies the first no flight zone to be the third no flight zone by applying a vertex reduction algorithm to the first no flight zone.

20. A system, comprising:

memory storing computer readable code; and

at least one processor to execute the computer readable code to cause the at least one processor to;

determine an initial path estimate between a source point and a target point associated with a flight of an aircraft;

identify a first no flight zone and a second no flight zone;

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

identify an overlap between the first no flight zone including the first buffer area and the second no flight zone including the second buffer area;

merge the first no flight zone including the first buffer area and the second no flight zone including the second buffer area into a third no flight zone including a third buffer area when the overlap is identified;

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

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

21. The system of claim 20, wherein the computer readable code, when executed, causes the at least one processor to translate the first lateral path to a geodetic pseudo-optimal lateral path for use by the aircraft.

22. The system of claim 20, wherein the computer readable code, when executed, causes the at least one processor to cause the aircraft to follow the first lateral path.

23. The system of claim 20, wherein the aircraft is an unmanned aerial vehicle, and the computer readable code, when executed, causes the at least one processor to determine the initial path estimate between the source point and the target point associated with the unmanned aerial vehicle.