Complete Coverage Path Planning of a Random Polygon - a Frobomind Component

Complete coverage path planning of a random polygon - A FroboMind component

Sebastian Aslund2, Kjeld Jensen1, Rasmus N. Jørgensen1

1Institute of Chemical Engineering, Biotechnology and Environmental Technology

2The Maersk Mc-Kinney Moller Institute

University of Southern Denmark, Campusvej 55, 5230 Odense M, Denmark

Corresponding author: [email protected]

Complete coverage path planning has many cases where it is useful for modern agriculture. Examples are grass mowing, weeding, harvesting, demining etc. Each of these tasks may be solved by a random walk repeated a sufficient number of times. However this approach is highly inefficient and will not guarantee complete coverage.

Figure 1: Computer Assisted Slope Mowing Robot also known as Casmobot (www.casmobot.dk) which with a complete coverage plan will result in a significant more efficient slope mowing

The broad range of applications where coverage path planning is useful makes it is not only limited to agriculture, but also usable for other sectors. This means significant research and effort have been put into the development of coverage path planning algorithms.

One of the earlier works is [1] where the article address the problem with the trapezoidal decomposition on a polygon, which is based on the geometry of the boundaries. Instead it propose a new method, the boustrophedon decomposition, which is based on the changes in the connectivity. The decomposition is simple, straightforward and effective, but leaves the issues with finding the optimal path open and does not go into details with coverage path planning besides the decomposition.

[2] and [3] extends the work done in [1] to the realm of uncertainty and presents a more complete solution. Since the environment is unknown, then it is not possible to optimize the path planning and the morse decomposition is introduced to detect changes in connectivity based on a random range scan. Furthermore is cycle path introduced to avoid missing critical points, points that defines a change in connectivity. While [2] and [3] are very complete in their coverage of coverage path planning, then they assumes the existence of a physical boundary which is not a sound assumption within agriculture. The ability detect obstacles and decompose the environment at run-time is useful, but in agriculture the environment is often sparse and the obstacles are usual small, doing a decomposition might result in a longer path and execution time compared to a simple avoidance and boundary following.

[4] and [5] present a new approach to complete coverage path planning where a neural network is used for path planning, each neuron represent a specific sub-space and is connected to its neighboring neurons. The shunting equation is defined so obstacles only affect the path planning locally while unvisited neurons attracts globally. The idea of using neural networks is interesting and integrates dynamic obstacles seamlessly, seen in [6], where a rolling window is used to locally determine a path using the neural network together with the values returned by a range scanner. A problem with the neural network approach is the resolution, for [4][5] and [6] then each neuron represents a sub-space of the environment corresponding to the size of the robot. Furthermore is an 8-way connectivity used, which means the robot is restricted to move in eight specific directions. The result is that complete coverage cannot be guaranteed for a random polygon representing the environment, only a very high coverage can be guaranteed with a risk of a jerky motion along edges that does not have an orientation corresponding to one of the eight possible directions of the robot.

[7] presents a solution to complete coverage path using the split-and-merge method and allows different process directions. The optimal process direction for the different sub-regions is approximated by a driving direction search based on the relative efficiency, remaining area to process and the normalized distance. The article uses the trapezoidal decomposition and later merges them together through a set of requirement, but the result is not entirely optimal compared to the boustrophedon decomposition, which would have been a better choice. While the article presents an interesting way to search and find the optimal process direction for the different sub-regions, then it does not take the motion or connection between the regions into account, which can possibly lead to long paths when moving from one region to another. An alternative to finding the near optimal process direction is to abandon the idea that the process is executed by moving up and down in straight lines. Here [8] presents a method to generate curved tracks which consist of piecewise linear segments, while the result shows that using curved tracks improves the total path length over pure linear tracks, then it also shows that it can increase the total path length depending on the parameter settings. Curved tracks do therefore not present a general solution and is sensible to parameter choices.

The aim of this work is to have an universal solution for complete coverage which will be a component in the FroboMind architecture suggested by Kjeld Jensen in [9].

Figure 2 sketches the overall algorithm, the input is either a sequence of positions retrieved by logging the GPS coordinates while driving around the boundaries of the region using Real Time Kinematic - Global Positioning System (RTK-GPS) or having a list of positions defining the corners, which could have been found manually by tools like Google Maps. For the first case is linear segmentation used to reduce the number of vertexes due to the continuously logging and will also help reducing the jitter caused by the errors in the retrieved GPS location, sways of the antenna etc.

Besides the GPS coordinates, then the second input is the tool size, which is used to create the configuration space of the polygon. This will help executing and verifying the complete coverage algorithm: If the path covers the internal part of the configuration space including its boundaries, then complete coverage is achieved.

Figure 2: Abstract flow of the method including the preprocess step

After the configuration space is found, then the main algorithm can be executed. Here the boustrophedon decomposition from [1] is used to divide the region into easy processable sub-regions. However the modular design makes it possible to later include variable process direction using the cost function from [7] or curved tracks from [8] if it is beneficial given the structure of the region.

While the boustrophedon decomposition does an excellent job, then there exist special cases where it fail. The work will here present a general method, which eliminates the risk of failure due to these special cases, but it can also be applied on other decomposition methods like the trapezoidal decomposition.

Figure 3: Perimeter of the area to be covered e.g. by the Casmobot mower in figure 1. The surface is approximated/represented by a polygon with n-vertexes

Figure 4: Determine the configuration space based on the tool size and original polygon

To determine the path between the sub surfaces then a search algorithm is used, here the depth-first is used together with a look-up table to optimize the resulting path.

Knowing the initial position, then the global path can be found, which defines the sequence of sub-regions that needs to be visited in order to perform a complete coverage path planning. Here there result is 1-3-0-3-2-3-4, using the look-up table is it reduced to 1-3-0-2-4.

The local path planning for each sub-region is then found and merged with the path from a neighboring sub-polygon, the result is a single path that covers that ensures complete coverage of the whole region.

Figure 5: Decomposing the region and finding the complete coverage path

As seen in figure 5 then the movement between sub-polygons have a risk of going outside the polygon due to the optimizations done by the look-up table, the work will here present a method to detect and solve this problem.

Compared to previously work done within the field of coverage path planning this work presents a complete, universal and generic solution where all the steps in the process is included: Segmentation of a data set, creation of a configuration space, decomposition of a polygon, global and local path planning.

To achieve this, a series of known algorithms are used including some tweaks and improvements to create a solid foundation for the FroboMind architecture and the agricultural community to explore and develop new algorithms for coverage path planning. Furthermore will the project be tested and verified by implementing it on a vehicle based on the FroboMind architecture.

Acknowledgement

We would like to acknowledge Ph.D. student I.A.F.A. Ibrahim from The Department of BioSystems Engineering Aarhus University for constructive feed back during the writing process and Jensen Hansen from for cooperation on the slope mower.

References

[1] Howie Choset. 2000. Coverage of Known Spaces: The Boustrophedon Cellular Decomposition.Autonomous Robots 9, pp. 247-253

[2] Ercan U. Acar, Howie Choset. 2002. Sensor-based Coverage of Unknown Environments: Incremental Construction of Morse Decompositions. The International Journal of Robotics Research Volume 21, Number 4, pp. 345-366

[3] Ercan U. Acar, Howie Choset, Yangang Zhang, Mark Schervish. 2003. Path Planning for Robotics Demining: Robust Sensor-based Coverage of Unstructured Environments and Probabilistic Methods. The International Journal of Robotics Research Volume 22, Number 7-8, pp. 441-466

[4] Chaomin Lou, Simon X. Yang, Deborah A. Stacey, Jan C. Jofriet. 2002. A Solution to Vicinity Problem of Obstacles in Complete Coverage Path Planning International Conference on Robotics and Automation

[5] Simon X. Yang, Chaomin Luo. 2004. A Neural Network Approach to Complete Coverage Path Planning

System, Man and Cybernetics Volume 31, Number 1

[6] Xuena Qiu, Jiatao Song, Xuejun Zhang, Shirong Liu. 2006. A Complete Coverage Path Planning Method for Mobile Robot in Uncertain Environment6th World Congress on Intelligent Control and Automation

[7] Timo Oksanen, Arto Visala. 2009. Coverage Path Planning Algorithms for Agricultural Field MachinesJournal of Field Robotics Volume 26, Number 8, pp. 651-668

[8] I.A. Hameed, D.D. Bochtis, C.G. Sørensen and M. Nørremark. 2010. Automated generation of guidance lines for operational field planning. Biosystems Engineering Volume 107, Issue 4, pp. 294-306

[9] Kjeld Jensen, Anders Bøgild, Søren H. Nielsen, Martin P. Christiansen, Rasmus N. Jørgensen. 2011. FroboMind, a conceptual architecture for agricultural field robot navigation. NJF seminar 441, Automation and System Technology in Plant Production CIGR section V & NJF section VII conference, 30 June - 2 July 2011 Denmark (Publication within this conference).

NJF Conference: