## Algorithmic Questions on Combinatorial Filters

- Nov. 18, 2016
- 2:30 p.m.
- LeConte 312

## Abstract

This talk will address some algorithmic questions related to automating the design of robots. Specifically, we consider the combinatorial filters introduced by Tovar, Cohen, Czarnowski, and LaValle, which represent a robot's interaction with its environment as a finite-state transition system. We show that many natural problems on these filters are NP-hard, even to approximate. This is joint work with with Dylan Shell, Fatemeh Saberifar, and Shervin Ghasemlou.