Abstract:
An autonomous navigation system for a mobile vehicle arranged to move within an environment includes a plurality of sensors arranged on the vehicle and at least one neural network including an input layer coupled to the sensors, a hidden layer coupled to the input layer, and an output layer coupled to the hidden layer. The neural network produces output signals representing respective positions of the vehicle, such as the X coordinate, the Y coordinate, and the angular orientation of the vehicle. A plurality of patch locations within the environment are used to train the neural networks to produce the correct outputs in response to the distances sensed.

Description:
ORIGIN OF THE INVENTION 
     The invention described herein was made by an employee the United States Government and may be manufactured and used by or for the Government of the United States of America for governmental purposes without the payment of any royalties thereon or therefore. 
    
    
     BACKGROUND OF THE INVENTION 
     The present invention relates to autonomous navigation apparatus for a mobile vehicle, such as a robot, truck, automobile, boat, airplane or space ship, which vehicle is arranged to move in a forward (or rearward) direction within an environment that is delimited, at least in part, by a boundary, such as a wall, curb, ocean buoys or the like. 
     For example, in the case of a robot, which may be designed to deliver mail within an office building, move boxes in a warehouse or perform other tasks, the robot moves in a forward and rearward direction within the boundaries set by walls, fixtures, furniture and the like. 
     In the case of a truck, this vehicle may be required to move either forward or backward on a ramp, delimited on one side by a loading platform, and then to back toward the loading platform and to stop just prior to contact. 
     A truck, or an automobile, is also required to drive on a road which is delimited on the left side by a painted center line or barrier strip and on the right side by a painted line, curb, wall or the like. 
     In the case of a boat, this mobile vehicle is required to stay within water traffic lanes and, upon approach to a harbor, its movement is delimited by the harbor shore line defined by docks, cement abutments and the like. 
     In the case of an airplane, this &#34;vehicle&#34; is required to move about or taxi on the ground within an area delimited by the edges of runways, taxiways and ramps, and is even limited in its movements while in the air. 
     While most applications of the present invention concern three degrees of freedom--that is, movement in a horizontal plane defined by orthogonal coordinates such as Cartesian (X Y) coordinates and yaw (angle of rotation about a third (e.g., Z) orthogonal coordinate)--the invention is also applicable to an airplane or a space ship which operates with six degrees of freedom--that is, three dimensional space coordinates plus three motion coordinates (roll, pitch and yaw). For example, the invention may be applied to a small, cylindrical robot arranged to move in a gravity-free environment within an enclosed space defined by the walls of a large space ship. This robot must be controlled to move from one desired position to another within the three dimensional space and to orient itself at each position. 
     The invention will be described herein with reference to a robot designed to move in two dimensions along hallways within a building and to rotate about its vertical axis; however, it will be readily apparent that the invention is applicable also to other types of mobile vehicles as noted above. 
     Mobile robots used in the delivery of mail, for example, have relied for navigation on devices external to the robot, such as active beacons and/or bar code targets, for determining the instantaneous location of the robot and maintaining calibration. In addition to using these external devices, the wheels of some mobile robots have been equipped with high precision wheel odometers to keep track of movement from one position to another. 
     The disadvantages associated with these navigation systems may be categorized as both qualitative and quantitative. Systems which use external bar code targets require a large number of these targets in the enclosed environment, each of which must be precisely aligned in height, etc. for interrogation by the target readers located on the robot. Position accuracy provided by systems based on active beacons is inadequate for some applications. High precision wheel odometry systems are expensive to design, manufacture and maintain. 
     SUMMARY OF THE INVENTION 
     It is a principal object of the present invention to provide an autonomous navigation system for a mobile vehicle which overcomes the disadvantages of the prior known systems noted above. 
     It is a further object of the present invention to provide an autonomous navigation system for a mobile vehicle that can maintain calibration as the vehicle moves about within an environment that is delimited, at least in part, by a boundary. 
     These objects, as well as other objects which will become apparent from the discussion that follows, are achieved, in accordance with the present invention, by providing apparatus which includes: 
     (a) a plurality of sensors arranged on the vehicle and adapted to determine the distance from the vehicle to the environmental boundary, with each sensor being operative to determine the distance in a unique angular direction, substantially perpendicular to the central vertical axis of the vehicle; 
     (b) a first neural network comprising an input layer coupled to the sensors, a hidden layer coupled to the input layer and an output layer coupled to the hidden layer, for producing a first output representing a first identification of the position of the vehicle; and 
     (c) a second neural network comprising an input layer coupled to the sensors, a hidden layer coupled to the input layer and an output layer coupled to the hidden layer, for producing a second output representing a second identification of the position of the vehicle. 
     Preferably, the first and second position identifications for the vehicle are first and second spacial coordinates, respectively. In a preferred embodiment, these coordinates are orthogonal and, in particular, are Cartesian coordinates of the position of the vehicle. 
     The first and second neural networks may be completely separate and independent, or they may overlap in whole or in part to form a combined neural network producing the first and second outputs. In the latter case, the network elements (nodes) of the first and second networks and at least two layers of these networks are associated with, and serve, both the first and second neural networks. It will be understood that, in this case, the network elements are combined to form a single neural network with plural outputs representing the first and second position identifications of the vehicle. 
     Also, it will be understood that the neural network(s) may have one or more hidden layers. A three layer neural network (i.e., a neural network with one hidden layer) is the minimum configuration for the present invention. 
     As used herein, the term &#34;neural network&#34; is intended to mean an actual or simulated (e.g., by computer program) network comprised of numerous, independent, highly interconnected artificial neurons which simulate the functions of biological neurons. Such neural networks, particularly those known as &#34;backpropagation neural networks&#34; are disclosed, inter alia, in the U.S. Pat. No. 5,253,329. 
     In addition to sensors for determining the distance from the vehicle to a boundary of the environment, the apparatus may be provided with encoders which supply other parameters to the neural networks. For example, the encoders may determine and provide a signal representing the distance traveled by the vehicle. Such a parameter is preferably obtained from a wheel odometer. 
     According to a particular feature of one embodiment of the present invention, the apparatus includes a third neural network comprising an input layer coupled to the sensors, a hidden layer coupled to the input layer and an output layer coupled to the hidden layer, for producing a third output signal representing a third identification of the position of the vehicle. Advantageously, where the first and second position identifications are spacial coordinates, the third position identification is an angular coordinate representing the angular orientation of the vehicle within the spacial coordinate frame. 
     As described previously, the third neural network may be combined with the first and/or the second neural network to form a single neural network with plural outputs representing the first, second and third position identifications of the vehicle. 
     The present invention thus provides a mobile vehicle with a navigation system that can maintain calibration as the vehicle moves within an enclosed environment. The invention utilizes neural network technology to determine both Cartesian coordinate and angular orientation associated with the vehicle&#39;s position for specific regions within the enclosed environment. These specific regions are defined as &#34;patches&#34; which the vehicle learns with respect to position and angular orientation. Data provided by proximity sensors, such as ultrasonic range sensors, is used to determine the vehicle&#39;s position at each patch. Every position within each patch provides a unique, repeatable set of sensor readings the navigation system uses to &#34;learn&#34; the environment. The navigation system maintains calibration by recalibrating the vehicle&#39;s position each time the vehicle enters one of several patches in the environment. 
     The basis of this invention is a fully interconnected neural network with three or more layers. No external devices or high-precision wheel odometry is required. Neural networks are high-speed parallel processing electronic circuits modeled after the way in which neurons are connected in the human brain. These circuits have the ability to map (learn) the functional relationship between input and output data sets if such a functional relationship exists. Processing data in parallel via multiple neural networks, or a single neural network, can often simplify a problem. 
     Low precision wheel odometry may be used to determine the approximate location of the vehicle as it moves between the &#34;patches&#34; or regions where the system is recalibrated. 
     For the proposed application of this invention discussed hereinbelow, three on-board neural networks are used to determine the position and angular orientation of a mobile vehicle operating within an office building environment. One network generates the X coordinate, another network generates the Y coordinate, and a third network generates a Theta value associated with the vehicle&#39;s position within regions defined as &#34;patches&#34; in the building. Once regions within the vehicle&#39;s environment are defined to be recalibration patches, data from multiple ultrasonic range sensors located on the vehicle is taken for several locations within each patch. The data associated with these locations is defined as &#34;training&#34; data. Data provided by the multiple ultrasonic range sensors is provided to the three networks for processing. The neural networks thus map the functional relationship between the actual data collected for training and the desired X, Y and Theta values associated with the sensor readings. After the networks have been &#34;trained&#34; they can provide the Cartesian coordinates and angular orientation for any set of sensor readings taken within a recalibration patch. The robot&#39;s navigation system maintains calibration as it moves from patch to patch. 
     Alternative embodiments of this invention include any variety of applications where one or multiple neural networks can be used to map data from multiple sensors onboard a vehicle to a set of coordinates used by the vehicle for navigation and/or collision avoidance. The only requirement is that the environment be such that a neural network can be trained with the sensor data used to characterize the environment. This implies that there be a functional relationship between the sensor data and the coordinates. Once these conditions are met, the present invention can be implemented. 
     This invention offers advantages over prior vehicle navigation systems. The neural network based position recalibration system is a self-contained system that is on board the vehicle. The system is flexible and can easily adapt to new environments via training. By having the vehicle move through several recalibration patches in the environment, the vehicle&#39;s dependency on high fidelity odometry is greatly reduced, thus reducing the cost of the mobile base development and maintenance. 
     Unlike other mobile vehicle navigation systems, the present invention utilizes neural network technology to determine position and angular orientation in real time. The system does this without any extensive data or mathematical processing. The concept of using recalibration patches enables a system to &#34;learn&#34; the features associated with the enclosed environment of the vehicle. An important characteristic of the neural network is its ability to provide interpolation. Consequently, the network, once trained, can allow for some variation in the input data due to noise and still provide good performance. 
     For a full understanding of the present invention, reference should now be made to the following detailed description of the preferred embodiments of the invention as illustrated in the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a plan view showing the path of a robot within the hallway of a building. 
     FIG. 2 is a representational diagram showing the position of ultrasonic proximity sensors mounted on a robot. 
     FIGS. 3A, 3B and 3C are representational diagrams of three neural networks which receive sensor inputs and produce an output signal representing the X coordinate, Y coordinate and Theta orientation of the robot, respectively. 
     FIG. 4 is a representational diagram of three neural networks, similar to those of FIGS. 3A, 3B and 3C, wherein the outputs of two networks are supplied as inputs to a third network. 
     FIG. 5 is a representational diagram of a combined neural network having three output nodes for producing signals representing the X coordinate, Y coordinate and Theta orientation of a robot, respectively. 
     FIG. 6 is a plan view, similar to FIG. 1, showing the location of a training patch. 
     FIG. 7 is a plan view showing the detailed points within a training patch. 
     FIG. 8 is a plan view illustrating the movement of a robot within a building hallway. 
     FIG. 9 is a plan view, similar to FIG. 8, illustrating the movement of a robot within a building hallway. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     The preferred embodiments of the present invention will now be described with reference to FIGS. 1-9 of the drawings. Identical elements in the various figures are designated with the same reference numerals. 
     The present invention makes it possible to derive repeatable, accurate information relative to the position and orientation of a mobile vehicle using low-cost sensors (i.e., sonar, microwave, wheel odometry encoders and the like) that individually provide a variety of different, but not always accurate data about the environment. In the past, fully automated and autonomous navigation of mobile vehicles required either that the vehicles moved along a defined track or that the vehicles were controlled from wheel odometry data and other positional data which repeatedly corrected for slippage in the wheels that made the encoder data inaccurate. In either case, the power train design from the motor on down through to the wheels had to be very tightly engineered and designed to ensure precise control and measurement. Furthermore, if moderately priced sensors were used to determine position, errors and variances in their performance data would result. 
     In order to obtain meaningful useable information from such distance sensors, it has been necessary to write extensive software routines. This software had to be written specifically to analyze all the varied sensor data and to correct all the inconsistencies. The software had to be repeatedly revised for nuances in each of the operating arenas to insure accuracy. As a consequence, the final system was complicated, unwieldy and expensive. 
     With the present invention, the approximate range (determined by sonar or infra-red signals) and distance travelled (determined by an encoder) are fed into one or more neural networks. These neural networks were previously &#34;trained&#34; to provide useful outputs identifying the position and orientation of the vehicle. 
     Neural networks are high-speed parallel processing electronic circuits modeled after the way in which neurons are connected in the human brain. These circuits have the ability to map (learn) the functional relationships between input and output data sets if such functional relationships exist. A detailed disclosure of neural networks, such as &#34;backpropagation&#34; networks, may be found in the U.S. Pat. No. 5,253,329, which disclosure is incorporated herein by reference. 
     The present invention was actually constructed and tested in connection with a so-called &#34;Courier Robot&#34;, that is, a robot designed to traverse the hallways of a building and deliver mail. FIG. 1 is a diagram showing the optimum path of a Courier Robot within a hallway. The location of the Robot within the hallway is definable at any time by Cartesian (X, Y) coordinates. Any other coordinate system may also be used, however, it is preferable that the coordinates be orthogonal. 
     FIG. 2 shows the arrangement of range detecting sensors around the periphery of the Robot. In the present embodiment--that is, and on the Courier Robot actually constructed and tested--five sensors were used: three forward viewing sensors S1, S2 and S3 and two side viewing sensors S4 and S5. The center forward viewing sensor S2 was aimed directly forward, along the radial of the Robot. The other two forward viewing sensors S1 and S3 were aimed at a five degree angle with respect to the radial, giving a slight (plus or minus 10 degrees) width to the angle of &#34;vision&#34;. 
     The side viewing sensors S4 and S5 was aimed in a direction parallel to the radial which was perpendicular to the forward radial of sensor S2. Consequently, the sensors S4 and S5 were aimed directly toward a side wall of a hallway. 
     To date, one navigation system prototype has been developed for the &#34;Courier Robot&#34;. It was comprised of three independent three-layer backpropagation neural networks. Each network was fully interconnected with five input layer nodes, forty-five hidden layer nodes, and a single output layer node. The system architecture is shown in FIG. 3. The system required no device external to the robot. 
     The three on-board neural networks were used to determine both the Cartesian coordinates (position) and angular orientation of the Courier Robot as a function of range data generated from on-board proximity sensors as it traveled within an office building. A neural network simulator (i.e., a software controlled microprocessor) was used instead of actual circuitry to train and operate the Courier Robot navigation system. Such neural network simulators are available commercially, for example, from NASA, Johnson Space Center, Houston, Tex. One network generated the X coordinate, another network generated the Y coordinate, and the third network generated a Theta value associated with Courier Robot&#39;s position at designated regions in the building defined as &#34;patches&#34;. Each &#34;patch&#34; was a predefined area in the building, usually located in a hallway. 
     In practice, the Courier Robot learned to recognize its own position and angular orientation at one patch in a building. The range data was provided by the five on-board ultrasonic sensors (FIG. 2), collected sequentially for several locations within each patch. 
     The data associated with these locations provided the &#34;training&#34; data for the three neural networks. For each location within the patch, sensor readings were taken as the Courier Robot was rotated in a clockwise and counterclockwise direction. By implication, the Courier Robot can thus be &#34;trained&#34; to determine its position and angular orientation within a patch for each patch in the building. As the Courier Robot travels from patch to patch it can perform wheel odometry recalibration, as necessary, in order to ensure that low-level commands to the on-board motor control circuitry are able to maneuver the Robot into the next patch of the planned path. 
     The Courier Robot&#39;s navigation system was thus constructed and tested using a single recalibration patch in the hallway of an office building as shown in FIG. 6. FIG. 7 depicts the patch in detail and shows the positions within the patch where sensor data was collected. At each location, sensor data was collected as the Courier Robot was rotated plus and minus 10 degrees in 1 degree increments. The input and output range data used to train all three networks independently was determined in millimeters. The X and Y coordinate networks were successfully trained to maximum errors of 14 mm and 24 mm, respectively, using the sensor readings. The trained networks were then tested using sensor data not used during the training process to measure the system performance. The trained networks produced values for X and Y with RMS error values of only 6.47 mm and 13.81 mm, respectively. 
     Due to the inconsistencies in sensor data generated by the particular sensors used on the Courier Robot, the network for determining the Theta value associated with the Courier Robot&#39;s location within the patch could not be trained using only the five sensor readings. Alternative network architectures and input data sets were then investigated to solve the problem. One approach that was tested used a three-layer network with seven input layer nodes. The input data consisted of the five range sensor outputs and both the X and Y coordinates generated by the other two networks. The architecture for this system is shown in FIG. 4. The number of positions within the patch used for the network training was reduced to a certain number of positions along a line. This approach produced Theta values with RMS error of only 0.414 degrees using test positions within the patch. 
     FIGS. 8 and 9 show how the Courier Robot could be trained to learn a path using the present invention. This learning process could be easily automated, where the Robot would be given its coordinates and would automatically step through the learning process. For example, the Robot being trained may have the following input devices: 
     1. Two encoders one on each drive wheel; 
     2. A range detection device (long broken arrows going down the length of the hall); and 
     3. A sonar device shooting out radially towards walls (shorter broken arrows). 
     &#34;Case 1&#34;, shown in FIG. 8, is for the device facing dead straight down the hallway and &#34;Case 2&#34;, shown in FIG. 9, is for the device being trained at the same location but now rotated 10 degrees. 
     It is not important that the Robot recognize every location in the hallway, although this would be optimum and is theoretically possible. The bare minimum would be that it be able to recognize two areas (i.e., each corner at the end of the hallways) in order to get a fix on its location. These areas the Robot has learned to recognize are termed &#34;patches&#34;. As long as the Robot can reach a patch, it can get a fix on its position at that time. Once the Robot knows its exact location, the locations of the two patches and their relationship to each other, it can maneuver in the region between. Basically it has then acquired a built-in recalibration device. 
     The Robot would initially be located at position X=0, Y=0, Theta angle=0. The neural network may then be fed these sensor signals and may be trained to recognize this unique combination of signals as being equal to x=0, y=0, Theta=0. 
     The Robot may then be rotated clockwise 10 degrees and trained to recognize the new unique set of sensor signals as being equal to x=0, y=0, Theta=+10 degrees (Case 2 in FIG. 9). This may be repeated for minus 10 degrees and then for plus and minus 20 degrees, and so forth. 
     The Robot may then be moved in the X direction one foot and trained to recognize the new combination of sensor inputs for that position as being X=10, Y=0, Theta=0 (Case 1 in FIG. 8). 
     This may be repeated again for minus 10 degrees and then for plus and minus 20 degrees, and so on. 
     In this manner, the neural network may correlate every one of the unique combinations of sensor signals (range, sonar, encoder) to an X, Y, location and an orientation Theta. 
     As long as enough of a combination of sensor inputs are provided for each location and the appropriate three layer network is used (with enough neurons in each layer to match the complexity of the problem), the neural network would be able to solve this otherwise extremely difficult problem. 
     The requirements are that (a) enough samples be taken to facilitate training, and (b) enough sensors be provided to give a combination of data for each location; that is, at a minimum: 
     1. Three to eight sonar sensors; and 
     2. One long range microwave range finder (to give data reflective of distance to the end of the hall). 
     In addition, it is preferable to provide the Robot with an encoder for at least one wheel. FIG. 5 depicts a combined neural network having two encoder input nodes, one range input node, and three sonar input nodes for producing signals representing the X coordinate, Y coordinate, and Theta orientation of the robot. 
     Neural networks are ideally suited for recognizing very complex relationships. Their requirements are that there be a functional relationship between the inputs and the outputs, and that they be given enough good training data and time to be able to learn the problem. These conditions are met as proposed. 
     Due to the nature of neural networks, they tend to ignore the inaccuracies in the signal. As long as the neural network(s) can find a unique combination of information that matches that location, they will learn to identify that defined location with that accumulation of data. If the sonar signal has a variation, this can still be used because that variation will still have a unique average value at each location and the other sensors will have a unique set of inputs also. This combination, along with the unique encoder data and the varying range data, is sufficient for a properly designed network to identify the location. 
     Rather than rely on inaccurate data and massaging it in the conventional way, this proposed method actually teaches the neural network how to recognize its position using a learning algorithm. The system relies on a series of inputs and makes use of a robust, noise tolerant, massively parallel, computing process to learn the hallway layout. 
     There has thus been shown and described a novel autonomous navigation apparatus which fulfills all the objects and advantages sought therefor. Many changes, modifications, variations and other uses and applications of the subject invention will, however, become apparent to those skilled in the art after considering this specification and the accompanying drawings which disclose the preferred embodiments thereof. All such changes, modifications, variations and other uses and applications which do not depart from the spirit and scope of the invention are deemed to be covered by the invention, which is to be limited only by the claims which follow.