The coverage path planning problem refers to the task of determining an optimal path for an autonomous agent to navigate through an area, ensuring that the entire area is covered. This problem is commonly encountered in various domains, including robotics, agriculture, cleaning operations, and surveillance.
The objective of coverage path planning is to systematically visit all points or regions of interest within the area while minimizing travel distance.
The presented algorithm operates under the assumption that the region is partitioned into square cells, where each cell can be classified as either an obstacle or an open space. The autonomous agent is restricted to moving in a manner parallel to the grid lines, without any additional time required for turning.
These instructions will get you a copy of the project up and running on your local machine for development and testing purposes.
CMake — an open-source, cross-platform family of tools designed to build, test and package software.
OR Tools — a fast and portable software for combinatorial optimization.
Pygame — a computer graphics and sound libraries designed to be used with the Python.
Download current repository to your local machine. Use
git clone https://github.com/NDamirov/CoverageProblem.gitor direct downloading.
Built current project using CMake.
cmake -B build
cmake --build build The input file should consist of a table of symbols representing the area to be covered. In this table, the # symbol indicates an obstacle, while the * symbol represents a free space. Each symbol corresponds to a square cell in the coverage region.
The output file consists of a table of symbols representing the area to be covered. In this table, the # symbol indicates an obstacle, while the | and - symbols represent vertical and horizontal ranks respectively. It also may have path of agent if needed.
To launch an application you need to have input file:
./build/CoverageProblem input.txt output.txt--ranks_only — if you need only ranks decomposition without path generation.
--slow — if you want to use more effective slow algorithms (A-Star instead of Manhattan distance).
Just path the output file to visualizer:
python3 visualizer/visualizer.py output.txt