This will be a hybrid event with in-person attendance in Levine 307 and virtual attendance on Zoom.

ABSTRACT

This talk describes investigations into the nature of robot–environment interaction and “niche fit” through the lens of state (or memory) minimization. The idea is that by limiting what a robot can store, much like so-called bottleneck methods, one hopes to uncover the information needed to perform specific tasks.  We study a setting in which robots are able to exploit structural regularity within the environment.  Doing so alters the minimization problem from classical reduction problems (i.e., those of Myhill–Nerode or bisimulation relations) in an important, fundamental way: it changes computational complexity class.  The later part of the talk will try to explore interpretations and intuitions behind the (multiple) extra sources of this complexity.  Touching briefly upon intriguing ways in which nondeterminism and casualty manifest themselves, the final part of the talk will describe how we are now approaching sensors within this theoretical framework too.