IROS2019国际学术会议论文集1402

Heuristic-based Multiple Mobile Depots Route Planning for Recharging Persistent Surveillance Robots Yifan Ding, Wenhao Luo, Katia Sycara AbstractPersistent 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, , 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, ,nhas 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, ,nis 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, ,ncorrelates 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=1maxp,qCidist(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 thanBOPT(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)+2nd. 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) = B3l. 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 Prims 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|TiTj| = , and |Ti Tj| = C, where i,j 1,2, ,k,i 6= j. Proof: If we apply the modifi ed Prims 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 Prims 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 |TiTj| = 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