Path planner and method for planning a path plan having a spiral component

• US 7,228,214 B2
• Filed: 01/25/2005
• Issued: 06/05/2007
• Est. Priority Date: 03/31/2003
• Status: Expired due to Term

• Current Assignee: Deere & Company
• Original Assignee: Deere & Company
• Inventors: Hansen, Shane Lynn, Gray, Sarah Ann, Flann, Nicholas Simon
• Primary Examiner(s): Tran; Dalena
• Application Number:
  US11/042,561
• Publication Number:
  US 20050197757A1
• Time in Patent Office: 861 Days
• Field of Search: 701/50, 701/41, 701/23, 701/26, 701/207, 701/122, 701/200, 701/214, 701/224, 180/168, 172/3, 172/5, 172/26, 56/102.F, 56/101, 56/102.D, 56/102.H
• US Class Current: 701/50
• CPC Class Codes: A01B 69/008 automatic
• CPC Class Codes: G05D 1/0219 ensuring the processing of the whole working surface
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0255 using acoustic signals, e.g. ultra-sonic singals sonar systems designed for anti-collision purposes G01S15/93
• 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

Abstract

A method and path planner for planning a path of a vehicle comprising a perimeter training module for identifying a border of a region associated with a work area. A definer for defining a reference row having a reference path that tracks at least a majority of the border. A generator generates tracking rows that track the reference row. The tracking rows comprise at least one inner tracking row and an outer tracking row. Each inner tracking row having at least one inner curve with a lesser radius than an outer tracking row having a corresponding outer curve with a greater radius.

Claims

1. A method for planning a path of a vehicle, the method comprising:

identifying a border of a region associated with a work area;

defining a reference row having a reference path that tracks at least a majority of the border;

generating tracking rows that track the reference row, the tracking rows comprising at least one inner tracking row and an outer tracking row, each inner tracking row having at least one inner curve with a lesser radius than an outer curve of an outer tracking row to form a path plan having a spiral component; and

detecting a pinch region associated with the path plan, the pinch region referring to a narrow region or bottleneck of the work area in which a spiral path is constrained or prevented from realization.

2. The method according to claim 1 wherein the border comprises an outer border and wherein the generating of tracking rows tracks inward from the reference row.

3. The method according to claim 1 wherein the border comprises an inner border about an obstacle in the work area and wherein the generating of tracking rows tracks outward from the reference row.

4. The method according to claim 1 wherein the identifying of the border of the region is associated with at least one of a generally circular portion and a generally semi-circular portion, and wherein the generating comprises generating tracking rows to form a set of arcs inward from at least one of the generally circular portion and generally semi-circular portion.

5. The method according to claim 4 wherein the radius of each arc is defined in accordance with the following equation:

Arc radius=a×

theta, where a is the initial radius or outer radius and wherein theta is a variable that reduces the initial radius as a function of angular displacement along a path and inward toward a central area of the region.

6. The method according to claim 1 wherein the border is generally circular and wherein the tracking rows form a spiral with a varying radius that decreases toward an interior or center of the region.

7. The method according to claim 1 wherein the identifying of the border comprises identifying a corner associated with the region;

and further comprising;

establishing an additional path extending diagonally between the identified corner and a central area of the region.

8. The method according to claim 1 wherein the identifying of the border comprises identifying a corner associated with the region;

and further comprising;

establishing a virtual boundary extending diagonally from the corner to an interior region of the region; and

planning one or more flip turns associated between tracking rows along the virtual boundary.

9. The method according to claim 1 further comprising:

detecting the pinch region in a tracking row associated with a loop in a path plan; and

defining one or more cross-over rows at the pinch region over which the vehicle may travel multiple times to service areas on each side of the pinch region in accordance with a path plan having a spiral component.

10. The method according to claim 1 further comprising:

detecting the pinch region in a tracking row associated with a loop in a path plan; and

defining a first coverage area on a first side of the pinch region and a second coverage area on a second side of the pinch region.

11. The method according to claim 10 further comprising:

applying a first spiral path plan to the first side and a second spiral path plan to a second side.

12. The method according to claim 1 wherein the generating comprises:

forming a series of nested loops spaced apart from one another by a generally uniform spacing, at least one of the nested loops tracking the reference row; and

linking one nested loop to another nested loop to interconnect the nested loops for the path plan having a spiral component.

13. The method according to claim 12 wherein the linking is accomplished by moving transversely inward to the nested loops toward a central area of the region.

14. The method according to claim 12 wherein the linking is accomplished by moving transversely outward to the nested loops away from a central area of the region.

15. The method according to claim 12 further comprising:

identifying a corner associated with the region of the work area; and

wherein the linking of nested loops is accomplished by the vehicle'"'"'s traverse movement along a diagonal formed between the central area and the identified corner.

16. The method according to claim 1 further comprising:

identifying the presence of one or more obstacle areas in the region; and

defining flip turns in the tracking rows associated with a zone boundary of one or more obstacle clearance zones to interconnect different tracking rows, while maintaining a desired clearance from a corresponding obstacle.

17. The method according to claim 1 further comprising:

determining a first figure of merit for a generally linear coverage path for the region, the first figure of merit being based on at least one of total length, elapsed total time, and a total energy consumption of a vehicle to execute the generally linear coverage path;

determining a second figure of merit for a generally spiral coverage path for the region, the second figure of merit being based on at least one of total length, elapsed total time, and a total energy consumption of a vehicle to execute the generally spiral coverage path; and

determining whether to select the generally linear coverage path or the spiral coverage path based on the first figure of merit and the second figure of merit, the selection based on at least one of the shortest total length, the shortest elapsed total time, and the lowest total energy consumption.

18. A path planner for planning a path of a vehicle comprising:

a perimeter training module for identifying a border of a region associated with a work area;

a definer for defining a reference row having a reference path that tracks at least a majority of the border;

a generator for generating tracking rows that tracks the reference row, the tracking rows comprising at least one inner tracking row and an outer tracking row, each inner tracking row having at least one inner curve with a lesser radius than an outer tracking row having a corresponding outer curve with a greater radius; and

a detector for detecting a pinch region associated with the path plan, the pinch region referring to a narrow region or bottleneck of the work area in which a spiral path is constrained or prevented from realization.

19. The path planner according to claim 18 wherein the border comprises an outer border and wherein the generating of tracking rows tracks inward from the reference row.

20. The path planner according to claim 18 wherein the border comprises an inner border about an obstacle in the work area and wherein the generating of tracking rows tracks outward from the reference row.

21. The path planner according to claim 18 wherein a data processor detects the presence of at least one of a generally circular portion and a generally semi-circular portion of the border, and wherein the generator comprises generating tracking rows to form a set of arcs inward from at least one of the generally circular portion and generally semi-circular portion.

22. The path planner according to claim 21 wherein the radius of each arc is defined in accordance with the following equation:

Arc radius=a×

theta, where a is the initial radius or outer radius and wherein theta is a variable that reduces the initial radius as a function of angular displacement along a path and inward toward a central area of the region.

23. The path planner according to claim 18 wherein the border is generally circular and wherein the tracking rows form a spiral with a varying radius that decreases toward an interior or center of the region.

24. The path planner according to claim 18 wherein a data processor supports identification of a comer of the border associated with the region;

and wherein the generator establishes an additional path extending diagonally between the identified corner and a central area of the region.

25. The path planner according to claim 18 wherein a data processor supports the identification of a corner of the border associated with the region;

and wherein the generator establishes a virtual boundary extending diagonally from the corner to an interior region of the region,

an interconnection module planning one or more flip turns between tracking rows along the virtual boundary.

26. The path planner according to claim 18 further comprises:

an interconnection module defining one or more cross-over rows at the pinch region over which the vehicle may travel multiple times to service areas on each side of the pinch region in accordance with a path plan having a spiral component.

27. The path planner according to claim 18 further comprises:

a definer for defining a first coverage area on a first side of the pinch region and a second coverage area on a second side of the pinch region.

28. The path planner according to claim 18 further comprising:

a data processor for applying a first spiral path plan to the first side and a second spiral path plan to a second side.

29. The path planner according to claim 18 wherein:

a generator is arranged to form a series of nested loops spaced apart from one another by a generally uniform spacing, at least one of the nested loops tracking the reference row;

an interconnection module for linking one nested loop to another nested loop to interconnect the nested loops.

30. The path planner according to claim 18 further comprising:

a safeguarding system for identifying the presence of one or more obstacle. areas in the region; and

a spiral region filling module for defining turns in the tracking rows associated with a zone boundary of one or more obstacle clearance zones to interconnect different tracking rows.

31. The path planner according to claim 18 further comprising:

a linear path estimator and a turn estimator for determining a first figure of merit for a generally linear coverage path for the region, the first figure of merit being based on at least one of total length, elapsed total time, and a total energy consumption of a vehicle to execute the generally linear coverage path;

a spiral path estimator and the turn estimator for determining a second figure of merit for a generally spiral coverage path for the region, the second figure of merit being based on at least one of total length, elapsed total time, and a total energy consumption of a vehicle to execute the generally spiral coverage path; and

a data processor for determining whether to select the generally linear coverage path or the spiral coverage path based on the first figure of merit and the second figure of merit, the selection based on at least one of the shortest total length, the shortest elapsed total time, and the lowest total energy consumption.