State space reduction of combinatorial filters

A map of the third floor of ACES building of University of Texas at Austin (P. Beeson, M. MacMahon, J. Modayil, A. Murarka, B. Kuipers, and B. Stankiewicz, "Integrating multiple representations of spatial knowl-edge for mapping, navigation, and communication." in Interaction Challenges for Intelligent Assistants, 2007, pp. 1-9.). The map is overlaid with the generalized Voronoi graph (GVG) of the environment in red. A simple environment and its GVG for illustrating how a combinatorial filter can be used as a plan to reach a goal location from full location uncertainty. A naively-constructed combinatorial filter, which the robot can use to navigate through the environment in part b) to reach point 3, starting from full location uncertainty.


Combinatorial filters are formal structures for filtering and reasoning over discrete sensor data as well as for discrete planning. This project focuses on the combinatorial filter minimization problem, which is proved to be computationally hard. We study this problem and variant of through the lens of (bi)simulation, and show that the classical notion of bisimulation usually provides only sub-optimal solution to the problem. We introduce variants of bisimulation that are used to compute exact solution to the problem. We provide mathematical programming formulations that are used to compute exact and approximate solutions of the problem. We also identify several classes of filters for which the problem is solvable in polynomial time.


Hazhar's home page