Method for the orientation, route planning and control of an autonomous mobile unit

• US 5,793,934 A
• Filed: 12/17/1996
• Issued: 08/11/1998
• Est. Priority Date: 06/22/1994
• Status: Expired due to Fees

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Bauer, Rudolf
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Smith, Jeffrey S.
• Application Number:
  US08/750,883
• Time in Patent Office: 602 Days
• Field of Search: 318/587, 318/568.12, 364/424.027, 364/424.029, 364/424.031, 364/424.032, 364/461, 395/85, 395/90, 395/94, 901/1
• US Class Current: 700/250
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

Different bonus values and penalty values are allotted for each partial task of the unit such as, for example, drive from A to B, hold your positional uncertainty below a specific threshold, or draw up a map of the surroundings and add landmarks to it. Performance weightings for the individual tasks are yielded, in conjunction with a need to carry the latter out, after analysis of the bonus values and penalty values, and are evaluated in a control unit. Furthermore, in the context of the method a local planning horizon is specified in which the surroundings of the unit are subdivided into grid cells. Preferred directions, which lead the unit by the shortest path to already known or unconfirmed landmarks are stored for these grid cells, with the aim of reducing the positional uncertainty, or of being able to confirm a landmark. All the different routes which are possible within the framework of this grid are then investigated as to what contribution they make to enable the unit to reach the goal. In this process, the different costs and benefits per partial task are added up along each path. That route is selected which has the greatest benefit or the lowest loss. Finally, a destination which is situated outside the local planning horizon is reached by carrying out the method cyclically.

Claims

1. A method for orientation, route planning and control of an autonomous mobile unit, comprising the steps of:

in a first step the unit drawing up a map of its surroundings in a first routine to be evaluated by using an on-board sensor arrangement for surveying the surroundings and, starting from a position of the unit, evaluating features of the surroundings which become known to the unit and entering the features into the map of the surroundings in a form of landmarks;

in a second step, in surroundings the unit does not know completely, the unit moves in a second routine to be evaluated from a starting point via at least one partial goal in a direction of a destination and in so doing makes use of at least the map of the surroundings and the sensor arrangement for orientation, route planning and control;

in a third step in a third routine to be evaluated the unit monitors errors, due to measuring inaccuracy of the sensor arrangement, in determination of a position of the unit, as positional inaccuracy, and reduces the errors by approaching a landmark;

in a fourth step at least one bonus value and/or penalty value is respectively allotted for each routine of the first, second and third routines to be carried out, as a function of contribution which the at least one bonus value and/or penalty value make in order to enable the unit to reach its destination whereby at least one destination direction deviation and/or a great positioning error and/or a slight plurality of landmarks are poorly evaluated in the map;

in a fifth step as a consequence of a common evaluation of respective bonus values and/or penalty values in a control unit of the unit at least the routine to be carried out is determined, and a route of the unit is planned and controlled.

2. The method as claimed in claim 1, wherein at least for one routine to be evaluated of the first, second and third routines a weighting factor is obtained by adding up associated bonus values and/or penalty values and multiplying by a necessity value currently valid for the at least one routine.

3. The method as claimed in claim 1, wherein at least for each routine to be evaluated of the first, second and third routines a threshold value is fixed for the bonus values and/or penalty values upon overshooting or undershooting of the threshold value which the at least one routine is carried out in a prioritized fashion.

4. The method as claimed in claim 1, wherein in order to reduce positional uncertainty a landmark is deliberately approached and surveyed, the unit knowing its location in the surroundings with great accuracy.

5. The method as claimed in claim 1, wherein at least one penalty value is a function of a path distance the unit must cover to perform a routine to be evaluated.

6. The method as claimed in claim 1 wherein at least the bonus value for the second routine is a function of an angle which is formed by a selected travel direction with a start/destination axis.

7. The method as claimed in claim 3, wherein, referred to elongated landmarks, at least the bonus value for the third routine is a function of a magnitude of a segment projected on to a normal (p_r) of the landmark, which is produced by projecting a positional uncertainty area around a site of the unit.

8. The method as claimed in claim 1, wherein a landmark whose position in the surroundings of the unit is known only very inaccurately is deliberately approached and surveyed.

9. A method for orientation, route planning and control of an autonomous mobile unit, comprising the steps of:

in a first step the unit drawing up a map of its surroundings in a first routine to be evaluated by using an on-board sensor arrangement for surveying the surroundings and, starting from a position of the unit, evaluating features of the surroundings which become known to the unit and entering the features into the map of the surroundings in a form of landmarks, the autonomous unit drawing up a cellularly structured map of surroundings of the unit in the first routine, the landmarks being distinguished as confirmed and unconfirmed landmarks as a function of the number of measuring operations affecting the landmarks and/or of the number of the locations from which the landmarks were surveyed, and at least the following information being stored per cell of the map of the surroundings;

i) seen from the cell, is a landmark located in a measuring range of a distance meter on-board the unit;

ii) if i) is answered affirmatively,

for confirmed landmarks;

a direction of distance measurement along a direction between the affected cell and at least one confirmed landmark;

for unconfirmed landmarks;

the travel direction along at least one unconfirmed landmark;

iii) how often has the affected cell already been crossed;

in a second step, in surrounding the unit does not know completely, the unit moves in a second routine to be evaluated from a starting point via at least one partial goal in a direction of a destination and in so doing makes use of at least the map of the surroundings and the sensor arrangement for orientation, route planning and control,

in a third step in a third routine to be evaluated the unit monitors errors, due to measuring inaccuracy of the sensor arrangement, in determination of a position of the unit, as positional inaccuracy;

in a fourth step at least one bonus value and/or penalty value is respectively allotted for each routine of the first, second and third routines to be carried out, as a function of contribution which the at least one bonus value and/or penalty value make in order to enable the unit to reach its destination whereby at least one destination direction deviation and/or a great positioning error and/or a slight plurality of landmarks are poorly evaluated in the map, a planning horizon being prescribed as a number of cells to be driven through in succession possible travel directions of a unit being discretized such that, starting from a given cell position of the unit, each immediately adjacent cell being reached only in respectively one discrete travel direction, and for the planning horizon all routes which can be combined with using the discrete travel directions, being evaluated by adding up respectively occurring bonus values and/or penalty values in the control unit of the unit and that route being traveled which achieves a highest bonus value or lowest penalty value; and

in a fifth step as a consequence of a common evaluation of respective bonus values and/or penalty values in a control unit of the unit at least the routine to be carried out is determined, and a route of the unit is planned and controlled.

10. The method as claimed in claim 9, wherein the degree-of-occupancy values, which are incremented per cell, are stored as a measure of the probability of occurrence of an obstacle.

11. The method as claimed in claim 9, wherein the cells are square, thereby establishing eight travel directions.

12. The method as claimed in claim 9, wherein the cells are hexagonal, thereby establishing six travel directions.

13. The method as claimed in claim 9, wherein the combined routes are evaluated in a configuration space whose space axes are bounded by the planning horizon in two axial directions, and the number of discrete travel directions is bounded in a third travel direction, common information from information stored in the cells being stored in the direction of the travel direction axis for all respectively superimposed cells.

14. The method as claimed in claim 13, wherein at least a route cell sequence which achieves a highest bonus value and/or lowest penalty value is stored per cell of the configuration space.

15. The method as claimed in claim 9, wherein a resultant benefit for a route combination is determined as:

space="preserve" listing-type="equation">R.sub.N =α

.sub.u *B.sub.u +α

.sub.c *B.sub.c +α

.sub.ƒ

*B.sub.ƒ

wherein

B is a partial benefit,

α

is a weighting factors,

index u is task of driving to a goals,

index c is task of monitoring positional uncertainty,

index f is task of drawing up map,

individual partial benefits being yielded as ##EQU10## wherein N_ui (p)=cos(φ

) as partial benefit for the route from one cell to the next cell with partial goal P and φ

as an angle between a discrete travel direction and a start/goal direction ##EQU11## σ

specifying positional uncertainty in the x-direction , σ

positional uncertainty in the y-direction and σ

positional uncertainty in the φ

-direction of rotational orientation of the unit ##EQU12## wherein

space="preserve" listing-type="equation">N.sub.ƒ

i =(V.sub.i +T.sub.i +O.sub.i)*C.sub.i

and V_i as functional value of a function which, depending on a quantity of the crossing operations in a cell, supplies a real number which continually decreases with increasing quantity, T_i as a functional value of a function which, depending on a quantity of the unconfirmed landmarks which are seen from a cell, supplies a real number which continually increases with increasing quantity, and O_i as a functional value of a function which, depending on correspondence between actual travel direction and a travel direction stored for the cell, supplies a real number which continually increases with a travel direction stored for the cell, and C_i as a functional value of a function which, depending on a quantity of the confirmed landmarks which are seen from a cell, delivers a continually decreasing real number with increasing quantity.

16. The method as claimed in claim 15, wherein the following functions hold:

##EQU13## with Z_u as a quantity of crossings of the cell considered ##EQU14## with Z_Lu as a quantity of visible unconfirmed landmarks ##EQU15## with Z_F as a quantity of stored travel directions corresponding to current travel direction of a unit ##EQU16## with Z_Lb as a quantity of visible confirmed landmarks.

17. The method as claimed in claim 9, wherein a resultant benefit for an individual cell is calculated as:

space="preserve" listing-type="equation">R.sub.i =α

.sub.u *B.sub.ui +α

.sub.ƒ

*B.sub.ƒ

i +α

.sub.c *(1-B.sub.ci).

18. The method as claimed in claim 9, wherein a resultant benefit for an individual cell is calculated as:

space="preserve" listing-type="equation">R.sub.i =(α

.sub.u *B.sub.ui +α

.sub.ƒ

*B.sub.ƒ

i)*B.sub.ci.