Multi-UAV Routing for Persistent Intelligence Surveillance & Reconnaissance Missions
Satyanarayana G. Manyam Steven Rasmussen David W. Casbeer Krishnamoorthy Kalyanam Suresh Manickam

[
    [
    Received: date / Accepted: date
===================================

empty
empty






We consider a Persistent Intelligence, Surveillance and Reconnaissance (PISR) routing problem, which includes collecting data from a set of specified task locations and delivering that data to a control station. Each task is assigned a refresh rate based on its priority, where higher priority tasks require higher refresh rates.  The UAV team's objective is to minimize the maximum of the delivery times of all the tasks' data to the control station, while simultaneously, satisfying each task's revisit period constraint. The centralized path planning problem for this PISR routing problem is formulated using mixed integer linear programming and solved using a branch-and-cut algorithm. Heuristics are presented to find sub-optimal feasible solutions that require much less computation time. The algorithms are tested on several instances and their performance is compared with respect to the optimal cost and computation time.




§ INTRODUCTION
 

Unmanned Aerial Vehicles (UAVs) are a natural choice for deployment in many military Intelligence, Surveillance and Reconnaissance (ISR) missions<cit.>. A typical ISR scenario involves monitoring a set of task locations for an indefinitely long period of time. These task locations can be buildings, road networks bordering a military base etc. Since these task locations are spatially dispersed, UAVs can be deployed to visit them regularly and ferry the information such as images, videos, sensor data etc. to a control station. This data needs to be delivered to the control station at regular intervals. The importance level of each of the task locations may vary from minimal to highly critical. While scheduling these monitoring missions, it is imperative to schedule the UAV to visit important task more frequently than the ones with lesser significance. 


We consider a persistent monitoring scenario, where a set of task locations needs to be visited persistently by multiple UAVs. We assume all the available UAVs are homogeneous. Therefore, there is no difference between visits by different UAVs to the same task. We are interested in two metrics viz. data latency or delivery time (to the control station) and revisit rate or revisit period. We define the data delivery time (or latency time) as the time elapsed from collection of data from a task to the time the data is delivered to the control station. The data needs to be delivered at control stations as early as possible. The revisit period is the time between two successive visits to a task location; a task with higher priority needs to have a smaller revisit period compared to a low priority.


Prior work: Several variants of persistent routing problem were addressed in <cit.>. Strategies to perform patrolling tasks by multiple agents on a network defined as a graph are presented in <cit.>. In <cit.>, persistent surveillance of an area decomposed into cells is considered; <cit.> attempts to minimize the maximum time since last visit of all the cells, whereas <cit.> balances the frequency of visit to each cell. Persistent surveillance problems with tasks spatially distributed is posed as a vehicle routing problem with time windows in <cit.>. Patrolling strategies to minimize the refresh time of the viewpoints is presented in <cit.>. Approximation algorithms are presented in <cit.>, that minimize the maximum weighted latency (time between successive visits) in discrete environments. In <cit.>, the authors attempts to minimize time between two consecutive visits to partitioned regions while satisfying temporal logic constraints of each agent. A persistent routing scenario where some regions need more visitation than others is addressed in <cit.>, and a policy to achieve that is proposed. 

In this article, we consider a persistent routing of tasks that are spatially distributed. Also the data collected at the task locations needs to be delivered at a control station (also referred to as depot). In the existing literature concerning persistent routing, the concept of a control station is not considered and delivery time is not addressed. 


We model this persistent routing problem as a multiple traveling salesman problem with revisit period constraints, and formulated as a mixed integer linear programming (MILP) problem. The contributions of this article are the following: (i) We present a novel formulation addressing two important metrics, delivery time and revisit period for the tasks in ISR missions and model it as a multiple vehicle path planning problem with cycle length constraints. (ii) We present two different MILP models to find optimal solutions to the corresponding path planning problem. The two MILP models constitute novel constraints to address the cycle length limits, which could be applied to any general routing problem involving constraints on cycle length. (iii) A heuristic via assignment-tree search is presented that produces good sub-optimal solutions, and it could be easily generalized to address different cost functions and/or constraints. (iv) We test the algorithms on several random instances and computational results are presented. 

The PISR routing problem is closely related to the distance constrained and fuel constrained vehicle routing problems <cit.>. This problem differs from these as follows: rather than the constraints being dictated by the UAV, the constraints on a tour are dictated by the tasks a UAV visits, which is a harder constraint to deal with. Also the cost function chosen here to capture the latency requirements is different from the cost of distance constrained VRPs.



§ PRELIMINARIES AND ASSUMPTIONS

Here, we aim to optimize the total cost of the persistent ISR mission by centralized planning. We are looking at solving the problem before the mission begins and assigning the tasks for each UAV/agent to perform in a pre-specified sequence. Ideally, in a persistent routing scenario, the objective is to optimize the chosen metrics over an infinite time horizon. To plan the mission and schedule tasks to be serviced by each UAV, we need to generate an infinite sequence of visits for each UAV, which is infeasible. To overcome this, one may periodically solve a receding horizon problem, generate the task sequences and schedule the UAVs as proposed in <cit.>. However, reliable UAV-to-UAV communication links would be required, as well as the precise location of all the UAVs each time the planner is executed. 

A critical assumption we make for a-priori mission planning is the following: we restrict each task to be serviced by the same UAV throughout the mission. Each UAV performs the tasks assigned and returns to the control station, and repeats exactly the same sequence throughout the mission. For example consider a mission with two UAVs and five tasks {t_1, t_2, t_3, t_4, t_5}, and let t_d represent the control station (or depot). A sample assignment for two vehicles V_1 and V_2 is as follows: V_1: t_d → t_1 → t_2 and V_2: t_d → t_3 → t_4 → t_5. Here, if the time of travel for the sequence t_d → t_1 → t_2 → t_d is R_1 seconds, then tasks t_1 and t_2 are serviced once every R_1 seconds.


Some of the advantages of this class of solutions are the following: we do not need to have communication between UAVs to update the scheduled tasks at each planning time interval. Whenever a UAV breaks down or needs refueling, the operator precisely knows which tasks are not being serviced, such that a contingency plan could be scheduled. The revisit period for each task is exactly known based on the tasks and the sequence assigned to the UAVs. Also under this restriction, the data that is collected from a task is delivered to the control station before its next visit. This is not guaranteed in the unrestricted case, where a task could be serviced by two different UAVs at successive visits. Along with the above advantages, there is a shortcoming; the cost one would optimize with this restriction could be different from the cost of the unrestricted case. However, due to its advantages in planning the mission and implementing, we pursue the restricted case where each tasks is assigned to one of the UAVs, and it is serviced by the same UAV throughout the mission.

There are two important metrics that needs to be addressed in PISR missions. The first one is the data delivery time or data latency (D_i) for each task t_i; D_i is the elapsed time from when a task is completed until the vehicle returns to the depot. This is not the direct travel time between the task and the depot, as the vehicle may service other tasks before returning to depot. This is illustrated in Fig. <ref>, the delivery time for the tasks t_3, t_4 and t_5 are shown as D_3, D_4 and D_5 respectively. 

The other metric that we consider is the revisit period of each task. It is the time between two successive visits of a task by an UAV. Since each UAV visits the same set of tasks and repeats, the revisit period is the same for every successive visit. The revisit periods R_1 and R_2 are illustrated in Fig. <ref> for the tasks t_1 and t_2. Based on the importance or risk levels, some of the tasks require higher revisit rates than others. We aim to solve the PISR routing problem where a maximum limit on revisit period, R_i,  is specified for each task t_i. We want the data delivered at the control station to be as fresh as possible, which requires the delivery times to be as small as possible. To accomplish this, we minimize the maximum delivery time of all the tasks: minmax_i ∈ T D_i. This cost is different from minimizing total cost of the paths, and it is a measure of the delivery time of the first task that is serviced. 




§ PROBLEM FORMULATION
 
In this section, we define the path planning problem for the PISR missions in more detail. Also we present a mixed integer linear programming (MILP) formulation to find the optimal solution to the path planning problem. We model the MILP using node based and arc based formulations; these models are akin to the models in <cit.> and <cit.> used to solve the traveling salesman problem with time windows and the distance constrained vehicle routing problem. Similar formulations were also used to solve fuel constrained multiple vehicle routing problem in <cit.>. In these articles, the constraints on the length of a tour starting from a depot are constrained. In the formulation presented here, the length of a tour starting from a depot to each task and the length starting from the task returning to the depot together are constrained. The novelty of this formulation lies in modeling and constraining these two lengths together. Also this could be applied to other routing problem which requires to handle cycle lengths such as min-max traveling salesman problem.

Let T = {t_1, t_2, … t_n } represent a set of tasks, and as in the previous example d be the index referring to the depot. We define the problem on a graph G(V, E). V is the set of nodes V =T ∪{d}, and E is the set of edges between every pair of nodes in V. Let n_v represent the number of UAVs available for the mission. The problem can be stated as the following: find at most n_v cycles that minimizes the maximum delivery time such that, (i) each task T is covered by one cycle, and (ii) if a task t_i assigned to one of the UAVs, v, with cycle length L_v, then L_v ≤ R_i,  ∀ i ∈ T. 



 §.§ MILP Formulation

In the MILP formulation, we use a set of binary variables x_ij's and two sets of real variables u_i's and v_i's. Each variable x_ij corresponds to an edge (i,j), and x_ij=1 if edge (i,j) is in any of the UAV cycles.  Otherwise, x_ij=0. For a particular cycle (assignment), the variables u_i's denote the travel time from the depot to the task t_i, and v_i's represent the return travel time along the cycle from task t_i to the depot; this is illustrated in Fig. <ref>. Let c_ij represent the time elapsed from task t_i to task t_j. Here, c_ij includes the time of travel between the tasks and the time to perform task t_j. Now we present the MILP formulation using degree constraints, sub-tour elimination constraints (SEC) and revisit period constraints. 


Degree constraints: 

    ∑_j ∈ Vx_ij =1 ∑_j ∈ Vx_ji =1,   ∀ i ∈ T, 
       ∑_j ∈ Tx_dj≤ n_v ∑_j ∈ Tx_jd≤ n_v, 
        x_ij∈{0,1 }  ∀ (i,j) ∈ E.
 
Constraints in Equation (<ref>) state that for every node representing a task, there should be one incoming edge and one outgoing edge. The constraints (<ref>) state that there should be a maximum of n_v number of incoming and outgoing edges for the depot node; and the binary constraints on the x_ij variables are in (<ref>).



Sub-tour elimination constraints:

    u_i - u_j + c_ij≤ M(1-x_ij),   ∀ i ∈ V,  j ∈ T 
        c_di≤ u_i ≤ R_i-c_id,   ∀ i ∈ T, 
        v_j - v_i + c_ij≤ M(1-x_ij),   ∀ i ∈ T,   j ∈ V 
        c_id≤ v_i ≤ R_i-c_di,   ∀ i ∈ T.
 
With just the degree constraints, the MILP may produce solutions containing sub-tours; a sub-tour is an assignment where a subset of tasks are connected as a cycle, but are isolated from the depot. One may refer to <cit.> for further reading on sub-tours. One can remove these infeasible solutions using the sub-tour elimination constraints. To this end, we use the inequalities (<ref>, <ref>) similar to the MTZ-constraints used to solve traveling salesman problem<cit.>.
If an edge (i,j) is present in the tour, then the value of the variable u_j should be at least  the sum of travel time from depot to task t_i and the travel time from task t_i to t_j. If x_ij=1, then u_j ≥ u_i +c_ij. This is enforced by the constraints in (<ref>), where M (referred to as big-M in literature) is a constant of arbitrarily high value. When x_ij is zero, the constraint (<ref>) is trivially satisfied. For every t_i, the minimum value of u_i is the direct travel time from the depot to the task, and the maximum is R_i - c_id. These lower and upper limits on u_i's are imposed by (<ref>). Inequalities (<ref>), (<ref>) are equivalent to (<ref>), (<ref>), using the variables v_i's instead. Inequality (<ref>) states that, when x_ij=1, then v_j should be less then v_i - c_ij. Either the set of constraints (<ref>), (<ref>) or (<ref>), (<ref>) are sufficient to eliminate the sub-tours, but we need both of these to formulate the revisit period constraint, which need both sets of variables, u_i's and v_i's. 


Revisit period constraints:

    u_i + v_j ≤ R_i,  ∀ i ∈ T.
 
For each task, u_i is the time of travel from the depot to the task t_i, and v_i is the return time of travel from the task to the depot. Hence, the sum of these two variables gives the time of travel of the full cycle which covers the task t_i. Therefore, inequalities (<ref>) enforce the revisit period constraints for all of the tasks in T. 


Objective:

    z 
        v_i≤ z,   ∀ i ∈ T.

The variables v_i's also are equal to the delivery time of the data collected from each task. To minimize the maximum of all the delivery time, we introduce an auxiliary variable z, which is needed to formulate the min-max objective. The objectives min z and the inequality (<ref>) together minimize the maximum of all of the delivery times (v_i's).

The MILP formulation for the PISR routing problem is the following:

   (ℱ_1)     z 

     

In the above formulation, the big-M in the constraints (<ref>), (<ref>) is known to cause computational problems <cit.>, and hence make the MILP model computationally less efficient. We propose a second formulation without big-M constraints and compare the computational performance of these two formulations.



 §.§ Formulation based on arcs (ℱ_2)


Here, we use the binary variables x_ij's similar to the previous formulation, and the real variables y_ij's and w_ij's  ∀ i,j ∈ V are used instead of u_i's and v_i's.   Variables y_ij represent the travel time from depot to the task t_j if the edge (i,j) is selected in the assignment, i.e., x_ij = 1.  Also, when x_ij=1 the variable w_ij is equal to the return travel time from t_i to the depot. For each task t_i, only one of the variables in the set y_ij,   j ∈ T and one of the variables in the set  w_ij,   j ∈ T's are non-zero. The arc based MILP formulation to solve the PISR routing problem is the following:

















   (ℱ_2)     z 

    

    ∑_j ∈Vx_ij =1  ∑_j ∈Vx_ji =1,    ∀i ∈T,  

    ∑_j ∈Tx_dj ≤n_v  ∑_j ∈Tx_jd ≤n_v,  
 
    ∑_j ∈Vy_ij - ∑_j ∈Vy_ji = ∑_j ∈Vc_ijx_ij,    ∀i ∈T,  

    y_di = c_dix_di,    ∀i ∈T,  

    0 ≤y_ij ≤R_j x_ij,    ∀i ∈V,   j ∈T,  

    ∑_j ∈Vw_ji - ∑_j ∈Vw_ij = ∑_j ∈Vc_jix_ji,    ∀i ∈T,  

    w_id = c_idx_id,    ∀i ∈T,  

    0 ≤w_ij ≤D_i x_ij,    ∀i ∈T,  j ∈V  

    ∑_j ∈Vy_ji + ∑_j ∈V w_ij ≤R_i,    ∀i ∈T,  

    w_ij ≤z,    ∀i ∈T,   j ∈V,  

    x_ij ∈{0,1 }    ∀(i,j) ∈E. 




Here, constraints in the Equation (<ref>) are the degree constraints, which enforce that only one incoming and one outgoing edge exists for any task. Equation (<ref>) imposes the maximum number of edges going out of and coming into depot to be n_v. The time elapsed from leaving the depot to the end of the task t_i is given by the summation ∑_j ∈ Vy_ji, and the time from leaving the depot to the end of the task that is serviced after t_i is given by the summation ∑_j ∈ Vy_ij; these two summation are illustrated in Fig. <ref>. Constraints (<ref>) and (<ref>) ensure that the difference between these two should be equal to the time between t_i and task serviced after t_i. These constraints are needed to eliminate the sub-tours. Equations (<ref>) ensures the variables y_ij's are non-negative always, and nonzero only when x_ij=1. Constraints in  (<ref>) are the counterpart of (<ref>), where the summations ∑_j ∈ Vw_ij and ∑_j ∈ Vw_ji are the return travel times to the depot from the task t_i  and the task serviced before t_i respectively. The difference between these two should be equal to the time between these two tasks, and this is imposed by constraints in (<ref>) and (<ref>). The non-negative and non-zero constraints on variables w_ij's are enforced by (<ref>). The set of constraints (<ref>) - (<ref>) or (<ref>) - (<ref>) are sufficient to eliminates the sub-tours, however we need both of these to implement the revisit rate constraints.

The summation ∑_j ∈ Vy_ji is the time of travel for a UAV from the depot to the task t_i, and the summation ∑_j ∈ V w_ij is the return travel time from the task t_i to the depot. If UAV_v is visiting task t_i, then these two summations adds up to the total time elapsed to service all the tasks assigned to UAV_v. Constraints (<ref>) enforces the maximum limit on the revisit period for each of the tasks. The variables w_ij's are the delivery time of the tasks, hence the objective function min z and the inequalities (<ref>) together minimizes the maximum delivery time.


Inequalities (<ref>) - (<ref>) and (<ref>) - (<ref>) in formulation ℱ_2 can be strengthened using the following inequalities:

    y_ij ≤(R_j-c_jd)x_ij,    ∀i,j ∈V,  

    y_id ≤R_ix_id,    ∀i ∈V,  

    y_ij ≥(c_di + c_ij)x_ij,    ∀i,j ∈V,,  

    w_ij ≤(R_i-c_di)x_ij,    ∀i,j ∈V,,  

    w_di ≤R_ix_di,    ∀i ∈V,  

    w_ij ≥(c_ij + c_jd)x_ij,    ∀i,j ∈V. 



When j is not the depot index, sum of the time from leaving the depot to the end of task t_j and c_jd, direct travel time from the end of task t_j to the depot should be less than the revisit period limit for the task t_j. This inequality is expressed in (<ref>), and since c_jd is non-negative, (<ref>) is tighter than (<ref>). Inequality (<ref>) is same as (<ref>) where j is the depot index. Inequality (<ref>) indicates that when i and j are not depot indices and x_ij=1, then the time to travel from depot to t_j should be at least  the sum of time to travel from depot to t_i and time of travel from t_i to t_j.  

Inequalities (<ref>) - (<ref>) are counterpart of the inequalities (<ref>) - (<ref>) for the w_ij variables. Inequality (<ref>) states that, when x_ij=1, sum of the direct time of travel from depot to t_i and time from t_i to depot along the cycle should be less than the revisit period limit of t_i. When x_ij=1, w_ij is the time from end of task t_i to returning to the depot, which should be at least the sum of time to travel from t_i to t_j and time to travel from t_j to the depot; this is enforced by (<ref>).



To minimize the maximum delivery time, inequalities (<ref>) can be replaced with the following inequalities:

w_di - c_di ≤z,    ∀i ∈T. 



Clearly, the first task serviced has the highest delivery time. If t_i is the first task, then w_di - c_di is the delivery time for t_i. Therefore, the objective min z along with inequalities (<ref>) minimizes the maximum delivery time. Note that, if t_i is not the first task visited, then w_di=0, and (<ref>) is trivially satisfied.


We present the strengthened arc based formulation as follows:

   (ℱ_3)     z 

    

    (<ref>) - (<ref>), (<ref>),(<ref>), (<ref>),  (<ref>) - <ref>).




§ ASSIGNMENT TREE SEARCH HEURISTIC

In this section, we present a heuristic to solve the PISR routing problem. The heuristic is a greedy assignment tree search, based on the prior work in <cit.>, for planning missions involving multiple UAVs. Here, we present a synopsis of the tree search algorithm, however one can refer to <cit.> for further details. This tree search follows a best first search pattern until it finds a feasible assignment. At the root node, the algorithm creates branches and a child node at each branch. Each child corresponds to an assignment of one of the tasks to one of the available UAVs. The number of child nodes are all possible ways to select one unassigned task and assign it to a UAV. Among all the child nodes, the algorithm selects the node with the least cost, and repeats the branching process similar to the branching at root node. This process repeats until all the tasks are assigned.  At this point in the search the algorithm arrives at a "leaf" node, which corresponds to a feasible solution to the planning problem. Once, a feasible assignment is found the algorithm stores the solution as an incumbent solution. It proceeds to search the tree by evaluating the unexplored child nodes, and tries to find solutions of lower cost than the incumbent  solution. Also, the tree search prunes the branches before reaching a leaf node, if the current cost at the branch is more than the incumbent solution. The search is terminated either when it finds a feasible solution, or if it reaches a pre-specified maximum number of nodes to be explored. 

We use this tree search heuristic to find feasible paths for the PISR routing problem. The algorithm is adapted to find feasible paths, such that the cycle lengths of each UAV adheres to the revisit period constraints of the tasks the UAV is assigned, and minimizes the maximum delivery time of all the tasks.

Tree search heuristic:


  * Initialize the problem at a root node with the following: the locations of the tasks, time of travel between the tasks, the maximum limit on the revisit period for each task, and the number of UAVs available.

  *  Create child nodes (n_i), each corresponds to an assignment of a task to an available UAV. Each node corresponds to a list of assignments for each UAV. 

	
  * Compute the current cost of each child node C(n_i), which is the maximum of the delivery times of all the tasks. For example, a UAV is assigned tasks in the order t_s_1, t_s_2, t_s_3, the maximum of the delivery times is the sum c_s_1s_2 + c_s_2s_3 + c_s_3d. ( Here, c_ij is the sum of the time of travel between t_i and t_j and the time to performs task t_j.)
	
  * Check if the assignments violates the revisit period constraints of all the tasks assigned so far. For example if the tasks, t_s_1, t_s_2, t_s_3 are assigned to an UAV, compute the travel time of the cycle c_ds_1+ c_s_1s_2 + c_s_2s_3 + c_s_3d is less than R_s_1, R_s_2 and R_s_3. If any UAV violates the revisit period constraints, assign an infinite cost to the child node.


  *  To select a child node for further branching, we scale the cost based on two factors based on the current task and current UAV that are assigned at each node. The first scale C_s_1 is to force a task with the lowest revisit period limit to be assigned earliest to an UAV. C_s_1 = R_i/R_maxi, where R_j is the maximum revisit period limit of the task t_j that is assigned at the current node, and R_max is the maximum revisit period limits of all the tasks. The second scale S_c_2 is to prioritize a UAV which is assigned a task with revisit limits in earlier assignments (at parent or above nodes); S_c_2 = 10^-n_t, where n_t is the number of revisit period constrained tasks assigned to the current UAV.

  * Select the child node with the lowest scaled cost S_c_1S_c_2C(n_i), and repeat the branching, steps <ref> - <ref>, until a leaf node is found. Update the incumbent solution, and proceed to explore the unevaluated child nodes at the parent nodes and further until another leaf node is found. 

  * Exit the tree search when there are no child nodes to be evaluated, or the number of nodes evaluated reaches the specified limit, and output the solution with the lowest cost. 




§ COMPUTATIONAL RESULTS
 
The MILP formulations ℱ_1 and ℱ_3 are solved using branch and cut algorithm. The algorithms are implemented using CPLEX (version 12.6) with C++ API. CPLEX solves the MILP using branch and cut algorithm, which generates the feasible solutions (upper bounds) and lower bounds based on a solution to the dual problem iteratively, and outputs the optimal solution when the gap between the lower bound and upper bound converges to zero. All the simulations were run on a Macbook with Intel i5, 2.7 GHz processor and 8 GB memory. We generated random instances by choosing task locations (xy-coordinates) from an uniform distribution in a square grid of size 4000 × 4000 meters. We have tested the algorithms on 30 random instances,  10 each with 10, 20 and 30 tasks and 4 UAVs. We impose the revisit period constraints on 3, 4 and 5 of the tasks for the instances with 10, 20 and 30 tasks respectively. For all the instances, we have chosen the task farthest from the depot, and the revisit period limit is set to 1.1 times the sum of the time from the depot to the farthest task and the task to the depot. We have selected the nearest 2, 3 and 4 tasks for the instances with 10, 20 and 30 tasks respectively to set the revisit period limits. We set the revisit period limit to be 1.1 times the optimal cost of the traveling salesman problem solved on these tasks including the depot, with travel times as the cost of travel between tasks. We assume the UAVs travel at unit speed (one meter per second), and the Euclidean distance between the task locations is chosen to be the travel times between them. The tree search heuristic is implemented in C++, and the maximum number of nodes to be evaluated is set to one million. 

The computational results for the 30 instances are shown in the Table <ref>. The first and second column refers to the instance number and the number of tasks in the instance respectively. The third and fourth column refers to the cost of the solution and the computation time required by the formulation ℱ_1. The fifth and sixth column refers to the solution cost and the computation time required for solving using formulation ℱ_3. A time limit of one hour and 2.5 hours are set for solving the instances with 20 and 30 tasks. For the instances where the algorithm could not find optimal solutions in the set time limit, the cost of the best found solution are listed. All the computation times reported are in seconds. The seventh and eighth columns refer to the cost of the first feasible solution found (referred to as best first search solution) and the corresponding computation time by the tree search heuristic.  The ninth and tenth columns refer to the final cost of the heuristic solution and the computation time required after exploring one million nodes of the tree. 

With the formulation ℱ_1, the branch-and-cut algorithm could not converge with in the time limit for instances with 20 and 30 tasks. We could find optimal solutions for all the instances with 10 and 20 tasks using the formulation ℱ_3, and for 4 out of 10 instances with the 30 tasks. Though tight feasible solutions are found, the lower bounds given by the LP relaxations of these formulations are not tight enough, and therefore the algorithm needs more computation time to converge. Finding better valid inequalities may solve this problem, which can be a future direction of this research. From the computational results, clearly the formulation ℱ_3 outperformed ℱ_1. The tree search heuristic generated a best first search solution within 11 milliseconds and final solutions with in 11 seconds for all the instances. Also the cost of these solutions are within 50% of the optimal for most of the instances. This heuristic is well suitable for quick planning and onboard re-planning of the missions. Plots of the solutions found by solving the MILP formulation ℱ_3 and the heuristic for an instance with 20 tasks are shown in Fig. <ref>. One can see that the tasks t_6,   t_8 and t_14 with tight revisit period limits lie on a UAV tour with the smallest tour length. The task t_10 also has revisit period limits, however the corresponding UAV also visits other tasks without violating the revisit period constraints of t_10.








§ CONCLUSION
 
We considered a path planning problem for PISR missions that involves multiple UAVs collecting data from spatially dispersed tasks, and delivering at a depot. We have modeled this as an optimization problem to minimize the maximum delivery time for all the tasks while satisfying the revisit period constraints for the high priority tasks. To find optimal solutions, we presented two MILP formulations ℱ_1 and ℱ_3, which include novel constraints to satisfy revisit period limits. These formulations are solved using branch and cut algorithm, and it could find optimal solutions for instances up to thirty tasks. Also, we presented a heuristic based on assignment tree search; it produces sub-optimal solutions which require only a few seconds of computation time. The heuristic could find feasible solutions for all the instances with in 10 milliseconds. For the missions where onboard re-planning is necessary due to change in the tasks or locations, this heuristic is well suitable for quick onboard re-planning. The future directions of this research include finding better valid inequalities for the formulations to strengthen the lower bounds for computational efficiency. Also one can develop similar MILP models to find paths that minimizes the weighted sum of the revisit periods of all the tasks.
IEEEtran


