Systems and Methods for Navigation Path Determination for Unmanned Vehicles

• US 20190041219A1
• Filed: 08/02/2017
• Published: 02/07/2019
• Est. Priority Date: 08/02/2017
• Status: Active Grant

• Current Assignee: Wing Aviation LLC (Alphabet Inc.)
• Original Assignee: X Development LLC (Alphabet Inc.)
• Inventors: Schubert, Martin, Watson, Philip, Grundmann, Michael, Levine, Gabriella
• Granted Patent: US 10,393,528 B2
• Time in Patent Office: Days
• CPC Class Codes: B64C 39/024 of the remote controlled vehicle type, i.e. RPV
• 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 2101/60 for transporting passengers; for transporting goods other than weapons
• CPC Class Codes: B64U 2101/64 for parcel delivery or retrieval
• 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: G01C 21/1652 with ranging devices, e.g. LIDAR or RADAR
• CPC Class Codes: G01C 21/1654 with electromagnetic compass
• CPC Class Codes: G01C 21/1656 with passive imaging devices, e.g. cameras
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3602 Input other than that of destination using image analysis, e.g. detection of road signs, lanes, buildings, real preceding vehicles using a camera
• CPC Class Codes: G01S 19/47 the supplementary measurement being an inertial measurement, e.g. tightly coupled inertial
• CPC Class Codes: G05D 1/0011 associated with a remote control arrangement
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G06Q 10/083 Shipping
• CPC Class Codes: G06T 2207/10032 Satellite or aerial image; Remote sensing
• CPC Class Codes: G06T 2207/30261 Obstacle
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59
• CPC Class Codes: G06V 20/58 Recognition of moving objects or obstacles, e.g. vehicles or pedestrians; Recognition of traffic objects, e.g. traffic signs, traffic lights or roads

Abstract

Examples implementations relate to navigation path determination. An example method includes receiving, at a computing system, video data showing a demonstration path for navigating a location. The method further includes identifying, using the video data, a set of permissible surfaces at the location, wherein each permissible surface was traversed by the demonstration path. The method additionally includes determining a navigation path for a vehicle to follow at the location, wherein the navigation path includes a variation from the demonstration path such that the variation causes the vehicle to stay within one or more permissible surfaces from the set of permissible surfaces. The method also includes causing, by the computing system, the vehicle to follow the navigation path to navigate the location.

Claims

1. A method comprising:

receiving, at a computing system, video data showing a demonstration path for navigating a location;

identifying, using the video data, a set of permissible surfaces at the location, wherein each permissible surface was traversed by the demonstration path;

determining a navigation path for a vehicle to follow at the location, wherein the navigation path includes a variation from the demonstration path such that the variation causes the vehicle to stay within one or more permissible surfaces from the set of permissible surfaces; and

causing, by the computing system, the vehicle to follow the navigation path to navigate the location.

2. The method of claim 1, wherein the demonstration path ends with a delivery destination, wherein the navigation path is determined to reach the delivery destination, wherein the method further comprises causing the vehicle to deliver an object to the delivery destination.

3. The method of claim 1, wherein receiving video data showing the demonstration path comprises:

receiving global positioning system (GPS) waypoints positioned at a plurality of points of the demonstration path; and

determining a mapping between the GPS waypoints and corresponding portions of video data.

4. The method of claim 3, wherein determining the navigation path for the vehicle to follow at the location is based on the mapping between the GPS waypoints and the corresponding portions of video data.

5. The method of claim 1, wherein receiving video data showing the demonstration path comprises:

receiving global positioning system (GPS) and accelerometer data that corresponds to the video data showing the demonstration path;

determining a mapping between the GPS and accelerometer data and corresponding portions of video data, and

wherein determining the navigation path for the vehicle to follow at the location is based on the mapping between the GPS and accelerometer data and the corresponding portions of video data.

6. The method of claim 1, further comprising:

based on the navigation path, selecting the vehicle from a group of vehicles to navigate the location, wherein the group of vehicles includes at least a first type of vehicle having a first set of capabilities and a second type of vehicle having a second set of capabilities, and wherein selecting the vehicle from the group of vehicles is based on capabilities of the selected vehicle.

7. The method of claim 1, further comprising:

based on determining the navigation path for the vehicle to follow at the location, estimating an amount of time that the vehicle will require to navigate the navigation path.

8. The method of claim 1, further comprising:

identifying, using the video data, an obstacle positioned proximate the demonstration path; and

wherein determining the navigation path for the vehicle to follow at the location comprises;

determining the navigation path such that the navigation path includes a given variation that avoids the obstacle but causes the vehicle to stay within one or more permissible surfaces from the set of permissible surfaces.

9. The method of claim 1, wherein determining navigation path for the vehicle to follow at the location comprises:

determining the navigation path to include the variation from the demonstration path based on locomotive capabilities of the vehicle.

10. The method of claim 1, wherein determining the navigation path for the vehicle to follow at the location comprises:

determining the navigation path to include the variation from the demonstration path based on one or more parameters of an object to be delivered at the location.

11. A system comprising:

a vehicle; and

a control system configured to;

receive video data showing a demonstration path for navigating a location;

identify, using the video data, a set of permissible surfaces at the location, wherein each permissible surface was traversed by the demonstration path;

determine a navigation path for the vehicle to follow at the location, wherein the navigation path includes a variation from the demonstration path such that the variation causes the vehicle to stay within one or more permissible surfaces from the set of permissible surfaces; and

cause the vehicle to follow the navigation path to navigate the location.

12. The system of claim 11, wherein the control system is further configured to:

determine a position proximate to the location to drop off the vehicle, wherein the vehicle is positioned on another vehicle configured to navigate between locations; and

cause the drop off of the vehicle at the position.

13. The system of claim 11, wherein the control system is configured to identify the set of permissible surfaces at the location further by determining physical features for each permissible surface of the set of permissible surfaces.

14. The system of claim 13, wherein the control system is configured to determine the navigation path for the vehicle to follow at the location based on the physical features determined for each permissible surface of the set of permissible surfaces.

15. The system of claim 11, wherein the control system is further configured to provide, based on the received video data, a request for annotations that indicate waypoints that correspond to the demonstration path.

16. The system of claim 15, wherein the control system is configured to determine portions of the navigation path based on the waypoints.

17. A non-transitory computer readable medium having stored therein program instructions executable by a computing system to cause the computing system to perform operations, the operations comprising:

receiving video data showing a demonstration path for navigating a location;

identifying, using the video data, a set of permissible surfaces at the location, wherein each permissible surface was traversed by the demonstration path;

determining a navigation path for a vehicle to follow at the location, wherein the navigation path includes a variation from the demonstration path such that the variation causes the vehicle to stay within one or more permissible surfaces from the set of permissible surfaces; and

causing the vehicle to follow the navigation path to navigate the location.

18. The non-transitory computer readable medium of claim 17, wherein the operation of identifying the set of permissible surfaces at the location comprises:

identifying a paved walkway that corresponds to a given permissible surface at the location.

19. The non-transitory computer readable medium of claim 18, wherein the operation of determining the navigation path for the vehicle to follow at the location comprises:

determining the navigation path such that a portion of the navigation path uses a portion of the identified paved walkway.

20. The non-transitory computer readable medium of claim 17, wherein the operations further comprise:

identifying, using the video data, an obstacle positioned proximate the demonstration path;

determining that the obstacle prevents the vehicle from following the navigation path at the location; and

sending a request to a user at the location to expand the set of permissible surfaces to circumnavigate the obstacle to complete navigation at the location.