Skip to content

Code pertaining to coverage path planning and area division.

Notifications You must be signed in to change notification settings

18alantom/CoveragePathPlanning

Repository files navigation

Coverage Path Planning

Contains python implementations of various algorithms used for coverage path planning and one for area division used in mCPP.

DARP - Area Division

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.

DARP Image source notebook. Preprint and Repository.


Coverage Path Planning

  • 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.

Spanning Tree Coverage

Creates a minimum spanning tree from the given area for generation of the coverage path. STC is run individually on the sub regions. DARP and STC

Boustrophedon

An online algorithm that uses A* to get to the next starting point. Boustrophedon is run individually on the sub regions. DARP and Bous

Wavefront

An algorithm that uses a distance to central point based gradient to traverse the region. Waverfront is run individually on the sub regions. DARP and Wavefront


Other Stuff

Fuelling Algo

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. Fuelling while STC

Tests

Tests on the CPP and Fuelling algos with metrics are here. Tests on STC running on the test area maps. STCTests

Running on Shapefiles

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. Raster

The shapefile on a map tile with the reprojected path as an overlay. ShapefileOverlay More here (execrable reprojections, pls hlp).


Should Do

  • Fix issue with DARP.
  • Add latest optimizaiton of STC.

About

Code pertaining to coverage path planning and area division.

Resources

Stars

Watchers

Forks