Efficient certified algorithms for robot motion planning (ECARP)

Overall description

Recently, several breakthroughs in computer algebra opened new perspectives to better tackle problems in semialgebraic geometry such as connectivity queries and determination of connected components of semialgebraic sets. An important application to this is the motion planning of robots. In this project, we are specifically interested in kinematic singularity avoidance path planning. Existing algorithms that are used are not always certified. Currently, path planning problems are posed as optimal control problems and solved numerically which generally does not give a global solution or simply disregard kinematic singularity. We aim at approaching this problem from a computer algebra perspective.

Our goal is to develop dedicated high performance computer algebra algorithms for robotics and path planning. We aim to improve current Gröbner basis engines and real root isolation algorithms involved in roadmap computations that are very relevant to this problem. We are also very interested in understanding the topological and algebraic properties of the singularities of manipulators. An important property is cuspidality, i.e. the existence of a singularity-free path between two points on a fiber of the kinematic map of a 6R manipulator. This is important in engineering applications because 6R manipulators are by far the most widely used robots in industry. From an algebro-geometric viewpoint, the kinematic singularity of a 6R manipulator is just the projection of a hyperplane section of a Segre subvariety in a projective space. Thus there is an exact algebraic description of the problem, yet the problem of characterization of cuspidal 6R manipulator remains widely open to date and we are confident we can solve this problem in this project. Even if a 6R manipulator is non-cuspidal engineers are eager to know if a path with minimal singularity crossing is possible and this can also be tackled through algebraic means. This algebraic description will eventually be used by the roadmap algorithms that we will develop. But they may even help us to theoretically describe the number of connected components of singularity-free configuration- and work- spaces and thus we can complement and compare with results from our high performance computer algebra algorithms.

Finally, we also aim to study self-motion of n-SPS platforms i.e. if two points in the workspace of n-SPS platforms can be connected. The configuration set of a parallel linkage is a topological space that has recently attracted the attention of many researchers in geometry, rigidity theory, and topology. The two-dimensional situation is classical: the topology of the configuration space depends on inequalities in the lengths of the bars (Grashof's conditions). We intend to use elimination theory in order to obtain generalizations to parallel linkages in 3-space.

We boast a multidisciplinary team of experts in computer algebra (Linz, Paris), robotics (Linz, Nantes) and algebraic geometry (Linz) in this project.