Orienteering-based path selection for mobile sensors

Abstract

The goal of information gathering is to obtain data from the environment generating an accurate model for the application of interest. In many applications the information gathering process requires to obtain measurement of the phenomena of interest in harsh or dangerous conditions (e.g., environmental monitoring applications of water in a lake or search and rescue operations in disaster response). Moreover, in recent years, the interest towards robotic sensors such as Unmanned Ground Vehicles (UGVs), Unmanned Aerial Vehicles (UAVs) or Autonomous Surface Vessels (ASVs) for information gathering application is steadily increasing. For example, in the context of environmental monitoring a successful monitoring operation must acquire large datasets to build an accurate model of the environmental phenomena of interest. For an exhaustive overview on advancements and applications of mobile sensors for environmental monitoring see [3]. Moreover, in the context of aerial monitoring, Unmanned Aerial Vehicles (UAVs), which can y autonomously at low altitude, are an emerging technology being adapted for a wide range of applications such as remote sensing, scienti c research, and search and rescue tasks [9, 10, 15]. In general, when using mobile robotic systems, di erent path selection strategies could be identi ed [12]. O ine strategies rely on a prede ned path for the agent that is independent from the data that the sensors read. Conversely, using online strategies, the path selection procedure is dependent on the data that has been previously collected from the sensor. In this work we show two di erent applications for online path selection procedures that rely on a common orienteering formulation. Speci cally the contribution is to highlight the formulation of the orienteering problem in the context of information gathering through the use of mobile sensors.

Introduction

Orienteering problem

In the Orienteering problem (OP) we have a start and an end point speci ed along with a set of checkpoints each with an associated score. Moreover, we have a given time budget and we aim at moving from the start to the end within the budget and by maximizing the total score collected moving through the checkpoints. More formally, the OP can be de ned with a weighted graph G = (V; E) where V = fv1; : : : ; vN g is the set of nodes (start point, end point, and checkpoints) and E is the set of edges. In this formulation, the nonnegative score Si of location i is associated with a vertex vi 2 V and the travel time tij between location i and j is associated with each edge eij 2 E. A solution for the orienteering problem is an Hamiltonian path over a subset of V , including the start node (v1) and the end node (vN ), and having a length not exceeding the bound Tmax, in order to maximize the total collected score.

The orienteering problem can also be de ned as a combination of node selection and shortest path computation between the graph nodes. OP can be seen as a combination of the Knapsack Problem (KP) and the Traveling Salesman Problem (TSP) [ 2 ], where the KP goal is to maximize the total score collected while the TSP aims at minimizing the travel distance. This formulation is also referred to as a generalized travelling salesman problem (GTSP) [ 4 ]. Intuitively, the orienteering problem is NP-hard as it contains the well known traveling salesman problem as a special case.

This problem has been studied in routing and scheduling applications and it is also known as the selective traveling salesperson problem ([ 8 ], [ 13 ]) or the maximum collection problem ([ 7 ]). Numerous variants and practical applications can be modeled as an orienteering problem. For a general review, we suggest the surveys proposed by Vansteenwegen et al. [ 14 ] and Gunawan et al. [ 6 ]. 3

Applications

In what follows, we propose two mobile sensor applications in which the orienteering problem is a viable option for computing an e cient path. The key aspect that binds the following applications to the orienteering problem is the value of a location, which is related to the information that can be acquired by the platform in that point of space. 3.1

ASV for environmental monitoring The rst application we consider is the environmental monitoring and, speci cally, the Level Set Estimation (LSE) problem. In LSE we have to classify regions of the space where the analyzed phenomena is above or below a given threshold value. For example, when analyzing the PH value of waters in a lake, the goal of the level set estimation is to identify the locations where the value exceeds a dangerous threshold level.

In [ 1 ] we proposed an orienteering formulation of the level set estimation problem to compute informative paths for a mobile sensor such as the boat in Figure 1. The described technique is speci cally designed for continuous measuring sensors where we aim at obtaining a near optimal classi cation while taking the path length into account to meet the typical energy constraint we must consider when operating with mobile sensors. Speci cally, the SBOLSE algorithm [ 1 ] can be summarized as follow: 1. The environmental phenomena is modeled using a Gaussian Process [ 11 ]. 2. Following the approach of [ 5 ] the algorithm classi es the locations that can be classi ed with the current information acquired. 3. For the points that still cannot be classi ed, the algorithm de nes an ambiguity measure that identi es the uncertainty about the classi cation of the point. This value represents the informativeness that we can obtain by taking a measurement in that location. 4. We build an orienteering instance, which is a graph where the nodes represent the unclassi ed locations and the ambiguity measure represents the score. 5. Using an orienteering heuristic, we obtain an informative path for the mobile sensor and we analyze all the data along that path. 6. We update the Gaussian Process with the newly acquired information and iterate the process until everything is classi ed.

The SBOLSE algorithm we proposed in [ 1 ] has been compared with the state of the art techniques for the level set estimation problem on two di erent datasets, namely a real-world dataset of water's PH value and a synthetic dataset. The results in Table 1 show that the proposed algorithm signi cantly outperforms other techniques in terms of total path length required to obtain a near optimal classi cation. The second application we propose is a UAV system for livestock monitoring applications. UAVs can be equipped with many sensors such as gps, laser scanner and digital camera. With those sensors, one of the main advantages of monitoring systems based on the UAV is to quickly obtain high-resolution sensory data on a selected area. For this reason many studies using UAV systems have been conducted in various elds such as environmental, agricultural and pollution monitoring, forest re detection and disaster applications [ 9, 10, 15 ]. Here we focus on a system that for a given selected area can detect and track livestocks. The framework we developed can be summarized as follows: { We trained a real-time object detection system based on OpenCV 1 to detect our target. A drone with an equipped camera can now detect targets while scanning the selected area. { Using the detector, locations where the targets are discovered becomes highlighted by rectangles. { We consider an \accuracy" value, that is the number of rectangles that overlaps in a small portion of the image. This value identi es the con dence about the detection of the target. { After the initial scan of the area, we can use this accuracy level for the orienteering instance to compute a path that moves the UAV over the locations where it is most likely to nd the livestock.

We performed some preliminary tests by comparing the use of an orienteering heuristic against a greedy approach. To run these tests we performed a simulation using ROS and V-REP (see Figure 1) and the results are shown in Table 2. With this framework we would be able to detect targets in a selected area and then to use the remaining energy of the autonomous UAV to keep track of the most interesting locations where targets have been identi ed. In this work we showed how the orienteering problem relates to information gathering for mobile sensors. We described two di erent applications where an orienteering problem formulation allows computing e cient paths for the agents. 5

Acknowledgements

This work was supported by the European Unions Horizon 2020 research and innovation programme under grant agreement No 689341. This work re ects only the authors' view and the EASME is not responsible for any use that may be made of the information it contains. 1 http://opencv.org/

References

1. Lorenzo Bottarelli , Manuele Bicego, Jason Blum, and Alessandro Farinelli . Skeleton-based orienteering for level set estimation . In ECAI 2016 - 22nd European Conference on Arti cial Intelligence , 29 August -2 September 2016 , The Hague, The Netherlands - Including Prestigious Applications of Arti cial Intelligence (PAIS 2016 ), pages 1256 { 1264 , 2016 .

2. Thomas H. Cormen , Charles E. Leiserson, Ronald L. Rivest , and Cli ord Stein . Introduction to Algorithms . MIT Press, third edition, 2009 .

3. M. Dunbabin and L. Marques . Robots for environmental monitoring: Signi cant advancements and applications . Robotics Automation Magazine , IEEE, 19 ( 1 ): 24 { 39 , March 2012 .

4. Bruce L. Golden , Larry Levy , and Rakesh Vohra . The orienteering problem . Naval Research Logistics (NRL) , 34 ( 3 ): 307 { 318 , 1987 .

5. Alkis Gotovos , Nathalie Casati, Gregory Hitz, and Andreas Krause . Active learning for level set estimation . In Proceedings of the Twenty-Third International Joint Conference on Arti cial Intelligence , IJCAI '13 , pages 1344 { 1350 . AAAI Press, 2013 .

6. Aldy Gunawan , Hoong Chuin Lau, and Pieter Vansteenwegen . Orienteering problem: A survey of recent variants, solution approaches and applications . European Journal of Operational Research , 255 ( 2 ): 315 { 332 , 2016 .

7. S. Kataoka and S. Morito . An algorithm for single constraint maximum collection problem . Journal of the Operations Research Society of Japan , 31 ( 4 ): 515 { 31 , 1988 .

8. Gilbert Laporte and Silvano Martello . The selective travelling salesman problem . Discrete Applied Mathematics , 26 ( 2 ): 193 { 207 , 1990 .

9. M. Nagai , T. Chen , R. Shibasaki , H. Kumagai , and A. Ahmed . Uav-borne 3-d mapping system by multisensor integration . IEEE Transactions on Geoscience and Remote Sensing , 47 ( 3 ): 701 { 708 , March 2009 .

10. A. Ollero , J. Alcazar , F. Cuesta , F. Lopez-pichaco, and C. Nogales . Helicopter teleoperation for aerial monitoring in the comets multi-uav system .

11. C. E. Rasmussen and Williams C. K. I. Gaussian Processes for Machine Learning . MIT Press, Cambridge, MA, USA, 2006 .

12. Amarjeet Singh , Andreas Krause , Carlos Guestrin, and William J. Kaiser . E cient informative sensing using multiple robots . J. Artif. Int. Res. , 34 ( 1 ): 707 { 755 , April 2009 .

13. T. Thomadsen and T. Stidsen . The quadratic selective travelling salesman problem . Technical report, Informatics and Mathematical Modelling , Technical University of Denmark, DTU, Richard Petersens Plads, Building 305, DK-2800 Kgs . Lyngby, 2003 .

14. Pieter Vansteenwegen , Wouter Sou riau, and Dirk Van Oudheusden. The orienteering problem: a survey . EUROPEAN JOURNAL OF OPERATIONAL RESEARCH , 209 ( 1 ):1{ 10 , 2011 .

15. Haitao Xiang and Lei Tian . Development of a low-cost agricultural remote sensing system based on an autonomous unmanned aerial vehicle (uav) . Biosystems Engineering , 108 ( 2 ): 174 { 190 , 2011 .