Polymorphic path planning for robotic devices

Patent metadata

Field	Value
Publication number	US-10353399-B2
Application number	US-201816041286-A
Country	US
Kind code	B2
Filing date	Jul 20, 2018
Priority date	Jul 21, 2017
Publication date	Jul 16, 2019
Grant date	Jul 16, 2019

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.

First claim

I claim:

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 en

Assignees

• Ai Inc

Inventors

• Ebrahimi Afrouzi Ali

Classifications

• B25J9/0003

  Home robots, i.e. small robots for domestic use · CPC title

• G01C22/02

  by conversion into electric waveforms and subsequent integration, e.g. using tachometer generator {(G01C22/002, G01C22/004, G01C22/006 take precedence)} · CPC title

• B25J9/1664

  characterised by motion, path, trajectory planning · CPC title

• G05D2201/0215

  Physics · mapped topic

• G05D1/0272 Primary

  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) · CPC title