Intention-Aware Routing to Minimise Delays at Electric Vehicle Charging Stations

1 Introduction

Decentralized partially observable Markov decision processes (Dec-POMDPs) have been studied as a general model for decision making under uncertainty in cooperative multiagent systems [Bernstein et al., 2002; Szer et al., 2005; Boularias and Chaib-draa, 2008; Amato et al., 2009; Bernstein et al., 2009; Aras and Dutech, 2010; Dibangoye et al., 2011; Spaan et al., 2011; Oliehoek et al., 2013]. While a number of algorithms have been developed, current optimal algorithms cannot scale beyond small benchmark problems. This is not unexpected given the worst-case NEXP complexity [Bernstein et al., 2002], but many real-world problems have structure that should allow greater scalability.

Current optimal algorithms for general Dec-POMDPs search through the space of solutions (or policies) which map histories of actions that have been taken and observations that have been seen to actions [Hansen et al., 2004; Szer et al., 2005; Boularias and Chaib-draa, 2008; Amato et al., 2009; Spaan et al., 2011; Oliehoek et al., 2013]. These approaches

Olivier Buffet and Franc¸ois Charpillet Inria / Universit´e de Lorraine Nancy, France ¶firstname.lastname♦@inria.fr

typically proceed by iteratively growing these policies from either the first step (using heuristic search) [Szer et al., 2005; Spaan et al., 2011; Oliehoek et al., 2013] or the last step (using dynamic programming) [Hansen et al., 2004; Boularias and Chaib-draa, 2008; Amato et al., 2009] until policies for the full problem horizon are constructed. As the horizon increases, the doubly exponential growth in the number of possible policies causes solution methods to quickly become intractable. Methods for increasing scalability by compressing policies [Boularias and Chaib-draa, 2008] and histories [Oliehoek et al., 2009] have begun to be explored, but scalability remains limited for many problems.

In contrast, significant progress has been made in the size of problems solved as fully and partially observable Markov decision processes (MDPs and POMDPs). One reason for progress in MDPs has been the use of approximate dynamic programming and function approximation [Powell, 2007; De Farias and Van Roy, 2003] to represent the state of the system (and value function) more concisely. For POMDPs, efficient algorithms have been developed by recasting problems as belief MDPs that utilize probability distributions over states of the system, namely belief states [Smallwood and Sondik, 1973]. This belief MDP is a continuous-state MDP with a piecewise linear convex value function, allowing algorithms for POMDPs to scale to large problems while sometimes retaining performance bounds [Shani et al., 2012].

To take advantage of the advances in solvers for POMDPs and MDPs, we solve a Dec-POMDP by recasting it as a continuous-state MDP. The state space consists of all reachable probability distributions over states of the system and histories of the agents (which we term occupancy states) and the action space consists of all decision rules mapping histories to actions. A primary result of this paper is a demonstration that the occupancy state is sufficient for optimal planning in Dec-POMDPs. Then, we show that the value function is a piecewise linear and convex function of occupancy states. As a result, POMDP algorithms can for the first time be applied directly to Dec-POMDPs. This is a significant theoretical advance for planning in Dec-POMDPs. However, given that both occupancy states and decision rules are defined over the full history space, scalability remains limited. To increase scalability, we replace the full history space by a low-dimensional feature set using a lossless dimension reduction technique. This reduction allows scalability in the horizon that is significantly greater than previous state-of-the-art optimal algorithms.

The remainder of this paper is organized as follows. We first present the necessary background in Section 2. We then discuss, in Section 3, the transformation of a Dec-POMDP into a continuous-state MDP together with theoretical results. Next, we introduce, in Section 4, our algorithm, featurebased heuristic search value iteration (FB-HSVI), which encodes the occupancy state using a low-dimensional feature space and can generate an optimal Dec-POMDP policy. We conclude with experimental results on several benchmarks.

2 Background and related work

We first review relevant models and provide a short overview of optimal Dec-POMDP algorithms.

2.1 MDPs, POMDPs and Dec-POMDPs

An MDP is a tuple (S↪ A↪ P ↪ R) where S is a set of states, A is a set of actions, P a is a ♣S♣ × ♣S♣ stochastic matrix denoting the probability of transiting from state s to state s￿ using action a, Ra is a ♣S♣ ×1 reward vector defining the reward of executing action a in state s. In solving an MDP, the goal is to produce a policy π (a mapping from states to actions) to be executed at each time step t that maximizes some measure of accumulated reward - here we focus on the expected total reward over planning horizon T .

A POMDP is a tuple (S↪A↪Z↪P↪O↪R↪ b0 ) where S↪A↪P↪R are the same as in an MDP, Z is a set of observations and set O consists of ♣S♣ × ♣S♣ observation matrices Oaz , one for each observation z and action a. While the agent is unable to observe the true state of the world, it can nonetheless maintain a belief state bt [s] = P(st = s ♣ b0 ↪ a0 ↪ z1 ↪ · · · ↪ at-1 ↪ zt ). Belief b0 defines the initial belief state. We shall refer to the past sequence of actions and observations the agent experienced up to time step t as θt = (a0 ↪ z1 ↪ · · · ↪ at-1 ↪ zt ), a t-length history. POMDPs can be solved as MDPs with continuous states that are the belief states in the POMDP. In this formulation a policy is a mapping from belief states to actions.

A Dec-POMDP is a tuple (S↪⊗iAi↪⊗iZi↪P↪O↪R↪ b0 ). These quantities are the same as a POMDP, but now each agent has its own action and observation sets. The transitions, observations and rewards depend on the actions chosen by all agents. Because each agent only has access to its own local observations, the goal is to maximize a common value function while executing policies that depend on solely each agent's own histories. Due to this decentralized nature of information, Dec-POMDPs cannot na¨ıvely be transformed into POMDPs (or MDPs). In fact, by casting the Dec-POMDP model into a continuous MDP with a piecewise linear convex value function, as we demonstrate in Section 3.2, we provide the first evidence that POMDP methods also directly apply in Dec-POMDPs. Because a central belief state cannot be calculated by the agents, previous work has typically represented a T -step policy for each agent as a policy tree which maps each history to an action. Details are discussed in Section 3.1.

2.2 Optimal solutions for Dec-POMDPs

One class of Dec-POMDP solution methods is based on dynamic programming [Howard, 1960]. Here, a set of T-step policy trees, one for each agent, is generated from the bottom up [Hansen et al., 2004]. On each step, all t-step policies are generated that build off policies from step t + 1. Any policy that has lower value than some other policy for all states and possible policies of the other agents is then pruned (with linear programming). This generation and pruning continues until the desired horizon is reached and trees with the highest value at the initial state are chosen. More efficient dynamic programming methods have been developed, reducing the number trees generated [Amato et al., 2009] or compressing policy representations [Boularias and Chaib-draa, 2008].

Trees can also be built from the top down using heuristic search [Szer et al., 2005]. In this case, a search node is a set of partial policies for the agents up to a given horizon, t. These partial policies can be evaluated up to that horizon and then a heuristic (such as the MDP or POMDP value) can be added. The resulting heuristic values are over-estimates of the true value, allowing an A*-style search through the space of possible policies for the agents, expanding promising search nodes to horizon t +1 from horizon t. A more general search framework was also developed [Oliehoek et al., 2008]. Recent work has included clustering probabilistically equivalent histories [Oliehoek et al., 2009] and incrementally expanding nodes in the search tree [Spaan et al., 2011], greatly improving scalability of the original algorithm.

While current methods attempt to limit the number of policies considered, they rely on explicit policy representations that consider the full histories of each agent. Furthermore, even though these algorithms use an offline centralized planning phase, they have not been able to identify a concise sufficient statistic that allows for greater scalability.

3 Dec-POMDPs as continuous-state MDPs

We now discuss the transformation of a Dec-POMDP into a continuous-state MDP, starting with the required definitions. This approach utilizes the commonly used offline planning phase to centralize the available information as a distribution over the state and agent histories from the perspective of a central planner. Note that the central planner does not observe the agent's actions or observations during execution but knows what policies they are executing. The actions can then be selected in the form of decision rules which condition actions on specific histories seen by each agent.

3.1 Preliminary definitions

Let Θti and Θt be sets of agent i's and joint histories at time step t = 0↪ 1↪ · · · ↪ T - 1, respectively. A local policy for agent i is an ordered sequence of local decision rules, πi ≡ π0 i π1 i · · · πT-1 i . A local decision rule πt i : Θti ￿→ Ai is a mapping from local histories θt i ∈ Θti to local actions πt i (θt i ) ∈ Ai.

A separable policy π is a tuple of n local policies, π ≡ (π1↪ π2↪ · · · ↪ πn), one for each agent i = 1↪ 2↪ · · · ↪ n. We denote πi the local policy of agent i, and π-i ≡

(π1↪ · · · ↪ πi-1↪ πi+1↪ · · · ↪ πn) that of its teammates. A separable decision rule at time step t is a tuple of n local decision rules at time step t, πt ≡ (πt1 ↪ πt2 ↪ · · · ↪ πtn ), one local decision rule for each agent. One can consider a separable policy as a sequence of separable decision rules, π ≡ (π0 ↪ π1 ↪ · · · ↪ πT-1 ), one for each time step. We use notation πt:l (where l ≥ t) to represent an ordered sequence of separable decision rules (πt ↪ · · · ↪ πl ), namely a (partial) policy.

The occupancy state of the process under the control of separable policy π0:t-1 starting at initial probability distribution b0 is the probability distribution over states of the system and joint histories, ηt = b0P π0:t-1 . Like πt:l , we shall use notation ηt:l instead of (ηt ↪ · · · ↪ ηl ). Here, occupancy state ηt is a (♣S♣ × ♣Θt ♣) × 1 stochastic vector, and P πt:l is a (♣S♣ × ♣Θt ♣) × (♣S♣ × ♣Θl+1 ♣) stochastic matrix, where each entry P πt:l [st ↪ θt ; sl+1 ↪ θl+1 ] is the conditional probability of being in (sl+1 ↪ θl+1 ) if the initial state and history is (st ↪ θt ) and agents follow separable policy πt:l . For the sake of simplicity, we use notation P πt instead of P πt:t . Note that given a policy and initial state distribution, the occupancy state can be calculated from P and O in the Dec-POMDP.

3.2 Formulation and properties

The first property of the occupancy state is that it summarizes all past information of the agents. The proof can be derived by expanding out the occupancy state representation ηt = b0P π0:t-1 . While we utilize action-observation histories, it can also be shown that occupancy states depending on just observation histories and states are also sufficient when using deterministic policies (which contain an optimal policy) [Oliehoek, 2013].

Theorem 1. The future occupancy state depends only upon the present occupancy state and separable decision rule:

This theorem shows that occupancy states describe a Markov decision process: the occupancy MDP model. Equation (1) defines the transition function of this model. Not surprisingly, the occupancy MDP model is deterministic. A complete representation of the occupancy MDP model is obtained by also specifying the reward function over occupancy states. We denote Rπt the reward vector associated to separable decision rule πt , where entries are defined by: ∀st ∈ S↪θ t ∈ Θt , Rπt [st ↪ θt ] = Rπt (θt ) [st ]. That is, the reward for choosing a decision rule at an occupancy state is defined as the expected value of rewards over underlying states and histories. We are now ready to formally define the occupancy MDP model that corresponds to the Dec-POMDP model. If we let ￿ be the occupancy state space, and A be the separable decision rule space, then we define tuple (￿↪A↪P↪R↪ b0 ) to be the occupancy MDP model that corresponds to the Dec-POMDP model.

Solving the occupancy MDP determines policy π∗ that maximizes the expected cumulative reward over horizon T :

Similar to the traditional MDP model, the t-th value function υt under the control of a policy is defined as follows: ∀t = 0↪ 1↪ · · · ↪ T - 1, ∀ηt ∈ ￿

where υT (·) = 0. The quantity at the right hand side of max operator of Equation (2) is referred to as the Q-value function defined by: ∀ηt ∈ ￿, and ∀πt ∈ A, Qυt+1 (ηt ↪ πt ) = (Rπt )￿ηt + υt+1 (ηtP πt ).

Notice Equation (2) is Bellman's optimality equation for the occupancy MDP model. This leads to the following result.

Corollary 1. Optimizing the occupancy MDP model is equivalent to optimizing the Dec-POMDP.

This follows from expanding Equation (2) for each step of the problem and noting that due to the deterministic update of η, the resulting policy is a sequence of separable decision rules that maximizes the expected value for the Dec-POMDP.

We can also show that the value function is a piecewise linear and convex (PWLC) function of the occupancy states.

Theorem 2. The t-th value function υt : ￿ ￿→ R solution of the Equation (2) is a PWLC function of the occupancy states.

Similar to belief MDPs, the proof holds by induction given that υT , Rπt and P πt are linear and all operators involved in Equation (2) preserve the PWLC property. With Theorems 1 and 2 as a background, one can exploit advances in belief MDPs to solve occupancy MDPs. However, given that both occupancy states and decision rules are defined over the entire history space, the ability to scale up remains limited. In the remainder of this paper, we will use Dec-POMDPs and occupancy MDPs interchangeably.

4 Optimally solving occupancyMDPs

In this section, we first present an outline of a novel algorithm for solving Dec-POMDPs. We also propose a dimension reduction framework that replaces the high-dimensional history space by a lower-dimensional feature set, with no risk of losing: (PWLC) the PWLC property of the value function over occupancy states in the lower-dimensional feature set; and (LOSSLESS) the sufficiency of occupancy states in the lowerdimensional feature set.

4.1 The FB-HSVI algorithm

Our algorithm, termed feature-based heuristic search value iteration (FB-HSVI), exploits the PWLC structure of the value function within a general heuristic search algorithm. Many algorithms for solving belief MDPs take advantage of the PWLC property of the value function. One such heuristic search algorithm that preserves the ability to theoretically converge to an ￿-optimal solution is heuristic search value iteration (HSVI) [Smith and Simmons, 2004]. We extend HSVI to solve the occupancy MDP, but other POMDP algorithms would also be applicable.

HSVI proceeds by creating trajectories, based on upper and lower bounds over the exact value function, denoted ¯ υ and υ, respectively. Each such trajectory starts from the initial probability distribution b0 . HSVI always executes the best action

Algorithm 1: The FB-HSVI algorithm

specified by the upper bound, and then selects the next belief state that maximizes the gap between the bounds. When the trajectory is finished the beliefs are backed up in reverse order. HSVI uses the following ideas: value function guarantees: value function representations for the lower bound υ and upper bound ¯ υ maintain valid bounds on the optimal value function υ∗ ; point-based backups: value functions are improved by using backup operations only over a subset of the entire belief simplex; trajectory-based heuristic search: the upper bound guides search through trajectories of beliefs, focusing on regions where the bounds need improvement.

FB-HSVI, as described in Algorithm 1, uses the HSVI algorithmic framework, inheriting the above characteristics. FB-HSVI differs from HSVI in many aspects, including: (1) efficient point-based backup: we use an efficient implementation of the backup that typically circumvents the systematic enumeration of all separable decision rules [Dibangoye et al., 2012; 2013]; (2) low-dimensional feature set representations: we replace the high-dimensional history space by a lower dimensional feature set, allowing for compact representations (represented with the Compress operation in the algorithm); and (3) bound updates: we take advantage of the determinism of occupancy MDPs to update forward the upper bound and backward the lower bound. These ideas together allow FB-HSVI to: (1) scale up to Dec-POMDP problems of unprecedented horizon size; (2) allow value function generalization over unvisited occupancy states; and (3) speed up the convergence to the optimal value function.

4.2 Lossless linear dimension reduction

In the following, we describe the dimension reduction framework that permits compact representations. This consists of defining metrics for considering histories to be equivalent. Then, we build upon this framework to introduce a feature selection algorithm that we use in practice. We introduce finite-order feature selection (FOFS) that operates incrementally during algorithm execution. That is, histories can be generated for the next step using forward search (as in Algorithm 1) with the current histories. The next-step histories can then be compressed by the methods discussed below, providing a reduced set of histories to be utilized in the algorithm. FOFS seeks to find representative sets of shorter horizon histories to replace the possible histories at a given step without any loss in solution quality.

Using feature mappings

The (local) feature associated with local history θi given occupancy state ηt , denoted φθi , is a function mapping all pairs of states and histories of the other agents to reals, such that ∀s↪ ∀θ-i : φθi [s↪θ-i] = p(s↪θ-i↪ θi♣ηt ). Each feature φθi has a label associating it with a local history, ￿i or L(θi). Furthermore, we denote C￿i the cluster of local histories with label ￿i. One way to make explicit the relationship between features and occupancy states is to consider occupancy in matrix form, where columns correspond to labels and rows are states and histories of the other agents.

In selecting features, we combine two criteria. The first criterion permits us to group together local histories that are probabilistically equivalent and treat them as a single local history. For agent i, we say that two local histories θi and θ￿i are probabilistically equivalent when φθi ∝ φθ￿i . Intuitively, it can be seen that probabilistically equivalent histories provide the same information about the environment (including the other agents) from a single agent's perspective. It has been shown that it is lossless to condition action selection only upon label L(θi) instead of θi [Oliehoek et al., 2009]. This allows a lossless compression of features with values generated as follows: ∀s↪ ∀θ-i : φ￿i [s↪ L(θ-i)] = ￿θi∈C￿i φθi [s↪θ -i].

The second criterion enhances the generalization of the value function over unvisited occupancy states while preserving important information. This approach can be thought of as having a "sliding window" of history information. We can consider labels ￿i to be any length local history in set Θi. To reduce the space of labels, we define a finite-order label ￿i↪k or Lk (￿i) to be label ￿i's k rightmost (most recent) actions and observations. In addition, we denote C￿i↪k the cluster of labels with identical finite-order label Lk (￿i). This allows a (possibly lossy) compression of features with values defined as follows ∀s↪ ∀￿-i : φ￿i↪k [s↪ Lk (￿-i)] = ￿￿i∈C￿i↪k φ￿i [s↪￿ -i]. Obviously, there is always a parameter k from 0 to t - 1 so that features φ￿i↪k are lossless (such as k = t - 1). Next, we present an algorithm that finds such a parameter k.

Algorithmic details

To guarantee the dimension reduction preserves the PWLC property, we consider linear dimension reductions [Boularias and Chaib-draa, 2008]. More specifically, we use clustering based on probabilistic equivalence and finite-order labels and generate a linear dimension reduction accordingly.

In order to ensure the sufficiency of occupancy states, we introduce the concept of Hajnal lossless compression. Informally, this property gives insight on how to select features that preserve the ability to eventually find an optimal policy. In defining this property, we need to bound the regret of searching for the optimal policy over the restricted space instead of the original high-dimensional history space. The regret depends on distance metrics that are used to measure the closeness between exact and approximate occupancy states.

Define metrics d and D as follows: ∀ηtx ↪ ∀ηty , d(ηtx ↪ ηty ) = ￿s∈S ￿θ∈Θ ￿P(s↪θ ♣ηtx ) -P(s↪θ ♣ηty )￿+↪ where (o)+ = o if o > 0 and zero otherwise, and D(η0:T -1 x ↪ η0:T -1 y ) = ￿T-1 t=0 d(ηtx ↪ ηty )▷ Metric d, known as the Hajnal measure, has many applications in the theory of ergodic chains [Paz, 1971]. Informally, d(ηtx ↪ ηty ) is the minimal quantity of probability that would have to be re-assigned in order to transform exact occupancy state ηtx to occupancy state ηty . Similarly, D(η0:T-1 x ↪ η0:T -1 y ), referred to as the variational Hajnal measure between sequences of occupancy states, is the minimal cumulated quantity of probability by which both sequences might differ.

The following theorem bounds the regret of searching for the optimal policy over the restricted space instead of the original high-dimensional history space. The proof is similar to the performance guarantee of the policy search algorithm (Theorem 1) [Bagnell et al., 2003].

Theorem 3. Let policies π and ￿ π be the solution of the occupancy state MDP model when optimized on exact and approximate occupancy states, respectively. Then,

Proof. If we let β = υπ (η0 ) -υ ￿ π (η0 ), then we have that:

Now, let βt = υπt ↪￿ πt+1:T -1 (ηt ) - υ ￿ πt:T-1 (ηt ), and αt be the hyperplane in value function υπt ↪￿ πt+1:T-1 that is maximal at ηt , and ￿αt be the hyperplane in υ ￿ πt:T-1 that is maximal at ￿ηt .

=(αt - ￿αt ) · (ηt - ￿ηt ) ≤ Td(ηt ↪ ￿ηt )♣♣r♣♣ The first inequality holds since (￿αt )￿ ·￿ηt ≥ (αt )￿ ·￿ηt , where ￿ηt and ηt need to be losslessly (de-)compressed to fit ￿αt and αt , respectively. The last inequality holds using the H¨older inequality and Hajnal measure. By replacing βt in the last expression of β and definition of D, the result holds.

The bound (Theorem 3) depends on how close, in the Hajnal sense, exact and approximate occupancy states are. When the linear dimension reduction is lossless, that is D(η0:T-1 ↪ ￿η0:T-1 ) = 0, the bound implies that there exists a policy in the restricted space that achieves performance as good as any policy in the high-dimensional history space.

It is easy to check whether or not a linear dimension reduction is Hajnal lossless. In fact, checking the property over the entire sequence η0:T-1 of occupancies consists of checking that d(ηt ↪ ￿ηt ) = 0 holds for any occupancy ηt in that sequence. We call this a local Hajnal lossless compression. We are now ready to introduce our feature selection algorithm, namely the finite-order feature selection (FOFS), that automatically selects informative features based on the Hajnal lossless compression.

FOFS first compresses occupancy states based on probabilistic equivalence as in [Oliehoek et al., 2009]. Given occupancy state ηt , for each agent i, we replace histories with the associated labels, thereby replacing features φθi by corresponding feature φ￿i . Let ˜ηt be the occupancy state with probabilistically equivalent histories removed. Clearly, there is no risk of loosing either property (PWLC) or property (LOSSLESS) by planning over ˜ηt instead of ηt since this compression is lossless and linear. However, ˜ηt is still defined over a high-dimensional label set. This significantly limits the generalization of the value function over unvisited occupancy states and highlights the necessity of a dimension reduction transformation.

FOFS continues by compressing occupancy ˜ηt into ￿ηt using finite-order labels, starting with k = 0. This compression is linear so it preserves property (PWLC), but it can be lossy. When local Hajnal lossless compression holds, that is ∀s↪ ∀￿: P(s↪￿ ♣˜ηt ) - P(s↪ Lk (￿)♣￿ηt ) = 0, FOFS returns ￿ηt with labels ￿ replaced with finite-order labels Lk (￿). Otherwise, it re-computes ￿ηt with increased length k = k+1. The algorithm iterates until the local Hajnal lossless compression holds. In the worst case, FOFS terminates with k = t - 1, and returns a lossless representation ￿ηt of the original occupancy state ηt . When k < t-1, occupancy state ￿ηt is defined as a probability distribution over states and l-length histories where l ≤ k < t-1, and thus the compression is a dimension reduction.

In both cases, to compress an occupancy state for a given criterion, FOFS proceeds by clustering histories (or labels) of one agent at a time assuming the other agents' labels are fixed (as full extensions of previous step histories initially and then as their compressed length). It repeats this procedure for each agent alternatively until no more clustering can occur.

5 Experiments

We ran FB-HSVI on a Mac OSX machine with 2.4GHz DualCore Intel and 2GB of available RAM. We solved the backup using constraint optimization with the toulbar2 solver. We initialized the upper bound as the value function of the underlying MDP; and the lower bound as the value function of the blind policy. We evaluate three variants of FB-HSVI(ρ): the first variant, FB-HSVI(0), is FB-HSVI without compression or efficient backups; the second variant, FB-HSVI(1) utilizes k = ∞ (full histories), but incorporates efficient point-based backups; and FB-HSVI(2) uses both efficient backups and histories compressed with FOFS.

We evaluated our algorithms on five benchmark problems from the literature: multi-agent tiger; recycling-robot; gridsmall; cooperative box-pushing; and mars rovers. These are the largest and most difficult benchmarks from the literature. For each benchmark, we compared our algorithms with state-of-the-art exact solvers: GMAA*-ICE [Spaan et al., 2011], IPG [Amato et al., 2009], MILP [Aras and Dutech, 2010], and LPC [Boularias and Chaib-draa, 2008]. IPG and LPC perform dynamic programming, GMAA*-ICE performs heuristic search and MILP is a mixed integer linear programming method. Results for GMAA*-ICE (provided by Matthijs Spaan), IPG, MILP and LPC were conducted on different machines. Because of this, the timing results are not directly comparable to the other methods, but are likely to only differ by a small constant factor.

The results can be seen in Table 1. For each algorithm we reported the computation time, which includes the time to compute heuristic values when appropriate since all algorithms do not use the same heuristics. We also reported the ￿- optimal expected cumulative reward υ￿(η0 ) (where ￿ = 0▷01) at the initial occupancy state. Furthermore, we also reported K the maximum parameter k found by FOFS for each benchmark (representing the maximum history length used). Table 1 clearly shows that FB-HSVI(2) allows for significant improvement over the state-of-the-art solvers: for all tested benchmarks we provide results for longer horizons than have been solved previously (the bold entries).

There are several reasons for FB-HSVI(2)'s performance: first, we search in the space of policies mapping lowerdimensional features to actions, whereas the other solvers search in the space of policies mapping histories to actions;

we use a value function mapping occupancy states to reals allowing it to generalize the value function over unvisited occupancies whereas all other solvers use value functions mapping partial policies to reals; finally, we replace the brute-force backup by an efficient constraint optimization approach.

To better understand FB-HSVI, we compare three variants ρ = 0↪ 1↪ 2 presented earlier. For ρ = 0, we quickly run out of time since we explicitly enumerate all separable decision rules. For ρ = 1, we scale up to larger horizons but convergence slows down because the value function is defined over the full history space. For ρ = 2, we enhance the generalization of the value function over unvisited occupancy states by means of finite-order labels. This circumvents unnecessary backups and speeds up convergence.

6 Conclusion

This paper explores new theory and algorithms for solving Dec-POMDPs. This theory builds upon a novel transformation of Dec-POMDPs to continuous-state and deterministic MDPs, generalizing previous theory and algorithmic results. In particular, we demonstrate two important results: (1) the distribution over both the states and the histories, namely occupancy states, are sufficient for optimal planning in DecPOMDPs; (2) the value function is piecewise linear and convex over the occupancy states. With this new formulation, POMDP methods can, for the first time, be directly applied to Dec-POMDPs. This permits us to no longer maintain an explicit policy representation and allows us to exploit structure in the value function. We also describe a novel algorithm for this representation, extending to large state and action spaces by dimension reduction and constraint optimization. This algorithm, termed feature-based heuristic search value iteration or FB-HSVI, was shown to scale up to large planning horizons, reducing the computation time by multiple orders of magnitude over previous approaches.

In the future, we plan to explore applying this theory and algorithm to subclasses of Dec-POMDPs and larger teams of agents. For instance, we have already shown that occupancy states over just states (and not agent histories) can be used in transition and observation independent Dec-MDPs to greatly increase scalability [Dibangoye et al., 2012; 2013]. We would like to explore using occupancy states over observation histories (rather than action-observation histories), which were shown to be sufficient (along with action-observation histories) simultaneous to this work [Oliehoek, 2013]. In addition, we think occupancy states together with graphical models could help exploit the locality of interaction among agents statically (as in ND-POMDPs [Nair et al., 2005; Kumar and Zilberstein, 2009]) or dynamically (as in [Canu and Mouaddib, 2011]). Furthermore, the scalability of FBHSVI is encouraging and we will pursue additional methods to automatically compute compact representations.

7 Acknowledgements

We would like to thank Matthijs Spaan for providing results for GMAA*-ICE as well as Frans Oliehoek and the reviewers for their helpful comments. Research supported in part by AFOSR MURI project #FA9550-09-1-0538.