Accelerating combinatorial filter reduction through constraints
Yulin Zhang, Hazhar Rahmani, Dylan A. Shell, Jason M. O'Kane
In Proc. IEEE International Conference on Robotics and Automation
2021
Abstract
Reduction of combinatorial filters involves compressing state representations
that robots use. Such optimization arises in automating the construction of
minimalist robots. But exact combinatorial filter reduction is an NP-complete
problem and all current techniques are either inexact or formalized with
exponentially many constraints.
This paper proposes a new formalization needing only a polynomial number of
constraints, and characterizes these constraints in three different forms:
nonlinear, linear, and conjunctive normal form. Empirical results show that
constraints in conjunctive normal form capture the
problem most effectively, leading to a method that outperforms the others.
Further examination indicates that a substantial proportion of constraints
remain inactive during iterative filter reduction. To leverage this
observation, we introduce just-in-time
generation of such constraints, which yields improvements in
efficiency and has the potential to minimize large filters.
Download
BibTeX
@inproceedings{zhang2021accelerating,
title={Accelerating combinatorial filter reduction through constraints},
author={Zhang, Yulin and Rahmani, Hazhar and Shell, Dylan A and O’Kane, Jason M},
booktitle={Proc. IEEE International Conference on Robotics and Automation},
pages={9703--9709},
year={2021},
organization={IEEE}
}