Visual navigation system for a mobile robot having capabilities of regenerating of hidden images

• US 4,887,223 A
• Filed: 07/20/1988
• Issued: 12/12/1989
• Est. Priority Date: 08/30/1985
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Christian, Donald J.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): HERNDON, HEATHER R
• Application Number:
  US07/222,322
• Time in Patent Office: 510 Days
• Field of Search: 364/518, 364/424.02, 364/444, 364/449, 364/460, 364/513, 180/167-169, 358/103, 358/108, 901/1, 901/47, 901/50
• US Class Current: 382/153
• CPC Class Codes: G05D 1/0234 using optical markers or beacons optical beacons per se G01S1/70
• 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/028 using a RF signal
• CPC Class Codes: G05D 2201/0216 Vehicle for transporting goods in a warehouse, factory or similar

Abstract

A manufacturing system has a material handling system that uses free roaming mobile apparatuses that are under the control of a visual navigation system that has the capability of regenerating images that are temporarily obstructed from view of a visual navigation system. The visual navigation system uses the images to provide commands that navigate an electrical controllable apparatus such as a mobile robot. The mobile robot is fitted with a minimum of three navigation beacons which emit a light visible to overhead television cameras. The beacon area is arranged so as to form a triangle. The shape and dimension of the triangular pattern is measured and stored in a memory unit within the visual navigation system. When a beacon is blocked from view of the television cameras, the visual navigation will regenerate coordinate of the blocked beacon and provide the necessary navigation commands to the mobile apparatus.

Claims

1. A visual navigation system with a regeneration capability comprising:

control and navigation means for obtaining the position of a mobile robot, including;

a predefined visually detectable pattern on the mobile robot;

camera means for obtaining a visual image of said pattern;

control and navigation circuit means electrically connected to the camera means, for regenerating portions of the predefined visually detectable pattern which are hidden from the field of view of the camera means;

wherein the X-Y position and heading of the mobile robot are determined by the control and navigation circuit means from the visual image, and said regenerated portions thereof, of the predefined visually detectable pattern.

2. The visual navigation system according to claim 1, wherein the predefined visually detectable pattern is a predetermined number of lighted points mounted in predetermined locations on the mobile robot, in a predefined pattern, wherein the lighted points are separated from one another by predefined distances.

3. The visual navigation system according to claim 2, wherein the camera means comprises:

a raster scan camera means for converting light to an electrical signal that represents light intensity in relationship to raster scan position of the raster scan camera means; and

first identifying means for identifying the raster scan position by frame, row and column coordinates, the raster scan camera means having a spatial plumbed point.

4. The visual navigation system according to claim 3, wherein the first identifying means comprises:

first transformation means for transforming the electrical signal from an analog signal to a digital signal.

5. The visual navigation system according to claim 4, wherein the first transformation means comprises:

second identifying means for identifying clusters of pixels of light from the electrical signal and providing coordinates of the clusters of pixels of light thereby;

second transformation means for transforming the clusters of pixels representing light intensity into centroids having identifiable coordinates.

6. The visual navigation system according to claim 5, wherein the second transformation means comprises:

digitizing means for digitizing the electrical signal to obtain a first digital signal;

dividing means for dividing the first digital signal into a row digital signal and a column digital signal that correspond to the raster coordinates;

summation means for performing a vector summation of the row and column digital signals to obtain a first and second integrated signal; and

comparator means for comparing the first and second integrated signals to a predefined threshold to obtain a first ordinate signal and a second ordinate signal thereby.

7. The visual navigation system according to claim 6, further comprising:

means for locating centroids that represent the clusters of pixels of light; and

means for comparing a pattern created by the centroids to the predefined pattern of lighted points.

8. The visual navigation system according to claim 7, wherein the means for comparing a pattern comprises:

means for obtaining chordal lengths between the centroids;

length means for comparing the chordal lengths to the predefined distance;

means for determining if the centroids represent the cluster of lighted points from the chordal lengths.

9. The visual navigation system according to claim 8, wherein the predefined pattern is a right triangle, the predetermined number of lighted points is three in number, and the means for determining if the centroids represent the cluster of lighted points comprises:

means for identifying a chordal length having the same length as the predefined distance that represents the length of the hypotenuse of right triangle;

means for ordering the chordal lengths in a first direction from the identified chordal length;

means for determining if the order of chordal lengths are ordered so as to have a length that has a predefined relationship to the lengths of the adjoining chordal lengths;

means for obtaining the angle between the chordal lengths; and

means for comparing the angles between the chordal lengths to the angles of the right triangle.

10. The visual navigation system according to claim 9, further comprising:

means for summing the chordal lengths; and

means for comparing the summation of the chordal lengths to the length of the perimeter of the right triangle.

11. The visual navigation system according to claim 7, wherein the predefined pattern is a right triangle and the means for regenerating includes means for identifying the coordinates of a missing cluster of light from a first and second centroid that represent two visible clusters of light that are arranged in the right triangle pattern, wherein the means for identifying comprises:

means for obtaining the distance between the first and second centroid to obtain a centroidal distance;

means for comparing the centroidal distances to the predefined distances and to associate the centroidal distance with a member of the predefined distances that is the closest in length;

means for establishing intersections of arcs having radii equal in length to nonassociated members of the predefined distances and centered about the first and second centroids to obtain a first, second, third and fourth intersection, said first, second, third and fourth intersections having identifiable coordinates;

means for selecting first and second candidate images from the intersections of arcs; and

means for selecting the hidden image from the first and second candidate images.

12. The visual navigation system according to claim 11, wherein the means for selecting the first candidate image comprises:

means for obtaining the length between the first centroid and the first intersection to obtain a first chord having a first length;

means for obtaining the length between the second centroid and the first intersection to obtain a second chord having a second length;

means for selecting a hypotenuse from the first chord, second chord and chordal length that is closely equal to the length of the hypotenuse of the right triangle to obtain a first side;

means for ordering the chordal length, first chord, and second chord according to coordinates beginning with the first side and going in a first direction; and

means for identifying the first intersection as a first primary candidate if the lengths increase in the ordered direction and the second intersection as the first primary candidate if the lengths decrease in the ordered direction.

13. The visual navigation system according to claim 12, wherein the means for selecting the second primary candidate comprises:

means for obtaining the distance between the first primary candidate and the third intersection to obtain a third length;

means for obtaining the distance between the first primary candidate and the fourth intersection to obtain a fourth length; and

means for comparing the third length to the fourth length to identify the third intersection as a second primary candidate when the third length is longer than the fourth length and the fourth intersection as the second primary candidate when the fourth length is longer than the third length.

14. The visual navigation system according to claim 13, wherein the means for selecting the hidden image comprises:

means for obtaining the distance between the spatial plumbed point and the first primary candidate, to obtain a fifth length;

means for obtaining the distance between the spatial plumbed point and the second primary candidate, to obtain a sixth length; and

means for comparing the fifth length to the sixth length and to identify the first primary candidate as having the spatial coordinates of the hidden image when the fifth length is longer than the sixth length and to identify the second primary candidate as having the spatial coordinates of the hidden image when the sixth length is longer than the fifth length.

15. The visual navigation system according to claim 14, wherein the means for comparing a pattern comprises:

means for obtaining chordal lengths between the centroids and the spatial coordinates of the hidden image;

means for comparing the chordal lengths to the predefined distances; and

means for determining if the centroids and the spatial coordinates of the hidden image represent the cluster of lighted points from the chordal lengths.

16. The visual navigation system according to claim 15, wherein the predefined pattern is a right triangle and the means for determining if the centroids and the coordinates of the hidden image represent the cluster of lighted points comprise:

means for identifying a chordal length having the same length as the predefined distance that represents the length of the hypotenuse of the right triangle;

means for ordering the chordal lengths in a first direction from the identified chordal length;

means for determining if the order of chordal lengths are ordered so as to have a length that has a predefined relationship to the lengths of the adjoining chordal lengths;

means for obtaining the angle between the chordal lengths; and

means for comparing the angles between the chordal lengths to the angles of the right triangle.

17. The visual navigation system according to claim 16, further comprising:

means for summing the chordal lengths; and

means for comparing the summation of the chordal lengths to the length of the perimeter or the right triangle.

18. A method for mobile robot navigation and hidden image regeneration, comprising:

obtaining the position of the mobile robot, including;

using a camera means to obtain a visual image of a predefined visually detectable pattern on the mobile robot;

regenerating portions of the predefined visually detectable pattern which are hidden from the field of view of the camera means;

using a control and navigation circuit means to determine the X-Y position and heading of the mobile robot, from the visual image, and said regenerated portions thereof, of the predefined visually detectable pattern.

19. The method according to claim 18, wherein the step of obtaining an image of the predefined visually detectable pattern on the mobile robot comprises:

providing the predefined visually detectable pattern by providing a predetermined number of lighted points and mounting them in predetermined locations on the mobile robot, in a predefined pattern, and separating the lighted points one from the other by predefined distances.

20. The method according to claim 19, wherein the step of obtaining an image of the lighted points comprises the steps of:

identifying clusters of light that represent the lighted points which includes the step of;

converting light with a raster scan camera from the lighted points to an electrical signal that represents light intensity in relationship to raster scan position of the raster scan camera, the raster scan position being identified by frame, row and column coordinates, the raster scan camera having a spatial plumb point.

21. The method according to claim 20, wherein the step of identifying clusters of light comprises the step of:

transforming the electrical signal from an analog signal to a digital signal.

22. The method according to claim 21, wherein the step of transforming comprises the steps of:

identifying clusters of pixels of light from the electrical signal and providing coordinates of the clusters of pixels of light thereby; and

transforming the clusters of pixels representing light intensity into centroids having identifiable coordinates.

23. The method of claim 22, wherein the step of transforming comprises:

digitizing the electrical signal to obtain a first digital signal;

dividing the first digital signal into a non digital signal and a column digital signal that correspond to the raster coordinates;

performing a vector summation of the row and column digital signals to obtain a first and second integrated signal; and

comparing the first and second integrated signals to a predefined threshold to obtain a first ordinate signal and second ordinate signal thereby.

24. The method according to claim 23, wherein the identifying step comprises:

locating centroids with a window that represents the clusters of light, the window being bounded by the first and second ordinates; and

comparing a pattern created by the centroids to the predefined pattern of the lighted points.

25. The method according to claim 24, wherein the step of comparing a pattern comprises:

obtaining the chordal lengths between the centroids;

comparing the chordal lengths to the predefined distances; and

determining if the centroids represent the cluster of lighted points from the chordal lengths.

26. The method according to claim 25, wherein the predefined pattern is a right triangle and the step of determining if the centroids represent the cluster of lighted points comprises the steps of:

identifying a chordal length having the same length as the predefined distance that represents the length of the hypotenuse of the right triangle;

ordering the chordal lengths in a first direction from the identified chordal length;

determining if the order of chordal lengths are ordered so as to have a length that has a predefined relationship to the lengths of the adjoining chordal lengths;

obtaining the angle between the chordal length and

comparing the angles between the chordal lengths to the angles of the right triangle.

27. The method according to claim 26, further comprising the steps of:

summing the chordal lengths; and

comparing the summation of the chordal lengths to the length of the perimeter of the right triangle.

28. The method according to claim 27, wherein the predefined pattern is a right triangle and the method for regenerating hidden portions includes the steps of identifying the coordinates of a missing cluster of light from a first and second centroid that represent two visible clusters of light that are arranged in the predefined pattern, wherein the steps of identifying comprise:

obtaining the distance between the first and second centroid to obtain a centroidal distance;

comparing the centroidal distance to the predefined distances and to associate the centroidal distance with a member of the predefined distances that is the closest in length to the centroidal distance;

establishing intersections of arcs having radii equal in length to nonassociated members of the predefined distances and centered about the first and second centroids to obtain a first, second, third and fourth intersection, said first, second, third and fourth intersections having identifiable coordinates;

selecting first and second candidate images from the intersections of arcs; and

selecting the hidden image from the first and second candidate images.

29. The method according to claim 28, wherein the step of selecting the first candidate image comprises:

obtaining the distance between the first centroid and the first intersection to obtain a first chord of a first length;

obtaining the distance between the second centroid and the first intersection to obtain a second chord of a second length;

selecting from the first length, second length or chordal length a length that is closely equal to the length of the hypotenuse of the right triangle to obtain a first side;

ordering the chordal length, first chord, and second chord according to coordinates beginning with the first side and going in a first direction; and

identifying the first intersection as a first primary candidate if the length of the distances increases in the ordered direction and the second intersection as the first primary candidate if the lengths decrease in the ordered direction.

30. The method according to claim 29, wherein the steps of selecting the second primary candidate comprise:

obtaining the distance between the first primary candidate and the third intersection to obtain a third length;

obtaining the distance between the first primary candidate and the fourth intersection to obtain a fourth length; and

comparing the third length to the fourth length to identify the third intersection as a second primary candidate when the third length is longer than the fourth length and the fourth intersection as the second primary candidate when the fourth length is longer than the third length.

31. The method according to claim 30, wherein the steps of selecting the hidden image comprise:

obtaining the distance between the spatial plumbed point and the first primary candidate, to obtain a fifth length;

obtaining the distance between the spatial plumbed point and the second primary candidate, to obtain a sixth length;

comparing the fifth length to the sixth length and to identify the first primary candidate as having the coordinates of the hidden image when the fifth length is longer than the sixth length and to identify the second primary candidate as having the coordinates of the hidden image when the sixth length is longer than the fifth length.

32. The method according to claim 31, wherein the step of comparing a pattern comprises:

obtaining chordal lengths between the centroids and the spatial coordinates of the hidden image;

comparing the chordal lengths to the predefined distances; and

determining if the centroids and the spatial coordinates of the hidden image represent the cluster of lighted points from the chordal lengths.

33. The method according to claim 32, wherein the predefined pattern is a right triangle and the steps of determining if the centroids and the coordinates of the hidden image represent the cluster of lighted points comprise:

identifying a chordal length having the same length as the predefined distance that represents the length of the hypotenuse of the right triangle;

ordering the chordal lengths in a first direction from the identified chordal length;

determining if the order of chordal lengths are oredered so as to have a length that has a predefined relationship to the lengths of the adjoining chordal lengths;

obtaining the angle between the chordal lengths; and

comparing the angles between the chordal lengths to the angles of the right triangle.

34. The method according to claim 33, further comprising the steps of:

summing the chordal lengths; and

comparing the summation of the chordal lengths to the length of the perimeter of the right triangle.