Multi-Objective POMDPs with Lexicographic Reward Preferences

1 Introduction

Planning with multiple objectives is prevalent throughout numerous problem domains such as water reservoir control [Castelletti et al., 2008], industrial scheduling [Aissani et al., 2009], energy-conserving smart environments [Kwak et al., 2012], anthrax outbreak detection [Soh and Demiris, 2011b], and semi-autonomous driving [Wray et al., 2015]. Multi-objective Markov Decision Processes (MOMDPs) are commonly used to solve these sequential optimization problems, leveraging a scalarization function which combines the multiple objectives into a single one. However, finding a suitable scalarization function is non-trivial because there may be many valid Pareto optimal solutions to explore, and combining objective functions with differing units may be impossible. Furthermore, according to a recent survey, several existing algorithms are computationally expensive [Roijers et al., 2013]. We leverage the observation that lexicographic ordering of objectives offers a natural way to describe numerous optimization problems [Mitten, 1974;

Sobel, 1975; G´abor et al., 1998; Rangcheng et al., 2001; Wray et al., 2015]. We optimize each objective function in order, only using subsequent objectives to break ties.

Recently, a partially observable model for Multi-Objective POMDPs (MOPOMDP) has been introduced, which generalizes POMDPs using a vector of rewards [Soh and Demiris, 2011a]. We define a new MOPOMDP model with a lexicographic preference over rewards, building upon previous work in this area [Rangcheng et al., 2001] by introducing the notion of slack (allowing small deviation from optimal). This extends the original Lexicographic MDP (LMDP) model [Wray et al., 2015]. Slack increases the space of possible actions for subsequent value functions to utilize, as long as the deviation caused by sub-optimal action selection is within the allotted slack. For example, the highest-priority objective may be to minimize execution time, but within some neighborhood of the optimal time, a secondary objective could be optimized. Work on MOPOMDPs has been sparse outside of evolutionary approaches [Soh and Demiris, 2011a; 2011b]. Constrained POMDPs (CPOMDP) present a similar framework, which states an additional constraint function with a budget [Isom et al., 2008]. The expected constraint penalty must be less than a given limit. In essence, CPOMDPs present a related but distinct problem, since we characterize our problem using deviation from optimal (slack) and allow for many rewards following a preference.

We consider a semi-autonomous driving scenario, which requires the driver to take over control of the vehicle under some conditions [Zilberstein, 2015]. This scenario consists of a car capable of autonomous driving on selected well-mapped roads such as major highways. In order to ensure safety, the car monitors the state of the driver: attentive or tired. The system is not perfect, however, and obtains noisy estimates of the driver's true state. We seek to minimize the travel time while maximizing the time spent safely driving autonomously when the driver is tired. Since autonomous driving is only possible on some roads, it generally increases travel time, but could also increase safety when the driver is tired. The introduction of slack allows the car to select a slightly longer route in order to travel on safe roads which are autonomy-capable.

Our contributions include a new model entitled LPOMDP, which extends an LMDP by addressing partial observability. We present two algorithms for solving LPOMDPs: LVI and LPBVI. These are non-trivial extensions, due in part to our novel definition of slack. Without slack, lexicographic preference orderings would have been far less interesting to utilize because the likelihood of a tie among α-vectors at a belief point is highly unlikely in practice. Hence, without slack, the result would often be a unique policy that optimizes the highest-priority value function while ignoring all secondary optimization criteria. We present three propositions that prove convergence and the proper bounds on slack assignment. We experiment within a recently proposed semi-autonomous driving domain, which constructs POMDPs from real-world road data, using Open Street Map (OSM). Furthermore, we present a novel method for pointbased POMDP and LPOMDP solvers that leverages the massive parallel processing power of a Graphics Processing Unit (GPU). We demonstrate performance of both CPU and GPU implementations within this realistic domain.

Section 2 formally introduces the problem description and relevant background material. Section 3 presents the Lexicographic Value Iteration (LVI) algorithm for LPOMDPs, as well as the Lexicographic Point-Based Value Iteration (LPBVI) variant which enables scalability. Section 4 introduces a convergence result and two strong bounds on slack for both LVI and LPBVI. Section 5 grounds our theoretical results within the semi-autonomous driving application. Additionally, this section covers the GPU optimization that vastly improves performance. Section 6 concludes with final thoughts.

2 ProblemDefinition

LPOMDP encapsulates a multi-objective, partially observable, sequential decision problem such that for each state s the agent lexicographically prefers to improve the value of the state for objective i over objective i � 1. The LPOMDP model extends the Lexicographic MDP (LMDP) model to include partial observability [Wray et al., 2015].

Definition 1. A Lexicographic POMDP (LPOMDP) is represented by a 7-tuple xS, A, Ω, T, O, R, δy:

• S is a finite set of n states
• A is a finite set of m actions, with Apsq denoting the actions available in state s P S
• Ω is a finite set of z observations
• T : S � A � S � r0, 1s is a state transition function, with T ps, a, s1 q � P rps1 |s, aq denoting taking the action a P A in state s P S, then transitioning to state s1 P S
• O : A � S � Ω � r0, 1s is an observation transition function, with Opa, s1 , ωq � Prpω|a, s1 q denoting the probability of observing ω P Ω after taking the action a P A and entering successor state s1 P S
• R � rR1, . . . ,RksT is a vector of k reward functions, with Ri : S � A � R, i P K � t1, . . . , ku, mapping a state s P S and action a P A to a reward Rips, aq
• δ � xδ1, . . . , δky is a tuple of slack values, δi¥0, @iPK

The horizon h denotes the number of time steps in the stochastic process, namely finite (h � 8) and infinite (h � 8), with discount factor γ P r0, 1q. As with most point-based POMDP solvers, we will consider infinite horizon POMDPs and approximately solve them via a large finite horizon.

The agent maintains a belief over the current state, given the history of observations and actions. It is often useful to refer to a set of beliefs B � △n , within the standard n-simplex △n . At each time step, the agent has a belief b P B, takes an action a P A, makes an observation ω P Ω, and updates the belief to b1 P B for all states s1 P S:

,

with normalizing constant c � Prpω|b, aq�1 [Kaelbling et al., 1998]. We often write b1 � rb1 ps1|b, a, ωq, . . . , b1 psn|b, a, ωqsT . The belief state is a sufficient statistic for a history. Note the belief does not depend on the reward vector.

Definition 1 is a direct extension of the original LMDP definition to include partial observability, although we have chosen to omit the state-dependent orderings, wherein the preference ordering could change depending on the belief state. Formally, we would include S � tS1, . . . , Sℓu to be an ℓpartition over B � △n and a tuple of strict preference orderings for each o � xo1, . . . , oℓy, with oj denoting an ordering over the rewards. In other words, we will limit the scope of our investigation to ℓ � 1, i.e., one preference ordering over all belief states: S � tS1u, S1 � △n , o � xo1y, and o1 � x1, . . . , ky. The reason for this is that LPOMDPs are quite expressive with just a single preference-ordering and the inclusion of slack. The additional complexity of belief state-dependent orderings, which previously required a partition assumption for convergence, will be left to future work. In any case, the ordering may be naturally applied following the LMDP model, and our two algorithms for LPOMDPs may also be extended in the natural way.

Policy representations for LPOMDPs are the same as for POMDPs, e.g., policy trees or policy graphs. Formally, we define a policy π : B � A as a mapping from beliefs to actions [Sondik, 1978]. A value function maps belief states to a real value, such that for each reward i P K, Vi : B � R. Let V � rV1, . . . , VksT refer to the vector of value functions. Each value function in belief space, for finite horizon LPOMDPs, is piecewise linear and convex (PWLC) [Smallwood and Sondik, 1973]. This can be represented as a set of r α-vectors Γi � tαi1, . . . , αiru, @i P K, such that @j P t1, . . . , ru, αij � rαijps1q, . . . , αijpsnqsT � rVips1q, . . . , VipsnqsT .

Each α-vector has an associated action, we denote as aα P Aipbq � A, with Aipbq denoting the set of actions available at belief point b P B. Finite horizon LPOMDPs have a Γt , for each time step t. In the exhaustive case, each Γt denotes the α-vectors for all possible histories of length 2t (actions and observations). Infinite horizon LPOMDPs are only approximated by a set of α-vectors, as with POMDPs [Sondik, 1978], explained in the next section.

We write Bellman's equation for the induced continuousstate MDP [Kaelbling et al., 1998] at horizon h, following policy π, given an initial belief state b P B [Sondik, 1978]:

Examining any individual value function i P K at time t, we may write the Bellman optimality equation with:

,

Applying a lexicographic preference ordering over value functions follows similar logic as LMDPs. In an LMDP, for a particular value function i P K, following the ordering, and a state s P S, we allow for a one-step deviation from the optimal value at that state defined by ηi ¥ 0. This enables a restriction on the set of actions available at this state for the next value function i �1 following the ordering. Each value function restricts the actions for subsequent ones, until all value functions have been optimized under these constraints.

This process differs for an LPOMDP, since we do this for a belief state, meaning the set of actions must be appropriately restricted for all belief points. At each time step, for each belief point, we retain α-vectors' actions which are dominated so long as they are within ηi of the maximal value. So long as there exists a belief point for which the α-vector is within ηi of optimal, we must keep it in the set Γti .

Formally, for a value function i P t1, . . . , k�1u, we restrict the set of actions for a belief point b P B, by defining the set of actions available to the belief point Aipbq � A:

with converged values Qi. Since LPOMDPs have an equivalent representation in terms of α-vectors (Equation 2), we may also write this as a restriction to a new set ¯Γi�1 given the original set of α-vectors Γi�1:

Figure 1 illustrates this action restriction. It depicts two belief points b1 and b2; two value functions V1 and V2; and four α-vectors for each value function. The unknown true (infinite horizon) value of V1pbq and V2pbq are shown, as well as the original V 1 1 pbq and V 1 2 pbq which would have been selected if slack was not introduced. First we examine V1. For belief b1, we observe two α-vectors: α11 and α14. The difference between b1 � α11 and b1 � α14 is greater than the allowed slack η1. Therefore, α14 is thrown out of Γt1 . Conversely, for belief b2, the b2 � α12 and b2 � α13 are within ηi so Γt1 contains both. These two sets of α-vectors define the actions available to V2. We make three observations about V2. First, α24 corresponds to the potential α-vector that would have been available had we not removed α14's action. Its actual value was higher, but the first value function restricted the set of available actions for the second value function. Second, α13's action inclusion for the actions available at b2 in V2 enabled it to obtain a higher value (with α23) than it would have if we had only allowed the maximal action to be taken (with α22). Third, the infinite horizon values of V 1 1 pbq decreased slightly to V1pbq because we allowed for slack in order to greatly improve the second value function from V 1 2 pbq to V2pbq.

3 Solving LPOMDPs

We will describe two general methods of solving LPOMDPs: Lexicographic Value Iteration and Point-Based Algorithms.

3.1 Lexicographic Value Iteration

Fortunately, the original formulations of value iteration for POMDPs [Smallwood and Sondik, 1973; Sondik, 1978; Kaelbling et al., 1998] can be directly extended to LPOMDPs. For all i P K, we may write an equivalent equation to Equation 2 following the stochastic process. This result follows exactly as Sondik's formulation.

,

,

Similarly, we define the set of α-vectors, Γti , using a Minkowski sum (cross-sum) operator '. 1 We define sets Γtia� , Γtiaω , for all a P Aipbq and ω P Ω:

Finally, we are able to define Γt :

/

This form constructs all possible combinations of action selections and resulting α-vectors following the policy tree.

We always select our initial vector α's values to be αpsq � Rmin i {p1 � γq for all s P S; this guarantees that α-vectors form a lower bound, remaining the same or improving at each time step [Lovejoy, 1991; Pineau et al., 2006]. Additionally, as others have shown, for each i P K we may assign horizon T to ensure we are within ϵ ¡ 0 such that T satisfies: γ T pRmax i �Rmin i q � ϵ, with Rmax i �max sPS max aPA Rips, aq and Rmin i �min sPS min aPA Rips, aq.

1 For sets A � ta1, . . . , anu and B � tb1, . . . , bmu, A ' B � ta1 � b1, a1 � b2, . . . , a1 � bm, a2 � b1, . . . , an � bmu

3.2 Point-Based Variants

Due to the complexity of exact value iteration in POMDPs, point-based methods have been developed, which perform Bellman updates to a set of α-vectors for a particular set of belief points. Algorithms differ in their selection, addition, and update frequency of belief points: Point-Based Value Iteration (PBVI) [Pineau et al., 2006], Heuristic Search Value Iteration (HSVI2) [Smith and Simmons, 2005], Perseus [Spaan and Vlassis, 2005], and SARSOP [Kurniawati et al., 2008]. At their core, however, they all exploit a new Bellman update that only operates over belief points (Equations 9 and 10).

,

4 Theoretical Analysis

We will now provide a series of theoretical results for LPOMDPs, LVI, and LPBVI. First, we show that LVI converges to a unique fixed point in the limit in Proposition 1. Propositions 2 and 3 give a bound on slack for LVI and LPBVI, respectively. Additionally, they provide a correctness result for both, which guarantees that the returned policy is within the allotted slack.

Proposition 1 (Convergence). Lexicographic Value Iteration (LVI) for LPOMDPs converges to a unique fixed point.

Proof. For all i P K, in order, we have a fixed set of actions for each belief point b P B, restricted from the previous value function i � 1. Therefore, value iteration converges to a unique fixed point for Vi [Smallwood and Sondik, 1973; Sondik, 1978; Wray et al., 2015]. Since this is true for all i P K, once i � k, it converges to a unique fixed point, returning a final policy π. Thus, LVI converges to a unique fixed point Vπ .

With convergence established, we now are able to state a strong slack guarantee in Proposition 2. The proposition guarantees that LVI returns a policy that satisfies the slack constraints. The proof is similar to the one for LMDPs [Wray et al., 2015], with a few adjustments for the belief-state MDPs induced by each value function in an LPOMDP.

Proposition 2 (LVI Slack Bound; Correctness). For i P K, assume 1, . . . i � 1 have converged. Let V η i be the value functions returned by value iteration. Let V π i be the value function returned by the policy π returned after running LVI over all K. If ηi � p1�γqδi, then @b P B, V η i pbq�V π i pbq / δi .

Proof. First, let ρi : B�A � R and τi : B�A�B�r0, 1s denote the reward and state transition for the induced belief state MDP, respectively [Kaelbling et al., 1998]. Let us examine the full expansion of t time steps (t � 8) of Bellman's equation for V π i pbt q.

»

By Proposition 1 there is exactly one unique fixed point, so the initial value V 0 i does not matter. Following the policy, we assign V 0 i pb0 q � V η i pb0 q. In doing so, we recognize the existence of Qηi pb1 , πpb1 qq (the ρp�q plus the integral over b0 ). By Equation 4, V η i pb1 q � Qηi pb1 , πpb1 qq / ηi, since πpb1 q P Akpb1 q � � � � � Ai�1pb1 q. Rewriting this, we obtain Qηi pb1 , πpb1 qq ¥ V η i pb1 q�ηi. Applying this equation, recognizing that γηi is constant, and ‡b0 τpb1 , πpb1 q, b0 qdb0 � 1, we get:

»

We apply this process for all t �8 (let b8 � b), noting that each time an extra γηi falls out, and the previous ones gain an extra product of γ. We also may subtract an extra ηi ¥ 0 to obtain a geometric series.

Assign ηi � p1 � γqδi to obtain our desired inequality.

LVI is guaranteed to converge to a unique fixed point within the afforded slack; now we may analyze LPBVI. Like PBVI, LPBVI introduces an error from the approximation, i.e., using belief points B instead of △n . This affects the set of actions available to the next value function, since some actions may have been included which should not have been. We can, however, account for this in our selection of η in order to guarantee all actions passed to the next value function are valid; Proposition 3 formally states this bound.

Let the density of belief points δB be defined in the same manner as Pineau et al. [2006], albeit with slightly overloaded notation: δB � maxb1 P△n minbPB }b � b1 }1. For i P K, assume 1, . . . , i � 1 has converged. Let the maximal (worstcase) error after horizon t be ϵti .

Proposition 3 (LPBVI Slack Bound; Correctness). For iP K, assume 1, . . . , i�1 have converged. Let V ηB i be the value function returned by PBVI for belief set B. Let V πB i be the value function returned by the policy π returned after running LPBVI over all K. If

Proof. Let V η i and V π i denote the true values following value iteration and LVI, respectively, as defined in Proposition 2. We know that @b P B:

For all b P B, we begin with V ηB i pbq �V πB i pbq:

The worse-case upper bound value comes from the fact that V πB i pbq P rV π i pbq � ϵti , V π i pbqs. In order to guarantee exactly δi slack, we solve for ηi. We also select the maximum of 0 and this value in order to satisfy the constraint:

Interestingly, this bound has the desired property that as we improve the density of our belief points (i.e., B � △n and δB � 0), the acceptable value of each ηi converges to the result from Proposition 2. Additionally, the bound makes intuitive sense: ηi describes the acceptable slack for one iteration's action's deviation from optimal. It turns out that the adjustment of Rmax i �Rmin i 1�γ δB is exactly the definition of PBVI's one-step error [Pineau et al., 2006], which obviously must be accounted for in the tolerable amount of one-step slack ηi.

Equation 11 raises one issue: We cannot compute δB without solving a linear program. Therefore, we will use an approximation ˆ δB � maxb1 PBminbPB }b � b1 }1 to create a weaker slack variable ˆ ηi. It is easy to show that the approximation we will use is an upper bound: ηi / ˆ ηi because ˆ δi / δi. The density of belief points ˆ δB will be updated upon every expansion of B and weakly monotonically decrease.

5 Experimentation

Semi-autonomous systems require collaboration between a human and an agent in order to achieve a goal [Cohn et al., 2011; Zilberstein, 2015]. We experiment within one such domain-semi-autonomous driving-in which a car may only drive autonomously on some subset of autonomy-capable roads, requiring manual driving on the remaining roads. In our scenario the driver may be attentive or tired, extending the original problem formulation by Wray et al. [2015].

States are defined as all pairs of intersections, which implicitly represent location and direction, as well as two Boolean values, indicating whether the driver is tired and if autonomy is enabled. All actions are therefore taken at intersections and simply refer to which road to take next. Additionally, autonomy can be enabled or disabled at an intersection; however, the car can only drive autonomously on major roads, not minor back roads. Following the model introduced by Wray et al., we use a real-world dataset and allow for autonomy whenever the speed limit is greater than 30 miles per hour. State transitions capture the likelihood (0.1 probability) that the human driver will drift from attentive to tired.

An LPOMDP differs from an LMDP in that the true state of the system is unobservable. We do assume that the car's location and autonomy indicator are perfectly observable, and include noisy observations regarding the driver's state. Thus, observations simply denote if the driver is attentive or tired. The observation model captures the inaccuracy of the system monitoring human attentiveness, e.g., an eye tracking system [Pradhan et al., 2005]. In the experiments, we use a 0.75 probability for accurately determining the true state of the driver, with a 0.25 error rate.

We include two reward functions: time and autonomy. The first seeks to reduce time spent to reach the goal, i.e., shortest path. More concretely, it penalizes the agent for the time spent on each road (distance divided by speed in seconds). The second function only penalizes the agent if: (1) autonomy was not enabled while the driver was tired, or (2) the agent did not enable autonomy if it had the option to do so. At the goal state, both reward functions provide zero penalty.

Figure 2 demonstrates an example policy for a section of Boston. At each intersection, the action is shown with arrows. The blue roads are autonomy-capable and white roads are not. Since values and actions exist within an impossibleto-visualize high-dimensional belief space, we simply took two "slices" over this space. We assumed the physical state and autonomy were known, assigning a probability of 0.2 to being attentive and 0.8 to being tired.

5.1 GPUOptimization

To improve the scalability of (L)PBVI and other point-based algorithms, we develop a GPU-based parallel variant for (L)POMDPs. 2 We implemented it within CUDA 3 to demonstrate that CUDA provides a vast performance improvement over CPU-based versions. This is a relatively unexplored, fertile area of research. GPU-based MDP solvers have been developed in the past [J´ohannsson, 2009; Wray et al., 2015], as well as a Monte Carlo Value Iteration GPU solver for continuous state POMDPs [Lee and Kim, 2013]. Crook et al. [2011] parallelized only the belief update equation within a spoken dialog system domain. To the best of our knowledge, no one has explored our parallel approach for point-based solvers that leverages a GPU's parallel computational capabilities.

To start, we divide the update step of (L)PBVI at a horizon into two subproblems, each executed as a kernel (i.e., a program which runs on the GPU). Equation 10 requires a maximization and a summation over states (dot product). This will form our first kernel, which computes the maximal α-vectors over each belief separately in parallel with a simple reduction. In order to do this, however, we must compute the α-vectors within Γtib . This will be our second kernel; it is computed by Equation 9, which contains a summation over observations, a maximization over α-vectors (the size of belief space B), and a summation over states (dot product). Furthermore, Γtiaω must be computed from Equation 6, which is another summation over states. This is done in parallel over beliefs, actions, and observations. The result is cached for use in the first kernel.

Table 1 shows performance over 10 cities, as well as the values of both objective functions at the initial belief point, which has uniform belief over the fatigue of the driver. The improvement ratio of p50�CPUq{GPU is shown, too. These are point-based algorithms without expansion, so each horizon step is the same operation. For that reason, the improvement multiplies the CPU time by 50 as it accounts for the horizon difference, shifting them to the same scale.

2 Trivially, this also works perfectly with point-based methods for POMDPs, yielding the same kind of performance improvements.

3 https://developer.nvidia.com/about-cuda

Experiments were conducted with an Intel(R) Core(TM) i7-4702HQ CPU at 2.20GHz, 8GB of RAM, and an Nvidia(R) GeForce GTX 870M graphics card using C++ and CUDA(C) 6.5. The results demonstrate that the GPU implementation produces a speedup of more than two orders of magnitude over the CPU implementation. Note, however, that our CPU implementation used STL objects, whereas the GPU used arrays. While these results are preliminary and are specific to our implementations, the trend is evident from our initial experimentation in parallelizing (L)PBVI.

6 Conclusion

We present a model for a lexicographic multi-objective POMDP with slack entitled LPOMDP, which naturally captures many real-world problem domains with multiple, prioritized objectives. In fact, it is our novel definition of slack that enables the use of lexicographic orderings in MOPOMDPs. It allows for higher-preference objective functions to slightly deviate from optimal, up to the allotted slack, in order to hopefully improve lower-preference objective functions.

We present two algorithms that solve this problem: LVI, which extends value iteration to LPOMDPs, and LPBVI, which to the best of our knowledge is the first multi-objective point-based algorithm for MOPOMDPs. We prove convergence, as well as bounds on slack for both, thereby proving their correctness. To illustrate our model's applicability to real-world problems, we examine its performance within the recently proposed semi-autonomous driving domain. Our experiments show that our algorithms can solve practical LPOMDPs with large state-spaces-in line with the capabilities of state-of-the-art POMDP solvers. Furthermore, we present a GPU-based version of point-based solvers that reduces runtime by orders of magnitude, and is immediately applicable to a range of existing POMDP solvers.

In future work, we will expand our investigation of LPOMDPs and their applications. Additionally, we plan to make our domain-specific tools public, in addition to both our CPU and GPU source code, to facilitate community-wide development of realistic-scale domains and algorithms for planning under partial observability.

Acknowledgments

We thank the anonymous reviewers for their helpful comments. This research was supported in part by NSF grant number IIS-1405550.