Multi-Robot Optimal Surveillance Coverage for Unknown Environments
In this work we introduce a methodology for optimal surveillance coverage using a team of Micro Aerial Vehicles (MAVs), based on maps created by a monocular-vision approach online and in real-time. A state-of-the-art visual-SLAM algorithm tracks the pose of the camera while, simultaneously, building an incremental map of the surrounding environment. The generated map is processed and serves as an input in an optimization procedure using the CAO.
To define the surveillance coverage problem we can identify two main optimization objectives, which can be expressed as follows:
- (O1) The part of the terrain that is “visible” — i.e. that is monitored — by the robots is maximized;
- (O2) The team members are arranged so that for every point in the terrain, the closest robot is as close as possible to that point.
In most of the existing approaches, the terrain morphology is assumed to be convex and/or known. In such cases the problem of multi-robot surveillance coverage can be seen to be equivalent to a standard optimization problem where the robot trajectories are generated according to a gradient-descent or gradient-descent-like methodology.
However, in the case where it is required that both of the objectives (O1) and (O2) are simultaneously addressed and the terrain’s morphology is non-convex and/or unknown, standard optimization tools are not applicable anymore as these tools require full knowledge of an objective function that depends on the unknown terrain’s morphology.
To overcome the above-mentioned shortcomings of the existing approaches for multi-robot surveillance coverage, we propose a new solution that is based on (CAO) algorithm. The main advantage of CAO as compared to standard optimization tools is that it does not require the explicit knowledge of the objective function to optimize; CAO instead requires that at each time instant a value (measurement) of this objective function is available. As a result, if it is possible to define an appropriate objective function, whose analytical form may be unknown but is available for measurement for every given team configuration, the CAO methodology will be directly applicable to the problem of surveillance coverage treated in this work.
Our intent is to define this objective function such that it simultaneously takes into account both the criteria (O1) and (O2), trying to obtain a compromise between maximizing visible area and minimizing the distance of the robots to points in the environment. It has to be emphasized that, apart from rendering the optimization problem solvable, the CAO-based approach preserves additional attributes that make it particularly tractable: it can easily handle a variety of physical constraints and limitations and it is fast and scalable. The methodology has been successfully tested on a large variety of 2D and 3D non‐convex unknown environments. Moreover, the methodology has been applied using real‐data from the Birmensdorf test area and the ETHZ’s hospital area.
- Fig. 1. 3D Path followed by a robot team in a coverage scenario in Birmensdorf area
- Fig. 2. Final configurations of three robot teams starting from different initial positions.
CAO has been implemented in C#. The graphical user interface of the optimization framework and its functionality are presented in the following video.
CAO has been integrated within the sFLY framework and has been tested in real missions using a team of three aerial vehicles. The functionality of the sFLY framework is presented in the following video.
You can also check a cool article about the sFLY project at the IEEE’s Spectrum Magazine.
Related Publication(s):
The Two Dimensional Case
A. Renzaglia, L. Doitsidis, A. Martinelli and E.B. Kosmatopoulos, “Adaptive-based Control for Distributed Multi-Robot Coverage,” 2011 American Control Conference, pp. 468-473. pdf
A. Renzaglia, L. Doitsidis, A. Martinelli and E.B. Kosmatopoulos, “Cognitive-based Adaptive Control for Cooperative Multi-Robot Coverage,” in proceeding of the IEEE International Conference on Robotics and Intelligent System (IROS’10), pp.3314-3320, Taipei, Taiwan, 2010. pdf
A. Renzaglia, L. Doitsidis, A. Martinelli and E.B. Kosmatopoulos, “Adaptive-based, Scalable Design for Autonomous Multi-Robot Surveillance,” in 49th IEEE Conference on Decision and Control (CDC), pp. 4618-4624, Atlanta, Georgia, USA, 2010. pdf
The Three Dimensional Case
L. Doitsidis, A. Renzaglia, S. Weiss, E. Kosmatopoulos, D. Scaramuzza, R. Siegwart, “3D Surveillance Coverage Using Maps Extracted by a Monocular SLAM Algorithm,” 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1661-1667, San Francisco, USA. pdf
A. Renzaglia, L. Doitsidis, A. Martinelli and E.B. Kosmatopoulos, “Multi-Robot 3D Coverage of Unknown Terrains,” in proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference, pp. 2046-2051, 2011. pdf
A. Renzaglia, L. Doitsidis, A. Martinelli and E.B. Kosmatopoulos, “Multi-Robot 3D coverage of unknown areas,” International Journal of Robotics Research, Vol. 31, no.6, pp. 738-752, May 2012. (Sage link)
Lefteris Doitsidis, Stephan Weiss, Alessandro Renzaglia, Markus W. Achtelik, Elias Kosmatopoulos, Roland Siegwart, Davide Scaramuzza, “Optimal Surveillance Coverage for Teams of Micro Aerial Vehicles in GPS-Denied Environments using Onboad Vision,” Autonomous Robots, in press. (Springer link)
This work is performed in the context of the sFLY project (www.sfly.org), in collaboration with A. Renzaglia & A. Martinelli from INRIA (France).
