# US 2021/0240187 A1 · 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 2021/0240187 A1
- Document ID: US20210240187A1
- Status: Published application
- Kind: A1
- Application number: 17/236,548
- Filed: 2021-04-21
- Published: 2021-08-05
- Earliest claimed: 2020-01-23
- Assignees: The Toro Company
- Applicants: The Toro Company
- Inventors: Mickey Barboi; Nevin Gilbert; Eesam Hourani; Terry Olkin
- Web page: https://patentgrep.com/patent/US20210240187A1

## 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 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 its lane processing order and a finishing vertex of a last lane in its lane processing order;
generating a cell graph connecting the starting vertex of each of the permutations of each of the plurality of cells with the finishing vertex of each of the permutations of every other of the plurality of cells; and
determining a shortest path through the cell graph that single-time visits each of the plurality of cells.

### Claim 2 (depends on 1)

The field coverage method of claim 1, wherein determining the shortest path comprises skipping a combination of two consecutive cells when a distance between (a) the finishing vertex of an earlier one of the two consecutive cells and (b) the starting vertex of a latter one of the two consecutive cells does not conform to the minimum turning radius of the nonholonomic robot.

### Claim 3 (depends on 1)

The field coverage method of claim 1, further comprising:
generating a step list defining a path that follows shortest-path lanes of each of the plurality of cells based upon its corresponding lane processing order; and
adding, to the step list, at least one lap adjacent to, and inside of, a field boundary of the field.

### Claim 4 (depends on 3)

The field coverage method of claim 3, further comprising generating, based upon the step list, a path program to control the nonholonomic robot to process the field.

### Claim 5 (depends on 4)

The field coverage method of claim 4, further comprising:
receiving field data defining geographic locations around the field boundary; and
converting the geographic locations to a plurality of points on a two-dimensional plane, wherein the steps of (i) determining permutations, (ii) generating the cell graph, (iii) determining the shortest path, and (iv) adding the at least one lap, process the points on the two-dimensional plane, and wherein the step of generating the path program further comprises converting points defined within the step list into geographical locations.

### Claim 6 (depends on 5)

The field coverage method of claim 5, 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 lanes of each of the plurality of cells are generated parallel to an X axis of the two-dimensional plane.

### Claim 7 (depends on 3)

The field coverage method of claim 3, 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 one soft boundary, the plurality of cells within the field, and for each of the plurality of cells, parallel lanes corresponding to a processing width of the nonholonomic robot.

### Claim 8 (depends on 7)

The field coverage method of claim 7, wherein the determining the plurality of cells further comprises:
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 9 (depends on 7)

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

### Claim 10 (depends on 3)

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

### Claim 11 (depends on 3)

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

### Claim 12 (depends on 11)

The field coverage method of claim 11, wherein generating the transit between each pair 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; and
adding the transit to the step list.

### Claim 13 (depends on 12)

The field coverage method of claim 12, the first curve and the second curve each comprising a Dubins curve in a direction of the latter of the pair of consecutive lanes.

### Claim 14 (depends on 1)

The field coverage method of claim 1, 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 15 (depends on 14)

The field coverage method of claim 14, 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 16

A field coverage method for a nonholonomic robot to process a field divided into a plurality of cells, comprising:
determining a shortest path that visits, only once, each of the plurality of cells and traverses parallel lanes of said each cell in a lane processing order, the lane processing order based upon a minimum turning radius of the nonholonomic robot;
generating a step list defining the shortest path; and
generating, based upon the step list, a path program to control the nonholonomic robot to process the field.

### Claim 17 (depends on 16)

The field coverage method of claim 16, further comprising adding, to the step list, at least one lap adjacent to, and inside of, a field boundary of the field.

### Claim 18 (depends on 16)

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

### Claim 19 (depends on 16)

The field coverage method of claim 16, the step of determining the shortest path comprising:
determining, for each of the plurality of cells, permutations of lane processing orders based upon minimum turning radius of the nonholonomic robot, each permutation defining a starting vertex of a first lane in its lane processing order and a finishing vertex of a last lane in its lane processing order;
generating a cell graph connecting the starting vertex of each of the permutations for each cell with the finishing vertex of each of the permutations of the other cells; and
determining the shortest path through the cell graph that single-time visits each of the plurality of cells.

### Claim 20

A computer-readable media storing instructions that, when executed by a computer, cause the computer to perform a method for generating a path program for controlling a nonholonomic robot to process a field divided into a plurality of cells, the method comprising:
determining a shortest path that single-time visits each of the plurality of cells and traverses parallel lanes of the cell in a lane processing order, the lane processing order being based upon a minimum turning radius of the nonholonomic robot;
generating a step list defining the shortest path; and
generating, based upon the step list, a path program to control the nonholonomic robot to process the field.