SYSTEM AND METHOD FOR AREA COVERAGE USING SECTOR DECOMPOSITION

• US 20110153136A1
• Filed: 12/17/2009
• Published: 06/23/2011
• Est. Priority Date: 12/17/2009
• Status: Active Grant

• Current Assignee: Deere & Company
• Original Assignee: Deere & Company
• Inventors: Anderson, Noel Wayne
• Granted Patent: US 8,224,516 B2
• Time in Patent Office: Days
• US Class Current: 701/25
• CPC Class Codes: G05D 1/0219 ensuring the processing of the whole working surface
• CPC Class Codes: G05D 1/0227 using mechanical sensing means, e.g. for sensing treated area
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0251 extracting 3D information from a plurality of images taken from different locations, e.g. stereo vision stereoscopic image analysis H04N13/00; depth recovery from images G06T7/593
• 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/0259 using magnetic or electromagnetic means
• CPC Class Codes: G05D 1/0265 using buried wires
• 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/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59

Abstract

The different illustrative embodiments provide a method for generating an area coverage path plan using sector decomposition. A starting point is identified on a worksite map having a number of landmarks. A first landmark in the number of landmarks is identified. A path is generated around the first landmark until an obstacle is detected. In response to detecting the obstacle, the path is made linear to a next landmark. The path is generated around the next landmark.

Claims

1. A method for generating an area coverage path plan, the method comprising:

identifying a starting point on a worksite map having a number of landmarks;

identifying a first landmark in the number of landmarks;

generating a path around the first landmark until an obstacle is detected;

responsive to detecting the obstacle, making the path linear to a vicinity of a next landmark; and

generating the path around the next landmark.

2. The method of claim 1, wherein the path around the first landmark is a set of concentric arcs.

3. The method of claim 1, wherein generating the path around the first landmark further comprises:

determining whether a first worksite boundary is detected;

responsive to a determination that the first worksite boundary is detected, moving the path a predefined width away from the first landmark along the first worksite boundary; and

continuing the path around the first landmark.

4. The method of claim 3, further comprising:

responsive to a determination that the first worksite boundary is not detected, determining whether an obstacle is detected; and

responsive to a determination that no obstacle is detected, continuing the path around the first landmark.

5. The method of claim 4, further comprising:

iteratively generating the path around the number of landmarks until the path covers the worksite map; and

generating a path plan using the path covering the worksite map.

6. A method for executing an area coverage path plan, the method comprising:

determining an expected width of a landmark in pixels for a desired distance away from the landmark;

identifying an image having the landmark;

determining an observed width of the landmark using the image;

comparing the observed width of the landmark to the expected width of the landmark; and

sending a message to a vehicle control process to move an autonomous vehicle based on the comparison of the observed width and the expected width.

7. The method of claim 6, further comprising:

filtering the image to form a filtered image consisting of the landmark.

8. The method of claim 6, further comprising:

normalizing an orientation of the landmark in a vertical direction in the image.

9. The method of claim 6, wherein comparing the observed width of the landmark to the expected width of the landmark further comprises:

determining whether the observed width of the landmark is greater than the expected width of the landmark; and

responsive to a determination that the observed width is greater than the expected width, sending a message to the vehicle control process to move the autonomous vehicle away from the landmark.

10. The method of claim 9, further comprising:

responsive to a determination that the observed width is not greater than the expected width, determining whether the observed width is less than the expected width;

responsive to a determination that the observed width is less than the expected width, sending a message to the vehicle control process to move the autonomous vehicle toward the landmark.

11. The method of claim 10, further comprising:

determining whether an obstacle is detected; and

responsive to a determination that no obstacle is detected, identifying a next image having a landmark.

12. A method for executing a path plan, the method comprising:

receiving a worksite map for a worksite having a number of landmarks;

generating an area coverage grid map having a number of area coverage grid elements for the worksite using the worksite map;

generating a path plan for the worksite using the worksite map and the area coverage grid map;

marking the number of landmarks on the worksite map as unvisited;

initializing the number of area coverage grid elements as uncovered; and

performing an area coverage task at the worksite.

13. The method of claim 12, wherein the worksite map includes at least one of a number of landmark locations, a number of landmark attributes, and a number of obstacles.

14. The method of claim 12, further comprising:

identifying a landmark marked as unvisited on the worksite map;

sending a message to a vehicle control process to proceed to the landmark marked as unvisited; and

executing an area coverage behavior on a path around the landmark.

15. The method of claim 14, further comprising:

determining whether an obstacle is detected;

responsive to a determination that the obstacle is detected, marking the landmark marked as unvisited as visited on the worksite map; and

marking associated area coverage grid elements of the landmark marked as visited as covered.

16. The method of claim 12, further comprising:

determining whether there are any remaining landmarks marked as unvisited;

responsive to a determination that there are remaining landmarks marked as unvisited, identifying a next landmark marked as unvisited on the worksite map; and

sending a message to a vehicle control process to proceed to the next landmark marked as unvisited.

17. The method of claim 16, further comprising:

responsive to a determination that there are no remaining landmarks marked as unvisited, determining whether there are any remaining area coverage grid elements marked as uncovered;

responsive to a determination that there are remaining area coverage grid elements marked as uncovered, sending a message to the vehicle control process to proceed along the path plan to a visited landmark associated with an area coverage grid element marked as uncovered; and

executing an area coverage behavior on a path around the visited landmark.

18. A method for executing a path plan, the method comprising:

receiving a number of landmark attributes and obstacle information for a worksite;

generating an area coverage grid map having a number of grid elements;

acquiring an image of a worksite area of the worksite;

determining whether a landmark is identified in the image;

responsive to a determination that the landmark is identified in the image, determining whether the landmark identified has been visited; and

responsive to a determination that the landmark identified has not been visited, calculating a path plan to the landmark identified.

19. The method of claim 18, wherein the number of landmark attributes include at least one of a landmark description, landmark image, and a landmark characteristic.

20. The method of claim 18, wherein the image of the worksite area is acquired using a vision system associated with an autonomous vehicle.

21. The method of claim 18, further comprising:

responsive to a determination that the landmark is not identified in the image, searching for the landmark in the worksite area using a number of cameras rotating at an amount which is the product of the field of view in degrees multiplied by a value between zero and one to provide image overlap in additional images acquired.

22. The method of claim 21, further comprising:

determining wherein the landmark is identified in the additional images acquired;

responsive to a determination that the landmark is not identified in the additional images acquired, determining whether the number of cameras have rotated 360 degrees; and

responsive to a determination that the number of cameras have not rotated 360 degrees, rotating the number of cameras at an amount which is the product of the field of view in degrees multiplied by a value between zero and one to provide image overlap in additional images acquired.

23. The method of claim 22, responsive to a determination that the landmark is identified in the additional images acquired, determining whether the landmark identified has been visited;

and

responsive to a determination that the landmark identified has not been visited, calculating a path plan to the landmark identified.

24. The method of claim 18, further comprising:

responsive to a determination that the landmark identified has been visited, determining whether all grid map elements have been covered;

responsive to a determination that all grid map elements have not been covered, acquiring a next image for a next worksite area; and

determining whether a next landmark is identified in the next image.

25. An apparatus for generating an area coverage path plan, the apparatus comprising:

a processor unit configured to generate an area coverage path plan for a worksite using a number of landmarks; and

a vehicle control process configured to execute the area coverage path plan for the worksite received from the processor unit using a mobility system.

26. The apparatus of claim 25, wherein the processor unit is further configured to receive a worksite map for the worksite having the number of landmarks;

generate an area coverage grid map having a number of area coverage grid elements for the worksite using the worksite map;

generate a path plan for the worksite using the worksite map and the area coverage grid map;

mark the number of landmarks on the worksite map as unvisited; and

initialize the number of area coverage grid elements as uncovered

27. The apparatus of claim 26, wherein the mobility system is further configured to perform an area coverage task at the worksite.

28. The apparatus of claim 26, wherein the worksite map includes at least one of a number of landmark locations, a number of landmark attributes, and a number of obstacles.

29. The apparatus of claim 26, wherein the processor unit is further configured to identify a landmark marked as unvisited on the worksite map;

and send a message to the vehicle control process to proceed to the landmark marked as unvisited.

30. The apparatus of claim 26, wherein the processor unit is further configured to determine whether an obstacle is detected;

responsive to a determination that the obstacle is detected, mark the landmark marked as unvisited as visited on the worksite map; and

mark associated area coverage grid elements of the landmark marked as visited as covered.

31. The apparatus of claim 26, wherein the processor unit is further configured to determine whether there are any remaining landmarks marked as unvisited;

responsive to a determination that there are remaining landmarks marked as unvisited, identify a next landmark marked as unvisited on the worksite map; and

send a message to the vehicle control process to proceed to the next landmark marked as unvisited.

32. The apparatus of claim 26, wherein the processor unit is further configured to, responsive to a determination that there are no remaining landmarks marked as unvisited, determine whether there are any remaining area coverage grid elements marked as uncovered;

responsive to a determination that there are remaining area coverage grid elements marked as uncovered, send a message to the vehicle control process to proceed along the path plan to a visited landmark associated with an area coverage grid element marked as uncovered; and

execute an area coverage behavior on a path around the visited landmark.

33. The apparatus of claim 25, further comprising:

a vision system configured to capture a number of images of the worksite.

34. An apparatus for generating an area coverage path plan, the apparatus comprising:

a processor unit configured to generate an area coverage path plan using a number of landmarks for a worksite by generating a path around a first landmark until an obstacle is detected, and responsive to detecting the obstacle, making the path linear to a vicinity of a next landmark, and generating the path around the next landmark; and

a vehicle control process configured to execute the area coverage path plan for the worksite received from the processor unit using a mobility system.