Patent Publication Number: US-2002004699-A1

Title: System and method for guiding a vehicle

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
     [0001] This application claims priority benefits based on Swedish Patent Application No. 0000948-0, filed on Mar. 21, 2000, and U.S. Provisional Application 60/207,840, filed on May 30, 2000, the technical disclosures of both of which are hereby incorporated herein by reference. 
    
    
     
       BACKGROUND OF THE INVENTION  
       [0002] 1. Field of the Invention  
       [0003] The present invention relates to self-propelled vehicles and to systems and methods for guiding a self-propelled vehicle.  
       [0004] 2. Description of the Related Art  
       [0005] Self-propelled vehicles are becoming ever more common in industry. Such vehicles include various types of robots used in a number of applications. For example, robots are used to move items stored in storage warehouses or to move cars between different assembly stations.  
       [0006] Automated self-propelled vehicles either move by themselves in a predetermined pattern, or they include a guidance system to navigate a certain area.  
       [0007] U.S. Pat. No. 4,656,406 discloses a system for guiding automated vehicles that sense an electric field from wires buried underneath the floor. As a result, the vehicle can follow the guidepath provided by the wires. A drawback of this system, however, is that it may require a considerable investment to change the path followed by the vehicle.  
       [0008] U.S. Pat. No. 5,814,961 discloses an optical guidance system for an automated vehicle. The &#39; 961  patent discloses that the floor on which the vehicle moves has grooves defining the path of the vehicle. The vehicle then optically detects these grooves as it moves. However, this system may also require a substantial investment if one desires to change the path of the vehicle since the grooves in the floor must be changed.  
       [0009] U.S. Pat. No. 5,999,866 describes a vehicle that records images on the floor on which it moves and compares the recorded images with a stored image of the floor. Based on this comparison, the vehicle can then determine its position. Thus, in this system, the entire floor surface may need to be mapped before the vehicle can navigate on its own. Moreover, the appearance of the floor may change over time due to wear, thus requiring remapping of the surface at periodic intervals.  
       SUMMARY OF THE INVENTION  
       [0010] Systems and methods consistent with the present invention allow a user to easily and efficiently guide a vehicle using a position-coding pattern.  
       [0011] More specifically, systems and methods consistent with the present invention may include a surface for guiding a vehicle in an operating area. The surface may include a position-coding pattern having an arbitrary subset of a predetermined size. The subset may identify a unique position in the operating area. The vehicle may then determine its absolute position within the operating area by recording an image of the arbitrary subset on the surface.  
       [0012] Systems and methods consistent with the present invention may also include a self-guided vehicle for operation on a surface. A control means may control the movement of the vehicle. An image sensor may record an image of the surface having a position-coding pattern. The control means may then convert the recorded position-coding pattern into a position of the vehicle and then control the movement of the vehicle in response to the vehicle position.  
       [0013] The foregoing summarizes only a few aspects of the invention and is not intended to be reflective of the full scope of the invention as claimed. Additional features and advantages of the invention are set forth in the following description, and may be apparent from the description, or may be learned by practicing the invention. Moreover, both the foregoing general description and the following detailed description are exemplary and explanatory and are intended to provide further explanation of the invention as claimed. 
     
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
     [0014] The accompanying drawings provide a further understanding of the invention and, together with the detailed description, explain the principles of the invention. In the drawings:  
     [0015]FIG. 1 is a schematic view of a surface consistent with the present invention used for guiding a vehicle;  
     [0016]FIG. 2 is a diagram of coding symbols used in a position-coding pattern consistent with the present invention;  
     [0017]FIG. 3 illustrates a coding sequence used to code the position-coding pattern according to a preferred embodiment of the present invention;  
     [0018]FIG. 4 is a cross-sectional view of a vehicle consistent with the present invention;  
     [0019]FIG. 5 illustrates in more detail view of the surface of FIG. 1;  
     [0020]FIG. 6 illustrates a method consistent with the present invention for converting the position-coding pattern to a position value; and  
     [0021]FIG. 7 illustrates the conversion of part of the separating coding pattern to a value.  
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS  
     [0022] Systems and methods consistent with the present invention will now be described in detail with reference to the accompanying drawings. FIG. 1 is a schematic view of a storage area  1  having a plurality of shelves  2  and pallets  5  located on a floor  3 . The floor  3  may further include a position-coding pattern (not shown in FIG. 1) used by an automated self-propelled vehicle  4  to navigate the storage premises  1 . For example, the position-coding pattern may be a plastic film overlaid on the floor of the area  1 , thus not requiring a specially constructed floor. Both the shelves  2  and the pallets  5  may include position devices  6  that record the position-coding pattern on the floor  3 .  
     [0023] For example, FIG. 1 shows that the shelves  2  may each be provided with two of the position devices  6  for establishing the area that the shelves occupy on the floor  3 . The position devices  6  may then communicate with a central control device  7  having a memory  8  that may store information about any obstacle occupying a portion of the floor  3 . Accordingly, vehicle  4  can receive from control device  7  updated information about obstacles (e.g., shelves  2  or pallets  5 ) located on floor  3 . Alternatively, the system may not use position devices  6  and, in which case, the vehicle  4  may be manually updated with new positions of shelves  2  or the pallets  5 .  
     [0024] In a preferred embodiment, items may be placed on top of the pallets  5  and moved throughout the storage area  1 . When a pallet is moved to a new position, a position device associated with that pallet may detect that it has been moved to a new position and transmits the new position information to the central control device  7 . In turn, the central control device  7  may transmit the position information to vehicle  4  in the storage area  1 .  
     [0025] The position-coding pattern may comprise a coding pattern that encodes each position within the pattern by a particular symbol, as described in U.S. Pat. No. 5,852,434, the technical disclosure of which is incorporated herein by reference. Alternatively, the position-coding pattern may use multiple symbols to respectively encode multiple positions, as disclosed in WO 00/73983, PCT/SE00/01895, and WO 01/16691, corresponding to Swedish Patent Application Nos. 9901954-9, 9903541-2, and 9903051-2, respectively, the technical disclosures of which are incorporated herein by reference. For example, WO 00/73983 discloses a position coding pattern having a large dot representing a “one” and a small dot representing a “zero”. Thus, differently sized dots may represent different values. Further, the PCT/SE00/1895 and WO 01/16691 applications disclose that the coding pattern may encode four possible values by having four different displacements of a dot in relation to a raster point.  
     [0026]FIGS. 2 a - d  show exemplary symbols consistent with the present invention for coding positions in the position-coding pattern located on floor  3 . As shown in FIG. 2, each symbol may be defined by a mark  10  and a virtual raster point  9 , corresponding to the intersection between two raster lines. The value of each symbol may be based on the location of mark  10  in relation to raster point  9 . For example, FIG. 2 illustrates four possible locations of mark  10 . In each case, the mark  10  is located on a raster line a predetermined distance away from point  9 . In this way, the symbol can define four different values. In particular, the symbol of FIG. 2 a  has the value “0”, the symbol of FIG. 2 b  has the value “1”, the symbol of FIG. 2 c  has the value “2”, and the symbol of FIG. 2 d  has the value “3”. Thus, each symbol can thus represent one of four different values (e.g., “0-3”).  
     [0027] The distance between two adjacent raster points may preferably be about 3 to 12 mm, with the displacement of the mark  10  from the raster point  9  being about ¼ to ⅛, (preferably ⅙) of the total distance between adjacent raster points. In this exemplary embodiment, the effective diameter of the mark  10  is also preferably about 5% to 240% of the total displacement of the mark from the raster point. However, the invention in its broadest sense is not limited to particular dimensions.  
     [0028]FIG. 3 illustrates a sequence  11  consistent with the present invention and which may be used in the position-coding pattern on the floor  6 . The sequence  11  may include a string of digit values  12 , each of which, in this case, is either a “0” or a “1”. Each arbitrary subsequence (e.g., 13 or 14) of five values unambiguously defines a unique value corresponding to the position of that subsequence in the overall sequence  11 . Each subsequence may occur in the sequence only once. Thus, the first subsequence  13  corresponds to the value “0” and the second subsequence  14  to the value “1”.  
     [0029]FIG. 4 is a cross-sectional view of a vehicle  20  consistent with the present invention. The vehicle  20  may include a drive wheel  21  driven by a motor  22 , a steering wheel  23  controlled by a control motor  24 , an image sensor  25  for recording an image of the floor, and a control means  26  coupled to a memory  27 . The image sensor  25 , which may be, for example, a video camera, optical imager, or electromagnetic radiation imager, further may include a lens  46  and a lamp  47  (e.g., emitting infrared or visible wavelength light) for illuminating the portion of the floor to be recorded. The control means  26  may further include a programmable computer having a timer  45 , such as an oscillator, for measuring time.  
     [0030] As shown in FIG. 4, the vehicle  20  may include a transceiver  28  for communicating with the central control device  7 . The control means  26  may calculate a position on the basis of an image of a position-coding pattern recorded by the image sensor  25 . The control means  26  may then control the drive motor  22  and the control motor  24  based on the calculated position of vehicle  20  within the storage area  1 .  
     [0031] In this respect, the memory  27  preferably contains information about where the shelves  2 , pallets  5 , or other obstacles are located within the storage area  1 , as well as information about the walls or boundaries of the storage area  1 . The memory  27  may also store instructions for defining the movement of the vehicle  20  within area  1 , and for storing instructions for when the vehicle  20  encounters a moving obstacle. These instructions are preferably entered into memory  27  using a computer and define the movement pattern of the vehicle  20  with respect to the location of the shelves  5  in the storage area  1 . The vehicle runs along the programmed path by comparing its calculated position with the programmed path in the memory  27 . In this way, the vehicle  20  does not need to communicate with an external computer when moving. However, the central control device  7  may also transmit update information to the vehicle  20  on the position of obstacles.  
     [0032] The timer  45  of the control means  26  may be used to calculate a speed and a direction of the vehicle. For example, the control means  26  may measure two position points based on the last two recorded images. The timer  45  may then measure the time elapsed between the recording of these two images. From these two position values and the time it took the vehicle  20  to travel between these two positions, the control means  26  may calculate the vehicle&#39;s current speed and direction. The speed and direction may then be used when controlling the movement of the vehicle  20 .  
     [0033] Thus, in systems consistent with the present invention, the control means  26  may convert the image of the position-coding pattern into a position. In this case, the vehicle  20  may not communicate the image to an external computer. However, the vehicle  20  may alternatively record the image and transfer it to an external computer that converts the image into a position. In this way, the computational burdens imposed on the vehicle  20  are reduced.  
     [0034] The movement of vehicle  20  may also be programmed or controlled by using a drawing or “blueprint” (in paper or electronic form) of storage area  1  which has a position-coding pattern similar to that on the floor  3  of area  1 . A user may then select the movement of the vehicle by scanning a device (e.g., a pen having an image sensor) over the blueprint to record portions of the pattern and to determine the corresponding coordinate positions. The determined coordinate positions of the blueprint, which correspond to the actual coordinate positions in storage area  1 , are then stored in a blueprint coordinate sequence corresponding to the desired path of the vehicle. This sequence may then be transferred from the scanning device to a computer which controls the movement pattern of vehicle  20 . In this way, a user may easily define the vehicle&#39;s movement pattern by simply tracing a path over a blueprint of the storage area. However, graphics tablets or dedicated computers maybe used to define the vehicle&#39;s movement path.  
     [0035]FIG. 5 illustrates in more detail part of the floor in the storage area of FIG. 1. As shown in FIG. 5, the floor  15  may include a plurality of floor plates  16  each having a position-coding pattern. Each floor plate  16  may preferably code positions in a virtual area common to all floor plates. In other words, each floor plate may contain the same position-coding pattern defining the same positions. When the vehicle  20  is on a floor plate, it can determine its position within that plate by recording an image of the floor and calculating the position that corresponds to the recorded pattern. Further, the memory  27  preferably contains information about the particular plate  16  on which the vehicle is located. This may be done by having a plate coordinate unique for each plate  16 .  
     [0036] Between the plates  16 , there may be separating fields  17 ,  18 , which may consist of plastic strips attached to the floor and containing a position-coding pattern. The position-coding patterns of the separating fields preferably use different symbols than those used in the coding pattern on plates  16 . In this way, the vehicle can detect when it transitions from a plate to a separating field. When the vehicle  20  passes over a separating field, the control means  26  may update the plate coordinate by recording an image of the separating field converting it to the plate coordinate. The position-coding patterns of all of the plates  16  are preferably aligned in the same direction. Consequently, the vehicle  20  can determine between which plates it moves. If the vehicle reverses its direction, the vehicle will detect that it returns to the same floor plate since it will return to the same part of that plate, instead of coming to the opposite part of an adjacent floor plate.  
     [0037] According to an alternative embodiment of the present invention, each floor plate may code unique absolute positions. Thus, an automated self-propelled vehicle can determine its absolute position in the storage area by recording an image of the floor and converting the position-coding pattern to a unique position within area  1 .  
     [0038]FIG. 6 illustrates an exemplary portion of the position-coding pattern placed on the floor  3  of FIG. 1 and on each of the plates  16  of FIG. 5. A first matrix  30  in FIG. 6 a  is a portion of matrix that unambiguously defines a position. In FIG. 6, the position-coding pattern comprises symbols  31  like those shown in FIG. 2. The position-coding pattern may use the four different values to code a binary bit in each of two orthogonal directions. Thus, the four different values “0, 1, 2, 3” code the four different bit combinations (0, 0), (0, 1), (1, 0), (1, 1), where the first digit in each bit combination relates to a first direction and the second digit relates to a second direction orthogonal to the first direction.  
     [0039] When the vehicle records the image of the first matrix  30  of FIG. 6, it is preferably converted into a second matrix  32  with values  33  defining the x coordinates, and into a third matrix  34  with values  35  defining the y coordinates. As described above, the first matrix  30  is converted into the second and third matrices  32  and  34  based on the predefined relationship between the values and the bit combinations. As shown in FIG. 6 b , the second matrix  32  contains a column corresponding to the subsequences  36 . The values in the matrix  32  are either “0” or “1”. Further, the subsequences  36  are a part of the sequence  11  described above in connection with FIG. 3. Each subsequence  36  thus has a unique sequence value. The five subsequences in the columns in the second matrix  32  are then converted to five sequence values Sx 1 , SX 2 , SX 3 , SX 4  and Sx 5 , which define the x coordinate. Similarly, as shown in FIG. 6 c , subsequences  37  with values  35  are arranged in rows in the third matrix  34 . These subsequences are also parts of the sequence in FIG. 3 and are similarly converted to a second set Sy 1 -Sy 5  of sequence values defining the y coordinate.  
     [0040] Subsequently, the difference between adjacent sequence values Sx and Sy is calculated, resulting in two sets of four difference values Dx 1 -Dx 4  and Dy 1 -Dy 4 , respectively. These difference values Dx and Dy may then be used to generate an x and y coordinate. The equations below may be used to calculate the difference values: 
       Dx   n   =Sx   n+1   −Sx   n  modulo R, 
     [0041] and 
       Dy   n   =Sy   n+1   −Sy   n  modulo R, 
     [0042] where R is the number of unique subsequences in the sequence  11  of FIG. 3.  
     [0043] Systems consistent with the present invention may convert the difference values to coordinates in a number of ways. For example, the subsequences may be arranged such that one of the difference values in each matrix has an integer value in the range “0-3”. This codes the most significant digit. The subsequences may also be arranged so that the x coordinate will be one unit greater when moving one column to the right in the matrix. Similarly, the y coordinate will also be one unit greater when moving downward one row down in the matrix. Since, in this case, the columns in the second matrix in FIG. 6 b  consist of parts of the sequence  11  of FIG. 3, each of the sequence values in the two columns Sx 1  and Sx 2  furthest to the left in the matrix in FIG. 6 b  will be one unit greater when moving down one row in the matrix  32 . However, Dx 1  remains constant. Consequently, the x coordinate also remains constant when moving downwards in the second matrix  32 .  
     [0044] In systems consistent with the present invention, the image sensor  25  of vehicle  20  may record an image containing more position symbols than is needed to determine the position. According to one embodiment, the image sensor may record N×N position symbols (N&gt;5), while only 5×5 position symbols may be needed to determine a position. This allows for error correction by using the other recorded position symbols in the position determination. For example, position symbols partly covered by dirt may not be recorded by the image sensor, and thus the other recorded position symbols may be used. In any event, any number of symbols may be used to code a position. The number of position coding symbols used in any specific embodiment will typically depend on how many position points need to be coded in the area.  
     [0045]FIG. 7 illustrates an exemplary portion of the separating field  17  in FIG. 5. The separating field  17  preferably has a plurality of symbols, such as those described above with respect to FIG. 2, arranged in a manner similar to that of the position-coding pattern. FIG. 7 further shows four different floor plates  38  to  41 , each having a different serial number defining its respective position in relation to the other plates on the floor. For example, plate  38  has the serial number “12” in the x-direction and the serial number “14” in the y-direction, plate  39  has the serial number “13” in the x-direction and the serial number “14” in the y-direction, plate  40  has the serial number “12” in the x-direction and the serial number “13” in the y-direction, and plate  41  has the serial number “13” in the x-direction and the serial number “13” in the y-direction.  
     [0046] The symbols within the frame  42  may be converted, in the manner described above, to a difference value for the x-coordinate. The x-coordinate value, which has the value “11” in this example, indicates the serial number of the adjacent floor plate in the x-direction (the plate to the left of the frame  42 ). Similarly, the symbols within the frame  43  correspond to a difference value in the x-direction having the value “12”. Further, the symbols within the frame  44  correspond to a difference value in the y-direction of “13”. Accordingly, by using the information contained in the separating fields, a vehicle can determine on which floor plate it is positioned.  
     [0047] It will be apparent to those skilled in the art that various modifications and variations can be made to the system and method of the present invention without departing from the spirit or scope of the invention. For example, while system has been described with respect to a vehicle operating in a storage area, the system may be used to control any vehicle operating on any type of surface having a position-coding pattern in a variety of applications. For instance, the vehicle may be used on an outside storage surface or even on a roof, and may increase the life of those surfaces by eliminating the need for persons to walk on it. The present invention covers the modifications and variations of this invention provided they come within the scope of the appended claims and their equivalents.  
     [0048] Concurrently filed with the application for this patent are applications entitled Systems and Methods for Information Storage based on Swedish Application No. 0000947-2, filed Mar. 21, 2000, and U.S. Provisional Application No. 60/207,839, filed May 30, 2000; Secured Access Using a Coordinate System based on Swedish Application No. 0000942-3, filed Mar. 21, 2000, and U.S. Provisional Application No. 60/207,850 filed on May 30, 2000; System and Method for Printing by Using a Position Coding Pattern based on Swedish Application No. 0001245-0, filed on Apr. 5, 2000, and U.S. Provisional Application No. 60/210,651, filed on Jun. 9, 2000; Apparatus and Methods Relating to Image Coding based on Swedish Application No. 0000950-6, filed on Mar. 21, 2000, and U.S. Provisional Application No. 60/207,838, filed on May 30, 2000; Apparatus and Methods for Determining Spatial Orientation based on Swedish Application No. 0000951-4, filed on Mar. 21, 2000, and U.S. Provisional Application No. 60/207,844, filed on May 30, 2000; System and Method for Determining Positional Information based on Swedish Application No. 0000949-8, filed Mar. 21, 2000, and U.S. Provisional Application No. 60/207,885, filed on May 30, 2000; Method and System for Transferring and Displaying Graphical Objects based on Swedish Application No. 0000941-5, filed Mar. 21, 2000, and U.S. Provisional Application No. 60/208,165, filed May 31, 2000; Online Graphical Message Service based on Swedish Application No. 0000944-9, filed Mar. 21, 2000, and U.S. Provisional Application No. 60/207,881, filed May 30, 2000; Method and System for Digitizing Freehand Graphics With User-Selected Properties based on Swedish Application No. 0000945-6, filed Mar. 21, 2000, U.S. Provisional Application No. 60/207,882, filed May 30, 2000; Data Form Having a Position-Coding Pattern Detectable by an Optical Sensor based on Swedish Application No. 0001236-9, filed Apr. 5, 2000, and U.S. Provisional Application No. 60/208,167, filed May 31, 2000; Method and Apparatus for Managing Valuable Documents based on Swedish Application No. 0001252-6, filed Apr. 5, 2000, and U.S. Provisional Application No. 60/210,653 filed Jun. 9, 2000; Method and Apparatus for Information Management based on Swedish Application No. 0001253-4 filed Apr. 5, 2000, and U.S. Provisional Application No. 60/210,652, filed Jun. 9, 2000; Device and Method for Communication based on Swedish Application No. 0000940-7, filed Mar. 21, 2000, and U.S. Provisional Application No. 60/208,166, filed May 31, 2000; Information-Related Devices and Methods based on Swedish Application No. 0001235-1, filed Apr. 5, 2000, and U.S. Provisional Application No. 60/210,647, filed Jun. 9, 2000; Processing of Documents based on Swedish Application No. 0000954-8, filed Mar. 21, 2000, and U.S. Provisional Application No. 60/207,849, filed May 30, 2000; Secure Signature Checking System based on Swedish Application No. 0000943-1, filed Mar. 21, 2000, and U.S. Provisional Application No. 60/207,880, filed May 30, 2000; Identification of Virtual Raster Pattern, based on Swedish Application No. 0001235-1, filed Apr. 5, 2000, and U.S. Provisional Application No. 60/210,647, filed Jun. 9, 2000, and Swedish Application No. 0004132-7, filed Nov. 10, 2000, and U.S. Provisional Application No. ______, filed Jan. 12, 2001; and a new U.S. Provisional Application entitled Communications Services Methods and Systems.  
     [0049] The technical disclosures of each of the above-listed U.S. applications, U.S. provisional applications, and Swedish applications are hereby incorporated herein by reference. As used herein, the incorporation of a “technical disclosure” excludes incorporation of information characterizing the related art, or characterizing advantages or objects of this invention over the related art.  
     [0050] In the foregoing Description of Preferred Embodiments, various features of the invention are grouped together in a single embodiment for purposes of streamlining the disclosure. This method of disclosure is not to be interpreted as reflecting an intention that the claimed invention requires more features than are expressly recited in each claim. Rather, as the following claims reflect, inventive aspects lie in less than all features of a single foregoing disclosed embodiment. Thus, the following claims are hereby incorporated into this Description of the Preferred Embodiments, with each claim standing on its own as a separate preferred embodiment of the invention.