Contains python implementations of various algorithms used for coverage path planning and one for area division used in mCPP.
DARP : Divide Areas Algorithm for Optimal Multi-Robot Coverage Path, is an equal area division algorithm for multiple robot coverage paths.
- DARP visualization on a test area map.
- Left most images are area maps that have roughly the same number of assigned cells.
- Point gradients are traversable L1 distance based.
- Region gradients pertain to the computation of the Ci matrix as given in the paper.
Image source notebook. Preprint and Repository.
- Gradients are created from the starting points.
- Green points are the start points, red are the end points and white is the coverage path.
- Images source notebook.
Creates a minimum spanning tree from the given area for generation of the coverage path.
STC is run individually on the sub regions.
An online algorithm that uses A* to get to the next starting point.
Boustrophedon is run individually on the sub regions.
An algorithm that uses a distance to central point based gradient to traverse the region.
Waverfront is run individually on the sub regions.
Uses the shortest L1 path to get to the fuel point from a point in the coverage path that minimizes the residual fuel. The Pink
- Pink path is the coverage path, light blue is the fuelling path.
- Yellow is the start point and red is the end point.
- The algorithm displayed is STC.
- Animation source notebook, algo notebook.
Tests on the CPP and Fuelling algos with metrics are here.
Tests on STC running on the test area maps.
The Area division and coverage path algorithms were run on shapefiles pertaining to actual areas but reprojection of the generated path is (highly) inaccurate.
The rasteriszed map with the path overlay.
The shapefile on a map tile with the reprojected path as an overlay.
More here (execrable reprojections, pls hlp).
Should Do
- Fix issue with DARP.
- Add latest optimizaiton of STC.