| Title: |
Accelerating combinatorial filter reduction through constraints |
| Authors: |
Zhang, Yulin; Rahmani, Hazhar; Shell, Dylan A.; O'Kane, Jason M. |
| Publication Year: |
2020 |
| Collection: |
Computer Science |
| Subject Terms: |
Computer Science - Robotics; Computer Science - Artificial Intelligence |
| Description: |
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.; Comment: 7 pages, 3 figures |
| Document Type: |
Working Paper |
| Access URL: |
http://arxiv.org/abs/2011.03471 |
| Accession Number: |
edsarx.2011.03471 |
| Database: |
arXiv |