Implementation for Multi-Agent Coverage in Urban Environments
Team - Members:
Md Ishat E Rabban , Email: ier@umd.edu Jingxi Chen, Email: ianchen@terpmail.umd.edu
Vishnu Dutt Sharma, Email: vishnuds@umd.edu Kulbir Singh Ahluwalia, Email: kulbir@umd.edu
Persistent Monitoring means long-term continuous monitoring of an area. In this task, a robot (or team of robots) needs to move around the area to continuously observe/search it. Continuous monitoring is needed to maintain confidence in the observations. When a robot moves away from an area, its certainty about the state of that area decreases (higher certainty for the areas monitored recently). Thus to gain more certainty, the robot will need to revisit each area it has visited previously. Over a long time, this would look like the robot(s) moving in a loop unless there is a change in the area.
Some of the real-life examples where we need persistent monitoring include (1) environmental monitoring, like forest fire monitoring, where robots keep patrolling the forest to keep an eye on fire incidents, (2) infrastructure inspection, like manhole cover inspection (Tulabandhula et al. [2]), where one must inspect the infrastructure frequently to report any problem; and (3) surveillance, where we should monitor discrete location (like windows, doors) to watch out for intruders (Michael et al. [3]).
Persistent monitoring is quite similar to the mapping problem. The key difference between the two is that in mapping we do not need to revisit the areas already explored. Using multiple robots helps in decreasing the time required to cover the while areas, as well as reduces the burden on a single robot (one robots can recharge while others monitor its area). We focus only on the path-planning part of this problem and use one of the solutions from Patel et al. [1] for it.
First, we provide a high-level overview of the multi-UGV persistent monitoring problem. In this problem, we are given a discrete grid-based environment. Each UGV is equipped with a 360-degree sensor with limited range to visually monitor the environment. The environment contains obstacles. The grid cells occupied by the obstacles are not visible to the UGVs. The objective is to plan paths for the UGVs such that the free grid cells (i.e., cells not occupied by obstacles) within the environment are repeatedly monitored by the UGVs.
To formalize the idea of repeated monitoring of the grid cells, we introduce the concept of latency. Let C denote the set of all free grid cell . Each grid cell c in C has a latency value (denoted by l_c) in the range [0, l*]. The latency of a cell varies according to the last time the cell was visible from some UGV. If a cell c is visible from some UGV in the current time step, l_c is set to 0. Otherwise, if c is visible from no UGVs currently, l_c increases linearly by d at each time step, until it reaches l*. The latency thus indicates the time since the cell was last observed.
Now we formally define the multi UGV persistent monitoring problem. We assume that in each time-step, each UGV generates a set of candidate trajectories, one of which will be followed in the current time step. Given the number of time-steps, T, the goal of the multi UGV persistent monitoring problem is to select one trajectory for each UGV at each time-step, such that the average value of latency of all free grid cells over all time-steps is minimized.
rcm.mkvThe video above shows a team of UGVs in action solving the persistent monitoring problem. Here blue circles and red boxes represent UGVs and obstacles respectively. Purple arrows show the direction of the current trajectory of the UGVs. Shades between green and black represent latency of the cells, where pure green and pure black stands for 0 and l* respectively.
Persistent monitoring can be solved by multiple robots sharing the task of monitoring. In our scenario, it means dividing the whole area into multiple parts, and each robot monitoring the area assigned to it. Here, we use Multi-Agent Coverage Algorithms by Patel et al. [1] with a few adaptations for persistent monitoring. Patel et al. study Multi-Agent Lawnmower Algorithm and Multi-Agent Voronoi Cover Algorithm for multi-agent coverage and among six solutions for coverage problem. We combine the two algorithms for persistent monitoring, which can be thought of as a dynamic coverage problem.
We assume that all the robots (UGVs) have infinite resources for functioning i.e. they can keep running without needing any recharge. This relaxes the problem to convert it into a trajectory finding problem. This assumption is valid when the area to be monitored is small or the robots have efficient power sources to keep them running for a long time. Additionally, we have only static obstacles in our environments.
With these assumptions, our problem effectively is to find out a good way to divide the area to be monitored among the robots and to plan the paths for monitoring for each robot.
We solve the multi-agent persistent monitoring problem by dividing it into two sub-problems as follows:
Voronoi Partitioning Problem: In this problem, we split the whole environment into Voronoi Partitions of approximately equal area. Each such non-overlapping region is assigned to each UGV for monitoring. We implement a modified version of Algorithm 7 presented in [1] to solve the Voronoi partitioning problem.
Lawnmower Coverage Problem: Also known as Boustrophedon cellular decomposition (Choset et al. [4]), the objective of this problem is to determine a path for each UGV inside its assigned region which enables the UGV to persistently monitor the region. We implement a modified version of Algorithm 1 presented in [1] to solve the Lawnmower coverage problem.
The following video shows a demonstration of the Voronoi partitioning and the lawnmower coverage. Here, the six magenta polygons show the Voronoi regions assigned to the six UGVs. Each UGV follows a lawnmower like zigzag path to monitor its assigned region. In the next two sections, we discuss these two algorithms in detail.
mp2.mkvA Voronoi cell/region is a cell that contains a generator point x with the property that all points in this cell are closer to x than any other generator points. A collection of all such Voronoi regions is called the Voronoi diagram.
To make the Voronoi cells inside the rectangle, we take the reflection of the generator points along the sides of the rectangle. Then, we compute the boundaries of the Voronoi cells. This has the advantage that we get the side of the rectangle as one of the cell's boundaries and prevent the formation of cells that are infinitely big.
Input: Rectangular boundary, N starting points of robots
Outputs: N Voronoi partitions (within the rectangular boundary)
The steps to generate the Voronoi partitioning are as follows:
4N out-of-boundary points + N original robot locations<- Reflecting all N starting points along 4 edges
Perform Voronoi partitioning once on the 5N points
For the N Voronoi cells corresponding to N original locations of robots, compute N centers.
Assigning N robots to the corresponding centers, and only keep these N points as new starting points
N Voronoi cells that partition the boundary <- Repeat step 1-4 until the partitioning converges
We use the reflection trick along the boundary in order to enable Voronoi partitioning to get cells bounded by the boundary edges.
The robot starting locations are random and to ensure that the region of all Voronoi cells are roughly equal, we iteratively partition and assign agents to the center of cells.
Visualizing Voronoi partitioning after starting from the generator points provided as arguments to the script. Green dots are the generator points also known as "sites" , the black boundaries are equidistant from the two nearest generator points and the black dots are the vertices of the Voronoi cells. The vertices are equidistant from three closest generator points.
The lawnmower algorithm is a commonly used algorithm to solve coverage and exploration problems. In this algorithm, a set of parallel scanlines inside a polygon are selected and a zigzag like path along the scanlines is followed by the agent which ensures coverage of the polygon. A sample lawnmower path is shown in the right.
We faced the following challenges while implementing the lawnmower algorithm to solve the multi UGV persistent monitoring problem.
In the paper by Patel et al., the agents are UAVs, hence they can fly over the obstacles. But in our setup of the persistent monitoring problem, the agents are UGVs, which cannot go over or through the obstacles.
Hence we modify the algorithm so that the UGVs go around the obstacles when moving along a scanline. And when the UGVs move from one scanline to the next scanline, we determine the shortest path avoiding the obstacles using the BFS algorithm. Please refer to the video above to see these modifications in effect.
Unlike the discussed paper, the performance of the lawnmower algorithm for the persistent monitoring problem is critically dependent on the distance between successive scanlines. If the distance between successive scanlines is too high, some grid cells may never be visible. On the other hand, if the distance between successive scanlines is too low, it will result in performance degradation.
In our implementation, we set the distance between successive scanlines such that the scanlines are farthest apart while maintaining that all grid cells between the scanlines are visible from the scanlines.
We use a rectangular environment consisting of 200 x 150 cells. The dimension of each cell is 1m x 1m. At each time-step, the UGVs can move to one of its 4 adjacent cells (i.e., north, south, east, and west). A UGV cannot move to a cell occupied by obstacles. It also cannot go outside the rectangular environment.
We use d = 0.002, and l* = 1.0. Thus, if a grid cell is not visible from any UGV for 500 timesteps, its latency reaches the threshold value of 1.0 and remains there until the cell becomes visible from a UGV.
We generate rectangular axis-aligned obstacles uniformly at random over the rectangular environment. The length and width of the obstacles are chosen uniformly at random within the range 5m to 15m. We use three environments marked out by the density of obstacles, which are called highly, moderately, and sparsely occluded environments, which contain 80, 40, and 20 obstacles respectively. The following figure shows samples of the three types of environments.
Variations of the environment used in the experiments (Left to right): Highly Occluded Environment (80 obstacles), Moderately Occluded Environment ( 40 obstacles), and Sparsely Occluded Environment
We evaluate the performance of the baseline algorithm using the metric average latency. By average latency, we mean the average value of latency of all the free grid cells over time-steps 0 through T. In our experiments, we use T=10000.
The algorithms are implemented using C++ (lawnmower algorithm) and Python (Voronoi partitioning algorithm). The experiments are conducted on a core-i7 2GHz PC with 8GB RAM, running Microsoft Windows 10. The visualization tool used is OpenGL.
To evaluate the baseline algorithm, we vary the number of UGVs (from 2 to 10, in increments of 2) and the visibility range of the UGV sensors (from 5m to 20m, in increments of 5m), and compare the average latency for highly, moderately, and sparsely occluded environments. The default value of the number of UGVs is 6, and the visibility range is 10m. The experimental results are shown in the figure below. In the figure, the legends high, mid, and low denote highly, moderately, and sparsely occluded environments respectively. Note that a lower value of average latency represents better performance and vice versa.
Effect of number of UGVs and visibility range of the UGVs on the average latency
The experimental results show that increasing the number of UGVs results in a decrease in average latency because a higher number of UGVs can cover a larger portion of the environment. Also, increasing the visibility range decreases the average latency, because higher-visibility range allows the UGVs to monitor wider space in the environment. In both experiments, the performance improves with decreasing obstacle density, because in a densely occluded environment, the UGVs need to go around the obstacles more frequently in comparison with a sparsely occluded environment.
The code for this project is available at following GitHub repo: CMSC818B_MiniProject_2 - https://github.com/kulbir-ahluwalia/CMSC818B_MiniProject_2
Requirements:
This code runs on Windows. The files uploaded on the repo use Visual Studio. We have used VS 2019 for building it.
However, you can install OpenGL and run with your choice of development environment as well. The CodeBlocks project is available here.
Python3 is required for running voronoi.py.
Steps:
Voronoi Partitioning Algorithm
Run python3 voronoi.py 0 0 800 600 6, where the first four argument represent the coordinates of the bottom left and upper right corner of the window/rectangle and the last argument represent the number of robots. This will generate a file named voronoi.txt.
Lawnmower Algorithm
Copy the voronoi.txt file into the OpenGL_Visual_Studio/OpenGL/ folder
Open the OpenGL.sln file in visual Studio
Update Line 30 in main.cpp to #define inputfilename "voronoi.txt"
Build and Run the project in Visual Studio
Sub-Experiments:
For experiment on changing the number of UGVs: Generate voronoi.txt with the required number of robots (last argument)
For experiment on changing the number of obstacles: Update Line 25 of main.cpp as desired
For experiment on changing the visibility range of UGVs: Update Line 26 of main.cpp as desired
Following are the important components of the project:
---- voronoi.py
---- voronoi.txt
|---- OpenGL_Visual_Studio/
|---- OpenGl.sln
|---- OpenGl/
|---- main.cpp
voronoi.py: Python file to generate Voronoi partitions on a rectangular area. This program takes 5 arguments as input. This generates a files named vornoi.txt which is described below
e.g. python3 voronoi.py 0 0 3.5 4.0 5, where
(0, 0) is the (x, y) coordinates of the lower left corner of the boundary rectangle
(3.5, 4.0) is the (x, y) coordinates of the upper right corner of the boundary rectangle
5 is the number of UGVs, which is equal to the number of Voronoi cells to be generated
You can also use the command "python3 voronoi.py -h" to get a detailed explanation of all the input arguments
voronoi.txt: This file contains the description of the Voronoi Partitions. The format of the text file is shown in the following figure.
Here, the first line shown the number of Voronoi cells, i.e., the number of UGVs. Then the description of all the Voronoi cells follows. Each cell is described by the number of vertices, followed by the Cartesian coordinates of the vertices in counter-clockwise order. Please note that the lower left coordinates of the boundary rectangle must be set to (0, 0) for smooth running of the project.
Format of the voronoi.txt file which is the input to the Lawnmower algorithm
OpenGL_Visual_Studio/: This directory contains the files required for running the experiment and the visualization.
OpenGL.sln: The Visual Studio solution file for the project .
OpenGL/: This directory contains the main codes and input files for the experiments. For running the experiments, voronoi.txt must be copied in this directory.
main.cpp: This is the main file of the project. This contains the parameters for defining the entities in environment (number of obstacles, visual range, etc.)
One can modify the problem parameters inside the main.cpp program, which allows the user to change the number and size of the obstacles, the size of the grid cells, the visibility range of the UGVs, and l*. A snapshot of the input parameters inside the main.cpp file is shown below. Here N and M are the numbers of grid cells along the X and Y axis, and cpx is the size of each grid cell. Please note that N*cpx and M*cpx must match the dimensions of the boundary rectangle. crange is visibility range of the UGV sensors. numobs is the number of obstacles. osa and osd are the average and deviation of the dimension of the obstacles in terms of grid cell size. lmax stands for l*. While changing the input parameters of the lawnmower algorithm, a user should keep in mind that the number of obstacles is not too high to fit inside the boundary rectangle.
Input parameters of the Lawnmower algorithm
Patel, Shivang, et al. "Multi-Agent Coverage in Urban Environments." arXiv preprint arXiv:2008.07436 (2020).
Tulabandhula, Theja, Cynthia Rudin, and Patrick Jaillet. "The machine learning and traveling repairman problem." International Conference on Algorithmic Decision Theory. Springer, Berlin, Heidelberg, 2011.
Michael, Nathan, Ethan Stump, and Kartik Mohta. "Persistent surveillance with a team of mavs." 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2011.
Choset, Howie, and Philippe Pignon. "Coverage path planning: The boustrophedon cellular decomposition." Field and service robotics. Springer, London, 1998.