Path planner and a method for planning a path of a work vehicle

• US 7,010,425 B2
• Filed: 03/31/2003
• Issued: 03/07/2006
• 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/403,681
• Publication Number:
  US 20050075785A1
• Time in Patent Office: 1,072 Days
• Field of Search: 701/23, 701/25, 701/26, 701/50, 701/202, 701/209, 56/102.A, 172/2
• US Class Current: 701/202
• 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 method for planning a path for a vehicle comprises creating a travel row transparency over a mapped area. The travel row transparency comprises one or more travel rows are split into travel row sections defined by intersecting the travel row with a map object (e.g., a boundary of mapped area). Partition nodes are generated from the travel row sections. The partition nodes or partition edges are linked together to form a potential drivable path consistent with user input and vehicular constrains. An efficient ordering of the partition nodes are determined consistent with the user input. A path is generated by looping through the ordered partition nodes in the determined efficient order.

Claims

1. A method of planning a path comprising:

creating a travel row transparency over a mapped area, the travel row transparency comprising a representation of a group of generally parallel travel rows;

splitting the travel rows into travel row sections defined by intersecting the travel rows of the travel row transparency with a map object or boundary;

generating partition nodes associated with ends of the travel row sections;

linking the partition nodes together to build at least one of a drivable path portion and a visibility graph;

determining an efficient order of the partition nodes consistent with at least one of a user-definable preferential rule and a pattern parameter for imparting a desired aesthetic appearance to at least a portion of the mapped area; and

generating a preferential path by looping through or interconnecting the ordered partition nodes in the determined efficient order.

2. The method according to claim 1 further comprising defining a baseball stadium as a map object in the mapped area by obtaining at least one of local coordinates of an outfield, local coordinates of a right foul area, and local coordinates of a left foul area.

3. The method according to claim 1 wherein the efficient order is determined based on adherence to a set of path rules, including that path is drivable by the vehicle based on vehicular constraints, including at least vehicle width, minimum vehicular turning radius, initial vehicular position, and initial vehicular heading.

4. The method according to claim 1 wherein the efficient order is determined based on adherence to a set of path rules, including compliance with a user-definable pattern parameter as the pattern parameter, the user-definable pattern parameter selected from the group consisting of traversing adjacent travel rows in opposite directions, traversing intra-group rows of travel rows in the same direction and inter-group travel rows in opposite directions, back-and-forth straight sweep of the travel rows, row direction rules, parallel tracking of target contour, and parallel tracking of a target line.

5. The method according to claim 1 wherein the creating comprises generating a series of straight parallel lines representing travel rows of the vehicle in a specified direction and generally covering a desired portion of the mapped area.

6. The method according to claim 1 wherein the creating comprises:

defining a target contour superimposed over a map object in the mapped area; and

forming parallel segments with respect to the target contour over the mapped area to produce the transparency, the parallel segments and the target contour extending beyond the map object.

7. The method according to claim 1 wherein the splitting comprises dividing travel rows of the travel row transparency into travel row sections associated with one or more intersections of a respective travel row with a corresponding map object.

8. The method according to claim 7 wherein a first and an Nth section of a travel row extend past the map object, where N equals any odd whole number equal to or greater than three;

each even section of the travel row indicating a section that the vehicle must track starting with the second section on to the Mth section of the travel row, where M equals N minus 1.

9. The method according to claim 1 wherein the generating the partition nodes comprise generating partition nodes from travel row sections;

where two sections are in the same partition node if a starting point and end points are adjacent to each other, if there are no intervening travel rows between the two, and if their start and end points lie on the same map object.

10. The method according to claim 1 wherein the linking comprises connecting partition nodes by an edge as the drivable path portion.

11. The method according to claim 1 wherein the determining comprises using a bounded search algorithm to determine an efficient order of the partition nodes.

12. The method according to claim 1 wherein the generating comprises connecting a series of drivable path portions via curved path segments consistent with the determined efficient order from a first partition node to a last partition node.

13. The method according to claim 1 wherein each of the partition nodes is defined at an intersection or near adjacent termination points of two travel row sections if a starting point and an end point of the adjacent travel row sections are adjacent to each other, and if the starting point and the end points of the adjacent travel row sections lie on the same map object or boundary.

14. The method according to claim 1 wherein the visibility graph comprises at least one graph of the partition nodes and edges that represents possible solutions for a preferential path of the vehicle that covers the mapped area or a desired portion thereof.

15. The method according to claim 1 wherein determining of the efficient order is based on at least one of mapped area data, defined pattern parameters, established vehicular constraints, and established user-definable preferential rules.

16. The method according to claim 1 wherein determining of the efficient order comprises determining the efficient order of the partition nodes consistent with tracing travel row sections within the map object.

17. The method according to claim 1 wherein determining the efficient order comprises minimizing cumulative total distance to be traveled by a vehicle to cover a desired portion of the mapped area.

18. The method according to claim 1 wherein determining the efficient order comprises minimizing the cumulative total distance of a traveled route of a vehicle to fully cover a desired portion of the mapped area without significant overlap of the traveled route.

19. The method according to claim 1 wherein the desired aesthetic appearance comprises a striped visual appearance of a grass field, the grass field comprising the portion of the mapped area, and the at least one user-definable preferential rule authorizing respective directions of travel of adjacent groups travel rows for a mowing of the grass field to produce the striped visual appearance for the generated preferential path.

20. The method according to claim 19 wherein the grass field is selected from the group consisting of a baseball field, a baseball stadium, and a baseball outfield, an arena, and sports stadium.

21. The method according to claim 19 wherein the at least one user-definable preferential rule prohibits turns on a defined portion of the grass field for the generated preferential path.

22. A path planner for planning a path, the system comprising:

a creator for creating a travel row transparency over a mapped area, the travel row transparency comprising a representation of a group of generally parallel travel rows;

a splitter for splitting the travel rows into travel row sections defined by intersecting the travel rows of the travel transparency with a map object or boundary;

a generator for generating partition nodes associated with ends of the travel row sections, each partition node defined by a respective node identifier;

a data processor for determining an efficient order of the partition nodes based upon the mapped area, defined pattern parameters, established vehicular constraints, and established user-definable preferential rules and for generating a planned path by looping through or interconnecting the ordered partition nodes in the determined efficient order consistent with at least one of the user-definable preferential rules and the pattern parameters for imparting a desired aesthetic appearance to at least a portion of the mapped area.

23. The path planner according to claim 22 wherein the mapped area comprises a baseball stadium defined by at least one of local coordinates of an outfield, local coordinates of a right foul area, and local coordinates of a left foul area.

24. The path planner according to claim 22 wherein the data processor determines the efficient order based on vehicular constraints, including at least vehicle width, minimum vehicular turning radius, initial vehicular position, and initial vehicular heading.

25. The path planner according to claim 22 wherein the data processor determines the efficient order based on adherence to a set of path rules, including compliance with a user-definable pattern parameter as one of the pattern parameters, the user-definable pattern parameter selected from the group consisting of traversing adjacent travel rows in opposite directions, traversing intra-group rows of travel rows in the same direction and inter-group travel rows in opposite directions, back-and-forth straight sweep of the travel rows, row direction rules, parallel tracking of target contour, and parallel tracking of a target line.

26. The path planner according to claim 22 wherein the creator generates a series of straight parallel lines representing travel rows of the vehicle in a specified direction and generally covering the mapped area.

27. The path planner according to claim 22 wherein the desired aesthetic appearance comprises a striped visual appearance of a grass field, the grass field comprising the portion of the mapped area, and the at least one user-definable preferential rule authorizing respective directions of travel of adjacent groups travel rows for a mowing of the grass field to produce the striped visual appearance for the generated preferential path.

28. The path planner according to claim 27 wherein the grass field is selected from the group consisting of a baseball field, a baseball stadium, and a baseball outfield, an arena, and sports stadium.

29. A method of planning a path, the method comprising:

defining a group of travel row sections being generally parallel to one another and spaced apart from one another in a mapped area, each travel row section having ends or partition nodes associated with a map object or boundary;

determining an efficient order for a vehicle to traverse the partition nodes such that the associated travel row sections are traversed consistent with at least one of a user-definable preferential rule and a pattern parameter for imparting a desired aesthetic appearance to at least a portion of the mapped area; and

generating a preferential path by looping through or interconnecting the ordered partition nodes in the determined efficient order.