Positive dimensional parametric polynomial systems, connectivity queries and applications in robotics

In this paper we introduce methods and algorithms that will help us solve connectivity queries of parameterized semi-algebraic sets. Answering these connectivity queries is applied in the design of robotic structures having similar kinematic properties (e.g. topology of the kinematic-singularity-free space). From these algorithms one also obtain solutions to connectivity queries of a specific parameter which is in turn related to kinematic-singularity free path-planning of a specific manipulator belonging to the family of robots with these properties; i.e. we obtain paths joining two given singularity free configurations lying in the same connected component of the singularity-free space. We prove in the paper how one reduces the problems related to connectivity queries of parameterized semi-algebraic sets to closed and bounded semi-algebraic sets. We then design an algorithm using computer-algebra methods for solving positive dimensional polynomial system depending on parameters. The meaning of solving here means partitioning the parameter space into semi -algebraic components over which the number of connected com-ponents of the semi-algebraic set defined by the input system is invariant. The complexity of this algorithm is singly exponential in the dimension of the ambient space. The algorithm scales enough to analyze automatically the family of UR-series robots. Finally we provide manual analysis of the family of UR-series robots, proving that the number of connected components of the

Automated summary

This paper introduces methods and algorithms for solving connectivity queries of parameterized semi-algebraic sets. These queries are applied in the design of robotic structures with similar kinematic properties. The algorithms provide solutions to connectivity queries of a specific parameter, which is related to kinematic-singularity free path-planning of a specific manipulator. The paper proves how to reduce the problems related to connectivity queries of parameterized semi-algebraic sets to closed and bounded semi-algebraic sets. The algorithm designed in this paper uses computer-algebra methods and has a complexity of singly exponential in the dimension of the ambient space. The algorithm is scalable enough to analyze the family of UR-series robots. The paper also provides a manual analysis of the UR-series robots, proving the number of connected components.