Autonomous navigation system for a mobile robot or manipulator

• US 5,758,298 A
• Filed: 03/15/1995
• Issued: 05/26/1998
• Est. Priority Date: 03/16/1994
• Status: Expired due to Fees

• Current Assignee: Deutsche Telekom AG
• Original Assignee: Deutsche Telekom AG
• Inventors: Guldner, Jurgen
• Primary Examiner(s): LOUIS JACQUES, JACQUES H
• Application Number:
  US08/404,552
• Time in Patent Office: 1,168 Days
• Field of Search: 364/424.02, 364/424.01, 364/461, 364/444, 364/449, 364/450, 364/443, 364/424.03, 364/559, 340/995, 340/988, 395/94, 395/96, 395/80-93, 901/48, 901/1, 901/3, 901/9, 901/46, 901/47, 318/580, 318/587
• US Class Current: 701/23
• CPC Class Codes: G01S 13/931 of land vehicles
• CPC Class Codes: G01S 15/42 Simultaneous measurement of distance and other co-ordinates indirect measurement G01S15/46
• CPC Class Codes: G01S 15/931 of land vehicles
• CPC Class Codes: G05D 1/0255 using acoustic signals, e.g. ultra-sonic singals sonar systems designed for anti-collision purposes G01S15/93
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

In an autonomous navigation system for a mobile robot or a manipulator which is intended to guide the robot through the workspace to a predetermined target point in spite of incomplete information without colliding with known or unknown obstacles. All operations are performed on the local navigation level in the robot coordinate system. In the course of this, occupied and unoccupied areas of the workspace are appropriately marked and detected obstacles are covered by safety zones. An intermediate target point is defined in an unoccupied area of the workspace and a virtual harmonic potential field is calculated, whose gradient is followed by the robot. Mobile robots with such an autonomous navigation system can be used as automated transport, cleaning and service systems.

Claims

1. An autonomous navigation system for a mobile robot moving in a workspace from a starting point to a predetermined target point (TAR), comprising:

a global path planning level (GPP) comprising means to determine a global reference route (RR) to the target point (TAR) from data regarding a topology of the workspace and obstacles present therein known at a time of planning, as well as from measured data regarding an already traveled route in a workspace coordinate system (x_W, y_W),

a sensor system (SEN) comprising means to monitor a vicinity of the robot (ROB) and the workspace and to provide measured sensor data regarding position and the movement of obstacles within a range (R_SEN) thereof,

a local navigation level (LNC) hierarchically placed below the global path planning level (GPP), comprising means to continuously calculate a virtual potential field from the global reference route (RR), an instantaneous position of the robot, and measured data of the sensor system (SEN), and by means of the measured data of the sensor system (SEN) to determine control commands for drive and steering systems of the robot (ROB);

a motion control level (RMC) comprising means for executing control commands issued by the local navigation level (LNC) for the drive and steering systems of the robot

and further comprising means for the local navigation level (LNC) continuously to perform, when an obstacle (OBS) is detected within the detection range (R_SEN) of the sensor system (SEN), the following operations in a robot coordinate system (x_R,y_R) relative to the robot (ROB), namely

a₁) marking the area of the workspace in which the obstacle (OBS) was detected as an occupied area;

b₁) placing a safety zone (SA) over the obstacle (OBS) in such a way that at least a portion of the obstacle detected by the sensor system (SEN) is covered;

c₁) defining an intermediate target point (ITP) in an unoccupied area of the workspace outside the safety zone (SA);

d₁) calculating the virtual potential field as a harmonic potential field (HPF) for the determination of the control commands for the drive and steering systems of the robot (ROB), a gradient of which virtual potential field has inside the safety zone (SA) a component directed away from the obstacle (OBS) and outside of the safety zone (SA) has a component directed toward the intermediate target point (ITP), such that the robot (ROB) following the gradient always moves toward the intermediate target point (ITP) and not into the safety zone (SA);

wherein the means for the local navigation level (LNC) continuously to perform includes means for avoiding a plurality of obstacles (OBS1, OBS2, . . . ) and means for placing respective safety zones (SA1, SA2, . . . ) placed around each of the obstacles, and further comprises;

i) means for selecting a respective unoccupied area between the safety zones which is closest to a global reference route (RR) and which is of sufficient size to allow passage of the robot therethrough;

ii) means for considering in subsequent operations only two bordering safety zones (SA1, SA2) which are immediately adjacent to the selected unoccupied area; and

iii) means for determining a center line (ML), which is equidistant to the two bordering safety zones (SA1, SA2) and has a center zone (MA) on both sides thereof, having a total width less than a least distance between the bordering safety zones (SA1, SA2).

2. An autonomous navigation system in accordance with claim 1, wherein the position of the mobile robot in relation to the center zone (MA) is taken into consideration in such a way that, when the robot (ROB) is in an area outside the center zone (MA), only respectively one virtual harmonic potential field for the closest obstacle or the safety zone (SA1 or SA2) is calculated in respect to the intermediate target point (ITP).

3. An autonomous navigation system in accordance with claim 2, wherein inside the center zone (MA) the weighting of the two virtual harmonic potential fields is selected proportionally to the instantaneous distance of the robot (ROB) from the center line (ML), and that the sum of the weights is one.

4. An autonomous navigation system in accordance with claim 1, wherein the position of the mobile robot in relation to the center zone (MA) is taken into consideration in such a way that, when the robot (ROB) is in the center zone (MA), respectively two virtual harmonic potential fields for the two closest obstacles (OBS1, OBS2) or the safety zones (SA1, SA2) are calculated separately each with respect to the intermediate target point (ITP) and the respective safety zone and a resultant virtual harmonic potential field (HPFR) is calculated for determining the control commands for the drive and steering systems of the mobile robot (ROM) or the drive joints of the manipulator by a weighted linear superposition of the two said potential fields, whose gradient has inside the selected safety zones (SA1, SA2) a component directed away from the respective obstacle (OBS1, OBS2)) and outside of the safety zones (SA1, SA2) has a component directed toward the intermediate target point (ITP), so that the robot (ROB) following the gradient always moves toward the intermediate target point (ITP) and not into the safety zones (SA1, SA2).

5. An autonomous navigation system in accordance with claim 1, wherein the position of the mobile robot in relation to the center zone (MA) is taken into consideration in such a way that

respectively one virtual harmonic potential field is continuously calculated for the two closest obstacles (OBS1, OBS2), with respect to the intermediate target point (ITP) and taking into consideration the respective safety zone (SA1, SA2);

to determine the control commands for the drive and steering systems of the robot (ROB) or the drive joints of the manipulator, the two virtual harmonic potential fields are weighted and linearly superimposed to form a resultant harmonic potential field (HPFR), wherein the sum of the weights is one and wherein the gradient of the resultant virtual harmonic field (HPFR) has inside the selected safety zones (SA1, SA2) a component directed away from the respective obstacle (OBS1, OBS2) and outside of the safety zones (SA1, SA2) has a component directed toward the intermediate target point (ITP), so that the robot (ROB) following the gradient always moves toward the intermediate target point (ITP) and not into the safety zones (SA1, SA2), wherein

if the robot (ROB) is in an area outside of the center zone (MA), the potential field for the closest obstacle (OBS1) is marked with the weight one and the potential field (HPF2) for the obstacle (OBS2) located farther away with the weight zero;

or

if the robot (ROB) is in the center zone (MA), the two weights are selected to be not equal to "zero".

6. An autonomous navigation system in accordance with claim 1, including means for employing the sensor system (SEN) to divide the vicinity of the mobile robot (ROB) or the workspace into sectors and to monitor the vicinity by the sectors, and means for the navigation level (LNC) to mark a sector containing an obstacle (OBS) or a safety zone (SA) as being an occupied sector and defining the intermediate target point (ITP) in an unoccupied sector.

7. An autonomous navigation system in accordance with claim 6, wherein the edge areas of the sectors overlap.

8. An autonomous navigation system in accordance with claim 6, wherein the sensor system (SEN) has a number of sensors which monitor the vicinity of the mobile robot (ROB) or the manipulator or the workspace by sectors and periodically transmit measured data regarding the position and

obstacles in the individual sectors to the navigation level (LNC).

9. An autonomous navigation system in accordance with claim 6, wherein the sensor system has a sensor such as a rotating sensor or a "phased array", which sequentially scans the sectors.

10. An autonomous navigation system in accordance with claim 6, wherein the intermediate target point (ITP) is defined in an unoccupied sector adjoining the occupied sector(s).

11. An autonomous navigation system in accordance with claim 1, wherein the sensor system (SEN) is arranged on a mobile robot (ROB) or a manipulator.

12. An autonomous navigation system in accordance with claim 1, wherein the sensor system (SEN) is fixed in relation to the workspace.

13. An autonomous navigation system in accordance with claim 1, wherein for determining the intermediate target point (ITP), this intermediate target point (ITP) is placed into an unoccupied area of the workspace and approximately at the end of the range (R_SEN) of the sensor system (SEN).

14. An autonomous navigation system in accordance with claim 1, comprising means for determining the intermediate target point (ITP), and wherein the intermediate target point (ITP) is placed into the area of the reference route (RR) outside the safety zone (SA) and outside the range (R_SEN) of the sensor system (SEN).

15. An autonomous navigation system in accordance with claim 1, wherein the safety zone (SA) designed as safety ellipses.

16. An autonomous navigation system in accordance with claim 1, wherein the safety zone (SA) is surrounded by an expanded safety zone which is determined by taking into account traveling speed and dynamics of the robot (ROB), whereby evasion is still possible, even if the robot enters the expanded safety zone, without the actual safety zone being violated.

17. An autonomous navigation system in accordance with claim 1, wherein the gradient of the virtual harmonic potential field (HPF or HPFR) has a finite curvature which the robot can follow taking into consideration dynamics thereof.

18. An autonomous navigation system in accordance with claim 1, wherein the measured data of the sensor system (SEN) is collected in the robot coordinate system (x_R, y_R) specific to the robot,

the navigation level (LNC) calculates the virtual harmonic potential field (HPF or HPFR) in the Cartesian space of the robot coordinate system (x_R, y_R) and transforms the potential into control commands for the drive and steering systems in the configuration space of the robot coordinate system.

19. An autonomous navigation system in accordance with claim 1, wherein the measured data of the sensor system (SEN) is collected in the robot coordinate system (x_R, y_R) specific to the robot (ROB) or the manipulator and are transformed in the configuration space of the robot coordinate system, and

the navigation level (LNC) calculates the virtual harmonic potential field (HPF or HPFR) in the configuration space of the robot coordinate system and directly defines the control commands for the drive and steering systems.

20. An autonomous navigation system in accordance with claim 1, wherein the measured data of the sensor system (SEN) is collected in the workspace coordinate system (x_W, y_W) and transformed in the Cartesian space of the robot coordinate system (x_R, y_R), and

the navigation level (LNC) calculates the virtual harmonic potential field (HPF or HPFR) in the Cartesian space of the robot coordinate system (x_R, y_R) and transforms the potential into control commands for the drive and steering systems in the configuration space of the robot coordinate system.

21. An autonomous navigation system in accordance with claim 1, wherein the measured data of the sensor system (SEN) is collected in the workspace coordinate system (x_W, y_W) and transformed in the configuration space of the robot coordinate system, and

the navigation level (LNC) calculates the virtual harmonic potential field (HPF or HPFR) in the configuration space of the robot coordinate system and in this way directly defines the control commands for the drive and steering systems.

22. An autonomous navigation system for a mobile robot in accordance with claim 1, wherein non-holonomic kinematics and the size of the robot are taken into consideration in the configuration space.

23. An autonomous navigation system for a manipulator in accordance with claim 1, wherein the coordinates of the joints and the size of the links of the manipulator are taken into consideration in the configuration space of the manipulator.