Method and system for determining an efficient vehicle path

• US 6,934,615 B2
• Filed: 05/28/2003
• Issued: 08/23/2005
• 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): Zanelli, Michael J.
• Assistant Examiner(s): Gibson, Eric M.
• Application Number:
  US10/446,345
• Publication Number:
  US 20040193349A1
• Time in Patent Office: 818 Days
• Field of Search: 701/50, 701/202, 701/209, 56/102.A, 172/2
• 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/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

A system and method for determining a path plan for a vehicle includes organizing a work area into partition areas based on at least one of an obstacle, a concavity, and an exclusion area associated with a work area. An external cost indicator is established for indicating the economic cost corresponding to the vehicle traversing from one partition area to another partition area for each possible permutation or potential combination of successive partition areas. The established external cost indicators are searched to determine a preferential order of traversing the partition areas. A preferential path plan is determined based on the internal path plan of each partition and a transfer path plan of transferring from a prior partition to a latter partition until each partition in the work area is traversed.

Claims

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

organizing a work area into partition areas based on at least one of an obstacle, a concavity, and an exclusion area associated with the work area;

establishing an external cost indicator for indicating an economic cost corresponding to the vehicle traversing from one partition area to another partition area for each possible permutation or potential combination of successive partition areas;

searching the established external cost indicators to determine a preferential order of traversing the partition areas, each of the external cost indicators being based on the distance of a transfer path between a candidate prior partition and a candidate subsequent partition; and

determining a preferential path plan based on the internal path plan of each partition and an external path plan of transferring from prior partition to a latter partition until each partition in the work area is traversed.

2. The method according to claim 1 wherein each of the partition areas comprises a region selected from the group consisting of a generally triangular region, a generally trapezoidal region, and a generally rectangular region.

3. The method according to claim 1 wherein each partition area is defined by a first boundary intersecting with adjacent path rows and by a second boundary intersecting with said adjacent path rows.

4. The method according to claim 1 wherein the searching finds the preferential order based on a substantially global lowest cost of traversing candidate external path plans and candidate internal path plans, the global lowest cost defined as a function of a remaining distance of remaining paths plus a cost of traversed paths traversed so far.

5. The method according to claim 1 wherein the searching finds the preferential order based on a substantially local lowest cost of traversing candidate transfer path plans and candidate internal path plans, the local lowest cost estimated to be less than or equal to children local costs derived from parameters associated with the local lowest cost.

6. The method according to claim 1 wherein the internal path plan comprises a series of generally parallel rows arranged at a defined angle with respect to a target axis, the generally parallel rows being interconnected by at least one of a loop and an interconnection segment.

7. The method according to claim 1 wherein the searching comprises applying an A* search algorithm to determine the preferential order within the preferential path plan.

8. The method according to claim 1 wherein the searching comprises applying a bounded A* search algorithm to determine the preferential order within the preferential path plan.

9. The method according to claim 1 wherein the searching comprises applying a minimum set filter to limit a number of candidate path plans to be considered for selection as the preferential path plan.

10. The method according to claim 1 wherein the searching comprises applying an unreachable filter to limit the detection of one or more isolated partitions that are difficult to access to limit a number of candidate path plans to be considered for selection as the preferential path plan.

11. The method according to claim 10 further comprising:

redefining the organized partition areas to eliminate any isolated partitions;

searching the redefined partition areas to determine the preferential path plan.

12. A system of determining a path plan for a vehicle, the system comprising:

an organizer for organizing a work area into partition areas based on at least one of an obstacle, a concavity, and an exclusion area associated with a work area;

a cost estimator for establishing an external cost indicator for indicating an external economic cost corresponding to the vehicle traversing from one partition area to another partition area for each possible permutation or potential combination of successive partition areas;

a search engine for searching the established eternal cost indicators to determine a preferential order of traversing the partition areas, each of the external cost indicators being based on the distance of a transfer path between a candidate prior partition and a candidate subsequent partition;

a path determination module for determining a preferential path plan based on the internal path plan of each partition and an external path plan of transferring from a prior partition to a latter partition until each partition in the work area is traversed.

13. The system according to claim 12 wherein each of the partition areas comprises a region selected from the group consisting a generally triangular region, a generally trapezoidal region, and a generally rectangular region.

14. The system according to claim 12 wherein each partition area is defined by a first boundary intersecting with adjacent path rows and by a second boundary intersecting with said adjacent path rows.

15. The system according to claim 12 wherein the search engine is arranged to find a substantially global lowest cost of traversing candidate external path plans and candidate internal path plans;

the global lowest cost defined as a function of a remaining distance of remaining paths plus a cost of traversed paths traversed so far;

the substantially global lowest cost being associated with a corresponding order of partition execution as the preferential order.

16. The system according to claim 12 wherein the search engine is arranged to find a substantially local lowest cost of traversing candidate transfer path plans and candidate internal path plans;

the local lowest cost estimated to be less than or equal to children local costs derived from parameters associated with the local lowest cost;

the substantially local lowest cost being associated with a corresponding order of partition execution as the preferential order.

17. The system according to claim 12 wherein the internal path plan comprises a series of generally parallel rows arranged at an defined angle with respect to a target axis, the generally parallel rows being interconnected by at least one of a loop and an interconnection segment.

18. The system according to claim 12 wherein the search engine applies an A* search algorithm to determine the preferential path plan.

19. The system according to claim 12 wherein the search engine applies a bounded A* search algorithm to determine the preferential path plan.

20. The system according to claim 12 wherein the search engine applies a minimum set filter to limit a number of candidate path plans to be considered for selection as the preferential path plan.

21. The system according to claim 12 wherein the search engine applies an unreachable filter to limit detection of one or more isolated partitions that are difficult to access to limit a number of candidate path plans to be considered for selection as the preferential path plan.

22. The system according to claim 21 wherein the organizer redefines the partition areas to eliminate any isolated partitions;

and wherein the search engine searches the redefined partition areas to determine the preferential path plan.

23. A method of determining a path plan for vehicle, the method comprising:

organizing a work area into partition areas comprising regions containing a set of rows for traversal by a vehicle, each partition area being positioned based on a location of at least one of an obstacle, a concavity, and an exclusion area associated with the work area;

establishing an external cost indicator for indicating an economic cost corresponding to the vehicle traversing from one partition area to another partition area for each possible permutation or potential combination of successive partition areas;

searching the established external cost indicators to determine a preferential order of traversing the partition areas; and

determining a preferential path plan based on the internal path plan of each partition and an external path plan of transferring from a prior partition to a latter partition until each partition in the work area is traversed.

24. The method according to claim 23 further comprising determining boundaries of each partition comprising a first row and a second row satisfying at least the following requirements:

(a) a first shape of an obstacle touched by a top or end of the first row being the same first shape touched by the top or end of the second row; and

(b) a second shape of an obstacle touched by a bottom or opposite end of the first row being the same second shape touched by the bottom or opposite end of the second row.

25. The method according to claim 23 wherein each of the partition areas comprises a region selected from the group consisting of a generally triangular region, a generally trapezoidal region, and a generally rectangular region.

26. The method according to claim 23 wherein each partition area is defined by a first boundary intersecting with adjacent path rows and by a second boundary intersecting with said adjacent path rows.

27. The method according to claim 23 wherein each of the external cost indicators is based on the distance of a transfer path between a candidate prior partition and a candidate subsequent partition.

28. The method according to claim 23 wherein the searching finds the preferential order based on a substantially global lowest cost of traversing candidate external path plans and candidate, internal path plans, the global lowest cost defined as a function of a remaining distance of remaining paths plus a cost of traversed paths traversed so far.

29. The method according to claim 23 wherein the searching finds the preferential order based on a substantially local lowest cost of traversing candidate transfer path plans and candidate internal path plans, the local lowest cost estimated to be less than or equal to children focal costa derived from parameters associated with the local lowest cost.

30. The method according to claim 23 wherein the internal path plan comprises a series of generally parallel rows arranged at a defined angle with respect to a target axis, the generally parallel rows being interconnected by at least one of a loop and an interconnection segment.

31. The method according to claim 23 wherein the searching comprises applying an A* search algorithm to determine the preferential order within the preferential path plan.

32. The method according to claim 23 wherein the searching comprises applying a bounded A* search algorithm to determine the preferential order within the preferential path plan.

33. The method according to claim 23 wherein the searching comprises applying a minimum set filter to limit a number of candidate path plans to be considered for selection as the preferential path plan.

34. The method according to claim 23 wherein the searching comprises applying an unreachable filter to limit the detection of one or more isolated partitions that are difficult to access to limit a number of candidate path plans to be considered for selection as the preferential path plan.

35. The method according to claim 34 further comprising:

redefining the organized partition areas to eliminate any isolated partitions;

searching the redefined partition areas to determine the preferential path plan.