Research output: Scientific - peer-review › Article

**Exploiting submodular value functions for scaling up active perception.** / Satsangi, Yash; Whiteson, Shimon; Oliehoek, Frans A.; Spaan, Matthijs T. J.

Research output: Scientific - peer-review › Article

Satsangi, Y, Whiteson, S, Oliehoek, FA & Spaan, MTJ 2018, 'Exploiting submodular value functions for scaling up active perception' *Autonomous Robots*, vol 42, no. 2, pp. 209-233. DOI: 10.1007/s10514-017-9666-5

Satsangi, Y., Whiteson, S., Oliehoek, F. A., & Spaan, M. T. J. (2018). Exploiting submodular value functions for scaling up active perception. *Autonomous Robots*, *42*(2), 209-233. DOI: 10.1007/s10514-017-9666-5

Satsangi Y, Whiteson S, Oliehoek FA, Spaan MTJ. Exploiting submodular value functions for scaling up active perception. Autonomous Robots. 2018;42(2):209-233. Available from, DOI: 10.1007/s10514-017-9666-5

@article{9dce2be87a4345c9ae092c694c037295,

title = "Exploiting submodular value functions for scaling up active perception",

abstract = "In active perception tasks, an agent aims to select sensory actions that reduce its uncertainty about one or more hidden variables. For example, a mobile robot takes sensory actions to efficiently navigate in a new environment. While partially observable Markov decision processes (POMDPs) provide a natural model for such problems, reward functions that directly penalize uncertainty in the agent’s belief can remove the piecewise-linear and convex (PWLC) property of the value function required by most POMDP planners. Furthermore, as the number of sensors available to the agent grows, the computational cost of POMDP planning grows exponentially with it, making POMDP planning infeasible with traditional methods. In this article, we address a twofold challenge of modeling and planning for active perception tasks. We analyze rhoPOMDP and POMDP-IR, two frameworks for modeling active perception tasks, that restore the PWLC property of the value function. We show the mathematical equivalence of these two frameworks by showing that given a rhoPOMDP along with a policy, they can be reduced to a POMDP-IR and an equivalent policy (and vice-versa). We prove that the value function for the given rhoPOMDP (and the given policy) and the reduced POMDP-IR (and the reduced policy) is the same. To efficiently plan for active perception tasks, we identify and exploit the independence properties of POMDP-IR to reduce the computational cost of solving POMDP-IR (and rhoPOMDP). We propose greedy point-based value iteration (PBVI), a new POMDP planning method that uses greedy maximization to greatly improve scalability in the action space of an active perception POMDP. Furthermore, we show that, under certain conditions, including submodularity, the value function computed using greedy PBVI is guaranteed to have bounded error with respect to the optimal value function. We establish the conditions under which the value function of an active perception POMDP is guaranteed to be submodular. Finally, we present a detailed empirical analysis on a dataset collected from a multi-camera tracking system employed in a shopping mall. Our method achieves similar performance to existing methods but at a fraction of the computational cost leading to better scalability for solving active perception tasks.",

keywords = "Sensor selection, Long-term planning, Mobile sensors, Submodularity, POMDP",

author = "Yash Satsangi and Shimon Whiteson and Oliehoek, {Frans A.} and Spaan, {Matthijs T. J.}",

year = "2018",

doi = "10.1007/s10514-017-9666-5",

volume = "42",

pages = "209--233",

journal = "Autonomous Robots",

issn = "0929-5593",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - Exploiting submodular value functions for scaling up active perception

AU - Satsangi,Yash

AU - Whiteson,Shimon

AU - Oliehoek,Frans A.

AU - Spaan,Matthijs T. J.

PY - 2018

Y1 - 2018

N2 - In active perception tasks, an agent aims to select sensory actions that reduce its uncertainty about one or more hidden variables. For example, a mobile robot takes sensory actions to efficiently navigate in a new environment. While partially observable Markov decision processes (POMDPs) provide a natural model for such problems, reward functions that directly penalize uncertainty in the agent’s belief can remove the piecewise-linear and convex (PWLC) property of the value function required by most POMDP planners. Furthermore, as the number of sensors available to the agent grows, the computational cost of POMDP planning grows exponentially with it, making POMDP planning infeasible with traditional methods. In this article, we address a twofold challenge of modeling and planning for active perception tasks. We analyze rhoPOMDP and POMDP-IR, two frameworks for modeling active perception tasks, that restore the PWLC property of the value function. We show the mathematical equivalence of these two frameworks by showing that given a rhoPOMDP along with a policy, they can be reduced to a POMDP-IR and an equivalent policy (and vice-versa). We prove that the value function for the given rhoPOMDP (and the given policy) and the reduced POMDP-IR (and the reduced policy) is the same. To efficiently plan for active perception tasks, we identify and exploit the independence properties of POMDP-IR to reduce the computational cost of solving POMDP-IR (and rhoPOMDP). We propose greedy point-based value iteration (PBVI), a new POMDP planning method that uses greedy maximization to greatly improve scalability in the action space of an active perception POMDP. Furthermore, we show that, under certain conditions, including submodularity, the value function computed using greedy PBVI is guaranteed to have bounded error with respect to the optimal value function. We establish the conditions under which the value function of an active perception POMDP is guaranteed to be submodular. Finally, we present a detailed empirical analysis on a dataset collected from a multi-camera tracking system employed in a shopping mall. Our method achieves similar performance to existing methods but at a fraction of the computational cost leading to better scalability for solving active perception tasks.

AB - In active perception tasks, an agent aims to select sensory actions that reduce its uncertainty about one or more hidden variables. For example, a mobile robot takes sensory actions to efficiently navigate in a new environment. While partially observable Markov decision processes (POMDPs) provide a natural model for such problems, reward functions that directly penalize uncertainty in the agent’s belief can remove the piecewise-linear and convex (PWLC) property of the value function required by most POMDP planners. Furthermore, as the number of sensors available to the agent grows, the computational cost of POMDP planning grows exponentially with it, making POMDP planning infeasible with traditional methods. In this article, we address a twofold challenge of modeling and planning for active perception tasks. We analyze rhoPOMDP and POMDP-IR, two frameworks for modeling active perception tasks, that restore the PWLC property of the value function. We show the mathematical equivalence of these two frameworks by showing that given a rhoPOMDP along with a policy, they can be reduced to a POMDP-IR and an equivalent policy (and vice-versa). We prove that the value function for the given rhoPOMDP (and the given policy) and the reduced POMDP-IR (and the reduced policy) is the same. To efficiently plan for active perception tasks, we identify and exploit the independence properties of POMDP-IR to reduce the computational cost of solving POMDP-IR (and rhoPOMDP). We propose greedy point-based value iteration (PBVI), a new POMDP planning method that uses greedy maximization to greatly improve scalability in the action space of an active perception POMDP. Furthermore, we show that, under certain conditions, including submodularity, the value function computed using greedy PBVI is guaranteed to have bounded error with respect to the optimal value function. We establish the conditions under which the value function of an active perception POMDP is guaranteed to be submodular. Finally, we present a detailed empirical analysis on a dataset collected from a multi-camera tracking system employed in a shopping mall. Our method achieves similar performance to existing methods but at a fraction of the computational cost leading to better scalability for solving active perception tasks.

KW - Sensor selection

KW - Long-term planning

KW - Mobile sensors

KW - Submodularity

KW - POMDP

UR - http://resolver.tudelft.nl/uuid:9dce2be8-7a43-45c9-ae09-2c694c037295

U2 - 10.1007/s10514-017-9666-5

DO - 10.1007/s10514-017-9666-5

M3 - Article

VL - 42

SP - 209

EP - 233

JO - Autonomous Robots

T2 - Autonomous Robots

JF - Autonomous Robots

SN - 0929-5593

IS - 2

ER -

ID: 34681403