I-dual: Solving Constrained SSPs via Heuristic Search in the Dual Space

1 Introduction

Stochastic Shortest Paths problems (SSPs) are widely used models for planning under uncertainty. Given an initial state, a set of goal states, actions with probabilistic outcomes, and an action cost function, the objective is to find a policy that minimises the expected cost of reaching the goal from the initial state. For SSPs, the optimal policies are deterministic mappings from states to actions and can be efficiently computed using heuristic search algorithms [Mausam and Kolobov, 2012]. These algorithms focus the search on promising regions of the state space by using the guidance of an admissible heuristic. This focused search sets these algorithms apart from linear programming formulations and dynamic programming algorithms, such as Value and Policy Iteration, which explore the entire state space.

In many application domains, SSPs have limited value, as multiple competing performance criteria need to be considered and are difficult to encapsulate in a single scalar cost function [Undurti and How, 2010]. For example, in a UAV

Pedro Santana BrianWilliams MERS Group Massachusetts Institute of Technology

{psantana,williams}@mit.edu

search and rescue mission, as many targets as possible need to be found as fast as possible, whilst minimising battery usage and the probability of reaching dangerous areas. A natural approach to deal with such situations is to optimise a primary cost function, and constrain the others [Altman, 1999]. This leads to constrained SSPs which augment SSPs with upper bounds on the expected value of the secondary costs.

In this paper, we present i-dual, the first heuristic algorithm for constrained SSPs. Similarly to unconstrained planning algorithms, i-dual incrementally builds the search space reachable from the initial state by repeatedly expanding the fringe states reachable under the current best policy, and updating that policy using linear programming. By using the dual LP formulation [D'Epenoux, 1963], i-dual can easily represent the secondary cost constraints and ensures that the resulting policy satisfies them. Our empirical evaluation shows that i-dual successfully leverages the heuristics over the primary and secondary cost functions to prune suboptimal and infeasible solutions, and is able to solve problems up to two orders of magnitude larger than the regular dual LP approach. Moreover, we show how non-admissible heuristics can be used by i-dual to trade-off optimality with scalability and quickly compute policies that still respect the constraints, an option not offered by the dual LP approach.

The paper is organised as follows: Section 2 presents the background on SSPs and constrained SSPs; i-dual, our novel algorithm, is introduced in Section 3; the empirical evaluation of i-dual is presented in Section 4; and we conclude in Section 5. Further details can be found in [Trevizan et al., 2016].

2 Background

A Stochastic Shortest Path problem (SSP) [Bertsekas and Tsitsiklis, 1991] is a tuple 〈S, s0, G, A, P,C〉 in which: S is the set of states; s0 is the initial state; G ⊆ S is the set of goal states; A is the set of actions; P(s′ |s, a) is the probability that s′ is reached after applying action a in state s; and C(s, a) ∈ R∗+ is the cost of applying action a in state s. We represent by A(s) the actions applicable in state s and we assume that a goal state is reachable from every state s.

A solution to an SSP is a policy π, i.e., a mapping from states to actions. If a policy π can be executed from s0 to a goal state for any probabilistic outcome of the actions (i.e., no replanning is needed) then π is a closed policy. A policy can also be deterministic or stochastic. The former maps a state s to one action a ∈ A(s) and the latter maps a state s to a probability distribution over A(s). We denote by π(s, a) the probability of executing a in s.

The optimal solution for an SSP is a closed policy π∗ that minimises the total expected cost of reaching the goal from s0. For SSPs, π∗ might not be unique and there always exists at least one optimal policy that is deterministic. The optimal solution of an SSP can be uniquely described by the optimal value function V ∗ , i.e., a function from S to R+ representing the minimum total expected cost to reach the goal from each state s [Bertsekas and Tsitsiklis, 1996]. V ∗ can be computed iteratively, using linear programming, and through heuristic search [Mausam and Kolobov, 2012]. We refer to these algorithms that explicitly compute V ∗ as primal-space algorithms. An admissible heuristic H for primal-space algorithms is any lower bound on V ∗ .

An alternative to primal-space algorithms is to solve the linear program over the dual space [D'Epenoux, 1963] presented in (LP 1) in which: the optimisation variables xs,a, known as occupation measure, represent the expected number of times action a ∈ A(s) is executed in s; in(s) = ∑s′∈S,a∈A(s′ ) xs′ ,aP (s|s′ , a); and out(s) = ∑a∈A(s) xs,a.

This dual formulation can be interpreted as a flow problem, where: in(s) and out(s) define the expected flow entering and leaving the state s, respectively; (C2) is the flow conservation principle; and (C3) and (C4) define, respectively, the source (s0) and the sinks (goal states). The objective function of (LP 1) captures the minimisation of the total expected cost to reach the goal from s0. Once we have the solution x∗ of (LP 1), the optimal policy is π∗ (s, a) = x∗s,a /out(s) and is guaranteed to be deterministic, i.e., x∗s,a > 0 for exactly one action a ∈ A(s) for all s such that out(s) > 0.

A constrained SSP (C-SSP) is an SSP with k+1 cost functions in which one cost function is optimised while the remaining k costs are constrained by an upper bound. Formally, a C-SSP is the tuple 〈S, s0, G, A, P, ⃗C,⃗ˆ c〉 where S, s0, G, A, and P are defined as in the SSPs and ⃗C = [C0, . . . , Ck] is the cost functions vector and ⃗ˆ c = [ˆ c1, . . . , ˆ ck] is the cost upper bound vector (ˆ cj > 0, ∀j). We refer to C0 as primary cost and all other cost functions as secondary costs.

The constraints on costs Cj , for j ∈ {1, . . . , k}, are on expectation, i.e., given a policy π, the expected value of Cj over all executions of π from s0 to the goal must be less or equal to ˆ cj . Even though an upper bound on the maximum incurred cost (as opposed to its expectation) might be desired, such bounds make most SSPs infeasible because they require that none of the possible executions of π violate the constraints.

The optimal solution to a C-SSP is defined as the solution of (LP 1) subject to the additional constraint C5 and replacing C by the primary cost function C0 in the objective function.

In contrast to SSPs, there is no guarantee that the optimal policy for C-SSPs is deterministic. Nevertheless, the complexity of finding the (potentially stochastic) optimal policy for CSSPs is polynomial in the number of reachable states as in the case of SSPs [Altman, 1999].

The occupation measure space is interesting for C-SSPs because, the total expected j-th cost of following x from s0 to a goal can be easily computed by ∑s,a xs,aCj(s, a). In contrast, primal-space algorithms have to represent and compute the fixed-point solution for each value function Vj associated with Cj (j ∈ {0, . . . , k}). Moreover, the set of costs computed need to be those for a single policy, and imposing this constraint in the primal-space is non-trivial.

Although the dual approach is tractable, a significant computational cost required is that all the reachable states from s0 must be encoded in the LP, even if only a fraction of them are needed to compute π∗ . Furthermore, deriving a non-zero lower bound for the occupation measure x is not trivial because xs,a > 0 if and only if π∗ (s, a) > 0 for at least one optimal policy π∗ . In fact, the authors are not aware of any domain-independent bounds for xs,a.

3 i-dual

To overcome the lack of lower bounds for xs,a, we use a heuristic vector over costs ⃗H = [H0, . . . ,Hk], where Hj : S → R+ for all j ∈ {0, . . . , k} is a heuristic for the expected value of Cj (i.e, a primal-space heuristic). A heuristic Hj is admissible for Cj if it is a lower bound for the j-th total expected cost and it can be easily derived by relaxing the C-SSP into an unconstrained SSP as a range of heuristics exist for SSPs [Mausam and Kolobov, 2012]. Formally, given a C-SSP 〈S, s0, G, A, P, ⃗C,⃗ˆ c〉 and j ∈ {0, . . . , k}, let Sj be the SSP 〈S, s0, G, A, P,Cj〉, then the optimal value function V ∗ for Sj is an admissible heuristic for Cj. Therefore, any admissible heuristic H for Sj is also admissible for Cj .

Our novel approach consists in defining incrementally larger partial problems starting from s0, using artificial goals to represent non-explored areas of the occupation measure space. Artificial goals are prioritised using their heuristic values, incurred as a one-time terminal cost when the artificial goal state is first reached. Each partial problem is thus represented as a C-SSP with terminal costs 〈ˆS, s0, ˆG, ˆA, P, ⃗C,⃗ˆ c, ⃗H〉, where: 〈ˆS, s0, ˆG, ˆA, P, ⃗C,⃗ˆ c〉 is a regular C-SSP, ˆS ⊆ S, G ∩ ˆS ⊆ ˆG, ˆA ⊆ A, and ⃗H is the heuristic vector. The dual linear program for C-SSPs with such terminal costs is presented in LP 2.

I-dual is depicted in Algorithm 1 and the key elements that vary from one iteration of the algorithm to the next are: the set ˆS of states considered so far; the set F ⊆ ˆS of fringe states (i.e., the unexpanded states in ˆS); the fringe states FR ⊆ F reachable from s0 by following the policy encoded by x; and the set ˆG of artificial goals for the current partial problem. At each iteration, i-dual computes the set N of all the new states reachable from FR by applying one action (line 5), and updates the set of states, the fringe, and the artificial goals accordingly (lines 6-8). When FR is empty, a closed policy has been found, that is, all of the flow injected into the system on s0 is absorbed by goals of the original problem.

Since i-dual always enforces the cost constraints (C6), the returned policy π (if any) is always feasible regardless of the heuristic vector used and its admissibility. Moreover, if all the heuristics in ⃗H are admissible, then π is optimal:

Theorem 1 ([Trevizan et al., 2016]). Given a C-SSP C = 〈S, s0, G, A, P, ⃗C,⃗ˆ c〉 and a vector of admissible heuristics ⃗H, the policy π returned by i-dual is an optimal policy for C.

Similarly to primal-space heuristic search algorithms for SSPs, i-dual is complete but suboptimal when the heuristics H1, . . . ,Hk for the secondary costs are admissible but the heuristic H0 for the primary cost is not. When any secondary heuristic is not admissible, i-dual is incomplete: it might not find a solution even if one exists because the non-admissible heuristic can incorrectly indicate that a feasible solution violates the constraints.

I-dual can be viewed through two different prisms: as a heuristic search algorithm and as a column and row generation algorithm. In the former, an Artificial Intelligence point of view, i-dual is analogous to A* where the cost g(n) to reach an artificial goal (fringe) n from s0 is computed using LP 2. The LP handles the search in the cyclic space of occupation measures to find a solution that minimises the expected value of g(n) +H0(s). As in A*, the selected fringe states (FR in Algorithm 1) are expanded and the search continues until a solution is found.

Alternatively, from an Operations Research point of view, i-dual is a column and row generation algorithm. That is, at each iteration, new variables xs,a are added (columns) as well as new flow conservation constraints (rows) for the newly expanded states, and their corresponding occupation measures. The heuristics ⃗H prioritise the candidate columns and the solution of LP 2 indicates what columns should be added, namely, xs,a for all s ∈ FR and a ∈ A(s). Columns are added in batch because, if a is applied in s, then all states s′ s.t. P(s′ |s, a) > 0 need to be considered in order to obtain a closed policy.

The column and row generation point of view is not only theoretically relevant, it also increases the performance of i-dual. The overhead of building the LPs in line 12 (Algorithm 1) is minimised by keeping only one LP in memory and adding columns and rows to it. More importantly, this approach can take advantage of "warm starts", i.e., to solve the new LP by reusing the solution of the previous one.

4 Empirical Evaluation

We empirically evaluated i-dual and the dual LP (LP 1 with the additional constraint C5) in three different domains:

Search and rescue: an n × n grid navigation problem where the goal is to find one survivor, board her on the vehicle and bring her to a safe location as fast as possible. The constraint is to keep the expected fuel consumption under a certain threshold. The location of one survivor is known a priori; however, some other locations (selected at random) have 0.05, 0.1, or 0.2 probability of also having a survivor. Thus, the planner has to trade off fuel, exploration of unknown survivors, and time to rescue. The parameters for the SAR problem generator is n, the distance to the known survivor (d), and the density of potential survivors (r).

Elevators: a 20-storey building with e elevators in which w persons are known to be waiting for an elevator and h persons are expected to arrive and request an elevator. Each "hidden" person arrives at the elevator in the next time step with probability 0.75. The origin and destination of all persons are known a priori. In this domain, the planner has to minimize the number of elevators movements (actions) while satisfying the maximum waiting and travelling time of each person; and Exploding blocks world: an extension of the domain with same name from IPPC [Bryce and Buffet, 2008] in which the expected number of blocks explosion is constrained through an upper bound. This extension does not have unavoidable dead ends due to the introduction of the action fix-table that restores the table to its original condition in case a block destroyed it. For these problems, the primary objective is to minimise the action costs. The problem instances are those of the IPPC augmented with the constraint and the fix-table action.

The heuristic vector ⃗H used by i-dual is denoted as (X, Y ) representing [X, Y, Y, . . . , Y ] where the heuristics for Cj is computed over the all-outcomes determinisation of the SSP with Cj as cost function (Section 3). We consider the following domain-independent heuristics: always zero (h0), maximal (hmax), additive (hadd), and lm-cut (hlmc). The complete empirical evaluation, description of the domains and methodology can be found in [Trevizan et al., 2016].

Table 1 shows the average cpu-time, number of states explored and percentage of the cpu-time spent encoding LP 2, computing the vector of heuristics ⃗H, and solving LP 2 for selected problems of each domain. For SAR and elevators, each problem number (second column) represents a different parametrization of the generator and the planners were evaluated by solving 30 randomly generated problems for each parametrization. For the augmented exploding blocks world, each entry represents the problem number in IPPC'08 and planners were evaluated by solving each problem 30 times using different random seeds. Only planners that obtained 100% coverage (i.e., found a closed policy from s0 for all the 30 runs in each entry) are shown in Table 1.

For SAR, the dual LP fails to scale up and is unable to solve even trivial problems (e.g., for n = 4, d = 1 and r = 0.75) due to the large reachable state space that needs to be explicitly constructed even if only a small fraction of it is needed to compute the optimal policy. As shown in Table 1, i-dual is able to explore at least one order of magnitude less states than the dual LP, allowing it to scale up to larger problems. For the elevator problems, the dual LP dominates all i-dual parametrisations when the reachable state space is small because, in this case, it is feasible to encode the complete dual LP. The admissible parametrisations of i-dual were also dominated by the dual LP in the medium size instances because of the large number of cost constraints (1 + 2(w + h) constraints) and thus the dimension of ⃗H (see column 7 of Table 1). hmax and hlmc also provided weak guidance for this domain not paying off the overhead to compute them. In contrast, the nonadmissible hadd was able to offer good guidance and allowed i-dual to solve problems overcoming the overhead of the large number of heuristic calls per state. For the exploding blocks world, the dual LP is unable to solve problems with more than 5 blocks while i-dual is able to solve problems with up to 8 blocks. Furthermore, i-dual is two orders of magnitude faster than the dual LP for the problems that the latter can solve. As shown in Table 1, i-dual obtains this performance by using the heuristics to prune a large portion of the state space.

5 Conclusion, Related and FutureWork

I-dual combines heuristic search and the dual LP formulation of SSPs to optimally solve constrained SSPs resulting, to the best of our knowledge, in the first heuristic search algorithm for constrained SSPs (C-SSPs). I-dual is able to efficiently encode and enforce secondary cost constraints, and to focus the search on regions that are relevant to the optimal stochastic policy, using (admissible) value function heuristics. This results in up to two orders of magnitude improvements in run-time and memory when compared to C-SSP algorithms based on linear programming alone. Furthermore, i-dual is able to trade-off optimality with scalability and quickly compute policies that still respect the constraints, an option not offered by the primal linear programming approach.

In terms of related work, Altman (1999) was one of the first to research linear and dynamic programming algorithms for a range of constrained Markov Decision Processes. Dolgov and Durfee (2005) extend the work of Altman to the generation of deterministic policies for constrained MDPs. None of these algorithms are capable of using a heuristic to guide their search. Santana, Thi´ebaux, Williams (2016) propose RAO*, an extension of AO* for finite-horizon POMDPs with chance constraints (i.e., bounds on the probability of a constraint being violated) that uses heuristics to guide its search in the primal space. Note that, chance constraints can be encoded as constraints over expectation if we assume that their their violation cause policy termination. Trevizan and Veloso (2012) introduce an algorithm for unconstrained SSPs that shares with i-dual the usage of subproblems with artificial goals but performs search in the primal space. Our future work agenda includes combining both algorithms to obtain a version of i-dual for planning and execution that could offer guarantees regarding constraint violation during execution.

Lastly, Teichteil, Sprauel, and Kolobov (2012, 2014) consider the generation of optimal stochastic policies for discounted MDPs with path constraints expressed in probabilistic computational tree logic (pCTL). They describe iterative linear and dynamic programming algorithms that improve on algorithms used in the probabilistic model-checking community [Kwiatkowska and Parker, 2013, Baier et al., 2004]. Having an efficient algorithm for C-SSPs which could be used or extended to deal with path constraints in probabilistic temporal logic is one of the motivation that lead to i-dual, and this extension is an item on our future work agenda.

Acknowledgements

This research was funded by AFOSR grant FA2386-15-14015. We thank Patrik Haslum for fruitful discussions and the anonymous reviewers for their helpful comments.