Robot intelligence in natural environments

• US 6,941,191 B2
• Filed: 10/06/2003
• Issued: 09/06/2005
• Est. Priority Date: 04/05/2001
• Status: Expired due to Fees

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Jaeger, Markus
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Marc, McDieunel
• Application Number:
  US10/678,262
• Publication Number:
  US 20040068348A1
• Time in Patent Office: 701 Days
• Field of Search: 700/245, 700/250, 700/253, 700257-259, 700/264, 701/1, 701/3, 701 23- 26, 701/120, 701/123, 701/200, 701/207, 701/215, 701300-301, 901/47
• US Class Current: 700/245
• CPC Class Codes: G05D 1/0295 by at least one leading vehicle of the fleet

Abstract

A method for automatic, decentralized coordination of the movement paths of mobile robots in order to prevent collisions and to detect and resolve mutual blockings. According to the method, a robot receives position information from other robots and establishes a coordinating connection with another robot if the position falls below a minimum allowable distance. One of the robots is then chosen as coordinator and the other robot is chosen as partner. The coordinator initiates an algorithm for the prevention of collisions, wherein a time sequence diagram is determined for the motion path segments of the coordinator and the partner. A robot for detecting robots that are mutually blocking one another in a circuit initiates an algorithm for detecting blocking if the robot has not been given authorization to execute its next motion path segment. An algorithm for resolving the blocking is initiated if robots mutually blocking each other in a circuit are detected by the detecting robot. The algorithm includes a first step and optionally a second step, whereby the sequence for the execution of the next motion path segment of the robots is interchanged during a coordinating connection and the motion paths of one or more robots mutually blocking each other in a circuit are newly planned.

Claims

1. A method for automatic, decentralized coordination of independent motion paths that are broken down into motion path segments of a plurality of mobile robots communicating with each other within a specified geographical area, to avoid collisions and to detect and resolve mutual blockings, comprising:

a robot receiving positioning information from the other robots and determining its distance (d_rob) to the other robots,

when the robot moves to within a specified relative distance (d_safe) of at least one of the other robots, the robot setting up and maintaining a coordination connection to these robots to coordinate its motion path with the motion paths of the at least one other robot for as long as its distance is less than the specified relative distance, in which case one of the robots linked by the coordination connection is selected as a coordinator and the other robot is selected as a partner,

the coordinator requesting the planned movement segments of the partner and initiating an algorithm for avoiding collisions, with which the motion path segments of the partner are harmonized with the motion path segments of the coordinator, in order to determine the collision areas in which the robots are less than a specified minimum distance (d_min) apart and in which a timing sequence scheme for the motion path segments of the coordinator and the partner is determined,

the coordinator giving permission to itself and to the partner to execute the next motion path segment, on the basis of the timing sequence scheme for the motion path segments of the coordinator and the partner, whereby the motion path segment is executed only when the permission is granted,

one of the robots initiating an algorithm to detect blocking in order to detect a group of mutually blocking robots if the detecting robot has not been granted permission to execute its next motion path segment,

on detection of a group of mutually blocking robots by the detecting robot, the detecting robot initiating an algorithm to resolve the blocking, whereby the resolving algorithm comprises at least a first step and optionally a second step, wherein, in the first step, the mutually blocking robots that are connected by the coordination connection exchange the sequence for executing the next motion path segment, and in the second step, at least one of the mutually blocking robots plan new motion paths, with the second step being executed only if the first step fails to resolve the blocking.

2. The method according to claim 1, wherein the algorithm for avoiding collisions determines the time sequence scheme for the planned motion path segments of the coordinator and the partner by:

presenting the motion path segments of the coordinator and the partner in accordance with a horizontal and a vertical axis of a two-dimensional diagram,

checking for positions of the robots in the motion path segments that produce a distance for the robots that is less than a specified minimum distance d_min and marking the positions as collision areas,

establishing an execution path that avoids all of the marked collision areas, beginning with a bottom left corner and ending in a top right corner of the two-dimensional diagram,

dividing the execution path into linear sections, beginning with the lower left corner of the diagram, and making an entry for each linear section in the time sequence scheme, wherein for each horizontal section the coordinator, for each vertical section the partner, and for each diagonal section both the coordinator and the partner are granted permission to execute the next motion path segment.

3. The method according to claim 2, wherein the execution path for the motion path segments is established to be as short as possible.

4. The method according to claim 3, wherein the execution path established has collision paths that meet in the lowest left corner of the collision areas.

5. The method according to claim 1, wherein the algorithm to detect blocking includes:

defining a directed coordination connection such that the origin of a directed coordination connection is assigned to a waiting robot and the destination of the directed coordination connection is assigned to a priority robot,

transmitting a test message along the newly defined directed coordination connection,

receiving the test message from the transmitting robot and forwarding the test message to all of the receiving robot'"'"'s outbound coordination connections, along with an identification of the robot forwarding the test message,

receiving the forwarded test message from the forwarding robot and checking as to whether the forwarded test message originated from the robot performing the checking, and

detecting a mutual blocking situation with a simultaneous identification of all robots, in the event of at least one of;

(i) the test message originates from one robot, and (ii) if the test message does not originate from the one robot, the test messages are forwarded to all outbound coordination connections with the identifications.

6. The method according to claim 1, wherein the first step of the algorithm to resolve the blocking includes:

sending a change message to the group of the mutually blocking robots,

receiving a change message by the robots involved in the group of mutually blocking robots and inquiring of the coordinator as to whether the sequence for executing the next motion path segment is to be swapped,

discarding the change message if swapping the sequence of execution resolves the blocking, or receiving the change message by the robot initiating the change message in order to initiate the second step,

and whereby the second step of the algorithm to resolve the blocking includes;

sending a replan message to the group of the mutually blocking robots,

receiving the replan message by the robots involved in the group of mutually blocking robots and requesting the robot planning the motion path to plan an alternate motion path,

discarding the new plan message and removing all directed coordination connections if an alternate motion path is successfully planned by the robot, or receiving the new plan message by the robot initiating the new plan message and thereupon initiating a freeing message,

sending the freeing message to the group of mutually blocking robots, whereby the freeing message is enabled to leave the group, to cause all available robots to plan an alternate motion path and to register whether a robot other than the mutually blocking robots is located in the vicinity of the mutually blocking robots,

receiving a freeing message by the robots initiating the freeing message, checking whether any of the mutually blocking robots can plan an alternate motion path and whether any of the mutually blocking robots registers a non-blocking robot in its vicinity, and canceling the blocking resolution if an alternate motion path is planned or a non-blocking robot is registered.

7. The method according to claim 1, wherein the mobile robots comprise robots configured to jointly clean an area.

8. The method according to claim 7, wherein the specified geographical area comprises at least one of a supermarket and an airport.

9. A method for automatic, decentralized coordination of movement paths between at least two mobile robots, which prevents collisions and detects and resolves mutual blocking situations between the mobile robots, comprising:

one of the robots receiving position information from the other of the robots;

establishing a coordinating connection between the one robot and the other robot if, according to the position information, a position between the robots falls below a predetermined minimum acceptable distance;

designating the two mobile robots as respectively either a coordinator or a partner;

wherein the coordinator initiates a collision avoidance algorithm that utilizes a time sequence diagram for motion path segments of the coordinator and the partner in order to prevent a collision between the one robot and the other robot, and wherein the collision avoidance algorithm includes granting authorization by the coordinator to execute a next step in the motion path segments to at least one of the coordinator and the partner;

in the event of a failure by the collision avoidance algorithm to successfully grant the authorization, initiating an algorithm for detecting a mutual blocking situation;

if the blocking detection algorithm detects a mutual blocking situation, initiating an algorithm for resolving the blocking, including interchanging a sequence for executing the next step in the motion path between the coordinator and the partner.

10. The method according to claim 9, wherein, in the event of a failure by the interchanging to successfully resolve the mutual blocking situation, the blocking resolution algorithm replans the motion paths of the motion path segments of the time sequence diagram.