# DARP: Divide Areas Algorithm for Optimal Multi-Robot Coverage Path Planning

10 min readSep 1, 2021

--

One of the fundamental problems in robotics is determining an optimal path involving all points of a given area of interest while avoiding sub-areas with specific characteristics (e.g., obstacles, no-fly zones, etc.). In the literature, this problem is often referred to as coverage path planning (CPP), but can also be found as sweeping, exhaustive geographical search, area patrolling, etc. This problem is directly related to a plethora of robotic applications, such as vacuum cleaning robots, seabed mapping, demining robots, automated harvesters, planetary exploration, and search and rescue operations.

# Multi-Robot Coverage Path Planning (mCPP) | Problem Definition

Such a problem is usually defined as follows:

## Given:

1) An area of interest

2) Robots’ initial positions

## Objective:

Design robot paths that completely cover this area of interest in the minimum possible time

Usually, complete coverage is needed to reconstruct the underlying environment (e.g., seabed, ground morphology, cm-level mapping, etc.).

Of course, this can even be achieved by a single robot moving randomly in the space after a (probably) long period of time. However, the limited battery capabilities of autonomous vehicles, in addition to the constantly increased areas that need to be covered/monitored, have motivated the deployment of several autonomous devices with advanced path planning mechanisms.

## What are the key attributes that affect the performance?

The bad news is that the mCPP setup is at least NP-hard [1]! Ok, mCPP is hard, but what about single robot CPP?

# Single robot Coverage Path Planning Problem

Design the trajectory for a single robot to cover the whole operational area in the minimum possible time:

Good news at last! There exists a dedicated O(n) algorithm, called Spanning-Tree Coverage (STC) [2], that computes the optimal robot path under some mild discretization assumptions, where n denotes the size of the area.

## Spanning-Tree Coverage (STC) Algorithm in a nutshell

Apart from being able to tackle the CPP setup in linear time with respect to the size of the grid, STC also designs a coverage path that

1. finishes in the starting position
2. is actually valid from any starting point inside the operational area

Both features are of paramount importance. The first one eases the utilization of the generated trajectory as a patrolling path that can be executed continuously, enabling efficient persistent coverage. The latter enables the deployment of the mobile robot in different locations without having to change a thing in the mission plan!

# Can the STC algorithm be useful in the multi-robot CPP domain?

## Yes! → Opt_MSTC Algorithm [3]

Opt_MSTC Algorithm [3]

1. Extract a single path using STC algorithm

2. Each robot follows the segment that starts from its initial position till it reaches the starting position of any other robot

+O(n) independent of the number of robots

+non-backtracking solution

+complete coverage

+no mismatch between the current position and starting location

-Uneven robot trajectories. Highly dependent on the initial positions of the robots

The following illustration depicts the influence of the initial positions of the robots on their resulting paths:

It is worth mentioning that the structure of the spanning tree can be tuned to favor a multi-robot setup with specific initial positions. However, there is no analytical methodology to completely remove the effect of the initial position of the robots on the resulted quality of the solution.

## Relax backtracking constrain

Recognizing such an inefficient task allocation, many algorithms have been proposed to mitigate the effect of robots’ initial positions by relaxing the backtracking constrain of the original mCPP setup. The most representative approach is Multi-robot Forest Coverage (MFC) [4], a polynomial-time heuristic algorithm capable of constructing spanning trees for each robot.

+complete coverage

+no mismatch between the current position and starting location

+significant improvement over Opt_MSTC

+improved fairness among robots’ paths

-produced solution can be at most 16 times greater than the optimal one

-backtracking solution

In simple words, this family of approaches demonstrated that it was beneficial to sacrifice the non-backtracking property in exchange for more balanced robot paths.

# Exploit STC in mCPP domain with area division

STC algorithm can optimally tackle the single-robot CPP problem under some mild discretization assumptions. How can we utilize this effectively?

Main idea: Define areas for each robot, and then apply STC algorithm to each one of them.

By design, the STC paths inside these areas are going to be optimal, with respect to the optimality conditions defined earlier. But the catch here is that these paths are only optimal for the divided subparts, and the overall mCPP problem might not be appropriately tackled. Therefore, any such division should meet the following area division objectives to constitute an optimal solution after the appliance of the STC algorithm inside the separate robot regions:

Having translated the original mCPP setup to an equivalent area division setup, we should now shift our attention to the algorithms/methodologies that could address such a setup.

## Voronoi space partitioning

Probably the first approach that comes to mind is the Voronoi space partition:

How many of the area division objectives have been met?

By applying Voronoi space partition, several conditions are already met, however,

the failure to construct equal regions, independently of the robots’ initial positions (3rd objective) is a big deal!

Technically, such a methodology would be pretty similar to Opt_MSTC [3], and the overall quality of the solution would strongly depend on the initial positions of the robots.

Let’s see this with an example:

The final image graphically illustrates the Voronoi space partition based on the Euclidean distance matrices. The cyan robot will cover 32 cells, while the red robot will only cover 4 cells. Assuming that both robots have the same moving and sensing capabilities and can operate simultaneously, the above grid will be covered in 32 x [the time need to scan one grid cell] (completion time for the robot with the longer task).

Let’s now assume that we have some other evaluation metric (not the Euclidean one), as it is depicted below:

Using this evaluation metric instead of the Euclidean distance results in a fair assignment of 18 cells per robot, reducing the overall completion time by 43%. With the above assignment matrix, we may now apply “blindly” the STC algorithm in each robot territory and ensure that we reached the optimal solution for the original mCPP setup.

The takeaway message is that Voronoi partitioning coupled with some other metric function can satisfy the previously defined area-division objectives and therefore tackle the original mCPP problem.

But how can we find such a metric function that strongly depends on the area morphology and the initial positions of the robots?

# Divide Areas based on Robots’ Initial Positions (DARP)

That’s exactly the goal of Divide Areas based on Robot’s Initial Positions (DARP) algorithm [5].

## Core idea:

> Retain the assignment process from Voronoi partitioning and

> Tune each robot’s metric function to meet the 3rd (equal division) objective without violating the others.

DARP algorithm stems from 2 elements:

## 1. There is a metric to evaluate area equality:

> [Important] The number of cells that should be assigned to each robot is known apriori.

## 2. Update robots’ metric tables using a multiplier:

Combining these two elements, we can construct DARP algorithm version 0.5:

In essence, the DARP algorithm follows a cyclic coordinate descent optimization scheme updating each robots’ territory separately but towards achieving the overall mCPP objectives.

+convergence guarantees from the coordinate descent algorithms

+fast optimization procedure

+very easy to implement

-Spatial connectivity inside each robot’ territory is not guaranteed

## Deal with spatial disconnectivity

Although in the original Voronoi partitioning, spatial connectivity was guaranteed by design, now, in some cases is violated. This phenomenon is due to the fact that now the metric function for each robot, over which the assignment process is implemented, is no longer a distance function. For example, the following figure illustrates the initial partitioning (left-hand side) based on the Euclidean distance, and the subfigure on the right-hand side illustrates the assignment after some iterations.

It is evident that the purple region is disconnected, and therefore with such an assignment, the non-backtracking guarantee is now at risk. To tackle this issue, an extra connectivity matrix is introduced. The rationale behind the calculation of this connectivity matrix is as follows:

In essence, the DARP algorithm incentivizes closed shape regions around the robot’s initial position and attempts to eliminate all the others, as is graphically illustrated in the following image:

The following pseudocode presents the DARP algorithm [5], which also encapsulates the connectivity matrix:

At a glance, the operation of the DARP algorithm coupled with STC for each robot region is illustrated in the following figure:

During the optimization process and depending on the difficulty of the mCPP setup, robots’ territories are expected to change formation several times till the convergence to a fair and spatially connected division:

## Beyond fair division

The DARP algorithm, as defined in version 1.0 pseudocode, is tuned to provide equal-area division among the operational robots. However, there are cases where a custom-defined percentage of coverage is more preferable. Such cases could include scenarios with heterogeneous robots, different battery levels, or other human-imposed reasons (e.g., underutilize a specific robot to be readily available for a follow-up mission). To cope with such custom-defined percentages of coverage, the following change in the objective function should take place:

In a nutshell, compared to DARP version 1.0, only the update rule for the ith robot is going to change to encompass the robot-specific percentage:

An example of such a path-planning with 3 robots with 50%, 30%, and 20% requested percentages of coverage is illustrated in the following figure:

# Material

Paper: Zenodo

GitHub repositories: Java, Python

ROS integration: Wiki

# Acknowledgments

Big thanks to Savvas Apostolidis and Aliki Stefanopoulou for their helpful comments on the original draft of this article.

# References

[1] Rekleitis, I., New, A.P., Rankin, E.S. and Choset, H., 2008. Efficient boustrophedon multi-robot coverage: an algorithmic approach. Annals of Mathematics and Artificial Intelligence

[2] Gabriely, Y. and Rimon, E., 2001. Spanning-tree based coverage of continuous areas by a mobile robot. Annals of mathematics and artificial intelligence

[3] Agmon, N., Hazon, N. and Kaminka, G.A., 2006, May. Constructing spanning trees for efficient multi-robot coverage. ICRA 2006

[4] Zheng, X., Koenig, S., Kempe, D. and Jain, S., 2010. Multirobot forest coverage for weighted and unweighted terrain. IEEE Transactions on Robotics

[5] Kapoutsis, A.C., Chatzichristofis, S.A. and Kosmatopoulos, E.B., 2017. DARP: divide areas algorithm for optimal multi-robot coverage path planning. Journal of Intelligent & Robotic Systems