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

• US 10,032,383 B2
• Filed: 07/08/2016
• Issued: 07/24/2018
• 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/206,189
• Publication Number:
  US 20170116863A1
• Time in Patent Office: 746 Days
• Field of Search: 701410, 701426, 701117, 701 23, 701 25, 701 3, 701408, 701412
• 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, by executing an instruction with at least one processor, an initial scenario including a source point, a target point, and a no flight zone;

determining, by executing an instruction with the at least one processor, 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;

determining, by executing an instruction with the at least one processor, 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, changing, by executing an instruction with the at least one processor, 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;

determining, by executing an instruction with the at least one processor, 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, by executing an instruction with the at least one processor, 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

identifying, by executing an instruction with the at least one processor, 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 the 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 changing the first number of vertices of the no flight zone includes applying a vertex reduction algorithm to the no flight zone.

9. 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.

10. The method of claim 1, wherein the buffer area includes a first buffer area, further including modifying 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 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.

12. The method of claim 11, 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.

22. The method of claim 1, further causing the aircraft to follow the shortest lateral path.

23. The method of claim 22, wherein the aircraft includes an unmanned aerial vehicle.

13. A method, comprising:

defining, by executing an instruction with at least one processor, an area between a source point and a target point;

identifying, by executing an instruction with the at least one processor, a first no flight zone within the area;

identifying, by executing an instruction with the at least one processor, a second no flight zone outside of the area;

estimating, by executing an instruction with the at least one processor, 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;

comparing, by executing an instruction with the at least one processor, 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, by executing an instruction with the at least one processor, the first no flight zone to be a third no flight zone; and

estimating, by executing an instruction with the at least one processor, 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 method of claim 13, further including defining a buffer area around the third no flight zone, the estimating to consider the third no flight zone.

15. The method of claim 13, 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.

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

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

19. The method of claim 13, 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.

20. A method, comprising:

determining, by executing an instruction with at least one processor, an initial path estimate between a source point and a target point;

identifying, by executing an instruction with the at least one processor, a first no flight zone outside of a threshold of the initial path estimate and a second no flight zone that satisfies the threshold of the initial path estimate;

removing, by executing an instruction with the at least one processor, the first no flight zone from consideration to reduce a computation time to identify a lateral path that an aircraft is to traverse that avoids the second no flight zone, the computation time being associated with a number of vertices of the second no flight zone;

determining, by executing an instruction with the at least one processor, a buffer area surrounding the second no flight zone, wherein the buffer area is defined by an offset distance from a perimeter of the second no flight zone;

constructing, by executing an instruction with the at least one processor, a visibility graph including lateral paths between the source point and the target point, the lateral paths not passing through the second no flight zone including the buffer area, the lateral paths connecting vertices of the second no flight zone;

identifying, by executing an instruction with the at least one processor, a first lateral path of the lateral paths, the first lateral path being shorter than others of the lateral paths; and

causing the aircraft to follow the first lateral path.

21. The method of claim 20, further including translating the first lateral path to a geodetic pseudo-optimal lateral path for use by the aircraft.

24. A method, comprising:

determining, by executing an instruction with at least one processor, an initial path estimate between a source point and a target point;

identifying, by executing an instruction with the at least one processor, a first no flight zone and a second no flight zone;

determining, by executing an instruction with the at least one processor, 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;

identifying, by executing an instruction with the at least one processor, an overlap between the first no flight zone including the first buffer area and the second no flight zone including the second buffer area;

in response to identifying the overlap, merging, by executing an instruction with the at least one processor, 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;

constructing, by executing an instruction with the at least one processor, 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

identifying, by executing an instruction with the at least one processor, a first lateral path of the lateral paths, the first lateral path being shorter than others of the lateral paths.