Isomorph-Free Branch and Bound Search for Finite State Controllers

1 Introduction

In this work we describe an approach to generate isomorphfree Moore finite state automata. This is an important problem since deterministic finite state controllers (FSCs) for partially observable Markov decision processes (POMDPs) are Moore finite state automata. The optimization of a POMDP policy can be cast as a search for the best FSC of a given size. However, since there are many controllers that encode the same policy, there is a need for techniques that can generate only the controllers that correspond to different policies. We denote by "equivalent" the controllers that encode the same policy. Controllers can be thought as deterministic finite automata for which there exist several minimization techniques to identify smaller equivalent automata [Huffman, 1954; Moore, 1956; Hopcroft, 1971]. Building on this work we show how to generate only non-equivalent minimal FSCs.

Meuleau et al. [1999] previously designed a branch and bound technique to search for the best controller of a given size that avoids the generation of some symmetric controllers.

Two controllers are symmetric when a permutation of the actions of the first controller yields the second controller. Controller symmetry is a special type of controller equivalence, but does not cover all forms of controller equivalence. We show that a significant speed up can be obtained by generating only non-equivalent controllers. We also show how to further prune the search space by using tighter upper bounds in branch and bound.

The optimization of POMDP policies by branch and bound in the space of fixed-size deterministic controllers is particularly useful in applications where some performance guarantees are desired and online computation costs need to be minimized. For instance, the emerging class of monitoring and assistive applications on mobile or wearable devices can be cast as POMDPs. While these applications need to be continuously running, they also need to minimize energy consumption to maximize battery life. Controllers are ideally suited since there is no online planning or belief monitoring. Due to the non-convex nature of controller optimization, alternative approaches such as bounded policy iteration [Poupart and Boutilier, 2003], stochastic local search [Braziunas and Boutilier, 2004], quadratically constrained linear programming [Amato et al., 2009], gradient ascent [Meuleau et al., 1999] and expectation maximization [Toussaint et al., 2006] may get stuck in arbitrarily bad local optima (although some techniques to escape local optima have been proposed [Poupart et al., 2011b]). In contrast, branch and bound is guaranteed to find the best deterministic controller of a given size with enough time.

The paper is structured as follows. Sec. 2 reviews POMDPs and finite state controllers. Sec. 3 describes related work on controller optimization, including branch and bound. Sec. 4 shows how to detect equivalent controllers and how to efficiently generate isomorph-free controllers. Sec. 5 explains how to improve branch and bound by generating only non-equivalent controllers, using tighter upper bounds, prioritizing the search and by limiting the number of edges. Sec. 6 reports experiments with benchmark problems and a wayfinding application to assist people with Alzheimer's disease. Sec. 7 concludes.

2 Background

Partially observable Markov decision processes are formally defined by a tuple <S, A, O, T, Z, R, γ> where S is the set of states s, A is the set of actions a, O is the set of observations o, T(s′ , s, a) = Pr(s′ |s, a) defines the transition probabilities, Z(o, a, s′ ) = Pr(o|a, s′ ) defines the observation probabilities, R(s, a) defines the reward function and 0 < γ < 1 is the discount factor. The goal is to find a policy π : H → A that maps histories h ∈ H of previous actions and observations to the next action. Since the length of histories grows with time and the number of histories grows exponentially with time, there is a need for a bounded representation. One option is to use belief states (i.e., distributions over states) which can be thought as a sufficient statistic that encodes the same information as histories. Alternatively, we can restrict policies to finite state controllers, which define a compact mapping from histories to actions.

A finite state controller (FSC) consists of a set of nodes labeled with actions and edges labeled with observations. An FSC is parametrized by an action mapping φ, which assigns an action to each node (i.e., φ : A → N) and a node mapping ψ, which indicates which node each edge maps to (i.e., ψ : N ×O → N). The policy encoded by a controller is executed by performing the action associated with each node traversed and by following the edge associated with each observation received. This execution requires a negligible amount of computation at each step to update the current node and lookup the corresponding action. Hence, it is ideal for mobile applications, especially those with severe computation or energy constraints.

We consider the problem of finding the best controller with a fixed number of nodes. The more nodes there are the better the controller may be, but past experience has shown that for many POMDPs there exist small controllers that are quite good [Poupart et al., 2011b]. Hence, by fixing the number of nodes we can limit the search space and still find a good controller most of the time. The search space consists of all possible φ's and ψ's, which is exponentially large. The value V π (s, n) of starting a controller π = <φ, ψ> in node n at state s can be computed as follows:

Without loss of generality, we assume that the policy of a controller always starts in the first node n1. Hence the value of a controller at initial belief b0 is V π (b0) = ∑s b0(s)V π (n1, s).

3 RelatedWork

The optimization of POMDP controllers is notoriously difficult [Vlassis et al., 2012]. Hansen [Hansen, 1998] first proposed a policy iteration algorithm that gradually constructs a controller by adding nodes. However, the size of the controller tends to grow exponentially with the number of time steps. Subsequently, several approaches were proposed to optimize controllers of a fixed size [Poupart and Boutilier, 2003; Braziunas and Boutilier, 2004; Amato et al., 2009; Meuleau et al., 1999; Toussaint et al., 2006]. These approaches often consider stochastic controllers, allowing them to employ techniques from continuous optimization. Unfortunately, due to the non-convex nature of the optimization, they may get trapped in arbitrarily bad local optima. Some approaches have been augmented with escape techniques, but this is usually done by increasing the size of the controller [Poupart and Boutilier, 2003; Poupart et al., 2011b]. Alternatively, an exhaustive search in the space of deterministic controllers can guarantee that the best deterministic controller is found. To that effect, Meuleau et al. [1999] proposed a branch and bound technique to efficiently search the space of controllers. We briefly review Meuleau's approach since we will improve it in the next sections.

Branch and bound performs a depth-first backtracking search in the space of controller parameters. This space consists of |N| action variables (one for each node mapping φ(n)) and |N||O| node variables (one for each edge mapping ψ(n, o)). The search incrementally builds a controller by assigning values to the variables until a full controller is obtained or we backtrack at a partial controller. At each partial controller, an upper bound on the value of all possible completions of this partial controller is computed. If this upper bound is lower than the value of the best controller visited so far, then the search is cut. Alg. 1 describes a generic branch and bound algorithm for controllers. It requires a method to compute partial controller upper bounds and heuristics to determine the order in which the variables and their values should be enumerated. In addition, a pruning technique may be used to detect equivalent controllers.

Meuleau et al. [1999] prune symmetric controllers by imposing a lexicographic ordering on the actions assigned to the nodes. Assuming that actions are numbered from 1 to |A|, then controllers whose nodes are not assigned actions in increasing order are rejected. This prunes factorially many equivalent controllers that would result from permuting nodes with different actions. However, nodes with identical actions may still be permuted to yield syntactically different controllers that are equivalent. Other non-obvious forms of equivalence will also go undetected. We explain how to detect and prune all forms of equivalence in the next section.

Algorithm 1 Branch and Bound

BRANCHANDBOUND(π, LB)

1 if PRUNE(π) then return LB 2 if π is fully specified then return max(V π (b0),LB) 3 UB ← UPPERBOUND(π) 4 if UB < LB then return LB 5 Select next variable V to instantiate 6 while some domain values have not been tried 7 Select next value v to try 8 Let π′ be π extended with V = v 9 if ¬PRUNE(π′ ) 10 LB ← BRANCHANDBOUND(π′ , LB) 11 return LB

For the upper bound, Meuleau et al. [1999] adapt the QMDP upper bound to partial controllers. The idea is to let the choice of action and next node in the φ and ψ mappings depend on the underlying state s even if it is not observable. Because decisions are based on more information than what is normally available, the resulting value is necessarily higher, yielding an upper bound. When φ and ψ are completely unspecified, the QMDP upper bound ¯ V satisfies:

The above equation can easily be adapted to partially specified controllers by replacing the maximization over actions by the action selected for each specified action mapping and by replacing the maximization over next nodes by the selected next node for each specified next node mapping. The upper bound is computed with dynamic programming by repeatedly computing the right-hand-side of Eq. 1. In Sec. 5, we explain how to improve this bound by considering the fast informed bound and an augmented POMDP.

4 Detecting Equivalent Controllers

Two FSCs are said to be equivalent when they encode the same policy. The policy encoded by a controller is a set of conditional plans rooted at each node. Here a conditional plan is a tree that alternates between actions and observations. Trees are generally infinite unless the planning horizon is finite. Two controllers that contain the same set of conditional plans are considered equivalent. Detecting equivalent controllers is related to the problem of detecting that two automata accept the same language. In fact, finite state controllers are deterministic finite automata (DFA) where the observations are input symbols and actions are output symbols. In automata theory, it is common to consider only two outputs (accept and reject) since the goal is to define a language that accepts a specific set of strings. Nevertheless, controllers can be viewed as a straightforward extension where strings of inputs/observations are partitioned into several classes labeled with different outputs/actions. Hence algorithms to detect equivalent DFA can be used to detect equivalent controllers.

Equivalent DFA/FSCs arise when some nodes are repeated or permuted. Several algorithms have been proposed to minimize automata by detecting repeated nodes [Huffman, 1954; Moore, 1956; Hopcroft, 1971]. The same can be done with controllers by detecting nodes that are the root of identical conditional plans. Alg. 2 describes how to do this by gradually updating a matrix that indicates which pairs of nodes are the roots of different trees. Let M be an |N| × |N| matrix where |N| is the number of nodes in a FSC. The algorithm starts with all entries in M set to 1, indicating that all nodes of the FSC may be equivalent. Then the algorithm repeatedly inspects the entries and revises an entry Mi,j to 0 when the conditional plans of nodes ni and nj are found to be different. This occurs when the actions of those nodes are different or their edges point to subtrees that are not equivalent. The algorithm terminates when there are no more entries to be revised. If there is a non-diagonal entry set to 1, then the FSC is not minimal since some of its nodes are repeated. While the procedure described in Alg. 2 is not the most efficient, it is conceptually simple and it can be easily modified to deal with partial controllers as we will see in Alg. 3.

Minimal FSCs (no repeated nodes) may still be equivalent if their nodes are permuted. In that case the FSCs are said to be isomorphic. Since our goal is to generate non-equivalent controllers, we can generate a single minimal FSC in each equivalence class by imposing a lexicographic ordering. This

Algorithm 2 Repeated Trees in Full FSC

REPEATEDTREESINFULLFSC(FSC)

1 Let M be an |N| × |N| matrix of ones 2 repeat 3 for each i, j ∈ {1, ..., |N|} such that i ̸= j 4 if φ(ni) ̸= φ(nj) then Mi,j ← 0 5 for each observation o 6 if Mψ(ni,o),ψ(nj ,o) = 0 then Mi,j ← 0 7 until M doesn't change 8 if ∃i ̸= j such that Mij = 1 then return true 9 else return false

will ensure that among all node permutations, only one configuration is retained. Suppose that we number all nodes from 1 to |N| and all observations from 1 to |O|, we can then number edges from 1 to |N||O| such that the index of the edge coming out of node n and labeled with observation o is (n - 1)|O| + o. We can retain a single permutation of the nodes by making sure that the edges point to nodes that satisfy the following conditions:

The first condition says that the first edge should point to node 1 or a new node that will take the next index. In this case the next index is 2. The second condition says that all other edges should point to a node that has already been pointed to by a previous edge or a new node that will take the next index. In this case the index is 1 plus the largest index of the nodes pointed to so far.

Theorem 1. There is exactly one minimal controller in each equivalence class that satisfies the conditions in (2).

Proof. We sketch an informal proof. There is at least one minimal controller in each equivalence class that satisfies the conditions in (2) since we can take any minimal controller and renumber its nodes according to the order in which the nodes would be visited by a breadth first search that expands each node at most once.

We prove by contradiction that there is at most one minimal controller in each equivalence class that satisfies the conditions in (2). Suppose that we have two syntactically different minimal controllers in the same equivalence class. By definition, these controllers encode the same policy, which means that they have the same set of conditional plans. Alg. 2 ensures that none of their conditional plans are repeated. So they must have the same number of nodes and there exists a one-to-one mapping between the conditional plans of the two controllers. The conditions in (2) also ensure that the nodes are ordered in the same way, which means that there is no syntactic difference between the controllers. This contradicts our assumption.

Alg. 2 and the conditions in (2) give us the tools to identify a unique minimal controller in each equivalence class that we will call the canonical controller. We can use these tools in a branch and bound procedure to generate only canonical controllers corresponding to different policies. That being said, branch and bound operates by gradually completing partial controllers. Hence, we would like to detect as early as possible that all completions of a partial controller will yield noncanonical controllers in order to cut the search early. This can be done by modifying Alg. 2 to detect repeated trees in partial controllers. When an action or an edge is unassigned, we will assume that it can take any desirable assignment to show that two trees are different. Hence, Alg. 3 will detect identical trees only when two trees will necessarily be identical, regardless of how unassigned variables are assigned. We denote by '*' the value of an unassigned variable.

Algorithm 3 Repeated Trees in Partial FSC

REPEATEDTREESINPARTIALFSC(FSC) 1 Let M be an |N| × |N| matrix of ones 2 repeat 3 for each i, j ∈ {1, ..., |N|} such that i ̸= j 4 if φ(ni) = ∗ or φ(nj) = ∗ or φ(ni) ̸= φ(nj) 5 Mi,j ← 0 6 for each observation o 7 if ψ(ni, o) = ∗ or ψ(nj , o) = ∗ or Mψ(ni,o),ψ(nj ,o) = 0 then Mi,j ← 0 8 until M doesn't change 9 if ∃i ̸= j such that Mij = 1 then return true 10 else return false

5 Improved Branch and Bound

There are several factors that influence the effectiveness of branch and bound. In addition to pruning non-canonical controllers as in the previous section, the quality of the upper bounds, the order in which variables and values are selected and the number of edges will influence the amount of search.

5.1 Upper Bound

Tighter upper bounds can significantly reduce the amount of search. We propose to adapt the fast informed bound (FIB) to controllers since this bound is tighter than QMDP. While QMDP provides an upper bound by assuming that the current state is observed, FIB assumes that the previous state is observed. In practice, neither the current nor the previous states are observable, however the previous state provides less additional information than the current state, which is why FIB is tighter. When φ and ψ are completely unspecified, the upper bound ¯ V based on FIB is obtained as follows:

The above equation can easily be adapted to partially specified controllers by replacing the maximization over actions by the action selected for each specified action mapping and by replacing the maximization over next nodes by the selected next node for each specified next node mapping.

Upper bounds such as QMDP and FIB can be further improved by creating an augmented POMDP [Hauskrecht, 2000; Poupart et al., 2011a]. The idea is to augment the state space with belief points to create a larger POMDP. If we treat all reachable beliefs as states, the augmented POMDP becomes a belief state MDP that can be solved exactly by MDP techniques. QMDP and FIB then return tight upper bounds that correspond exactly to the optimal value function. Since it is not practical to treat all reachable beliefs as states, we only consider a subset of reachable beliefs, which yield an augmented POMDP somewhere between the original POMDP and the belief state MDP. Although the QMDP and FIB upper bounds won't be tight, they will be tighter than for the original POMDP. The combination of FIB with an augmented POMDP currently yields the lowest known upper bounds for many POMDPs [Poupart et al., 2011a]. We use the same approach as in the gapMin solver [Poupart et al., 2011a] to select the belief points and create the augmented POMDP.

5.2 Variable and Value Ranking

The order in which variables and values are selected for assignment can greatly influence the amount of search. If we make good assignments initially then we will quickly obtain a good controller with a high lower bound, allowing us to prune more aggressively in the rest of the search. We propose to rank variables according to their occupancy frequencies. Intuitively, the more often a node or an edge is visited, then the more critical it will be to set it properly. Hence, we rank the unassigned variables in decreasing order of occupancy frequency and select the one with highest frequency. Occupancy frequencies are estimated by performing a simulation of the controller and recording how often each node and each edge is visited. When the simulation reaches an unassigned node or edge in a partial controller, the best action or best next node according to the FIB upper bound is assumed. This allows us to simulate the specified and unspecified parts of a controller.

Values are ranked based on their expected utility. For instance, when instantiating a node with an action, we select actions in decreasing order of expected utility measured by the upper bound at the belief corresponding to the normalized state occupancy frequency of the node. Let b(s) be the belief proportional to the state occupancy frequency at node n. We then rank actions according to ∑s b(s) ¯Q(n, s, a). Similarly, when assigning an edge to a node, we select nodes in decreasing order of expected utility measured by the upper bound. Again, let b(s) be the belief proportional to the state occupancy at node n. We then compute the reachable belief b(s′ ) ∝ ∑s b(s) Pr(s′ |s, φ(n)) Pr(o|s, φ(n)) and rank next nodes n′ according to ∑s′ b(s′ ) ¯Q(n′ , s′ , φ(n′ )).

5.3 Observation Aggregation

The size of the controller greatly influences the amount of search because it determines the number of variables. While we bound the number of nodes, most of the variables in the search correspond to edges instead of nodes since there are |O| edges for each node. As a result, problems with many observations tend to have a search space that is intractable, even when the number of nodes is small. We propose to bound the number of edges. More precisely, we propose to merge several edges together in a way that only a bounded number of edge groups need to be instantiated. Grouping edges really corresponds to merging observations. We show that for several benchmarks, merging observations by grouping edges does not hurt the performance in the sense that a good controller can still be found while cutting the search space.

Hoey et al. [2005] demonstrated that observations can be merged without any loss as long as they do not lead to different decisions. In a controller, observations label edges which are used to decide which conditional plan will be executed next. If a problem has more observations than the number of nodes, then observations will be partitioned into at most |N| groups. In practice, the optimal controller will often have fewer than |N| observation groups per node since the graph is often sparse (i.e., each node links to only a few nodes).

We propose to bound the number of edge groups (and therefore observation groups). Let |E| be the maximum number of edge groups. We propose to instantiate |E| - |N| individual edges as usual. Then |N| edge groups are formed by grouping together all unassigned edges for each node. The edges in a group will be instantiated to the same value simultaneously, which reduces the amount of search. Since edges are instantiated in decreasing order of occupancy frequency, the remaining edges that are grouped together at each node are the ones with the lowest occupancy frequency and therefore the loss of accuracy due to grouping should be small.

6 Experiments

We compare Meuleau's search technique with our improved branch and bound with and without pruning equivalent controllers as well as three optimization techniques for stochastic controllers: bounded policy iteration (BPI) with escape [Poupart and Boutilier, 2003], quadratically constrained linear programming (QCLP) [Amato et al., 2009], expectation maximization (EM) with forward search [Poupart et al., 2011b]. The experiments are conducted with some benchmark problems and a real-world wayfinding POMDP that runs on a mobile phone.

6.1 LaCasa Domain

Wandering is a common behavior among people with dementia (PwD). It is also one of the main concerns of caregivers since it can cause the person to get lost and injured. The frequency and manner in which a person wanders is highly influenced by the person's background and contextual factors specific to the situation. We developed a POMDP model for a mobile application called "LaCasa" [Hoey et al., 2012] that estimates the risk faced by the PwD and decides on the appropriate action to take, such as prompting the PwD or calling the caregiver. Contextual information gathered from sensors is integrated into the model, including current location, battery power, and proximity to the caregiver. The system can reason about the costs of sensors (e.g. battery charge) and the relative costs of different types of assistance. A preliminary version of the system has been instantiated in a wandering assistance application for mobile devices running on an Android platform. However, in the current system, the necessary POMDP belief updates and policy queries are computationally too demanding and are done on a remote server that communicates with the smartphone using simple XML messages. This is a problem since the server communications can be expensive battery-wise, and rely on a data connection. The FSCs we find using the method proposed in this paper alleviate this problem, allowing the policy to run directly and cheaply on the smartphone. Additionally, it is not necessarily the case that persons with dementia will be able to carry a smartphone, and may require a much smaller, embedded or wearable device. In such cases, the memory and computation power available becomes a more serious constraint, making the use of FSCs imperative. We experimented with three LaCasa versions of different sizes-initially designed with our technique [Grze´s et al., 2013] for engineering POMDPs.

6.2 Results

Table 1 summarizes the results. The branch and bound (B&B) techniques find FSCs with highest value V (b0) for a fixed number of nodes and close to the upper bound computed by GapMin [Poupart et al., 2011a]. For our improved B&B with and without pruning, the number of edge groups is bounded as indicated in the column #edges. This did not diminish the value of the controllers found except for lacasa3-ext. #evals indicates the number of (partial) controllers that were evaluated to complete the search. Although the controllers are small, the search space is huge. Meuleau's B&B was not able to complete the search within 72 hours for most problems. Our improved B&B with tighter upper bounds and prioritized variable/value selection significantly reduced the search and an additional reduction was achieved by pruning equivalent controllers. BPI, QCLP and EM search in the space of stochastic controllers and therefore have an advantage since the best stochastic controller of a given size may have higher value than the best deterministic controller of the same size. Nevertheless, they are prone to local optima and as a result they found controllers with lower average value than B&B.

While our approach clearly improves the state of the art for B&B, the time taken to find a controller is still significantly higher than the time taken by search techniques for stochastic controllers, point-based techniques and online search techniques. However, as illustrated with the LaCasa domain, there is a need for techniques that can reliably find good controllers that can be executed with minimal online computation. In these cases, the additional offline cost to find the controller is acceptable and worthwhile.

7 Conclusion

This work shows how to improve branch and bound by using tighter bounds, prioritizing the selection of variables/values, bounding the number of edge groups and pruning equivalent controllers. The controllers that we considered in this work are Moore automata. In the future, it would be interesting to extend this work to Mealy automata [Amato et al., 2010] which can encode the same policies as Moore automata with fewer nodes, but more parameters (since the action mapping depends on nodes and observations instead of nodes only).

Acknowledgments

This work was supported by the Ontario Ministry of Research and Innovation, NSERC, Toronto Rehabilitation Institute and the Alzheimer's Association grant ETAC-10-173237.