# US 11,029,691 B1 · Nonholonomic robot field coverage method

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,029,691 B1
- Document ID: US11029691B1
- Status: Granted
- Kind: B1
- Application number: 16/847,223
- Filed: 2020-04-13
- Granted: 2021-06-08
- Earliest claimed: 2020-01-23
- Assignees: Left Hand Robotics, Inc.
- Applicants: Left Hand Robotics, Inc.
- Inventors: Mickey Barboi; Nevin Gilbert; Eesam Hourani; Terry Olkin
- Web page: https://patentgrep.com/patent/US11029691B1

## CPC

- G05D 1/0212: {with means for defining a desired trajectory (involving a plurality of land vehicles G05D1/0287)}
- G05D 1/0219: {ensuring the processing of the whole working surface}
- G05D 1/0088: {characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours (using knowledge based models G06N5/00)}
- G05D 1/0268: {using internal positioning means}
- B25J 5/00: Manipulators mounted on wheels or on carriages (B25J1/00 takes precedence; program-controlled manipulators B25J9/00)
- B25J 9/16: Program controls (total factory control, i.e. centrally controlling a plurality of machines, G05B19/418)
- B25J 9/1664: {characterised by motion, path, trajectory planning}
- B25J 9/1666: {Avoiding collision or forbidden zones}
- B25J 11/00: Manipulators not otherwise provided for
- G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- B25J: MANIPULATORS; CHAMBERS PROVIDED WITH MANIPULATION DEVICES ({manipulators specially adapted for use in surgery A61B34/70; manipulators used in cleaning hollow articles B08B9/04}; manipulators associated with rolling mills B21B39/20; manipulators associated with forging machines B21J13/10; {manipulators associated with picking-up and placing mechanisms B23P19/007}; means for holding wheels or parts thereof B60B30/00; {vehicles with ground-engaging propulsion means, e.g. walking members B62D57/02, B62D57/032; devices for picking-up and depositing articles or materials between conveyors B65G47/90, B65G47/91; manipulators with gripping or holding means for transferring packages B65H67/065}; cranes B66C; {manipulators used in the protection or supervision of pipe-line installations F17D5/00; walking equipment adapted for nuclear steam-generators F22B37/006}; manipulators specially adapted for, or associated with, nuclear reactors G21C; {apparatus used for handling wafers during manufacture or treatment of semiconductor H10P72/50})

## Abstract

A software product and methods determine a field coverage method for a nonholonomic robot to process a field using parallel lanes. A cellular decomposition algorithm divides the field into a plurality of cells, each having a plurality of parallel lanes. Permutations of lane processing orders are determined for each cell, based upon a minimum turning radius of the robot. A cell graph is generated to determine a shortest path for single-time processing each lane in each cell without violating the minimum turning radius of the robot. A step list defining movement of the nonholonomic robot along each lane in each cell of the shortest path through the cell graph is generated, and transits between the lanes, and laps around the field and any obstacles are added. A path program to control the nonholonomic robot to process the field is generated based upon the step list.

## Claims

### Claim 1

A field coverage method for a nonholonomic robot to process a field using parallel lanes, comprising:
receiving field data defining (a) a plurality of geographical locations along a field boundary of the field and (b) a plurality of geographical locations along an obstacle boundary for each obstacle in the field;
converting the field data to two-dimensional coordinates defining the field boundary and each of the obstacle boundaries;
generating at least one headland lap relative to, and within, the field boundary, the headland lap defining at least one path around the field boundary for the nonholonomic robot to follow;
generating one soft boundary relative to, and within, the field boundary, the soft boundary defining lane end points that provide space for the nonholonomic robot to turn between lanes without traversing the field boundary;
for each of the obstacles, generating (a) at least one obstacle lap relative to and around the obstacle boundary, and (b) one soft boundary relative to, and around, the obstacle boundary defining lane end points that provide space for the nonholonomic robot to turn between the lanes without traversing the obstacle boundary;
determining, using a cellular decomposition algorithm, a plurality of cells each having a plurality of parallel lanes bounded by the soft boundaries;
determining, within each of the plurality of cells, permutations of lane processing orders that allow the nonholonomic robot to transition between a finishing point of one lane and a starting point of a next lane based upon a minimum turning radius of the nonholonomic robot, wherein each lane processing order defines, for that permutation, a starting vertex of a first lane in the lane processing order and a finishing vertex of a last lane in the lane processing order;
generating a cell graph connecting the plurality of cells based upon the permutations of lane processing orders of each cell;
determining, based upon a modified travelling salesperson algorithm, a shortest path through each cell graph that visits each of the plurality of cells once;
generating a step list defining movement of the nonholonomic robot along each lane in each cell of the shortest path through the cell graph;
generating transits between the plurality of cells on the shortest path and adding the transits to the step list;
adding transits between the lanes of the lane processing order for each cell to the step list;
adding laps to the step list; and
generating, based upon the step list, a path program to control the nonholonomic robot to process the field.

### Claim 2

A field coverage method for a nonholonomic robot to process a field divided into a plurality of cells, comprising:
determining, for each of the plurality of cells, permutations of lane processing orders based upon a minimum turning radius of the nonholonomic robot, each permutation defining a starting vertex of a first lane in the lane processing order and a finishing vertex of a last lane in the lane processing order;
generating a cell graph connecting the starting vertex of each of permutation for each cell with the finishing vertex of each of the permutations of the other cells;
determining a shortest path through the cell graph that single-time visits each of the plurality of cells;
generating a step list defining a path for the nonholonomic robot to follow shortest-path lanes of each of the plurality of cells based upon its lane processing order;
adding, to the step list, at least one lap adjacent to, and inside of, a field boundary of the field for the nonholonomic robot to follow; and
generating, based upon the step list, a path program to control the nonholonomic robot to process the field.

### Claim 3 (depends on 2)

The field coverage method of claim 2, further comprising:
generating one soft boundary relative to, and within, the field boundary of the field; and
determining, using a cellular decomposition algorithm and based at least in part on the soft boundary, the plurality of cells within the field, and for each of the plurality of cells, the lanes being determined based upon a processing width of the nonholonomic robot.

### Claim 4 (depends on 3)

The field coverage method of claim 3, the determining the plurality of cells further comprising:
detecting islands created by the cellular decomposition algorithm from either (a) different boundaries, or (b) a common boundary; and
forcing a cell division for each detected island.

### Claim 5 (depends on 3)

The field coverage method of claim 3, further comprising:
generating, for each of at least one obstacle located in the field, one obstacle soft boundary relative to, and around, a boundary of the at least one obstacle;
wherein the cellular decomposition algorithm determines the cells and lanes using the one obstacle soft boundary.

### Claim 6 (depends on 2)

The field coverage method of claim 2, determining the shortest path further comprising skipping a combination of two consecutive cells when a distance between the finishing vertex of the earlier of the two consecutive cells and the starting vertex of the latter of the two consecutive cells does not conform to the minimum turning radius of the nonholonomic robot.

### Claim 7 (depends on 2)

The field coverage method of claim 2, generating the step list further comprising:
generating, for each of the plurality of cells on the shortest path, a transit between each pair of consecutive lanes in the lane processing order of the cell; and
adding the transit to the step list.

### Claim 8 (depends on 2)

The field coverage method of claim 2, generating the step list further comprising:
generating, for each pair of consecutive cells in the shortest path, a transit between the finishing vertex of the earlier cell of the pair of consecutive cells and the starting vertex of the latter of the pair of consecutive cells; and
adding the transit to the step list.

### Claim 9 (depends on 8)

The field coverage method of claim 8, wherein generating the transit between pairs of consecutive lanes comprises generating a first curve between a finishing end of the earlier of the pair of consecutive lanes to a boundary lap and generating a second curve between the boundary lap and a starting end of the latter of the pair of consecutive lanes.

### Claim 10 (depends on 9)

The field coverage method of claim 9, the first curve and the second curve each comprising a Dubins curve.

### Claim 11 (depends on 9)

The field coverage method of claim 9, the first curve and the second curve each being in a direction of the second lane.

### Claim 12 (depends on 2)

The field coverage method of claim 2, wherein, for each of the permutations of lane processing orders for each of the plurality of cells, the starting vertex is located at a starting end of a starting lane of the lane processing order and the finishing vertex is located at a finishing end of a finishing lane of the lane processing order.

### Claim 13 (depends on 12)

The field coverage method of claim 12, the starting end and the finishing end being at the same end of the cell when a number of lanes in the cell is even, and the starting end and the finishing end being at opposite ends of the cell when the number of lanes in the cell is odd.

### Claim 14 (depends on 2)

The field coverage method of claim 2, further comprising, prior to determining the permutations of lane processing orders, merging adjacent cells that share two corners on a common side.

### Claim 15 (depends on 2)

The field coverage method of claim 2, further comprising:
receiving field data defining geographic locations of a plurality of points around the field boundary; and
converting the geographic locations to points on a two-dimensional plane, wherein the steps of determining, generating and adding process the points on the two-dimensional plane, and wherein the step of generating the path program further comprises converting the points defined within the step list into geographical locations.

### Claim 16 (depends on 15)

The field coverage method of claim 15, further comprising, prior to converting the geographic locations, rotating the field boundary by a fill angle that defines a direction of movement for the nonholonomic robot within the field, wherein the lanes of each of the plurality of cells are generated parallel to an X axis of the two-dimensional plane.

### Claim 17 (depends on 2)

The field coverage method of claim 2, further comprising determining, based upon the minimum turning radius and a lane width, a value of T that defines a nearest lane that the nonholonomic robot can transition to from a current lane, T being an integer greater than one, and wherein the permutations of lane processing orders are determined using T.

### Claim 18 (depends on 17)

The field coverage method of claim 17, wherein determining the shortest path inhibits cell sequences where a finishing lane of one cell and a starting lane of a subsequent cell do not conform to T.

### Claim 19 (depends on 2)

The field coverage method of claim 2, wherein the lanes in each of the plurality of cells are processed together in one pass.

### Claim 20

A software product comprising instructions, stored on computer-readable media, wherein the instructions, when executed by a computer, perform steps for a nonholonomic robot to process a field divided into a plurality of cells, comprising:
instructions for determining, for each of the plurality of cells, permutations of lane processing orders based upon a minimum turning radius of the nonholonomic robot, each permutation defining a starting vertex of a first lane in the lane processing order and a finishing vertex of a last lane in the lane processing order;
instructions for generating a cell graph connecting the starting vertex of each of permutation for each cell with the finishing vertex of each of the permutations of the other cells;
instructions for determining a shortest path through the cell graph that single-time visits each of the plurality of cells;
instructions for generating a step list defining a path for the nonholonomic robot to follow shortest-path lanes of each of the plurality of cells based upon its lane processing order;
instructions for adding, to the step list, at least one lap adjacent to, and inside of, an outer boundary of the field for the nonholonomic robot to follow; and
instructions for generating, based upon the step list, a path program to control the nonholonomic robot to process the field.