Robust Optimization for Hybrid MDPs with State-Dependent Noise

1 Introduction

Many real-world sequential decision-making problems are naturally modeled with both discrete and continuous (hybrid) state and action spaces. When state transitions are stochastic, these problems can be modeled as Hybrid Markov Decision Processes (HMDPs), which have been studied extensively in AI planning [Boyan and Littman, 2001; Feng et al., 2004; Li and Littman, 2005; Kveton et al., 2006; Marecki et al., 2007; Meuleau et al., 2009; Zamani et al., 2012] as well as control theory [Henzinger et al., 1997; Hu et al., 2000; De Schutter et al., 2009] and operations research [Puterman, 1994]. However, all previous solutions to hybrid MDPs either take an approximation approach or restrict stochastic noise on continuous transitions to be state-independent or discretized (i.e., requiring continuous transitions to be a finite mixture over deterministic transitions).

Unfortunately, each of these assumptions can be quite limiting in practice when strong a priori guarantees on performance are required in the presence of general forms of state-

Karina Valdivia Delgado Leliane Nunes de Barros

University of Sao Paulo Sao Paulo, Brazil kvd@ime.usp.br leliane@ime.usp.br

dependent noise. For example, in a UAV NAVIGATION problem [Blackmore et al., 2011], a human controller must be aware of all positions from which a UAV with a given amount of fuel reserves can return to its landing strip with high probability of success given known areas of (state-dependent) turbulence and weather events. In a SPACE TELESCOPE CONTROL problem [L¨ohr et al., 2012], one must carefully manage inertial moments and rotational velocities as the telescope maneuvers between different angular orientations and zoom positions, where noise margins increase when the telescope is in unstable positions (extended zooms). And in a RESERVOIR CONTROL problem, one must manage reservoir levels to ensure a sufficient water supply for a population while avoiding overflow conditions subject to uncertainty over daily rainfall amounts. In all of these problems, there is no room for error: a UAV crash, a space telescope spinning uncontrollably, or a flooded reservoir can all cause substantial physical, monetary, and/or environmental damage. What is needed are robust solutions to these problems that are cost-optimal while guaranteed not to exceed a prespecified margin of error.

To achieve cost-optimal robust solutions we build on ideas used in the chance-constrained control literature [Schwarm and Nikolaou, 1999; Li et al., 2002; Ono and Williams, 2008; Blackmore et al., 2011] that maintain confidence intervals on (multivariate) noise distributions and ensure that all reachable states are within these noise margins. However, previous methods restrict either to linear systems with Gaussian uncertainty and state-independent noise or resort to approximation techniques. Furthermore, as these works are all inherently focused on control from a given initial state, they are unable to prove properties such as robust controllability, i.e., over all states, which have a policy that can achieve a given cost with high certainty over some horizon?

In this work, we adopt a robust optimization receding horizon control approach in which Nature is allowed to adversarially determine transition noise w.r.t. constrained nondeterministic transitions in HMDPs. This permits us to find robust solutions for a wide range of non-deterministic HMDPs and allows us to answer questions of robust controllability in very general state-dependent continuous noise settings. Altogether, this work significantly extends previous results in both the HMDP literature in AI and robust hybrid control literature and permits the solution of a new class of robust HMDP control problems.

2 Non-deterministic HybridMDPs

We first formally introduce the framework of Hybrid (discrete and continuous) Markov decision processes with nondeterministic continuous noise (ND-HMDPs) by extending the HMDP framework of [Zamani et al., 2012]. A robust solution for this model is then defined via robust dynamic programming.

2.1 Factored Representation

An HMDP is modelled using state variables (⃗b, ⃗x) = (b1, . . . , ba, x1, . . . , xc) where each bi ∈ {0, 1} (1 ≤ i ≤ a) represents a discrete boolean variable and each xj ∈ R (1 ≤ j ≤ c) is continuous. To model continuous uncertainty in ND-HMDPs we additionally define intermediate noise variables ⃗n = n1, . . . , ne where each nl ∈ R (1 ≤ l ≤ e). Both discrete and continuous actions are represented in the set A = {a1(⃗y1), . . . , ap(⃗yp)} where each action a(⃗y) ∈ A references a (possibly empty) vector of continuous parameters ⃗y ∈ R|⃗y| ; we say an action is discrete if it has no continuous parameters (|⃗y| = 0), otherwise it is continuous.

Given a current state (⃗b, ⃗x) and next state (⃗b′ , ⃗x′ ) and an executed action a(⃗y) at the current state, a real-valued reward function R(⃗b, ⃗x,⃗b′ , ⃗x′ , a, ⃗y) specifies the immediate reward obtained at the current state. The probability of the next state (⃗b′ , ⃗x′ ) is defined by a joint state transition model P(⃗b′ , ⃗x′ |⃗b, ⃗x, a, ⃗y, ⃗n) which depends on the current state, action and noise. In a factored setting, we do not typically represent the transition distribution jointly but rather we factorize it into a dynamic Bayes net (DBN) as follows:

Here we allow synchronic arcs under the condition that the DBN forms a proper directed acyclic graph (DAG). For binary variables bi (1 ≤ i ≤ a), P(b′i |⃗b, ⃗x,⃗b′ , ⃗x′ , ⃗x, a, ⃗y, ⃗n) are defined as general conditional probability functions (CPFs), which are not necessarily tabular since they may condition on inequalities over continuous variables. For continuous variables xj (1 ≤ j ≤ c), the CPFs P(x′j |⃗b, ⃗x,⃗b′ , ⃗x′ , a, ⃗y, ⃗n) are represented with piecewise linear equations (PLEs) that may have piecewise conditions which are arbitrary logical combinations of ⃗b, ⃗b′ and linear inequalities over ⃗x, ⃗x′ , and ⃗n. Examples of PLEs will follow shortly.

In general, we assume that for each intermediate continuous noise variable nl (1 ≤ l ≤ e) a non-deterministic noise interval constraint function N(nl|⃗b, ⃗x, a, ⃗y) has been defined that represents a range covering α of the probability mass for nl and evaluates to -∞ for legal values of nl and +∞ otherwise. The reason for the ±∞evaluation is simple: in a robust solution to HMDPs with non-deterministic noise constraints, Nature will attempt to adversarially minimize the reward the agent can achieve and hence we let N(nl|⃗b, ⃗x, a, ⃗y) take the value +∞ for illegal values of nl to ensure Nature will never choose illegal assignments of nl when minimizing.

As an intuitive example, if P (nl|⃗b, ⃗x, a, ⃗y) = N(nl; μ; σ2 ) is a simple Normal distribution with mean μ and variance σ2 and we let α = 0.95 then we know that that the 95% of the probability mass lies within μ ± 2σ, hence

Of course, there is no requirement for this interval to be symmetric, so there are technically many ways one could define N to achieve α = 0.95. Thus, the method for defining N given an α must be specified by the modeler.

To make the ND-HMDP framework concrete, we now introduce a running example used throughout the paper:

Example (RESERVOIR CONTROL). The problem of maintaining maximal reservoir levels subject to uncertain amounts of rainfall is an important problem in operations research (OR) literature [Mahootchi, 2009; Yeh, 1985]. In one variant of this problem, a reservoir operator must make a daily decision to drain some water from a reservoir or not subject to weather forecasts over some time horizon. Specifically in a seven day period, we assume that the weather forecast calls for a substantial amount of rain on the fourth day and chances of less rain on the others. The objective of the reservoir operator is to avoid underflow or overflow conditions while maximizing reservoir capacity.

Formally, we assume a state consisting of continuous reservoir level l1 ∈ R and 3 boolean variables ⃗b to encode a time period of eight days. We have two actions a ∈ A = {drain, no-drain}. The reward function R is used to prevent overflow and underflow by assigning -∞ penalty to water levels outside of lower reserve and upper capacity limits and a reward for the amount of water stored at the end of the time step. For both a ∈ A this is formally defined as:

For the transition function, we assume that on each time step ⃗b′ = ⃗b + 1 (not shown) and the reservoir level changes according to the amount of outflow (2000 units of water on a drain and 0 units on a no-drain action) plus a noisy (uncertain) amount of rain n:

The use of the δ[·] function here ensures that the continuous CPF over l′ integrates to 1, which is crucial for defining a proper probability distribution. While these PLEs are deterministic note that all continuous noise in this framework enters via the non-deterministic noise variables in ND-HMDPs. The noisy level of rainfall n is state-dependent and legal intervals are defined as follows:

In short, on day four (⃗b = 4) the amount of rain is expected to be between 1200 and 2000 units, whereas on the other days it is expected to be between 0 and 400 units.

A policy π(⃗b, ⃗x) specifies the action a(⃗y) = π(⃗b, ⃗x) to take at state (⃗b, ⃗x). In a robust solution to HMDPs with nondeterministic noise constraints, a sequence of finite horizon policies Π∗ = (π∗,1 , . . . , π∗,H ) is desired such that given the initial state (⃗b0, ⃗x0) at h = 0 and a discount factor γ, 0 ≤ γ ≤ 1, the expected sum of discounted rewards over horizon h ∈ H (H ≥ 0) is maximized subject to Nature's adversarial attempt to choose value minimizing assignments of the noise variables. The value function V w.r.t. Π∗ in this case is defined via a recursive expectation

where rh is the reward obtained at horizon h following policy Π∗ and using Nature's minimizing choice of ⃗n at each h.

The effect of "max'ing" in each of the previously defined N(nl|⃗b, ⃗x, a, ⃗y) (1 ≤ l ≤ e) with the value function is one of the major insights and contributions of this paper. We noted before that Nature will never choose an illegal value of nl where N(nl|⃗b, ⃗x, a, ⃗y) = +∞, instead it will choose a legal value of nl for which N(nl|⃗b, ⃗x, a, ⃗y) = -∞ which when "max'ed" in with the value function effectively vanishes owing to the identity max(v, -∞) = v.

Finally, by leveraging the simple union bound, we can easily prove that that a policy will achieve V Π∗,H with at least 1-H(1-α) probability since the probability of encountering a noise value outside the confidence interval is only (1 - α) at any time step. Hence for a success probability of at least β, one should choose α = 1 - 1-β H , e.g., β = 0.95 success probability requires an α = 0.99 for H = 5.

2.2 Robust Dynamic Programming

We extend the value iteration dynamic programming algorithm [Bellman, 1957] and specifically the form used for HMDPs in [Zamani et al., 2012] to a robust dynamic programming (RDP) algorithm for ND-HMDPs that may be considered a continuous action generalization of zero-sum alternating turn Markov games [Littman, 1994]. Initializing V 0 (⃗b, ⃗x) = 0 the algorithm builds the h-stage-to-go value function V h (⃗b, ⃗x).

The quality Qha (⃗b, ⃗x, ⃗y, ⃗n) of taking action a(⃗y) in state (⃗b, ⃗x) with noise parameters ⃗n and acting so as to obtain V h-1 (⃗b′ , ⃗x′ ) thereafter is defined as the following:

Here the noise constraints N(⃗n,⃗b, ⃗x) are "max'ed" in with the value function to ensure Nature chooses a legal setting of nl, effectively reducing each max to an identity operation.

Next, given Qha (⃗b, ⃗x, ⃗y, ⃗n) as above for each a ∈ A, we can proceed to define the h-stage-to-go value function assuming that the agent attempts to maximize value subject to Nature's adversarial choice of value-minimizing noise:

The optimal policy at horizon h can also be determined using the Q-function as below:

For finite-horizon HMDPs the optimal value function and policy are obtained up to horizon H. For infinite horizons where the optimal policy has finitely bounded value then value iteration terminates when two values are equal in subsequent horizons (V h = V h-1 ). In this case V ∞ = V h and π∗,∞ = π∗,h .

Up to this point we have only provided the abstract mathematical framework for ND-HMDPs and RDP. Fortuitously though, all of the required RDP operations in (2) and (3) can be computed exactly and in closed-form as we discuss next.

3 Robust Symbolic Dynamic Programming

In order to compute the equations above, we propose a robust symbolic dynamic programming (RSDP) approach building on the work of [Zamani et al., 2012; Sanner et al., 2011]. This requires a value iteration algorithm described in Algorithm 1 (VI) and the regression subroutine described in Algorithm 2. All required operations have been previously defined in [Zamani et al., 2012; Sanner et al., 2011]. In what follows we show how these operations can be used to compute RSDP from the previous section exactly and in closed-form.

In general we define all symbolic functions to be represented in case form [Boutilier et al., 2001] for which a binary "cross-sum" operation can be defined as follows:

Here φi and ψj are logical formulae defined over the state (⃗b, ⃗x) and can include arbitrary logical (∧, ∨, ¬) combinations of boolean variables and linear inequalities (≥,>,≤ ,<) over continuous variables - we call this linear case form (LCF). The fi and gj are restricted to be linear functions. Similarly operations such as ⊖ and ⊗ may be defined with operations applied to LCF functions yielded LCF results.

In addition to ⊖ and ⊗ another key binary operation on case statements the preserves the LCF property is symbolic case maximization:

To demonstrate how VI symbolically implements RDP, we compute V 1 for the RESERVOIR CONTROL example. For both actions, the function Q1a is computed in line 6 using Algorithm 2 with the following operations for action no-drain:

Algorithm 1: VI(CSA-MDP, H) -→ (V h , π∗,h

• Priming V 0 which requires a substitution Q0 = V 0σ where σ = {di \ d′i , lj \ l′j }. Here, V 0 = 0 so Q0 = 0.
• Since the reward function contains the primed variable l′1 , line 4 is performed (and not line 15).
• For boolean variables, regression is performed using f|b=v (restriction operator) which assigns the value v ∈ {0, 1} to any occurrence of b in f - not applicable to the example. For continuous variables line 9 follows the rules of integration w.r.t. a δ function [Sanner et al.,

2011] which simply yields a symbolic substitution:

This results in the following Q-value for RESERVOIR CONTROL :

• Maximizing the result with each of the noise variables in defined line 20 using a sequence of symbolic maximizations. Each noise variable assigns -∞ for legal values inside the boundary range +∞ for illegal values defined by the noise model N(⃗n,⃗b, ⃗x). The result is defined below:

where legal noise value corresponds to [0,400] or [1200,2000] and safe water levels to [200,4500].

The regressed stochastic Qha (⃗y, ⃗n) from Alg 2 is now minimized over the noise variables ⃗n in line 7 of Alg 1. Intuitively this continuous minimization will never choose +∞ as there is always some legal noise value which insures that the illegal noise values are never chosen. Each partition i of this intermediate Q is considered for a continuous minimization separately with the final result a casemin (definition follows from casemax) on all the individual minimum results: casemini minn φi(⃗b, ⃗x, ⃗n)fi(⃗b, ⃗x, ⃗n). We demonstrate the steps of this algorithm for the third partition of the regressed Q defined as:

For each partition the logical constraints are used to derive the (a) lower bound on n (LB = 1200, 200 - l1); (b) upper bound on n (UB = 2000, 4500 - l1) and (c) constraints independent of n (IND = d1, 200 ≤ l1 ≤ 4500). In case of several bounds on n the maximum of all lower bounds and the minimum of all upper bounds is desired.:

The minima points of upper and lower bounds are evaluated for the leaf value which equals to substituting the bounds instead of the noise variable n in the leaf function n + l1:

Natural constraints on bounds LB ≤ UB and the IND constraints are also considered for the minimization on a single partition to obtain:

The final result of a continuous minimization is a casemin over all partitions which results in the following Q-value:

The resulting Q-value with minimal noise is maximized over the continuous action parameter (not available in our example) in line 8. A discrete casemax on the set of discrete actions for all Q-functions defines the final V :

To implement the case statements efficiently with continuous variables, extended Algebraic Decision diagrams (XADDs) are used from [Sanner et al., 2011] extended from ADDs [Bahar et al., 1993].

In summary we remark that all operations including the continuous max and min operations preserve the LCF property, hence all operations for Robust SDP can be performed exactly in closed-form - a novel result for robust solutions to hybrid MDPs with state-dependent noise.

4 Empirical Results

We evaluated Robust SDP on the RESERVOIR CONTROL problem used as a running example, a UAV NAVIGATION problem and a SPACE TELESCOPE CONTROL problem - all risk-sensitive problems as described below. 1

Figure 1 (left) shows the value function for the RESERVOIR CONTROL problem in horizon seven. We can observe that we can gain approximately 11000 units of reward if the reservoir begins with a water level approximately equal to 3000 at day zero. Otherwise, a lower initial starting state or the need to drain when the reservoir is near full lead to lower rewards for all states. Discontinuities in the value function occur at critical points where the policy changes over the time horizon.

SPACE TELESCOPE CONTROL: We have extended the problem of slewing a space telescope in order to look a new objective as given in [L¨ohr et al., 2012]. This problem has six actions a0, · · · , a5 that change the continuous angle k and angular rate v. The problem has one boolean state variable z for the telescope zoom state, one g for reaching the goal state, and one continuous noise variable. To model noise in this problem, we have only modified the transition function for the a5 action in the description from [L¨ohr et al., 2012]

1 All source code and domain definitions can be found at http://code.google.com/p/xadd-inference.

(which could not handle noise) to add noise n when v < 1 deg seg and z = false yielding state updates for a5 as follows:

We model the noise in the transition function of the angular velocity v for a5 (which changes the zoom of the telescope and for which the dynamical model is only approximate) as follows:

where we note that noise depends linearly on the angular velocity.

The reward for actions a0, · · · , a5 is given by

where the cost(a) of action a0 is 0, 1 for actions ai i ∈ {1, 2, 3, 4} and 10 for action a5. Figure 1 (middle) shows the value function for the horizon four. We observe there are states with low angular rate (approximately -0.04 ≤ v ≤ 0.04) that have a policy to achieve a goal (a reward of 100) with high certainty over this horizon.

UAV NAVIGATION: In this problem a UAV needs to be able to plan trajectories that take the aircraft from its current location to a goal given constraints on time or fuel consumption and known areas of state-dependent turbulence (e.g., from localized weather events).

The state consists of a UAVs continuous position x and y and a boolean variable l indicating whether it has landed. In a given time step, the UAV may move a continuous distance ax ∈ [-40, 40] and ay ∈ [-40, 40]. The turbulence introduces noise nx and ny in the ax and ay movements, given by:

The UAV goal is to achieve the region x + y > 200. It receives a reward penalty (-∞) for being in positions from which a UAV with a given amount of fuel reserves cannot return to its landing strip with high certainty.

If the UAV is not in the goal position (¬l), the action reward is a cost of -20 fuel units for the given time period. We note that with six continuous variables in the regression (2 state, 2 action, 2 noise), this problem is relatively high-dimensional and could not be easily solved via discretization methods, which also incur approximation error not encountered in our exact solution provided here.

Figure 1 (right) shows the converged value function for a horizon of four time steps showing the relative cost of returning to the landing strip from different positions with lower values near high levels of turbulence.

Time and Space: Figure 2 shows the time and space for each of the solved problems. The UAV NAVIGATION problem has more continuous variables, however we can see that it is easier to solve than the SPACE TELESCOPE CONTROL, one possible reason is that the latter has more actions with more complex forms of linearly state dependent noise.

5 RelatedWork

This work extends results in HMDP in AI [Boyan and Littman, 2001; Feng et al., 2004; Li and Littman, 2005; Kveton et al., 2006; Marecki et al., 2007; Meuleau et al., 2009; Zamani et al., 2012] and hybrid system control literature [Henzinger et al., 1997; Hu et al., 2000; De Schutter et al., 2009] to handled state-dependent noise.

In the hybrid control literature, a challenging topic is to solve the controllability problem that is NP hard [Blondel and Tsitsiklis, 1999]. A hybrid system is called hybrid controllable if, for any pair of valid states, there exists at least one permitted control sequence (correct control-laws) between them [Tittus and Egardt, 1998; Yang and Blanke, 2007]. Another challenging topic for stochastic hybrid systems, a class of hybrid systems that allows uncertainty, is tried to maximize the probability that the execution will remain in safe states as long as possible [Hu et al., 2000]. This work is related with both topics, however we want to answer a slightly different question, called the robust controllability problem: what states have a policy to achieve a goal (that can be modeled as a reward or cost function) with high certainty over some horizon? To the authors knowledge, in the control area there are few results to answer a similar question except in the chance-constrained predictive stochastic sub-area, that finds the optimal sequence of control inputs subject to the constraint that the probability of failure must be below a user-specified threshold [Blackmore et al., 2011]. However all the previous work in this sub-are is focused on linear systems subject to Gaussian uncertainty and state-independence noise [Schwarm and Nikolaou, 1999; Li et al., 2002; Ono and Williams, 2008; Blackmore et al., 2011] or resort to approximation techniques [Blackmore et al., 2010]. We note that our approach is not approximate and can optimally solve problems with state-dependent noise in a receding horizon control framework that answers the robust controllability question for the first time for such problems.

6 Concluding Remarks

This work has combined symbolic techniques and data structures from the HMDP literature in AI with techniques from chance-constrained control theory to provide closed-form robust solutions to hybrid MDPs with state-dependent noise. Combining this receding horizon control approach with initial-state focused search techniques as in HAO* [Meuleau et al., 2009] should preserve our strong robust optimality guarantees while increasing scalability.

Acknowledgements

NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program.