Visual navigation and obstacle avoidance structured light system

• US 5,040,116 A
• Filed: 06/20/1990
• Issued: 08/13/1991
• Est. Priority Date: 09/06/1988
• Status: Expired due to Term

• Current Assignee: Transitions Research Corp.
• Original Assignee: Transitions Research Corp.
• Inventors: King, Steven J., Weiman, Carl F. R., Evans, John M. Jr.
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): ZANELLI, MICHAEL J
• Application Number:
  US07/541,285
• Time in Patent Office: 419 Days
• Field of Search: 364/424.02, 364/449, 364/456, 364/461, 364/513, 364/424.01, 318/587, 180/167, 180/168, 180/169, 356/3, 356/4
• US Class Current: 701/28
• CPC Class Codes: G01S 17/931 of land vehicles
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

A vision system for a vehicle, such as a mobile robot (10) includes at least one radiation projector (14, 16) which projects a structured beam of radiation into the robot'"'"'s environment. The structured beam of radiation (14a, 16a) preferably has a substantially planar pattern of sufficient width to encompass the immediate forward path of the robot and also to encompass laterally disposed areas in order to permit turning adjustments. The vision system further includes an imaging (12) sensor such as a CCD imaging device having a two-dimensional field of view which encompasses the immediate forward path of the robot. An image sensor processor (18) includes an image memory (18A) coupled to a device (18D) which is operable for accessing the image memory. Image processing is accomplished in part by triangulating the stored image of the structured beam pattern to derive range and bearing, relative to the robot, of a object being illuminated. A navigation control system (20) of the robot inputs data from at least the vision system and infers therefrom data relating to the configuration of the environment which lies in front of the robot. The navigation control system generates control signals which drive propulsion and steering motors in order to navigate the robot through the perceived environment.

Claims

1. A method of generating navigation related information for a mobile robot, comprising the steps of:

projecting at least one structured, substantially planar radiation beam into an environment in front of and including a desired path of the robot, said radiation beam forming a linear pattern upon a surface disposed within the environment;

generating a two-dimensional pixel image of the environment, said image including at least an image of said linear pattern which reflects from a surface, if any, within the environment;

locating said image of said linear pattern within the two-dimensional pixel image of the environment of said robot;

inferring from the located position of the linear pattern, within said image of the environment, a range and a bearing of the surface relative to the robot;

generating a geometric map representation that includes a location of the surface, relative to a current location of said robot; and

processing said geometric map representation to generate robot motion control signals to accomplish a forward motion of said robot through the environment.

2. A method as defined in claim 1 wherein the step of generating a two-dimensional pixel image generates an image comprised of a two dimensional array of pixels, each of said pixels having an associated value which is a function of an amount of reflected radiation received from an associated portion of environment.

3. A method as defined in claim 2 wherein the step of locating includes a step of determining a location, within said array of pixels, of one or more pixels which have a value equal to or greater than a predetermined threshold value.

4. A method as defined in claim 3 wherein the step of inferring includes a step of accessing an entry within a data structure having a plurality of range and bearing entries, each of said entries corresponding to one of said pixels, a location of said entry being accessed being a function of said determined pixel location.

5. A method as defined in claim 3 wherein the step of inferring includes a step of converting a value of each of said pixels to a binary value.

6. A method as defined in claim 3 wherein the step of locating includes a first step of searching said image of the environment with a resolution of n pixels to locate a pixel or pixels having a a value equal to or greater than said predetermined threshold value, and further includes a second step of searching said image of the environment with a resolution of m pixels, after said pixel or pixels are located, wherein n is greater than m.

7. A method as defined in claim 1 wherein the step of generating a geometric map representation includes the steps of:

representing an underlying surface over which the robot moves as a two dimensional grip comprised of grid cells; and

designating those grid cells which correspond to a range and a bearing, relative to said robot, to said linear pattern reflecting surface.

8. A method as defined in claim 7 and further comprising the step of:

assigning a confidence factor to designated grid cells based upon a plurality of consistently inferred ranges and bearings corresponding to said designated cells.

9. A method as defined in claim 8 and further comprising a step of:

determining a radius which encloses one or more of said designated grid cells.

10. Apparatus for generating navigation related information for a mobile robot, comprising in combination:

means for projecting at least one structured, substantially planar radiation beam into an environment in front of and including a desired path of said robot, said radiation beam forming a linear pattern upon a surface disposed within the environment;

means for generating a two-dimensional pixel image of the environment, said image including at least an image of said linear pattern which reflects from a surface, if any, within said environment;

means for locating said image of said linear pattern within said two-dimensional pixel image of the environment;

means for inferring, from the located position within said image of said linear pattern, a range and a bearing relative to said robot, of said surface reflecting said linear pattern;

means for generating a geometric map representation of said robot'"'"'s environment, said geometric map representation including the inferred surface position of said linear pattern; and

means for processing said geometric map representation to generate robot motion control signals to accomplish a forward motion of said robot through the environment.

11. Apparatus as set forth in claim 10 wherein said image generating means generates an image comprised of a two dimensional array of pixels, each of said pixels having an associated value which is a function of an amount of reflected radiation within an associated portion of said image.

12. Apparatus as set forth in claim 11 wherein said location means includes means for determining a location within said array of pixels of one or more pixels having a value equal to or greater than a predetermined threshold value.

13. Apparatus as set forth in claim 11 wherein said inferring means includes means for accessing an entry within a data storage means having a plurality of range and bearing entries, each of said entries corresponding to one of said pixels, a location of an accessed entry being a function of a determined pixel location.

14. Apparatus as set forth in claim 11 wherein said means for inferring includes means for converting a value of each of said pixels to a binary value.

15. Apparatus as set forth in claim 11 wherein said locating means includes means for searching said image of the environment with a resolution of n pixels to locate a pixel or pixels having a value equal to or greater than said predetermined threshold value, and further includes means for searching said image of the environment with a resolution of m pixels, wherein n is greater than m.

16. Apparatus as set forth in claim 10 wherein said means for generating a geometric map representation comprises:

means for representing an underlying surface over which the robot moves as a two dimensional grip comprised of grid cells;

means for designating those grid cells which correspond to a range and a bearing, relative to said robot, of said linear pattern reflecting surface;

means for assigning a confidence factor to designated grid cells based upon a plurality of consistently inferred ranges and bearings corresponding to said designated cells; and

means for determining a radius that encloses one or more of said designated grid cells.

17. Apparatus for generating navigation information for a vehicle, comprising:

means for projecting at least one structured, substantially planar radiation beam into an environment in front of and including a desired path of a vehicle;

means for repetitively generating two-dimensional pixel images of the environment as the vehicle moves through the environment, each of said pixel images including an image of a reflection or reflections of said structured radiation beam that reflects from an object or objects within the environment;

means for detecting a location, within each of the two-dimensional pixel images, of said image of the reflection or reflections;

means for determining from a change in the located position of the image of the reflection or reflections, over a plurality of two-dimensional pixel images, a position, relative to the vehicle, of an object or objects disposed within the environment; and

means, responsive to the determined position of the object or objects, for generating vehicle motion control signals so as to steer the vehicle along a path through the environment.

18. Apparatus as set forth in claim 17 wherein said determining means includes means for determining, for each of the two-dimensional pixel images, a range and a bearing, relative to the vehicle, of the object or objects.

19. Apparatus as set forth in claim 18 wherein said determining means further includes means, responsive to the determined ranges and bearings, for generating a geometric map representation of the vehicle'"'"'s environment.

20. Apparatus as set forth in claim 17 wherein each of said two-dimensional pixel images is comprised of a plurality of pixels and wherein said detecting means includes means for searching a first portion of said two-dimensional pixel image with a first pixel resolution, and further includes means for searching a second portion of said two-dimensional pixel image with a second pixel resolution.