Title: PERCEPTION-AWARE POINT-BASED VALUE ITERATION FOR PARTIALLY OBSERVABLE MARKOV DECISION PROCESSES

Abstract: Partially observable Markov decision processes (POMDPs) are a widely-used framework to model decision-making with uncertainty about the environment and under stochastic outcome. In conventional POMDP models, the observations that the agent receives originate from fixed known distribution. However, in a variety of real-world scenarios the agent has an active role in its perception by selecting which observations to receive. Due to combinatorial nature of such selection process, it is computationally intractable to integrate the perception decision with the planning decision. To prevent such expansion of the action space, we propose a greedy strategy for observation selection that aims to minimize the uncertainty in state. We develop a novel point-based value iteration algorithm that incorporates the greedy strategy to achieve near-optimal uncertainty reduction for sampled belief points. This in turn enables the solver to efficiently approximate the reachable subspace of belief simplex by essentially separating computations related to perception from planning. Lastly, we implement the proposed solver and demonstrate its performance and computational advantage in a range of robotic scenarios where the robot simultaneously performs active perception and planning.

1. INTRODUCTION:

In the era of information explosion it is crucial to develop decision-making platforms that are able to judiciously extract useful information to accomplish a defined task. The importance of mining useful data appears in many applications including artificial intelligence, robotics, networked systems and Internet of things. Generally in these applications, a decision-maker, called an agent, must exploit the available information to compute an optimal strategy toward a given objective.

Partially observable Markov decision processes (POMDPs) provide a framework to model sequential decision-making with partial perception of the environment and under stochastic outcomes. The flexibility of POMDPs and their variants in modeling real-world problems has led to extensive research on developing efficient algorithms for finding near-optimal policies. Nevertheless, the majority of previous work on POMDPs either deal with sole perception or sole planning.

While independent treatment of perception and planning deteriorates performance, an integrated approach usually becomes computationally intractable. Thereupon, one must establish a trade-off between optimality and tractability when determining how much perception and planning rely on each other. We show that by restricting the perception to the class of subset selection problems and exploiting submodular optimization techniques, it is possible to partially decouple computing perception and planning policies while considering their mutual effect on the overall policy value.

In this work, we consider joint perception and planning in POMDPs. More specifically, we consider an agent that decides about two sets of actions; perception actions and planning actions. The perception actions, such as employing a sensor, only affect the belief of the agent regarding the state of the environment. The planning actions, such as choosing navigation direction, are the ones that affect the transition of the environment from one state to another. In subset selection problems, at each time step, due to power, processing capability, and cost constraints, the agent can pick a subset of available information sources along a planning action. The subset selection problem arise in various applications in control systems and signal processing, in wireless sensor networks, as well as machine learning (Hashemi et al., 2018) and have been widely-studied (Shamaiah et al., 2010; Krause & Guestrin, 2007) . However, the previous work on sensor selection problems assume that the planning strategy is known, while in this work, we simultaneously learn a selection strategy and a planning strategy.

1.1. RELATED WORK:

Exact POMDP solvers optimize the value function over all reachable belief points. However, finding exact solution to POMDPs is PSPACE-complete (Papadimitriou & Tsitsiklis, 1987) which deems solving even small POMDPs computationally intractable. This has led to extensive search for nearoptimal algorithms. A common technique is to sample a finite set of belief points that approximate the reachable subspace of belief and apply value iteration over this set, e.g., (Sondik, 1978; Cheng, 1988; Lovejoy, 1991; Zhang & Zhang, 2001; Spaan & Vlassis, 2005; Pineau et al., 2006) . Pineau et al. (2006) proved that the errors due to belief sampling is bounded where the bound depends on the density of the belief set. A well-established offline POMDP solver is SARSOP (Kurniawati et al., 2008) . SARSOP, similar to HSVI (Smith & Simmons, 2012) , aims to minimize the gap between the lower and upper bounds on the value function by guiding the sampling toward the belief points that are reachable under union of optimal policies. In this paper, we show that the proposed greedy observation selection scheme leads to belief points that are on expectation close to the ones from the optimal (with respect to uncertainty reduction) set of observations, and hence value loss is small. An instance of active perception is dynamic sensor selection. Kreucher et al. (2005) proposes a reinforcement learning approach that uses Rènyi divergence to compute utility of sensing actions. Joshi & Boyd (2009) formulated a single step sensor selection problem as semi-definite programming, however, it lacks theoretical guarantee. In Kalman filtering setting, Shamaiah et al. (2010) developed a greedy selection scheme with near-optimal guarantee to minimize log-determinant of the error covariance matrix of estimated state. Some prior work such as (Spaan, 2008; Spaan & Lima, 2009; Natarajan et al., 2015) model active perception as a POMDP. However, the most relevant work to ours are that of (Araya et al., 2010; Spaan et al., 2015; Satsangi et al., 2018) . Araya et al. (2010) proposed ρPOMDP framework where the reward depends on entropy of the belief. Spaan et al. (2015) introduced POMDP-IR where the reward depends on accurate prediction about the state. Satsangi et al. (2018) established an equivalence property between ρPOMDP and POMDP-IR. Furthermore, they employed the submodularity of value function, under some conditions, to use greedy scheme for sensor selection. The main difference of our work is that we consider active perception as a means to accomplishing the original task while in these work, the active perception is the task itself and hence the POMDP rewards are metrics to capture perception quality.

The problem of selecting an optimal set of sensors from a ground set under cardinality constraint is NP-hard (Williams & Young, 2007) . This hardness result has motivated design of greedy algorithms since they make polynomial oracle calls to the objective function. Additionally, if the objective function is monotone non-decreasing and submodular, Nemhauser et al. (1978) showed that a greedy selection achieves (1 -1/e) approximation factor. Mirzasoleiman et al. (2015) and Hashemi et al. (2018) developed randomized greedy schemes that accelerate the selection process for monotone submodular and weak-submodular objective functions, respectively. Krause & Guestrin (2007) ; Krause & Golovin (2014) have introduced different submodular information-theoretic objectives for greedy selection and have studied the theoretical guarantees of their maximization under different constraints. Here, we use the entropy of belief to capture the level of uncertainty in state and aim to select a subset of sensors that leads to maximum expected reduction in entropy. We employ the monotonicity and submodularity of the proposed objective to establish near-optimal approximation factor for entropy minimization.

1.2. CONTRIBUTIONS:

A summary of our contributions are as follows:

• Formulating the active perception problem for POMDPs: We introduce a new mathematical definition of POMDPs, called AP 2 -POMDP, that captures active perception as well as planning. The objective is to find deterministic belief-based policies for perception and planning such that the expected discounted cumulative reward is maximized.

• Developing a perception-aware point-based value iteration algorithm: To solve AP 2 -POMDP, we develop a novel point-based method that approximates the value function using a finite set of belief points. Each belief point is associated with a perception action and a planning action. We use the near-optimal guarantees for greedy maximization of monotone submodular functions to compute the perception action while the planning action is the result of Bellman optimality equation. We further prove that greedy perception action leads to an expected reward that is close to that of optimal perception action.

2. PROBLEM FORMULATION:

This section starts by giving an overview of the related concepts and then stating the problem.

2.1. PRELIMINARIES:

The standard POMDP definition models does not capture the actions related to perception. We present a different definition which we call AP 2 -POMDP as it models active perception actions as well as original planning actions. The active perception actions determine which subset of sensors (observations) the agent should receive. We restrict the set of states, actions, and observations to be discrete and finite.

2.1.1. POMDP WITH PERCEPTION ACTION:

We formally define an AP 2 -POMDP below. Definition 1. An AP 2 -POMDP is a tuple P = (S, A, k, T, Ω, O, R, γ), where

• S is the finite set of states.

• A = A pl × A pr is the finite set of actions with A pl being the set of planning actions and A pr being the set of perception actions. A pr = {δ ∈ {0, 1} n | |δ| 0 ≤ k} constructs an n-dimensional lattice. Each component of an action δ ∈ A pr determines whether the corresponding sensor is selected.

• k is the maximum number of sensor to be selected.

• T : S × A pl × S → [0, 1] is the probabilistic transition function.

• Ω = Ω 1 × Ω 2 × . . . × Ω n is the partitioned set of observations, where each Ω i corresponds to the set of measurements observable by sensor i. 1] is the probabilistic observation function.

• O : S × A × Ω → [0,

• R : S × A pl → R is the reward function, and

• γ ∈ [0, 1] is the discount factor.

At each time step, the environment is in some state s ∈ S. The agent takes an action β ∈ A pl that causes a transition to a state s ∈ S with probability P r(s |s, β) = T (s, β, s ). At the same time step, the agent also picks k sensors by δ ∈ A pr . Then it receives an observation ω ∈ Ω with probability P r(ω|s , β, δ) = O(s , β, δ, ω), and a scalar reward R(s, β). Assumption 1. We assume that the observations from sensors are mutually independent given the current state and the previous action, i.e., ∀I 1 , I 2 ⊆ {1, 2, . . . , n}, I 1 ∩ I 2 = ∅ : P r( i1∈I1 ω i1 , i2∈I2 ω i2 |s, β) = P r( i1∈I1 ω i1 |s, β)P r( i2∈I2 ω i2 |s, β).

Let ζ(δ) = {i|δ(i) = 1} to denote the subset of sensors that are selected by δ. If Assumption 1 holds, then:

EQUATION

where P r(ω i |s , β) = O i (s , β, ω i ).

The belief of the agent at each time step, denoted by b t is the posterior probability distribution of states given the history of previous actions and observations, i.e., h t = (a 0 , ω 1 , a 1 , . . . , a t-1 , ω t ).

A well-known fact is that due to Markovian property, a sufficient statistics to represent history of actions and observations is belief ( Åström, 1965; Smallwood & Sondik, 1973) 

= i∈ζ(δ) O i (s , β, ω i ) s T (s, β, s )b(s) s i∈ζ(δ) O i (s , β, ω i ) s T (s, β, s )b(s)

.

(

EQUATION

The goal is to learn a deterministic policy to maximize E[

∞ t=0 γ t R(s t , β t )|b 0 ].

A deterministic policy is a mapping from belief to actions π : B → A, where B is the set of belief states. Note that B constructs a (|S| -1)-dimensional probability simplex.

The POMDP solvers apply value iteration (Sondik, 1978) , a dynamic programming technique, to find the optimal policy. Let V be a value function that maps beliefs to values in R. The following recursive expression holds for V :

V t (b) = max a s∈S b(s)R(s, a) + γ ω∈Ω P r(ω|b, a)V t-1 (b a,ω b

) .

(3)

The value iteration converges to the optimal value function V * which satisfies the Bellman's optimality equation (Bellman, 1957) . Once the optimal value function is learned, an optimal policy can be derived. An important outcome of ( 3) is that at any horizon, the value function is piecewise-linear and convex (PWLC) (Smallwood & Sondik, 1973) and hence, can be represented by a finite set of hyperplanes. Each hyperplane is associated with an action. Let α's to denote the corresponding vectors of the hyperplanes and let Γ t to be the set of α vectors at horizon t. Then,

EQUATION

This fact has motivated approximate point based solvers that try to approximate the value function by updating the hyperplanes over a finite set of belief points.

2.1.2. SUBMODULARITY:

Since the proposed algorithm is founded upon the theoretical results from the field of submodular optimization, here, we overview the necessary definitions. Let X to denote a ground set and f a set function that maps an input set to a real number.

Definition 2. Set function f : 2 X → R is monotone nondecreasing if f (T 1 ) ≤ f (T 2 ) for all T 1 ⊆ T 2 ⊆ X . Definition 3. Set function f : 2 X → R is submodular if f (T 1 ∪ {i}) -f (T 1 ) ≥ f (T 2 ∪ {i}) -f (T 2 ) for all subsets T 1 ⊆ T 2 ⊂ X and i ∈ X \T 2 . The term f i (T 1 ) = f (T 1 ∪ {i}) -f (T 1 ) is the marginal value of adding element i to set T 1 .

Monotonicity states that adding elements to a set increases the function value while submodularity refers to diminishing returns property.

2.2. PROBLEM DEFINITION:

Having stated the required background, next, we state the problem. Problem 1. Consider a AP 2 -POMDP P = (S, A, k, T, Ω, O, R, γ) and an initial belief b 0 . We aim to learn a policy π(b) = (β, δ) such that the expected discounted cumulative reward is maximized, i.e, It is worth noting that the perception actions affect the belief and subsequently the received reward in the objective function.

EQUATION

3. ACTIVE PERCEPTION WITH GREEDY SCHEME:

For variety of performance metrics, finding an optimal subset of sensors poses a computationally challenging combinatorial optimization problem that is NP-hard. Augmenting POMDP planning actions with n k active perception actions results in a combinatorial expansion of the action space. Thereupon, it is infeasible to directly apply existing POMDP solvers to Problem 1. Instead of concatenating both sets of actions and treating them similarly, we propose a greedy strategy for selecting perception actions that aims to pick the sensors that result in minimal uncertainty about the state.

The key enabling factor is that the perception actions does not affect the transition, consequently, we can decompose the single-step belief update in (2) into two steps:

EQUATION

EQUATION

)

This in turn implies that after a transition is made, the agent should pick a subset of observations that lead to minimal uncertainty in b δ,ω b .

To quantify uncertainty in state, we use Shannon entropy of the belief. For a discrete random variable x, the entropy is defined as H(x) =i p(x i ) log p(x i ). An important property of entropy is its strict concavity on the simplex of belief points, denoted by ∆ B (Cover & Thomas, 2012) . Further, the entropy is zero at the vertices of ∆ B and achieves its maximum, log |S|, at the center of ∆ B that corresponds to uniform distribution, i.e., when the uncertainty about the state is the highest. Figure 1 demonstrates the entropy and its level sets for |S| = 3. Since the observation values are unknown before selecting the sensors, we optimize conditional entropy that yields the expected value of entropy over all possible observations. For discrete random variables x and y, conditional entropy is defined as

H(x|y) = E y [H(x|y)] = i p(y i )H(x|y i ).

Subsequently, with some algebraic manipulation, it can be shown that the conditional entropy of state given current belief with respect to δ is:

EQUATION

where

ζ(δ) = {i 1 , i 2 , . . . , i k }.

It is worth mentioning that b is the current distribution of s and is explicitly written only for the purpose of better clarity, otherwise, H(s|b, δ) = H(s|δ).

To minimize entropy, we define the objective function as the following set function:

f (ζ) = H(s| bβ b ) -H(s| bβ b , i∈ζ ω i ) (8)

and the optimization problem as:

EQUATION

We propose a greedy algorithm, outlined in Algorithm 1 to find a near-optimal, yet efficient solution to (9). The algorithm takes as input the agent's belief and planning action. Then it iteratively adds elements from the ground set (set of all sensors) whose marginal gain with respect to f is maximal and terminates when k observations are selected.

Algorithm 1 Greedy policy for perception action 

j * = argmax j∈X \ζ -H(s| bβ b , i∈ζ∪{j} ω i ) 6: ζ ← ζ ∪ {j * } 7: end for 8: return δ corresponding to ζ.

Next, we derive a theoretical guarantee for the performance of the proposed greedy algorithm. The following lemma states the required properties to prove the theorem. The proof of the lemma follows from monotonicity and submodularity of conditional entropy (Ko et al., 1995) . See the appendix for the complete proof. Lemma 1. Let Ω = {ω 1 , ω 2 , . . . , ω n } to represent a set of observations of the state s that conditioned on the state, are mutually independent (Assumption 1 holds). Then, f (ζ), defined in (8), realizes the following properties:

1. f (∅) = 0,

2. f is monotone nondecreasing, and 3. f is submodular.

The above lemma enables us to establish the approximation factor using the classical analysis in (Nemhauser et al., 1978) . Theorem 1. Let ζ * to denote the optimal subset of observations with regard to objective function f (ζ), and ζ g to denote the output of the greedy algorithm in Algorithm 1. Then, the following performance guarantee holds: Sondik, 1978) , this in turn implies that the agent is moving toward regions of belief space that have higher value.

EQUATION

Although Theorem 1 proves that the entropy of the belief point achieved by the greedy algorithm is close to the entropy of the belief point from the optimal solution, the key question is whether the value of these points are close. We assess this question in the following and show that at each time step, on expectation, the value from greedy scheme is close to the value from optimal observation selection with regard to (9). To that end, we first show that the distance between the two belief points is upper-bounded. Thereafter, using a similar analysis as that of Pineau et al. (2006) , we conclude that the difference between value function at these two points is upper-bounded. Theorem 2. Let the agent's current belief to be b and its planning action to be β. Consider the optimization problem in (9), and let δ * and δ g to denote the optimal perception action and the perception action obtained by the greedy algorithm, respectively. It holds that: 1 . Theorem 3. Instate the notation and hypothesis of Theorem 2. Additionally, let V to be the true value function for AP 2 -POMDP. The following statement holds:

E[ b g -b * 1 ] ≤ C 1 ,

E[V (b g ) -V (b * )] ≤ C 2 .

Proof. The proof is omitted for brevity. See the appendix for the proof.

4. PERCEPTION-AWARE POINT-BASED VALUE ITERATION:

In this section, we propose a novel point-based value iteration algorithm to approximate the value function for AP 2 -POMDPs. The algorithm relies on the performance guarantee of the proposed greedy observation selection in previous section. Before describing the new point-based solver, we first overview how point-based solvers operate. Algorithm 2 outlines the general procedure for a point-based solver. It starts with an initial set of belief points B 0 and their corresponding α vectors. Then it performs a Bellman backup for each point to update α vectors. Next, it prunes α vectors to remove dominated ones. Afterwards, it samples a new set of belief points and repeats these steps until convergence or other termination criteria is met. The difference between solvers is in how they apply sampling and pruning. The sampling step usually depends on the reachability tree of belief space, see Figure 2 . The state-of-the-art point-based methods do not traverse the whole reachability tree, but they try to have enough sample points to provide a good coverage of the reachable space.

Algorithm 2 Generic algorithm for point-based solvers (Araya et al., 2010) 1: Input: POMDP. Note that the combinatorial number of actions due to observation selection highly expand the size of the reachability tree. To avoid dealing with perception actions in the reachability tree, we apply the greedy scheme to make the choice of δ deterministically dependent on β and previous belief. To that end, we modify the BackUp step of point-based value iteration. The proposed BackUp step can be combined with any sampling and pruning method in other solvers, such as the ones developed by Spaan & Vlassis (2005); Kurniawati et al. (2008) ; Smith & Simmons (2012) .

4.1. PROPOSED POINT-BASED SOLVER:

In point-based solver each witness belief point is associated with an α vector and an action. Nevertheless, for AP 2 -POMDPs, each witness point is associated with two actions, β and δ. We compute δ based on greedy maximization of (9) so that given b and β, δ is uniquely determined. Henceforth, we can rewrite (3) using ( 4) to obtain:

V t (b) = max (β,δ) s∈S b(s)R(s, β) + γ ω∈Ω P r(ω|b, β, δ) max α∈Γt-1 α.b β,δ,ω b = max β s∈S b(s)R(s, β)+ ω∈Ω i 1 ×...×Ω i k ij ∈ζ( δ) max α∈Γt-1 s ∈S α(s ) × ij ∈ζ( δ) O i (s , β, ω ij ) s∈S T (s, β, s )b(s) = max β s∈S b(s)R(s, β)+ ω∈Ω i 1 ×...×Ω i k ij ∈ζ( δ) max α∈Γt-1 s∈S s ∈S α(s ) × ij ∈ζ( δ) O i (s , β, ω ij )T (s, β, s )b(s) .

where δ = argmax δ∈A pr f (ζ(δ)) and f is computed at bβ b . This way, we can partially decouple the computation of perception action from the computation necessary for learning the planning policy.

Inspired by the results in the previous section, we propose the BackUp step detailed in Algorithm 3 to compute the new set of α vectors from the previous ones using Bellman backup operation. What distinguishes this algorithm from conventional Bellman backup step is the inclusion of perception actions. Basically, we need to compute the greedy perception action for each belief point and each action (Line 7). This in turn affects computation of Γ b,β,ω t as it represents a different set for each belief point (Lines 9-13). However, notice that this added complexity is significantly lower than concatenating the combinatorial perception actions with the planning actions and using conventional point-based solvers. See the appendix for detailed complexity analysis.

5. SIMULATION RESULTS:

To evaluate the proposed algorithm for active perception and planning, we developed a point-based value iteration solver for AP 2 -POMDPs. We initialized the belief set by uniform sampling from ∆ B (Devroye, 1986) . To focus on the effect of perception, we did not apply a sampling step, i.e, the belief set is fixed throughout the iterations. However, one can integrate any sampling method such as the ones proposed by Smith & Simmons (2012) ; Kurniawati et al. (2008) . The α vectors are initialized by 1 1-γ min s,a R(s, a).Ones(|S|) (Shani et al., 2013) . Furthermore, to speedup the solver, one can employ a randomized backup step, as suggested by Spaan & Vlassis (2005) . The solver terminates once the difference between value functions in two consecutive iterations falls below a predefined threshold. We also implemented a random perception policy that selects a subset of information sources, uniformly at random, at each backup step. We implemented the solver in Python 2.7 and ran the simulations on a laptop with 2.0 GHz Intel Core i7-4510U CPU and with 8.00 GB RAM.

5.1. ROBOTIC NAVIGATION IN 1-D GRID:

The first scenario models a robot that is moving in a 1-D discrete environment. The robot can only move to adjacent cells and its navigation actions are A pl = {lef t, right, stop}. The robot's transitions are probabilistic due to possible actuation errors. The robot does not have any sensor and it relies on a set of cameras for localization. There is one camera at each cell that outputs a probability Algorithm 3 BackUp step for AP 2 -POMDP Figure 3 : The robot moves in a grid while communicating with the cameras to localize itself. There is a camera at each state on the perimeter. The accuracy of measurements made by each camera depends on the distance of the camera from that state. The robot's objective is to reach the goal state, labeled by star, while avoiding the obstacles.

1: Input: AP 2 -POMDP P = (S, A, k, T, Ω, O, R, γ), Current set of belief points B t , Current set of α vectors Γ t-1 . 2: Output: Next set of α vectors Γ t . 3: Initialize Γ t = ∅, Γ b,β t = ∅ for all b ∈ B t and β ∈ A pl . 4: for β ∈ A pl do 5: Γ β, * t ← α β, * (s) = R(s, β) 6: for b ∈ B t do 7: δ = Greedy argmax δ∈A pr f (ζ(δ)) 8: Γ b,β,ω t = ∅ 9: for ω ∈ Ω i1 × . . . × Ω i k , i j ∈ ζ( δ) do 10: for α ∈ Γ t-1 do 11: α b,β,ω (s) = γ s ∈S ij ∈ζ( δ) O i (s , β, ω ij )T (s, β, s )α(s ) 12: Γ b,β,ω t ← Γ b,β,ω t ∪ α b,β,ω

distribution over the position of the robot. The camera's certainty is higher when the robot's position is close to it. To model the effect of robot's position on the accuracy of measurements, we use a binomial distribution with its mean at the cell that camera is on. The binomial distribution represents the state-dependent accuracy. The robot's objective is to reach an specific cell in the map. For that purpose, at each time step, the robot picks a navigation action and selects k camera from the set of n cameras.

After the solver terminates, we evaluate the computed policy. To that end, we run 1000 iterations of Monte Carlo simulations. The initial state of the robot is the origin of the map and its initial belief is uniform over the map. entropy of greedy perception, compared to random perception, shows less uncertainty of the robot when taking planning actions. See the appendix for further results.

5.2. ROBOTIC NAVIGATION IN 2-D GRID:

The second setting is a variant of first scenario where the map is 2-D. Therefore the navigation actions of robot are A pl = {up, right, down, lef t, stop}. The rest of the setting is similar to 1-D case, except the cameras' positions, as they are now placed around the perimeter of the map. Additionally, the robot has to now avoid the obstacles in the map. The reward is 10 at the goal state.

-4 at the obstacles, and -1 in other states.

We applied the proposed point-based solver with both random perception and greedy perception on the 2-D example. Next, we let the robot to run for a horizon of 25 steps and we terminated the simulations once the robot reached the goal. Figure 5 illustrates the normalized frequency of visiting each state for each perception algorithm. It can be seen that the policy learned by greedy active perception leads to better obstacle avoidance. See the appendix for further results.

6. CONCLUSION:

In this paper, we studied joint active perception and planning in POMDP models. To capture the structure of the problem, we introduced AP 2 -POMDPs that have to pick a cardinality-constrained subset of observations, in addition to original planning action. To tackle the computational challenge of adding combinatorial actions, we proposed a greedy scheme for observation selection. The greedy scheme aims to minimize the conditional entropy of belief which is a metric of uncertainty about the state. We provided a theoretical analysis for the greedy algorithm that led to boundedness of value function difference between optimal entropy reduction and its greedy counterpart. Furthermore, founded upon the theoretical guarantee of greedy active perception, we developed a point-based value iteration solver for AP 2 -POMDPs. The idea introduced in the solver to address active perception is general and can be applied on state-of-the-art point-based solvers. Lastly, we implemented and evaluated the proposed solver on a variety of robotic navigation scenarios.

Proof. Notice that bβ b is explicitly present to determine the current distribution of s and it is not a random variable. Therefore, for simplicity, we omit that in the following proof. It is clear that

f (∅) = H(s| bβ b ) -H(s| bβ b ) = 0. Let [n] = {1, 2, . . . , n}. To prove the monotonicity, consider ζ 1 ⊂ [n] and j ∈ [n]\ζ 1 . Then, H(s| i∈ζ1∪{j} ω i ) (a) = H( i∈ζ1∪{j} ω i |s) + H(s) -H( i∈ζ1∪{j} ω i ) (b) =H( i∈ζ1 ω i |s) + H(ω j |s) + H(s) -H( i∈ζ1 ω i ) -H(ω j | i∈ζ1 ω i ) (c) = H(s| i∈ζ1 ω i ) + H(ω j |s) -H(ω j | i∈ζ1 ω i ) (d) = H(s| i∈ζ1 ω i ) + H(ω j |s, i∈ζ1 ω i ) -H(ω j | i∈ζ1 ω i ) (e) ≤ H(s| i∈ζ1 ω i ) + H(ω j | i∈ζ1 ω i ) -H(ω j | i∈ζ1 ω i ) =H(s| i∈ζ1 ω i ),

where (a) and (c) are due to Bayes' rule for entropy, (b) follows from the conditional independence assumption and joint entropy definition, (d) is due to the conditional independence assumption, and (e) stems from the fact that conditioning does not increase entropy. The monotonicity of the objective function means that if the number of obtained observations are higher, the conditional entropy will be lower, and hence, on expectation, the uncertainty in the state will be lower.

Furthermore, from the third line of above proof, we can derive the marginal gain, i.e., the value of adding one sensor, as:

f j (ζ 1 ) = H(s| i∈ζ1 ω i ) -H(s| i∈ζ1∪{j} ω i ) = H(ω j | i∈ζ1 ω i ) -H(ω j |s) To prove submodularity, let ζ 1 ⊆ ζ 2 ⊂ [n] and j ∈ [n]\ζ 2 . Then, f j (ζ 1 ) = H(ω j | i∈ζ1 ω i ) -H(ω j |s) (a) ≥ H(ω j | i∈ζ1∪(ζ2\ζ1) ω i ) -H(ω j |s) (b) = H(ω j | i∈ζ2 ω i ) -H(ω j |s) = f j (ζ 2 ),

where (a) is based on the fact that conditioning does not increase entropy, and (b) results from ζ 1 ⊆ ζ 2 . The submodularity (diminishing returns property) of objective function indicates that as the number of obtained observations increases, the value of adding a new observation will decrease.

In the next theorem, we exploit the properties of the proposed objective function to analyze the performance of the greedy scheme.

Theorem 1. Let ζ * to denote the optimal subset of observations with regard to objective function f (ζ), and ζ g to denote the output of the greedy algorithm in Algorithm 1. Then, the following performance guarantee holds:

EQUATION

Proof. The properties of f stated in Lemma 1 along the theoretical analysis of greedy algorithm by Nemhauser et al. (1978) yields

f (ζ g ) ≥ (1 - 1 e )f (ζ * ).

Using the definition of f (ζ) and rearranging the terms, we obtain the desired result.

PROOF OF THEOREM 2:

Before stating the proof to Theorem 2, that bounds the distance of belief points from the greedy and optimal entropy minimization algorithms, we need to present a series of propositions and lemmas.

Mutual information between two random variables is a positive and symmetric measure of their dependence and is defined as:

I(x; y) =

x,y p x,y (x, y) log p x,y (x, y) p x (x)p y (y) .

Mutual information, due to its monotonicity and submodularity, has inspired many subset selection algorithms (Krause & Golovin, 2014) . In the following proposition, we express the relation between conditional entropy and mutual information. Proposition 1. Minimizing conditional entropy of the state with respect to a set of observations is equivalent to maximizing the mutual information of state and the set of observations. This equivalency is due to the definition of mutual information, i.e.,

I(s;:

i∈ζ

EQUATION

and the fact that H(s) is computed at bβ b which amounts to a constant value that does not affect selection procedure. Additionally, notice that (12) is the same as the definition of normalized objective function of greedy algorithm in (8).

Another closely-related information-theoretic concept is Kullback-Leibler (KL-) divergence. The KL-divergence, also known as relative entropy, is a non-negative and non-symmetric measure of difference between two distributions. The KL-divergence from q(x) to p(x) is:

D KL (p x q x ) = x p x (x) log p x (x) q x (x) .

The following relation between mutual information and KL-divergence exists: which allows us to state the next proposition.

I(x; y) = x,y

Proposition 2. The mutual information of state and a set of observations is the expected value of the KL-divergence from prior belief to posterior belief over all realizations of observations, i.e.,

i∈ζ , ω ∼ i∈ζ * Ω i to denote prior belief (after taking planning action), posterior belief after greedy perception action, and posterior belief after optimal perception action, respectively. So far, we have established a relation between minimizing the conditional entropy of posterior belief and maximizing the expected KL-divergence from prior belief to posterior belief, i.e., D KL (p g p 0 ) (See Proposition 1 and Proposition 2). To relate D KL (p g p 0 ) and D KL (p g p * ), we state the next lemma. But first, we bring information-geometric definitions necessary for proving the lemma. Definition 4. Let p to be a probability distribution over a finite alphabet. An I-sphere with center p and radius ρ is defined as:

EQUATION

)

S(p, ρ) def = {q | D KL (q p) < ρ}. Definition 5. Let Λ to denote a convex set of probability distributions that intersect S(p, ∞). A q satisfying D KL (q p) def = min q∈Λ D KL (q p),

is called the I-projection of p on Λ. Lemma 2. Instate the definition of p 0 , p g , and p * . The following inequality holds on expectation:

D KL p 0 p * ≥ D KL p 0 p g + D KL (p g p * ) .

Proof. Consider the set Λ g = {p ∈ ∆ B |H(p) ≥ H(p g ) that contain probability distributions whose entropy is lower-bounded by entropy of p g . Since entropy is concave over ∆ B , its hypographs are convex. Consequently Λ g , the projection of a hypograph onto ∆ B , is a convex set. Furthermore, due to monotonicity of conditional entropy, i.e., expected value of entropy over observations, we know that p 0 ∈ Λ g . Besides, Due to optimality of ζ * , it holds that

H(s| bβ b , i∈ζ * ω i ) ≤ H(s| bβ b , i∈ζ g ω i )

which in turn yields p * ∈ ∆ B \Λ g . Figure 6 demonstrates these facts for an alphabet of size 3. p g is the I-projection of p * on Λ g . Therefore, by exploiting the analogue of Pythagoras' theorem for KL-divergence (Csiszár, 1975) , we conclude:

D KL p 0 p * ≥ D KL p 0 p g + D KL (p g p * ) .

A direct result of the above lemma, after taking the expectation over i∈[n] ω i , is:

EQUATION

In the following theorem, we use the stated lemma to bound the expected KL-divergence distance between greedy and optimal selection strategies. Theorem 4. The KL-divergence between p g and p * is upper-bounded, i.e.,

E i∈[n] ω i [D KL (p g p * )] ≤ C 3 , where C 3 is a constant.

Proof. Notice that while KL-divergence is not symmetric, the following fact still holds:

argmax ζ E i∈ζ ω i D KL (b δ,ω b bβ b ) = argmax ζ E i∈ζ ω i D KL ( bβ b b δ,ω b ) ,

whenever the distributions consist of only non-zero elements. Once the algorithm is initialized with belief points that are not on the boundary of the probability simplex, this condition will hold. Also, notice that

E i∈ζ * ω i D KL ( bβ b b δ,ω b

) is constant. Now, Lemma 2 along the near-optimality result of greedy algorithm for entropy minimization (See Theorem 1) yield the desired result.

Next, we bound the total variation distance between p g and p * . Definition 6. The total variation distance between two probability distributions p and q, over a countable state space S, is defined as:

TVD(p, q) = 1 2 s∈S |p(s) -q(s)|.

Pinsker's inequality bounds the total variation distance in terms of the KL-divergence (Cover & Thomas, 2012) . Using this inequality, we can prove Theorem 2. Theorem 2. Let the agent's current belief to be b and its planning action to be β. Consider the optimization problem in (9), and let δ * and δ g to denote the optimal perception action and the perception action obtained by the greedy algorithm, respectively. It holds that:

E[ b g -b * 1 ] ≤ C 1

, where b * and b g are the updated beliefs according to (6). Proof. Note that the total variation distance is half of the l 1 -norm. Hence,

EQUATION

≤ 2 E[ 

PROOF OF THEOREM 3:

In the next theorem, we use the bounded distance of belief points, obtained from the greedy and optimal entropy minimization algorithms to find an upper bound on the gap between the corresponding value functions. Theorem 3. Instate the notation and hypothesis of Theorem 2. Additionally, let V to be the true value function for AP 2 -POMDP. The following statement holds:

E[V (b g ) -V (b * )] ≤ C 2 .

Proof. We use the PWLC property of value function. Let α g and α * to represent the gradient of value function at b g and b * , respectively. Note that for every α vector, α ∞ ≤ max{|Rmax|,|Rmin|} 

COMPLEXITY ANALYSIS OF ALGORITHM 3:

In this section, we compare the computational complexity of a point-based value iteration method that works with the concatenated action space, with the computational complexity of the proposed point-based method that picks the perception actions based on a greedy approach.

First, we compute the computations required for a single backup step in the point-based method with concatenated action space. To that end, consider a fixed set of sampled belief points B. Let Γ to denote the current set of α vectors. Further, for the simplicity of analysis, assume that the number of possible observations from each information source is |Ω Hence, the proposed approach, as a result of exploiting the structure of action space, would lead to significant computational gain, especially for large n.

:



Figures and Tables:

. Given the initial belief b 0 , the following update equation holds between previous belief b and the belief b a,ω b after taking action a = (β, δ) and receiving observation ω: b a,ω b (s ) = P r (ω|s , β, δ) s P r(s |s, β)b(s) P r (ω|β, δ)

Figure 1: Entropy of belief for a 3-state POMDP.

Input: AP 2 -POMDP P = (S, A, k, T, Ω, O, R, γ), Current belief b, Planning action β. 2: Output: Perception action δ. 3: Initialize X = {1, 2, . . . , n}, ζ = ∅. 4: for l = 1, . . . , k do 5:

Intuitively, one can interpret the minimization of conditional entropy as pushing the agent's belief toward the boundary of the probability simplex ∆ B . Due to convexity of POMDP value function on ∆ B (

where b * and b g are the updated beliefs according to (6) and C 1 is a constant value.

Figure 2: The belief reachability tree. The circles are belief points while squares depict branchings based on actions. Addition of perception actions leads to combinatorial expansion of number of belief points in each layer.

2: Output: Approximate value function V . 3: Initialize B = B 0 and Γ 0 . 4: while ∼ (termination condition) do while 9: return V (b) = max α∈Γ α.b.

β = α β, * + ω∈Ω i 1 ×...×Ω i k ij ∈ζ( δ) argmax α∈Γ b,βfor 19: for b ∈ B t do 20: α b = argmax α∈Γ b,β t ,β∈A pl α.b 21: Γ t = Γ t ∪ α b 22: end for 23: return Γ t . (a) 1-D grid (b) 2-D grid

Figure 4: Results of 1-D simulation for a map of size 12, averaged over 1000 runs for each perception policy. Left: The average discounted cumulative reward. The solid lines depict the corresponding standard deviations. Right: The average belief entropy over the time horizon of 25.

E y [D KL (p x|y p x )],

bβ b is the prior belief before selecting observations and b δ,ω b is the posterior belief after selecting perception action δ and receiving the observations.

Figure 6: The probability simplex, ∆ B , for a 3-state POMDP. Gray area illustrates the projection of hypograph of entropy, corresponding to posterior belief after greedy perception action, onto ∆ B .

2C 3 , where (a) is the result of applying Pinsker's inequality, b is obtained by applying Jansen's inequality to concave square-root function, and (c) follows from Theorem 4. The proof completes by taking C 1 = √ 2C 3 .

R max = max s,β R(s, β) and R min = min s,β R(s, β). Therefore, we can show thatE[V (b g ) -V (b * )] = E[α g .b g -α * .b * ] = E[α g .b g -α g .b * + α g .b * -α * .b * ] (a) ≤ E[α g .b g -α g .b * + α * .b * -α * .b * ] = E[α g .(b g -b * )] (b) ≤ E[ α g ∞ b g -b * 1 ] (c) ≤ C 1 max {|R max |, |R min |} 1 -γ ,

Figure 7: Comparing random and greedy selection for 2-D robotic navigation in terms of the average belief entropy over the time horizon of 25.

i | = Ω, ∀i ∈ [n]. The cardinality of a concatenated action space is |A| = |A pr ||A pl | = n k |A pl |.Therefore, the complexity of a single backup step would be O( n k |A pl | × Ωn × |Γ| × |S| 2 + |B| × n k |A pl | × |S| × Ωn ) (Shaniet al.,  2013).On the other hand, applying greedy algorithm to pick a perception action requires O(n × k) calls to an oracle that computes the objective function (or equivalently, the marginal gain). Here the objective function is the conditional entropy whose complexity with a naive approach in the k th iteration is O( Ωk × |S| 2 ). Therefore, applying Algorithm 3 as the backup step leads to O(|A pl | × |B| × n × k × Ωk × |S| 2 + |A pl | × |B| × Ωk × |Γ| × |S| 2 + |B| × |A pl | × |S| × Ωk ) operations.

Peer review (iclr2019):
 This paper proposes a planning algorithm for a restricted class of POMDPs where the sensing decisions do not have any bearing on the hidden state evolution, or any material cost in terms of reward. A sensing decision consists of querying k out of n sensors which yield independent measurements of the hidden state. In this setting, the authors propose an optimization 2-stage optimization strategy, the first stage tries to find the optimal "planning" action in a point-based fashion, whereas the second aims to find the the sensor configuration that reduces the entropy of the post-update belief-state. The key observation is that the entropy minimization step is submodular and can be approximated greedily. This in turn translates to policy approximation bounds via information geometric arguments. The positive: the paper is well written (save for some contained parts), the algorithm looks to be generally sound. Altogether the paper makes good points and is an interesting read. The negative: * first, I think there is some wide-spread misuse of the term "nearly optimal". When talking about near-optimality, this usually refers to finding a (controllably) bounded approximation to the optimal policy/value function. However, here this refers to the error relative to the approximate solution produced by the 2-stage procedure of minimizing entropy, then making a planning decision. It is not clear to me to begin with that this approach would produce bounded policies/value functions. As a counter example, consider a state space consisting of two state variables S1, S2 which evolve independently with additive reward R(S1, a) + R(S2, a) with R(S1, a) !=0, while R(S2, a) = 0 for all actions a. Now, there could be a sensing configuration that collapses the uncertainty over S2 completely, but does nothing over S1, and a different one that give some small reduction of uncertainty over S1 and nothing over S2. The former may outperform the latter to any degree in terms of belief state entropy, but it will not lead to an optimal policy, since that entropy reduction is not value directed. Unless I misunderstand something, in which case the authors should clarify. * Second, the particular assumptions in this paper are quite restrictive. This paper generally reads like a solution that was fit to a problem. This really hurts the story of the paper. It would be a vast improvement if the authors could find at least one plausible problem where there*s a compelling case for this particular configuration of assumptions and try to evaluate how well they do on that problem relative to some reasonable baseline. Remarks: * The belief state notation used in this paper impacts undue suffering upon the reader. It comes in the form of expressions with multi-level sub/superscipts and accents such as: "b prime subscript b tilde superscript a superscipt pr comma omega". This is extremely hard to parse and possibly unnecessary, as b prime subscript b tilde and b tilde are the only configurations of accents and subscripts that appear. These could just be called alpha and beta and the rest is clear from the context. * The claim in theorem 4, the argmax is the same under both directions of the KL divergence, is not obvious. It is definitely not true for minimization, otherwise the I-projection and the M-projection would coincide. This should be argued. Alternatively, this point can be alltogether skipped, since Pinsker*s bound, which is the only place this is used, does not depend on the direction of KL. Overall, this paper raises some nice points, but with these problems it is not a clear accept.