Coverage path planning for a flock of aerial vehicles to support autonomous rovers through traversability analysis ACTA IMEKO ISSN: 2221-870X December 2019, Volume 8, Number 4, 9 - 12 ACTA IMEKO | www.imeko.org December 2019 | Volume 8 | Number 4 | 9 Coverage path planning for a flock of aerial vehicles to support autonomous rovers through traversability analysis Dario Calogero Guastella1, Luciano Cantelli1, Domenico Longo1, Carmelo Donato Melita1, Giovanni Muscato1 1Università degli Studi di Catania, Dipartimento di Ingegneria Elettrica, Elettronica e Informatica, Viale Andrea Doria 6, 95125 Catania, Italy Section: RESEARCH PAPER Keywords: unstructured environments; photogrammetry; terrain traversability analysis; UAV/UGV cooperation Citation: Dario Calogero Guastella, Luciano Cantelli, Domenico Longo, Carmelo Donato Melita, Giovanni Muscato, Coverage path planning for a flock of aerial vehicles to support autonomous rovers through traversability analysis, Acta IMEKO, vol. 8, no. 4, article 3, December 2019, identifier: IMEKO-ACTA-08 (2019)-04-03 Editor: Yvan Baudoin, International CBRNE Institute, Belgium Received November 22, 2018; In final form April 2, 2019; Published December 2019 Copyright: This is an open-access article distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. Funding: The presented work is in the framework of the CLARA PON project. The Project CLARA (CLoud plAtform and smart underground imaging for natural Risk Assessment) is supported by MIUR under the program PON R&C SCN_00451 Corresponding author: D. C. Guastella, e-mail: dario.guastella@dieei.unict.it 1. INTRODUCTION The problem with the autonomous navigation of an Unmanned Ground Vehicle (UGV) in outdoor environments, which are most of the times unstructured environments, cannot be considered as having been fully solved in the current robotics literature. In particular, path planning, one of the key elements in the general problem of robot navigation, is still difficult in such scenarios due to the difficulty of taking into account many issues simultaneously e.g. robot kinematics and stability and terrain geometry [1]. Furthermore, most robotics research has been carried out on structured environments, such as roads, indoor spaces, and factories, where the vehicle is expected to move within clearly defined regions. A rather common approach to coping with the problem of autonomous outdoor navigation has been to employ Unmanned Aerial Vehicles (UAVs) in order to provide an aerial overview of the considered environment or for drone-based mapping [2], [3], [4]. At the same time, photogrammetric 3D reconstruction from aerial surveys has gained more and more relevance over the years, thanks to the enhanced quality of the results and the increased computation power available [5], [6]. Such 3D modelling, belonging to the wider class of structure- from-motion approaches, can provide an accurate representation of the environment across which the ground vehicle has to move, both from the geometrical perspective and from the appearance perspective, thanks to texture mapping. These features allow the performance of a reliable terrain traversability assessment [1] on the recreated environment model. Although such processing of the environment on 3D models has been widely adopted in the literature [4], [7], only recent examples exploit photogrammetry from airborne imagery for this purpose [8], [9]. ABSTRACT In rough terrains, such as landslides or volcanic eruptions, it is extremely complex to plan safe trajectories for an Unmanned Ground Vehicle (UGV), since both robot stability and path execution feasibility must be guaranteed. In this paper, we present a complete solution for the autonomous navigation of ground vehicles in the mentioned scenarios. The proposed solution integrates three different aspects. The first is the coverage path planning for the definition of UAV trajectories for aerial imagery acquisition. The collected images are used for the photogrammetric reconstruction of the considered area. The second aspect is the adoption of a flock of UAVs to implement the coverage in a parallel way. In fact, when non-coverable zones are present, decomposition of the whole area to survey is performed. A solution to assign the different regions among the flying vehicles composing the team is presented. The last aspect is the path planning of the ground vehicle by means of a traversability analysis performed on the terrain 3D model. The computed paths are optimal in terms of the difficulty of moving across the rough terrain. The results of each step within the overall approach are shown. mailto:dario.guastella@dieei.unict.it ACTA IMEKO | www.imeko.org December 2019 | Volume 8 | Number 4 | 10 In this article, an integrated strategy for solving the problem of rover path planning in unstructured environments is presented based on the previous experience of the authors in the field. The three main aspects considered herein are: 1) the coverage path planning for aerial vehicles, discussed in section 2; 2) the assignment of the coverage regions to each member of a flock of UAVs, described in section 3; 3) the costmap derived from the traversability assessment on the environment model, reported in section 4. Finally, in section 5, a brief description of the experimental hardware setup is given, while some considerations about the proposed approach are reported in the concluding section. 2. COVERAGE PATH PLANNING Coverage path planning refers to a special kind of planning algorithm used for large regional surveys. Although such planning has been used for a large variety of applications on several kinds of vehicle (ranging from ground [10], [11], to underwater vehicles [12], [13]), here, we focus on aerial vehicles only. In particular, an offline coverage path planning method is proposed, designed for trajectory planning with static 3D models of the environment. Such approaches are essentially the opposite of the so-called online methods, where the environment model is dynamically built and can change over time [14]. In our solution, the first step is to define the Region of Interest (ROI) to survey as a 2D top-view area over a georeferenced map. In particular, we consider a georeferenced Digital Elevation Model (DEM) of the environment. A DEM is a gridded representation of the environment, and its cells contain the height values of the 3D structure. Although this type of model does not allow us to include multi-layered or overhanging structures, it offers a helpful 3D representation of the environment, being a fair compromise between the complexity and detail of the model. After that, non-coverable zones within the ROI are defined, namely those zones above which we do not want the UAV to fly. These zones can be defined as a sequence of vertices, thus obtaining polygonal zones. At this point, the whole area is decomposed into free-to-fly subregions via an exact cell decomposition algorithm i.e. the Morse-based decomposition [15]. It is an exact decomposition because all the available free area is included in the subregions, without overlaps. As suggested by the name, this decomposition algorithm is based on an analysis of the singular points of a suitably defined Morse function. By considering different Morse functions, a wide variety of decomposition patterns can be obtained. In this work, two simple functions have been considered, thus obtaining two linear decompositions: one parallel to the vertical axis and the other parallel to the horizontal axis of the map frame. An example of georeferenced DEM, the ROI defined over it (in green), and the two types of decompositions are shown in Figure 1. Easting and northing coordinates (in metres) are respectively reported along the x and y axes, according to the UTM (Universal Transverse of Mercator) convention. Eventually, coverage trajectories within each region are defined. These trajectories are used for the photogrammetric analysis and reconstruction. In fact, by taking regularly spaced aerial pictures, if a suitable overlap is guaranteed, it is possible to derive the 3D structure of the environment with its real- world size. Nowadays, several mapping programs are available that can deliver different kinds of 3D models by processing the acquired pictures, once the details of the acquisition camera are given. In this work, the Pix4D Mapper program has been used [16]. It can derive textured meshes as well as digital elevation models. As a coverage pattern, the so-called back-and-forth motion has been considered (Figure 2), and the trajectories along each side of each region are computed. Among these trajectories, the one with the minimum number of turns is chosen. In fact, according to [5], [6], and [16], the manoeuvres involved in a turn (decelerate, move to the following line, and accelerate again) are the main losses of energy and time during the back- and-forth motion execution. The resulting trajectories for the vertical decomposition example, chosen according to the Figure 1. Examples of vertical and horizontal decompositions. Figure 2. The back-and-forth pattern chosen as coverage trajectory within each subregion. Figure 3. Example of the environment decomposition and related coverage trajectories. ACTA IMEKO | www.imeko.org December 2019 | Volume 8 | Number 4 | 11 principle described, are shown in Figure 3. 3. COVERAGE SUBREGIONS ASSIGNMENT Once the coverage paths for all the regions have been defined, our approach proposes the adoption of a flock of UAVs in order to parallelise and then speed up the mission for the imagery acquisition. A negotiation rule is then used to assign each region to one of the members of the team. The strategy described in [18] has been adopted. It assumes a number of vehicles equal to the number of regions to be surveyed. This strategy involves computing the lengths of the paths to reach each region for all the UAVs of the flock from their starting positions. A 3D implementation of the A* algorithm has been used for this purpose [18]. After that, all the possible combinations of UAVs/region are derived and, eventually, the combination with the minimum total path length for the whole swarm is chosen. This is obtained by simply summing up the computed trajectory lengths of all the UAVs for a certain combination. The enhancement in this work with respect to [18] consists of considering both ends of the coverage trajectories as potential target positions while computing UAVs/region combinations. In fact, as underlined by [5], coverage paths can be travelled indistinctly along the two possible directions, thus providing a further variable element in the negotiation task. In Figure 4, an example of the target points, the first points of the coverage trajectories assigned to each UAV, and the paths to reach them are shown. It is important to note that the information about the terrain geometry given by the DEM is considered in trajectory computations. The trajectories in red are those obtained after a line-of-sight length reduction approach, as described in [18]. 4. TRAVERSABILITY COSTMAP GENERATION After the coverage mission is carried out by the flock and the environment model is reconstructed by the mapping software [16], a terrain traversability assessment is performed on such model, as reported in [8]. The DEM of the terrain is also considered; however, this is the model obtained by the aerial photogrammetric reconstruction, which is much finer than the DEM used for the flock mission planning in terms of resolution. This level of detail allows us to perform an analysis of the geometric properties of the environment: the slope of the terrain and the presence of height discontinuities [8]. The outcome of this processing is a map that includes the traversing costs, which is used for the path planning of the rover within the unstructured environment in order to avoid steep paths as well as obstacles. The latter may be either physical obstacles, such as walls; rocks or trees; or non-traversable zones, such as cliffs or areas that are too steep. Combining the costmap with classical grid-based path planning algorithms, the trajectories for the UGV can be computed. In this work, the D* algorithm has been used, thus obtaining paths that are optimal in terms of the difficulty of travelling through the environment, according to the traversing costs derived. Clearly, the costmap derived by the georeferenced DEM includes geographical data, which is fundamental during the autonomous GNSS (Global Navigation Satellite System) navigation of the rover. The resulting costmap from the terrain traversability analysis of a subregion within the considered ROI is shown in Figure 5. Darker areas are easily traversable zones, grey areas are those zones that are difficult to Figure 4. Three-dimensional model of the terrain and UAV-to-region paths for a flock with six vehicles. Figure 5. Map of traversing costs of a subregion within the ROI. ACTA IMEKO | www.imeko.org December 2019 | Volume 8 | Number 4 | 12 cross, and white areas are absolutely unpassable zones. 5. EXPERIMENTAL SETUP AND TESTING For the experimental testing, the U-Go rover, a rough terrain tracked vehicle, was adopted [19] (Figure 6). It embeds a GPS-based navigation system, an IMU (Inertial Measurement Unit) for the attitude data acquisition, and a frontal 2D laser range finder for the detection and avoidance of local or dynamic obstacles. An on-board companion computer is used to run the robot operating system infrastructure [20] that allowed us to verify and monitor the proper behaviour of the autonomous navigation algorithm during the on-field tests. From the obtained costmaps, the vehicle was capable to autonomously reach a goal in the environment map while avoiding the static obstacles and the steepest paths, which may expose the rover to instability. 6. CONCLUSIONS In this paper, an integrated strategy for the autonomous navigation of a rover in an outdoor unstructured environment has been discussed. It exploits the 3D photogrammetric reconstruction of the considered area with the help of a flock of UAVs for fast coverage missions and, therefore, the subsequent reconstruction. Once the 3D model of the environment was recreated, a geometry-based traversability assessment was carried out, and the obtained 2D costmap was combined with a D* algorithm for the path planning of the rover. Although geometric terrain traversability analysis represents a well-known approach in robotics research, the novelty of the present work lies in the combination of such approach with drone-based photogrammetry. Another contribution is related to the suggestion of a flock of UAVs for the coverage mission. Most of the single research has been focusing on single-vehicle solutions rather than multi-vehicle approaches. As future developments, we aim to improve the region/UAV assignment strategy by taking into account the coverage path lengths within each subregion, besides the distance to reach the region itself. A further enhancement will be to consider the more general case of a number of UAVs different from the number of regions to be surveyed. This involves the definition of flock management routines to be applied before the coverage path planning step. REFERENCES [1] P. Papadakis, Terrain traversability analysis methods for unmanned ground vehicles: a survey, Engineering Applications of Artificial Intelligence 26(4) (2013) pp. 1373-1385. [2] L. Cantelli, P. Laudani, C. D. Melita., G. Muscato, UAV/UGV cooperation to improve navigation capabilities of a mobile robot in unstructured environments, Advances in Cooperative Robotics (2017) pp. 217-224. [3] B. Grocholsky, J. Keller, V. Kumar, G. Pappas, Cooperative air and ground surveillance, IEEE Robotics & Automation Magazine 13(3) 2006, pp. 16-25. [4] H. Balta, G. De Cubber, D. Doroftei, Y. Baudoin, H. Sahli, Terrain traversability analysis for off-road robots using time-of- flight 3S sensing, Proc. of the 7th IARP International Workshop on Robotics for Risky Environment-Extreme Robotics, 2013. [5] M. Torres, D. A. Pelta, J. L. Verdegay, J. C. Torres, Coverage path planning with unmanned aerial vehicles for 3D terrain reconstruction, Expert Systems with Applications 55 (2016) pp. 441-451. [6] C. Di Franco, G. Buttazzo, Coverage path planning for UAVs photogrammetry with energy and resolution constraints, Journal of Intelligent & Robotic Systems 83(3-4) 2016, pp. 445-462. [7] T. Braun, H. Bitsch, K. Berns, Visual terrain traversability estimation using a combined slope/elevation model, Proc. of the Annual Conference on Artificial Intelligence, 2008, pp. 177-184. [8] D. C. Guastella, L. Cantelli, C. D. Melita, G. Muscato, A global path planning strategy for a UGV from aerial elevation maps for disaster response, ICAART 1 (2017) pp. 335-342. [9] R. Fedorenko, A. Gabdullin, A. Fedorenko, Global UGV path planning on point cloud maps created by UAV, Proc. of the 3rd IEEE International Conference on Intelligent Transportation Engineering (ICITE), 2018, pp. 253-258. [10] J. Prado, L. Marques, Energy efficient area coverage for an autonomous demining robot, Proc. of the ROBOT2013: 1st Iberian Robotics Conference, 2014, pp. 459-471. [11] J. Jin, L. Tang, Optimal coverage path planning for arable farming on 2D surfaces, Transactions of the ASABE 53(1) 2010, pp. 283-295. [12] L. Paull, S. Saeedi, M. Seto, H. Li, Sensor-driven online coverage planning for autonomous underwater vehicles, IEEE/ASME Transactions on Mechatronics 18(6) 2013, pp. 1827-1838. [13] B. Englot, F. S. Hover, Three-dimensional coverage planning for an underwater inspection robot, The International Journal of Robotics Research 32(9-10) 2013, pp. 1048-1073. [14] A. Khan, I. Noreen, Z. Habib, On complete coverage path planning algorithms for non-holonomic mobile robots: survey and challenges, Journal of Information Science and Engineering, 2017, 33 1, pp. 101-121. [15] E. U. Acar, H. Choset, A. A. Rizzi, P. N. Atkar, D. Hull, Morse decompositions for coverage tasks, The International Journal of Robotics Research 21(4) 2002, pp. 331-344. [16] Pix4D mapper, https://pix4d.com. [17] E. Galceran, M. Carreras, A survey on coverage path planning for robotics, Robotics and Autonomous Systems 61(12) 2013, pp. 1258-1276. [18] D. C. Guastella, N. D. Cavallaro, C. D. Melita, M. Savasta, G. Muscato, 3D path planning for UAV swarm missions, Proc. of the 2nd International Conference on Mechatronics Systems and Control Engineering, 2018, pp. 33-37. [19] F. Bonaccorso, D. Longo, G. Muscato, The U-Go Robot, Proc. of the World Automation Congress, 2012, pp. 1-6. [20] M. Quigley, K. Conley, B. Gerkey, J. Faust, T. Foote, J. Leibs, E. Berger, R. Wheeler, A. Y. Ng, ROS: an open-source robot operating system, Proc. of the ICRA Workshop on Open-Source Software 3(3.2), 2009, pp. 5-10. Figure 6. The U-Go rover adopted for the experimental tests.