## Automatic design of discreet discrete filters

**Jason M. O'Kane**, Dylan A. Shell

In *Proc. IEEE International Conference on Robotics and Automation*

2015
**Abstract**
We address the problem of deciding what information a robot should transmit
to the outside world, by exploring a setting where some information (e.g.,
current status of the task) must be shared in order for the robot to be
useful, but where, simultaneously, we wish to impose limits which ensure
certain information is never divulged. These sorts of conditions arise in
several circumstances of increasing relevance: robots that can provide some
guarantee of privacy to their users, controllers which safely use untrusted
"cloud" services or smart-space infrastructure, or robots that act as
inspection devices in information-sensitive contexts (e.g., factories,
nuclear plants, etc.) We introduce an algorithm which takes as input an
arbitrary combinatorial filter, expressed as a transition graph, and a set
of constraints, constituting both upper and lower bounds, that specify the
desired informational properties. The algorithm produces a coarser version
of the input filter which possesses the desired informational properties,
if and only if such a filter exists. We show that determining whether it
is possible to satisfy both the distinguishablity and indistinguishablity
constraints is NP-hard. The hardness result helps justify the worst-case
running time of the algorithm. We describe an implementation of the
algorithm along with empirical results showing that, beyond some minimum
problem complexity, the algorithm is faster than naive filter enumeration,
albeit with greater memory requirements.

@inproceedings{OKaShe15,
author = {Jason M. O'Kane and Dylan A. Shell},
booktitle = {Proc. IEEE International Conference on Robotics and Automation},
title = {Automatic design of discreet discrete filters},
year = {2015}
}

*Last updated 2020-09-23.*