System for assigning one of many part domains in a domain to one of many mobile units

• US 7,792,606 B2
• Filed: 10/02/2002
• Issued: 09/07/2010
• Est. Priority Date: 10/11/2001
• Status: Expired due to Fees

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Jager, Markus
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): Peche, Jorge O
• Application Number:
  US10/492,303
• Publication Number:
  US 20040249511A1
• Time in Patent Office: 2,897 Days
• Field of Search: 700/245, 700/248, 700/255, 700/262, 901/6, 901/8, 901/40, 901/47
• US Class Current: 700/245
• CPC Class Codes: A47L 2201/04 Automatic control of the travelling movement; Automatic obstacle detection
• 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/0291 Fleet control monitoring fleets in traffic control systems for road vehicles G08G1/127, G08G1/127

Abstract

A partial surface of a total surface, divided into several partial surfaces, is allocated to one of several mobile units by determining the partial surface of the total surface and allocating one of the several mobile units with a reservation. The mobile unit transmits allocation information indicating the allocation of the partial surface. The reservation is lifted and the allocation of the partial surface is validated when the one of the several mobile units receives no allocation rejection information from at least one of the other mobile units, indicating a rejection of the allocation of the partial surface. If rejection information is received, the reservation is lifted and the allocation of the partial surface is invalidated.

Claims

1. A method for assigning a part domain of a whole domain which is divided into part domains to one of a plurality of interacting mobile units to process a specific area, comprising:

specifying a part domain of the whole domain which is divided into part domains for assignment provisionally to one of the mobile units, wherein the part domains are selected and allocated using a connectivity graph;

transmitting to the one of the plurality of mobile units an assignment notification indicating the assignment of the part domain to the one of the mobile units provisionally;

making the assignment of the part domain non-provisional if the one of the mobile units does not receive an assignment rejection notification, indicating a rejection of the assignment of the part domain, from at least one other of the plurality of mobile units;

notifying the other mobile units when one mobile unit allocates at least one part domain of the whole domain;

making the assignment of the part domain invalid if the one of the mobile units receives at least one assignment rejection notification;

ensuring each mobile unit has a reserve of part domains to process;

allocating additional part domains when the number of part domains to be processed by each mobile unit falls below a specific threshold;

selecting a newly allocated part domain adjacent to the part domains which are already allocated;

storing in each of the mobile units a local map of the whole domain in which at least validly assigned part domains thereof are identified; and

exchanging notifications whenever at least two of the mobile units are within a predeterminable communication distance, and synchronizing local views of the map of the whole domain of the at least two mobile units to develop a common view of the whole domain, whereby global coordination is not required.

2. The method as claimed in claim 1, wherein at least one of said specifying and said transmitting of the assignment notification is performed when the one of the mobile units is at least a predeterminable assignment distance from the part domain.

3. The method as claimed in claim 2, wherein at least one of said specifying and said transmitting of the assignment notification is included in a request for the part domain by the one of the mobile units.

4. The method as claimed in claim 3, wherein at least one of said specifying and said transmitting of the assignment notification is performed during a processing of other part domains of the whole domain by the mobile units.

5. The method as claimed in claim 1, wherein the assignment notification includes an importance notification describing how important the assignment of the part domain is for the one of the mobile units.

6. The method as claimed in claim 5, further comprising combining the part domain provisionally assigned to the one of the mobile units with other part domains assigned to the one of the mobile units to form a processing area.

7. The method as claimed in claim 6, wherein said specifying and combining results in the processing area being as compact as possible.

8. The method as claimed in claim 7, further comprising determining a processing path for the processing area using a path planning method.

9. The method as claimed in claim 8, further comprising identifying the part domain in the map of the one of the mobile units when the assignment is made non-provisional.

10. The method as claimed in claim 9, further comprising carrying out an agreement method if the part domain assigned to the one of the mobile units has already been assigned to another of the mobile units.

11. The method as claimed in claim 10, wherein the mobile units are cleaning robots used to clean the whole domain.

12. A system for assigning a part domain of a whole domain divided into part domains to one of a plurality of mobile units to process a specific area, comprising:

an assignment unit specifying a part domain of the whole domain and assigning the part domain to the one of the mobile units provisionally, wherein the part domains are selected and allocated using a connectivity graph;

a communication unit transmitting an assignment notification indicating assignment of the part domain to the one of the mobile units provisionally and receiving an assignment rejection notification from at least one other mobile unit if the assignment is rejected, said assignment unit making the assignment of the part domain valid if no assignment rejection notification is received within a predetermined time and invalidating the assignment of the part domain if at least one assignment rejection notification is received;

a notification unit notifying the other mobile units when one mobile unit allocates at least one part domain of the whole domain;

a reservation unit ensuring each mobile unit has a reserve of part domains to process;

an allocation unit allocating additional part domains when the number of part domains to be processed by each mobile unit falls below a specific threshold;

a selection unit selecting a newly allocated part domain adjacent to the part domains which are already allocated;

a storing unit storing in each of the mobile units a local map of the whole domain in which at least validly assigned part domains thereof are identified; and

a synchronization unit exchanging notifications whenever at least two of the mobile units are within a predeterminable communication distance, and synchronizing local views of the map of the whole domain of the at least two mobile units to develop a common view of the whole domain, whereby global coordination is not required.

13. A computer software product embodied on at least one non-transitory computer-readable medium storing instructions to control at least one processor to perform a method to process a specific area, comprising:

specifying a part domain of the whole domain which is divided into part domains for assignment provisionally to one of the mobile units, wherein the part domains are selected and allocated using a connectivity graph;

transmitting to the one of the plurality of mobile units an assignment notification indicating the assignment of the part domain to the one of the mobile units provisionally;

making the assignment of the part domain non-provisional if the one of the mobile units does not receive an assignment rejection notification, indicating a rejection of the assignment of the part domain, from at least one other of the plurality of mobile units;

notifying the other mobile units when one mobile unit allocates at least one part domain of the whole domain;

making the assignment of the part domain invalid if the one of the mobile units receives at least one assignment rejection notification;

ensuring each mobile unit has a reserve of part domains to process;

allocating additional part domains when the number of part domains to be processed by each mobile unit falls below a specific threshold;

selecting a newly allocated part domain adjacent to the part domains which are already allocated;

storing in each of the mobile units a local map of the whole domain in which at least validly assigned part domains thereof are identified; and

exchanging notifications whenever at least two of the mobile units are within a predeterminable communication distance, and synchronizing local views of the map of the whole domain of the at least two mobile units to develop a common view of the whole domain, whereby global coordination is not required.