System and method for generating paths in an autonomous vehicle

• US 5,648,901 A
• Filed: 05/01/1995
• Issued: 07/15/1997
• Est. Priority Date: 02/05/1990
• Status: Expired due to Term

• Current Assignee: Caterpillar Incorporated
• Original Assignee: Caterpillar Incorporated
• Inventors: Gudat, Adam J., Koehrsen, Craig L., Whittaker, William L., Shin, Dong Hun, Kemner, Carl A., Devier, Lonnie J., Kyrtsos, Christos T., Lay, Norman K., Peterson, Joel L., Schmidt, Larry E., Kleimenhagen, Karl W., Stafford, Darrell E., Weinbeck, Louis J., Singh, Sanjiv J., Christensen, Dana A., Bradbury, Walter J.
• Primary Examiner(s): PARK, COLLIN
• Application Number:
  US08/432,396
• Time in Patent Office: 806 Days
• Field of Search: 364/424.02, 364/443, 364/444, 180/167, 180/168, 180/169
• US Class Current: 701/23
• CPC Class Codes: B60K 31/0008 including means for detecting potential obstacles in vehicle path
• CPC Class Codes: B60K 31/04 and means for comparing one electrical quantity, e.g. voltage, pulse, waveform, flux, or the like, with another quantity of a like kind, which comparison means is involved in the development of an electrical signal which is fed into the controlling means
• CPC Class Codes: B62D 1/28 non-mechanical , e.g. following a line or other known markers
• CPC Class Codes: G01S 17/42 Simultaneous measurement of distance and other co-ordinates indirect measurement G01S17/46
• CPC Class Codes: G01S 17/86 Combinations of lidar systems with systems other than lidar, radar or sonar, e.g. with direction finders
• CPC Class Codes: G01S 17/931 of land vehicles
• CPC Class Codes: G01S 19/11 wherein the cooperating elements are pseudolites or satellite radio beacon positioning system signal repeaters
• CPC Class Codes: G01S 19/27 creating, predicting or correcting ephemeris or almanac data within the receiver
• CPC Class Codes: G01S 19/41 Differential correction, e.g. DGPS [differential GPS]
• CPC Class Codes: G01S 19/46 the supplementary measurement being of a radio-wave signal type
• CPC Class Codes: G01S 19/47 the supplementary measurement being an inertial measurement, e.g. tightly coupled inertial
• CPC Class Codes: G01S 19/52 Determining velocity
• CPC Class Codes: G01S 5/009 Transmission of differential positioning data to mobile
• CPC Class Codes: G01S 7/4811 common to transmitter and receiver
• CPC Class Codes: G05D 1/0011 associated with a remote control arrangement
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0242 using non-visible light signals, e.g. IR or UV signals
• CPC Class Codes: G05D 1/0268 using internal positioning means
• CPC Class Codes: G05D 1/027 comprising intertial navigation means, e.g. azimuth detector inertial navigation G01C21/16; inertial navigation combined with non-inertial navigation instruments G01C21/165
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• CPC Class Codes: G05D 1/0278 : using satellite positioning signals, e.g. GPS
• CPC Class Codes: G05D 1/0297 : by controlling means in a control room
• CPC Class Codes: G08G 1/202 : Dispatching vehicles on the basis of a location, e.g. taxi dispatching

Abstract

A system for generating a path allows a vehicle to traverse a predetermined route. The system stores route data for the predetermined route. The route data identifies a series of contiguous path segments that form the predetermined route. The route data also identifies a series of nodes located at the beginning and the end of the predetermined route and between adjacent path segments. Each path segment represents a series of postures along the predetermined route. Each posture identifies a position, a heading, and a curvature for the vehicle at a particular point along the predetermined route. The system stores the path segments and nodes as compressed path data. In one embodiment, the compressed path data is a function that is continuous in posture, i.e., continuous in position, heading and curvature. The system retrieves the compressed path data and generates a series of postures from the retrieved compressed path data to allow the vehicle to traverse the predetermined route.

Claims

1. In a system for enabling a vehicle to traverse a predetermined route, a system for generating a path for the vehicle to track comprising:

means for storing route data for the predetermined route, said route data identifying a plurality of path segments forming the predetermined route and a plurality of nodes located along the predetermined route at the beginning and the end of the predetermined route and between adjacent path segments, said path segments representing a plurality of postures of the vehicle, wherein each of said plurality of postures includes a position, a heading, and a curvature for the vehicle along the predetermined route;

means for storing said plurality of path segments and said plurality of nodes as compressed path data, said compressed path data representing said plurality of path segments and said plurality of nodes as a function, wherein said function is continuous in posture, said compressed path data reducing an amount of storage required for the predetermined route;

means for retrieving said compressed path data associated with the predetermined route; and

means for generating a series of postures from said retrieved compressed path data for the vehicle to track thereby allowing the vehicle to traverse the predetermined route.

2. The system of claim 1, wherein said means for storing said plurality of path segments and said plurality of nodes further comprises:

means for representing said plurality of path segments and said plurality of nodes as a clothoid curve.

3. The system of claim 2, wherein said means for representing said plurality of path segments and said plurality of nodes as a clothoid curve further comprises:

means for selecting a sequence of postures from said plurality of path segments and said plurality of nodes; and

means for interpolating between a first posture and a second posture with at least one clothoid segment, said first posture and said second posture being adjacent postures in said sequence of postures.

4. The system of claim 3, wherein said means for interpolating further comprises:

means for determining at least three clothoid segments between said first posture and said second posture so that an initial posture of a first clothoid segment is equal to said first posture and a final posture of a last clothoid segment is equal to said second posture.

5. The system of claim 4, wherein said means for determining at least three clothoid segments further comprises:

means for selecting sharpness parameters for said at least three clothoid segments so that said sharpness parameters have equal magnitude and alternating sign for each of said at least three clothoid segments.

6. The system of claim 1, wherein said means for storing said plurality of path segments and said plurality of nodes further comprises:

means for representing said plurality of path segments and said plurality of nodes as a B-spline.

7. The system of claim 6, wherein said means for representing said plurality of path segments and said plurality of nodes as a B-spline further comprises:

means for selecting a sequence of postures from said plurality of path segments and said plurality of nodes; and

means for fitting a B-spline function to said sequence of postures, said B-spline having sufficient order so that a curvature of said B-spline function is continuous, wherein said B-spline function represents a portion of the predetermined route.

8. The system of claim 6, wherein said means for representing said plurality of path segments and said plurality of nodes as a B-spline further comprises:

means for selecting a sequence of postures as the entire predetermined route; and

means for fitting a B-spline function to said sequence of postures, said B-spline having sufficient order so that a curvature of said B-spline function is continuous, wherein said B-spline function represents an entire portion of the predetermined route.

9. The system of claim 6, wherein said means for storing said plurality of path segments and said plurality of nodes as compressed path data further comprises:

means for storing each of said plurality of path segments as an individual B-spline function; and

means for fitting an overall B-spline function to said individual B-spline functions to form the compressed path data.

10. In a system for enabling a vehicle to traverse a predetermined route, a method for generating a path for the vehicle to track comprising the steps of:

storing route data for the predetermined route, said route data identifying a plurality of path segments forming the predetermined route and a plurality of nodes located along the predetermined route at the beginning and the end of the predetermined route and between adjacent path segments, said path segments representing a plurality of postures of the vehicle,, wherein each of said plurality of postures includes a position, a heading, and a curvature for the vehicle along the predetermined route;

storing said plurality of path segments and said plurality of nodes as compressed path data, said compressed path data representing said plurality of path segments and said plurality of nodes as a function, wherein said function is continuous in posture, said compressed path data reducing an amount of storage required for the predetermined route;

retrieving said compressed path data associated with the predetermined route; and

generating a series of postures from said retrieved compressed path data for the vehicle to track thereby allowing the vehicle to traverse the predetermined route.

11. The method of claim 10, wherein said step of storing said plurality of path segments and said plurality of nodes further comprises the step of:

representing said plurality of path segments and said plurality of nodes as a clothoid curve.

12. The method of claim 11, wherein said step of representing said plurality of path segments and said plurality of nodes as a clothoid curve further comprises the steps of:

selecting a sequence of postures from said plurality of path segments and said plurality of nodes; and

interpolating between a first posture and a second posture with at least one clothoid segment, said first posture and said second posture being adjacent postures in said sequence of postures.

13. The method of claim 12, wherein said step of interpolating further comprises the step of:

determining at least three clothoid segments between said first posture and said second posture so that an initial posture of a first clothoid segment is equal to said first posture and a final posture of a last clothoid segment is equal to said second posture.

14. The method of claim 13, wherein said step of determining at least three clothoid segments further comprises the step of:

selecting sharpness parameters for said at least three clothoid segments so that said sharpness parameters have equal magnitude and alternating sign for each of said at least three clothoid segments.

15. The method of claim 10, wherein said step of storing said plurality of path segments and said plurality of nodes further comprises the step of:

representing said plurality of path segments and said plurality of nodes as a B-spline.

16. The method of claim 15, wherein said step of representing said plurality of path segments and said plurality of nodes as a B-spline further comprises the steps of:

selecting a sequence of postures from said plurality of path segments and said plurality of nodes; and

fitting a B-spline function to said sequence of postures, said B-spline having sufficient order so that a curvature of said B-spline function is continuous, wherein said B-spline function represents a portion of the predetermined route.

17. The method of claim 15, wherein said step of representing said plurality of path segments and said plurality of nodes as a B-spline further comprises the steps of:

selecting a sequence of postures as the entire predetermined route; and

fitting a B-spline function to said sequence of postures, said B-spline having sufficient order so that a curvature of said B-spline function is continuous, wherein said B-spline function represents an entire portion of the predetermined route.

18. The method of claim 15, wherein said step of storing said plurality of path segments and said plurality of nodes further comprises the steps of:

storing each of said plurality of path segments as an individual B-spline function; and

fitting an overall B-spline function to said individual B-splines function to form the compressed path data.