Exploiting submodular value functions for faster dynamic sensor selection



Satsangi, Y, Whiteson, S and Oliehoek, FA
(2015) Exploiting submodular value functions for faster dynamic sensor selection. In: UNSPECIFIED, ? - ?.

[img] Text
Satsangi15AAAI.pdf

Download (692kB)

Abstract

© Copyright 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. A key challenge in the design of multi-sensor systems is the efficient allocation of scarce resources such as bandwidth, CPU cycles, and energy, leading to the dynamic sensor selection problem in which a subset of the available sensors must be selected at each timestep. While partially observable Markov decision processes (POMDPs) provide a natural decision-theoretic model for this problem, the computational cost of POMDP planning grows exponentially in the number of sensors, making it feasible only for small problems. We propose a new POMDP planning method that uses greedy maximization to greatly improve scalability in the number of sensors. We show that, under certain conditions, the value function of a dynamic sensor selection POMDP is submodular and use this result to bound the error introduced by performing greedy maximization. Experimental results on a realworld dataset from a multi-camera tracking system in a shopping mall show it achieves similar performance to existing methods but incurs only a fraction of the computational cost, leading to much better scalability in the number of cameras.

Item Type: Conference or Workshop Item (Paper)
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Depositing User: Symplectic Admin
Date Deposited: 20 Oct 2015 07:49
Last Modified: 08 Aug 2018 07:10
URI: http://livrepository.liverpool.ac.uk/id/eprint/2032381
Repository Staff Access