#006 Autonomous Mower Planning

last updated: 9/29/23

The path generated by the program.

I did this project as part of my work for Mowze, a startup robotic mowing company. I was the sole developer of this aspect of the project and got permission to post my results here.

The goal of the project was to create a program that implemented the path planning method described in A novel solution with rapid Voronoi-based coverage path planning in irregular environment for robotic mowing systems, a 2021 paper by Kuo-Chun Huang, Feng-Li Lian, Chien-Tung Chen, Chung-Hou Wu & Chao-Cheng Chen.

The algorithm works in two main stages. First, it creates a number of 'sections', that are Boustrophedon (sweep left as long as possible, move up a row, speed right as long as possible, move up a row, repeat) motions. Then, it connects the sections using Voronoi points and Dijkstra's algorithm. I modified the algorithm to optimize the order and direction of the Boustrophedon sections. The ordering of sections (can be imagined as a set of line segments) can be thought of as the Rural Postman Problem, which is (disappointingly) NP-Hard. I used a simple greedy algorithm that searched for the closest (start or end point of a) section to the current section that had not been visited yet. This was good enough. I also optionally add the obstacles and border to the final path.

Step 1

The user is presented with a 3 step process to use the generator. First, the upload a Mission Planner style .waypoints file. The file should have all points that describe both the border and the obstacles.

Step 2

Second, the user must define the obstacles and border. If the waypoints file was generated using our mowers, which log points every .5 meters, I can autodetect where the border starts and stops. This will be the standard when in production. Otherwise, the user must define the start and end point manually. Using tab and arrow keys one can pretty quickly define a mission, this one took me about a minute.

This obstacle and border was auto-detected due to close spacing of points. The outline was generated by driving the mower around the perimeter and obstacle.

The border and obstacles had to be manually entered due to the inconsistent spacing of the border.

The map can be zoomed and panned. When you zoom in, arrows appear on the path to indicate direction.

Lastly, the user configures the plan. Plans take between 5ms and 150ms to generate, depending on the complexity of the path, so it is easy to tweak variables and instantly see results. (Thank you svelte for all that wonderful performance...). You can set the strip angle or have it be automatically determined. An estimated time is determined using the mowers top speed, acceleration, deceleration, angular speed, angular acceleration.

The waypoints can be downloaded as a .waypoints file. The blade on off behavior is encoded in a set servo waypoint.