System and method for area coverage using sector decomposition

• US 8,224,516 B2
• Filed: 12/17/2009
• Issued: 07/17/2012
• Est. Priority Date: 12/17/2009
• Status: Active Grant

• Current Assignee: Deere & Company
• Original Assignee: Deere & Company
• Inventors: Anderson, Noel Wayne
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): Amin, Bhavesh V
• Application Number:
  US12/640,845
• Publication Number:
  US 20110153136A1
• Time in Patent Office: 943 Days
• Field of Search: None
• US Class Current: 701/23
• 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. 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;

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.

2. 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, wherein the path around the first landmark is a set of concentric arcs;

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

generating the path around the next landmark;

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.

3. The method of claim 2, 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.

4. 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, wherein the path around the first landmark is a set of concentric arcs;

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

generating the path around the next landmark;

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;

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.

5. 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, wherein the path around the first landmark is a set of concentric arcs;

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

generating the path around the next landmark;

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.

6. The method of claim 5, further comprising:

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

7. The method of claim 5, further comprising:

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

8. The method of claim 5, 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.

9. The method of claim 8, 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.