Computing the Number of Connected Components of Spaces Defined by Generic Non-linear Inequalities скачать в хорошем качестве

Computing the Number of Connected Components of Spaces Defined by Generic Non-linear Inequalities

Speaker: Hugo Rémin (Université Angers, France) Abstract: Topological spaces are used in almost all branch of modern mathematics, it is of importance in robotics as the free configuration space of a robot is a topological space. Thus knowing underlying topological properties on the free configuration space can be used in motion planning. In this talk, our focus is on computing the number of path-connected components of spaces defined by generic non-linear inequalities. With our approach we are able to guarantee whether a trajectory between two configurations is feasible or not. Previous research includes formal methods limited to semi-algebraic sets and, most relevant to this paper, an algorithm on the same spaces as our focus running in O(2^{2n}) time using star domains and interval analysis. Here we show that by using contractibility over star domain a substantial improvement on the time complexity can be accomplished. An algorithm is presented with a time complexity of O(2^{n}) and the results are shown on examples.