Efficient Certified Algorithms for Robot Motion Planning – ECARP

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. To do that, we will rely on the
notion of roadmaps which reduce connectivity queries in arbitrary dimension to
connectivity queries on dimension one. Our goal is to enhance the foundations of
roadmap algorithms as well as computer algebra routines on which these
algorithms rely.

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, robotics and
algebraic geometry in this project.