Method and apparatus for determining a path to be traversed by a mobile machine

• US 6,088,644 A
• Filed: 08/12/1998
• Issued: 07/11/2000
• Est. Priority Date: 08/12/1998
• Status: Expired due to Fees

• Current Assignee: Caterpillar Incorporated
• Original Assignee: Caterpillar Incorporated
• Inventors: McGee, Robert J., Brandt, Everett G., Rockwood, Brian D.
• Primary Examiner(s): Chin, Gary
• Application Number:
  US09/133,000
• Time in Patent Office: 699 Days
• Field of Search: 701/50, 701/207, 701/209, 342/357.01, 342/357.17, 340/988, 340/990, 340/995, 172/4.5, 172/9, 37/348
• US Class Current: 701/50
• CPC Class Codes: E01C 19/004 Devices for guiding or controlling the machines along a predetermined path for graders or bulldozers E02F3/841; for other soil-shifting machines E02F9/2045
• CPC Class Codes: E02F 3/842 using electromagnetic, optical or photoelectric beams, e.g. laser beams
• CPC Class Codes: E02F 3/847 using electromagnetic, optical or acoustic beams to determine the blade position, e.g. laser beams
• CPC Class Codes: E02F 9/2045 Guiding machines along a predetermined path for graders E02F3/841; machines for construction of roads E01C19/004
• CPC Class Codes: G05D 1/0236 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0257 using a radar radar systems designed for anti-collision purposes between land vehicles or between land vehicle and fixed obstacles G01S13/931
• 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/0278 using satellite positioning signals, e.g. GPS

Abstract

In one embodiment of the present invention, an apparatus and method for determining a path or series of paths at a work site for a mobile machine capable of operating autonomously or semi-autonomously is provided. The present invention determines a series of rows that are substantially parallel to the machine'"'"'s heading. The width of the rows is based on the width of the path worked by one or more of the machine'"'"'s work implements. The work site is bounded by three or more corner points and the perimeter of the work site is defined by boundary lines connecting the corner points. A first line substantially perpendicular to the machine'"'"'s heading is calculated starting at an initial corner point and ending at a terminal point along the line having a distance approximately equal to the width of the path. A second line parallel to the machine'"'"'s heading and passing through the terminal point is determined. The points of intersection of the second line with the boundary lines are calculated and stored as end points of a first path. Endpoints of successive paths are found in a similar manner by incrementing the distance along the parallel line by the width of the work path.

Claims

1. A method for determining a path for a mobile machine to follow in a work area bounded by a perimeter having a plurality of corner points, the method comprising the steps of:

(a) determining the heading of the path based on the heading of the mobile machine;

(b) calculating a vector substantially perpendicular to the heading of the mobile machine;

(c) determining the distance between adjacent paths based on the width of a work implement on the mobile machine; and

(d) determining a start point and an end point of the path based on the location of the corner points, the perimeter of the work area, and the width of the work implement.

2. The method, as set forth in claim 1, wherein the vector has an origin at a corner point adjacent one side of the mobile machine and a length proportional to the width of the work implement.

3. The method, as set forth in claim 2, wherein the step (d) further comprises determining a line through the terminal point of the vector, the line being substantially parallel to the heading of the mobile machine and intersecting two sides of the perimeter, one point of the intersecting being the start point of the path and the other point of the intersecting being the end point of the path.

4. A method for determining a series of paths for a mobile machine to follow in a work area, the work area being bounded by a multi-sided perimeter having a plurality of corner points, the method comprising the steps of:

(a) determining the heading of the paths based on the heading of the mobile machine;

(b) determining the width of a path based on the width of a work implement on the mobile machine;

(c) calculating a first vector substantially perpendicular to the heading of the mobile machine, the terminal point of the first vector being at a distance proportional to the width of the path and the origin of the first vector being at the corner point adjacent the left side of the mobile machine having the furthest distance from the mobile machine;

(d) determining a start point and an end point for the path based on the location of the corner points, the perimeter of the work area, and the first vector;

(e) incrementing the terminal point of the first vector perpendicular to the heading of the mobile machine by the distance to an adjacent path in the series of paths;

(f) calculating a second vector substantially parallel to the heading of the mobile machine, the second vector having an origin at the terminal point of the first vector;

(g) calculating a third vector, the origin of the third vector being at the corner adjacent the furthest corner point in the clockwise direction and the terminal point of the third vector being at the terminal point of the first vector;

(h) calculating the vector cross product of the second and the third vectors;

(i) using the sign of the cross product to determine the side of the perimeter to use to calculate the start point and the end point of the next path;

(j) determining a start point and an end point for the next path based on the terminal point of the first vector and the perimeter of the work area;

(k) repeating steps (e) through (j) until the next path is outside the perimeter of the work area.

5. The method, as set forth in claim 4, wherein the step (d) further comprises determining a line through the terminal point of the first vector, the line being substantially parallel to the heading of the mobile machine and intersecting two sides of the perimeter, one point of the intersecting being the start point of the path and the other point of the intersecting being the end point of the path.

6. The method, as set forth in claim 4, wherein the step (j) further comprises determining a line through the terminal point of the first vector, the line being substantially parallel to the heading of the mobile machine and intersecting two sides of the perimeter, one point of the intersecting being the start point of the next path and the other point of the intersecting being the end point of the next path.

7. An apparatus for determining a path for a mobile machine to follow in a work area bounded by a perimeter having a plurality of corner points, the apparatus comprising:

a positioning system for providing position data for the mobile machine;

a data processor in communication with the positioning system, the data processor being operable to determine the heading of the mobile machine based on said position data from the positioning system;

the data processor being further operable to determine the heading of the path based on the heading of the mobile machine;

the data processor being further operable to determine the width of the path based on the width of a work implement on the mobile machine; and

the data processor being further operable to determine a start point and an end point of the path based on the location of the corner points, the perimeter of the work area, and the width of the work implement.

8. The apparatus, as set forth in claim 7, wherein the data processor is further operable to determine the start point and the end point of the path by calculating a vector substantially perpendicular to the heading of the mobile machine, the vector having a length proportional to the width of the path and an origin at one of the corner points adjacent one side of the mobile machine.

9. The apparatus, as set forth in claim 8, wherein the data processor is further operable to determine a line through the terminal point of the vector, the line being substantially parallel to the heading of the mobile machine and intersecting two sides of the perimeter, one point of the intersecting being the start point of the path and the other point of the intersecting being the end point of the path.

10. An apparatus for determining a series of paths for a mobile machine to follow in a work area, the work area being bounded by a multi-sided perimeter having a plurality of corner points, the apparatus comprising:

a data processor in communication with a positioning system, the positioning system providing data on the position, speed, and heading of the mobile machine, the data processor being operable to determine the heading of the paths based on the heading of the mobile machine;

the data processor being further operable to determine the width of a path based on the width of a work implement on the mobile machine;

the data processor being further operable to calculate a first vector substantially perpendicular to the heading of the mobile machine, the terminal point of the first vector being at a distance proportional to the width of the path and the origin of the first vector being at the corner point adjacent the left side of the mobile machine having the furthest distance from the mobile machine;

the data processor being further operable to determine a start point and an end point for the path based on the location of the corner points, the perimeter of the work area, and the first vector;

the data processor being further operable to repeatedly increment the terminal point of the first vector perpendicular to the heading of the mobile machine by the width of a next path in the series of paths, to calculate a second vector substantially parallel to the heading of the mobile machine, the second vector having an origin at the terminal point of the first vector, to calculate a third vector, the origin of the third vector being at the corner adjacent the furthest corner point in the clockwise direction and the terminal point of the third vector being at the terminal point of the first vector, to calculate the vector cross product of the second and the third vectors, to determine the side of the perimeter to use to calculate the start point and the end point of the next path using the sign of the cross product, to determine a start point and an end point for the next path based on the terminal point of the first vector and the perimeter of the work area, until the next path is outside the perimeter of the work area.

11. The apparatus, as set forth in claim 10, wherein the data processor is further operable to determine a line through the terminal point of the first vector, the line being substantially parallel to the heading of the mobile machine and intersecting two sides of the perimeter, one point of the intersecting being the start point of the path and the other point of the intersecting being the end point of the path.

12. The apparatus, as set forth in claim 10, wherein the data processor is further operable to determining a line through the terminal point of the first vector, the line being substantially parallel to the heading of the mobile machine and intersecting two sides of the perimeter, one point of the intersecting being the start point of the next path and the other point of the intersecting being the end point of the next path.