Optimal Abort Rules for Multiattempt Missions

1 INTRODUCTION

When survival of a system has a higher priority than accomplishing a mission, a mission can be aborted if the risk of losing a system becomes too high and a rescue procedure aimed at saving a system can be activated. This is relevant, for example, for aircrafts, submarines, or complex costly technological processes, where the mission abort policy can improve survivability and thus decrease a risk of casualties and/or of substantial economic losses.

In practice, aborting a mission often follows when some degradation parameter describing a system state indicates that system deterioration has reached a critical level. For instance, the number of external impacts (shocks) experienced by a system can be a decision parameter for a possible mission termination, as with each shock, survivability of a system decreases (Levitin & Finkelstein, 2018c). A real-world example of the described scenario is an aircraft that can be required to abort a mission after a certain number of external impacts associated with, for example, malicious activity or nature conditions (e.g., lightning inducing electrical peaks in the electrical circuits). These impacts can cause deterioration of critical systems, which makes risks associated with mission completion unacceptable (Levitin, Finkelstein, & Dai, 2018).

When systems with the mission abort and rescue option are considered, two distinct performance measures should be balanced: the mission success probability (MSP), that is, the probability of successfully completing a mission with or without a specific time frame, and the system loss probability (SLP) indicating the risk that the entire system can be irreparably lost during the mission (Levitin, Xing, & Dai, 2018b; Myers, 2009).

As traditional reliability models are not applicable for addressing effects of mission aborts for evaluating and balancing the MSP–SLP tradeoff, we had to develop a new approach for modeling and evaluating the MSP and the SLP of systems operating in a random environment and subject to mission aborts. This was performed to some extent in our previous work, where relevant optimization problems were also considered (Levitin & Finkelstein, 2018c; Levitin et al., 2018b).

Though the optimal mission aborting rules and relationship between MSP and SLP have become recently a field of intensive study (Cha, Finkelstein, & Levitin, 2018; Levitin & Finkelstein, 2018a, 2018b, 2018c; Levitin et al., 2018; Levitin, Xing, & Dai, 2018a, 2018b; Levitin, Xing, & Luo, 2019; Myers, 2009; Peng, 2018; Qiu & Cui, 2019), all papers in the literature dealing with aborting or termination of a mission consider a single attempt to accomplish a mission, whereas in practice, this can be done several times when the time frame and resources allow for multiple attempts.

Thus, the main objective of this study is to develop a probabilistic model and obtain the optimal aborting rules for situations when the successfully aborted mission can be attempted again. We show that even when mission completion is the only concern (e.g., for the non-safety-critical systems), aborting a mission in the multiattempt policy can substantially improve the MSP, whereas in the single attempt case, a mission abort is never beneficial with respect to the MSP. This interesting and not intuitively evident observation considerably widens the class of systems to which mission aborts can be applied.

Systems in our study operate and perform missions in a random environment modeled by the Poisson process of adverse impacts (shocks). There is an extensive literature on shocks modeling in reliability and risk analysis (see, e.g., the monographs mostly devoted to shocks modeling; Finkelstein, 2008; Finkelstein & Cha, 2013; Nakagawa, 2007). Traditionally, one distinguishes between two major types of shock models: the cumulative shock models, when systems fail due to some cumulative effect, and the extreme shock models when systems can fail with certain probabilities upon any shock (Cha & Mi, 2007; Gut & Husler, 2005; Klefsjo, 1981; Mallor & Omey, 2001). In this article, we develop our approach based on the generalized extreme shock model (Cha & Finkelstein, 2011) when the probability of a failure upon a shock increases with each experienced shock, thus describing the corresponding deterioration in the remaining lifetime of a system. We consider a policy when a mission in the jth attempt is aborted and the rescue procedure is activated immediately after the m_jth shock. The mission abort during the jth attempt is allowed only during the time ξ_j from the start of this attempt.

Missions with a possibility of multiple attempts can occur in different real-world settings when accomplishing a mission is really important and the cost-related and time-wise restrictions for this are not very severe. As far as we know, this type of problem was not considered in the literature so far. The possible motivating examples are discussed below.

Consider an unmanned aerial vehicle (UAV) performing a surveillance mission. During the mission, it should cover the distance W. The adversary uses electronic interference (shocks) to destroy the UAV's control system, which can cause the UAV to crash. Each subsequent interference attack has a larger success probability than the previous one due to overheating and deterioration of the onboard interference filters. Attacks are detected by the UAV's operators and the mission attempt can be aborted upon the occurrence of a predetermined number of attacks. The rescue procedure presumes returning to the base after changing the flight altitude, which causes reduction of the interference attacks rate. After landing, the interference filters are changed and the next attempt to perform the mission starts. If, during any of the attempts, an attack succeeds in destroying the electronic equipment, the UAV is lost and the mission fails. The possible number of attempts, K, is determined by the time window during which the surveillance information remains vital and the time needed to accomplish the surveillance mission (single attempt). The mission succeeds when one of the K attempts to complete the surveillance task succeeds. If all K attempts fail, the entire mission fails.

Another example is a system performing an online “software as a service” task (the mission) consisting of W computational operations. Hackers’ attacks (shocks) can cause data corruption (the mission failure). As each attack, even when it fails, reveals to a hacker some information about the system protection, the probability of the attack success increases with its number. The attacks are detected by the system and the mission attempt can be aborted upon an attack with the predetermined number. When it happens, data check-pointing/backup and software reinstallation is performed (in cloud systems, software migration is usually performed as well), which constitutes the rescue procedure. The protection system is updated to make the information obtained by a hacker in the previous attacks useless. During the rescue procedure, the system is partially disconnected from the communication channels, which causes attack rate reduction compared to the phase of primary mission. After the system rescue, the next attempt to perform the service task starts. If an attack is successful (i.e., it succeeds in corrupting the data) at any attempt, the mission fails. The possible number of attempts, K, is determined by the maximum allowed service time and the time needed to accomplish a single task. The mission succeeds when one of the K attempts to complete the service task succeeds. If all K attempts fail, the entire mission fails.

A number of recent publications (Levitin, Xing, Amari, & Dai, 2013; Lu, Wu, Liu, & Lundteigen, 2015; Ma & Trivedi, 1999; Peng, Zhai, Xing, & Yang, 2014; Wang, Xing, & Levitin, 2015; Wang, Xing, Peng, & Pan, 2017 to name a few) are devoted to analysis of the phased-mission systems that somewhat resemble our setting. However, all referenced papers consider neither abort policies and the MSP-survivability tradeoff, nor the influence of random shocks. The latter is the main goal of our article.

The rest of the article is organized as follows. Sections 2 and 3 present the problem formulation and derivation of the MSP and the SLP. Section 4 presents an illustrative example and the corresponding analysis. Section 5 concludes the article and outlines possible directions for future research. Some supplementary material can be found in the Appendix.

2 PROBLEM FORMULATION

A system performs a mission task that should be completed within a predetermined time θ. The time needed to complete the task without failures is τ < θ. To perform the task, a system should operate in a random environment modeled by the homogeneous Poisson process (HPP) $\{N_M(t),t\ge 0$}, with rate ${\lambda }_M$, where $N_M(t)$ is the number of shocks in [0, t) and $T_1<T_2<\cdots$ are the random arrival times of shocks. Each shock can result in a failure of a system with probability that increases with the number of experienced shocks, thus describing deterioration of a system due to shocks. This means that the more shocks a system survives, there is less probability that it will survive the next shock (see the more detailed description in Section 3).

We assume that shocks are the only cause of system failures. Generalization to the case of internal failures independent from the shock process can be considered in a straightforward way (Levitin et al., 2018).

When some observed factors indicate that system survival in the case of mission continuation is unlikely, a mission can be aborted and a rescue procedure activated. Note that often the environment for the rescue procedure differs from that for the primary mission. Thus, we assume that the shock rate during the rescue, λ_R, differs from that during the primary mission (see example in Section 4).

In this work, we consider aborting a mission upon experiencing the predetermined number of shocks. This creates a possibility of considering the corresponding optimization problem when this number acts as a decision parameter for balancing the MSP and the SLP.

The duration of the rescue procedure is usually a function of the time of its beginning. If the mth shock triggers the mission abort, the rescue procedure duration is φ = φ(t_m), where $t_m$ is the realization of the random T_m. The larger m corresponds to the larger level of deterioration of a system and, therefore, to the larger risks of failure and system loss. When $t_m$ increases, the remaining mission time decreases. Thus, it may become unreasonable to start the rescue procedure if a mission is close to termination and a system has good chances to complete it. Therefore, we assume that the system continues executing the mission if t_m ≥ ξ, where ξ is a time after which the mission should never be aborted. Thus, ξ, along with m, can be considered as a decision variable that can be chosen to achieve a proper balance between the MSP and system survivability.

The above description refers to the case with a single attempt to perform a mission. However, if K attempts are allowed and j < K attempts were aborted with the successful consequent system rescue, the next (j + 1)th attempt can start. In each new attempt, all initial parameters and the attempt duration are the same as before. We will now generalize the single-attempt case to the multiple-attempt one.

It is important to note that although Equations 5, 7, and 8 present a simple multiplicative model, the parameters ${\xi }_k,m_k$, k = 1, 2, …, K can be different at each attempt, which eventually requires obtaining their optimal values while considering the corresponding optimization problem.

The cost of performing the mission and the cost of maintenance before each attempt can also be taken into consideration. However, usually, these costs are negligible compared to the costs associated with mission failure and system loss.

When system safety considerations are not relevant or the system's loss cost is negligible compared with the cost of the mission failure, the unconstrained max R(ξ, m) problem can be also considered.

3 MISSION SUCCESS PROBABILITY AND SYSTEM LOSS PROBABILITY

Our approach is based on the generalized extreme shock model developed in Cha and Finkelstein (2011) when the probability of a failure upon a shock increases with each experienced shock. Let the shock survival probability of a system depend on the number of shocks it has survived in the past, which is a meaningful generalization of the simplest extreme shock model. Indeed, often the resistance of elements to shocks decreases with the number of experienced shocks. Thus, if the probability that a system survives the ith shock at each attempt is q(i), then the probability of surviving all n shocks in this attempt is ${\prod }_{l=0}^{n}q(l)$, where q(0) ≡ 1 by definition.

The computational aspects of obtaining the infinite sum in Equation 13 are addressed in the Appendix.

Remark. In the derivations above, we assume perfect repair after each successful rescue. However, due to various reasons, this repair can be imperfect and the system's initial resistance to shocks can deteriorate with each attempt. To model imperfect repairs, we can assume that the first shock survival probability Ω_j before the jth attempt is smaller than for the previous attempt.

Having the MSP and the SLP evaluation algorithm described above, one can find the optimal mission attempts abort policy m, ξ using any general optimization procedure. In this work, we apply the genetic algorithm (GA) heuristic, the most widely used method in reliability optimization due to its advantages of having flexibility in solution representation, parallel computation possibility, quick convergence to near optimal solutions, and so on (Goldberg, 1989; Levitin, 2006).

4 ILLUSTRATIVE EXAMPLE

Consider an UAV that should cover a distance of 1,250 km between two locations (landing fields) performing a surveillance mission. The UAV speed during the mission is 212.5 km/h. Thus, the mission time is τ = 1,250/212.5 = 5.88 hours. During the surveillance mission, the UAV should remain on the altitude where it is exposed to external shocks caused by electronic interference that can destroy the UAV's control equipment and cause a crash. The shock rate is λ_M = 0.5. The interference filters protecting the UAV deteriorate with the number of experienced shocks because of overheating, which causes the decrease of their resistance to shocks. Model 16 with Ω = 0.99, ω = 0.93 is used to take this deterioration into account.

If the flight mission is aborted when the distance covered from the source location is x = 212.5⋅t, the UAV has to return to the closest landing field, covering the distance min(x, 1,250 – x). To perform the rescue procedure, the UAV descends to the altitude where the electronic interference shocks have the smaller rate, λ_R = 0.1 and reduces its speed to 160 km/h. Thus, the duration of the rescue procedure can be obtained as φ(t) = min(212.5⋅t, 1,250 – 212.5⋅t)/160. After the successful rescue procedure, the interference filters are replaced and the UAV is ready for the next mission attempt. The number of attempts is limited by the time window when the surveillance mission can provide relevant information.

Fig. 1 presents the MSP, R and the SLP, U as functions of the number of attempts K for unconstrained max R and min U solutions (for notational convenience, the arguments of the considered functions are omitted) obtained using the GA. It can be seen that with the increase of the number of attempts, the MSP increases. The SLP for the max R solutions is larger than that obtained for the min U solutions, which means that the compromise max R s.t. U < U^* can be found. Table I presents the optimal mission abort policies corresponding to some unconstrained max R and min U solutions. It can be seen that for K = 1, the largest MSP is achieved when no mission abort is allowed and the UAV tries to complete the mission independently from the number of experienced shocks.

On the contrary, the “most cautious” min U mission abort strategy presumes aborting the mission after the first shock independently from the time of the shock's occurrence (m = 1, ξ = τ). With the increase of the number of attempts, the time interval ξ, when the mission can be aborted, increases for the max R solutions and decreases for the min U solutions. For the max R solutions in the last attempt, the mission abort is not allowed (m = ∞) to maximize the UAV's chances to complete the mission. For the min U solutions in the last attempt, the mission is aborted when the first shock happens at any time (to minimize the SLP).

Observe that unlike the single attempt case when the mission abort cannot improve the MSP, in the multiattempt policy aborting the mission can improve the MSP even when the system's survival is not of interest. This happens because the next attempts can still complete the mission and the overall MSP depends not only on the attempt success probabilities, but also on the probabilities of successful system rescue. This expands the set of situations when mission aborting is justified.

Fig. 2 presents the MSP and the SLP obtained for the max R solutions as functions of the shock rates λ_M and λ_R for K = 3 and K = 5, whereas Tables II and III present abort policies for some of these solutions. It can be seen that both the MSP and the SLP are much more sensitive to variation of the shocks rate during the primary mission than to variation of the shocks rate during the rescue procedure. With the increase in the shocks rate, the max R abort policy allows for more shocks to happen and increases the duration of the mission interval when no aborts are allowed. These changes give the UAV more chances to complete the mission.

Tables IV and V present the best obtained max R s.t. U < U^* mission abort policies for K = 3, K = 5, and different values of U^*. It can be seen that for most of the obtained solutions, mission attempts should be aborted after the first shock and the balance between the MSP and the SLP is achieved by changing the intervals [0, ξ_j] when abort is allowed.

The values of ξ_j decrease in U^*, which corresponds to a “more risky” policy that gives the UAV more chances to complete the mission attempts. If for some reason the value of ξ_j cannot vary from attempt to attempt (e.g., when environmental conditions do not allow the UAV's descent to the safe altitude during a part of its route), the proper balance between the MSP and the SLP is achieved by changing the number of allowed shocks m_j. Tables VI and VII demonstrate the best obtained max R s.t. U < U^* mission abort policies for ξ_j = τ in all attempts and ξ_j = 0.8τ in all attempts. It can be seen that with the increase of the allowed value of the SLP, the number of allowed shocks increases, which weakens the abort conditions and gives the UAV more chances to complete mission attempts.

Fig. 3 presents the MSP, the SLP, and the normalized expected losses C(ξ, m)/C_F = (1–R(ξ, m)) + U(ξ, m)C_L/C_F for solutions of the min C(ξ, m) problem as functions of the cost ratio C_L/C_F for different numbers of attempts, K. Table VIII presents the best abort policies for some of these solutions. It can be seen that when the C_L/C_F ratio is small (mission completion is much more important than system survival), one should choose the maximum possible number of attempts to minimize the expected losses. On the contrary, when the C_L/C_F ratio is large (system survival is much more important than mission completion), one should choose the one-attempt policy to minimize the risk of system loss.

5 CONCLUSIONS

Previous works on mission aborting have discussed a situation when only one attempt to complete a mission is allowed and this attempt can be aborted. In this article, we develop the relevant probabilistic model and formulate the corresponding optimization problems for the multiattempt setting. The detailed example illustrates the solution of the optimization problems both for the constrained/nonconstrained maximization of the MSP and for the minimization of the cost of losses.

In the one-attempt setting, obviously, the mission abort cannot increase the MSP and is performed only for increasing the corresponding survivability. However, even when system's survival is not important, mission aborting can be used to maximize the MSP when several attempts to complete a mission are allowed. This is an important observation that considerably widens the class of systems that can employ mission aborting.

The detailed sensitivity analysis is performed for both optimization problems with two decision parameters in each attempt, that is, the number of shocks experienced by the system, $m_j$ and the time ${\xi }_j$ after which aborting is not performed. For instance, it can be seen that both the MSP and the SLP are much more sensitive to variation of the shock rate during the primary mission than to that during the rescue procedure. It is shown that when considering minimization of expected losses and the C_L/C_F ratio is small (mission completion is much more important than system survival), one should choose the maximum possible number of attempts to minimize the expected losses. On the contrary, when the C_L/C_F ratio is large (system survival is much more important than mission completion), one should choose the one-attempt policy to minimize the risk of system loss.

As a possible direction for future research, one can consider more general imperfect repair models than those discussed in the Remark. Specifically, imperfect repair after system rescue can decrease the damage accumulated by the system after experiencing the observed number of shocks (condition-based imperfect repair). The overall mission cost minimization that includes expected cost of rescue procedures and repairs along with the penalties associated with mission failure and system loss can be considered. The case when a part of the mission task that was accomplished in the earlier attempts can be saved (additively) and not discarded should also be addressed.