METHOD FOR GENERATING OFFSET PATHS FOR GROUND VEHICLES

• US 20110231057A1
• Filed: 03/19/2010
• Published: 09/22/2011
• Est. Priority Date: 03/19/2010
• Status: Active Grant

• Current Assignee: Javad GNSS, Inc.
• Original Assignee: Javad GNSS, Inc.
• Inventors: Pesterev, Alexander V., Rapoport, Lev B., Ashjaee, Javad
• Granted Patent: US 9,168,946 B2
• Time in Patent Office: Days
• US Class Current: 701/41
• CPC Class Codes: A01B 69/008 automatic
• CPC Class Codes: B62D 1/02 vehicle-mounted
• CPC Class Codes: B62D 1/28 non-mechanical , e.g. following a line or other known markers
• CPC Class Codes: G05D 1/02 Control of position or course in two dimensions

Abstract

A computer-implemented method for generating at least one segment of an offset path for a vehicle based on at least one segment of a base path is provided. The at least one segment of the base path is represented by a stored set of data points. The computer-implemented method includes comparing the at least one segment of the base path to a curvature constraint to determine if the at least one segment of the base path violates the curvature constraint. The curvature constraint is based on a characteristic of the vehicle and a desired offset distance from the at least one segment of the base path. The characteristic reflects the vehicle'"'"'s ability to traverse at least one segment of a path. The method further includes modifying the at least one segment of the base path to satisfy the curvature constraint, if the at least one segment of the base path violates the curvature constraint. At least one segment of an offset path for the vehicle to follow is generated based upon the desired offset distance from the modified at least one segment of the base path.

Claims

1. A computer-implemented method for generating at least one segment of an offset path for a vehicle based on at least one segment of a base path, wherein the at least one segment of the base path is represented by a stored set of data points, the computer-implemented method comprising:

comparing the at least one segment of the base path to a curvature constraint to determine if the at least one segment of the base path violates the curvature constraint, wherein the curvature constraint is based on a characteristic of the vehicle and a desired offset distance from the at least one segment of the base path, and the characteristic reflects the vehicle'"'"'s ability to traverse at least one segment of a path;

modifying the at least one segment of the base path to satisfy the curvature constraint, if the at least one segment of the base path violates the curvature constraint; and

generating at least one segment of an offset path for the vehicle to follow, based upon the desired offset distance from the modified at least one segment of the base path.

2. The computer-implemented method of claim 1, wherein the at least one segment of the offset path is parallel to the modified at least one segment of the base path.

3. The computer-implemented method of claim 1, wherein comparing the at least one segment of the base path to the curvature constraint includes comparing the curvature constraint with a curvature parameter of the at least one segment of the base path to identify violation points, and modifying the at least one segment includes satisfying the curvature constraint based upon the identified violation points.

4. The computer-implemented method of claim 1, wherein generating the at least one segment of the offset path includes interpolation by parametric functions.

5. The computer-implemented method of claim 1, wherein the at least one segment of the base path and the at least one segment of the offset path are interpolated by cubic B-splines.

6. The computer-implemented method of claim 3, wherein the at least one segment of the base path comprises a plurality of at least one smaller segments, and modifying the at least one segment of the base path comprises sequentially modifying the at least one smaller segments containing violation points.

7. The computer-implemented method of claim 3, wherein comparing the curvature constraint with the curvature parameter of at least one segment of the base path comprises comparing a representation of the curvature constraint with the curve of the at least one segment of the base path.

8. The computer-implemented method of claim 7, wherein the representation of the curvature constraint is graphically represented as a disk.

9. The computer-implemented method of claim 8, wherein a radius of the disk is based on a maximum wheel turning angle of the vehicle.

10. The computer-implemented method of claim 1, wherein the characteristic is based on a maximum wheel turning angle of the vehicle.

11. The computer-implemented method of claim 10, wherein the characteristic is also based on a wheel base of the vehicle.

12. The computer-implemented method of claim 8, wherein comparing the disk with the curvature parameter of the at least one segment of the base path further comprises:

positioning the representation at a first violation point of the set of data points of the base path within the at least one segment of the base path;

if any points of the base path are identified within the disk, then repositioning the disk along the path in the backward direction to the previous point of the at least one segment of the base path;

identifying points of the stored set of data points of the at least one segment of the base path within the disk repositioned at the previous point; and

continuing to reposition the disk along the path in the backward direction at other points, until no points of the at least one segment of the base path lie within the disk.

13. The computer-implemented method of claim 12, wherein the disk is repositioned until only two points of the set of data points of the at least one segment of the base path touch the disk, wherein the set of data points of the at least one segment of the base path between the two points is a segment to be modified, and wherein an arc of the disk is defined by the two points of the disk that touch the at least one segment of the base path.

14. The computer-implemented method of claim 13, wherein modifying the at least one segment of the base path to satisfy the curvature constraint comprises:

replacing the segment to be modified by an arc of the disk defined by the two points of the disk that touch the at least one segment of the base path.

15. A computer-readable storage medium encoded with executable instructions for generating at least one segment of an offset path for a vehicle based on at least one segment of a base path, wherein the at least one segment of the base path is stored as a set of data points, the instructions comprising instructions for:

comparing the at least one segment of the base path to a curvature constraint to determine if the at least one segment of the base path violates the curvature constraint, wherein the curvature constraint is based on a characteristic of the vehicle and a desired offset distance from the at least one segment of the base path, and the characteristic reflects the vehicle'"'"'s ability to traverse at least one segment of a path;

modifying the at least one segment of the base path to satisfy the curvature constraint, if the at least one segment of the base path violates the curvature constraint; and

generating at least one segment of an offset path for the vehicle to follow, based upon the desired offset distance from the modified at least one segment of the base path.

16. The computer-readable storage medium of claim 15, wherein the at least one segment of the offset path is parallel to the at least one segment of the modified base path.

17. The computer-readable storage medium of claim 15, wherein the instructions for comparing the at least one segment of the base path to the curvature constraint includes comparing the curvature constraint with a curvature parameter of the at least one segment of the base path to identify violation points, and the instructions for modifying the at least one segment comprises instructions for satisfying the curvature constraint based upon the identified violation points.

18. The computer-readable storage medium of claim 15, wherein the instructions for generating the at least one segment of the offset path includes instructions for interpolation by parametric functions.

19. The computer-readable storage medium of claim 15, wherein the at least one segment of the base path and the at least one segment of the offset path are interpolated by cubic B-splines.

20. The computer-readable storage medium of claim 18, wherein the at least one segment of the base path comprises a plurality of at least one smaller segments, and the instructions for modifying the at least one segment of the base path comprises instructions for sequentially modifying the at least one smaller segments containing violation points.

21. The computer-readable storage medium of claim 17, wherein the instructions for comparing the curvature constraint with the curvature parameter of at least one segment of the base path comprises instructions for comparing a representation of the curvature constraint with the curve of the at least one segment of the base path.

22. The computer-readable storage medium of claim 21, wherein the representation of the curvature constraint is graphically represented as a disk.

23. The computer-readable storage medium of claim 22, wherein a radius of the disk is based on a maximum wheel turning angle of the vehicle.

24. The computer-readable storage medium of claim 15, wherein the characteristic is based on a maximum wheel turning angle of the vehicle.

25. The computer-readable storage medium of claim 24, wherein the characteristic is also based on a wheel base of the vehicle.

26. The computer-readable storage medium of claim 22, wherein the instructions for comparing the disk with the curvature parameter of the at least one segment of the base path further comprises instructions for:

positioning the disk at a first violation point of the set of data points of the base path within the at least one segment of the base path;

if any points of the base path are identified within the disk, then repositioning the disk along the path in the backward direction to the previous point of the at least one segment of the base path;

identifying points of the stored set of data points of the at least one segment of the base path within the disk repositioned at the previous point; and

continuing to reposition the disk along the path in the backward direction at other points, until no points of the at least one segment of the base path lie within the disk.

27. The computer-readable storage medium of claim 26, wherein the disk is repositioned until only two points of the set of data points of the at least one segment of the base path touch the disk, wherein the set of data points of the at least one segment of the base path between the two points is a segment to be modified, and wherein an arc of the disk is defined by the two points of the disk that touch the at least one segment of the base path.

28. The computer-implemented method of claim 27, wherein the instructions for modifying the at least one segment of the base path to satisfy the curvature constraint comprises instructions for:

replacing the segment to be modified by an arc of the disk defined by the two points of the disk that touch the at least one segment of the base path.

29. A system for generating an offset path for a vehicle based on a base path, wherein the at least one segment of the base path is stored as a set of data points, the system comprising:

a memory for storing instructions; and

a processor for executing the instructions, the instructions comprising instructions for;

comparing the at least one segment of the base path to a curvature constraint to determine if the at least one segment of the base path violates the curvature constraint, wherein the curvature constraint is based on a characteristic of the vehicle and a desired offset distance from the at least one segment of the base path, and the characteristic reflects the vehicle'"'"'s ability to traverse at least one segment of a path;

modifying the at least one segment of the base path to satisfy the curvature constraint, if the at least one segment of the base path violates the curvature constraint; and

generating at least one segment of an offset path for the vehicle to follow, based upon the desired offset distance from the modified at least one segment of the base path.

30. The system of claim 29, wherein the system is installed in a vehicle.

31. The system of claim 29, further comprising a transmitter for transmitting the generated at least one segment of the offset path to a ground vehicle.

32. The system of claim 30, further comprising a GPS receiver for receiving GPS data for storing the at least one segment of the base path.

33. The system of claim 30, further comprising control logic connected to the processor for communicating with a steering control system of the vehicle.