Mowing and Search Algorithms

Although Kupe is aimed at being a rover, I intend to use it as a platform to explore mowing and search algorithms. A typical search algorithm aims to get from point A to point B using the shortest route. A mower aims to cover *everything* in a specified area which calls for different algorithms.

This type of algorithm is called Coverage Path Planning; we have an area and aim to cover all of it during our travels. There may be obstacles in the path and we may need other algorithms to deal with those.

Coverage Path Planning

A good CPP algorithm tries to:

• Cover 100% of free space
• Minimize overlap (don’t mow twice)
• Minimize turns (turning costs power)
• Be robust to obstacles
• Work with imperfect localization

There are several CPP algorithms and I intend to use Grid Coverage, namely travel in straight lines, row-by-row turning at the boundaries. This is what I used in Moana, but now I want to tie it to an internal map of the area being covered.

Simple grid coverage works fine for rectangular areas but not for obstacles. It will need augmenting using other search algorithms when it encounters obstacles. One approach is to have smaller grids connected by shortest path search algorithms. This is called a boustrophedon pattern. However, baby steps. I need to integrate it with a map and use some form of localization first.

So, given a virtual map, the aim is to use Grid CPP to visit all available location on the map. When we hit an obstacle, we will fall back to A* (A-star) to navigate from the current position, to the next available location in the CPP route. Thereafter, we will continue with CPP

April 2026