Methods and systems of distributing task regions for a plurality of cleaning devices

Patent metadata

Field	Value
Publication number	US-10824166-B2
Application number	US-201916410193-A
Country	US
Kind code	B2
Filing date	May 13, 2019
Priority date	Oct 23, 2018
Publication date	Nov 3, 2020
Grant date	Nov 3, 2020

Abstract

A method of distributing task regions for a plurality of cleaning devices, including: dividing a task map into a plurality of basic sub-regions according to concave corners corresponding to the shape of the task map; combining each two adjacent basic sub-regions, and calculating basic cleaning time corresponding to each of the combined basic sub-regions; repeatedly combining each two adjacent basic sub-regions according to the basic cleaning time, and obtaining a basic partition result; selecting starting blocks according to positions of the plurality of task sub-regions in the basic partitioning result; combining the task sub-regions according to the position of each starting block, the position of each task sub-region, and the cleaning time corresponding to each task sub-region, and obtaining the task region distribution result; enabling cleaning devices to perform cleaning tasks according to the position of each cleaning device and the task region distribution result.

First claim

What is claimed is:

1. A method of distributing task regions for a plurality of cleaning devices, comprising:
acquiring a task map;
acquiring a shape corresponding to the task map;
dividing the task map into a plurality of basic sub-regions according to a plurality of concave corners of the shape;
combining each two adjacent basic sub-regions, and calculating a basic cleaning time corresponding to each of the combined basic sub-regions, wherein each two adjacent basic sub-regions have a common side of equal length;
combining each two adjacent basic sub-regions repeatedly according to the length of the basic cleaning time until all of the adjacent basic sub-regions don't have a common side of equal length, and obtaining a basic partition result;
selecting a plurality of starting blocks according to positions of a plurality of task sub-regions in the basic partition result, wherein the number of starting blocks is equal to the number of cleaning devices;
combining the plurality of task sub-regions according to a position of each of the starting blocks, a position of each of the task sub-regions, and a cleaning time corresponding to each of the task sub-regions until the number of remaining task sub-regions is equal to the number of cleaning devices, and obtaining a task region distribution result; and
enabling each of the cleaning devices to perform a cleaning task according to positions of the plurality of cleaning devices and the task region distribution result.

2. The method of claim 1 , wherein the calculation of cleaning time corresponding to the plurality of basic sub-regions and the plurality of task sub-regions further comprises:
obtaining the cleaning time through a first formula or a second formula according to the number of cleaning units on a short side of the plurality of basic sub-regions and the plurality of task sub-regions;
wherein when the number of cleaning units on the short side is odd, the cleaning time is calculated by the first formula, wherein the first formula is:
T total =2 XT +( XY− 1) L +√{square root over (1+( Y− 2) 2 )}* L

wherein when the number of cleaning units on the short side is even, the cleaning time is calculated by the second formula, wherein the second formula is:
T total =2 XT+XYL

where T total is the cleaning time, X is the number of cleaning units on the short side, Y is the number of cleaning units on a long side, T is the time required for the plurality of cleaning devices to turn, and L is the time required for the plurality of cleaning devices to clean one of the cleaning units.

3. The method of claim 1 , further comprising:
obtaining an average cleaning time according to the cleaning time corresponding to each of the task sub-regions and the number of cleaning devices; and
combining the adjacent task sub-regions according to the length of the cleaning time corresponding to the plurality of starting blocks until the difference between the cleaning time corresponding to the combined task sub-regions and the average cleaning time is smaller than a given tolerance, and obtaining the task region distribution result.

4. The method of claim 3 , further comprising:
determining whether the cleaning time corresponding to the plurality of task sub-regions is longer than the average cleaning time; and
dividing the plurality of task sub-regions along a long side in response to determining that the cleaning time corresponding to the plurality of task sub-regions is longer than the average cleaning time.

5. The method of claim 4 , further comprising:
dividing the combined task sub-regions in response to the plurality of task sub-regions having no adjacent and combined task sub-regions; and
enhancing the given tolerance in response to all of the task sub-regions having been divided and the difference between each of the combined task sub-regions and the average cleaning time still being higher than the given tolerance.

6. A task distribution system for cleaning devices, comprising:
a control terminal, comprising:
a first storage unit for storing a task map;
a first processing unit configured to:
acquire the task map from the first storage unit;
acquire a shape corresponding to the task map;
divide the task map into a plurality of basic sub-regions according to a plurality of concave corners of the shape;
combine each two adjacent basic sub-regions and calculate a basic cleaning time corresponding to each combination, wherein each two adjacent basic sub-regions have a common side of equal length;
combine each two adjacent basic sub-regions repeatedly according to the length of the basic cleaning time until all of the adjacent basic sub-regions don't have a common side of equal length, and obtaining a basic partition result;
select a plurality of starting blocks according to positions of a plurality of task sub-regions in the basic partition result, wherein the number of starting blocks is equal to the number of cleaning devices;
combine the plurality of task sub-regions according to the position of each of the starting blocks, the position of each of the task sub-regions, and the cleaning time corresponding to each of the task sub-regions until the number of remaining task sub-regions is equal to the number of cleaning devices, and obtaining a task region distribution result;
distributing a cleaning task to each of the cleaning devices according to the position of the cleaning devices and the task region distribution result;

a plurality of the cleaning devices, wherein each of the cleaning devices comprises:
a second storage unit for storing the task region distribution result; and
a second processing unit for performing the cleaning task according to the task region distribution result.

7. The task distribution system of claim 6 , wherein the first processing unit further obtains the cleaning time through a first formula or a second formula according to the basic sub-regions and the number of cleaning units on a short side;
wherein when the number of cleaning units on the short side is odd, the cleaning time is calculated by the first formula, wherein the first formula is:
T total =2 XT +( XY− 1) L +√{square root over (1+( Y− 2) 2 )}* L

wherein when the number of cleaning units on the short side is even, the cleaning time is calculated by the second formula, wherein the second formula is:
T total =2 XT+XYL

where T total is the cleaning time, X is the number of cleaning units on the short side, Y is the number of cleaning units on a long side, T is the time required for the plurality of cleaning devices to turn, and L is the time required for the plurality of cleaning devices to clean one of the cleaning units.

8. The task distribution system of claim 6 , wherein the first processing unit is further configured to:
obtain an average cleaning time according to the cleaning time corresponding to each of the task sub-regions and the number of cleaning devices; and
combine the adjacent task sub-regions according to the length of the cleaning time corresponding to the plurality of starting blocks until the difference between the cleaning time corresponding to the combined task sub-regions and the average cleaning time is smaller than a given tolerance, and obtaining the task region distribution result.

9. The task distribution system of claim 8 , wherein the first processing unit is further configured to:
determine whether the cleaning time corresponding to the plurality of task sub-regions is longer than the average cleaning time; and
divide the plurality of task sub-regions along the long side in response to determining that the cleaning time corresponding to the plurality of task sub-regions is longer

Assignees

• Quanta Comp Inc

Inventors

• Hsu Tao-Chih
• Wang yang-sheng
• Chen Chun-Ting
• Chen Yu-Ching

Classifications

• A47L11/4011

  Regulation of the cleaning machine by electric means; Control systems and remote control systems therefor · CPC title

• A47L2201/04

  Automatic control of the travelling movement; Automatic obstacle detection · CPC title

• G06Q10/06311 Primary

  Scheduling, planning or task assignment for a person or group · CPC title

• G05D2201/0203

  Physics · mapped topic

• G05D1/0219

  ensuring the processing of the whole working surface · CPC title