Navigation system for a mobile robot

• US 5,363,305 A
• Filed: 02/28/1992
• Issued: 11/08/1994
• Est. Priority Date: 07/02/1990
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Research Institute, Inc. (NEC Corporation)
• Inventors: Durrant-Whyte, Hugh, Cox, Ingemar, Leonard, John J.
• Primary Examiner(s): Ray, Gopal C.
• Assistant Examiner(s): DAVIS, GEORGE B
• Application Number:
  US07/843,570
• Time in Patent Office: 984 Days
• Field of Search: 364/443, 364/424.02, 395/88, 395/93, 901/1
• US Class Current: 701/200
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G05D 1/0234 using optical markers or beacons optical beacons per se G01S1/70
• 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/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

A navigation system for a mobile autonomous robot that includes apparatus for creating and maintaining a map of an environment the mobile autonomous robot is to traverse including provision for storing in a map at an assigned location features representative of geometric beacons located in the environment. Because of the uncertainty in its sensor'"'"'s operating conditions and changes in the environment, a credibility measure is associated with each map feature stored. This credibility measure is increased or decreased whenever the map feature assigned to a location matches or does not match, respectively, a geometric beacon corresponding to such location. Whenever a geometric beacon is observed for a location that does into match a previously stored map features, an appropriate map feature is added for such location.

Claims

1. A navigation system to be carried on a mobile robot that is to traverse an environment that includes geometric beacons comprising,

means for scanning the environment for detecting reflections from geometric beacons in the environment and from said detected reflections extracting information as to the location of observed geometric beacons,

means responsive to the information extracted from the detected reflections for storing in storing means the location of said geometric beacons as features in a map with an initial credibility value, unless already stored in the storing means,

means for matching the location of geometric beacons extracted from said reflections information with map features in said storing means,

means for increasing the credibility value of a map feature in the storing means each time said feature is found to match the location of an observed geometric beacon as the robot traverses the environment,

means for decreasing the credibility value of a map feature in the storing means when no beacon is observed by the scanning means at the corresponding location as the robot traverses the location where such geometric beacon should have been observed, and

means for computing the position of the robot that includes selecting for the computation the needed data from those geometric beacons then being observed that match the map features having relatively high credibility values.

2. The navigation system of claim 1 in which the means for scanning comprises means for radiating ultrasonic energy for reflection by geometric beacons for subsequent detection by the means for scanning.

3. The navigation system of claim 2 in which the means for extracting from the detected reflections information as to the location of the geometric beacons is Kalman filter means.

4. The navigation system of claim 1 in which the means serving as a map includes a semiconductive memory in which are stored as a map feature the coordinates of each geometric beacon observed and an associated credibility value, which value can be increased or decreased as a geometric beacon is observed or not observed at the corresponding coordinates in subsequent traversals by the robot of the environment.

5. A method for use by a robot in navigating a limited environment comprising the steps of

scanning repeatedly the environment as the robot moves therealong for reflecting surfaces that can be used as observed geometric beacons and ascertaining their coordinates relative to a reference origin position,

scanning the coordinates of said observed beacons in a storage medium as map features and associating with each feature a credibility value that can be increased or decreased,

on each scan using the features previously stored for predicting the locations of geometric beacons that should be observed in such scan,

matching such predictions with the locations of geometric beacons observed in the scan,

when there is a match, increasing the credibility value of any feature matched to the location of a beacon observed in the scan,

when there is no match decreasing the credibility value of any feature representing a beacon not matched with a predicted beacon at its location, and

determining the position of the robot in the environment by reference to its position relative to beacons then being observed corresponding to map features of highest credibility values.

6. The method of claim 5 in which the scanning utilizes ultrasonic energy.

7. The method of claim 5 in which the scanning utilizes electromagnetic energy chosen from microwave, infra-red and visible light.