IROS2019国际学术会议论文集 1402

Heuristic based Multiple Mobile Depots Route Planning for Recharging Persistent Surveillance Robots Yifan Ding Wenhao Luo Katia Sycara Abstract Persistent surveillance of a target space using multiple unmanned aerial vehicles UAVs has multiple appli cations such as geographical surveys air quality monitoring and security monitoring The limited onboard battery capacity challenges the continuous operation in these applications of persistent robots We consider the problem for recharging persistent robots using mobile depots The mobile depots collectively compute a set of tours to recharge all persistent robots with the minimum total cost Compared to other works the persistent UAVs are not required to detour to a static depot for energy replenishment such as recharging or battery swapping We formulate this problem as a Generalized Multiple Depots Travelling Salesman Problem GMDTSP on a complete graph A heuristic based algorithm Multiple Depots Random Select RSMD is proposed to solve the recharging problem effi ciently The RSMD has proved to have an analytical constant upper bound in the worst case scenario We also propose a post processing heuristic RSMD IM to improve the solution quality further We demonstrate the effi ciency and effectiveness of our algorithm via benchmark on multiple instances from TSPLIB and GTSPLIB The simulation results show that RSMD and RSMD IM will perform signifi cantly faster than the state of the art heuristic solver LKH with a loss of about 10 of solution quality I INTRODUCTION Persistent surveillance of a target space using multiple unmanned aerial vehicles UAVs has numerous applications such as geographical surveys air quality monitoring and security monitoring 1 2 3 Limited onboard battery ca pacity is one of the challenges for UAVs to execute persistent tasks continuously To address the long term operation for the persistent surveillance tasks periodic recharging or battery swapping for multiple UAVs becomes one of the popular research questions There is an extensive literature on recharging UAVs by placing static depots so that the UAVs can detour for recharging 4 5 6 These literature discuss the optimal quantity and placement for the static depots which will lead to a minimum cost for the UAVs to recharge However the recharging operation needs to remove UAVs from persistent tasks which will become a challenge for UAVs executing safety critical missions Also the detour for the UAVs to the static depots can be a waste of energy Moreover due to the dynamics for the environment the optimal placement always changes with respect to time and is relevant to the persistent missions The authors are with the Robotics Institute School of Com puterScience CarnegieMellonUniversity Pittsburgh Pennsylva nia USA Email yifand1 wenhaol andrew cmu edu katia cs cmu edu Fig 1 Example for the multiple mobile depot route planning problem with 2 mobile depots and 4 persistent robots The red asterisks are the preferred recharging locations The green paths are the pre planned route for persistent robots To address these problems mobile depots are deployed in this paper to recharge the persistent UAVs so that the persistent UAVs are not required to detour for recharging Fig 1 shows an example for our formulation where there are two types of robots persistent robots and the mobile depots The persistent robots are monitoring based on a pre planned fi xed route Before persistent robot run out of fuel it will broadcast a set of preferred recharging locations to all mobile depots The persistent robots only allowed to be recharged at their own preferred recharging locations The problem we need to solve is to fi nd tours for the mobile depots to recharge all persistent robots within their preferred recharging locations with the minimum total cost We formulate this problem as a generalized multiple depots travelling salesman problem GMDTSP which turns out to be an NP hard problem The challenge for this problem is 1 how to assign persistent robots to different mobile depots 2 what is the optimal order to visit the persistent robots 3 what is the optimal location to refuel given each persistent robot has multiple preferred recharging locations To simplify the analysis we assume that mobile depots have unlimited battery capacity This paper presents two main contributions First a heuristic based algorithm Multiple Depots Random Select RSMD is proposed to effi ciently solve the route planning problem for multiple mobile depots for recharging persistent surveillance robots The problem is modeled as a GMDTSP on a complete graph The RSMD has proved to have an analytical constant upper bound in the worst case scenario 2019 IEEE RSJ International Conference on Intelligent Robots and Systems IROS Macau China November 4 8 2019 978 1 7281 4003 2 19 31 00 2019 IEEE3308 Second a post processing heuristic RSMD IM is proposed to improve the solution quality further The simulation results show that RSMD and RSMD IM will perform signifi cantly faster than the state of the art heuristic solver LKH 7 with a loss of about 10 of solution quality II RELATEDWORK Recharging the persistent robots with mobile depot has many different formulations in the literature Different than the route planning for multiple mobile depots 8 9 formulate the problem as a single mobile depot planning a route for recharge the UAVs The single mobile depot problem can be solved by the transformation method mixed integer programming MIP or heuristic based algorithm In 10 11 12 a battery swapping system has been modeled with the assumption that the swap can happen instantly without the charging duration However the battery swapping needs to have fully charged battery in stock which may signifi cantly increase the operation cost A recent work 13 has a similar formulation where a heuristic based solution performs effi ciently but the ef fectiveness is only shown based on empirical simulation results instead of analytical analysis Also the algorithm did not admit the periodic structure Similar to this work 14 discretize the state space for periodic recharges and cast this problem as a generalized travelling salesman problem GTSP on a partitioned directed acyclic graph However in our work the problem is formulated as a GMDTSP on a complete graph Moreover the work 14 use the modifi ed noon bean transformation 15 to transform the problem to a traditional TSP problem which will increase the size of the vertex set We formulate the problem as a GMDTSP where an exact MIP formulation exists 16 However the computation time is not acceptable for real time application An effi cient and effective heuristic based algorithm is needed for solving this problem III PROBLEMFORMULATION Considernpersistent robots moving inR3 following their pre planned routes to monitor their own prescribed areas periodically Each persistent roboti 1 2 n has a set of preferred refueling locationsCi whereCiis a vertex set which consists of a set of discretized vertices on its pre planned route Assume robotionly accept to be recharged at one of its own preferred refueling locations inCi When robotirun out of fuel it will broadcast the vertex setCito allkholonomic mobile depotsD Di i 1 2 k Defi ne a set of preferred charging locations for all persistent robots C Ci i 1 2 n Fig 1 shows an example for the multiple mobile depot route planning problem with two mobile depots k 2 and four persistent robots n 4 The multiple mobile depots route planning problem can be formulated in a complete undirected graphG V E c with vertex setV C D The cost of an edgee p q E is assigned to be the Euclidean distance between vertices p q V The mobile depots collectively compute a set of at mostktoursTh h 1 2 k withVhas the vertices in tourh The tour is defi ned as a simple circle onGwhere each mobile depot starts and ends at its initial location At least one vertex from each vertex setCi i 1 2 n is visited by at least one mobile depot The formal formulation for this problem then becomes minimize k X h 1 c Th subject toV fi rst h V last h h 1 k k h 1Vh Ci 1 i 1 n Note that this problem formulation falls into the category of GMDTSP When the vertex setCi i 1 2 n only contains a single vertex then this problem degenerate to an MDTSP Whenk 1 then this problem degenerates to a GTSP Remark 1 The graphGis a symmetric graph where c p q c q p for all verticesp q V For non holonomic mobile depot the edge cost may not be symmetric due to the dynamic constraints In our problem formulation all mobile depots are holonomic Remark 2 The complete graphG satisfi es the triangle inequality since the edge cost is defi ned by Euclidean distance between vertices Based on the problem formulation it is valid that multiple mobile depots recharging the same persistent robot However in fact to minimize the total cost for allk tours each persistent robot will only be charged by one and only one mobile depot due to the triangular inequality 17 Remark 3 Although the current cost only refl ects the Euclidean distance between vertices some other factors such as travel time and recharging time can also be associated with the cost as long as the new cost satisfy the triangle inequality IV RANDOMSELECTHEURISTICS ANDANALYSIS A Single Mobile Depot Scenario As discussed in Section III a single mobile depot k 1 degenerates the problem from a GMDTSP into a GTSP The simplifi ed version sheds light on a more complicated multiple depots scenario We fi rst discuss the intuition of the proposed Random Select RS heuristics and then we describe the steps of RS and fi nally we provide the proof of worst case upper bound for this heuristics The underlying nature for RS is that every vertex in the vertex setCi i 1 2 n correlates with others given every vertex are the potential charging location for the same persistent robot The correlation implies that if we randomly choose one vertex from the vertex set the selected vertex can represent the group of vertices With one vertex in each of the vertex set the GTSP problem degenerate to a classic symmetric TSP where many polynomial time approximate solutions exist 3309 Algorithm 1 Random Select RS heuristics 1Randomly select a single vertex from each of the disjoint vertex set Ci i 1 2 n to form a subset P V and P k 2Use any existed polynomial time TSP heuristic HEUR to solve the tourTon the selected subsetP ReturnTas an approximation for the problem Based on this assumption Algorithm 1 describe the procedures to executes RS Using the well known inequality scaling technique 18 RS can be proved to have an analytical constant upper bound in the worst case scenario Theorem 1 For any existed TSP heuristic HEUR bounded by constantB RS G is the cost of the route constructed by RS using HEUR onG and OPT G be the cost of the optimal route Then RS G OPT G B 1 2d whered maxn i 1 maxp q Cidist p q is the max imum diameter inter vertex set and mindist p q wherep Ci q Cj i 6 jis the minimum distance intra vertex sets Proof Given the problem formulation G V E c is a complete undirected graph Defi ne another complete undirected graphG0 P E0 c0 which is a subgraph ofG Note that the GTSP problem onGis degenerate to a TSP problem on G0 SinceG0is one of the selected subgraph forG which means using the same TSP heuristic HEUR RS G HEUR G0 Assume OPT G0 is the cost of the optimal route onG0 For any existed TSP heuristic HEUR bounded byB the cost for HEUR G0 is no greater thanB OPT G0 Therefore combine these two inequalities we have RS G B OPT G0 1 The obtained optimal TSP sequence onG0is some permutation on vertex setP and defi ne this optimal sequence asS Defi neS0as another sequence onP which uses the vertex set visitation sequence on OPT G We can imply that OPT G0 cost S cost S0 SinceS0is the optimal group visitation sequence on setP using the triangular inequality we can havecost S0 OPT G 2n d Based on the defi nition on we haveOPT G n Combine these inequalities we have OPT G0 1 2d OPT G 2 The theorem is proved by combining the inequality 1 and 2 Theorem 2 If the TSP heuristic obtained a worst case route with its upper boundB then there exist a worst case scenario that RS G OPT G B 1 2d Proof This can be shown by constructing an example Assume four vertices are co aligned on a line with equal distancelseparate apart Separate the four vertices in the middle to two vertex sets with two vertices each In this setting d l We can verify the optimal cost OPT G l Choose the points at the ends for both sets Given the chosen TSP heuristic obtained a worst case route RS G B 3l Thus RS G OPT G has the upper bound equal to B 1 2d Remark 4 d 0is a special case where the vertices in each vertex set degenerate to a single point This case implies the GTSP degenerates to a TSP The derived bound can be justifi ed since the bound becomesBfor the chosen TSP heuristic HEUR Remark 5 The proposed algorithm can be run inO n2 time wherenis the number of persistent robots Note that this is irrelevant to C the number of potential charging locations Remark 6 The upper bound for RHS does not depend on a specifi c TSP polynomial algorithm Some popular heuristics includes Christofi des algorithm withB 1 5 nearest neighbor heuristics with B 2 etc B Multiple Mobile Depots Scenario The general idea for tackling the multiple mobile depots scenario is to transform it into a single depot scenario Then apply RS described in Section IV A to fi nd the routes Inspired by the well known minimum spanning tree MST heuristic in TSP and mTSP the transformation can be achieved by introducing a dummy vertexvdummy and con struct a new complete undirected graphG00 V 00 E00 c00 whereV 00 V vdummy The costc00on the new graph is defi ned as 1 c00 i j d i j for all i j C 2 c00 i j d i j for all i C j D 3 c00 i j for all i j D 4 c00 vdummy i 0 for all i D 5 c00 vdummy i for all i C We can construct an MST based on the new graphG00 based on a modifi ed Prim s greedy algorithm When a vertex is connected to the tree the whole vertex set is considered to be connected to the tree and marked as visited Thus other vertices in this set are no longer able to be connected to the tree Each node in the MST is a vertex set and the MST has a total of C D 1 nodes if we also include the dummy node vdummy Lemma 1 Edgese vdummy i for alli Dare also edges for the MST onG00rooted at the dummy nodevdummy Mobile depotihas a sub treeTi i 1 2 k where Ti Tj and Ti Tj C where i j 1 2 k i 6 j Proof If we apply the modifi ed Prim s greedy algorithm then all mobile depots will be connected to the dummy node vdummysince the edge cost between them is the smallest zero With the connection between the dummy node and all 3310 Algorithm 2 Multiple depot random Select RSMD heuristics 1Construct an MST rooted at vdummy using modifi ed Prim s greedy algorithm 2The mobile depots are assigned all vertex sets that are connected to it in the constructed MST 3Solve the sub problem using Algorithm 1 for the single mobile depot scenario mobile depots any vertex inCwill not connect to dummy node since the edge cost between them is infi nite This implies Ti Tj C Also the sub tree rooted at the mobile depots will not intersect with each other Otherwise a circle will be formed which contradict with the concept of tree This implies Ti Tj With Lemma 1 proved the multiple mobile depots RS MDRS execute Algorithm 2 on the newly constructed graph G00 Theorem 3 Defi ne MDRS G as the cost of the route constructed by MDRS onG and OPT G be the cost of the optimal route Then MDRS G OPT G max i 1 k B 1 2di i Proof The bound can be shown by directly following the proof in Theorem 1 V IMPROVEMENTHEURISTICS ONTOURS Section IV A and IV B propose and analysis the Random Select heuristics for single and multiple depots scenarios respectively Since both RS and RSMD randomly select a vertex from each of the vertex set to represent the whole set the computed tours can be used as a near optimal vertex set visitation sequence to optimize further and improve the tour We will fi rst illustrate the Improvement Heuristics on Random Select RS IM for the single depot scenario in detail Defi ne the mapM R3 R which maps the randomly selected vertexvi Cito the corresponding vertex set indexi 1 2 n Given a tourT defi neT j as thejthvertex inT Defi ne two tourT1andT2are equal if and only if 1 T1 T2 and 2 T1 j T2 j for all j 1 2 T1 Otherwise T16 T2 For vertex set S V defi ne the tour computed by RS on the set S as T RS S Algorithm 3 describes the RS IM procedure to improve the solution quality Line 4 is for continuous improvement based on the previous post processing result Line 5 to Line 20 con struct a weighted directed graphGIM VIM EIM cIM so that we can perform a single shortest path search to fi nd the optimal route given the group sequence found byTRS The RS IM can be naturally extended to the multiple depots case RSMD IM Algorithm 3 Improvement Heuristics on Random Select RS IM Inputs The original tour TRScomputed by RS Outputs The improved tour TIM 1Initialize GIM VIM EIM cIM with VIM V 2p TIM 3L TRS 4while p OR RS p 6 Tijdo 5for j 0 1 L 1 do 6if j 0 then 7Insert dummy node s VIM VIM s 8Connect EIM s v v CM T 1 9Set cIM s v 0 v CM T 1 10end 11else if j L 1 then 12Insert dummy node t VIM VIM t 13Connect EIM v t v CM T L 14Set cIM v t 0 v CM T L 15end 16else 17Connect EIM u v for all u CM T j v CM T j 1 18Set cIM u v dist EIM u v 19end 20end 21end 22TIM p shortest path from dummy node s to t VI SIMULATIONRESULTS The proposed algorithms are implemented in C with an open source template graph library LEMON1 The library provides effi cient implementations of common data structures and graph algorithms It also provides a high level interface for several linear programming LP and mixed integer pro gramming MIP solvers such as IBM CPLEXr Simulation results were computed on a laptop running a 64 bit Ubuntu 16 04 operating system with an IntelrCoreTMi7 8550U CPU 1 80GHz x 8 and 16GB of RAM Fig 2 illustrates an example to solve the