Department of Mathematics




"Topological Robotics: Restricted Configuration Spaces of Metric Graphs"


(University of Oklahoma)
ABSTRACT: First I'll try to give some of the background of configuration spaces (of n ordered points) of a topological space (also related constructions like symmetric products and braid spaces) and their importance in topology and their relevance to robotics. There will be examples and few prerequisites. The nth configuration space of X is the subset of X^n where all n coordinates are distinct. These spaces are of interest (and not completely understood) even when n=2 and X is (the underlying topological space of) a finite simple graph. In applications it's more realistic to consider restricted configuration spaces (of hard disks or thick particles) where X is a metric space and the coordinates are required be further apart than a specified parameter r. When r is small, the homotopy type is the same as that of the configuration space. The restraint parameter r may also be a vector: The robots may have different sizes or, more generally, we may require that the distance between the ith and jth robots is at least r_ij (for any choice of n(n-1)/2 parameters r_ij).
     In joint work with James Dover we examined the variation of the homeomorphism and homotopy types of these configuration spaces of n robots on a (metric) graph, as the vector restraint parameter r = (r_ij) varies. We show in particular that there is a polynomial  bound (in the number of edges of the graph) on the number of homeomorphism types (extending earlier results of K. Deeley). The method of proof can be described as a piecewise linear vector-valued Morse theory. This is applicable to a polytopal cell complex equipped with a piecewise linear map to an n-dimensional space (in classical Morse theory n = 1) and is able to detect homeomorphism (not just homotopy) types.


Wednesday, April 13, 2016, 15.40

Mathematics Seminar Room, SA-141

All are most cordially invited. Tea and cookies: before the seminar