IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

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.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC