Point-to-point path planning

• US 7,079,943 B2
• Filed: 01/25/2005
• Issued: 07/18/2006
• Est. Priority Date: 10/07/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): Chin, Gary
• Application Number:
  US11/042,636
• Publication Number:
  US 20050192749A1
• Time in Patent Office: 539 Days
• Field of Search: 701/23, 701/25, 701/50, 701/200, 701/202, 701/209, 701/210, 340/995.19, 340/995.21, 172/4.5
• US Class Current: 701/202
• CPC Class Codes: A01B 69/008 automatic
• CPC Class Codes: B60K 6/48 Parallel type
• CPC Class Codes: B60W 2510/244 Charge state
• CPC Class Codes: B60W 2520/10 Longitudinal speed
• CPC Class Codes: B60W 2556/50 of positioning data, e.g. GPS [Global Positioning System] data
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: Y02T 10/62 Hybrid vehicles

Abstract

A path planner and a method for determining a path for a vehicle comprises defining a starting point for the vehicle. A termination point is defined. An obstacle detector detects one or more obstacles in a work area between the starting point and the termination point. A boundary zone is defined about each corresponding obstacle. Candidate paths are identified between the starting point and the termination point. Each candidate path only intersects each boundary zone once for each corresponding obstacle. An economic cost is estimated for traversing each candidate path or a portion thereof between the starting point and the termination point. A preferential path is selected from the identified candidate paths based on the preferential path being associated with a lowest estimated economic cost.

Claims

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

defining a starting point for the vehicle;

defining a termination point for the vehicle;

detecting two or more obstacles in a work area between the starting point and the termination point;

defining an obstacle clearance zone about each corresponding obstacle;

identifying candidate paths between the starting point and the termination point, each candidate path only intersecting each obstacle clearance zone a maximum number of times for each corresponding obstacle;

estimating an economic cost for traversing each candidate path or a portion thereof between the starting point and the termination point; and

selecting a preferential path from the identified candidate paths based on the preferential path being associated with a lowest estimated economic cost.

2. The method according to claim 1, wherein the defining of the starting point of the vehicle comprises defining the starting point and heading of the vehicle;

and wherein the defining the termination point comprises defining the termination point and heading for the vehicle.

3. The method according to claim 1, wherein the identified candidate path comprises a path from the starting point to the termination point.

4. The method according to claim 1 wherein the identified candidate path comprises a path from the starting point to an outer boundary of the obstacle clearance zone about a corresponding obstacle.

5. The method according to claim 4 wherein the identified candidate path comprises a path segment that is coextensive with a portion of the outer boundary of the obstacle clearance zone.

6. The method according to claim 1 wherein the identified candidate path comprises first a path segment from the starting point to a first obstacle clearance zone about a first corresponding obstacle and a second path segment interconnected to the first path segment, the second path extending from the first obstacle clearance zone to a second obstacle clearance zone about a second corresponding obstacle.

7. The method according to claim 1 wherein the identified candidate path comprises a path segment from a first outer boundary associated with an obstacle clearance zone of a first obstacle to a second outer boundary associated with an obstacle clearance zone of a second obstacle.

8. The method according to claim 7 wherein nodes or vertices of the candidate paths are determined by forming tangential interconnections with respect to the first outer boundary and the second outer boundary.

9. The method according to claim 1 wherein the selecting comprises searching of the candidate paths or portions of candidate paths in accordance with at least one of the A* search algorithm and the bounded A* search algorithm.

10. The method according to claim 1 wherein the selecting comprises searching of the candidate paths or portions of candidate paths after first discarding candidate paths or path segments that exceed a maximum number of permitted touches with respect to at least one of the obstacle clearance zone, an outer boundary of an obstacle clearance zone, a boundary clearance zone, and an outside border shape of a work area.

11. The method according to claim 1 wherein an outer boundary of an obstacle is spaced apart from the obstacle such that the vehicle has a physical clearance between the vehicle and the obstacle if the vehicle follows a path segment that is coextensive with the outer boundary.

12. The method according to claim 1 wherein an outer boundary of the obstacle clearance zone comprises a generally elliptical or generally circular shape.

13. The method according to claim 1 wherein an outer boundary of the obstacle clearance zone comprises a generally rectangular shape to reduce computational resources.

14. The method according to claim 1 wherein the maximum number of times is one for a generally convex obstacle.

15. The method according to claim 1 wherein the maximum number of times is one plus the number of material concavities associated with an obstacle.

16. The method according to claim 1 further comprising:

filtering the identified candidate paths based on at least one of a benchmark performance estimate of a generally direct linear path between the starting point and the termination point and a maximum-touches criteria, where the maximum touches criteria refers to contacting an outer boundary associated with an obstacle clearance about an obstacle less than or equal to an allotted maximum number of times.

17. The path planner according to claim 1 further comprising:

filtering the identified candidate paths to exclude at least a rejected portion of the identified candidate paths from a search process if the rejected portion has at least one of a total path cost estimate, a total path duration estimate, and a total path length estimate that exceeds a corresponding path benchmark estimate, by more than a maximum threshold, associated with a generally direct linear path between the starting point and the termination point.

18. A path planner for determining a path for a vehicle, the path planner comprising:

a location determining receiver for defining a starting point for the vehicle;

a definer for defining a termination point for the vehicle;

an obstacle detector for detecting two or more obstacles in a work area between the starting point and the termination point;

an obstacle modeler for defining an obstacle clearance zone about each corresponding obstacle;

an analyzer for identifying candidate paths between the starting point and the termination point, each candidate path only intersecting each obstacle clearance zone once for each corresponding obstacle;

an estimator for estimating an economic cost for traversing each candidate path or a portion thereof between the starting point and the termination point; and

a search engine for selecting a preferential path from the identified candidate paths based on the preferential path being associated with a lowest estimated economic cost.

19. The path planner according to claim 18, wherein the location determining receiver determines the starting point and corresponding starting heading of the vehicle;

and wherein the definer defines the termination point and corresponding termination heading for the vehicle.

20. The path planner according to claim 18, wherein the analyzer identifies a candidate path comprising a path portion from the starting point to the termination point.

21. The path planner according to claim 18 wherein the analyzer identifies the candidate path comprising a path portion from the starting point to an outer boundary of the obstacle clearance zone about a corresponding obstacle.

22. The path planner according to claim 18 wherein the analyzer identifies a candidate path portion comprising a first path segment from the starting point to a first obstacle clearance zone about a first corresponding obstacle and a second path segment interconnected to the first path segment, the second path segment extending from the first obstacle clearance zone to a second obstacle clearance zone about a second corresponding obstacle.

23. The path planner according to claim 18 wherein the analyzer identifies a candidate path portion comprising a path segment from a first outer boundary associated with an obstacle clearance zone of a first obstacle to a second outer boundary associated with an obstacle clearance zone of a second obstacle.

24. The path planner according to claim 23 wherein the analyzer determines nodes or vertices of the candidate paths by forming tangential interconnections with respect to the first outer boundary and the second outer boundary.

25. The path planner according to claim 18 wherein the search engine is adapted to search the candidate paths or portions of the candidate paths in accordance with at least one of an A* search algorithm and a bounded A* search algorithm.

26. The path planner according to claim 18 further comprising a filter for discarding or excluding the candidate paths from a search process if any of the candidate paths exceeds a maximum number of permitted touches for at least one of an outer boundary, a boundary clearance zone, the obstacle clearance zone, and an outside border shape of a work area.

27. The path planner according to claim 18 further comprising a filter for discarding or excluding the candidate paths from a search process if any of the candidate paths has at least one of a total path cost estimate, a total path duration estimate, and a total path length estimate that exceeds a corresponding path benchmark estimate, by more than a maximum threshold, associated with a generally direct linear path between the starting point and the termination point.

28. The path planner according to claim 18 wherein the obstacle modeler models the obstacle clearance zone such that an outer boundary of the obstacle clearance zone is spaced apart from the obstacle to provide a physical clearance between the vehicle and the obstacle if the vehicle follows a path associated with a vertex or node on an outer boundary of the obstacle clearance zone.

29. The path planner according to claim 18 wherein the obstacle modeler models an outer boundary associated with an obstacle as at least one of a generally elliptical, generally circular, and generally rectangular.