Systems and methods for dynamic route planning in autonomous navigation

• US 10,001,780 B2
• Filed: 11/02/2016
• Issued: 06/19/2018
• Est. Priority Date: 11/02/2016
• Status: Active Grant

• Current Assignee: Brain Corporation
• Original Assignee: Brain Corporation
• Inventors: Gabardos, Borja Ibarz, Passot, Jean-Baptiste
• Primary Examiner(s): FREJD, RUSSELL WARREN
• Application Number:
  US15/341,612
• Publication Number:
  US 20180120856A1
• Time in Patent Office: 594 Days
• CPC Class Codes: A47L 11/4011 Regulation of the cleaning machine by electric means; Control systems and remote control systems therefor
• CPC Class Codes: A47L 11/4061 Steering means; Means for avoiding obstacles; Details related to the place where the driver is accommodated
• CPC Class Codes: A47L 2201/04 Automatic control of the travelling movement; Automatic obstacle detection
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• 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: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0276 using signals provided by a source external to the vehicle involving a plurality of vehicles G05D1/0287; automatically controlling vehicle speed responsive to externally generated signals B60K31/0058

Abstract

Systems and methods for dynamic route planning in autonomous navigation are disclosed. In some exemplary implementations, a robot can have one or more sensors configured to collect data about an environment including detected points on one or more objects in the environment. The robot can then plan a route in the environment, where the route can comprise one or more route poses. The route poses can include a footprint indicative at least in part of a pose, size, and shape of the robot along the route. Each route pose can have a plurality of points therein. Based on forces exerted on the points of each route pose by other route poses, objects in the environment, and others, each route pose can reposition. Based at least in part on interpolation performed on the route poses (some of which may be repositioned), the robot can dynamically route.

Claims

1. A robot comprising:

one or more sensors configured to collect data about an environment including detected points on one or more objects in the environment; and

a controller configured to;

create a map of the environment based at least in part on the collected data;

determine a route in the map in which the robot will travel;

generate one or more route poses on the route, wherein each route pose comprises a footprint indicative of poses of the robot along the route and each route pose has a plurality of points disposed therein;

determine forces on each of the plurality of points of each route pose, the forces comprising repulsive forces from one or more of the detected points on the one or more objects and attractive forces from one or more of the plurality of points on others of the one or more route poses;

reposition one or more route poses in response to the forces on each point of the one or more route poses; and

perform interpolation between one or more route poses to generate a collision-free path between the one or more route poses for the robot to travel.

2. The robot of claim 1, wherein:

the one or more route poses form a sequence in which the robot travels along the route; and

the interpolation comprises a linear interpolation between sequential ones of the one or more route poses.

3. The robot of claim 1, wherein the interpolation generates one or more interpolation route poses having substantially similar footprints to the footprint of each route pose.

4. The robot of claim 1, wherein the determination of the forces on each point of the one or more route poses further comprises a computation of a force function that associates, at least in part, the forces on each point of each route pose with one or more characteristics of objects in the environment.

5. The robot of claim 4, wherein the one or more characteristics includes one or more of distance, shape, material, and color.

6. The robot of claim 4, wherein:

the force function associates zero repulsive force exerted by a first detected point on a first object where a distance between the first detected point and a second point of a first route pose is above a predetermined distance threshold.

7. The robot of claim 1, wherein the footprint of each route pose has substantially similar size and shape as the footprint of the robot.

8. The robot of claim 1, wherein the robot comprises a floor cleaner.

9. A method for dynamic navigation of a robot in an environment, comprising:

generating a map of the environment using data from one or more sensors;

determining a route on the map, the route including one or more route poses, each route pose comprising a footprint indicative at least in part of a pose and a shape of the robot along the route and each route pose having a plurality of points disposed therein;

computing repulsive forces from a point on an object in the environment onto the plurality of points of a first route pose of the one or more route poses;

repositioning the first route pose in response to at least the repulsive forces; and

performing an interpolation between the repositioned first route pose and another of the one or more route poses.

10. The method of claim 9, further comprising determining attractive forces from a point on another of the one or more route poses exerted on the plurality of points of the first route pose.

11. The method of claim 9, further comprising:

detecting a plurality of objects in the environment with the one or more sensors, each of the plurality of objects having detected points; and

defining a force function, the force function computing repulsive forces exerted by each of the detected points of the plurality of objects on the plurality of points of the first route pose, wherein each repulsive force comprises a vector.

12. The method of claim 11, wherein the repositioning of the first route pose comprises calculating a minimum of the force function.

13. The method of claim 9, wherein the repositioning of the first route pose comprises translating and rotating the first route pose.

14. The method of claim 9, wherein the performing of the interpolation comprises:

generating an interpolation route pose having a footprint substantially similar to the shape of the robot; and

determining a translation and rotation of the interpolation route pose based at least on a collision-free path between the translated and rotated first route pose and the another of the one or more route poses.

15. The method of claim 9, further comprising computing a magnitude of the repulsive forces as proportional to a distance between the point on the object and each of the plurality of points of the first route pose if the point on the object is outside of the footprint of the first route pose.

16. The method of claim 9, further comprising computing a magnitude of the repulsive forces as inversely proportional to a distance between the point on the object and each of the plurality of points of the first route pose if the point on the object is inside the footprint of the first route pose.

17. The method of claim 9, further comprising computing torque forces onto the plurality of points of the first route pose due to the repulsive forces.

18. A non-transitory computer-readable storage apparatus having a plurality of instructions stored thereon, the instructions being executable by a processing apparatus to operate a robot, the instructions configured to, when executed by the processing apparatus, cause the processing apparatus to:

generate a map of an environment using data from one or more sensors;

determine a route on the map, the route comprising one or more route poses, each route pose comprising a footprint indicative at least in part of a pose and a shape of the robot along the route and each route pose having a plurality of points disposed therein; and

compute repulsive forces from a point on an object in the environment onto the plurality of points of a first route pose of the one or more route poses.

19. The non-transitory computer-readable storage apparatus of claim 18, further comprising one or more instructions, which when executed by the processing apparatus, further cause the processing apparatus to determine attractive forces from a point on another of the one or more route poses exerted on the plurality of points of the first route pose.

20. The non-transitory computer-readable storage apparatus of claim 18, further comprising one or more instructions, which when executed by the processing apparatus, further cause the processing apparatus to determine torque forces from a point on another of the one or more route poses exerted on the plurality of points of the first route pose.