Reduced models of large Markov decision processes accelerate planning by considering a subset of outcomes for each state-action pair. This reduction in reachable states leads to replanning when the agent encounters states without a precomputed action during plan execution. However, not all states are suitable for replanning. In the worst case, the agent may not be able to reach the goal from the newly encountered state. Agents should be better prepared to handle such risky situations and avoid replanning in risky states. Hence, we consider replanning in states that are unsafe for deliberation as a negative side effect of planning with reduced models. While the negative side effects can be minimized by always using the full model, this defeats the purpose of using reduced models. The challenge is to plan with reduced models, but somehow account for the possibility of encountering risky situations. An agent should thus only replan in states that the user has approved as safe for replanning. To that end, we propose planning using a portfolio of reduced models, a planning paradigm that minimizes the negative side effects of planning using reduced models by alternating between different outcome selection approaches. We empirically demonstrate the effectiveness of our approach on three domains: an electric vehicle charging domain using real-world data from a university campus and two benchmark planning problems.
A Stochastic Shortest Path (SSP) problem is a Markov
Decision Process (MDP) with a start state and goal state(s),
where the objective is to find a policy that minimizes the
expected cost of reaching a goal state from the start state
Due to model simplification, an agent may encounter unexpected states during plan execution, for which the policy computed using reduced models may not specify an action.
In such instances, the agent needs to replan online and find
a new way to reach a goal state. We consider this as a side
effect of using reduced models as the agent never has to
replan when the complete model is used. Current reduced
model techniques assume that the agent can replan in any
state
Consider, for example, a robot navigating on a sidewalk
adjacent to a street. The robot has a 0:1 probability of
sliding on to the street when navigating at high speed and 0:02
probability of sliding to the street when navigating at a low
speed. When planning with a reduced model that ignores the
possibility of sliding as an outcome, the robot will have to
replan if the ignored outcome occurs during plan execution.
However, it is risky for the robot to replan while on the street
and it is expected to be better prepared to handle such
situations. Another example of replanning in risky states is an
autonomous vehicle replanning in the middle of an
intersection after missing a turn or an exit. In the terminology
introduced by
The importance of accounting for risks in AI systems is
attracting growing interest
We propose planning using a portfolio of outcome selection principles to minimize the negative side effects of planning with reduced models. The model fidelity is improved in states that are risky — unsafe for deliberation or replanning. We consider a factored state representation in which the states are represented as a vector of features. Given a set of features that characterize states unsafe for deliberation, our approach employs more informative outcomes or the full model for actions in states leading to these side effects and a simple outcome selection otherwise. To identify states where model fidelity is to be improved, the agent performs reachability analysis using samples and the given features. The sample trajectories are generated by depth-limited random walk. Reachability analysis is performed primarily with respect to negative side effects and this is used as a heuristic for choosing the outcome selection principles in a portfolio. We evaluate our approach in three proof-of-concept domains: an electric vehicle charging problem using real-world data, a racetrack domain and a sailing domain. Our empirical results show that our approach significantly minimizes the negative side effects, without affecting the run time. While we address one particular form of negative side effects in planning using reduced models, our proposed framework is generic and can be extended to potentially address other forms of negative side effects.
Our primary contributions are: (i) formalizing negative side effects in planning using reduced models; (ii) introducing a portfolio of reduced models approach to minimize the negative side effects; and (iii) empirical evaluation of the proposed approach on three domains.
This section provides a brief background on stochastic shortest path problems and planning using reduced models.
C : S A ! R+ [ f0g specifies the cost of executing an action a in state s and is denoted by C(s; a); s0 2 S is the start state; and SG
The cost of an action is positive in all states except goal states, where it is zero. The objective in an SSP is to minimize the expected cost of reaching a goal state from the start state. It is assumed that there exists at least one proper policy, one that reaches a goal state from any state s with probability 1. The optimal policy, , can be extracted using the value function defined over the states, V (s): V (s) = min a
Q (s; a);
8s 2 S
Q (s; a) = C(s; a)+X T (s; a; s0)V (s0); 8(s; a)
(1)
(2)
s0
where Q (s; a) denotes the optimal Q-value of the action a
in state s in the SSP M
While SSPs can be solved in polynomial time in the
number of states, many problems of interest have a state-space
whose size is exponential in the number of variables
describing the problem
Definition 1. A reduced model of an SSP M is represented by the tuple M 0 = hS; A; T 0; C; s0; SGi and characterized by an altered transition function T 0 such that 8(s; a) 2 S A; 0(s; a) (s; a), where 0(s; a) = fs0jT 0(s; a; s0) > 0g denotes the set of outcomes in the reduced model for action a 2 A in state s 2 S.
We normalize the probabilities of the outcomes included in the reduced model, but more complex ways to redistribute the probabilities of ignored outcomes may be considered. The outcome selection process in a reduced model framework determines the number of outcomes and how the specific outcomes are selected. Depending on these two aspects, a spectrum of reductions exist with varying levels of probabilistic complexity.
The outcome selection principle (OSP) determines the outcomes included in the reduced model per state-action pair, and the altered transition function for each state-action pair. The outcome selection may be performed using a simple function such as always choosing the most-likely outcome or a more complex function. Typically, a reduced model is characterized by a single OSP. That is, a single principle is used to determine the number of outcomes and how the outcomes are selected across the entire model. Hence, existing reduced models are incapable of selectively improving model fidelity.
One form of negative side effects of planning using reduced models is replanning in states, as a result of ignoring outcomes, which are prescribed by a human as unsafe for deliberation. The set of states characterizing negative side effects for planning with a reduced model M 0, denoted by N SE(M 0), is defined as N SE(M 0) = fs0jT (s; a; s0) > 0 ^ D(s0) = true ^ s0 2= 0(s; a)g, where D(s0) is true if the deliberation in the state is risky during policy execution. Thus, the OSP determines the reduced model and thereby the resulting negative side effects. The challenge is to determine outcome selection principles that minimize the negative side effects of planning with reduced models without significantly compromising the run time gains.
While the negative side effects can always be minimized
using the full model or picking the right determinization,
the former is computationally complex and finding the right
determinization is a non-trivial meta-level decision
problem
We present planning using a portfolio of reduced models
(PRM), a generalized approach to formulate reduced
models, by switching between different outcome selection
principles, each of which represents a different reduced model.
The approach is inspired by the benefits of using
portfolios of algorithms to solve complex computational
problems
Definition 2. Given a portfolio of finite outcome selection principles, Z = f 1; 2; :::; kg, k>1, a model selector, , generates T 0 for a reduced model by mapping every (s; a) to an outcome selection principle, : S A ! i, i 2 Z, such that T 0(s; a; s0) = T (s;a)(s; a; s0), where T (s;a)(s; a; s0) denotes the transition probability corresponding to the outcome selection principle selected by the model selector.
Clearly, the existing reduced models are a special case of PRMs, with a model selector ( ) that always selects the same OSP for every state-action pair. In planning using a portfolio of reduced models, however, the model selector typically utilizes the synergy of multiple outcome selection principles. Each state-action pair may have a different number of outcomes and a different mechanism to select the specific outcomes. Hence, we leverage this flexibility in outcome selection to minimize negative side effects in reduced models by using more informative outcomes in the risky states and using simple outcome selection principles otherwise. Though the model selector may use multiple outcome selection principles to generate T 0 in a PRM, note that the resulting model is still an SSP. In the rest of the paper, we focus on a basic instantiation of a PRM that alternates between the extremes of reductions.
Definition 3. A 0/1 reduced model (0/1 RM) is a PRM with a model selector that selects either one or all outcomes of an action in a state to be included in the reduced model.
A 0/1 RM is characterized by a model selector, 0/1, that either ignores the stochasticity completely (0) by considering only one outcome of (s; a), or fully accounts for the stochasticity (1) by considering all outcomes of the stateaction pair in the reduced model. For example, it may use the full model in states prone to negative side effects, and determinization otherwise. Thus, a 0/1 RM that guarantees goal reachability with probability 1 can be devised, if a proper policy exists in the SSP. Our experiments using 0/1 RM show that even such basic instantiation of a PRM works well in practice.
Devising an efficient model selector automatically can be treated as a meta-level decision problem that is computationally more complex than solving the reduced model, due to the numerous possible combinations of outcome selection principles. Even in a 0/1 RM, finding when to use determinization and when to use the full model is non-trivial. In the more general setting, all OSPs in Z may have to be evaluated to determine the best reduced model formulation in the worst case. Let max denote the maximum time taken for this evaluation across all states. In a PRM with a large portfolio, the OSPs may be redundant in terms of specific outcomes. For example, selecting the most-likely outcome and greedily selecting an outcome based on heuristic could result in the same outcome for some (s; a) pair. We use this property to show that the worst case time complexity of devising an efficient model selector is independent of the size of the portfolio, which may be much larger than the size of the problem under consideration, and depends only the size (a) Orignal Problem (b) MLOD (c) 0/1 RM of states and actions. The following proposition formally proves this complexity.
Proposition 1. The worst case time complexity for generate T 0 for a 0/1 RM is O(jAjjSj2 max): 0/1 to Proof Sketch. For each (s; a), at most jZj outcome selection principles are to be evaluated and this takes at most max time. Since this process is repeated for every (s; a), takes O(jSjjAjjZj max) to generate T 0. In the worst case, every action may transition to all states and the outcome selection principles in Z may be redundant in terms of the number and specific outcomes set produced by them. To formulate a 0=1 RM of an SSP, it may be necessary to evaluate every outcome selection principle that corresponds to a determinization or a full model. The set of unique outcomes, k, for a 0=1 RM is composed of all unique deterministic outcomes, which is every state in the SSP, and the full model, jkj jSj + 1. Replacing jZj with jkj, the complexity is reduced to O(jAjjSj2 max).
Since it is computationally complex to perform an exhaustive search in the space of possible 0/1 RM models, we present an approximation to identify when to use the full model, using samples.
Given the features characterizing negative side effects,
model selection is performed by generating and solving
samples. The samples are generated automatically by
sampling states from the target problem. Alternatively, small
problem instances in the target domain may be used as
samples. In this paper, smaller problems are created
automatically by multiple trials of depth limited random walk on the
target problems and solved using LAO*
Figure 2 is an example of an SSP with a risky state (shaded) and instantiations of reduced models formed with uniform and adaptive outcome selection principles. The most likely outcome determinization (MLOD) uses uniform outcome selection principle – always selects the most likely outcome – and may ignore s5 in the reduced model. A 0/1 RM, however, uses the full model in state action pair leading to the risky state, minimizing negative side effects and resulting in a model that is better prepared to handle the risky state. The reachability threshold can be varied to devise reduced models with different fidelity with varying proportions of full model usage, resulting in different sensitivity to negative side effects and computational complexity.
We experiment with the 0/1 RM on three proof-ofconcept domains including an electric vehicle charging problem using real world data from a university campus, and two benchmark planning problems: the racetrack domain and the sailing domain. The experiments employ a simple portfolio Z = fmost-likely outcome determinization (MLOD), full modelg. We compare the results of 0/1 RM to that of MLOD and M02 reduction, which greedily selects two outcomes per each state-action pair.
The expected number of negative side effects, cost of
reaching the goal, and planning time are used as
evaluation metrics. For 0/1 RM, we use the full model in states
that had a reachability of 0.25 or more to at least one of the
risky states, which is estimated using thirty samples. In all
other states, MLOD is used. All results are averaged over
100 trials of planning and execution simulations and the
average times include re-planning time. The deterministic
problems are solved using the A* algorithm
The electric vehicle (EV) charging domain considers an
EV operating in a vehicle-to-grid (V2G) setting in which
an EV can either charge or discharge energy from the
smart grid
We consider uncertainty in parking duration, which is specified by a probability that certain states may become terminal states. This problem is modeled as a discrete finitehorizon MDP with maximum parking duration as the horizon H . Each state is represented by the tuple hl; t; d; p; ei, where l denotes the current level of charge of the vehicle, t H denotes the current time step. d and p denote the current demand level and price distribution for electricity and 0 e 3 denotes the anticipated departure time specified by the owner. If the owner has not provided this information, then e = 3 and the agent plans for H . Otherwise, e denotes the time steps remaining for departure. The vehicle can charge ( i+) and discharge ( i ) at three different speed levels, where 1 i 3 denotes the speed level, or remain idle (?). The i+ and i actions are stochastic, while the ? action is deterministic. The objective is to find a reward maximizing policy : S ! A that maximizes goal reachability, given the charging preferences of the vehicle owner. If the exit level charge (goal) requirement of the owner is not met at departure, then the owner may need to extend the parking duration to reach the required charge level. Since this is undesirable, any state from where the goal cannot be reached in the remaining parking duration is treated as a preference violation (risk) in the MDP with a large penalty.
Four demand levels and two price distributions are used
in the experiments. Each t is equivalent to 30 minutes in real
time. We assume that the owner may depart between four
to six hours of parking with a probability of 0:2 that they
announce their planned departure time. Outside that
window, there is a lower probability of 0:05 that they announce
their departure. The charging rewards and the peak hours are
based on real data
EV Dataset The data used in our experiments consist of charging schedules of electric cars over a four month duration in 2017 from an American university campus. The data is clustered based on the entry and exit charges, and we selected 25 representative problem instances across clusters for our experiments. The data is from a typical charging station, where the EV is unplugged once the desired charge level is reached. Since we are considering an extended parking scenario as in a vehicle parked at work, we assume parking duration of up to eight hours in our experiments. Therefore, for each instance, we alter the parking duration.
We experimented with six problem instances from the
racetrack domain
Finally, we present results on six instances of the sailing
domain
Racetrack-Square-4 Racetrack-Square-5 Racetrack-Ring-3 Racetrack-Ring-5 Racetrack-Ring-6
Sailing-40(C) Sailing-80(C) Sailing-20(M) Sailing-40(M) Sailing-80(M) 7.16 6.60 8.24 12.09
0 10.73 16.30
0 11.58 3.33 in the direction of the wind. The negative side effects are estimated using one-step lookahead and based on state features such as: the difference between the action’s intended direction of movement and the wind’s direction, and if the successor is moving away from goal, estimated using the heuristic value.
Table 2 shows the average number of negative side effects (risky states encountered without an action to execute) of the three techniques in three domains. For the EV domain, the results are aggregated over 25 problem instances for each reward function. In our experiments, we observe that as the model fidelity is improved, the negative side effects are minimized. In all four reward functions cases of the EV, 0/1 RM has no negative side effects. Overall, 0/1 RM has the least negative side effects in all three proof-of-concept domains.
Table 3 shows the average increase in cost (%) (with respect to the optimal cost as lower bound) and the time savings (%) (with respect to solving the original problem). The least cost increase % indicate that the performance of the technique is closer to optimal. The higher time savings values indicate improved run time gains by using the model. The runtime of 0/1 RM is considerably faster than solving the original problem, while yielding almost optimal solutions. This shows that our approach does not significantly affect the run time gains so as to improve the solution quality and minimize negative side effects. Note that we solve 0/1 RM using an optimal algorithm, LAO*, to demonstrate the effectiveness of our framework by comparing the optimal solutions of the models. In practice, any SSP solver (optimal or not) may be used to improve run time gains. Over
Racetrack-Square-4 Racetrack-Square-5 Racetrack-Ring-4 Racetrack-Ring-5 Racetrack-Ring-6
Sailing-40(C) Sailing-80(C) Sailing-20(M) Sailing-40(M) Sailing-80(M) % Cost Increase % Time Savings % Cost Increase % Time Savings % Cost Increase % Time Savings all, 0/1 RM yields almost optimal results, in terms of cost and negative side effects.
Interest in using reduced models to accelerate planning
increased after the success of FF-Replan
Safety issues in SSPs have been studied mostly with
respect to unavoidable dead ends that affect the goal
reachability
The importance of addressing negative side effects in AI
systems is gaining growing interest.
Reduced models are a promising approach to quickly solve large SSPs. However, the existing techniques are oblivious to the risky outcomes in the original problem when formulating a reduced model. We propose planning using a portfolio of reduced models that provides flexibility in outcome selection to minimize the negative side effects while still accelerating planning. We also present a heuristic approach to determine the outcome selection principles. Our empirical results demonstrate the promise of this framework; 0/1 RM that is based on the proposed heuristic yields improves the solution quality, apart from minimizing the negative side effects. Our results also contribute to a better understanding of how disparate reduce model techniques help improve the solution quality, while minimizing the negative side effects.
This paper focuses on addressing one specific form of negative side effect in planning that occurs when using reduced models. There are a number of interesting future research directions in this area. First, we are looking into ways to automatically identify risks in the system. One approach is to generate samples for learning risks using machine learning techniques such as regression and decision stump. Another approach is to employ limited user data in the form of human demonstrations to learn the feature and states that are risky for replanning. Second, we aim to build a classifier to distinguish side effects from negative side effects, which is a critical component for automatically identifying the risks. Finally, the 0=1 RM represents an initial exploration of a broad spectrum of PRMs, which we will continue to explore and further analyze outcome selection methods for PRMs with varying levels of probabilistic complexity.
Support for this work was provided in part by the U.S. National Science Foundation grants IIS-1524797 and IIS-IIS1724101.