Automatic design of discreet discrete filters

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}
}