Granted Patent B2

US 12,298,775 · App. 18/092,548 · Granted May 13, 2025

Inventors: Marc Christopher Alban (San Antonio, TX); Zachary Austin Goins (Boulder, CO); Kristopher Charles Kozak (San Antonio, TX); John Gordon Morrison (Longmont, CO)

Assignee: Scythe Robotics, Inc.

G05D1/0219A01D34/008G05D1/0217

Abstract

Claims (111)

1. A system configured to generate a coverage plan, the system comprising:

one or more processors; and

one or more non-transitory computer readable media having instructions stored thereon which, when executed by the one or more processors, cause the one or more processors to perform operations comprising:

receiving a plurality of nodes indicative of a perimeter of a region;

determining, based at least in part on the plurality of nodes, a mesh;

determining a graph connecting elements of the mesh;

determining, based at least in part on the graph, a longest path between pairs of nodes of the plurality of nodes;

determining, based at least in part on the longest path, a set of segments;

performing an optimization associated with the set of segments to determine a coverage plan; and

transmitting the coverage plan to an autonomous lawn mower; and

controlling the autonomous lawn mower based at least in part on the coverage plan.

2. The system of claim 1 , wherein determining the set of segments comprises:

determining a plurality of struts normal to segments of the longest path;

determining, based at least in part on a cost associated with a strut of the plurality of struts, an optimal point along the strut;

determining a path comprising the pair of nodes associated with the longest path and the optimal point;

generating at least one offset path from the path, the offset path being offset by one or more of a width of the autonomous lawn mower or an overlap amount; and

determining, as the set of segments, the path and a portions of the offset path interior to the perimeter.

3. The system of claim 2 , wherein the cost comprises one or more of:

a cost based at least in part on a curvature of the path at the optimal point,

a cost based at least in part on a distance of the optimal point from a center of the strut, or

a cost based at least in part on a distance of the optimal point from a perimeter of the region, and

wherein determining the optimal point comprises determining a point along the strut which minimizes the cost.

4. The system of claim 1 , wherein determining the set of segments comprises:

determining, as a first side, a portion of the perimeter between the pair of nodes associated with the longest path;

determining, as a second side, a remaining portion of the perimeter between the pair of nodes opposing the first side;

determining a first initial offset segment associated with the first side and a second initial offset segment associated with the second side, the first and second initial offset segments spaced at least a portion of a width of the autonomous lawn mower from the first and second sides, respectively;

determining, based at least in part on a minimum and a maximum offset from the first initial offset, a first path;

determining, based at least in part on a minimum and a maximum offset from the second initial offset, a second path;

determining a first set of valid portions of the first path; and

determining a second set of valid portions of the second path,

wherein the set of segments comprises the first initial offset, the second initial offset, the first set of valid portions of the first path, and the second set of valid portions of the second path.

5. The system of claim 4 , wherein determining the set of segments comprises eroding the perimeter and wherein eroding the perimeter further comprises performing an iteration comprising:

determining, based at least in part on a minimum and maximum offset from a previously determined first set of valid portions, a first subsequent path;

determining, based at least in part on a minimum and maximum offset from a previously determined second set of valid portions, a second subsequent path; and

determining, based at least in part on the first subsequent path and the second subsequent path, a subsequent first set of valid portions and a subsequent second set of valid portions,

wherein the set of segments further comprises the subsequent first set of valid portions of the first subsequent path and the subsequent second set of valid portions of the second subsequent path.

6. The system of claim 1 , wherein at least one of:

the longest path is indicative of a longest distance between the pairs of nodes and is interior to the perimeter of the region, or

the operations include determining, as the coverage plan and by performing an optimization, a connection between the set of segments and an order in which to traverse the set of segments.

7. A method to generate a coverage plan, the method comprising:

receiving a plurality of nodes indicative of a perimeter of a region;

determining, based at least in part on the plurality of nodes, a mesh;

determining a graph connecting elements of the mesh;

determining, based at least in part on the graph, a longest path between pairs of nodes of the plurality of nodes;

determining, based at least in part on the longest path, a set of segments;

performing an optimization associated with the set of segments to determine a coverage plan; and

transmitting the coverage plan to an autonomous lawn mower; and

controlling the autonomous lawn mower based at least in part on the coverage plan.

8. The method of claim 7 , wherein determining the set of segments comprises:

determining a plurality of struts normal to segments of the longest path;

determining, based at least in part on a cost associated with a strut of the plurality of struts, an optimal point along the strut;

determining a path comprising the pair of nodes associated with the longest path and the optimal point;

generating at least one offset path from the path, the offset path being offset by one or more of a width of the autonomous lawn mower or an overlap amount; and

determining, as the set of segments, the path and a portions of the offset path interior to the perimeter.

9. The method of claim 8 , wherein the cost comprises one or more of:

a cost based at least in part on a curvature of the path at the optimal point,

a cost based at least in part on a distance of the optimal point from a center of the strut, or

a cost based at least in part on a distance of the optimal point from a perimeter of the region, and

wherein determining the optimal point comprises determining a point along the strut which minimizes the cost.

10. The method of claim 7 , wherein determining the set of segments comprises:

determining, as a first side, a portion of the perimeter between the pair of nodes associated with the longest path;

determining, as a second side, a remaining portion of the perimeter between the pair of nodes opposing the first side;

determining a first initial offset segment associated with the first side and a second initial offset segment associated with the second side, the first and second initial offset segments spaced at least a portion of a width of the autonomous lawn mower from the first and second sides, respectively;

determining, based at least in part on a minimum and a maximum offset from the first initial offset, a first path;

determining, based at least in part on a minimum and a maximum offset from the second initial offset, a second path;

determining a first set of valid portions of the first path; and

determining a second set of valid portions of the second path,

wherein the set of segments comprises the first initial offset, the second initial offset, the first set of valid portions of the first path, and the second set of valid portions of the second path.

11. The method of claim 10 , wherein determining the set of segments comprises eroding the perimeter and wherein eroding the perimeter further comprises performing an iteration comprising:

determining, based at least in part on a minimum and maximum offset from a previously determined first set of valid portions, a first subsequent path;

determining, based at least in part on a minimum and maximum offset from a previously determined second set of valid portions, a second subsequent path; and

determining, based at least in part on the first subsequent path and the second subsequent path, a subsequent first set of valid portions and a subsequent second set of valid portions,

wherein the set of segments further comprises the subsequent first set of valid portions of the first subsequent path and the subsequent second set of valid portions of the second subsequent path.

12. The method of claim 7 , wherein the longest path is indicative of a longest distance between the pairs of nodes and is interior to the perimeter of the region.

13. The method of claim 7 , comprising determining, as the coverage plan and by performing an optimization, a connection between the set of segments and an order in which to traverse the set of segments.

14. One or more non-transitory computer readable media having instructions stored thereon which, when executed by one or more processors, cause the one or more processors to perform operations comprising:

receiving a plurality of nodes indicative of a perimeter of a region;

determining, based at least in part on the plurality of nodes, a mesh;

determining a graph connecting elements of the mesh;

determining, based at least in part on the graph, a longest path between pairs of nodes of the plurality of nodes;

determining, based at least in part on the longest path, a set of segments;

performing an optimization associated with the set of segments to determine a coverage plan; and

transmitting the coverage plan to an autonomous lawn mower; and

controlling the autonomous lawn mower based at least in part on the coverage plan.

15. The one or more non-transitory computer readable media of claim 14 , wherein determining the set of segments comprises:

determining a plurality of struts normal to segments of the longest path;

determining, based at least in part on a cost associated with a strut of the plurality of struts, an optimal point along the strut;

determining a path comprising the pair of nodes associated with the longest path and the optimal point;

generating at least one offset path from the path, the offset path being offset by one or more of a width of the autonomous lawn mower or an overlap amount; and

determining, as the set of segments, the path and a portions of the offset path interior to the perimeter.

16. The one or more non-transitory computer readable media of claim 15 , wherein the cost comprises one or more of:

a cost based at least in part on a curvature of the path at the optimal point,

a cost based at least in part on a distance of the optimal point from a center of the strut, or

a cost based at least in part on a distance of the optimal point from a perimeter of the region, and

wherein determining the optimal point comprises determining a point along the strut which minimizes the cost.

17. The one or more non-transitory computer readable media of claim 14 , wherein determining the set of segments comprises:

determining, as a first side, a portion of the perimeter between the pair of nodes associated with the longest path;

determining, as a second side, a remaining portion of the perimeter between the pair of nodes opposing the first side;

determining a first initial offset segment associated with the first side and a second initial offset segment associated with the second side, the first and second initial offset segments spaced at least a portion of a width of the autonomous lawn mower from the first and second sides, respectively;

determining, based at least in part on a minimum and a maximum offset from the first initial offset, a first path;

determining, based at least in part on a minimum and a maximum offset from the second initial offset, a second path;

determining a first set of valid portions of the first path; and

determining a second set of valid portions of the second path,

wherein the set of segments comprises the first initial offset, the second initial offset, the first set of valid portions of the first path, and the second set of valid portions of the second path.

18. The one or more non-transitory computer readable media of claim 17 , wherein determining the set of segments comprises eroding the perimeter and wherein eroding the perimeter further comprises performing an iteration comprising:

determining, based at least in part on a minimum and maximum offset from a previously determined first set of valid portions, a first subsequent path;

determining, based at least in part on a minimum and maximum offset from a previously determined second set of valid portions, a second subsequent path; and

determining, based at least in part on the first subsequent path and the second subsequent path, a subsequent first set of valid portions and a subsequent second set of valid portions,

wherein the set of segments further comprises the subsequent first set of valid portions of the first subsequent path and the subsequent second set of valid portions of the second subsequent path.

19. The one or more non-transitory computer readable media of claim 14 , wherein the longest path is indicative of a longest distance between the pairs of nodes and is interior to the perimeter of the region.

20. The one or more non-transitory computer readable media of claim 14 , wherein the operations include determining, as the coverage plan and by performing an optimization, a connection between the set of segments and an order in which to traverse the set of segments.

Assignments (2)

Continuity (2)

References Cited (27)