Intelligent
Routing

Overview

Our state-of-the-art routing solution supports arbitrarily complex fields, headland navigation, and many other configurable options. On this page you'll find examples + explanations of the various routing features, as well as new and exciting experimental prototypes.

Turn Modelling

We support various turn types, which are chosen automatically depending on a combination of field geometry and equipment characteristics. If two tracks are within 3 swath widths of each other, we will attempt to directly connect them with a turn. If the turns are farther apart, or there is no turn that can fit, we instead will perform what we call a headland traversal, explained in more detail below.

Track-Track Connectors

If making a direct connection from a track to track, we support the following types of turns:

U-Turn

When turn radius is less than 50% of the swath width, U-turns such as this will be generated for adjacent tracks. Note there is an option to extend the straight segment to the headland to give more room to turn and to minimize trampling.

Perfect U-Turn

When turn radius is exactly 50% of the swath width, Perfect U-turns such as this will be generated for adjacent tracks, with no straight segment inbetween.

Bulb Turn

When turn radius is greater than 50% of swath width, a bulb turn is used to connect two adjacent tracks. This would only be used if a U-turn could not fit.

P Turn

If the headland is at a sharp angle compared to the turn, and the turn radius is large enough, we support P turns to minimize the amount of steering required to make the turn.

Track-Headland Connectors

If a direct connection can't be made, we will instead connect onto a nearby headland, performing one or more headland traversals to connect two tracks. This allows us to create paths between almost any two tracks in the entire field without invalidly crossing the field outside of a headland zone.

Arc Connectors

By default, we try to use arc connectors, which have constant curvature and have a turn radius at least as large as minimum turning radius. This allows for a smooth transition from the track to the headland without any jerky motions. Turn may be automatically shortened if there is not enough room to complete the turn without the vehicle leaving the boundary.

Dubins Connectors

If an arc connector fails, a search is performed to try to connect a dubins connector onto various points on the headland in the desired direction of travel, until a valid one is found that minimizes total angle change.

Fallback Connector

If all else fails, we create a fallback connector, which just directly joins the two points (either between two tracks or track-headland) and shows up in the UI as a big red line. User must manually make this turn before continuing the route.

Turn Shortening

If a turn can't fit from a track to another track or to a headland without any part of the vehicle leaving the boundary, and if the "Shorten Tracks" setting is enabled, the turn will be shortened, i.e turn sooner than the end of the track so that it can make it. Unfortunately this causes a miss, unless your vehicle can reverse before making the turn (future work would support this functionality if there is desire for it). If you notice that a lot of area is being missed, you likely don't have enough headlands based on your vehicle's turn radius, and may need to rerun the plan with more headlands. On the roadmap is to automatically suggest # of headlands based on your field and equipment.

Turn Extending

In some situations, you may wish to actually extend your turns into the headland further. This can be enabled by toggling the "Extend Turns Into Headlands" setting. If a turn can fit, it will be extended so that it touches the outermost headland. This allows for more room for turning, to straighten out, and minimizes trampling. Future work includes always latching onto headlands when possible to even further minimize trampling.

Shortened Headland Connections

Adjacent turns that are shortened to fit on the headland will instead be converted to headland traversals if possible. This can be enabled by toggling "Prefer Shortened Headland Connections". Future work includes enabling this for all track-track connections.

Without Setting

The turn is shortened to just touch the headland, but doesn't actually traverse along it.

With Setting

Connections are made onto the headland between adjacent connectors, minimizing trampling.

Headland Navigation

When a direction turn from track to track isn't possible, the routing solution will instead switch over to headland navigation mode. Connectors from the tracks to the headlands will be made, followed by a series of headland traversals and connectors between headlands.

Full Headland Traversals

Automatically work all the headlands in your field with additional planning, as we efficiently find a path to and from each headland in a group, minimizing the amount of non-working distance travelled while preversing wheel traffic. Our algorithm can work from any starting or ending track on the headland. The algorithm prevents any turns that might collide with the obstacle, ensuring safety.

Prefer Outermost Headland

When performing headland traversals, the algorithm defaults to attaching to the middle most exterior headland, as it provides a good tradeoff between room for turning and straightening out. Enabling "Prefer Outermost Headland" will instead attach to the outermost headland.

Default behaviour

Headland traversals naturally attach to the middle most headland.

Turns Attached to Outermost Headland

When "Prefer Outermost Headland" is enabled, all headland traversals attach to the outermost exterior headland if possible.

Multiple Internal Track Routing

Example of a complicated situation where the route solver finds a path through multiple headlands, working them, as well as all the internal tracks.

Algorithms / Patterns

Default Algorithm

By default, we model the problem as an instance of a Agricultural Routing Problem (ARP), which is the agricultural version of the well-known Vehicle Routing Problem. Its what's known as NP-hard, meaning there are no algorithms that can efficiently solve all possible instances of the problem perfectly. That is why we have developed a custom meta-heuristic solver to solve the ARP, encoding grower standards into the cost matrix itself, generating a route that can navigate even the most complex fields, in the matter of minutes or even seconds.

Our routing solver calculates the distances to/from every possible pair of tracks on the field, using exact routes for tracks in roughly the same area, and smart estimates for tracks on opposite side of the field. This creates what's known as a distance matrix, which is then fed into our propreitary solver to optimize a path that traverses every track and headland, while minimizing non-working distance. No prior assumptions are made about the working pattern, the results are solely based off the calculated distances between them. This allows the solver to have incredible foresight at times, skipping one or more tracks that aren't immediately obvious to a user, only to then use those tracks to efficiently navigate out of a situation where a traditional approach would have trapped it.

Avoid Skipping Passes

When enabled, the cost of traversing to an adjacent track is halved. This encourages (but by no means forces) a more straight pattern, but at the potential cost of additional non-working distance, or in the below case, more missed area. In the example below, another headland might be preferred in order for the turns to fit.

Continuous Tracks (Boustrophedon)

A predefined back-and-forth pattern, starting on one side of the field and going to the other. Great for simple fields and those with small obstacles.

If you notice that there are too many headland traversals, we recommend running our default algorithm and toggling "Avoid Skipping Passes". This will avoid extreme cases of headland traversals, at the cost of losing uniformity.

Clustered Spiral

A predefined pattern that enforces always at least a skipping of N tracks in a move forward then move back kind of pattern. Works best in simple fields and those with small obstacles.

Capacity Based Routing

If user specifies a capacity and flow rate for their vehicle, they can access our various capacity based routing features. Currently we have two separate workflows for this. The first is Single Vehicle, which is the kind of routes shown above, where theres no staging area, and only a single vehicle working. The other is Capacitated Multi Vehicle, where one or more vehicles start at a staging area, and can work tracks until they have reached their capacity, at which point they will traverse back to the staging depot via the headlands.

Multi Vehicle w/ Staging Area

Currently an experimental setting and a WIP. Routes may not be well optimized and may perform strangely or even outright crash until we develop them further.

If enabled, a staging area will be determined by first extending the median track in the field and choosing a point on the boundary that intersects it. The idea is for a roughly central staging area, but future work includes the option to define one or more possible staging areas to return to. Staging areas are defined as a single point on the boundary currently.

The route will now start and end at the staging area, and when required, the vehicle will perform a headland traversal back to the staging area to refill/dropoff. The optimizer itself is taking into account the cost of returning to and from the staging area, which is different than the above methods, which are done as a post-processing over a regular route without capacity. In the academic literature this is known as a Capacitated Vehicle Routing Problem, or CVRP.

Experimental

A collection of upcoming and experimental features the Verge team is working on. Please reach out to us for any questions or recommendations of what you'd like to see next.

Steerable Smoothing

If an angle change is greater than some threshold in a headland or curved track, we mark it as needing to be smoothed. There may be multiple of these near each other as the below image shows. Then we smartly try to embed circles with the vehicles turn radius in such a way that minimizes the missed area between passes. After smoothing, we get a headland pass that respects the vehicles curvature constraints and minimizes missed area. Future work includes incorporating crosshatch patterns with reversals to minimize missed area.

Before Smoothing

Example results of a standard offset algorithm. Brown points have angle change greater than steerable threshold

After Smoothing

After smoothing has been applied. Multiple angle violations have been combined together into one consistent smooth turn.

Headland Crosshatches

If an angle is too sharp, and the user doesn't wish to have skipped area, we can instead support crosshatches, where we extend the lines out and connect them with an arc respecting the vehicles turning radius. Realistically the below image would have only the sharpest corners as crosshatches, the rest using the above mentioned smoothing.

Trailed Implements

A vehicle may have one or more trailed implements attached behind it. We are currently modelling the main vehicle with ackermann steering geometry, with the hitch point a fixed distance behind the back axle of each vehicle + implement. Multiple implements may be chained together, and we assume all implements are non-powered. We run kinematic simulations for the vehicle traversing our turns to show where the boundaries of your equipment system will be, alerting you of any dangerous situations of leaving the field. Future work will include improving turns to account for the trailed implement, optimizing turns as to minimize stress on the hitch, any incorporating this into our search algorithm.

Grid based Representation of the Field

A promising approach often used in autonomy is to discretize the working area as a grid, where a type of search known as hybrid A* can be used to find the shortest steerable path between any two points on the grid. Below is an example part of a field discretized in such a manner. The green sections are headland passes and are considered preferable to travel, brown is valid headland space, and red is dangerous area that might leave the field.

All current approaches are based on geometric methods, and thus may have difficulty finding shortcuts. An example might be the bottom section there, where a traditional approach of "always follow headland" may cause the user to needlessly drive around the obstacle, causing additional nonworking time. Running a search algorithm we can see that we may be able to drive across here. This rough estimate can help drive a finer-tuned search, validating that your vehicle along with any implements can actually make this shortcut

An example of a vehicle searching for a path in a simpler grid system. Notice how the planner incorporates the vehicle dimensions. The various green and brown arcs correspond to possible trajectories that the algorithm has searched through before finding the final solution. Future work includes a penalization function that avoids closely hugging walls like this video, as well as various performance improvements, preferring to traverse along headlands, and generally integrating this into our full routing solution.

More infomation coming soon about potential use cases and further examples.

Configuration Options

A list of possible options passable to the routing algorithm, as well as a brief explanation. For more information please see our API docs or reach out to us.