Navigation and control system for autonomous vehicles

CROSS REFERENCE TO RELATED APPLICATIONS

0001This application is a continuation of Ser. No. 13/240,576 filed Sep. 22, 2011 which is a continuation of U.S. patent application Ser. No. 11/376,160, filed Mar. 16, 2006, the entire contents of each are incorporated herein by reference.

DISCUSSION OF THE BACKGROUND

00021. Field Of The Invention

0003The invention relates to a three-dimensional (3D) imaging sensor and method for controlling an autonomous vehicle.

00042. Background of the Invention

0005In a modern vehicle, the driver remains a critical component of the vehicle's control system as the driver makes numerous decisions directed to the safe operation of the vehicle including speed, steering, obstacle and hazard recognition, and avoidance thereof. Yet, the driver's ability to perform all of these functions can become compromised due to physical factors such as driver fatigue, driver impairment, driver inattention, or other factors such as visibility that reduce the reaction time needed by the driver to successfully avoid hazards.

0006Furthermore, in environmentally dangerous surroundings such as for example in warfare settings or in settings where toxic or nuclear radiation hazards are present, the driver is at risk. Indeed, roadside bombs in Iraq are just one contemporary example of the loss of human life which could in many situations be avoided if supply trucks bringing materials to the troops were unmanned.

0007In other more conventional environments, the driver may become disoriented or incapable of physically commanding the vehicle as would occur if the driver suffered a medical emergency or if for example the driver became disoriented under the driving conditions. One example of such a disorienting or incapacitating environment would be a car or ship being driven or steered under snow, fog, rain, and/or nighttime blackout conditions where the diver (or captain of the ship) is handicapped in his or her ability to perceive and react to hazards approaching or to which the ship is approaching.

0008Thus, whether addressing human deficiencies in the control of a vehicle or whether in environmentally hazardous conditions where human control is not preferred, there exists a need to have a system and method for vehicular identification of objects in the path of the vehicle.

0009Numerous articles on the development of autonomously driven vehicles and laser detection and visualization systems have been reported such as the following reference articles all of which are incorporated herein by reference: <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0010">1) H. Wang, J. Kearney, J. Cremer, and P. Willemsen, “Steering Autonomous Driving Agents Through Intersections in Virtual Urban Environments,” 2004 International Conference on Modeling, Simulation, and Visualization Methods, (2004);</li><li id="ul0002-0002" num="0011">2) R. Frezza, G. Picci, and S. Soatto, “A Lagrangian Formulation of Nonholonomic Path Following,” The Confluence of Vision and Control, (A. S. Morse et al. (eds), Springer Verlag, 1998);</li><li id="ul0002-0003" num="0012">3) J. Shirazi, Java Performance Tuning, (OReilly &amp; Associates, 2000);</li><li id="ul0002-0004" num="0013">4) J. Witt, C. Crane III, and D. Armstrong, “Autonomous Ground Vehicle Path Tracking,” Journal of Robotic Systems, (21(8), 2004);</li><li id="ul0002-0005" num="0014">5) C. Crane III, D. Armstrong Jr., M. Torrie, and S. Gray, “Autonomous Ground Vehicle Technologies Applied to the DARPA Grand Challenge,” International Conference on Control, Automation, and Systems, (2004);</li><li id="ul0002-0006" num="0015">6) T. Berglund, H. Jonsson, and I. Soderkvist, “An Obstacle-Avoiding Minimum Variation B-spline Problem,” International Conference on Geometric Modeling and Graphics, (July, 2003);</li><li id="ul0002-0007" num="0016">7) D. Coombs, B. Yoshimi, T. Tsai, and E. Kent, ‘Visualizing Terrain and Navigation Data,” NISTIR 6720, (Mar. 1, 2001);</li><li id="ul0002-0008" num="0017">8) U.S. Pat. No. 5,644,386 to Jenkins et al;</li><li id="ul0002-0009" num="0018">9) U.S. Pat. No. 5,870,181 to Andressen;</li><li id="ul0002-0010" num="0019">10) U.S. Pat. No. 5,200,606 to Krasutsky et al; and</li><li id="ul0002-0011" num="0020">11) U.S. Pat. No. 6,844,924 to Ruff et al; <br /> Despite this work, realization of suitable visualization, obstacle identification, and obstacle avoidance systems and methods has not been without problems limiting the operation of vehicles. </li></ul></li></ul>

SUMMARY OF THE INVENTION

0021Accordingly, one object of the present invention accomplished in various of the embodiments is to provide a system and method for vehicle object identification in which a location of the object relative to the vehicle is identified.

0022Another object of the present invention accomplished in various of the embodiments is to provide a system and method for vehicle object identification in which a path for the vehicle relative to the location of the object is identified.

0023Yet another object of the present invention accomplished in various of the embodiments is to provide a system and method for identifying objects in a field of view of the vehicle as obstacles.

0024Still another object of the present invention accomplished in various of the embodiments is to provide steering and vehicle control directions to avoid the obstacles

0025Various of these and other objects are provided for in certain ones of the embodiments of the present invention.

0026In one embodiment of the present invention, a navigation and control system includes a sensor configured to locate objects in a predetermined field of view from a vehicle. The sensor has an emitter configured to repeatedly scan a beam into a two-dimensional sector of a plane defined with respect to a first predetermined axis of the vehicle, and a detector configured to detect a reflection of the emitted beam from one of the objects. The sensor includes a panning mechanism configured to pan the plane in which the beam is scanned about a second predetermined axis to produce a three dimensional field of view. The navigation and control system includes a processor configured to determine the existence and location of the objects in the three dimensional field of view based on a position of the vehicle and a time between an emittance of the beam and a reception of the reflection of the emitted beam from one of the objects.

0027In one embodiment of the present invention, a method for navigation and control of a vehicle includes scanning a beam into a sector of a plane defined with respect to a first predetermined axis of the vehicle, detecting a reflection of the emitted beam from an object removed from the vehicle, panning the plane in which the beam is scanned about a second predetermined axis to produce a three dimensional field of view, and determining the existence and location of the object in the three dimensional field of view based on a position of the vehicle and a time between an emittance of the beam and a reception of the reflection of the emitted beam.

0028It is to be understood that both the foregoing general description of the invention and the following detailed description are exemplary, but are not restrictive of the invention.

BRIEF DESCRIPTION OF THE DRAWINGS

0029A more complete appreciation of the present invention and many attendant advantages thereof will be readily obtained as the same becomes better understood by reference to the following detailed description when considered in connection with the accompanying drawings, wherein:

0030<figref idref="DRAWINGS">FIG. 1A</figref> is a schematic illustration of an autonomous vehicle according to one embodiment of the present invention in which a two-dimensional (2D) scan is made in a sector of a plane normal to a predetermined axis of a vehicle;

0031<figref idref="DRAWINGS">FIG. 1B</figref> is a schematic illustration of an autonomous vehicle according to one embodiment of the present invention in which a three-dimensional (3D) scan is made by displacing the scan out the plane normal to the predetermined axis of a vehicle;

0032<figref idref="DRAWINGS">FIG. 2</figref> is a schematic illustration of an emitter and detector system according to one embodiment of the present invention;

0033<figref idref="DRAWINGS">FIG. 3</figref> is a detailed schematic illustration showing a perspective frontal view of a laser radar (LADAR) imaging sensor according to one embodiment of the present invention;

0034<figref idref="DRAWINGS">FIG. 4</figref> is a detailed schematic illustration showing a perspective rear view of the laser radar (LADAR) imaging sensor depicted in <figref idref="DRAWINGS">FIG. 3</figref>;

0035<figref idref="DRAWINGS">FIG. 5</figref> is a contour map of a 3D scan obtained by methods of the present invention;

0036<figref idref="DRAWINGS">FIG. 6A</figref> is a flow chart illustrating particular method steps of the present invention;

0037<figref idref="DRAWINGS">FIG. 6B</figref> is a flow chart illustrating particular method steps of the present invention for obstacle identification and avoidance;

0038<figref idref="DRAWINGS">FIG. 7A</figref> is a schematic illustration of a vehicle according to the present invention utilizing multiple LADAR imaging sensors to scan separate fields of view;

0039<figref idref="DRAWINGS">FIG. 7B</figref> is a schematic illustration of a vehicle according to the present invention utilizing multiple LADAR imaging sensors to scan the same or overlapping fields of view;

0040<figref idref="DRAWINGS">FIG. 8</figref> is a schematic illustration of an exemplary computer system of the present invention;

0041<figref idref="DRAWINGS">FIG. 9</figref> is a high level schematic of a computing network system of the present invention;

0042<figref idref="DRAWINGS">FIG. 10</figref> is a high level schematic of the vehicle control system of the present invention; and

0043<figref idref="DRAWINGS">FIGS. 11-13</figref> are schematics of path determinations made by the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

0044Referring now to the drawings, wherein like reference numerals designate identical, or corresponding parts throughout the several views, and more particularly to <figref idref="DRAWINGS">FIG. 1A</figref>, which depicts an imaging sensor <b>8</b> mounted, in one embodiment, on top of a vehicle <b>10</b> in which a two-dimensional (2D) scan is made in a sector of a plane <b>11</b> normal to a predetermined axis of the vehicle <b>10</b> referred to here for illustration purposes as a “vertical” scanning plane. The imaging sensor <b>8</b> includes in one embodiment an emitter <b>12</b> (as shown in <figref idref="DRAWINGS">FIG. 2</figref>) that transmits laser pulses (or light) <b>14</b> from the imaging sensor <b>8</b> into the environment about the vehicle <b>10</b>. As shown in <figref idref="DRAWINGS">FIG. 1A</figref>, the laser (or light) pulses <b>14</b> are emitted into the vertical scanning plane <b>11</b>. To produce a three-dimensional (3D) image, the imaging sensor <b>8</b> is panned (or oscillated) in and out of plane <b>11</b> to create a 3D scanning volume <b>16</b>, as shown in <figref idref="DRAWINGS">FIG. 1B</figref>. The imaging sensor <b>8</b> detects objects <b>22</b> (as shown in <figref idref="DRAWINGS">FIG. 1B</figref>) in the environment nearby the vehicle <b>10</b> by detecting light reflected from the objects <b>22</b>.

0045As shown in <figref idref="DRAWINGS">FIG. 2</figref>, the imaging sensor <b>8</b> includes a detector <b>18</b> for detecting return of an echoed signal <b>20</b>. The imaging sensor <b>8</b> utilizes a processor <b>24</b> for controlling the timing and emission of the laser pulses <b>14</b> and for correlating emission of the laser pulses <b>14</b> with reception of the echoed signal <b>20</b>. The processor <b>24</b> may be on-board the vehicle or a part of the imaging sensor <b>8</b>. Details of exemplary processors and their functions are provided later.

0046In an exemplary example, laser pulses <b>14</b> from emitter <b>12</b> pass through a beam expander <b>13</b><i>a </i>and a collimator <b>13</b><i>b</i>. The laser pulses <b>14</b> are reflected at a stationary mirror <b>15</b><i>a </i>to a rotating mirror <b>26</b> and then forwarded through lens <b>27</b><i>a </i>and a telescope <b>27</b><i>b </i>to form a beam for the laser pulses <b>14</b> with a diameter of 1-10 mm, providing a corresponding resolution for the synthesized three-dimensional field of view. The telescope <b>27</b><i>b </i>serves to collect light reflected from objects <b>22</b>.

0047In one embodiment of the present invention, the detector <b>18</b> is configured to detect light only of a wavelength of the emitted light in order to discriminate the laser light reflected from the object back to the detector from background light. Accordingly, the imaging sensor <b>8</b> operates, in one embodiment of the present invention, by sending out a laser pulse <b>14</b> that is reflected by an object <b>22</b> and measured by the detector <b>18</b> provided the object is within range of the sensitivity of the detector <b>18</b>. The elapsed time between emission and reception of the laser pulse permits the processor <b>24</b> is used to calculate the distance between the object <b>22</b> and the detector <b>18</b>. In one embodiment of the present invention, the optics (i.e., <b>13</b><i>a</i>, <b>13</b><i>b</i>, <b>15</b><i>a</i>, <b>26</b>, <b>27</b><i>a</i>, and <b>27</b><i>b</i>) are configured to direct the beam instantaneously into the sector shown in <figref idref="DRAWINGS">FIG. 1A</figref>, and the detector <b>18</b> is a field-programmable gate array for reception of the received signals at predetermined angular positions corresponding to a respective angular direction α₁shown in <figref idref="DRAWINGS">FIG. 1A</figref>.

0048Via the rotating mirror <b>26</b>, laser pulses <b>14</b> are swept through a radial sector a within plane <b>11</b>, as shown illustratively in <figref idref="DRAWINGS">FIG. 1A</figref>. In one embodiment of the present invention, in order to accomplish mapping of objects in the field of view in front of the imaging sensor <b>8</b>, the rotating mirror <b>26</b> is rotated across an angular displacement ranging from 30 to 90 degrees, at angular speeds ranging from 100-10000 degrees per second. For example, a 90 degree scanning range can be scanned 75 times per second or an 80 degree scanning range can be scanned between 5 and 100 times per second. Furthermore, the angular resolution can be dynamically adjusted (e.g., providing on command angular resolutions of 0.01, 0.5, 0.75, or 1 degrees for different commercially available sensors <b>8</b>.

0049Commercially available components can be used for the emitter <b>12</b> and the detector <b>18</b> to provide ranging measurements. In one embodiment, the emitter <b>12</b>, the detector <b>18</b>, and the associated optics constitute a laser radar (LADAR) system, but other systems capable of making precise distance measurements can be used in the present invention, such as for example a light detection and ranging (LIDAR) sensor, a radar, or a camera. LIDAR (Light Detection and Ranging; or Laser Imaging Detection and Ranging) is a technology that determines distance to an object or surface using laser pulses. Like the similar radar technology, which uses radio waves instead of light, the range to an object is determined by measuring the time delay between transmission of a pulse and detection of the reflected signal. LADAR (Laser Detection and Ranging) refers to elastic backscatter LIDAR systems. The term laser radar is also in use, but with laser radar laser light (and not radio waves) are used.

0050The primary difference between LIDAR and radar is that with LIDAR, much shorter wavelengths of the electromagnetic spectrum are used, typically in the ultraviolet, visible, or near infrared. In general it is possible to image a feature or object only about the same size as the wavelength, or larger. Thus, LIDAR provides more accurate mapping than radar systems. Moreover, an object needs to produce a dielectric discontinuity in order to reflect the transmitted wave. At radar (microwave or radio) frequencies, a metallic object produces a significant reflection. However non-metallic objects, such as rain and rocks produce weaker reflections, and some materials may produce no detectable reflection at all, meaning some objects or features are effectively invisible at radar frequencies. Lasers provide one solution to these problems. The beam densities and coherency are excellent. Moreover the wavelengths are much smaller than can be achieved with radio systems, and range from about 10 micrometers to the UV (e.g., 250 nm). At these wavelengths, a LIDAR system can offer much higher resolution than radar.

0051To produce a three-dimensional (3D) image, in one embodiment of the present invention, the imaging sensor <b>8</b> is panned (or oscillated) in and out the plane <b>11</b> to create a 3D scanning volume <b>16</b>, as shown in <figref idref="DRAWINGS">FIG. 1B</figref>. For sake of illustration, <figref idref="DRAWINGS">FIG. 1B</figref> defines the scanning volume <b>16</b> by the angle α (in the vertical scanning direction) and the angle β (in the horizontal scanning direction). The angle α, as noted earlier, ranges from 30 to 70 degrees, at angular speeds ranging from 100-1000 degrees per second. The angle β (i.e., the panning angle) ranges from 1 to 270 degrees, at a panning rate ranging from 1-150 degrees per second. Combined the imaging sensor <b>8</b> typically can completely scan the 3D scanning volume <b>16</b> at more than two times a second.

0052In order to accurately determine the distance to objects in the 3D scanning volume <b>16</b>, the direction that the imaging sensor <b>8</b> is pointed at the time of receiving light reflected from the objects <b>22</b> is needed (i.e., the angle of deflection from plane <b>28</b> is needed). Further, in one embodiment of the present invention, geospatial positional data of the instantaneous vehicle position is utilized by processor <b>24</b> to calculate based on the distance of the object from the vehicle and its direction from the vehicle, the geospatial location of the objects in the field of view. In one configuration of the present invention, the processor <b>24</b> includes a personal computer running on a Linux operating system, and the algorithms are programmed in Java programming language. Other computing systems and programming languages can be used in the present invention (as discussed in more detail below). As shown in <figref idref="DRAWINGS">FIG. 2</figref>, processor <b>24</b> is in communication with a real time positioning device <b>25</b>, such as for example a global positioning system (GPS) and/or an inertial navigation system (INS), that transmits the location, heading, altitude, and speed of the vehicle multiple times per second to processor <b>24</b>. The real time positioning device <b>25</b> is typically mounted to the vehicle <b>10</b> and transmits data (such as location, heading, altitude, and speed of the vehicle) to all imaging sensors <b>8</b> (and all processors <b>24</b>) on the vehicle <b>10</b>.

0053With commercially available GPS and the INS units, processor <b>24</b> can determine a position of an object in the field of view to an accuracy of better than 10 cm. In one embodiment of the present invention, the processor <b>24</b> correlates GPS position, LADAR measurements, and angle of deflection data to produce a map of obstacles in a path of the vehicle. The accuracy of the map depends on the accuracy of the data from the positioning device <b>25</b>. The following are illustrative examples of the accuracies of such data: position 10 cm, forward velocity 0.07 km/hr, acceleration 0.01%, roll/pitch 0.03 degrees, heading 0.1 degrees, lateral velocity 0.2%.

0054In one embodiment of the present invention, a Kalman filter (commercially integrated) sorts through all data inputs to processor <b>24</b>. A Kalman filter is a known method of estimating the state of a system based upon recursive measurement of noisy data. In this instance, the Kalman filter is able to much more accurately estimate vehicle position by taking into account the type of noise inherent in each type of sensor and then constructing an optimal estimate of the actual position. Such filtering is described by A. Kelly, in “A 3d State Space Formulation of a Navigation Kalman Filter for Autonomous Vehicles,” CMU Robotics Institute, Tech. Rep., 1994, the entire contents of which are incorporated herein by reference. The Kalman filter is a set of mathematical equations that provides an efficient computational (recursive) means to estimate the state of a process, in a way that minimizes the mean of the squared error. The filter is very powerful in several aspects: it supports estimations of past, present, and even future states, and it can do so even when the precise nature of the modeled system is unknown.

0055The positioning device <b>25</b>, by including GPS and INS data, provide complementary data to the processor <b>24</b>. GPS and INS have reciprocal errors. That is GPS is noisy with finite drift, while INS is not noisy but has infinite drift. Further, the processor <b>24</b> can be configured to accept additional inputs (discussed below) to reduce drift in its estimate of vehicle position when, for example the GPS data may not be available.

0056<figref idref="DRAWINGS">FIG. 3</figref> is a detailed schematic illustration of imaging sensor <b>8</b> of the present invention. <figref idref="DRAWINGS">FIG. 3</figref> presents a frontal view of imaging sensor <b>8</b>. <figref idref="DRAWINGS">FIG. 4</figref> presents a rear perspective view of imaging sensor <b>8</b>. <figref idref="DRAWINGS">FIG. 3</figref> shows a motor <b>30</b> configured to oscillate the imaging sensor <b>8</b> in and out of a plane normal to a predetermined axis of the imaging sensor. In one embodiment of the present invention, a 12-volt DC motor operating at a speed of 120 RPM is used to oscillate the imaging sensor <b>8</b> in and out the plane. Other motors with reciprocating speeds different than 120 RPM can be used.

0057As shown in <figref idref="DRAWINGS">FIG. 3</figref>, an absolute rotary encoder <b>32</b> is placed on a shaft <b>34</b> that is oscillating. The encoder <b>32</b> provides an accurate reading of the angle at which the shaft <b>34</b> is instantaneously located. By the encoder <b>32</b>, an accurate measurement of the direction that the imaging sensor <b>8</b> is pointed, at the time of the scan, is known. In one embodiment of the present invention, the encoder <b>32</b> is an ethernet optical encoder (commercially available from Fraba Posital), placed on shaft <b>34</b> to provide both the angular position and angular velocity of the shaft.

0058To decrease the delay between reading a value from the sensor and reading a value from the encoder, a separate 100 MBit ethernet connection with its own dedicated ethernet card connected the processor <b>24</b> with the encoder. This created communications delays between the encoder and the I/O computer that were consistent at approximately 0.5 ms. Testing revealed that an actual LADAR scan was taken approximately 12.5 ms before the data was available at the I/O computer. When this time was added to the 0.5 ms of delay from the encoder communications, a 13 ms delay from the actual scan to the actual reading of the encoder position and velocity was present. To counteract the angular offset this delay created, in one embodiment of the present invention, the velocity of the encoder is multiplied times the communications delay of 0.013 seconds to calculate the angular offset due to the delay. This angular offset (which was either negative or positive depending on the direction of oscillation) was then added to the encoder's position, giving the actual angle at the time when the scan occurred. This processing permits the orientation of the LADAR platform to be accurate within 0.05 degrees.

0059Further, as shown in <figref idref="DRAWINGS">FIGS. 3 and 4</figref>, the metal shaft <b>34</b> is attached to a detector bracket <b>36</b> which is supported by a metal casing <b>38</b> with bearing <b>40</b>. Bearing <b>40</b> is attached to metal casing <b>38</b> with a fastening mechanism such as bolts <b>42</b> and <b>44</b>. Detector bracket <b>36</b> is attached to metal shaft <b>34</b>. Further, as shown in <figref idref="DRAWINGS">FIGS. 3 and 4</figref>, metal shaft <b>46</b> is attached to bearing <b>48</b>. Bearing <b>48</b> is attached to metal casing <b>38</b> with a fastening mechanism such as bolts <b>50</b> and <b>52</b>. Push rod <b>54</b> is attached to detector bracket <b>36</b> with ball joint <b>56</b> on slot <b>58</b>. Push rod <b>54</b> is attached to pivot spacer <b>60</b> with ball joint <b>62</b>. Pivot spacer <b>60</b> is attached to servo arm <b>64</b> on slot <b>66</b>. Servo arm <b>64</b> is attached to metal shaft <b>68</b>. Motor <b>30</b> is attached to servo arm <b>64</b> and is suspended from metal casing <b>38</b> by motor mounts <b>70</b>, <b>72</b>, and <b>74</b>.

0060The imaging sensor <b>8</b> operates, in one embodiment, by oscillating a measurement sensor laterally about an axis of the vehicle <b>10</b>, as shown in <figref idref="DRAWINGS">FIG. 1A</figref>. In the one embodiment, the shaft <b>68</b> of motor <b>30</b> rotates at a constant speed, causing servo arm <b>64</b> to also spin at a constant speed. One end of push rod <b>54</b> moves with servo arm <b>64</b>, causing detector bracket <b>36</b> to oscillate back and forth. The degree of rotation can be adjusted by moving the mount point of ball joint <b>56</b> along slot <b>58</b>, and/or the mount point of ball joint <b>62</b> along slot <b>66</b>. Moving the mount point closer to shaft <b>46</b> increases the angle of rotation, while moving the mount point away from shaft <b>46</b> decreases the angle of rotation.

0061While sensor <b>18</b> is oscillating, the sensor <b>18</b> is taking measurements of the surrounding environment along the vertical scanning plane, as shown in <figref idref="DRAWINGS">FIG. 1A</figref>. The absolute rotary encoder <b>32</b> operates as an angular position mechanism, and transmits the absolute angle of deflection of detector bracket <b>36</b> to processor <b>24</b>. At the same time, a real time positioning device <b>76</b>, such as a global positioning system (GPS) or an inertial navigation system (INS), transmits the location, heading, altitude, and speed of the vehicle multiple times per second to processor <b>24</b>. Software running on the processor <b>24</b> integrates the data, and, in one embodiment, uses matrix transformations to transform the YZ measurements from each 2D scan (as shown in <figref idref="DRAWINGS">FIG. 1</figref>) into a 3D view of the surrounding environment. Due to the use of the real time positioning device, in the present invention, a terrain map can be calculated even while the vehicle is moving at speeds in excess of 45 miles per hour.

Obstacle Detection Algorithms

0062The imaging sensor <b>8</b> is configured, in one embodiment of the present invention, to receive data in the processor regarding echoed or returned signals, GPS position, LADAR measurements, and angle of deflection data to determine what sectors of the 3D scan contain obstacles, and therefore to determine which sectors are most likely impassable by the vehicle. In one embodiment of the present invention, data coming from detector <b>18</b> is formatted in a coordinate system relative to the detector <b>18</b>, as detailed in the exemplary illustrations below.

0063Since the imaging sensor <b>8</b> is in a “vertical” configuration, the coordinate system in that configuration has Y-axis representing a distance from the sensor roughly parallel with the forward direction of the vehicle, with the X-axis lined up along the vertical direction. Hence, in one embodiment of the present invention, a search for obstacles is manifest in the slope and extent in the X-axis. To facilitate this search, all measurement points in the detector's scan are sorted by the Y-values (i.e., by a distance from the detector <b>18</b>).

0064<figref idref="DRAWINGS">FIG. 5</figref> is a schematic representation of a contour map showing the reflected signatures from an object in a synthesized field of view. <figref idref="DRAWINGS">FIG. 5</figref> depicts two common obstacles that the vehicle <b>10</b> needs to avoid. Obstacle <b>22</b><i>a </i>is a depression in the highway (e.g., a pothole). Obstacle <b>22</b><i>b </i>is an obstruction in the highway (e.g., a fallen boulder). As shown in <figref idref="DRAWINGS">FIG. 5</figref>, lines of constant elevation have been added to the drawing in <figref idref="DRAWINGS">FIG. 5</figref> for clarity. The imaging sensor <b>8</b> of the present invention, as shown in <figref idref="DRAWINGS">FIG. 1A</figref>, produces a vertical scan, which in <figref idref="DRAWINGS">FIG. 5</figref> is shown depicted on an X-Y axis. A vertical scan provides the advantage of directly supplying slope data (i.e., ΔX/ΔY data) along the road and obstacles shown in <figref idref="DRAWINGS">FIG. 5</figref> without having to complete a full 3D scan, as shown in <figref idref="DRAWINGS">FIG. 1B</figref>, and then process the image map for slope data. Furthermore, in data from a vertical scan plane as in <figref idref="DRAWINGS">FIG. 1A</figref>, obstacles appear as either clusters of similar distance or gaps in distance, making obstacle identification more discernable in the data.

0065According to one embodiment of the present invention, any point P is classified as part of an obstacle if and only if there could be found a point Q such that Equations (1), (2), and (3) are satisfied (where h_maxis the maximum height or depth, m_maxis the maximum slope, is the unit vector in the X direction, and j is the unit vector in the Y direction).

0000<br /><i>Q·ĵ>P·ĵ</i>  (1)

0000<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mo></mo><mfrac><mrow><mrow><mi>Q</mi><mo>·</mo><mover><mi>i</mi><mo>^</mo></mover></mrow><mo>-</mo><mrow><mi>P</mi><mo>·</mo><mover><mi>i</mi><mo>^</mo></mover></mrow></mrow><mrow><mrow><mi>Q</mi><mo>·</mo><mover><mi>j</mi><mo>^</mo></mover></mrow><mo>-</mo><mrow><mi>P</mi><mo>·</mo><mover><mi>j</mi><mo>^</mo></mover></mrow></mrow></mfrac><mo></mo></mrow><mo>></mo><msub><mi>m</mi><mrow><mi>ma</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>x</mi></mrow></msub></mrow></mtd><mtd><mrow><mo>(</mo><mn>2</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><img file="US2013131908A1_D0001.tif" /><br />|<i>Q·î−P·î|>h</i>_max  (3)

0066Equation (1) represents a condition in which there exists a first point Q in the field of view that is farther away from the vehicle than a second point P. Equation (2) represents a condition in which a slope between the first point and the second point is greater than a predetermined slope. Equation (3) represents a condition in which a height between the first point and the second point is greater than a predetermined height.

0067Once an obstacle is found relative to the sensor, its location must be translated into the global reference frame (i.e., a geospatial reference frame). This can be accomplished in two similar steps. In each step, a transformation matrix is defined so that

0000<br /><i>P</i>₂<i>=T</i>_1→2<i>P</i>₁+Δ₁  (4)

0000where T_1→2is the transformation matrix for going from coordinate frame <b>1</b> to coordinate frame <b>2</b>, Δ₁is the vector representing the position of the coordinate frame <b>1</b> with respect to coordinate frame <b>2</b>, and P₁and P₂are the same point in coordinate frames <b>1</b> and <b>2</b>, respectively.

0068The first step converts from the detector coordinate frame to the vehicle's coordinate frame. The transformation matrix, T_s→v, is defined as

0000<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>T</mi><mrow><mi>s</mi><mo>-></mo><mi>v</mi></mrow></msub><mo>=</mo><mrow><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mrow><mi>cos</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>ψ</mi><mi>s</mi></msub></mrow></mtd><mtd><mrow><mrow><mo>-</mo><mi>sin</mi></mrow><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>ψ</mi><mi>s</mi></msub></mrow></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mrow><mi>sin</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>ψ</mi><mi>s</mi></msub></mrow></mtd><mtd><mrow><mi>cos</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>ψ</mi><mi>s</mi></msub></mrow></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable><mo>]</mo></mrow><mo></mo><mrow><mo>[</mo><mtable><mtr><mtd><mrow><mi>cos</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>θ</mi><mi>s</mi></msub></mrow></mtd><mtd><mn>0</mn></mtd><mtd><mrow><mi>sin</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>θ</mi><mi>s</mi></msub></mrow></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mrow><mrow><mo>-</mo><mi>sin</mi></mrow><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>θ</mi><mi>s</mi></msub></mrow></mtd><mtd><mn>0</mn></mtd><mtd><mrow><mi>cos</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>θ</mi><mi>s</mi></msub></mrow></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>[</mo><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mrow><mi>cos</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>φ</mi><mi>s</mi></msub></mrow></mtd><mtd><mrow><mrow><mo>-</mo><mi>sin</mi></mrow><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>φ</mi><mi>s</mi></msub></mrow></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mrow><mi>sin</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>φ</mi><mi>s</mi></msub></mrow></mtd><mtd><mrow><mi>cos</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>φ</mi><mi>s</mi></msub></mrow></mtd></mtr></mtable><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>]</mo></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>5</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><img file="US2013131908A1_D0002.tif" />

0000where Ψ_s, θ_sand φ_sare the yaw (around the z-axis), pitch (around the y-axis), and roll (around the x-axis) of the detector coordinate frame relative to the vehicle's coordinate frame. This transformation takes into account deviations in yaw, pitch, or roll caused by the mounting of the sensor. For example, if the detector were mounted pointed slightly downward, it would have a negative pitch that would need to be countered by setting θ_sto its inverse (or positive) value. In addition, the angle of deflection caused by the oscillation is processed here by adding it to θ_s.

0069In one embodiment of the present invention, the same basic transformation and translation is performed again in order to translate the obstacle's location from the vehicle's coordinate system to a global system. Yet another transformation matrix, T_v→g, is constructed for this purpose.

0000<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>T</mi><mrow><mi>v</mi><mo>-></mo><mi>g</mi></mrow></msub><mo>=</mo><mrow><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mrow><mi>cos</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>ψ</mi><mi>v</mi></msub></mrow></mtd><mtd><mrow><mrow><mo>-</mo><mi>sin</mi></mrow><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>ψ</mi><mi>v</mi></msub></mrow></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mrow><mi>sin</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>ψ</mi><mi>v</mi></msub></mrow></mtd><mtd><mrow><mi>cos</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>ψ</mi><mi>v</mi></msub></mrow></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable><mo>]</mo></mrow><mo></mo><mrow><mo>[</mo><mtable><mtr><mtd><mrow><mi>cos</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>θ</mi><mi>v</mi></msub></mrow></mtd><mtd><mn>0</mn></mtd><mtd><mrow><mi>sin</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>θ</mi><mi>v</mi></msub></mrow></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mrow><mrow><mo>-</mo><mi>sin</mi></mrow><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>θ</mi><mi>v</mi></msub></mrow></mtd><mtd><mn>0</mn></mtd><mtd><mrow><mi>cos</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>θ</mi><mi>v</mi></msub></mrow></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo></mo><mrow><mo>[</mo><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mrow><mi>cos</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>φ</mi><mi>v</mi></msub></mrow></mtd><mtd><mrow><mrow><mo>-</mo><mi>sin</mi></mrow><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>φ</mi><mi>v</mi></msub></mrow></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mrow><mi>sin</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>φ</mi><mi>v</mi></msub></mrow></mtd><mtd><mrow><mi>cos</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><msub><mi>φ</mi><mi>v</mi></msub></mrow></mtd></mtr></mtable><mo>]</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>6</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><img file="US2013131908A1_D0003.tif" />

0000where Ψ_v, θ_Vand φ_vare the heading (around the z-axis), pitch (around the y-axis), and roll (around the x-axis) of the vehicle relative to the global coordinate frame. These heading, pitch, and roll values are generated by the GPS/INS navigation sensor that is mounted on the vehicle.

0070After taking into account both of these transformation matrices, the full equation for transformation from detector frame to the global coordinate frame is:

0000<br /><i>P</i>_g<i>=T</i>_v→g(<i>T</i>_s→v<i>P</i>_s+Δ_s)+Δ_v.  (7)

0000where Δ_sis the vector representing the position of the sensor with respect to the center of the vehicle and Δ_vis the vector representing the position of the center of the vehicle with respect to the center of the GPS/INS navigation sensor.

0071At this point, in one embodiment of the present invention, the geospatial locations of all obstacles in the LADAR sensor's current scan are known. Each of these obstacles is now checked to determine if it can be safely ignored. If an obstacle is far enough away, it can safely be ignored for the time being. <figref idref="DRAWINGS">FIG. 5</figref> shows for the purposes of illustration a point R beyond the obstacles <b>22</b><i>a </i>and <b>22</b><i>b</i>. In some situations, data regarding the positioning of objects (or other obstacles) beyond this distance can be discarded for example until the vehicle has safely navigated the obstacles <b>22</b><i>a </i>and <b>22</b><i>b</i>. The distance to the point R will also depend on the speed of the vehicle and the accuracy of the detector <b>18</b> to see objects beyond a sensitivity of the detector <b>18</b>. Discarding object data serves two purposes. One, the further away an object is from the LADAR unit, the higher the chance that it is a false signature. False signatures could cause the autonomous vehicle to be unable to find a path, so they must be avoided at all costs. Two, by reducing the number of obstacles that must be processed at any given time, less computing resources are needed. The remaining obstacles are now processed to determine if the vehicle's current path will collide with any of these obstacles. If any of these obstacles will cause a collision, the path is shifted to avoid the obstacles (as will be discussed later).

0072Associated with the distance criteria, the processor <b>24</b> in one embodiment of the present invention discards objects in the field of view of the detector <b>18</b> that are beyond a travel-point distance. The travel-point distance (also exemplified by point R on <figref idref="DRAWINGS">FIG. 5</figref>) is in one embodiment the calculated distance that is an arbitrary factor (e.g., factors of 5, 10, 100) multiplied times the distance that the vehicle will travel at the current speed before the next complete 3D scan of angular sector <b>16</b> is made. The travel-point distance is in one embodiment set to an arbitrary distance (e.g., 100 m). The travel-point distance in different embodiments of the present invention can be calculated based on linear, sigmoid, or exponential functions that are evaluated using values such as vehicle speed and time and path. By discarding objects in the field of view beyond the travel-point distance, the processor will not be required to process data associated with objects so far removed from the vehicle that determination of whether or not the objects are obstacles to the path of the vehicle will make no difference in the steering of the vehicle.

0073Accordingly, in one embodiment of the present invention, every vertical scan produces from the slope and height data a set of obstacles that meet the vector criteria defined in eqns. (1)-(3). Since the vertical scan represents a very small slice of the 3D viewing field, the location of the obstacle can be represented by a polygon represented in this illustrative example by a series of spatial coordinate points including a center point and four corner points: 0.2 m from the back of center, 0.2 m from front of center, 0.2 m from left of center, and 0.2 m from right of center. In one embodiment of the present invention, spatial indices such as a quadtree stores the polygon and efficiently subdivides space, so that object retrieval (such as identifying if an obstacle exists within a space) is faster than having to search a plot map containing obstacles on a point-by-point analysis. Fitch et al., U.S. Pat. No. 6,212,392, the entire contents of which are incorporated herein by reference, describe the use of quadrees to determine whether or not a location associated with a wireless station is within an area of interest. Bao et al., “LOD-based Clustering Techniques for Efficient Large-scale Terrain Storage and Visualization,” in Proceedings SPIE Conference on Visualization and Data Analysis, pages 225-235 (2003), the entire contents of which are incorporated herein by reference, describe memory algorithms suitable for the present invention in which clustering algorithms and data structures including hierarchical quadree triangulation are explained in detail.

0074In one embodiment of the present invention, a navigation and control system includes a sensor (e.g., imaging sensor <b>8</b>) configured to locate objects in a field of view from a vehicle (e.g., vehicle <b>10</b>) and a processor (e.g., processor <b>24</b>) configured to determine the existence and location of the objects in the field of view based on a position of the vehicle and a time between an emittance of a beam from the sensor and a reception of a reflection of the emitted beam from one of the objects. In this embodiment, the processor includes a memory including storage elements corresponding to subsectors in the field of view. The processor is configured 1) to perform an obstacle identification algorithm to determine if any object is an obstacle, 2) to determine in which of the field of view subsectors a determined obstacle exists, and 3) to store in each corresponding memory element an obstacle indicator indicative that an obstacle exists in the corresponding subsector. In one embodiment of the present invention, processor <b>24</b> is configured to determine if a projected path of the vehicle intersects any subsector storing an indicator. In one embodiment of the present invention, processor <b>24</b> is configured to execute an obstacle identification algorithm including: determining first and second points on a contour map of an object, determining if the first point is farther away from the vehicle than the second point, determining a slope between the first point and the second point, determining if the slope is greater than a predetermined slope, and determining if a height between the first point and the second point is greater than a predetermined height, and if so, determining the object is an obstacle.

0075A path planning algorithm (to be discussed in more detail later) according to one embodiment of the present invention presents a “query” polygon for a sector in front of the vehicle and determines from the spatial index (e.g., a quadtree) if any of the stored obstacle polygons intersect the “query” polygon. If so, a path around the query polygon is chosen. If not, the path is clear of obstacles. The way that a quadtree (or most spatial indices) eliminates sectors of space is by keeping track of where it has inserted obstacles. For the quadtree techniques used in one embodiment of the present invention, the quadtree subdivides space as obstacles are inserted, thereby creating an indicator that this sector of space contains an obstacle. This leaves many sectors that are empty of obstacles, and the quadtree knows that these sectors are empty. Therefore, if the query is within one of these sectors, it cannot have an obstacle collision.

0076One conventional way to determine the number of obstacles in the path of the vehicle is to mount stationary LADAR units pointed at the ground. With these LADAR units being pointed at the ground, the angle at which the LADAR beam hits the ground is calculated. Based on this angle, simple trigonometry can determine where the object is located relative to the car. In most conventional cases, multiple stationary LADAR units are used and each is placed at a different known angle.

0077There are several disadvantages to the conventional approach:

00781) The conventional approach requires movement from the autonomous vehicle in order to map the environment. This means that while the vehicle is stationary, virtually no mapping is happening. The only data being mapped is from the same scans over and over again. Another problem with relying on vehicle movement to map data is that the integrity of the scans is dependent on the vehicle's speed. As the vehicle goes faster, the distance between scans increases. This could lead to obstacles being missed.

00792) Moving obstacles cannot be detected reliably. This is due to the fact that the LADAR scans are fixed. If an obstacle were to be in between two LADAR scans and moving at a similar speed and direction as the vehicle (e.g. another vehicle), the obstacle could be missed in the conventional approach.

00803) In general, the conventional approach uses more computing resources than the present invention. For example, in the conventional approach, since the LADAR units are scanning horizontally, scan data must be placed into a large terrain elevation map. To detect obstacles, this terrain elevation map must be searched. This is a computationally expensive process.

0081In one embodiment of the present invention, the imaging sensor <b>8</b> constantly oscillates to produce the three-dimensional scan. Accordingly, there is no need for vehicle motion to map data. Nor is there any need in the present invention to store massive amounts of map or sensor data in order to detect obstacles. Furthermore, the present invention in one embodiment only stores data of the geospatial locations of all the currently-identified obstacles, such as for example an obstacle that is within a certain distance of the vehicle and that has been seen within a certain amount of time. For example, in the present invention, an obstacle is considered pertinent if it was within 50 meters of the vehicle and if it had been seen within the last 5 seconds. Other definitions of pertinent obstacles based on their distance and historical observance in the field of view are possible.

0082Other advantages of the present invention include the detection of moving obstacles and the elimination of blind spot hidden obstacles. Since the imaging sensor <b>8</b> in one embodiment of the present invention rescans the same area multiple times per second, the chances of missing an obstacle are reduced as compared to a single scan over one area. As long as the area of oscillation covers a given area, any obstacle within that area should be seen.

0083In one embodiment of the present invention, processor <b>24</b> is configured to perform the illustrative steps shown in <figref idref="DRAWINGS">FIG. 6A</figref>. At step <b>602</b>, a sensing beam is repeatedly scanned into a two-dimensional sector of a plane defined with respect to a first predetermined axis of the vehicle. At step <b>604</b>, a reflection of the emitted beam from objects removed from the vehicle is detected. At step <b>606</b>, the plane in which the beam is scanned is panned about a second predetermined axis to produce a three dimensional field of view. At step <b>608</b>, the existence and location of the objects in the three dimensional field of view based on a position of the vehicle and a time between an emittance of the beam and a reception of the reflection of the emitted beam is determined.

0084The method of the present invention in one embodiment emits the beam into substantially a vertical sector. Accordingly, slope data related to the terrain and depressions or obstacle protruding from the terrain are accessible from the scan in the vertical sector without having to process the full three dimensional field of view. In one embodiment of the present invention, the processor operating with a vertically oriented sensor <b>8</b> does not need to process the full three dimensional field of view. The vertical scan lines (e.g., scans in α) originate from the vehicle and have slope data encoded in data due to the vertical orientation. Each independent scan line provides data of relevant obstacles.

0085The method of the present invention in one embodiment obtains a heading of the vehicle and a geospatial position of the vehicle, and processes data including the distance to the object, the direction to the object, the heading of the vehicle, and the geospatial position of the vehicle to determine whether the path for the vehicle intersects the object for example based on a predicted position of the vehicle. As discussed below, path planning and speed algorithms are used to direct the vehicle around the obstacles. The method of the present invention in one embodiment forms a three-dimensional field of view for the vehicle by scanning the beam in an angular sector of the plane while displacing the beam out of the plane, as shown in <figref idref="DRAWINGS">FIG. 1B</figref>.

0086The method of the present invention in one embodiment determines an angular coordinate of the beam relative to the second predetermined axis for the direction to the object and offsets the angular coordinate by an amount indicative of a time delay in receiving a signal indicative of the angular coordinate at a processor (used to calculate the location of the object). This permits a more accurate determination of the location of the object.

0087The method of the present invention in one embodiment directs the beam into respective angular sectors. The processor can determine the predetermined angular sectors based on a number of factors including but not limited to vehicle speed, an identified obstacle location, and a projected path of the vehicle. In the present invention, the sectors and/or the panning rate of each sector can be adjusted based upon some of the following non-limiting factors:

00881) if an area of interest does not have adequate scan data (i.e. it has not been scanned enough times to be confident in that area), the sectors can be adjusted to give that area of interest more coverage especially if the area of interest includes a projected path of an obstacle (i.e. projected path of a moving obstacle) or if the area of interest includes an obstacle with complexity (i.e., if a composite obstacle seems to have many facets and/or other features warranting more scans), or if the area of interest includes an obstacle density (i.e., if one area has more obstacles than another, the sectors and/or speed to cover that area are appropriately adjusted);

00892) if other sensor input such as a stereoscopic camera or radar sees an anomaly in an area or if an infrared camera picks up a high heat signature, for example of a human being, animal, or engine block, the sectors can be adjusted to provide better coverage in that area;

00903) if a priori information is known, such as for example from a topographical map indicating that a cliff should be on the left side of the road, then the sectors could be adjusted to scan where the cliff should be to ensure safety;

00914) if the vehicle was being operated in a convoy mode (either following a lead vehicle or possibly a walking human), the sectors could be adjusted to keep the lead vehicle or human in view;

00925) if the vehicle was being operated as part of weapons targeting, the sectors could be adjusted to provide higher resolution coverage of the target area;

00936) if information from other vehicles informs the autonomous vehicle about an area of interest, then the sectors could be adjusted to concentrate on the area of interest;

00947) if a driver through an input device such a keyboard or mouse indicates an area is of interest, the sectors could be adjusted to concentrate on the area of interest;

00958) if the autonomous vehicle receives a friend or foe signal, the sectors could be adjusted based upon whether the other vehicle is broadcasting a friend signal or a foe signal; and

00969) if the autonomous vehicle expects a landmark to appear in a certain area, the sectors could be adjusted to look for the landmark in that area (landmark recognition is one way to enhance navigational accuracy).

0097Accordingly, the method of the present invention in one embodiment determines the angular sectors (and/or the panning rate to scan with) based on at least one of a vehicle speed, an identified obstacle location, a projected path of the vehicle, a resolution required to resolve a complex obstacle or a collection of obstacles to be resolved, other sensory input, an identified priority sector in which an obstacle has been identified (e.g., a region in which high threat obstacles exist), and auxiliary information indicating the presence of an obstacle, a moving obstacle, another vehicle, a landmark, or an area (or region) of interest. When the imaging sensor <b>8</b> is configured in a vertical orientation, as shown in <figref idref="DRAWINGS">FIG. 1A</figref>, it may not even be necessary to pan the beam as shown in <figref idref="DRAWINGS">FIG. 1B</figref>, in which case the panning rate could be set to zero with the obstacles being identified on the basis of a single scan in which the angle α is varied, as discussed above.

0098The method of the present invention in one embodiment stores in memory indicators of whether an obstacle exists in a subsector of the three dimensional field of view. The method of the present invention in one embodiment further determines if a projected path of the vehicle intersects one of the subsectors containing the indicators.

0099One method of the present invention for obstacle identification and avoidance is illustrated by the flowchart in <figref idref="DRAWINGS">FIG. 6B</figref>. At <b>620</b>, the location of the object is determined in geospatial coordinates. In this step, the method determines angular coordinates (for the direction to the object) of the beam relative to the predetermined axis, obtains positioning data from a global positioning system device disposed on the vehicle, and/or obtains orientation data for the predetermined axis of the vehicle in a geospatial coordinate system. In this step, the method processes at least one of the angular coordinates, the positioning data, and the orientation data to determine the location of the object in geospatial coordinates. In one embodiment of the present invention, the data processed is limited to data for objects within a predetermined distance of the vehicle.

0100At <b>622</b>, the altitude of the vehicle is ascertained, and from that information the present invention determines an elevation of the object by correlating the location of the object relative to the vehicle with the geospatial position of the vehicle and the altitude of the vehicle, determines elevations for plural points on the object, and/or generates a contour map for the object.

0101At <b>624</b>, the present invention determines if the object is an obstacle. For instance, as detailed by the vector equations (1)-(3) listed above, one embodiment of the present invention determines if the object is an obstacle by assessing if there exists a first point on a contour map (or in the field of view) that is farther away from the vehicle than a second point P on the contour map, if a slope between the first point and the second point is greater than a predetermined slope, and if a height between the first point and the second point is greater than a predetermined height.

0102At <b>626</b>, if the object is an obstacle, the present invention determines if the obstacle is to be avoided, for example by determining if a geospatial position of the obstacle remains in the path of the vehicle over a time lapse period and/or by determining if a geospatial position of the obstacle is within a set distance from the vehicle. In one embodiment of the present invention, the obstacle (now identified) is mapped relative to the path of the vehicle.

0103At <b>628</b>, if the object is an obstacle, steering and speed control directions are provided to the vehicle in order to avoid the obstacle. The steering and speed control directions can take into consideration the destination of the vehicle, and thereby provide steering and speed control directions to the vehicle in order to avoid the obstacle and to return on course to the destination.

0104Or, at <b>630</b>, if no obstacles are present, then the steering and speed control directions provide steering and speed control directions to the vehicle to guide the vehicle to the destination.

0105<figref idref="DRAWINGS">FIG. 7A</figref> is a schematic illustration of a vehicle according to the present invention depicting one embodiment in which multiple LADAR imaging sensors are used. In this embodiment, one or more of the imaging sensors is dedicated to scanning for the detection of objects nearby the vehicle (e.g., within 50 m) while another of the imaging sensors is dedicated to scanning for the detection of objects farther away from the vehicle (e.g., beyond 50 m).

0106In another embodiment of the invention, multiple imaging sensors are used for redundancy and to provide different perspectives of the same object. <figref idref="DRAWINGS">FIG. 7B</figref> is a schematic illustration of a vehicle according to the present invention depicting one embodiment in which multiple LADAR imaging sensors are used to scan the same or overlapping fields of view. This configuration provides redundant coverage in the center of the path so that, if one imaging sensor <b>8</b> fails, the other one can still sense obstacles most likely to be directly in the vehicle's path. The data from the imaging sensors <b>8</b> are correlated by placing all data onto the same elevation grid (as illustrated for example in <figref idref="DRAWINGS">FIG. 5</figref>).

0107In another embodiment, the imaging sensors <b>8</b> are configured to locate objects removed from a vehicle <b>10</b>; and processor <b>24</b> is configured to direct one of the sensors to scan a first sector associated with a path of the vehicle, while directing another of the sensors to scan a second sector identified with an obstacle. As such, the first and/or second sector determinations can be based on a number of factors including, but not limited to a vehicle speed, an identified obstacle location, a projected path of the vehicle, a resolution required to resolve a complex obstacle or a collection of obstacles to be resolved, sensory input other than from the sensors, an identified priority sector in which an obstacle has been identified, and auxiliary information indicating the presence of an obstacle, a moving obstacle, another vehicle, a landmark, or an area of interest.

0108In one variant of this embodiment, the processor <b>24</b> can direct one sensor to scan a first sector associated with a path of the vehicle, and in a programmed manner direct the same sensor (e.g., in a dynamic fashion) to scan a second sector identified with an obstacle. Factors which determine the programmed duty cycle by which one sensor scans the first sector and then a second sector include for example the speed of the vehicle, the proximity of the obstacle, any movement of the obstacle, an identified status of the obstacle (e.g., friend or foe), the proximity of the obstacle to the projected path of the vehicle, and the calculated clearance from the vehicle to the obstacle.

0109Moreover, in one embodiment of the present invention, one of the imaging sensors <b>8</b> is dedicated to scanning in a horizontal direction while another imaging sensor is directed to scan in the vertical direction. Scan information from this unit permits the processor <b>24</b> to better identify the general terrain and terrain curvature from which obstacles such as shown in <figref idref="DRAWINGS">FIG. 5</figref> can be identified. Complementary data from both horizontal and vertical scans helps identity the edges of composite obstacles (groups of individual obstacles that should be treated as one obstacle) more accurately. One of the issues with handling moving obstacles is determining the full proportions of an obstacle. To calculate the full proportions of an obstacle, multiple “independent” obstacles are intelligently grouped to form one larger composite obstacle when for example the data points representing the independent obstacles are within a set distance of each other (e.g., within 100 cm). Moreover, in other embodiments of the present invention, the grouping into composite obstacles is set by more than just a distance of separation between points normally qualifying as an obstacle point. Other factors that can be used in the determination include for example the number of times each point identified as an obstacle is seen, whether the obstacle point moves spatially in time, and whether (as discussed elsewhere) if there is confirmation of the obstacle by other image sensors or stereographic cameras.

0110Having two completely different perspectives of the obstacles facilitates this task by the obstacles being viewed from two separate dimensions (i.e., from top to bottom and from left to right). Since the beams tend to wrap around the curvature of an obstacle, this provides accurate estimations of the size and orientation of a composite obstacle. For instance, consider a spherical boulder. While the backside of the spherical boulder can not be seen, the sensing beam maps out a contour of the spherical boulder providing the aforementioned size and orientation, providing an estimate of the full size of the spherical boulder.

0111Furthermore, having stepper motors (or in general any motor that can have its position dynamically adjusted) oscillate the platform rather than a continuously revolving motor creates several distinct advantages: 1) the rate at which the platform oscillates can be changed dynamically, and 2) the size of the sector which is scanned can be dynamically changed.

0112By having these dynamic capabilities, the present invention achieves several advantages:

01131) Path (or road) curvature can be tracked in the present invention. As the path in front of the vehicle curves, the imaging sensors <b>8</b> can change their sector to better match the path, thereby ensuring that the path always gets the best coverage. This also helps to ensure that hard 90 degree or more turns do not create blind spots on the path. An imaging sensor that cannot alter its sector would be fixated ahead of the vehicle, even though the path is turning towards the right or left, and therefore blindspots in the viewing field would develop that would not resolved until after the vehicle had started turning. Accordingly, in one embodiment of the present invention, the sensors <b>8</b> can preemptively adjust their orientation. For example, the imaging sensor <b>8</b> shown in <figref idref="DRAWINGS">FIG. 1B</figref> or the multiple imaging sensors <b>8</b> shown in <figref idref="DRAWINGS">FIGS. 7A and 7B</figref> can be directed into a three-dimensional field of view that follows the anticipated path of the vehicle <b>10</b> on for example a highway. Further, the angular sectors mapped by the multiple imaging sensors <b>8</b> can be dynamically adjusted using stepper motors to vary (in real time) the angular sector β scanned and the angular scan rate. Factors which influence selection of the angular sector to be scanned include vehicle speed, an identified obstacle location relative to a turn in a path of the vehicle, a projected path of the vehicle, a resolution required to resolve a complex obstacle or a collection of obstacles to be resolved, sensory input other than from the sensors, an identified priority sector in which an obstacle has been identified, and auxiliary information indicating the presence of an obstacle, a moving obstacle, another vehicle, a landmark, or an area of interest.

01142) The speed of oscillation of the platform can be adjusted based on the speed of the vehicle. If the vehicle is going slower, the speed of oscillation can be reduced, thereby causing a higher resolution 3D image of the environment. As the vehicle speeds up, the speed of oscillation can increase to give better overall coverage of obstacles further down the road. Accordingly, in one embodiment of the present invention, the angular scan rates for α and β (as shown in <figref idref="DRAWINGS">FIGS. 1A and 1B</figref> can be proportionate to the vehicle speed. Furthermore, in one embodiment of the present invention, as the vehicle moves faster, the scanned sectors could move farther out, or the speed of oscillation could change, or the angular sector could narrow (or all three could occur). The converse would apply when the vehicle slows down.

01153) Obstacles can be tracked in the present invention. Multiple imaging sensors can track obstacles and adjust their sectors to ensure that high threat obstacles are tracked (i.e., priority sectors or regions of interest can be established). For example, in one embodiment of the present invention, there are three imaging sensors on the front of the vehicle. If an obstacle is detected, two imaging sensors can keep analyzing the path, while the other sensor changes its sector to ensure that the obstacle can be scanned. Such capability permits the tracking of moving obstacles or other vehicles or for passing another vehicle at relatively high speed. Accordingly, in one embodiment of the present invention, respective ones of the imaging sensors <b>8</b> can be dedicated to imaging and obstacle identification and tracking in predetermined sectors.

01164) Zone coverage is another advantage that can be realized in the present invention. The processor <b>24</b> could specify several zones around the vehicle with different levels of priority and multiple imaging sensors could dynamically adjust their sectors to make sure that all zones were covered based upon priority. For example, if the path directly in front of the vehicle were the highest priority and the sides of the vehicle were lower priority, then the sensors could be dynamically adjusted to always ensure that the front of the vehicle was adequately covered, and if additional sensors were available, then the sides would be covered too. This approach allows for easy scalability and fault tolerance. The processor <b>24</b> in one embodiment of the present invention could realize that one of the sensors had failed, and then dynamically adjust for the failed sensor to ensure that the proper zones were always covered. Adding sensors increases coverage areas and redundancy or fault tolerance. Accordingly, in one embodiment of the present invention, respective ones of the imaging sensors <b>8</b> provide hardware redundancy and field of view redundancy.

0117Besides input from redundant imaging sensors, the processor <b>24</b> in one embodiment of the present invention receives input from on-board vehicle sensors. One of these inputs is a wheel speed sensor which provides transistor-transistor logic (TTL) pulses based upon an encoder placed on a single wheel on the vehicle. When a wheel speed sensor is added, the processor <b>24</b> uses GPS data from the positioning device <b>25</b> to initially calibrate the TTL pulses to actual vehicle movement. In the event that GPS data is not available, due to for example tunnels, canyons, or other obstructions, the processor <b>24</b> is able to minimize the positional drift by making use of the wheel speed sensor and its latest reliably known correspondence to the vehicle's movement.

0118The wheel speed sensor included a digital sensor capable of detecting either ferrous metal or magnets that are in motion. The digital sensor was mounted in the wheel well adjacent to the stock Antilock Brake System (ABS) sensor, which allowed the wheel speed sensor to read the same magnets mounted on the wheel that the ABS sensor did. This level of accuracy permits the vehicle <b>10</b> to precisely know its location on the earth.

0119Another input to processor <b>24</b> (as described later) is input from a biometric sensor or input from command button in which a driver to the vehicle can relinquish or take control of the vehicle <b>10</b>.

0120<figref idref="DRAWINGS">FIG. 8</figref> illustrates one embodiment of a computer system <b>1201</b> in which the processor <b>24</b> (or any of the specific processors discussed below) of the present invention can be implemented. The computer system <b>1201</b> is programmed and/or configured to perform any or all of the functions described above. Further, respective functions can be divided among different computers on board the vehicle (as shown for example in the computing network system of <figref idref="DRAWINGS">FIG. 9</figref>). These computers may be in communication with each other via the communications network <b>1216</b> (discussed below). The computer system <b>1201</b> includes a bus <b>1202</b> or other communication mechanism for communicating information, and a internal processor <b>1203</b> coupled with the bus <b>1202</b> for processing the information. The computer system <b>1201</b> includes a memory <b>1204</b>, such as a random access memory (RAM) or other dynamic storage device (e.g., dynamic RAM (DRAM), static RAM (SRAM), and synchronous DRAM (SDRAM)), coupled to the bus <b>1202</b> for storing information and instructions to be executed by the internal processor <b>1203</b>. In addition, the memory <b>1204</b> may be used for storing temporary variables or other intermediate information during the execution of instructions by the internal processor <b>1203</b>. The computer system <b>1201</b> preferably includes a non-volatile memory such as for example a read only memory (ROM) <b>1205</b> or other static storage device (e.g., programmable ROM (PROM), erasable PROM (EPROM), and electrically erasable PROM (EEPROM)) coupled to the bus <b>1202</b> for storing static information and instructions for the internal processor <b>1203</b>.

0121The computer system <b>1201</b> may also include special purpose logic devices (e.g., application specific integrated circuits (ASICs)) or configurable logic devices (e.g., simple programmable logic devices (SPLDs), complex programmable logic devices (CPLDs), and field programmable gate arrays (FPGAs)). The computer system may also include one or more digital signal processors (DSPs) such as the TMS320 series of chips from Texas Instruments, the DSP56000, DSP56100, DSP56300, DSP56600, and DSP96000 series of chips from Motorola, the DSP1600 and DSP3200 series from Lucent Technologies or the ADSP2100 and ADSP21000 series from Analog Devices. Other processors especially designed to process analog signals that have been converted to the digital domain may also be used (as detailed in the working example below).

0122The computer system <b>1201</b> performs a portion or all of the processing steps of the invention in response to the internal processor <b>1203</b> executing one or more sequences of one or more instructions contained in a memory, such as the main memory <b>1204</b>. Such instructions may be read into the main memory <b>1204</b> from another computer readable medium, such as a hard disk <b>1207</b> or a removable media drive <b>1208</b>. Such instructions may be read into the main memory <b>1204</b> from another computer readable medium, such as a USB flash drives or jump drives. Such drives are solid-state memory devices which have the ability to act as floppy disks or hard drives under most computer operating systems. One or more processors in a multi-processing arrangement may also be employed to execute the sequences of instructions contained in main memory <b>1204</b>. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions. Thus, embodiments are not limited to any specific combination of hardware circuitry and software.

0123As stated above, the computer system <b>1201</b> includes at least one computer readable medium or memory for holding instructions programmed according to the teachings of the invention and for containing data structures, tables, records, or other data described herein. Examples of computer readable media suitable for the present invention are compact discs, hard disks, floppy disks, tape, magneto-optical disks, PROMs (EPROM, EEPROM, flash EPROM), DRAM, SRAM, SDRAM, or any other magnetic medium, compact discs (e.g., CD-ROM), or any other optical medium, punch cards, paper tape, or other physical medium with patterns of holes, a carrier wave (described below), or any other medium from which a computer can read.

0124Stored on any one or on a combination of computer readable media, the present invention includes software for controlling the computer system <b>1201</b>, for driving a device or devices for implementing the invention, and for enabling the computer system <b>1201</b> to interact with a human user (e.g., a driver). Such software may include, but is not limited to, device drivers, operating systems, development tools, and applications software. Such computer readable media further includes the computer program product of the present invention for performing all or a portion (if processing is distributed) of the processing performed in implementing the present invention. The computer code devices of the present invention may be any interpretable or executable code mechanism, including but not limited to scripts, interpretable programs, dynamic link libraries (DLLs), Java classes, and complete executable programs. Moreover, parts of the processing of the present invention may be distributed for better performance, reliability, and/or cost.

0125The term “computer readable medium” as used herein refers to any medium that participates in providing instructions to the internal processor <b>1203</b> for execution. A computer readable medium may take many forms, including but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media includes, for example, optical, magnetic disks, and magneto-optical disks, such as the hard disk <b>1207</b> or the removable media drive <b>1208</b>. Volatile media includes dynamic memory, such as the main memory <b>1204</b>. Transmission media includes coaxial cables, copper wire and fiber optics, including the wires that make up the bus <b>1202</b>. Transmission media also may also take the form of acoustic or light waves, such as those generated during radio wave and infrared data communications.

0126Various forms of computer readable media may be involved in carrying out one or more sequences of one or more instructions to internal processor <b>1203</b> for execution. For example, the instructions may initially be carried on a disk to a remote computer. An infrared detector coupled to the bus <b>1202</b> can receive the data carried in the infrared signal and place the data on the bus <b>1202</b>. The bus <b>1202</b> carries the data to the main memory <b>1204</b>, from which the internal processor <b>1203</b> retrieves and executes the instructions. The instructions received by the main memory <b>1204</b> may optionally be stored on storage device <b>1207</b> or <b>1208</b> either before or after execution by the internal processor <b>1203</b>.

0127For instance, in one embodiment of the present invention, a computer readable medium contains program instructions for execution on a processor in a vehicle, which when executed by the processor, cause the processor to scan repeatedly a beam into a two-dimensional sector of a plane defined with respect to a first predetermined axis of the vehicle, to detect a reflection of the emitted beam from an object removed from the vehicle, to pan the plane in which the beam is scanned about a second predetermined axis to produce a three dimensional field of view, and to determine the existence and location of the object in the three dimensional field of view based on a position of the vehicle and a time between an emittance of the beam and a reception of the reflection of the emitted beam.

0128In one embodiment of the present invention, a computer readable medium contains program instructions for execution on a processor in a vehicle, which when executed by the processor, cause the processor to scan objects in a field of view from the vehicle, to determine a location of the objects in the field of view, to determine first and second points on a contour map of an identified object, to determine if the first point is farther away from the vehicle than the second point, to determine a slope between the first point and the second point, to determine if the slope is greater than a predetermined slope, and to determine if a height between the first point and the second point is greater than a predetermined height, and if so, to determine that the object is an obstacle.

0129In one embodiment of the present invention, a computer readable medium contains program instructions for execution on a processor in a vehicle, which when executed by the processor, cause the processor to scan objects in a field of view from the vehicle, to determine a location of the objects in the field of view, to perform an obstacle identification algorithm to determine if any object is an obstacle, to determine a field of view subsector in which a determined obstacle exists, and to store in a corresponding memory element an obstacle indicator indicative that an obstacle exists in a corresponding subsector.

0130In one embodiment of the present invention, a computer readable medium contains program instructions for execution on a processor in a vehicle, which when executed by the processor, cause the processor to scan objects in a field of view from the vehicle, to determine a location of the objects in the field of view, to direct a scan in a first sector associated with a path of the vehicle, and to direct a scan in a second sector identified with an obstacle.

0131In one embodiment of the present invention, a computer readable medium contains program instructions for execution on a processor in a vehicle, which when executed by the processor, cause the processor to scan objects in a field of view from the vehicle, to determine a location of the objects in the field of view, to direct a scan selectively in a sector associated with a projected turn in a path of the vehicle.

0132The program instructions, in various embodiments of the present invention, are configured to cause the processor to determine which of the sectors to scan based on at least one of a vehicle speed, an identified obstacle location, a projected path of the vehicle, a resolution required to resolve a complex obstacle or a collection of obstacles to be resolved, sensory input other than from the sensors, an identified priority sector in which an obstacle has been identified, and auxiliary information indicating the presence of an obstacle, a moving obstacle, another vehicle, a landmark, or an area of interest.

0133Further, the computer readable medium of the present invention can include program instructions detailing geographical information associated with a particular locale, path planning algorithms (as described below), navigational instructions, instructions particular to an installed image sensor on the vehicle, instructions for command and/or receipt of data from additional sensors such a stereoscopic cameras, or vehicle wheel speed sensors, or receipt of data from driver input control devices or other on-board devices (such as those described later), path planning algorithms, a particularized vehicle transfer function containing data regarding vehicle thrust and response to external forces for the autonomous vehicle in use, and steering control for the autonomous vehicle in use.

0134The computer system <b>1201</b> also includes a communication interface <b>1213</b> coupled to the bus <b>1202</b>. The communication interface <b>1213</b> provides a two-way data communication coupling to a network link <b>1214</b> that is connected at least temporarily to, for example, a local area network (LAN) <b>1215</b>, or to another communications network <b>1216</b> such as the Internet during downloading of software to the processor <b>24</b> or an internal network between multiple computers on board the vehicle. For example, the communication interface <b>1213</b> may be a network interface card to attach to any packet switched LAN. As another example, the communication interface <b>1213</b> may be an asymmetrical digital subscriber line (ADSL) card, an integrated services digital network (ISDN) card or a modem to provide a data communication connection to a corresponding type of communications line. Wireless links may also be implemented as part of the communication interface <b>1213</b> to provide data exchange with any of the on-board computers, image sensors, wheel speed sensors, biometric sensors, and/or driver command input devices. In any such implementation, the communication interface <b>1213</b> sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

0135The network link <b>1214</b> typically provides data communication through one or more networks to other data devices to provide data exchange with any of the on-board computers, image sensors, wheel speed sensors, biometric sensors, and/or driver command input devices. For example, the network link <b>1214</b> may provide a temporary connection to another computer through a local network <b>1215</b> (e.g., a LAN) or through equipment operated by a service provider, which provides communication services through a communications network <b>1216</b>. As shown in <figref idref="DRAWINGS">FIG. 8</figref>, the computing system <b>1201</b> can be in communication with an input device <b>1217</b> via the local network <b>1215</b> and the communications network <b>1216</b> which use, for example, electrical, electromagnetic, or optical signals that carry digital data streams, and the associated physical layer (e.g., CAT 5 cable, coaxial cable, optical fiber, etc). The signals through the various networks and the signals on the network link <b>1214</b> and through the communication interface <b>1213</b>, which carry the digital data to and from the computer system <b>1201</b> may be implemented in baseband signals, or carrier wave based signals. The baseband signals convey the digital data as unmodulated electrical pulses that are descriptive of a stream of digital data bits, where the term “bits” is to be construed broadly to mean symbol, where each symbol conveys at least one or more information bits. The digital data may also be used to modulate a carrier wave, such as with amplitude, phase and/or frequency shift keyed signals that are propagated over a conductive media, or transmitted as electromagnetic waves through a propagation medium. Thus, the digital data may be sent as unmodulated baseband data through a “wired” communication channel and/or sent within a predetermined frequency band, different than baseband, by modulating a carrier wave. The computer system <b>1201</b> can transmit and receive data, including program code, through the network(s) <b>1215</b> and <b>1216</b>, the network link <b>1214</b>, and the communication interface <b>1213</b>. Moreover, the network link <b>1214</b> may provide a connection through a LAN <b>1215</b> to the various GPS and INS systems on board the vehicle. The input device <b>1217</b> in various embodiments of the present invention provides input to the processor <b>24</b> and represents schematically the image sensors, wheel speed sensors, biometric sensors, and/or driver command input devices discussed in the present invention.

WORKING EXAMPLE

0136A 2005 Ford Escape Hybrid™ (hereinafter referred to as the working vehicle) was modified to include the imaging sensors <b>8</b> of the present invention. The working vehicle used a hybrid drive system in which an electric engine operates virtually all of the time and in which the gas engine starts and stops automatically to either provide extra horsepower or to recharge the electric engine's battery. The working vehicle's electrical system, which was powered by a 330-volt battery, provides over 1300 watts of power to the equipment mounted in the working vehicle.

0137The working vehicle utilized a commercially available Advanced Electronic Vehicle Interface Technology (AEVIT) “drive-by-wire” system from Electronic Mobility Controls (EMC) to physically control the car. The AEVIT system uses redundant servos and motors to turn the steering wheel, switch gears, apply throttle, and apply brake. This commercial system has a proven safety record in the automobile industry due to its use of redundant hardware.

0138The working vehicle provided 110 amps of power at 12 volts. The imaging sensor <b>8</b> utilized in the working vehicle operated on 24 volts. Rather than provide this power from the working vehicle's 12 volt electrical system, an auxiliary 24 volt electrical system for the imaging sensor was provided. The auxiliary electrical system included two 12 volt batteries connected in series to provide 24 volts of power. Solar panels were installed on top of the vehicle to charge the batteries in the auxiliary system.

0139In the working vehicle, a 2.8 Gigahertz Intel Pentium III™ processor including 2 gigabytes of RAM was used as the processor <b>24</b>. The 2.8 Gigahertz Intel Pentium III™ processor operated on 12 volt power supply, so an AC to DC power inverter was not needed. The 2.8 Gigahertz Intel Pentium III™ processor hosted the principle computing functions, such as for example the sensor communication, vehicle controls, and artificial intelligence.

0140Additionally, the working vehicle included several 1.42 Gigahertz Apple Mac Mini™ computers to host the path-planning software. The 1.42 Gigahertz Apple Mac Mini™ computers (running on running Apple OS X 10.4 software) were programmed to perform all of the path calculations in a redundant cluster to ensure that the path planning software was not suspect to a single point of failure. The Mac Mini™ computers had low power consumption (less than 2.3 amps at peak) and vector math processing capabilities. The processors listed above can be shock mounted on the vehicle to prevent damage from sudden changes in the direction of the vehicle or the crossing of obstacles along the path.

0141<figref idref="DRAWINGS">FIG. 9</figref> shows a high level schematic of a computing network system of the present invention employing the computers and sensor data discussed above. In this networked system, the individual processors have similar capabilities and computer elements as described with respect to <figref idref="DRAWINGS">FIG. 8</figref>. <figref idref="DRAWINGS">FIG. 9</figref> shows that on-board electrical motor control (EMC) equipment is driven by instructions from the Navigational Computer. The Navigational Computer is connected by a switch (shown as a CISCO Switch) to a Sensor Processing Computer and a Path Planning Computer. These computers receive input from the RT3000™ GPS and INS positioning device (described below). The Path Planning Computer and the Navigational Computer utilize various path planning and speed control algorithms (described below) to provide steering instructions to the vehicle. The Sensor Processing Computer as shown in one illustrative embodiment of the present invention receives input from imaging sensor <b>8</b> (for example the LADAR devices shown) and encoders on the shaft of a LADAR device (for example the optical encoders shown). The LADAR devices provide distance data and the instantaneous angle α of the LADAR device in the predetermined angular scanning sector as shown in <figref idref="DRAWINGS">FIG. 1A</figref>. In one embodiment, optical encoders are used as the rotary encoders <b>32</b> discussed above and provide the Sensor Processing Computer with the panning angle β relative to for example a vertical axis, as shown in <figref idref="DRAWINGS">FIG. 1B</figref>. Optical encoders are used in this embodiment of the present invention because of their high accuracy. Since optical encoders do not rely on physical contact with the shaft <b>34</b>, but rather visually determine movement, optical encoders are more accurate and less prone to failure. The encoders from Fraba Posital were specifically used in the working vehicle because of their Ethernet capability.

0142The working vehicle utilized RT3000™ positioning devices from Oxford Technical Solutions to provide vehicle localization (i.e., positioning data). The RT3000™ uses Omnistar™ HP differential GPS signals to provide position accuracy of 10 centimeters or less. Integrated INS in the RT3000™ permits the RT3000™ to survive GPS outages of up to 30 seconds with virtually no performance degradation. Because the GPS and INS were integrated together, each can compensate for problems with the other. For example, if the INS started to drift laterally, the integrated GPS will automatically correct that drift. In the working vehicle, two Oxford RT3000™ GPS units were employed in a primary/secondary role.

0143The working vehicle utilized commercially available laser modulation systems (LMS) for the imaging sensors <b>8</b> such as three SICK™ LMS <b>291</b> LADAR units and one RIEGL™ LMS-Q 120 LADAR on the front of the vehicle. The LADAR units in the working vehicle were split into three different roles. The RIEGL™ LADAR was mounted vertically in the center of the vehicle and is used for long range (up to 80 meters) obstacle detection. The two SICK™ LMS <b>291</b> units were mounted vertically on either side of the RIEGL™. These vertically mounted units were used for short range obstacle detection (up to 50 meters). The other SICK™ LMS <b>291</b> was mounted horizontally on the center of the vehicle and is used for analyzing terrain features.

0144In order to protect these sensors from the elements as much as possible, a sun/weather guard was constructed over the sensor mounts. This guard protects the LADAR units from being blinded by direct sun glare, a common problem with Sick LADAR units. The guard can constitute a simple optical shield such as for example a piece of sheet-metal that was attached to the top of the imaging sensor. The guard extended over the front of LADAR unit (or other imaging sensor) and had a slight bend to better protect the sensors from the sun. Since LADAR units produce their own light source, low light conditions have no effect on the sensors. In fact, testing showed that low light conditions actually produced better results than bright conditions, due to excessive reflections under bright sunlight. These reflections, along with dust or rain, can produce ghosting patterns or other anomalies in the sensor readings. To counteract these anomalies, the present invention utilizes filtering algorithms to correct for anomalies before the anomalies can cause problems in the path planning software. For example, the filtering algorithm in one embodiment associates isolated obstacle points with noise data and discards these data points, under the assumption that “real” obstacles have a physical size greater than the resolution of the imaging sensor.

0145On the working vehicle, stereoscopic cameras capable of producing a three-dimensional point cloud were mounted on the front of the vehicle behind the windshield. These cameras operated in a secondary mode to the LADAR units. The cameras are used to help identify the road and to confirm the existence of obstacles. If a LADAR unit identifies an obstacle and the stereoscopic cameras also detect an obstacle in that area, the obstacle avoidance algorithms increase the confidence level associated with that obstacle. Confidence levels were used to help decide which obstacles must absolutely be avoided and which obstacles are possibly driven over without damage.

0146<figref idref="DRAWINGS">FIG. 10</figref> is a high level schematic of the vehicle control system of the present invention. <figref idref="DRAWINGS">FIG. 10</figref> shows an iterative loop control system using inputs from the sensors and providing vehicle control. For the sake of illustration, at <b>102</b>, LADAR data stored in a memory unit for example of the Sensor Processing Computer in <figref idref="DRAWINGS">FIG. 9</figref> is provided to obstacle detection unit <b>104</b>, speed planning unit <b>106</b>, and accelerator/brake control <b>108</b>. GPS/INS unit <b>110</b> also provided to the obstacle detection unit <b>104</b>. Once the obstacle detection unit <b>104</b> decides which objects in the field of view are obstacles (for example using the conditions specified in eqns. (1), (2), and (3) above, obstacle identification data is forwarded to the speed planning unit <b>106</b> and to path planning unit <b>112</b>. The path planning unit <b>112</b> receives input from a route definition data file (RDDF) unit <b>114</b> and provides the path data to steering control unit <b>116</b>. EMC Vehicle Control <b>118</b> takes input from the steering control unit <b>116</b> and the accelerator/brake control <b>108</b> to control the working vehicle.

0147The obstacle detection unit <b>104</b> utilizes in one embodiment of the present invention spatial indices to correlate the sensor data with localization data indicating in which sector an obstacle is located (for example a near sector requiring immediate consideration or a far sector not requiring immediate consideration). <figref idref="DRAWINGS">FIG. 5</figref> shows a division of the field of view into sectors: the sector defined between rays A and B, the sector defined between rays B and C, and the sector defined beyond C. Instead of storing all obstacles in one large spatial index, each segment of the path corridor has a corresponding spatial index in memory. Such division in one embodiment permits the present invention to call up from memory the sectors of importance for example when navigating obstacles <b>22</b><i>a </i>and <b>22</b><i>b. </i>

0148The obstacle detection unit <b>104</b> in one embodiment of the present invention uses times-stamps taken with each LADAR scan and GPS reading. These timestamps are then correlated based upon position and heading to produce a geospatial location for obstacles, for example the obstacles themselves may be moving. Timestamping can counteract anomalies in the images. Highly reflective surfaces can cause the LADAR devices to register incorrect distances for obstacles. To counteract these anomalies, in one embodiment of the present invention, scans are only kept in memory for a designated amount of time. After that time has passed, if no more obstacles have been registered in that same area, the obstacle is removed from memory storage. This technique ensures that moving obstacles are handled correctly. If another vehicle or an obstacle(s) crosses the vehicle path in a perpendicular direction to the autonomous vehicle, the sensors would effectively register a sequence of obstacles in front of the autonomous vehicle. These obstacles would appear as a complete obstruction of the vehicle's path, forcing the vehicle to immediately stop. After enough time had passed, the obstacles would expire, and the autonomous vehicle would be able to start moving again. A persistent obstacle, on the other hand, would not expire.

0149Consider, for example, a large boulder that is located in the center of the path. At a distance of approximately forty to fifty meters, the LADAR devices will start to register parts of the boulder. As vehicle <b>10</b> gets to within ten to twenty meters of the vehicle, the previous scans would begin to approach the obstacle expiration time. Since the sensors are still registering the boulder, the previous scans will not expire. Instead, the previous scans along with the current scans would all be retained, giving the boulder a higher count for total number of scans. This high count for the number of scans causes the boulder to have an extremely high probability of being an obstacle.

0150The path-planning algorithms of the present invention avoid obstacles and routinely steer the vehicle within a planned corridor. In one embodiment, these algorithms without cause will not deviate the vehicle from the planned corridor. However, should the vehicle leave the route corridor for some reason, the navigation system will detect this and provide a safe route back into the corridor. If a waypoint is missed, the navigation system will simply continue to the next feasible waypoint on the path. If the path is obstructed by an obstacle, the path planning systems will determine a path around the obstacle.

0151Path planning in one embodiment of the present invention is accomplished through the use of cubic b-splines designed to follow the center of the planned route while still ensuring that the path is not impossible for the vehicle to navigate. This assurance means that the curvature at any point along the path is below the maximum curvature that the vehicle can successfully follow. In addition, the curvature is kept continuous so that it is not necessary to stop the vehicle in order to turn the steering wheel to a new position before continuing. B-splines were chosen for use in the path planning algorithms primarily because of the ease in which the shape of their resulting curves can be controlled. After an initial path is created that follows the center of the corridor, the path is checked against the obstacle repository to determine if it is a safe path. If the path is not safe, a simple algorithm generates and adjusts control points on the problem spots of the curve until the spline avoids all known obstacles while still containing valid maximum curvature. At this point, the path is both safe and drivable.

0152The path planning of the present invention can also uses a Level of Detail (LOD) based obstacle avoidance algorithm along with several planning algorithms to plan paths around obstacles. LOD analysis in one embodiment of the present invention permits running the same algorithm with different levels of detail. For example, running with less detail (e.g., to accommodate large safety margins), then iteratively increasing the detail (e.g., to accommodate smaller safety margins) until a valid path is found. The path planning algorithms run using several different parameters until a valid path is found. The initial parameters use safety margins (for example the clearance of the vehicle from an obstacle or between obstacles), while the final parameters use no safety margins around obstacles. This ensures that if a path is available that will avoid an obstacle with a large margin of error (e.g., vehicle lateral clearance) the path planning software selects that path. Otherwise, the planning algorithm will keep reducing the safety margin around obstacles until a valid path is determined.

0153<figref idref="DRAWINGS">FIGS. 11</figref>, <b>12</b>, and <b>13</b> illustrate results of path planning. In <figref idref="DRAWINGS">FIG. 11</figref>, the obstacle detection unit identifies an obstacle <b>22</b> by the cluster of data points in the center of the road <b>80</b>. The path planning unit determines that there is adequate clearance to permit the vehicle <b>10</b> to deviate to the right as it advances to the obstacle <b>22</b> and then deviate left to return to the center of the road <b>80</b>. The projected path of the vehicle <b>10</b> is shown by path <b>82</b>. In <figref idref="DRAWINGS">FIG. 12</figref>, the path <b>82</b> of the vehicle <b>10</b> passes a center of the obstacle <b>22</b> to the left and then to the right as shown. The path planning unit has divided the path and the data map into sectors as shown. The first sector at the bottom contains no obstacles and requires no deviation along the planned path <b>82</b>. The second sector contains an obstacle <b>22</b> and requires the path planning unit to determine clearance and a path around the obstacle <b>22</b>. Further, deviation from the path will rely on the speed planning unit to control the vehicle so as to safely pass the vehicle at a speed suited for the radius of the turn. <figref idref="DRAWINGS">FIG. 13</figref> shows a vehicle <b>10</b> that is about to navigate a series of obstacles in an immediate path of the vehicle.

0154The present invention recognizes that smooth paths alone are not necessarily drivable by the vehicle. The car should be able to slow down proportionally from straight-aways down to hairpin turns. Once a safe path is designed that avoids obstacles and yet remains drivable, the next step in the planning process is to decide on the speed at which the vehicle should take each section of the path. The speed chosen, in one embodiment of the present invention, is based on the curvature at that point in the path and upon the curvature further down the path. The speed is taken as the minimum of speed for the current curvature and the speed for future path curvature. The future path curvature is defined by a simple function that multiplies the curvature at a given future point by a fractional value that decreases towards zero linearly based upon the distance from the current path point to the given future path point.

0155The present invention accommodates factors such as vehicle thrust and external forces on the vehicle. System identification is a method used by the present invention by which the parameters that define a system can be determined by relating input signal into a system with the system's response to develop a transfer function that behaves in the same way (or a similar way) as the actual vehicle system. For instance, when attempting to control the speed of a vehicle, the inputs are the brake and accelerator position and the output is the vehicle's speed. If it is assumed that the transfer function, H(s), is first-order, it can be written as

0000<br /><i>y</i>(<i>s</i>)=<i>H</i>(<i>s</i>)<i>u</i>(<i>s</i>)  (8)

0000where H(s) is the transfer function of a system, u(s) is the input to the system, and y(s) is the output from the system. System identification was applied to real world data from the vehicle propulsion system to arrive at a transfer function of the vehicle system for example empirically tested for the working vehicle until confidence in an accurate transfer function was obtained.

0156Accordingly, speed control of the vehicle, according to the present invention, accommodated not only accelerator and brake functions but also accommodated many other factors in the physical engine system. For instance, since the working vehicle had a gas-electric hybrid engine, the coupling of the two propulsion systems was controlled by an inaccessible factory-installed on-board computer tuned for fuel efficiency. Consequently, the mapping of the requested pedal position and the actual position achieved was not linear and had to be remapped in software by empirical determination. In one embodiment of the present invention, the speed of the vehicle is controlled by an integrated proportional-derivative (PD) controller. This controller bases its output on the previous output and on the current error and derivative of the error. In the time domain, the controller can be written as

0000<br /><i>u</i>(<i>t</i>2)=(<i>t</i>2<i>−t</i>1)(<i>K</i>_p<i>e</i>(<i>t</i>₂)+<i>K</i>_d<i>e</i>′(<i>t</i>₂))+<i>u</i>(<i>t</i>₁)  (9)

0000where K_pand K_dare tunable coefficients, u(t) is the output of the controller at time t, and e(t) is the error at time t. The error was defined as actual output subtracted from target output. Actual output was reported by the RT3000™, and target speed was derived from the path planning algorithms.

0157The integrated PD controller was designed and tuned against the derived transfer function detailed above. For instance, the weights (for the proportionate control in the PD controller) needed for optimal performance were derived initially against the computational model of the derived transfer function, and then tuned when operated on the vehicle.

0158Accelerator and steering wheel control was achieved in the working vehicle using two separate processes, which were both independent of the path-planning systems. Once a path was decided on by the path-planning algorithms, acceleration and steering is used exclusively to remain on the chosen path. Since paths are checked for feasibility upon creation, it was assumed by the control systems that all paths given are possible for the vehicle to achieve. In this manner (although the present invention can use other starting assumptions), it becomes the burden of the control systems to decide how best to proceed in order to follow the selected path.

0159The steering controller for the working vehicle was a lead-lag controller based on the classical single-track model or bicycle model described ed by Riekert and Schunck “Zur fahrmechanik des gummibereiften kraftfahrzeugs,” in Ingenieur Archiv, vol. 11, 1940, pp. 210-224, the entire contents of which are incorporated herein by reference. A lead compensator increases the responsiveness of a system; a lag compensator reduces (but does not eliminate) the steady state error. The lead-lag compensator was based on the frequency response of the system. The lead-lag compensator was similar to that described by D. Bernstein, A students guide to classical control, IEEE Control Systems Magazine, vol. 17, pp. 96-100 (1997), the entire contents of which are incorporated herein by reference. The resulting controller in the working vehicle was a convolution of the two lead and lag functions multiplied by the low frequency gain, which was 0.045. Adaptive estimation parameters were used. Adaptive estimation uses a set of values (parameters) first gained from applying the theoretical functions and then iteratively tests and modifies the parameters in real-world scenarios (e.g., deep sand, rough terrain, and other terrain types) until the parameters are perfected.

0000<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>F</mi><mi>lead</mi></msub><mo></mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow><mo>=</mo><mfrac><mrow><mrow><mn>850</mn><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>s</mi></mrow><mo>+</mo><mn>1</mn></mrow><mrow><mrow><mn>900</mn><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>s</mi></mrow><mo>+</mo><mn>1</mn></mrow></mfrac></mrow></mtd><mtd><mrow><mo>(</mo><mn>10</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><mrow><msub><mi>F</mi><mi>lag</mi></msub><mo></mo><mrow><mo>(</mo><mi>s</mi><mo>)</mo></mrow></mrow><mo>=</mo><mfrac><mrow><mrow><mn>2</mn><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>s</mi></mrow><mo>+</mo><mn>4</mn></mrow><mrow><mrow><mn>0.2</mn><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>s</mi></mrow><mo>+</mo><mn>1</mn></mrow></mfrac></mrow></mtd><mtd><mrow><mo>(</mo><mn>11</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><img file="US2013131908A1_D0004.tif" />

0160The discretized controller was implemented as shown in (12) and (13), where x is the state vector, {dot over (x)} is the derivative of the state vector with respect to time, u is the input vector and δ_fis the output steering angle as measured at the tire with respect to the centerline. The state vector x is defined as [y_sΨ] where y_srefers to the distance from the virtual sensor to the reference path and Ψ is the vehicle's yaw rate. The virtual sensor is a point projected a given distance ahead of the vehicle along the vehicle's centerline. This point is commonly referred to as the look-ahead point, and the distance from the look-ahead point to the RT3000 is referred to as the look-ahead distance.

0000<maths id="MATH-US-00005" num="00005"><math overflow="scroll"><mtable><mtr><mtd><mrow><mover><mi>x</mi><mo>.</mo></mover><mo>=</mo><mrow><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mn>0.90475</mn></mtd><mtd><mrow><mo>-</mo><mn>0.00054</mn></mrow></mtd></mtr><mtr><mtd><mn>0.00054</mn></mtd><mtd><mn>0.99998</mn></mtd></mtr></mtable><mo>]</mo></mrow><mo></mo><mi>x</mi></mrow><mo>+</mo><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mrow><mo>-</mo><mn>1.07538</mn></mrow></mtd></mtr><mtr><mtd><mn>0.00277</mn></mtd></mtr></mtable><mo>]</mo></mrow><mo></mo><mi>u</mi></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>12</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><img file="US2013131908A1_D0005.tif" /><br />δ_f=[0.02150 0.00005<i>]x+[</i>0.00005<i>]u</i>  (13)

0161The input vector u to the controller is defined as [y_s]. The output of the controller is the steering angle measured at the tire with respect to the centerline.

0162The steering and control system in the working vehicle assumed that the relationship between the steering wheel angle and the resulting tire angle was linear and that the location of the vehicle's center of gravity was at the midway point between the front and rear axles. As a measure of safety the magnitude of the y_ssignal was monitored to prevent the vehicle from becoming unstable. If y_swere to cross a given threshold, meaning the vehicle is severely off path, the speed of the vehicle was reduced to 2 mph. This allowed the vehicle to return onto the desired path and prevented a possible rollover.

Application Areas

0163The present invention has widespread application in both autonomously driven and human driven vehicles where the present invention functions respectively in a primary or secondary mode.

0164In general, the present invention with various of the attributes described above can be included on a variety of driveable units. Such units in one embodiment of the present invention are powered land or water based vehicles, which include for example automobiles, trucks, sport utility vehicles, armored vehicles, boats, ships, barges, tankers, and armored vessels. For watercraft, the present invention could be used not only when navigating in weather or nighttime conditions where visibility is limited and avoidance of other watercraft is desired, but also in docking and lock operations where control of the watercraft between dock and lock structures is important to minimize damage to the watercraft of the dock and lock structures.

0165The present invention also has application to aircraft. In particular, the application to high speed aircraft will depend on detector sensitivity and accuracy to determine the existence of objects at a sufficient distance from the plane that the plane can take corrective action. However, airport approach and takeoff where the speeds are not high the present invention has utility. For example, on take off and landing, one concern has been whether flocks of birds frequently at the end of the run way area pose risk to engines. Birds are hard to see at distance for the human eye and hard to detect by aircraft radar. Moreover, the present invention has application to helicopters, especially rescue helicopters that frequently land in make-shift areas with obstacles many times hidden from the view of the pilot.

0166Other application areas include lighter-than-air vehicles (e.g., autonomous weather balloons, autonomous border patrol system including for example remote control small aircraft), other small reconnaissance aircraft, and amphibious vehicles (such as for example land-sea assault vehicles including hovercrafts etc.).

0167In one embodiment of the present invention, the driveable unit can be an autonomous vehicle without driver-assisted control or a driver-controlled vehicle with computer-assisted control. The autonomous vehicles find application, according to one embodiment of the present invention, in the above noted environmentally dangerous surroundings where a driver would be at risk. The driver-controlled vehicles of the present invention find application in the above noted more conventional environments, where the driver may become disoriented or incapable of physically commanding the vehicle as would occur if the driver suffered a medical emergency or if for example the driver became disoriented under an adverse driving condition. Accordingly, in one embodiment of the present invention, processor <b>24</b> is configured to control the vehicle in an event of driver impairment or in an event of immediate path obstruction or in an event of driver request.

0168As an illustrative example of this embodiment of the present invention, the autonomous vehicle could recognize driver impairment through observing where the driver is driving in comparison to a predetermined path. If the present path of the vehicle and the predetermined path are not similar, the autonomous vehicle could then check, for example, to see if the driver has recently turned the steering wheel and/or pressed on the either the brakes or throttle. Both of the comparison and the steering and brake check can be included in the decision making process, because if the driver were driving on a long straight road with cruise control on, he may not be actively turning the steering wheel or applying brake or throttle. By the same logic, the driver could be driving a path that is not consistent with the autonomous vehicle's path as long as the driver is actively steering the car. In the event that the autonomous vehicle needs to take over, then the autonomous vehicle in one embodiment of the present invention first audibly and visibly warns the driver that it is taking over, then second takes over and steers the vehicle to a safe stopping position as smoothly and safely as possible. If the driver wanted to regain control, the autonomous vehicle of the present invention, in one embodiment, provides a press-button or other input device for the driver to resume control. In another embodiment of the present invention, the driver could press the button (or command input) again to relinquish control to the autonomous vehicle. Hence, the present invention provides in various embodiments a cooperative autonomous driving mode.

0169In another embodiment of the present invention, a biometric sensor could represent another input device. In this embodiment, the biometric sensor determines if the driver was actively driving through input to processor <b>24</b> from for example a heart rate monitor built into the steering wheel of the vehicle. One example of a heart rate monitor that is suitable for the present invention is heart rate used in exercise equipment, which in one embodiment would be integrated into the steering wheel or alternatively could be worn by the driver and be in wireless communication to processor <b>24</b>. If the processor <b>24</b> detected either a complete loss of heart rate or an extremely low heart rate for an extended period of time (for example 5 seconds), the processor <b>24</b> is configured to take control of the vehicle. The processor, by monitoring the normal heart rate of the driver when the car was under proper control would have a basis for determining for example if the driver was impaired due to haven fallen asleep at the wheel, having had a stroke, or having had a heart attack. This embodiment could be implemented also in the cooperative mode of operation (discussed above). As before, in one embodiment of the present invention, an audible alarm is issued before taking over control of the vehicle and steering the vehicle to a safe stop. If the driver was in fact not impaired, the driver could simply press a button (or other input device) to take control back from the processor <b>24</b>.

0170In another embodiment of the present invention, the autonomous vehicle can be operated repeatedly over a predetermined course. For instance, a human driver presses a button that turns the autonomous vehicle into record mode. The human drives the vehicle exactly like he would want the autonomous vehicle to drive the course. The human driver then presses the button again, and the autonomous vehicle drives the recorded course over and over again with a very high level of reliability and repeatability. (Repeatability is an issue for automobile testers). This capability is also useful for endurance testing vehicles, where the vehicle is driven offroad in hazardous conditions for days in a row in which currently many human drivers are used to perform this task due to the human body's relative weakness. This capability is also useful for driving a vehicle at consistent speeds for long distances. For example, this capability would be useful in testing a vehicle at highway speeds on a race track for fuel consumption performance.

0171In another embodiment of the present invention, the driveable unit can be used, in conjunction with a mapping program (e.g., running on a laptop), in which the user could select a destination. At this point, the autonomous navigation software would access the mapping software and generate a route (like the software normally does) except in GPS waypoints rather than in human directions like “turn left at main street.” At this point, the autonomous vehicle proceeds in normal operation to follow that route. In one embodiment, the mapping software is customized to provide additional information to the autonomous navigation program such as the width of streets and speed limits.

0172Other application areas for the navigation and control system of the present invention include, but are not limited to: 1) agricultural equipment (e.g., gardening equipment) that performs repetitive tasks or tasks on predicted paths such as for example the harvesting of crops from fields, plowing, grass cutting, etc., 2) mining equipment including for example powered carts that could transport for example goods or people through blackout or smoke filled passages that would normally prevent escape, 3) cave exploration equipment, 4) emergency or police vehicles such as for example fire fighting, ambulances, and rescue squads where visibility impairment need not prevent the emergency vehicles from proceeding forward (as discussed below) or vehicles operating in hazardous environmental conditions where manning of the vehicle places the driver at risk, 5) warehouse management equipment used to store/retrieve pallets, boxes, etc., and 6) toys.

0173As an illustrative example of the application of the autonomous vehicle of the present invention to a police vehicle, on the Causeway bridge in New Orleans (the longest bridge in the world at 24 miles long), there is a significant fog season. On mornings with a dense fog, traffic is convoyed across the bridge by a police car driving at 35 mph. The low speed is required due to the extremely short visibility. On mornings with intense fog, the bridge is closed as even convoying is not possible. If the lead police car in the convoy were an autonomous vehicle of the present invention operating in the above-noted cooperative mode, the police car could safely convoy in any type of fog, especially when the RIEGL™ imaging sensor is used. The same applies to driving at night. The autonomous vehicle of the present invention is not affected by darkness.

0174Numerous modifications and variations on the present invention are possible in light of the above teachings. It is, therefore, to be understood that within the scope of the accompanying claims, the invention may be practiced otherwise than as specifically described herein.