Kemeny Elections with Bounded Single-Peaked or Single-Crossing Width

1 Introduction

The expected increase in the number of electric vehicles (EVs) necessitates novel solutions for managing the infrastructure required to charge these vehicles [R.A.E., 2010]. One of the most significant potential bottlenecks is the congestion at charging stations. This is likely to occur because fully charging an EV currently takes between half an hour and several hours and, moreover, EVs need to be charged frequently to complete longer trips. In order to address this challenge, new navigation systems need to be designed that predict congestion at charging stations based on stochastic information about arrivals, and then suggest to EV owners the most efficient route and station, in order to minimise both travel time and expected delays due to charging.

Within the transportation literature, the problem of optimal routing under uncertainty has been studied for several years. In particular, Hall [1986] and later Gao and Chabini [2006]

∗This work was supported by the ORCHID (orchid.ac.uk) and iDEaS projects (ideasproject.info).

Enrico H. Gerding, Sebastian Stein, Valentin Robu, and Nicholas R. Jennings

University of Southampton {eg,ss2,vr2,nrj}@ecs.soton.ac.uk

show that optimal policies can be computed even for settings where the stochastic information is not only link-dependent, but also time-dependent (i.e., travel times are conditional on the time of day). These approaches compute routing policies, i.e., time and location-dependent directions, to deal with such situations where travel times are not known in advance. However, they currently do not consider the specific requirements of EVs, which have a limited charge and may need to route past charging stations to reach their destination.

The problem of routing agents through a network is also studied using game-theoretic approaches. In this vein, Gawron [1998] studies a model in which each driver's choice over alternative routes is given by a discrete probability distribution and finds a dynamic equilibrium through simulation. However, these approaches take a centralised perspective and, moreover, abstract away from the details of the problem we consider related to EVs, such as their charging state and delays at charging stations.

A crucial problem, from an EV perspective, is coordinating en-route charging. Since charging EVs takes time and the capacity at charging stations is limited, waiting times can contribute significantly to the total journey time. For example, if one additional vehicle arrives at a station with a single charging point, this could immediately result in a 30-minute delay to all subsequent arrivals. Indeed, this problem has been recognised before. In particular, Qin and Zhang [2011] propose an approach where congested charging stations divert EVs by placing reservations at less congested stations on the same route. Kim et al. [2012] develop a constraint-based scheduler for charging stations to prevent peak consumption. These existing solutions are based on reserving a specific time slot. However, travel times are typically uncertain, and the distribution of such travel times changes throughout the day. Because of this, delays give rise to changes in the arrival time, but could also necessitate re-routing to a different charging station, invalidating any reservations.

To address this problem, we propose a novel IntentionAware Routing System (IARS), which is implemented as a software agent embedded in the navigation system of an EV. Crucially, this agent autonomously exchanges intentions (i.e., routing decisions) with other IARS agents. These intentions constitute probabilistic information about which stations the EVs will visit and when, thereby allowing the agent to accurately predict congestion (and thus waiting times) at charging stations and compute the most efficient route for the EV owner. Our proposed system employs and extends a range of techniques from the field of artificial intelligence to deal with the highly dynamic and uncertain environment it operates in. In more detail, it makes the following contributions to the current state of the art:

• We formalise the optimal EV routing problem with enroute charging stations. This is a challenging problem, because both travel and waiting times are stochastic and timedependent. Furthermore, the problem is highly constrained by the current state of charge of an EV and the need to route via charging stations.
• We propose the first EV routing system that uses intentions to produce accurate predictions of waiting times at charging stations. A key contribution of this system is its novel approach to fusing a range of information sources that vary in their precision - from information about historical and recent EV arrivals at stations (including from those EVs that do not communicate their intentions), to the probabilistic information encoded in the agents' intentions.
• We show experimentally that IARS leads to a significantly higher utility than state-of-the-art routing algorithms that rely only on historical information about road travel times (as used by some modern navigation devices). In some cases, our approach leads to an over 80% improvement in waiting times and a more than 50% reduction in overall journey times. As IARS also reasons about agents that do not use intentions, we demonstrate that even when only a small proportion of EV drivers use IARS, they achieve a significantly higher utility than those that do not.

The remainder of the paper is structured as follows. In Section 2 we formalise the routing problem with en-route charging. Then, in Section 3, we explain IARS and in Section 4 describe our experimental results. Finally, Section 5 concludes.

2 Model

First we introduce our model of stochastic time-dependent routing for EVs, where roads and charging stations are abstractly represented by probability distributions of their waiting time. We then go on to model the charging stations and the waiting times explicitly, which enables us to derive the waiting time probabilities when computing the policies, taking into account the intentions of other EVs.

2.1 The EVRouting Problem

We model an EV routing domain by 〈V, E, T, P, S, C〉, with directed edges e = 〈vi, vj〉 ∈ E and vertices vi, vj ∈ V . Edges represent either roads or charging stations, denoted by Estations ⊂ E and Eroads ⊂ E respectively. Roads and charging stations incur a probabilistic amount of travel or waiting time, described by a probability mass function P (more details below). These travel and waiting times vary depending on the time of the day, and T = {1, 2, . . . , tmax} denotes a finite set of time points (e.g., within a day, or over a week). Roads furthermore incur a cost to EVs in terms of power usage, whereas charging stations reset the EV battery to its maximum capacity level (we assume that a battery is always fully charged at a station). To this end, we introduce a finite set of possible charging states S = {0, 1, . . . , smax}, where a state represents the current capacity of the battery, and smax denotes a fully charged battery. Furthermore, we introduce function C, where C(e) ∈ S is the (deterministic) charging cost for edge e ∈ Eroads. 1 This charging cost is deducted from the current state of charge when the edge is traversed.

We consider time-dependent stochastic travel and waiting times and treat them as stochastically independent. That is, conditional on the time of day, the distributions at edges are uncorrelated, and we do not take into account that these distributions may be updated over time. This is common in the stochastic routing literature [Hall, 1986]. Formally, P(tb - ta|e, ta) denotes the probability mass function of the travel/waiting time at edge e = 〈va, vb〉 ∈ E, where ta ∈ T denotes the arrival time at vertex va, and tb ∈ T, tb ≥ ta the arrival time at vertex vb. Thus, when e is a road, then tb - ta is the travel time, and when e is a charging station, tb - ta is the combined waiting and charging time.

Given this, the problem is to find an optimal routing policy π∗ which maximises the agent's expected utility without running out of charge at any point during the journey. Formally, a routing policy is a function π : V × T × S → V which gives, for each vertex, each possible realisation of the arrival time, and each state of charge, the next vertex. Then, given a policy π, our current position vc ∈ V , current time tc ∈ T, current state of charge sc ∈ S and final destination vdest ∈ V , the first edge to follow is equal to ec = (vc, π(vc, tc, sc)) and the expected utility for the policy π can be computed using the following recursive formulation:

where s′ = SOC(ec, sc) determines the new state of charge when traversing edge ec, i.e., SOC(ec, sc) = sc - C(ec) if ec ∈ Eroads and SOC(ec, sc) = smax if ec ∈ Estations. Furthermore, U(tc, sc) is the agent's utility function for a given arrival time tc and a state of charge sc on arrival such that U(tc, sc) = -∞ if sc < 0. Otherwise, for example, U(tc, sc) = -tc; then maximising the expected utility means minimising the expected time of arrival.

The optimal policy is then given by π∗ (vc, tc, sc) = argmaxπ∈Π EU((w, π(vc, tc, sc)), tc, sc|π), where Π is the set of all valid policies.

2.2 Charging Stations Model

So far, we have modelled the waiting times at both edges and stations using abstract probability distributions, and we have not discussed where these distributions actually come from. Now, a main contribution of our paper is to combine historic information and intentions (policies) of other agents to derive the waiting time distributions at charging stations (we assume

1 Since we compute the route for each vehicle separately, it is straightforward to extend this model by allowing a different function C and a different smax for each type of EV.

• 10

1 user input: destination vi,dest 2 initialise vi, si, and ti to the current state 3 compute P arr based on historical arrivals 4 while vi ̸= vi,dest do 5 input: states vj, sj, tj, intentions πj, ∀j ∈ I \ {i}, and new arrivals 6 compute P arr j (e, t), ∀j ∈ I 7 compute P (∆t|e, t), ∀e ∈ Estations 8 compute policy πi 9 output: intention πi and current state vi, si, ti execute policy and update vi, si, ti

that the distributions for roads are derived using existing approaches, such as [Eglese et al., 2006], since they are influenced less by individual EVs). However, to do so, we first need to explicitly model the queues at the charging stations. In Section 3, we then show how we use this model to derive the waiting time probability distributions using a principled approach that includes the intentions of other agents.

The queueing model is as follows. We assume that each station e ∈ Estations has a fixed capacity, cape, due to space or electricity network constraints. This capacity is the maximum number of vehicles that can charge simultaneously. Furthermore, for simplicity, we assume that the time to (fully) charge a vehicle, denoted by tcharge ∈ T, is fixed (although it is straightforward to extend the model to stochastic or chargedependent times). We assume a first-come-first-served queueing model when the station is at full capacity and that there is no queue before time t = 1. Finally, if several EVs arrive at the same time, we assume they arrive in the order of their ID.

3 Intention-Aware Routing System

The IARS optimises the policy of an EV using the intentions of other EVs. The main feature of this system is that it is able to route using only historical information when no other information is available, but then gradually replaces this information with more accurate information about vehicles whose intentions become known or change, and as vehicles actually arrive at the stations. Algorithm 1 presents an overview of the steps involved. In detail, the journey starts by the user, denoted by i, entering his or her destination, vi,dest. The system is then initialised based on the current location, state of charge and departure time (line 2). Before it can compute the optimal policy (line 8), it needs to process the historical information about arrivals of vehicles at stations, and combine these with the currently known intentions of other users in the system and actual arrivals at the stations (lines 3, 6, and 7, detailed in the subsections below), where I denotes the set of EVs whose intentions are currently known. Importantly, since the system only knows intentions of users who have already entered their destination, the set I is not fixed and can change over time with users entering and leaving the system dynamically. For this reason, and because the available information is continually updated (line 5), the probability distributions and optimal policies are also updated at each new vertex (i.e., the decision points). We now describe the computation steps, lines 3, 6, 7, and 8 in detail.

3.1 Historical Arrival Probabilities

A possible approach to compute waiting times probabilities is to keep track of the historic waiting times, and simply take the average waiting time for each station and time point. However, this approach does not readily allow information of individual vehicles to be integrated as and when this becomes available. We therefore take a different approach which keeps track of when and where (i.e., at what station) vehicles arrive for charging. 2 We then aggregate these historical arrivals to compute the probabilities P arr (e, t) which gives, for an average EV, the probability that he or she arrives at station e ∈ Estations at time t ∈ T. In Section 3.3 we then show how this distribution is used to estimate the queues at the stations, and compute the waiting times.

3.2 Intention-Based Arrival Probabilities

The historical arrival probabilities represent the likelihood of a vehicle arriving at a certain station at a certain time, without having any additional information about these vehicles. However, a key aspect of our approach is that, for those vehicles with intentions, we can derive much more accurate estimates about which station they are going to visit, based on their current state and their policy (note that the information about station visits is still probabilistic since the actual route and arrival time depends on the realised travel times). To this end, we show how to derive P arr i (e, t), the probability that EV i is at station e ∈ Estations at time t ∈ T .

In detail, given πi, the current state (vi, ti, si) of i, and known travel time distributions at road edges P (∆t|(v, w), t), we can compute P arr i via summing up over s ∈ S of P arr i (v, t, s), the probabilities that i arrives at a particular vertex v at a particular time t with charging state s, using the dynamic program below:

P arr i (v, t, s) ← 0 for all v, t, s, but P arr i (vi, ti, si) ← 1 P arr i (e, t) ← 0 for all t ∈ T, e ∈ Estations for t ← 1, 2, . . . , tmax do forall the v ∈ V and s ∈ S do if P arr i (v, t, s) > 0 then (v, w) ← π(v, t, s) if (v,w) ∈ Estations then add P arr i (v, t, s) to P arr i ((v,w), t) for ∆t ∈ T do add P (∆t|(v, w), t) to P arr i (w,∆t + t, SOC((v,w), s))

3.3 ComputingWaiting Times Probabilities

We now discuss the main part of the system and show how to compute the waiting times probability mass function, P(∆t|e, t), by combining the historical information, P arr , with known arrivals so far, and with the intentions-derived probabilities, P arr i , i ∈ I, where I is the set of EVs who have (so far) reported their intentions to the system. We let n denote the total number of unique vehicles that have charged in the past (across stations), including both ones that use the system, and ones that do not. For simplicity, we assume that each EV charges en-route at most once a day, although having a single vehicle charge multiple times can be approximated by considering these are different vehicles (in which case n is the maximum number of charges per day). Furthermore, let m denote the number of vehicles who have already charged today, and I ′ ⊆ I those vehicles with known intentions who still need to charge (i.e., they are visiting a station with nonzero probability). Given this, there are n -m EVs that may still choose to charge, of which |I ′ | we know their intentions.

2 In practice, this can be achieved, for example, through sensors and/or credit card payment information at stations.

We then approximate the probability mass function using Monte-Carlo simulation as follows. For each sample, we independently draw for n - m - |I ′ | vehicles a pair 〈e, t〉 ∈ (Estations ×T) ∪ {⊥} according to the probabilities P arr (e, t|not charged), i.e., the arrival conditional on not having charged before (where the probability of charging before the current time is zero). Here, P arr (⊥)=1∑e∈Estations,t∈T P arr (e, t|not charged) is the probability that the EV does not charge at all. Similarly, we draw a single pair 〈e, t〉 from each distribution P arr i (note that we do not need to compute the conditional distribution, since it has already been updated). Finally, we add the EVs that have already arrived today with probability 1. Then, starting from t = 1, we simulate the queues at each station based on the model described in Section 2.2 until the end of the day, and measure the waiting times for each future time point. This process is repeated for a number of times (in the experiments in Section 4 we use 100 samples), and P(∆t|e, t) is estimated by averaging the waiting times at each station and time slot.

3.4 Computing the Optimal Policy

The final part is the computation of the routing policy. Since for every computation of EU the policy πi is required only for times strictly later than ti (we assume ∆t > 0), the optimal policy can be computed using dynamic programming in line with work on Markov decision processes [Puterman, 1994] based on the following recursive definition: if vi = vdest or si ≤ 0, then there is no good decision, and otherwise π∗ (vi, ti, si) = argmax{e|(vi,w)∈E} EU(e, ti, si|π∗ ). All computations described above can be done in O (|T|2 · |V | · |S| · |E|).

4 Experiments

In this section, we experimentally evaluate our intentionaware routing system in a wide range of settings. The purpose of this is to establish and quantify the potential benefits of 1) modelling station waiting times and 2) incorporating other agents' intentions into routing decisions. For ease of presentation, we assume that all agents wish to minimise their arrival time at the destination, and therefore our primary measure of performance is the average journey time of individual agents. In the following, we first describe the benchmarks we test, provide details of our setup and then present the results.

4.1 Benchmarks Solutions

We evaluate a range of navigation systems in this section:

• IARS: Our proposed intention-aware routing system, which is the main contribution of this paper.
• MIN: A system that always minimises the expected journey time. As such, it simulates existing state-of-the-art navigation systems.

· LOGIT(λ): This is a randomised variant of MIN. We include this, because agents employing MIN on similar source and destination pairs will often follow the same routes, exacerbating congestion at charging stations. While this is an inherent problem with current routing systems, we are interested in whether occasional randomisation may alleviate this. To achieve this, we use an approach where the probability of selecting an alternative is directly related to the expected utility of that same alternative. This is in line with work on the logit agent quantal response equilibrium [McKelvey and Palfrey, 1998] and is defined as follows. Given a λ ∈ [0,∞] the probability of selecting an edge e is defined as:

The policy π′ (vc, tc, sc) is then just drawn from this distribution, and the expected utilities are computed knowing that this distribution is used in future time steps, i.e., EU((u, vc), tc, sc|π′ ) = ∑{e′ |(vc,w)∈E} P(e′ |vc, tc, sc) · EU(e′ , tc, sc|π′ ).

We also attach a parameter FALSE or TRUE to each approach other than IARS, which determines whether the system models waiting times at charging stations using historical arrivals (TRUE), or always assumes the minimum charging time (FALSE). As such, MIN(FALSE), for example, always picks the shortest route and does not model charging delays (which may occur when using current standard GPS routing systems in an EV), while LOGIT(100,TRUE) uses historical arrivals to estimate queueing times, but sometimes randomly deviates from the optimal path.

4.2 Experimental Setup

Throughout our experiments, we assume that charging takes 30 minutes, which is realistic for current state-of-the-art charging stations (modelling 10 minutes as one time step). We also run each setting for 20 simulated days, in order to allow agents to learn and respond to the behaviour of others. 3 Whenever agents use Monte Carlo simulation to estimate arrival probabilities, we take 100 samples, which leads to good results in practice. We also repeat all experiments 1,000 times and report 95% confidence intervals.

We examine two separate scenarios in this section, in order to verify that similar trends hold in different graph topologies and problem sizes. Both scenarios are shown in Figure 1. Here, EVs leave from vertices labelled 'S' (source) and wish to travel to vertices labelled 'D' (destination), which are chosen uniformly at random between the alternatives in the second scenario. Charging stations are indicated by looping edges, with their charging capacities given by the label on the adjacent vertex. We set charging costs appropriately to ensure that all EVs must charge at least once, and, as we are interested in how the systems cope with congestion at peak times, we assume all vehicles leave at time t = 1 (we obtained similar results when vehicles leave gradually).

More specifically, the first of these scenarios, the bottleneck setting, focuses only on the decision of which charging stations to route to and assumes that all agents share the same source and destination. Here, non-station edges have probabilistic travel times, which we generate by drawing five samples from the set {1, 2, . . . , 12} (with replacement). Then we attach a value drawn uniformly at random from [0, 1] to each unique sample and normalise these to sum to 1, in order to obtain a probability mass function. 4 This is a realistic setting for the case where several potential routes exist to a popular destination, e.g., different roads between two large cities or from a commuter town to the commercial centre of a city. It represents an extreme setting, as agents need to commit to a station on departure, some of which will clearly be more desirable than others in the absence of congestion and may therefore become bottlenecks. Here, we simulate 20 EVs.

3 This is a conservative choice - in practice, the results typically do not change significantly after the first five days.

The second scenario, the grid setting, represents a case where agents have diverse sources and destinations and can potentially change their policy based on new information before reaching a station (if using IARS). Thus, it models a realistic road network, e.g., between several cities or other points of interest. Here, the travel time distribution on each road edge is generated by drawing two samples from {1, 2, . . . , 4}. We simulate 50 EVs, representing a larger, more complex setting. 5 Note the average travel time from a source to a random charging station (and again to the destination) is between 65 minutes for bottleneck, and 75 minutes for grid. This is reasonable, given the current range of EVs.

4.3 Results for Overall Performance

In our first set of experiments, we compare the performance of all systems in the two settings, as shown in Figure 2. As we show in Section 4.4, λ = 10 and λ = 100 perform well in these settings, respectively, and so we only show their performance here. For the bottleneck setting we also plot a centrally computed optimal solution. As a globally optimal algorithm is computationally not feasible in the grid setting (due to the large number of vehicles and possible paths), we give a lower bound on the journey time here, which is based on a simpler graph that combines all charging stations into a single one with an appropriately higher capacity. This is a very optimistic lower bound, because it allows a simple optimal strategy, where vehicles ignore congestion and choose the path with the shortest expected travel time.

4 For ease of presentation and because we focus on charging stations in this paper, these are not time-dependent.

5 We stress that significantly larger settings are similarly feasible. To illustrate this, simulating 1,000 EVs with IARS arriving over the course of a day in the grid setting takes just over two minutes. We choose 50 EVs here for practical reasons, to allow us to explore a large parameter space and collect statistically significant data. The general trends are the same as in larger settings.

Several interesting trends emerge here. First, in the bottleneck setting, both MIN approaches perform badly, leading to an average journey time of around 386 and 399 minutes (for MIN(FALSE) and MIN(TRUE), respectively). This is more than twice the optimal with 186 minutes. The reason for this is that the MIN approaches always choose the one route that minimises their travel time (in expectation), but as all agents act on the same information, they pick the same path, leading to a single extremely congested station. This is evidenced by the high proportion of time spent queueing rather than travelling. Surprisingly, performance decreases even further when an explicit model of waiting times is used by the MIN approach. This is because the agents learn that the first station was highly congested, but then move in tandem to the next best option, resulting in the same queues, but longer travel times. Clearly, this highlights the perils of using a simple travel time minimisation approach in settings where agents have similar requirements.

The remaining approaches in the bottleneck setting all perform surprisingly well. Our proposed IARS system achieves the same performance as the globally optimal benchmark, while even the simpler randomised LOGIT approaches lead to an average journey time of 192 minutes.

The trends in the grid setting are slightly different. Here, MIN(FALSE) without queueing model still achieves an overall bad performance with an average journey time of 329 minutes (a 101% increase over the optimal bound of 163 minutes), most of which is spent queueing again. However, this is significantly improved by including an explicit model of station waiting times using historical arrivals (223 minutes, 38% increase), because it allows the agent to reason about queues (which are more heterogeneous in this setting due to the variable sources and destinations). Also, adding randomisation (242 minutes, 48% increase over the bound) is beneficial in this setting, because it avoids congestion at otherwise more desirable stations. Combining both, the LOGIT(100,TRUE) achieves an average travel time of 195 minutes (20% increase). Finally, the IARS achieves an even higher performance, with an average journey time of 184 minutes (13% more than the optimal bound).

4.4 Results for LOGIT(λ)

So far, LOGIT(λ) appears to be a promising alternative to IARS. To examine this in more detail, we show the performance of LOGIT(λ,TRUE) for a range of λ parameters in Figure 3. These results show that LOGIT is somewhat sensitive to the choice of λ, which raises the question of how λ should be chosen in real-life settings.

More significantly, however, the figure also shows the average journey time a single deviating agent would achieve by switching to the MIN(TRUE) approach (assuming all other agents use LOGIT). This is never higher than LOGIT and, in fact, typically lower. In other words, while randomisation benefits the overall system, as it disperses agents across the stations, a single agent always has an incentive to deviate and head for the station with the lowest expected journey time. Thus, LOGIT is not a viable alternative in realistic systems.

4.5 Results for IARS

To further explore our proposed IARS system, we now consider settings where only a proportion of agents use IARS, while the others use MIN(TRUE) or LOGIT(100,TRUE). This is an interesting setting, because it shows how the system performance changes as intentions are gradually introduced into a system (and indeed whether it is beneficial if only a few agents use IARS). Similar to the previous section, it also investigates whether agents have an incentive to switch to (or from) IARS. In this setting, we measure the average journey time for each type of agent, but we also measure the systemwide average across the population (i.e., the social welfare).

The results are given in Figure 4 (we show only the grid settings, as the results in the bottleneck setting are similar). Here, several clear trends emerge: as more agents use IARS, the system-wide average journey time decreases. Furthermore, agents that use IARS always have lower average journey times than those that do not, indicating that there is a strong incentive to use IARS for all system participants. Apart from this, the graphs show two further interesting trends. First, even when only a few agents use intentions, their average journey time already dramatically decreases as they can coordinate their decisions. In fact, when others use LOGIT, the IARS agents achieve their minimum journey time when only a small proportion use the system. This is similar to the results in Figure 3, where agents can exploit inefficiencies in the strategies of other agents. The second interesting trend is that agents using MIN benefit themselves when more agents switch to IARS, but this trend is not evident for agents using LOGIT. This is simply because the typically high congestion at desirable stations caused by MIN is gradually reduced as fewer agents adopt this approach.

5 Conclusions and FutureWork

This work extends both models and algorithms for stochastic time-dependent routing to take charging stations and the state of charge of EVs into account. Another main contribution is a novel approach where we combine (stochastic) intentions of other agents with historical data to obtain more accurate waiting time distributions. In order to do so, we explicitly model queues at charging stations. As part of our evaluation we defined an optimistic bound, as well as an alternative routing system based on logit that does not use intentions, but helps to prevent congestion at charging stations by randomising over options. Through extensive experiments, we established that both an explicit queueing model as well as randomisation increases social welfare, but that IARS outperforms even a combination of these systems. Moreover, agents using the randomised system have an incentive to switch to a deterministic strategy, while we showed that individual agents always achieve lower journey times with IARS.

The IARS does not require any monetary transfers. However, an interesting direction for further study is to view coordinating the en-route charging of EVs under uncertainty as a mechanism design problem. In particular, we are interested in combining our work with pricing models to be able to find more efficient solutions, such as used for charging at home [Stein et al., 2012; Clement-Nyns et al., 2010; Vasirani and Ossowski, 2011].

To transition our solution into a practical application, we additionally plan to extend our work with simulations with real data to obtain better insights into the quantitative advantages of deploying IARS, and it would be useful to develop heuristics for both policy computation as well as combining the distributions to improve run time and scalability.