Patent Description:
Engineering vehicles such as tractors and compactors are widely used in agriculture and construction. For example, a variety of farm implements may be towed behind or mounted on a tractor to perform various agricultural tasks, such as plowing, irrigation, fertilizer and pesticide spraying, seed spraying, harvesting, and the like. As another example, compactors may be used to create a level grade in construction projects. Autonomous or semi-autonomous vehicles are used for precision agriculture and construction. Various navigation planning algorithms can be used to guide an autonomous vehicle. There is a need for a coverage planner that can generate a coverage trajectory for an autonomous vehicle with an implement to traverse a work area in an efficient way. For some applications, such as fertilizer spraying and seed spraying, the autonomous vehicle may need to be replenished with consumable materials (e.g., fertilizer and seeds) while traversing the work area. For such applications, there is a need for a replenishment planner that can generate replenishment trajectories for the autonomous vehicle. <CIT> discloses a method of determining target travel routes in an agricultural field area for route planning of an agricultural working machine. An inner field is defined with an inner field boundary in the field area so that there is an edge surface between a boundary contour of the field area and the inner field boundary. Target travel routes extending in the inner field are determined for route planning. Edge polylines are determined which extend in the edge surface along the boundary contour. The edge surface takes account of working machine-specific features. The edge surface has a minimum edge width. The minimum edge width is determined based on the machine-specific features. The minimum edge width is so selected that it corresponds at least to a sum of half a maximum working width and half a travel track width of the working machine. <CIT> discloses a method of generating a path which allows an autonomous vehicle to smoothly travel, by providing information regarding boundary points of a region and information regarding an obstacle in the region, and thereby designing a route. The method of designing a route in a region, for an autonomous vehicle which performs work while traveling in the region, is characterized by designing a traveling route for the autonomous vehicle by the steps of: acquiring boundary points of the region and boundary points of an obstacle existing in the region; approximating the region to a polygonal shape by using a representative point selected from among the acquired boundary points; dividing the region approximated to the polygonal shape into a plurality of trapezoidal or triangular shapes; merging regions other than the region in which the obstacle exists, among the plurality of divided regions; generating paths in the merged regions and paths connecting the merged regions to each other; and connecting the paths in the regions and the paths between the regions to one another.

According to some embodiments, a method of area coverage planning for an autonomous vehicle includes, at a computer system, receiving information of a boundary of a work area and information of one or more obstacles located within the work area, and laying a plurality of tracks within the boundary of the work area. The plurality of tracks is spaced apart from each other by a spacing. Laying the plurality of tracks includes, based on (i) the information of the boundary of the work area, and (ii) the information of the one or more obstacles, performing a multivariate optimization to: (i) determine an optimal direction of the plurality of tracks, and (ii) an optimal offset for a first track from the boundary, so as to minimize a total distance of the plurality of tracks. The method further includes generating a trajectory that is traversable by the autonomous vehicle to traverse the plurality of tracks.

According to some embodiments, a method of area coverage planning for an autonomous vehicle includes, at a computer system, receiving information of a boundary of a work area, and laying a plurality of tracks within the boundary of the work area. The plurality of tracks is spaced apart from each other by a spacing. Laying the plurality of tracks includes, based on the information of the boundary of the work area, performing a multivariate optimization to: (i) determine an optimal direction of the plurality of tracks, and (ii) an optimal offset for a first track from the boundary, so as to minimize a total distance of the plurality of tracks. The method further includes generating a trajectory that is traversable by the autonomous vehicle to traverse the plurality of tracks.

According to some embodiments, a method of area coverage planning with replenishment planning for an autonomous vehicle includes, at a computer system, receiving information of a boundary of the work area, receiving location information of one or more refill stations for replenishing the material, and receiving information of a current amount of the material left in the autonomous vehicle. The method further includes, based on the information of the boundary of the work area, laying a plurality of tracks within the boundary of the work area so as to minimize a total distance of the plurality of tracks. The plurality of tracks is spaced apart from each other by a spacing. The method further includes generating a coverage trajectory that is traversable by the autonomous vehicle to traverse the plurality of tracks, and based on (i) the coverage trajectory, (ii) the location information of the one or more refill stations, (iii) the current amount of the material left in the autonomous vehicle, and (iv) a nominal full amount and a nominal consumption rate of the material by the autonomous vehicle, determining one or more logistic points along the coverage trajectory at which a remaining amount of the material reaches a threshold. The method further includes, for each respective logistic point of the one or more logistic points, generating a respective replenishment trajectory for the autonomous vehicle. The respective replenishment trajectory includes a first part from the respective logistic point to a respective refill station of the one of the one or more refill stations for replenishing the autonomous vehicle with the material, and a second part from the respective refill station to the respective logistic point for the autonomous vehicle to resume traversing the coverage trajectory.

According to some embodiments, a method of area coverage planning with replenishment planning for an autonomous vehicle includes, at a computer system, receiving information of a boundary of the work area, receiving location information of one or more refill stations for replenishing the material, and receiving information of a current amount of the material left in the autonomous vehicle. The method further includes, based on the information of the boundary of the work area, laying a plurality of tracks within the boundary of the work area so as to minimize a total distance of the plurality of tracks. The plurality of tracks is spaced apart from each other by a spacing. The method further includes generating a coverage trajectory that is traversable by the autonomous vehicle to traverse the plurality of tracks, and based on (i) the coverage trajectory, (ii) the location information of the one or more refill stations, (iii) the current amount of the material left in the autonomous vehicle, and (iv) a nominal full amount and a nominal consumption rate of the material by the autonomous vehicle, determining one or more logistic points along the coverage trajectory at which the autonomous vehicle needs to be replenished with the material. Each respective logistic point is at an end of a respective track. The method further includes, for each respective logistic point of the one or more logistic points, generating a respective replenishment trajectory for the autonomous vehicle. The respective replenishment trajectory includes a first part from the respective logistic point to a respective refill station of the one of the one or more refill stations for replenishing the autonomous vehicle with the material, and a second part from the respective refill station to a beginning of a next track for the autonomous vehicle to resume traversing the coverage trajectory.

The goal of area coverage can be to efficiently apply an implement across a work area. According to some embodiments, provided with geographical information of the boundary of a work area, an area coverage planner can automatically generate a single trajectory for guiding an autonomous vehicle across the work area, so as to maximize coverage while minimizing the total distance travelled and the total duration of time, thus saving fuel and resources. The boundary can have irregular shapes, and can have convex as well as concave sections. In some embodiments, the area coverage planner can accommodate static obstacles, such as electrical poles, located inside the boundary so that the trajectory avoids the static obstacles. The area coverage planner can optimize the layout of tracks based on the geometry of the boundary and the locations and the geometries of the static obstacles.

In some embodiments, the area coverage planner can generate a trajectory for traversing the tracks (which can be either generated by the optimization or pre-determined). In some embodiments, given the location of an entry point and the location of an exit point, the area coverage planner can generate an entry route from the entry point to a first track, and an exit route from a last track to the exit point. In some embodiments, the area coverage planner can also generate a headland pass along a headland guideline at a periphery of the boundary. The headland pass can be traversed by the autonomous vehicle before, after, or in between traversing the tracks (e.g., as specified by a user). The entry route, the exit route, and the headland pass, as well as the trajectory for traversing the tracks, are traversable by the autonomous vehicle based on the constraints of the vehicle.

The following terms can be used herein to describe a work area. The term "geofence" may refer to a geographical boundary of a work area (e.g., an agricultural field, a construction site, and the like) that no part of the vehicle is permitted to go beyond. The term "boundary" may refer to any polygon or closed curve that is either identical to the geofence or is inwardly offset from the geofence. For example, a farmer may drive the vehicle around the crop rows to record a boundary of the work area. In construction applications, information of the boundary may be available by construction surveys and the site design. Information of the boundary may also be obtained by manually walking up the boundary, by using an autonomous ground vehicle (AGV), or the like. The boundary information may be input to an area coverage planner for algorithmic computation. The boundary may be used as the geofence. The term "headland" may refer to the region between the geofence and a second boundary inwardly offset from the geofence.

<FIG> illustrates an exemplary work area <NUM>. The work area <NUM> has a boundary or geofence <NUM>. A second boundary <NUM> is inwardly offset from the geofence <NUM>. The region inside the second boundary <NUM> may be the cropped area <NUM> with many swaths <NUM>. The region between the geofence <NUM> and the second boundary <NUM> may be referred to herein as the headland <NUM>. The geofence <NUM> may be referred to as the outer boundary of the headland <NUM>. The second boundary <NUM> may be referred to as the inner boundary of the headland <NUM> or as the headland boundary. The offset distance between the geofence <NUM> and the second boundary <NUM> may be referred to as the width of the headland <NUM>. A headland <NUM> may have a width that is an integer multiple of the implement width X being used. For instance, in the example illustrated in <FIG>, the width of the headland is equal to the implement width X.

The term "headland guideline" may refer to a guidance line <NUM> inside the headland <NUM> that may be used as a route for a vehicle to traverse along to cover the headland <NUM> or transition from one track to a next track (or from one segment of a track to a next segment of the track). For instance, in the example illustrated in <FIG>, the guidance line <NUM> may be offset from the headland boundary <NUM> by a distance that is equal to one half of the implement width X.

According to some embodiments, an area coverage planner can accommodate work areas (e.g., fields) with arbitrary boundary shapes. For example, a work area can have a boundary with an irregular shape. The boundary can also include convex sections as well as concave sections. In addition, the work area can include static obstacles within the boundary. In the discussions below, examples as applied to agricultural vehicles (e.g., tractors) working in fields will be used for illustration purposes. But embodiments of the present invention can be applied to applications other than agricultural applications, such as constructions.

<FIG> shows an exemplary field <NUM> with a boundary <NUM>. The field <NUM> can have an optional headland guideline <NUM>. As illustrated, the boundary <NUM> can have an irregular shape, and can have convex sections (e.g., the section <NUM>) as well as concave sections (e.g., section <NUM>). The field <NUM> can include some static obstacles <NUM> (e.g., electrical poles) within its boundary <NUM>. Optionally, an entry point <NUM> and an exit point <NUM> can be pre-defined.

Information of the boundary <NUM> (e.g., geometrical and location information) and information of the obstacles <NUM> (e.g., geometrical and location information) can be input into an area coverage planner. According to some embodiments, given this information, a first task for the area coverage planner may be to lay down the tracks for a vehicle to traverse in order to cover the entire field <NUM>.

<FIG> shows an exemplary layout of tracks (e.g., swaths) in the field <NUM> according to some embodiments. As illustrated, the tracks <NUM> can be a series of straight lines that cover the entire field <NUM>. The tracks <NUM> can be advantageously made parallel to each other. The spacing between adjacent tracks <NUM> can be related to the width of an implement attached to the vehicle (e.g., equal to, slightly smaller, or slightly greater than the width of the implement, depending on whether an overlap or a gap in the coverage between adjacent tracks is desired). In this manner, as the vehicle traverses along a given track <NUM>, the implement extends about one half of the track spacing on either side. Thus, as the vehicle completes traversing all the tracks <NUM> in the field, the entire field <NUM> can be covered. According to some embodiments, the spacing between adjacent tracks <NUM> can be specified by a user.

As illustrated in <FIG>, some tracks <NUM> can intersect some of the obstacles <NUM>. For example, the track <NUM> intersects the obstacles 230a and 230b. Thus, the track <NUM> can be divided into three segments 312a, 312b, and 312c, as illustrated in <FIG> shows the tracks <NUM> without showing the obstacles <NUM>, so as to show the segments more clearly. In addition, some tracks <NUM> can intersect the boundary <NUM>. For example, the track <NUM> intersects the concave section <NUM> of the boundary <NUM>. Thus, the track <NUM> can be divided into two segments 314a and 314b, as illustrated in <FIG>.

To transition from one segment to a next segment of a track, the vehicle may need to make a turn. For example, referring to <FIG>, to transition from the segment 312a to the segment 312b, the vehicle may need to make a semi-circular turn <NUM> to get around the obstacle 230a (the obstacle 230a is not shown in <FIG>). Similarly, to transition from the segment 314a to the segment 314b, the vehicle may need to navigate along the curved path <NUM> (e.g., along the headland guideline <NUM>) so as not to cross the concave section <NUM> of the boundary <NUM>. Also, to transition from the end of one track to the beginning of a next track, the vehicle may need to make an end-of-row-turn (e.g., a U-shaped turn along the headland guideline <NUM>). Since the vehicle may need to slow down in order to make a turn, more number of turns can result in a longer total duration of time to traverse all the tracks. Therefore, it can be advantageous to lay down the tracks <NUM> in a way that minimizes the total number of segments to the extent possible. A track that does not intercept any obstacle <NUM> can be considered as one segment. The number of segments can depend on the offset and the direction of the tracks, as discussed below.

<FIG> illustrate two examples of offset for laying down tracks in the field <NUM>. The term "offset" refers to the distance <NUM> of a first track <NUM> from the boundary <NUM>. The value of the offset can be a parameter to be optimized by the area coverage planner. In the example shown in <FIG>, the value of the offset <NUM> is <NUM> meters. In the example shown in <FIG>, the value of the offset <NUM> is <NUM> meters.

<FIG> illustrate how the value of the offset <NUM> can affect the total number of segments in a track layout. In the example illustrated in <FIG>, the value of the offset is set to zero (i.e., the first track <NUM> starts at the boundary <NUM>). Once the first track <NUM> is laid, the other tracks can be laid spaced apart from the first track <NUM> with an equal spacing with respect to each other (e.g., equal to the width of an implement attached to the vehicle). As illustrated in <FIG>, for this value of the offset, the track <NUM> intercepts the row of obstacles <NUM>, and is divided into as many as fifteen segments <NUM>. In the example illustrated in <FIG>, the value of the offset is set to <NUM> meters. As illustrated, here the tracks lie on either side of the row of obstacles <NUM>. As a result, the track <NUM> intercepts only two obstacles <NUM>, and is divided into as few as three segments <NUM>.

As discussed above, more segments can require more turns, and more turns can result in a longer duration of time. Thus, the track layout shown in <FIG> can be more advantageous than the track layout shown in <FIG> as it includes less number of segments. For example, for the track layout shown in <FIG>, the vehicle would make a total of <NUM> turns (including turns for transitioning from one track to a next track, referred to as end-of-row-turns), travel a total distance of about <NUM> meters, over a total duration of time of about <NUM> seconds, in order to complete all the tracks to cover the entire field <NUM>. In comparison, for the track layout shown in <FIG>, the vehicle would make only a total of <NUM> turns (which is <NUM> turns less than <NUM> turns), travel a total distance of only <NUM> meters (which is <NUM> meters less than <NUM> meters), over a total duration of time of about <NUM> seconds (which is <NUM> seconds less than <NUM> seconds).

<FIG> illustrate two examples of the direction of tracks in the field <NUM>. In the example shown in <FIG>, the tracks <NUM> are perpendicular to the horizontal axis (e.g., aligned with the North-South direction). In the example shown in <FIG>, the tracks <NUM> are tilted at <NUM> degrees with respect to the horizontal axis.

<FIG> illustrate how the direction of tracks can affect the total number of segments in a track layout. In the example illustrated in <FIG> in which the tracks <NUM> are perpendicular to the horizontal axis, many tracks <NUM> intercept the obstacles <NUM>, and thus are divided into multiple segments. In comparison, in the example illustrated in <FIG> in which the tracks <NUM> are tilted at <NUM> degrees so that the tracks <NUM> lie on either side of the row of the obstacles <NUM>, only a few tracks (e.g., the tracks <NUM> and <NUM>) intercept the obstacles <NUM> and are divided into multiple segments. In addition, the track layout shown in <FIG> includes a total of <NUM> tracks, whereas the track layout shown in <FIG> includes only a total of <NUM> tracks. Thus, there are more end-of-row-turns in the track layout shown in <FIG> than in the track layout shown in <FIG>.

Thus, the track layout shown in <FIG> can be more advantageous than the track layout shown in <FIG> as it includes less number of segments. For example, the track layout shown in <FIG> would require a total of <NUM> turns, a total distance of about <NUM> meters, and a total duration of time of about <NUM> seconds. In comparison, the track layout shown in <FIG> would require only <NUM> turns (which is <NUM> turns less than <NUM> turns), a total distance of only about <NUM> meters (which is <NUM> meters less than <NUM> meters), and a total duration of time of only about <NUM> seconds (which is <NUM> seconds less than <NUM> seconds).

According to some embodiments, a track layout can include curved tracks. <FIG> illustrate an example. The tracks <NUM> have a slight curvature (e.g., arc-shaped), and are spaced apart from each other by a spacing. Tracks with other gradual curved shapes are also possible. One of ordinary skill in the art would recognize many variations, alternatives, and modifications.

As discussed above with reference to <FIG>, <FIG>, <FIG>, and <FIG>, an area coverage planner can optimize both the offset and the direction of the tracks in a track layout. According to some embodiments, the area coverage planner can perform a multivariate optimization to obtain an optimal offset and an optimal direction of the tracks based on a heuristic objective. For example, the heuristic objective can include one of more of the following: minimum total distance traveled, minimum total duration, minimum number of turns, and maximum coverage. These objectives can be interrelated. For example, minimum total distance and minimum number of turns can help achieve minimum total duration. In the multivariate optimization, the offset and the direction of the tracks are optimized simultaneously.

After the tracks have been laid down in a work area, the next task for the area coverage planner is to generate a trajectory for an autonomous vehicle to traverse the tracks to cover the work area.

<FIG> shows an exemplary trajectory <NUM> for traversing the tracks <NUM> shown in <FIG> (the tracks are overlaid with the trajectory <NUM>). An entry point <NUM> and an exit point <NUM> can be optionally pre-defined. The trajectory <NUM> can start from the entry point <NUM>, and then continue along a section 220a of the headland guideline <NUM> onto the first track 620a. The trajectory <NUM> then traverses the tracks sequentially until it completes the last track 620b, and then continues along a section 220b of the headland guideline <NUM> to reach the exit point <NUM>. When transitioning from one track to a next track, the trajectory <NUM> can include a turn along a section of the headland guideline <NUM> (e.g., the section 220c). When transitioning from one segment to a next segment that are separated from each other by a section of the boundary <NUM>, the trajectory <NUM> can include a turn along a section of the headland guideline <NUM> (e.g., the section 220d). When transitioning from one segment to a next segment that are separated from each other by an obstacle <NUM>, the trajectory <NUM> can include a turn around the obstacle <NUM> (e.g., the turn <NUM>).

<FIG> illustrate a concept of route planning according to some embodiments. Assume that a field <NUM> with a boundary <NUM> includes a network of roads (e.g., the roads <NUM>, <NUM>, and <NUM>). Each road can have an associated unit cost of traversing that road (e.g., cost per meter). In some embodiments, each road can be specified to be a bidirectional (e.g., two-way road) or unidirectional (e.g., one-way road). The end points of each road (e.g., the end point 930a of the road <NUM>) and the cross-road points where two road cross each other (e.g., the cross road point <NUM> where the road <NUM> and the road <NUM> cross each other) can be referred to as nodes. Assume that traveling off-road (e.g., in areas where no road exits) has an associated unit cost much higher than that of the unit cost of any of the roads <NUM>, <NUM>, and <NUM>. The task of a route planner may be to find an optimal route from a starting point <NUM> to a goal point <NUM> that will incur a minimum cost.

<FIG> shows a possible optimal route <NUM> that the route planner can generate. Because the unit cost of travelling off-road has a much higher unit cost than traveling on the roads, the optimal route <NUM> (e.g., represented by the thick dashed line) can advantageously be on the roads as much as possible. The optimal route <NUM> can include a relatively short off-road segment 990a between the starting point <NUM> and a nearest road <NUM>, and a relatively short off-road segment 990b between the goal point <NUM> and a nearest road <NUM>. Assume that the unit cost for the different roads <NUM>, <NUM>, and <NUM> are about the same, the optimal route <NUM> can include an on-road section that has a shortest total distance traveled. For instance, in the example illustrated in <FIG>, the on-road section can include a first sub-section on the road <NUM>, and a second sub-section on the road <NUM>. The total distance of the first sub-section and the second sub-section can be the shortest possible distance. To avoid being off-road, transitioning from the road <NUM> to the road <NUM> occurs at the node <NUM> at which the road <NUM> and the road <NUM> cross each other.

<FIG> shows how the route-planning concept discussed above can be applied to optimizing an entry route and an exit route according to some embodiments. The tracks <NUM> and the headland guideline <NUM> form the network of roads. For the entry route, the starting point can be the entry point <NUM>, and the goal point <NUM>. The goal point <NUM> can be the beginning of the first track 620a. An optimal entry route <NUM> can include a relatively short off-road segment <NUM> between the entry point <NUM> and a nearest point <NUM> on the headland guideline <NUM>, followed by a segment along the headland guideline <NUM> to the goal point <NUM>. For the exit route <NUM>, the starting point <NUM> can be the end of the last track 620b, and the goal point can be the exit point <NUM>. An optimal exit route <NUM> can include a segment along the headland guideline <NUM>, followed by a relatively short off-road segment between the exit point <NUM> and a nearest point <NUM> on the headland guideline <NUM>.

According to some embodiments, after an optimal route has been generated, the area coverage planner can convert the route into a traversable trajectory to be used for guiding an autonomous vehicle. A traversable trajectory is one that can be executed by the autonomous vehicle given its motion limitations. For example, the autonomous vehicle may not be able to make a sharp turn due to its motion constraints. In a traversable trajectory, sharp corners can be converted into traversable corners.

<FIG> illustrate the conversion from routes into traversable trajectories according to some embodiments. <FIG> shows the entry route <NUM> (solid line) as shown in <FIG>. As illustrated, the entry route <NUM> includes a sharp corner <NUM>. <FIG> shows a traversable trajectory <NUM> (dashed line) converted from the entry route <NUM>. As illustrated, the sharp corner <NUM> in the entry route is converted into a rounded corner <NUM> in the traversable trajectory <NUM>, so that the autonomous vehicle may be able to execute the turn.

<FIG> shows the exit route <NUM> (solid line) as shown in <FIG>. As illustrated, the exit route <NUM> includes three sharp turns <NUM>, <NUM>, and <NUM>. <FIG> shows a traversable trajectory <NUM> (dashed line) converted from the exit route <NUM>. As illustrated, the sharp corners <NUM>, <NUM>, and <NUM> are converted into rounded corners <NUM>, <NUM>, and <NUM>, respectively, so that the autonomous vehicle may be able to execute the turns.

According to some embodiments, the area coverage planner can also generate a velocity profile for the traversable trajectory. The velocity profile can specify a speed for the autonomous vehicle at each respective point along the traversable trajectory. For example, the velocity profile can specify a work speed for the segments along the tracks, and specify a turn speed along turns. The turn speed is usually slower than the work speed. The velocity profile can specify transition speeds for the transitions from the work speed to the turn speed, or vice versa. The transition speeds can be determined based on the nominal acceleration of the autonomous vehicle.

<FIG> illustrate an exemplary velocity profile for the trajectory <NUM> shown in <FIG>. In <FIG>, the velocity profile is represented by dots of various sizes, the larger the dots, the slower the speed. As illustrated, the speed is substantially uniform along the segments of the tracks <NUM> (the uniform dots may appear as continuous lines), and is slower along the turns. <FIG> shows a close-up view of the velocity profile for the area <NUM> shown in <FIG> shows a close-up view of the velocity profile for the area <NUM> shown in <FIG>. In <FIG>, the dots are shown in equal time interval along the trajectory. Thus, the dots would appear to be uniformly spaced from each other if the speed is constant, and would appear to be closer to each other if the speed is decreased.

<FIG> includes the velocity profile along two adjacent tracks 620p and 620q. There is an obstacle 230a between the two tracks 620p and 620q. The track 620p does not intercept the obstacle 230a, whereas the track 620q intercepts the obstacle 230a. As illustrated in <FIG>, the speed along the track 620p is nearly constant (e.g., at work speed), as indicated by the uniform spacing between adjacent dots. In comparison, the trajectory along the track 620q includes a turn in order to get around the obstacle 230a. As illustrated in <FIG>, the speed along the track 620q slows down during the turns, as indicated by the reduced spacing between adjacent dots.

<FIG> includes the velocity profile for the end-of-row turn from one track 620r to a next track <NUM>. In this example, the trajectory for the turn has a "U" shape, including a section along the headland guideline <NUM>. Other types of end-of-row-turns are also possible, e.g., as described in <CIT> and <CIT>. As illustrated in <FIG>, the speed is reduced around the corners of the trajectory when transitioning from the track 620r to the headland guideline <NUM>, and from the headland guideline <NUM> to the next track <NUM>.

According to some embodiments, the tracks can be traversed according to various strategies. <FIG> illustrate two exemplary strategies. The thick black line indicates the trajectory. In the example shown in <FIG>, the tracks <NUM> are traversed sequentially. For example, after completing the first track 620a, the next adjacent track 620b is traversed, followed by the next adjacent track 620c, and so on and so forth, until the last track 620d is completed.

In the example shown in <FIG>, the tracks <NUM> are traversed in a "race track" pattern. For example, after completing the first track 1310a, the next track to be traversed is the sixth track 1310b, skipping four tracks in between. The trajectory can follow the headland guideline <NUM> when transitioning from the first track 1310a to the sixth track 1310b. After completing the sixth track 1310b, the next track to be traversed is the 11th track 1310c, again skipping four tracks in between. After the 11th track 1310c is completed, the next track to be traversed is the 16th track 1310d, again skipping four tracks in between. After the 16th track 1310d is traversed, the next track to be traversed is the last track 1310e (the 18th track). It then repeats the pattern of skipping four tracks by traversing the tracks 1310f, <NUM>, and <NUM>, in this order. Compared to the sequential strategy, the "race track" strategy can have the advantage that the turns from one track to a next track are wider. The trajectory can traverse the tracks in other non-sequential patterns. illustrated in <FIG>, the headland <NUM> in the periphery of the field <NUM> may not be covered. According some embodiments, the area coverage planner can include a headland pass in the trajectory. <FIG> illustrate two examples. In the example shown in <FIG>, the trajectory <NUM> (represented by the thick black line) can start from the entry point <NUM> onto the headland guideline <NUM>, and then traverse the entire headland guideline <NUM> before starting to traverse the tracks <NUM>. In the example shown in <FIG>, the trajectory <NUM> (represented by the thick black line) traverse the tracks <NUM> first (the tracks are overlaid with the trajectory <NUM>, and therefore are not visible), and then traverse the entire headland guideline <NUM> before going to the exit point <NUM>. According to some embodiments, a user can be presented with three options: (i) headland pass on entry, (ii) headland pass on exit, and (iii) no headland pass. For example, the three options can be presented to the user on a graphics user interface (GUI). The user can select one of them.

<FIG> shows a simplified flowchart illustrating a method <NUM> of area coverage planning for an autonomous vehicle according to some embodiments.

The method <NUM> includes, at <NUM>, receiving information of a boundary of a work area; and at <NUM>, receiving information of one or more obstacles located within the work area. The method <NUM> further includes, at <NUM>, laying a plurality of tracks within the boundary of the work area. The plurality of tracks are spaced apart from each other by a spacing. Laying the plurality of tracks comprises: based on (i) the information of the boundary of the work area, and (ii) the information of the one or more obstacles, performing a multivariate optimization to: (i) determine an optimal direction of the plurality of tracks, and (ii) an optimal offset for a first track from the boundary, so as to minimize a total distance of the plurality of tracks. The method <NUM> further includes, at <NUM> generating a trajectory that is traversable by the autonomous vehicle to traverse the plurality of tracks.

It should be appreciated that the specific steps illustrated in <FIG> provide a particular method of area coverage planning for an autonomous vehicle according to some embodiments. Other sequences of steps may also be performed according to alternative embodiments. For example, alternative embodiments of the present invention may perform the steps outlined above in a different order. Moreover, the individual steps illustrated in <FIG> may include multiple sub-steps that may be performed in various sequences as appropriate to the individual step. Furthermore, additional steps may be added or removed depending on the particular applications. One of ordinary skill in the art would recognize many variations, modifications, and alternatives.

The method <NUM> includes, at <NUM>, receiving information of a boundary of a work area; and at <NUM>, laying a plurality of tracks within the boundary of the work area. The plurality of tracks are spaced apart from each other by a spacing. Laying the plurality of tracks comprises: based on the information of the boundary of the work area, performing a multivariate optimization to: (i) determine an optimal direction of the plurality of tracks, and (ii) an optimal offset for a first track from the boundary, so as to minimize a total distance of the plurality of tracks. The method <NUM> further includes, at <NUM> generating a trajectory that is traversable by the autonomous vehicle to traverse the plurality of tracks.

For some applications, such as fertilizer spraying and seed spraying, the autonomous vehicle may need to be replenished with consumable materials (e.g., fertilizer or seeds) during the coverage of a work area. According to some embodiments, an area coverage planner can include replenishment planning during coverage. After a coverage trajectory (e.g., a single traversable trajectory covering the entire work area) has been generated, logistic points along the coverage trajectory at which the autonomous vehicle needs to be replenished can be computed according to a strategy. Provided with the locations of one or more refill stations adjacent to the boundary of the work area, the replenishment planner can generate a replenishment trajectory for each logistic point. The replenishment trajectory includes a first part from the logistic point to a refill station, and a second part from the refill station to a resume point.

<FIG> shows a field <NUM> with several refill stations. For example, a first refill station <NUM> can be located adjacent the entry point <NUM>, the second refill station <NUM> can be located adjacent the exit point <NUM>, and a third refill station <NUM> can be located adjacent the boundary <NUM> on the other side of the field <NUM>. The solid line indicates a trajectory <NUM> for an autonomous vehicle to traverse the tracks to cover the field <NUM>, which can be referred herein as a coverage trajectory. While traversing the coverage trajectory <NUM>, the autonomous vehicle can run out of the material at certain points (e.g., at the point <NUM>). Thus, the autonomous vehicle may need to go to one of the refill stations <NUM>, <NUM>, or <NUM> to be replenished with the material, before resuming the coverage trajectory.

According to some embodiments, the area coverage planner can first generate the coverage trajectory (e.g., a single traversable trajectory covering the entire field <NUM> while avoiding obstacles), using the methods discussed above. The area coverage planner can compute logistic points along the coverage trajectory where the autonomous vehicle would need to be replenished with the material. The area coverage planner can then generate a traversable trajectory from each respective logistic point to a respective refill station, and then from the respective refill station to a corresponding resume point. The trajectory from a logistic point to a refill station, and from the refill station to a resume point can be referred to as a replenishment trajectory.

The logistic points can be computed according to various strategies according to some embodiments. One strategy is to compute the logistic points based on threshold. In this strategy, a logistic point can be a point at which the remaining load of the material falls below a predetermined threshold. This strategy can be referred to as trigger at threshold. The threshold can be a percentage of a nominal full load (e.g., <NUM>% of the nominal full load), or can be an absolute amount of the material (e.g., <NUM> liters, assuming a nominal full load of <NUM> liters). Assuming a nominal consumption rate of the material (e.g., in liters per meter) is known and the autonomous vehicle is filled to the nominal full load each time it is refilled, a logistic point can be computed based on the distance the autonomous vehicle has traveled since the last refill based on the nominal consumption rate. In some embodiments, assuming that the autonomous vehicle stops consuming the material (e.g., stop spraying fertilizer or seeds) when it makes an end-of-row-turn, the distance traveled during end-of-row-turns can be excluded in the calculation.

<FIG> illustrates the strategy of trigger at threshold according to some embodiments. A refill station <NUM> is located adjacent to the boundary <NUM>. Assume that the coverage trajectory <NUM> (thin solid line) traverses the tracks sequentially, starting from the entry point <NUM>. It can be computed that a first logistic point will be reached at the location <NUM>. When the first logistic point <NUM> is reached, the autonomous vehicle will need to go to the refill station <NUM> to be replenished with the material. For example, the autonomous vehicle can continue to the end of the track <NUM>, and then follow the headland guideline <NUM> to the refill station <NUM> (along the thick grey line). After the refill, the autonomous vehicle can follow the headland guideline <NUM> to the track <NUM>, and then along the track <NUM> back to the first logistic point <NUM> (along the thick black line). The autonomous vehicle can then resume work by traversing along the coverage trajectory <NUM> from the first logistic point <NUM>. In this case, the logistic point is also the resume point. The trajectory from the first logistic point <NUM> to the refill station <NUM> (along the thick grey line), and from the refill station <NUM> back to the first logistic point <NUM> (along the thick black line) is referred to as a replenishment trajectory.

Additional logistic points (e.g., the logistic points <NUM> and <NUM>) can be computed in a similar manner, and the associated replenishment trajectories from each logistic point to the refill station <NUM> (along the thick grey line) and from the refill station <NUM> to the corresponding resume point (along the thick black line) can be determined. While the autonomous vehicle is traversing the replenishment trajectory (e.g., along the thick grey line and the thick black line), the autonomous vehicle can stop consuming the material (e.g., stop spraying fertilizer or seeds).

Another strategy is to compute logistic points at end-of-row according to some embodiments. In this strategy, a logistic point is always at the end of a track. For example, the replenishment planner can compute a logistic point to be at the end of a track, beyond which the autonomous vehicle may not have enough material to last through the next track. <FIG> illustrate some examples.

Referring to <FIG>, a first logistic point <NUM> can be computed to be at the end of the track <NUM>. After the autonomous vehicle has completed the track <NUM>, it would not have enough material to last through the next track <NUM>. Thus, the autonomous vehicle would need to go to one of the refill stations <NUM> and <NUM> to be replenished with the material. The replenishment planner can generate a replenishment trajectory from the logistic point <NUM> to a first refill station <NUM> (along the thick grey line), and after the refill, from the first refill station <NUM> to the beginning of the next track <NUM> (along the thick black line). The beginning of the next track <NUM> is the resume point <NUM>.

Referring to <FIG>, a second logistic point <NUM> can be computed to be at the end of the track <NUM>. The replenishment planner can generate a replenishment trajectory from the second logistic point <NUM> to the second refill station <NUM> (along the thick grey line), and after the refill, from the second refill station <NUM> to the resume point <NUM> at beginning of the next track <NUM> (along the thick black line).

Referring to <FIG>, a third logistic point <NUM> can be computed to be at the end of the track <NUM>. The replenishment planner can generate a replenishment trajectory from the third logistic point <NUM> to the second refill station <NUM> (along the thick grey line), and after the refill, from the second refill station <NUM> to the resume point <NUM> at the beginning of the next track <NUM> (along the thick black line).

<FIG> shows all three replenishment trajectories. As illustrated, in the strategy of trigger at end-of-row, the logistic point is always at the end of a track, and the resume point is always at the beginning of a next track. While the autonomous vehicle is traversing a replenishment trajectory (e.g., along the thick grey line and the thick black line), the vehicle can stop consuming the material (e.g., stop spraying fertilizer or seeds).

<FIG> shows a simplified flowchart illustrating a method <NUM> of area coverage planning with replenishment planning for an autonomous vehicle according to some embodiments.

The method <NUM> includes, at <NUM>, receiving information of a boundary of the work area; at <NUM>, receiving location information of one or more refill stations for replenishing the material; and at <NUM>, receiving information of a current amount of the material left in the autonomous vehicle. The method <NUM> further includes, at <NUM>, based on the information of the boundary of the work area, laying a plurality of tracks within the boundary of the work area so as to minimize a total distance of the plurality of tracks. The plurality of tracks are spaced apart from each other by a spacing. The method <NUM> further includes, at <NUM>, generating a coverage trajectory that is traversable by the autonomous vehicle to traverse the plurality of tracks.

The method <NUM> further includes, at <NUM>, based on (i) the coverage trajectory, (ii) the location information of the one or more refill stations, (iii) the current amount of the material left in the autonomous vehicle, and (iv) a nominal full amount and a nominal consumption rate of the material by the autonomous vehicle, determining one or more logistic points along the coverage trajectory at which a remaining amount of the material reaches a threshold. The method <NUM> further includes, at <NUM>, for each respective logistic point of the one or more logistic points, generating a respective replenishment trajectory for the autonomous vehicle. The respective replenishment trajectory includes: a first part from the respective logistic point to a respective refill station of the one of the one or more refill stations for replenishing the autonomous vehicle with the material, and a second part from the respective refill station to the respective logistic point for the autonomous vehicle to resume traversing the coverage trajectory.

It should be appreciated that the specific steps illustrated in <FIG> provide a particular method of area coverage planning with replenishment planning for an autonomous vehicle according to some embodiments. Other sequences of steps may also be performed according to alternative embodiments. For example, alternative embodiments of the present invention may perform the steps outlined above in a different order. Moreover, the individual steps illustrated in <FIG> may include multiple sub-steps that may be performed in various sequences as appropriate to the individual step. Furthermore, additional steps may be added or removed depending on the particular applications. One of ordinary skill in the art would recognize many variations, modifications, and alternatives.

The method <NUM> further includes, at <NUM>, based on (i) the coverage trajectory, (ii) the location information of the one or more refill stations, (iii) the current amount of the material left in the autonomous vehicle, and (iv) a nominal full amount and a nominal consumption rate of the material by the autonomous vehicle, determining one or more logistic points along the coverage trajectory at which the autonomous vehicle needs to be replenished with the material. Each respective logistic point is at an end of a respective track. The method <NUM> further includes, at <NUM>, for each respective logistic point of the one or more logistic points, generating a respective replenishment trajectory for the autonomous vehicle. the respective replenishment trajectory includes: a first part from the respective logistic point to a respective refill station of the one of the one or more refill stations for replenishing the autonomous vehicle with the material, and a second part from the respective refill station to a beginning of a next track for the autonomous vehicle to resume traversing the coverage trajectory.

<FIG> shows a simplified diagram of a system <NUM> for an autonomous vehicle according to some embodiments. The system <NUM> may include an area coverage planning module <NUM>, and a user interface <NUM>. In some embodiments, the user interface <NUM> may also include a display.

The area coverage planning module <NUM> can include one or more computer processors configured to perform area coverage planning according to the embodiments described above. The area coverage planning can include laying down the tracks and generating a traversable coverage trajectory for the autonomous vehicle. In some embodiments, the area coverage planning module <NUM> can also perform replenishment planning according to the embodiments described above. Replenishment planning can include computing logistic points according to various strategies, and generating replenishment trajectories. In some embodiments, the coverage trajectory and the replenishment trajectories can be displayed in a display (e.g., the display in the user interface <NUM>).

The system <NUM> can include a memory <NUM>. The memory <NUM> can store information needed for the area coverage planning module <NUM>, as well as other information. For example, the memory <NUM> can store information about a work area, such as a boundary (e.g., a geofence) and headland guidelines. The memory <NUM> can also store information of any static obstacles located within the boundary, the location of an entry point, and the location of an exit point. The memory <NUM> can also store information of the locations of one or more refill stations. The memory <NUM> can also store information about the nominal full load of a material that the autonomous vehicle may spray along the coverage trajectory, and the nominal consumption rate of the material, as well as a threshold load for triggering a logistic point. The memory <NUM> can also store computer-executable instructions to be executed by the computer processors of the area coverage planning module <NUM>. The memory <NUM> may comprise a volatile memory random access memory (RAM), or nonvolatile data storage device such as a hard disk drive, flash memory or other optical or magnetic storage device. In some embodiments, the area coverage planning module <NUM> may include its own memory.

The system <NUM> may include a global navigation satellite systems (GNSS) antenna <NUM> attached to the autonomous vehicle, and a GNSS receiver <NUM> coupled to the GNSS antenna <NUM>. The GNSS receiver <NUM> may be configured to determine a current position of the vehicle based on the satellite signals received from GNSS satellites. In some embodiments, the system <NUM> can also include an optional position correction system <NUM>. The position correction system <NUM> may include an antenna <NUM> and a receiver <NUM> for receiving correction data from a reference station or a network of reference stations. For example, the position correction system <NUM> may include a differential global positioning system (DGPS). The correction data may be used by the GNSS receiver <NUM> to determine a more precise position of the vehicle (e.g., to millimeter or sub-millimeter accuracies). In some embodiments, the GNSS receiver <NUM> may be an independent unit separate from the system <NUM>.

The system <NUM> can include other sensors <NUM>. For example, the other sensors <NUM> may include LiDAR sensors for obstacle detection, inertial measurement units or IMUs (e.g., accelerometers and gyroscopes), wheel angle sensors, and the like.

The system <NUM> can include a vehicle controller <NUM>. The vehicle controller <NUM> may be configured to operate the vehicle based on the sensor data (e.g., including GNSS data and other sensor data) and the trajectories determined by the area coverage planning module <NUM>. For example, the area coverage planning module <NUM> can output a coverage trajectory and/or a replenishment trajectory, along with a velocity profile, to the vehicle controller <NUM>, so that the vehicle controller <NUM> can cause the autonomous vehicle to follow the coverage trajectory and/or the replenishment trajectory. The velocity profile includes a respective speed for each respective point along the coverage trajectory and/or the replenishment trajectory.

In some embodiments, the various components of the system <NUM> may be interconnected with each other via a bus <NUM>. In some other embodiments, the various components may be connected with each other in other ways.

Claim 1:
A method of area coverage planning for an autonomous vehicle, the method comprising, at a computer system:
receiving information of a boundary (<NUM>) of a work area (<NUM>);
laying a plurality of tracks (<NUM>) within the boundary (<NUM>) of the work area (<NUM>), the plurality of tracks (<NUM>) being spaced apart from each other by a spacing, wherein laying the plurality of tracks (<NUM>) comprises:
based on the information of the boundary (<NUM>) of the work area (<NUM>), performing a multivariate optimization to: determine (i) an optimal direction of the plurality of tracks (<NUM>), and (ii) an optimal offset (<NUM>) for a first track (<NUM>) from the boundary (<NUM>), so as to minimize a total distance of the plurality of tracks (<NUM>); and
generating a trajectory that is traversable by the autonomous vehicle to traverse the plurality of tracks (<NUM>).