Performance Evaluation of Multiple Unmanned Aerial Vehicles Operating in General Regime with Shortage of Maintenance Facilities

Author(s)
Joseph Kreimer

Affiliation(s)

Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva, Israel.

Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva, Israel.

Abstract

We consider a real-world problem of military intelligence unit equipped with multiple identical unmanned aerial vehicles (UAV) responsible for several regions (with requests of real-time jobs arriving from independent sources). We suppose that there are no ample maintenance facilities, allowing simultaneous treatment of all vehicles if necessary. Under certain assumptions, these real-time systems can be treated using a queueing theory methodology and/or as Markov chains. We show how to compute steady-state probabilities of these systems, their performance effectiveness, and various performance parameters (for exponentially distributed service and maintenance times of UAVs, as well as tasks duration and their arrival pattern).

We consider a real-world problem of military intelligence unit equipped with multiple identical unmanned aerial vehicles (UAV) responsible for several regions (with requests of real-time jobs arriving from independent sources). We suppose that there are no ample maintenance facilities, allowing simultaneous treatment of all vehicles if necessary. Under certain assumptions, these real-time systems can be treated using a queueing theory methodology and/or as Markov chains. We show how to compute steady-state probabilities of these systems, their performance effectiveness, and various performance parameters (for exponentially distributed service and maintenance times of UAVs, as well as tasks duration and their arrival pattern).

Keywords

Markov Chain, Performance Effectiveness, Queuing, Real-Time Systems, Unmanned Aerial Vehicles

Markov Chain, Performance Effectiveness, Queuing, Real-Time Systems, Unmanned Aerial Vehicles

Received 20 June 2016; accepted 19 August 2016; published 22 August 2016

1. Introduction

From the earliest days of warfare, military commanders have wanted to know what lies over the hill. Today, the battlefield usually holds no secrets from sophisticated flying platforms. Modern airborne reconnaissance structures rely on a combination of satellites, aircraft and unmanned aerial vehicles (UAV). According to recent concept, a real-time data collected by different systems would be further integrated and redistributed in framework of Network-Centric Operations system. It would assimilate the data, recognize and control events, create a mosaic of what is happening at any time and provide a real-time decision support [1] .

To perform these functions properly, the best of modern technologies and methodologies must be used. High on the list of favored options are unmanned aerial vehicles (UAV’s). It is difficult to overestimate their role in real-time intelligence gathering, round-the-clock surveillance and day/night reconnaissance operations. These aircrafts are indispensable in monitoring restricted, hard-to-reach and dangerous locations.

During last two and half decades, various models concerning UAV’s have been presented in scientific literature.

In [2] , the behaviors of each sub-system, including the ground control station, the ground vehicle, a micro aerial vehicle, a high level UAV are investigated and captured and a Kripke model is used to formally describe the system. In [3] and [4] , the Cyclic Routing problem of UAVs is formally defined and a lower-bound on the number of required UAVs is obtained. In [5] , the authors have shown that the Cyclic Routing of UAVs problem is polynomial space PSPACE-complete. In [6] , a flexible model that allows multiple UAVs to cooperatively search for targets, and using a method to efficiently store dynamic target location probability distributions is addressed. In [7] , routing problems for heterogeneous UAVs are studied. In [8] , the authors present the statistical methodology used to devise a quick-running routing heuristic that provides reasonable solutions for UAV. In [9] , the application of a reactive tabu search metaheuristics to UAV routing problem with time windows is considered. In [10] , the maximum probability that the UAVs successfully reach the target is obtained, combining the Markov Decision Process and the sample path technique. In [11] , it is shown how the complex UAV availability model with ample maintenance facilities and general life time and maintenance distributions can be tackled analytically by using a basic model from reliability theory. In [12] , it was shown that even very large number of UAVs did not guarantee the maximum system availability, and optimal routing probabilities were computed analytically (for exponentially distributed service times) via Cross Entropy [13] - [15] simulation approach (for generally distributed service times).

In [16] and [17] , several UAV models have been first described and treated as Real-Time Systems (RTS) with a zero dead line for the beginning of job processing. Further, in [12] [18] [19] and [20] , these models working under a maximum load (worst case) of nonstop data arrival have been treated as queuing networks [21] . RTS with priorities were studied in [22] [23] (preemptive) and [24] (nonpreemptive) respectively.

The use of military systems involving UAVs relies on the principle of availability, i.e. their ability to process the maximal portion of real-time tasks. Traditional definitions of availability are not compatible for complex (e.g. multichannel) systems where changes of performance levels need not be identified with system failure. In [25] , such effectiveness measures as computation reliability and computation availability for gracefully degradable multiprocessor computer system were introduced. These ideas were generalized in [26] , where the concept of performability was formally defined. Another effectiveness measure, called the performance effectiveness index (PEI), and defined as a ratio of the expected system outcome to its maximal outcome, was suggested in [27] . In [28] and [29] , the concept of PEI was adjusted for RTS with ample maintenance facilities working in general regime.

In this work, we study the problem of multiple UAVs operating in general regime with limited maintenance facilities (extension of [28] ). We show how to compute steady-state probabilities of such a system with exponentially distributed service and maintenance times, as well as tasks durations and their arrival pattern. We provide three definitions of PEI and various performance measures for these systems. Finally, we discuss the numerical results.

2. Description of the Model

We consider a military intelligence unit equipped with N identical UAVs responsible for r non-overlapping homogeneous reconnaissance regions required to be under surveillance. The military command sends orders/tasks to patrol the region in real time (e.g. 9:00 - 10:00) without advance notice. If all UAV are not available until 9:30, then only the second half of the order/task gets filled. To observe one region at any moment, only one UAV is needed, thus no additional orders are sent to the region, which is already under observation. Therefore one UAV at most is used (with others being in maintenance or on stand-by or providing the service to another region) to execute the order concerning this region at any moment. Thus, the total number of orders in this military unit cannot exceed the number of regions, i.e. r. Execution of an order, which has found an available UAV starts immediately upon its arrival and continues while where are available UAVs in the system. Different parts (time intervals, e.g. 9:00 - 9:15 and 9:20 - 9:50) of the same order can be executed by different UAVs. Any part of the order that is not executed immediately (e.g. 9:15 - 9:20) in real time is lost. Queues of orders or their parts do not exist in this system.

An UAV flying over any region is operative for a period of time before requiring continuous time units of maintenance, after which it is again available for more time units of activity, and so on. The order/task for which it was responsible is taken over by another available UAV, if exists. and are independent exponentially distributed random values with parameters and respectively. Orders inter-arrival times and their duration times are also independent exponentially distributed random values with parameters, which will be determined later. It is assumed that there are K (K < N) maintenance facilities in this military unit. Each facility can treat only one UAV simultaneously. Thus the shortage of maintenance facilities can appear, and some of broken UAVs will have to wait for maintenance. As it was mentioned earlier, maintenance times are independent exponentially distributed random values with parameter.

3. Steady-State Probabilities

In this section we suppose that: UAV’s operation time (time to failure TTF), its maintenance time, orders inter-arrival and durations times are exponentially distributed. This enables as to treat the model under consideration as a Markov chain.

We define the state of the system (m, n), with and being numbers of orders in the system (i.e. number of regions, which need to be under surveillance) and fixed servers respectively. We denote, the steady-state probability of the state (m, n). Therefore we have states in total.

To be more specific we assume that:

UAV’s operation times are i.i.r.d.v. distributed exp (m), UAV’s maintenance times are i.i.r.d.v. distributed exp (l), orders interarrival times are i.i.r.d.v. distributed exp ((r − m)x), (with arrival rate proportional to the number of regions, which do not need to be under surveillance-without orders) and orders duration times are i.i.r.d.v. distributed exp (h).

There are no additional order arrivals when there are already r orders in the system.

Now we can calculate the numbers of UAVs, regions, orders and maintenance facilities in different positions in terms of m and n, namely:

Number of UAVs out of order is N − n;

Number of UAVs in maintenance (broken) is min(K, N − n) (busy facilities);

Number of UAVs waiting for maintenance (broken) is max(0, N − n − K);

Number of idle maintenance facilities is max(0, K − N + n);

Number of operating UAVs (executing one of orders) is k = min(m, n);

Number of regions under surveillance (executed orders) is also k = min(m, n);

Number of UAVs on stand-by (fixed) is n − k = max(0, n − m);

Number of regions with no order (empty) is r − m;

Number of non-executed orders waiting for service (task’s time is expiring) is m − k = max(0, m − n).

Figure 1 shows the state-transition-rate diagram for this Markov chain, where, e.g.,.

A corresponding set of simultaneous linear equations for steady state probabilities is as follows:

(1)

for the corner state m = n = 0;

(2)

for the corner state m = 0, n = N;

(3)

for the corner state m = r, n = 0;

(4)

for the corner state m = r, n = N;

Figure 1. State transition rate diagram for Theorem 1.

(5)

for “interior” states of diagram 0 < n < N, 0 < m < r;

(6)

for “interior” states on the upper border of diagram m = 0, 0 < n < N;

(7)

for “interior” states on the left border of diagram n = 0, 0 < m < r;

(8)

for “interior” states on the lower border of diagram m = r, 0 < n < N

(9)

for “interior” states on the right border of diagram n = N, 0 < m < r; and finally

. (10)

Thus we have proved the following:

Theorem 1: The steady state probabilities of system under consideration, with N UAVs, r regions, K < N maintenance facilities and independent exponentially distributed TTF, maintenance, inter-arrival (arrival rate proportional to the number of regions with no order) and order duration times is the unique solution of the system of linear Equations (1)-(10).

The system of linear Equations (1)-(10) can be easily solved by standard procedures.

Note: In the system under consideration the backlog of orders/tasks (total time of all orders at any instant) is not influenced by UAVs/servers and maintenance teams since order’s time is expiring anyway (either being processed or lost). Therefore, some of the probabilities (namely of m orders in the system) are the same as those in the model with ample maintenance facilities [28] :

It can be easily transformed to

(10)

Thus the number of orders in the system is distributed binomially.

4. Performance Effectiveness Index and Other Performance Characteristics

Performance Effectiveness Index (PEI) characterizes a system ability to perform its main functions even with partial capacity, and is defined [27] as a ratio of the expected system outcome to its maximal outcome.

For systems under consideration the following definitions were suggested [28] :

Definition 1: The current effectiveness of the system at moment u:

W (u) = (number of operating UAVs at moment u)/(number of orders at moment u).

Definition 2: Performance Effectiveness Index (PEI) of the system is the expected value of the current effectiveness, namely:

It was shown [28] that PEI of this system, considered as a Markov chain at a steady state in terms of steady- state probabilities can be calculated as follows:

(12)

Ignoring the case, when there are no orders in the system, i.e. m = 0.

(13)

Assuming automatically the maximal effectiveness 1 in the case, when there are no orders in the system (m = 0), even if there are no fixed UAVs in the system. And

(14)

by-passing this complications (no order in the system, m = 0)

It is important to remember, that the probabilities in Formulae (12)-(13), are those obtained in the previous Section from the set of linear Equations (1)-(10).

Next we shall show how to calculate some useful performance characteristics of the system under consideration.

Each UAV can be in one of four positions at any moment:

i) fixed and operating;

ii) fixed on stand-by;

iii) in maintenance;

iv) waiting for maintenance (shortage of facilities).

Each region can be in one of three positions at any moment:

i) with processed order inside;

ii) with non-processed order inside;

iii) empty (m = 0).

Each maintenance facility can be either idle or busy at any moment.

Each order/task can be either processed or non-processed at any moment.

Now we can obtain corresponding average values (see Section 3 above):

for average number of fixed UAVs;

for average number of operating UAVs (also an average number of processed orders);

for average number of fixed UAVs on stand-by;

for average number of broken UAVs;

for average number of UAVs in maintenance (also an average number of busy maintenance facilities);

,

for average number of idle maintenance facilities;

for average number of UAVs waiting for maintenance;

(Binomial distribution), for average number of orders in the system (also an average

number of regions needed to be under surveillance);

for average number of non-processed orders;

for average number of empty channels.

Finally, the performance measure can be introduced via cost function. Let C be the cost of one processed order during the time unit, D be the cost of one non-processed order (lost part) during the time unit, G be the cost of one UAV being on stand-by during the time unit, H be the cost of one UAV being in maintenance during the time unit, F be the cost of one UAV waiting for maintenance during the time unit and Q be the cost of one idle maintenance facility during the time unit.

Then the total expected cost per time unit of system operation is given by the following formula

This formula allows to make a good choice of numbers of UAVs and maintenance facilities needed for the proper operation of the system.

5. Numerical Results

In this Section we present some numerical results for N = 9, r = 5 and different sets of values., , , First, second and third lines of each cell contain the corresponding values of and respectively.

It can be easily seen from the numerical results that all three PEI’s:

i) increase, when increases and the rest of parameters do not change (Tables 1-3);

ii) decrease, when increases and the rest of parameters do not change (Tables 1-3);

iii) increase, when increases and the rest of parameters do not change (Table 1, Table 2);

iv) decrease, when increases and the rest of parameters do not change (Table 1, Table 3).

Table 1. PEI for.

Table 2. PEI for.

Table 3. PEI for.

6. Conclusion

In this paper, we presented a real world problem concerning multiple UAVs. Number of orders in this system is binomially distributed and does not depend on UAVs and maintenance facilities, since order/task time is expiring anyway (either being processed or lost). We presented this system as a Markov chain and provided a set of linear equations for steady-state probabilities, as well as performance effectiveness index, average cost function and other performance characteristics.

Cite this paper

Kreimer, J. (2016) Performance Evaluation of Multiple Unmanned Aerial Vehicles Operating in General Regime with Shortage of Maintenance Facilities.*Journal of Computer and Communications*, **4**, 70-78. doi: 10.4236/jcc.2016.410008.

Kreimer, J. (2016) Performance Evaluation of Multiple Unmanned Aerial Vehicles Operating in General Regime with Shortage of Maintenance Facilities.

References

[1] Lin, G.Y., Luby Jr., R.E. and Wang, K.-Y. (2004) New Model for Military Operations. ORMS Today, 31, 26-31.

[2] Ke, Y., Tsourdos, A., White, B. and Silson, P. (2009) Dynamic Mission Planning of Multiple Unmanned Autonomous Platforms for Sensing and Autonomous Urban Reconnaissance. AIAA Guidance, Navigation, and Control Conference, 10-13 August 2009, Chicago, Illinois.

http://enu.kz/repository/2009/AIAA-2009-6216.pdf

[3] Drucker, N., Penn, M. and Strichman, O. (2010) Cyclic Routing of Unmanned Aerial Vehicles. Technical Report, Faculty of Industrial Engineering and Management Technion—Israel Institute of Technology.

http://ie.technion.ac.il/tech_reports/1393234936_AUVSI-Abstract-31Aug2010-submitted.pdf

[4] Drucker, N. (2014) Cyclic Routing of Unmanned Aerial Vehicles. Master’s Thesis, Technion, Industrial Engineering and Management.

http://ie.technion.ac.il/~ofers/cruav/docs/CR-UAV.pdf

[5] Ho, H.-M. and Ouaknine, J. (2015) The Cyclic-Routing UAV Problem Is PSPACE-Complete. Technical Report, Department of Computer Science, University of Oxford, UK.

http://www.cs.ox.ac.uk/people/hsi-ming.ho/UAV14.pdf

[6] Flint, M., Fernandez, E. and Polycarpou, M. (2003) Models of Cooperative Autonomous UAV Search Problem. Military Operations Research, 8, 13-32.

http://dx.doi.org/10.5711/morj.8.4.13

[7] Harder, R.W., Hill, R.R. and Moore, J.T. (2004) A JavaTM Universal Vehicle Router for Routing Unmanned Aerial Vehicles. International Transactions in Operational Research, 11, 259-275.

http://dx.doi.org/10.1111/j.1475-3995.2004.00457.x

[8] Kinney, G.W, Hill, R.R. and Moore, J.T. (2005) Devising a Quick-Running Heuristic for an Unmanned Aerial Vehicle (UAV) Routing System. Journal of the Operational Research Society, 56, 776-786.

[9] O’Rourke, K.P., Carlton, W.B., Bailey, T.G. and Hill, R.R. (2001) Dynamic Routing of Unmanned Aerial Vehicles Using Reactive Tabu Search. Military Operations Research, 6, 5-30.

http://dx.doi.org/10.5711/morj.6.1.5

[10] Lian, Z.T. and Deshmukh, A. (2006) Performance Prediction of an Unmanned Airborne Vehicle Multi-Agent System. European Journal of Operational Research, 172, 680-695.

http://dx.doi.org/10.1016/j.ejor.2004.10.015

[11] Smith, M.A.J., Dekker, R., Kos, J. and Hontelez, J.A.M. (2001) The Availability of Unmanned Air Vehicles: A Post-Case Study. Journal of the Operational Research Society, 52, 161-168.

[12] Ianovsky, E. and Kreimer, J. (2011) An Optimal Routing Policy for Unmanned Aerial Vehicles (Analytical and Cross- Entropy Simulation Approach). Annals of Operations Research, 189, 215-253.

http://dx.doi.org/10.1007/s10479-009-0609-1

[13] Rubinstein, R.Y. and Kroese, D.P. (2008) Simulation and the Monte Carlo Method. 2nd Edition, John Wiley & Sons, New York.

[14] Rubinstein, R.Y., Ridder, A. and Vaisman, R. (2014) Fast Sequential Monte Carlo Methods for Counting and Optimization. John Wiley & Sons, New York.

[15] Kroese, D.P., Taimre, T. and Botev, Z.I. (2011) Handbook of Monte Carlo Methods. John Wiley & Sons, New York.

http://dx.doi.org/10.1002/9781118014967

[16] Kreimer, J. and Mehrez, A. (1993) An Optimal Operation Policy for Real-Time n-Server Stand-By System Involving Preventive Maintenance. European Journal of Operational Research, 69, 50-54.

http://dx.doi.org/10.1016/0377-2217(93)90089-6

[17] Kreimer, J. and Mehrez, A. (1994) Optimal Real-Time Data Acquisition and Processing by a Multiserver Stand-By System. Operations Research, 42, 24-30.

http://dx.doi.org/10.1287/opre.42.1.24

[18] Kreimer, J. and Mehrez, A. (1998) Computation of Availability of a Real-Time System Using Queuing Theory Methodology. Journal of the Operational Research Society, 49, 1095-1100.

http://dx.doi.org/10.1057/palgrave.jors.2600610

[19] Ianovsky, E. and Kreimer, J. (2015) Multiserver Multichannel Real-Time System with Limited Maintenance Facilities under Maximum Load. Open Journal of Applied Sciences, 5, 368-375.

http://dx.doi.org/10.4236/ojapps.2015.57037

[20] Kreimer, J. (2002) Real-Time System with Homogeneous Servers and Nonidentical Channels in Steady State. Computers and Operations Research, 29, 1465-1473.

http://dx.doi.org/10.1016/S0305-0548(01)00042-9

[21] Gross, D., Shortle, J.F., Thompson, J.M. and Harris, C.M. (2008) Fundamentals of Queuing Theory. 4th Edition, John Wiley, New York.

http://dx.doi.org/10.1002/9781118625651

[22] Bassan, E. and Kreimer, J. (2008) Multiserver and Multichannel Real-Time Systems with Separate Queues and Preemptive Priorities. Computer Modelling and New Technologies, 42, 7-15.

[23] Bassan, E. and Kreimer, J. (2009) Multichannel Real-Time System with Single Joint Queue and Preemptive Priorities. Communications in Dependability and Quality Management, 12, 37-50.

[24] Kreimer, J. and Ianovsky, E. (2015) Real Time Systems with Nonpreemptive Priorities and Ample Maintenance Facilities. Journal of Computer and Communications, 3, 32-45.

http://dx.doi.org/10.4236/jcc.2015.37004

[25] Beaudry, M.D. (1978) Performance-Related Reliability Measures for Computing Systems. IEEE Transactions on Computers, C-27, 540-547.

http://dx.doi.org/10.1109/TC.1978.1675145

[26] Meyer, J.F. (1980) On Evaluating the Performability of Degradable Computing Systems. IEEE Transactions on Computers, C-29, 720-731.

http://dx.doi.org/10.1109/TC.1980.1675654

[27] Gnedenko, B. and Ushakov, I. (1995) Probabilistic Reliability Engineering. John Wiley, New York.

http://dx.doi.org/10.1002/9780470172421

[28] Kreimer, J. (2002) Effectiveness Analysis of Real-Time Data Acquisition and Processing Multichannel Systems. IEEE Transactions on Reliability, 51, 91-99.

http://dx.doi.org/10.1109/24.994922

[29] Ianovsky, E. and Kreimer, J. (2009) Multiserver Real-Time System with Shortage of Maintenance Teams. Communications in Dependability and Quality Management, 12, 5-18.