Controlling unmanned aerial vehicles to avoid obstacle collision

• US 10,665,115 B2
• Filed: 12/29/2016
• Issued: 05/26/2020
• Est. Priority Date: 01/05/2016
• Status: Active Grant

• Current Assignee: California Institute of Technology
• Original Assignee: California Institute of Technology
• Inventors: Fragoso, Anthony T. S., Matthies, Larry H., Brockers, Roland, Murray, Richard M.
• Primary Examiner(s): Wiltey, Nicholas K
• Application Number:
  US15/394,647
• Publication Number:
  US 20170193830A1
• Time in Patent Office: 1,244 Days
• Field of Search: 701 2, 701 3, 701 15, 701 23, 382103, 244175
• CPC Class Codes: B64U 10/14 with four distinct rotor axes, e.g. quadcopters
• CPC Class Codes: B64U 2101/00 UAVs specially adapted for particular uses or applications
• CPC Class Codes: B64U 2101/30 for imaging, photography or videography
• 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: B64U 30/20 Rotors; Rotor supports
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01S 17/86 Combinations of lidar systems with systems other than lidar, radar or sonar, e.g. with direction finders
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G01S 17/933 of aircraft or spacecraft
• CPC Class Codes: G05D 1/102 specially adapted for vertical take-off of aircraft
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching
• CPC Class Codes: G06V 20/00 Scenes; Scene-specific elements control of digital cameras H04N23/60
• CPC Class Codes: G06V 20/13 Satellite images
• CPC Class Codes: G08G 5/0069 specially adapted for an unmanned aircraft
• CPC Class Codes: G08G 5/045 Navigation or guidance aids, e.g. determination of anti-collision manoeuvers radar or analogous systems specially adapted for anti-collision between aircraft G01S13/933

Abstract

A method, device, framework, and system provide the ability to control an unmanned aerial vehicle (UAV) to avoid obstacle collision. Range data of a real-world scene is acquired using range sensors (that provide depth data to visible objects). The range data is combined into an egospace representation (consisting of pixels in egospace). An apparent size of each of the visible objects is expanded based on a dimension of the UAV. An assigned destination in the real world scene based on world space is received and transformed into egospace coordinates in egospace. A trackable path from the UAV to the assigned destination through egospace that avoids collision with the visible objects (based on the expanded apparent sizes of each of the visible objects) is generated. Inputs that control the UAV to follow the trackable path are identified.

Claims

1. A method for controlling an unmanned aerial vehicle (UAV) to avoid obstacle collision, comprising:

(a) acquiring range data of a real-world scene using one or more range sensors, wherein the range data comprises depth data to one or more visible objects;

(b) combining the range data into an egospace representation comprising a first set of one or more pixels in egospace, wherein;

(1) each pixel in the first set of one or more pixels corresponds to a specific direction;

(2) each pixel in the first set of one or more pixels stores a depth;

(3) the depth comprises a distance, to one of the one or more visible objects encountered in the specific direction; and

(4) the egospace comprises a coordinate system given by a second set of all possible pixel and depth combinations;

(c) expanding an apparent size of each of the one or more visible objects based on a dimension of the UAV, wherein the UAV comprises a configuration flat vehicle (CFV), wherein a UAV with state variables x, control inputs u, and state equations {dot over (x)}=f (x,u) comprises a CFV if there exists a set of flat outputs

z=α

(x,u,{dot over (u)}, . . . ,u^(k)),

that are a smooth function α

of the state variables and control inputs, smooth functions β and

γ

such that

x=β

(z,ż

, . . . ,z^(j)),

u=γ

(z,ż

, . . . ,z^(j)),

and obstacle and configuration spaces O, C⊂

{z} such that C={z}\O;

(d) receiving an assigned destination in the real world scene based on world space;

(e) transforming the assigned destination into egospace coordinates in egospace;

(f) generating a trackable path from the UAV to the assigned destination through egospace that avoids collision with the one or more visible objects based on the expanded apparent sizes of each of the one or more visible objects; and

(g) identifying and providing one or more inputs to control the UAV to follow the trackable path, and wherein the UAV follows the trackable path based on the one or more inputs.

2. The method of claim 1, wherein for each of the one or more pixels of the egospace representation, a value is assigned that uniquely encodes the distance to the one of the one or more visible objects from a defined focal point, wherein the defined focal point is an arbitrary origin.

3. The method of claim 1, wherein the generating the trackable path comprises:

generating one or more predefined maneuvers simultaneously in egospace and world space; and

selecting and linking one or more of the predefined maneuvers to generate the trackable path.

4. The method of claim 1, wherein the generating the trackable path comprises:

generating one or more waypoints in egospace;

searching for a sequence of the one or more waypoints that define the trackable path; and

wherein the searching comprises comparing the depth of the one or more visible objects to egospace coordinates of the one or more waypoints to determine whether the one or more waypoints and segments connecting the one or more waypoints are valid.

5. The method of claim 4, wherein the searching is performed dynamically on the fly on board the UAV.

6. The method of claim 1, wherein the generating the trackable path comprises:

(a) determining an acceptable time to contact;

(b) checking if the assigned destination in egospace is collision free within the acceptable time to contact, wherein the checking comprises;

(1) converting the acceptable time to contact to an acceptable depth value; and

(2) comparing the acceptable depth value against a depth value corresponding to one of the one or more visible objects that occlude the assigned destination;

(c) repeating (b) for each of the one or more pixels of the egospace representation;

(d) selecting one of the one or more pixels in the egospace representation that is collision free as a target; and

(e) configuring the UAV wherein a velocity vector of the UAV aligns with the target.

7. A navigation framework in an unmanned aerial vehicle that avoids obstacle collision:

(a) an embedded flight computer integrated into the UAV that enables the UAV to maneuver, wherein the UAV;

(1) acquires range data of a real-world scene using one or more range sensors mounted on the UAV, wherein the range data comprises depth data to one or more visible objects;

(2) combines the range data into an egospace representation comprising a first set of one or more pixels in egospace, wherein;

(A) each pixel in the first set of one or more pixels corresponds to a specific direction;

(B) each pixel in the first set of one or more pixels stores a depth;

(C) the depth comprises a distance, to one of the one or more visible objects encountered in the specific direction; and

(D) the egospace comprises a coordinate system given by a second set of all possible pixel and depth combinations;

(3) expands an apparent size of each of the one or more visible objects based on a dimension of the UAV, wherein the UAV comprises a configuration flat vehicle (CFV), wherein a UAV with state variables x, control inputs u, and state equations {dot over (x)}=f (x,u) comprises a CFV if there exists a set of flat outputs

z=α

(x,u,{dot over (u)}, . . . ,u^(k)),

that are a smooth function α

of the state variables and control inputs, smooth functions β and

γ

such that

x=β

(z,ż

, . . . ,z^(j)),

u=γ

(z,ż

, . . . ,z^(j)),

and obstacle and configuration spaces O, C⊂

{z} such that C={z}\O;

(4) receives an assigned destination in the real world scene based on world space;

(5) transforms the assigned destination into egospace coordinates in egospace;

(6) generates a trackable path from the UAV to the assigned destination through egospace that avoids collision with the one or more visible objects based on the expanded apparent sizes of each of the one or more visible objects; and

(7) identifies and provides one or more inputs to control the UAV to follow the trackable path, and wherein the UAV follows the trackable path based on the one or more inputs.

8. The navigation framework of claim 7, wherein for each of the one or more pixels of the egospace representation, a value is assigned that uniquely encodes the distance to the one of the one of the one or more visible objects from a defined focal point, wherein the defined focal point is an arbitrary origin.

9. The navigation framework of claim 7, wherein the embedded flight computer generates the trackable path by:

generating one or more predefined maneuvers simultaneously in egospace and world space; and

selecting and linking one or more of the predefined maneuvers to generate the trackable path.

10. The navigation framework of claim 7, wherein the embedded flight computer generates the trackable path by:

generating one or more waypoints in egospace;

searching for a sequence of the one or more waypoints that define the trackable path; and

wherein the searching comprises comparing the depth of the one or more visible objects to egospace coordinates of the one or more waypoints to determine whether the one or more waypoints and segments connecting the one or more waypoints are valid.

11. The navigation framework of claim 10, wherein the embedded flight computer searches dynamically on the fly on board the UAV.

12. The navigation framework of claim 7, wherein the embedded flight computer generates the trackable path by:

(a) determining an acceptable time to contact;

(b) checking if the assigned destination in egospace is collision free within the acceptable time to contact, wherein the checking comprises;

(1) converting the acceptable time to contact to an acceptable depth value; and

(2) comparing the acceptable depth value against a depth value corresponding to one of the one or more visible objects that occlude the assigned destination;

(c) repeating (b) for each of the one or more pixels of the egospace representation;

(d) selecting one of the one or more pixels in the egospace representation that is collision free as a target; and

(e) configuring the UAV wherein a velocity vector of the UAV aligns with the target.