Polymorphic path planning for robotic devices

• US 10,353,399 B2
• Filed: 07/20/2018
• Issued: 07/16/2019
• Est. Priority Date: 07/21/2017
• Status: Active Grant

• Current Assignee: Ai Incorprated
• Original Assignee: Ai Incorprated
• Inventors: Ebrahimi Afrouzi, Ali
• Primary Examiner(s): Ramesh, Krishnan
• Application Number:
  US16/041,286
• Publication Number:
  US 20190025851A1
• Time in Patent Office: 361 Days
• Field of Search: 701 25
• CPC Class Codes: B25J 9/0003 Home robots, i.e. small robots for domestic use
• CPC Class Codes: B25J 9/1664 characterised by motion, path, trajectory planning
• CPC Class Codes: G01C 22/02 by conversion into electric waveforms and subsequent integration, e.g. using tachometer generator G01C22/002, G01C22/004, G01C22/006 take precedence
• CPC Class Codes: G05D 1/0219 ensuring the processing of the whole working surface
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00

Abstract

Provided is a robot-implemented, real-time, process to plan a coverage path, the process including: obtaining environment-sensor data indicating distances from the robot to surfaces in a portion of a working environment; obtaining odometry-sensor data; based on the environment-sensor data and the odometry-sensor data, determining at least a part of a coverage path of the robot through the working environment; and commanding an electric-motor driver to move the robot along the at least part of the path.

Claims

1. A robot-implemented, real-time, method of coverage path planning, the method comprising:

obtaining, with one or more processors of a robot, environment-sensor data indicating distances from the robot to surfaces in a portion of a working environment of the robot from sensors carried by the robot;

obtaining, with one or more processors of the robot, odometry-sensor data indicating changes in position of the robot over time;

based on the environment-sensor data and the odometry-sensor data, determining in real-time, with one or more processors of the robot, at least a part of a coverage path of the robot through the working environment, wherein determining the at least part of the coverage path comprises determining lengths of segments of the coverage path, the segments having a linear motion trajectory, and the segments forming a boustrophedon pattern that covers at least part of the working environment, wherein;

the working environment is divided into a plurality of regions in a region graph, and

an instance of the boustrophedon pattern is repeated in each region in a region-specific orientation, the region-specific orientation being determined for the respective regions based on dimensions of the respective regions; and

commanding, with one or more processors of the robot, an electric-motor driver to move the robot along the at least part of the path.

2. The method of claim 1, wherein:

the robot comprises a plurality of sensors from which the environment-sensor data is obtained; and

at least a plurality of the plurality of sensors output data that is independent and identically distributed.

3. The method of claim 1, wherein:

the boustrophedon pattern comprises at least four segments with motion trajectories in alternating directions.

4. The method of claim 1, wherein:

the coverage path includes an edge linked by vertices at which the coverage path is re-evaluated by the one or more processors of the robot.

5. The method of claim 1, comprising:

in response to the commanding, calculating and sending a plurality of electric pulses to the electric motor such that the movement of the robot is in a straight line, the length of the line being determined in real-time and based on the environment-sensor data and the odometry-sensor data.

6. The method of claim 1, wherein:

determining at least part of the coverage path comprises segmenting each of at least some regions within the working environment into a central area and a marginal area; and

the coverage path specifies that the central area is visited by the robot before the marginal area.

7. The method of claim 1, wherein:

the working environment is segmented, by one or more processors of the robot or a remote computing system, into the plurality of regions;

a preliminary path is determined before beginning to traverse the working environment and not in real time;

the preliminary path includes a different instance of the boustrophedon pattern in each of the regions; and

at least some instances of the boustrophedon pattern are adjusted in real-time by the determining the at least part of the path while traversing a respective one of the regions.

8. The method of claim 1, wherein:

determining at least part of the coverage path comprises selecting motion trajectories along segments of the path before beginning to traverse the respective segments.

9. The method of claim 1, wherein:

attributes of segments are selected with a Markov Decision Process.

10. The method of claim 1, wherein:

determining at least part of the coverage path comprises optimizing an objective function that assigns values to at least two of the following;

turns, repeated coverage, transitions between different types of flooring, or switching rooms, and assigns a reward based on the values.

11. The method of claim 10, wherein:

determining at least part of the coverage path comprises minimizing a cost function or maximizing a fitness function over a plurality of segments of the path.

12. The method of claim 10, comprising:

executing a plurality of tasks with the robot, each task including covering the working environment; and

adjusting a state-action value function or policy between at least some of the tasks to further optimize the object function.

13. The method of claim 10, wherein:

determining at least part of the coverage path comprises using a net cumulative reward to evaluate the coverage path and configuring segments predicted to result in more optimal net reward than alternatives and avoiding segments that previously resulted in sub-optimal net reward.

14. The method of claim 1, wherein;

the robot is a floor cleaning robot comprising;

a battery;

a cleaning tool;

the electric-motor controller; and

two or more electric motors coupled to the battery and controlled by the motor controller.

15. The method of claim 1, wherein:

a position of the robot is determined based on the data indicating changes in position of the robot over time and the output of a Kalman filter.

16. The method of claim 1, comprising:

steps for determining a route plan at runtime.

17. The method of claim 1, wherein:

at least some of the plurality of regions are bounded by boundaries of a map determined via user input to a graphical user interface presented on a user computing device, and

the method comprises determining which regions to vacuum based on user input obtained via the graphical user interface.

18. The method of claim 1, comprising:

storing a map of the working environment created by data obtained from simultaneous localization and mapping during a first cleaning session; and

revising the map of the working environment based on data obtained from simultaneous localization and mapping during a second cleaning session.

19. The method of claim 1, wherein:

a first length of a first instance of the boustrophedon pattern is determined in a first region among the plurality of regions based on a length of the first region sensed by the robot; and

a second length of a second instance of the boustrophedon pattern is determined in a second region among the plurality of regions based on a length of the second region sensed by the robot.

20. The method of claim 1, comprising:

traversing, by the robot, at least part of a perimeter of a mapped region of the working environment among the plurality of regions;

detecting, while traversing the at least part of the perimeter, an undiscovered region of the working environment that is not yet among the plurality of regions;

in response to detecting the undiscovered region, with one or more processors of the robot, determining in real-time an added instance of the boustrophedon pattern that covers at least part of the undiscovered region; and

commanding, with one or more processors of the robot, the electric-motor driver to move the robot along the added instance of a boustrophedon pattern.

21. A device, comprising:

a robot comprising;

a battery;

an electric-motor controller;

two or more electric motors coupled to the battery and controlled by the motor controller;

one or more processors configured to control the electric-motor controller; and

one or more tangible, non-transitory, machine readable media storing instructions that when executed by at least some of the processors effectuate operations comprising;

obtaining, with one or more processors of a robot, environment-sensor data indicating distances from the robot to surfaces in a portion of a working environment of the robot from sensors carried by the robot;

obtaining, with one or more processors of the robot, odometry-sensor data indicating changes in position of the robot over time;

based on the environment-sensor data and the odometry-sensor data, determining in real-time, with one or more processors of the robot, at least a part of a coverage path of the robot through the working environment, wherein determining the at least part of the coverage path comprises determining lengths of segments of the coverage path, the segments having a linear motion trajectory, and the segments forming a boustrophedon pattern that covers at least part of the working environment, wherein;

the working environment is divided into a plurality of regions in a region graph, and

an instance of the boustrophedon pattern is repeated in each region in a region-specific orientation, the region-specific orientation being determined for the respective regions based on dimensions of the respective regions; and

commanding, with one or more processors of the robot, an electric-motor driver to move the robot along the at least part of the path.

22. The device of claim 21, wherein:

the robot comprises a plurality of sensors from which the environment-sensor data is obtained; and

at least a plurality of the plurality of sensors output data that is independent and identically distributed.

23. The device of claim 21, wherein:

the pattern comprises a boustrophedon pattern with at least four segments with motion trajectories in alternating directions.

24. The device of claim 21, wherein:

the coverage path includes a line linked by vertices at which the coverage path is re-evaluated by the one or more processors of the robot.

25. The device of claim 21, the operations comprising:

in response to the commanding, calculating and sending a plurality of electric pulses to the electric motor such that the movement of the robot is in straight line, the length of the line being determined in real-time and based on the environment-sensor data and the odometry-sensor data.

26. The device of claim 21, wherein:

determining at least part of the coverage path comprises segmenting each of at least some regions within the working environment into a central area and a marginal area; and

the coverage path specifies that the central area is visited by the robot before the marginal area.

27. The device of claim 21, wherein:

the working environment is segmented, by one or more processors of the robot or a remote computing system, into the plurality of regions;

a preliminary path is determined before beginning to traverse the working environment, wherein traversing the working environment is based on the preliminary path;

the preliminary path includes a different instance of the boustrophedon pattern in each of the regions; and

at least some instances of the boustrophedon pattern are adjusted in real-time by the determining the at least part of the path while traversing a respective one of the regions.

28. The device of claim 21, wherein:

determining at least part of the coverage path comprises selecting motion trajectories along segments of the path before beginning to traverse the respective segments.

29. The device of claim 21, wherein:

attributes of segments are selected with a Markov Decision Process.

30. The device of claim 21, wherein:

determining at least part of the coverage path comprises optimizing an objective function that assigns values to at least two of the following;

turns, repeated coverage, transitions between different types of flooring, or switching rooms; and

determining at least part of the coverage path comprises minimizing a cost function or maximizing a fitness function over a plurality of segments of the path.