Decision-making under uncertainty: be aware of your priorities

We argue that adaptation decisions need to be informed by the NFRs’ priorities; something that cannot be achieved if the priorities are aggregated into a single combined value. However, it may prove that the priorities assigned at design time are not appropriate or even achievable under certain conditions. The priorities may need to be re-evaluated and changed, informed by the knowledge gained by the SAS encountering such conditions.

Let us define priority-awareness.

The compliance with the requirements (R), according to Zave and Jackson [63], can be achieved using a runtime specification model (S) that is equipped with the newly found knowledge (K’) that has an effect on changing individual NFR priorities.The key challenge here is to have a runtime specification model that has the capability of: Based on [63], next we present our main contributions towards addressing the specified research challenges.

In this paper, we propose Pri-AwaRE, a self-adaptive architecture, that uses an extension of Multi-Reward Partially Observable Markov Decision Process (MR-POMDP) [54, 55] called MR-POMDP++, as a runtime specification model (S) embedded within the MAPE-K loop. MR-POMDP++ is a multi-objective sequential decision-making technique that uses the concept of rewards to:

a. support priority-aware decision-making by providing the runtime modelling and reasoning of priorities of individual NFRs using a vector-valued reward function. Hence, the decision-making takes into account the knowledge (K’) that allows the MR-POMDP++ to re-evaluate the priorities.

b. provide SASs with a principled way to maintain compliance of the Requirements (R) by autonomously tuning the NFRs’ priorities at runtime under uncertain environmental contexts.

We also provide a proof of concept by applying our proposed approach to two different example applications from the networking and IoT domains and comparing it to the existing state-of-the-art techniques. Based on the experiments, we show that priority-aware decisions offered by our Pri-AwaRE architecture support satisfaction of NFRs in terms of more informed choices of NFRs’ priorities.

The paper is organized as follows: Sect. 2 explains baseline concepts related to decision-making in SASs. Section 3 presents the Pri-AwaRE architecture to support priority-aware decision-making in SASs. In Sect. 4, the experiments and evaluations are presented followed by threats to validity in Sect. 5. Section 6 presents related work. Finally, the conclusions and future work are presented in Sect. 7.

SASs are continuously exposed to different environmental contexts that affect the satisfaction of NFRs. During the decision-making process of a SAS, the system performs different tasks that have different impacts on the satisfaction levels of NFRs. The decision-making process of a SAS involves the following key concepts [4]:

The significance of POMDPs to SASs is that they are used to solve sequential decision-making problems under uncertain and dynamic environmental contexts [45, 56]. They offer an agent-based decision-making approach by considering the agents working in a partially observable environment. This means that the agent cannot directly observe the underlying state. Instead, to choose the optimal action, it must maintain a probability distribution over the set of possible states, known as a belief, based on a set of observations and observation probabilities.

An exact solution to a POMDP yields the optimal action for each possible belief over the possible states. The optimal action maximizes the expected reward of the agent over a possibly infinite horizon. The sequence of optimal actions is known as the optimal policy of the agent for interacting with its environment. The basic elements of a POMDP are shown in Fig. 1.

A POMDP is specified as a tuple <S,A,Z,T,O,R,\(\gamma>\) where S represents the set of states specifying a description of the state of the environment; A is the set of Actions that the agent can select to perform at a particular time; Z is the set of observations specifying the information received by the agent from the environment using sensors related to the set of states S; T is the transition function \(T(s,a,s')=P(s'|s,a)\) specifying the probability of moving to the next state s’ given an action a and current state s; O is the observation function \(O(s,a,z)=P(z|s,a)\) specifying the probability of observing the observation z given an action a and resulting state s; R is the reward function R(s,a) specifying a scalar real value generated by the environment as a feedback of the action a performed by the agent provided with the state s of the environment; \(\gamma \) is the discount factor to support the preference for the immediate reward values over the future rewards. The value of the discount factor lies between 0 and 1. The values for rewards are normally assigned by the domain experts at design time based on the information that is provided to them at design time or from the previous experiences [23, 34, 36].

The decision-making agent tries to find the policy \(\pi \), a mapping from the state of the environment to action, that maximizes the value function, i.e. the expected utility value of the sum of discounted rewards, as follows:Hence, based on the current state \(s_{t}\) of the system, the value function \(V_{\pi }\) is used to compute how much cumulative reward, discounted by \(\gamma \), we can expect to get in future, if a particular action is performed in a particular state at time t.

Thus, the reward value R(s,a) is used to evaluate the effect of performing an action a during the state s with the help of a value function. Therefore, a cardinal scale is assigned to each decision made during a specific state of the system to indicate its priority.

As the states in a POMDP are not fully observable, a belief b over the states of the system is maintained. A POMDP offers the capability to quantify uncertainty in terms of the (partially) observed state of the environment. In reference to point-based planning methods [53, 57] for solving POMDPs, that focus on the computation of a policy based on a sampling of points from the belief space, the value function over the belief \({\mathsf{{V}_{b}}}\) is represented by a set of \(\alpha \)-vectors A. Each \(\alpha \)-vector is associated with an action a and has a length of |S| in order to provide a value for each state s. The \(\alpha \)-vector is represented as follows:Here, \( V(s_{i}) \) represents the value of the value function for state \(s_{i} \) given a total number of n states.

Thus, given A, the value over the belief is computed as:Therefore, for each belief b, a set of \( \alpha \) vectors A provides a policy \(\pi _{A}\) for the action that maximizes the value. The application of selected actions by the decision-making agent leads to a change in the state of the system.

MR-POMDP [44, 54, 55], similar to POMDPs, is a sequential decision-making technique used to solve multi-objective decision problems. MR-POMDP is actually a POMDP that has more than one reward values represented in the form of a vector-valued reward function R as shown in Fig. 2. In MR-POMDPs, each objective (NFRs in our case) is associated with its own separate reward value. Hence, the size of the reward vector is equal to the number of objectives. As a consequence, the value function, given an initial belief V\(_{b_{0}}\) for the policy \(\pi \) of the MR-POMDP, is also a vector. Thus, each single element in the value function vector represents the expected utility value associated with each separate objective. As a result, it evaluates the effect of performing an action on the satisfaction of that objective given a particular state. The values of the elements in the value vector, associated with each objective, create a relative ranking for the objectives. Hence, these expected utility values represent the priority of objectives for their satisfaction, while making the decision. We use this built-in capability of MR-POMDPs to compute expected utility value for each individual objective as a base for the autonomous tuning of the priorities at runtime.

As R is a vector, each element in the \(\alpha \)-vector is also a vector as a result creating an \(\alpha \)-matrix, A. Each row in the \(\alpha \)-matrix represents the values for the objectives in a particular state. The multi-objective value of taking an action a associated with alpha matrix A under a belief b is computed as follows:As the value function is represented as a vector in MR-POMDP, there may be multiple policies. The value functions of these multiple policies can be considered as optimal on the basis of the different priorities associated with the objectives. In order to select the best optimal policy from these multiple policies, a scalarization function f(V\(_{b}\),W) is used to scalarize the value vectors V \(_{b}\) with respect to the weights W, and computed by the agent, corresponding to the objectives [43] and computed as follows:where \(w_{i}\) and \(V_{b_{i}}\) refer to the weight and value for the ith objective given n number of total objectives. The size of the weights vector W is also equal to the number of the objectives. In this paper, the weights vector values are computed using the Optimistic Linear Support (OLS) algorithm [44] at runtime.

Hence, for a given belief b, \(\alpha \) matrix for each action and weight w, we can compute the policy \( \pi _{A}\) that takes the maximal value using Eqs. 6 and 7 as:Hence, in MR-POMDP the reward vector is used to represent the priorities of objectives (NFRs in our case) by indicating their desirability in terms of their satisfaction given a particular state of the environment. The reward vector has to be initialized with estimated values. These values are assigned by domain experts and should reflect the experts’ knowledge and the information they have available to them. The design-time assignment of priorities is a normal requirements practice. However, it is difficult to get right and particularly so if, as is often the case for SASs, the priorities assigned to a set of requirements may not be appropriate for all contexts the system encounters at run-time. Nor is the deployment of expert knowledge always easy, as highlighted in [58] where consensus between experts proved hard to achieve. To mitigate these difficulties, Pri-AwaRE permits requirements’ priorities to be revised dynamically at runtime in a principled way. Nevertheless, the NFRs’ satisfaction may be compromised if the initial, estimated reward values are poorly chosen. In our work, we have used simulations [21, 50] to derive good initial values for the rewards.

The Optimistic Linear Support (OLS) algorithm is based on Cheng’s Linear Support [11] approach for solving POMDPs. OLS presented as Algorithm 1 follows an outer loop approach that creates an outer shell around a MR-POMDP solver (Persues¹) [57] to create a solution set known as the Convex Coverage Set (CCS) X [43] to represent the collection of value vectors V\(^{\pi } \)(specifying the multi-objective values) and their associated policies \( \pi \) such that after performing scalarization a maximizing policy is in the set. In order to select the policy having the maximizing value V\(^{*}_{X}(w)\), linear scalarization of the value vector is performed using the parameters in the form of weights vector.² OLS helps in finding these weights intelligently at runtime. The OLS algorithm considering a two objective problem is presented in Fig 3.

The OLS algorithm starts by taking an empty set of X denoting the CCS of value vectors as shown in line 1 of Algorithm 1. The algorithm repeatedly executes steps 2 to 9 until no improved value vectors are found evaluated by the Maximal Possible Improvement \(\varDelta \) [42, 44]. In the first two iterations of the while loop, the algorithm selects the first two corner points as the extrema of the weights simplex, i.e. \(w_{a}\) = 0.0 and \(w_{b}\) =1.0 as represented by the red vertical lines in Fig. 3. Next, the value vectors, for example \(V_{a}\) = [8,1] and \(V_{b}\) =[2,7], for these corner points (\(w_{a}\) and \(w_{b}\)) are computed using a MR-POMDP solver represented by the blue lines in between these corner points. On the basis of these value vectors, a new corner point (\(w_{c}\)) is identified at their intersection. Then, Maximal Possible Improvement \( \varDelta \) [44] is computed for \(w_{c}\). If \( \varDelta \) is improving then for this new corner weight \(w_{c}\), a new value vector \(V_{c}\) = [6,5] is calculated by the calling the MR-POMDP solver as shown in Fig. 3. More corner points are generated such as \(w_{d}\) and \(w_{e}\) from the intersecting points of the existing value vectors. Again Maximal Possible Improvement \(\varDelta \) for each \(w_{d}\) and \(w_{e}\) is calculated. The corner weight (out of \(w_{d}\) and w\(_{e}\)) having high \(\varDelta \) is selected and MR-POMDP solver is called again to compute the value vector for the selected weight. The process is repeated until none of the remaining corner weights yield an improvement in the form of \(\varDelta \).

The process returns a set X known as CCS of the value vectors and their associated policies. As we have more than one policy returned, we have to select the best policy on the basis of scalarization function by taking weight values generated as part of the OLS algorithm. The policy having the maximum scalarized value \(V^{*}_{X}(w)\) is then selected. The flow chart representing the step by step execution of OLS algorithm is shown in Fig. 4. More details on OLS and MR-POMDP solver can be found at [48].

The OLSAR³ algorithm is an extension of OLS algorithm. It follows the same steps as OLS but it reuses the alpha matrices from previous iterations to compute the approximate Convex Coverage Set (CCS) of value vectors.

The MAPE-K control loop is an architectural blueprint for autonomic computing systems and was first introduced by IBM as a vision about Autonomic Computing [25]. As SASs represent a specialized form of autonomic systems, they also employ the MAPE-K architecture loop. This architecture consists of the managing system and the managed system. The managed system corresponds to the application logic while the managing system corresponds with the decision-making agent, which makes use of the feedback loop with the phases Monitor-Analyse-Plan-Execute that run over a knowledge base. It is known as the MAPE-K loop for short. During the Monitor phase, the managing system collects data from the managed system supported by sensors connected to the managed system. In the Analyse phase, the managing system analyses the monitored data to check if adaptation actions are required. If an adaptation action is required, the decision-making agent plans for the adaptive actions that will be performed by the managing system. The goal is to achieve operational goals exhibited by the managed system along with satisfaction of NFRs during the Plan phase. Lastly, during the Execute phase, the planned actions are carried out through the actuators over the managed system. The knowledge K of the MAPE-K loop represents the data required by the managing system to execute all the loop. The runtime model based on the MR-POMDP is embedded in the MAPE-K architecture loop to underpin decision-making for SASs.

In order to illustrate our proposed approach, we consider the example of a self-adaptive Internet of Things (IoT) [2, 61] network. As a concrete application, we consider the simulating environment of DELTA-IoT an exemplar SAS representing an IoT network for a smart campus [21]. The simulator represents a multi-hop IoT network consisting of 15 motes, including RFID sensors, passive infrared sensors and temperature sensors, distributed across the various buildings of KU Leuven campus. These motes, based on LoRa (Long-Range) radio communication, are deployed in each building to provide access to the laboratories, monitor the occupancy status and sense the temperature. The motes communicate with each other to fulfil the functional goal of relaying information to the central gateway deployed at the central monitoring facility of the campus. The IoT networks are required to survive for a long period of time on a single battery along with maintaining communication reliability. Hence, the main goal for an IoT network is to increase the lifetime of the network by satisfying the NFRs of Minimization of Energy Consumption (MEC) and Reduction of Packet Loss (RPL) under uncertain environmental contexts of communication interference and dynamic traffic load. For the purpose of satisfaction of NFRs under uncertain environmental conditions, the network is required to tune network link settings such as the communication range, transmission power and distribution factor for links using different adaptation strategies.

In this section, we present MR-POMDP++, a priority-aware runtime model, to represent the priorities and satisfaction levels of NFRs to perform decision-making in a SAS as shown in Fig. 5. Next, we present the rules for NFRs representation in the form of MR-POMDPs to support runtime decision-making in SASs.

The proposed Pri-AwaRE architecture for SASs is inspired by the feedback architecture of the reinforcement learning (RL) process based on the interactions between the decision-making agent and the environment in which the decision-making agent operates [31]. On the basis of the observations monitored about the current state of the environment, the decision-making agent performs an action in order to achieve the desired goal. This process repeats continuously. Considering the above, we define an architecture for the SASs consisting of two components corresponding to the managed system (i.e. the environment in RL process) and the managing system (i.e. the decision-making agent in RL process), respectively, as shown in Fig. 6.

The Pri-AwaRE architecture structures the managing system (based on feedback loop) interacting with the managed system using probe and effector interfaces [50] as shown in Fig. 6. Our Pri-AwaRE approach focuses mainly on the aspects of the managing system.

In the next subsection, we present the components of the Pri-AwaRE architecture such as the managed and managing system (the decision-making agent). We also present the use of the MR-POMDP++ to support priority-awareness, by providing support to model and represent the satisfaction levels and priorities for NFRs.

The Pri-AwaRE architecture for the case of IoT networks consists of the following two components:

(1)The managed system represents an IoT network. As a concrete example, we consider an IoT network for smart campus represented by the DELTA-IoT simulator [21].

As solving a MR-POMDP is a computationally intractable problem, we have used Optimistic Linear Support with Alpha Re-use (OLSAR) algorithm based on a point-based MR-POMDP solver, to generate approximate solutions by performing approximate backups while computing \(\alpha -\)vectors only for a set of sampled belief values. Hence, it has proven to scale well during the experiments performed. The reuse of the alpha matrix in the algorithm also makes it efficient.

In this section, we define our hypotheses for the experiments. Let us revisit the concept of priority-awareness as defined in Definition 1.

Based on the above concept of priority-awareness, the null H\(_{0}\) and alternative H \(_{a}\) hypotheses are described as follows:

H\(_\mathbf{0}\): Pri-AwaRE does not improve decision-making under uncertainty in comparison with single-objective optimization techniques, which do not offer priority-awareness.

H\(_\mathbf{a}\): Pri-AwaRE improves decision-making under uncertainty in comparison with single-objective optimization techniques, which do not offer priority-awareness.

Next, we provide a description of the example applications and experimental evaluations to test the hypotheses using these example applications.

As our first example application, we have used the simulating environment of DELTA-IoT; an exemplar self-adaptive system representing an IoT network for a smart campus [21]. Next, we present the initial set-up for the experiments using the DELTA-IoT exemplar.

The RDM system [22] is a disaster recovery system for tolerating failures by maintaining multiple replicas (i.e. copies) of data at remotely located mirrors (i.e. servers). Access to the data can continue even if one of the copies of data is lost. Each network link in the network has an associated operational cost⁴ and a measurable throughput, latency and loss rate used to determine the reliability, performance and cost of the RDM system. The goal here is to achieve the satisfaction of the NFRs of Minimization of Costs (MC), Maximization of Performance (MP)⁵ and Maximization of Reliability (MR) under uncertain environmental contexts of link failures and varying ranges of bandwidth consumption [22]. Hence, the network is required to continuously take global adaptive decisions of switching between the topologies of Minimum Spanning Tree (MST) and Redundant Topology (RT) to maintain better levels of satisfaction of NFRs. Both the topological configurations have a different impact on the levels of satisfaction of NFRs. RT provides a higher level of reliability than MST topology but it has a negative impact on the satisfaction of the MC and MP as the cost of maintaining non-stop RT topology will be high and the performance can be reduced because of data redundancy. On the other hand, MST topology provides better levels of satisfaction for MC and MP by maintaining a minimum spanning tree for the network.

The techniques based on Multi-Criteria Decision-Making (MCDM) approaches such as Analytic Hierarchy Process [30] and Primitive Cognitive Network Process [62] to support ranking and explicit modelling of the NFRs have been presented but they are more of design time techniques. However, the approach of ARROW [39], based on P-CNP, provides support to RE-STORM, which is based on a POMDP model [18], to deal with the prioritization of NFRs. With the help of P-CNP, ARROW supports automatic update for initially defined priorities of NFRs at runtime but the update is not autonomous and does not work from within the POMDP model. Our approach tackles this limitation by improving the runtime representation of priorities of individual NFRs underpinned by the multi-rewards support offered by the MR-POMDP model. Hence, different from [18, 39], and supported by the results of the experiments performed, our MR-POMDP-based approach takes it further to support the explicit modelling of the individual NFRs’ priorities, allowing improved runtime reasoning, tuning and awareness during the decision-making process of a SAS at runtime.

In order to support optimization of NFRs, there are also approaches that are based on search based techniques such as [8, 41]. These techniques perform optimization of priorities at design time, while these initially optimized priorities are further used at runtime in an off-line fashion. Therefore, it is considered that the approaches provide an explicit representation of priorities of NFRs but they are design time techniques. In contrast to these techniques, our approach supports the runtime modelling and autonomous tuning of distinct priorities of NFRs to offer priority-aware decision-making and the usage of Optimistic Linear Support algorithm [44] to solve MR-POMDP makes it more efficient.

In order to support decision-making in SASs, a number of runtime modelling techniques have been in use to support priority-awareness. Such techniques include the usage of probabilistic models like Dynamic Decision Networks (DDNs) [4]. The DDNs are used to represent goal model as a runtime model to support decision-making under uncertainty. The DDNs with the help of Bayesian Theory of Surprise [6] provides quantification of uncertainty. The approach represents the priorities of NFRs as a single scalar utility value that represents a combined priority value for all NFRs. This scalar utility value is then used to determine the effect (positive or negative) of the decision of an action selection on the satisfaction of all of NFRs as a whole at runtime. Moreover, the technique based on DDNs deals with the problem of scalability over time (i.e. the curse of history, the graph to represent the history of observations and actions for the DDN planning grows exponentially with the planning horizon). On the other hand, the techniques presented in [1, 9, 16, 33, 38, 59] make use of Markov-based approaches such as Markov Decision Process (MDPs), Partially Observable Markov Decision Processes (POMDPs) and Discrete Time Markov Chains (DTMCs) along with probabilistic model checking to support runtime assurance of NFRs during decision-making in SASs. As these techniques are Markov based (similar to our approach), they support the quantification of uncertainty by maintaining probabilities over the state of the environment. An important limitation of these techniques is that they lack explicit modelling of the distinct priorities of NFRs at runtime. Furthermore, the approaches specifically based on MDPs and POMDPs (with no multiple-reward support) model the ranking of the NFRs as a scalar-reward value to indicate a cumulative priority of all the NFRs hindering priority awareness. Our MR-POMDP-based approach instead tackles these limitations using a vector-valued reward function to support modelling and reasoning about individual priorities of NFRs. Furthermore, our approach, based on the reward vector, also offers and exploits the built-in capability of autonomous tuning of priorities of NFRs. Hence, our Pri-AwaRE approach provides the SAS with a higher degree of awareness of priorities during decision-making.

Furthermore, control theory-based approaches such as [32, 40] have also been used to support explicit runtime configuration and tuning of NFRs. However, the technique in [32] lacks the autonomous prioritization of NFRs, while the approach in [40] lacks the capability of dealing with the NFRs having the same priority rank. Therefore, in such a situation it fails to perform trade-offs of the individual NFRs having the same priority rank as another NFR. Moreover, the technique in [40] also does not consider uncertainty as a quantifiable measure.