Allegrobotics - Pathfinding
Algorithms for pathfinding around the farm, using RRT variants

Disclaimer

Warning: This is a work in progress. The maps you see are simulations only to test the algorithms.

Motivation

It is tempting to program all missions as static paths with a GIS program, and send out the rover to follow the path and complete the mission. However, consider the following mission-pair:

Mission One

  • Starting from the refill/recharge point, go into paddock X and start to mow the appropriate area (with parallel mow lines or whatever)
  • After 50 minutes, or when battery charge goes below 30%, find your way back to the refill/recharge point.

Mission Two (after refill/recharge)

  • Go back to the mowing area, and take up from where Mission One left off
  • Continue to mow
  • Rinse and repeat

Ideally the rover has to find its way to an arbitrary point in the paddocks, and find its way home again. While solving this problem on a a 7 acre toy-farm might seem a little artificial, history produces strange artefacts. The fence and building layout is actually complex enough to provide a serious test for pathfinding navigation algorithms such as RRT, or RRT*.

Software

RRT was discovered around 1998. It is technique which creates a directed graph from a continuous space. RRT* is an optimisation of RRT which (hopefully) gives better results which don't wander all around the space inefficiently.

There are many animated examples of RRT on YouTube (check links below) which show its highly effective nature on a number of continuous space problems. However many of them are optimised to work in fundamentally different environments to farming with fences.


It is easy to optimise a rover which moves towards the goal avoiding blobs in the way. It is much harder to create a path which has to find small gates in number of interconnected large paddocks.

Farm environments typically have two interesting features.

  • there are frequently few obstacles within a paddock. Farmers try to remove obstacles within paddocks because of the general inconvenience and risk to equipment. Typically a dam, pump house, tree trunk or a occasional outcrops of rock might appear in an otherwise clear paddock.
  • fences are long and gates are small. It may be necessary to move a rover many hundreds of meters just to simply move from one side of a fence to another.
Most published examples of use do not have these features, suggesting the an agricultural optimisation of these algorithms would be quite different to others.

The modifications to the RRT algorithm

To be documented.

Results

Finding a route to the north-east paddock. There is a funny loop near the tractor shed, but otherwise it did okay. Actually such loops would be easy to optimise away in a final path processing step (though the obvious optimisation would not necessarily adapt for Ackermann steering rovers).


Finding a route to the north-west paddock. A slightly strange route, but again it did okay.


Finding a route to the south-west paddock which involves navigating the driveway. Not bad.


Finding a route into the orchard. Particularly challenging because of all the trees.


This is actually a fail - it didn't find a solution in the time allowed for the run. It looks like it would have eventually, but this is not an easy point to navigate from. In practice, running a rover this close to the dam would be a pretty stupid thing to do anyway, so it's not really a problem.

Software libraries

    500 lines of java using math.geom2d

Raspberry Pi load

Running this efficiently on the Raspberry Pi might involve a rewrite in C++.

The future

    Obstacle detection While this technique show promise, it will still require obstacle detection in the real world - what if one of the gates is closed? What if the idiot children leave the Tesla parked near the shed?
    Ackermann Steering Solving the problem for an Ackermann steering. This involves adding a third dimension to the Robot Pose, and also more complex transition rules.

Also, there is a lot of work still to do to make this a workable solution. In particular, the GPS/GNSS behaves poorly near sheet metal walls (presumably because of RF reflections) so any path near them is fundamentally dangerous. There are also other no-go areas on the farm (eg unmarked wood-piles, storage etc). Also the gates are generally closed to keep in the stock. Either some of the gates would have to be auto-opened, or the stock would have to be moved to other parts of the farm when the robots were working.

... and there would be a bunch of other miscellaneous issues.

Cool links

There are a cool bunch of RRT and RRT* simulations on YouTube.

Leave a comment

Something I'm doing wrong? Solved my problems? Got a better idea? Got a similar problem?
Think I might have solved your problem? Ninety-nine problems, but your robot ain't one? Say so ..