Path finding method for a self-propelled mobile unit

• US 5,920,172 A
• Filed: 12/03/1996
• Issued: 07/06/1999
• Est. Priority Date: 05/03/1994
• Status: Expired due to Fees

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Bauer, Rudolf
• Primary Examiner(s): MARTIN, DAVID S
• Application Number:
  US08/760,138
• Time in Patent Office: 945 Days
• Field of Search: 318/580-587, 318/560, 318/567, 318/568.1, 318/568.4, 318/568.12, 901/1, 901/46-47, 701/1, 701/2, 701/22-23, 701/41
• US Class Current: 318/587
• CPC Class Codes: G05D 1/0212 with means for defining a desired trajectory involving a plurality of land vehicles G05D1/0287
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0251 extracting 3D information from a plurality of images taken from different locations, e.g. stereo vision stereoscopic image analysis H04N13/00; depth recovery from images G06T7/593
• CPC Class Codes: G05D 1/0255 using acoustic signals, e.g. ultra-sonic singals sonar systems designed for anti-collision purposes G01S15/93

Abstract

With the improved path finding method a self-propelled mobile unit determines a path around obstacles. A heuristic avoidance strategy is used, whereby the mobile unit, when encountering an obstacle, first evades by taking a first direction and implements an avoidance procedure up to a limit value if it cannot move around the obstacle. Subsequently, the unit returns to the point of departure of the avoidance maneuver and attempts to evade in the other direction. If it is likewise not possible to move around the obstacle in this direction before the limit value is reached, the barrier for the deviation in the avoidance maneuver is incremented. The unit then again attempts to move around the obstacle, first in the original avoidance direction. The limit value is increased again after respectively two more abortive attempts. The procedure is implemented until a path around the obstacle has been found and the destination can be reached. This avoids situations wherein a self-propelled mobile unit remains captured in an endless loop due to an avoidance maneuver in front of an extensive obstacle, whereby it attempts to move around the obstacle toward the right and toward the left but is prevented by the evasion limit from covering enough distance to move around the obstacle.

Claims

1. A method for moving a self-propelled mobile unit relative to an obstacle, comprising the steps of:

moving the self-propelled mobile unit in a predetermined direction until it encounters an obstacle in its path;

deviating the self-propelled mobile unit from the predetermined direction in a first direction, by a predetermined angle which is different from the predetermined direction, proceeding from a point of departure in front of the obstacle;

moving the self-propelled mobile unit in the first direction;

returning the self-propelled mobile unit, if the self-propelled mobile unit encounters the obstacle, to the point of departure,

deviating the self-propelled mobile unit from the predetermined direction in a second direction, by the predetermined angle which is different than the first direction and which is different from the predetermined direction, proceeding from the point of departure;

moving the self-propelled mobile unit in the second direction;

returning the self-propelled mobile unit, if the self-propelled mobile unit encounters the obstacle, to the point of departure;

incrementing the predetermined angle after respectively two abortive attempts; and

repeatedly moving the self-propelled mobile unit in the first direction and then in the second direction and then incrementing the predetermined angle, until the self-propelled mobile unit does not encounter the obstacle.