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

• US 10,824,166 B2
• Filed: 05/13/2019
• Issued: 11/03/2020
• Est. Priority Date: 10/23/2018
• Status: Active Grant

• Current Assignee: Quanta Computer
• Original Assignee: Quanta Computer
• Inventors: Hsu, Tao-Chih, Wang, Yang-Sheng, Chen, Chun-Ting, Chen, Yu-Ching
• Primary Examiner(s): Sarwar, Babar
• Application Number:
  US16/410,193
• Publication Number:
  US 20200125115A1
• Time in Patent Office: 540 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 2201/04 Automatic control of the travelling movement; Automatic obstacle detection
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G05D 1/0219 ensuring the processing of the whole working surface
• 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/0287 involving a plurality of land vehicles, e.g. fleet or convoy travelling traffic control systems for road vehicles G08G1/00, particularly anticollision systems G08G1/16
• CPC Class Codes: G05D 1/0297 by controlling means in a control room

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.

Claims

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=2XT+(XY−

1)L+√

{square root over (1+(Y−

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=2XT+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=2XT+(XY−

1)L+√

{square root over (1+(Y−

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=2XT+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 than the average cleaning time.

10. The task distribution system of claim 9, wherein the first processing unit is further configured to:

divide the combined task sub-regions in response to the plurality of task sub-regions having no adjacent and combined task sub-regions; and

enhance 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.