Efficient Certified Algorithms for Robot Motion Planning

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.

Das Hauptziel des Projekts bestand darin, die interdisziplinäre und internationale Zusammenarbeit zwischen Mathematikern und Robotikern zu fördern, um Cuspidal-Manipulatoren und kinematische Singularitäten von Robotern zu verstehen. Wir verwenden Computeralgebra Methoden, um technische Herausforderungen zu bewältigen, die sich aus Singularitäten und Cuspidality ergeben. Dies ist von entscheidender Bedeutung, da nur wenige industrielle seriellen Manipulatoren die Eigenschaft als Cuspidality besitzen, was zu unerwartetem Verhalten bei der Bahnplanung führt. Viele Robotiker sind an nicht-Cuspidal 6R-Industrieroboter gewöhnt, während generische Roboter (z.B. zufällig oder durch KI entstandenen Designs) in der Regel Cuspidal sind. Ein Roboter ist Cuspidal, wenn er in der Lage ist, seine Gelenkkonfiguration für dieselbe Endeffektorposition zu ändern, ohne Singularitäten zu überschreiten. In diesem Projekt konnten wir die Cuspidal 3R-Roboter effizient kategorisieren und einige industrielle 6R-Roboter identifizieren, die Cuspidal sind und ursprünglich nicht bekannt waren. Ingenieure vermeiden in der Regel Singularitäten, da sie zu unerwartetem Roboterverhalten führen können. Bei singulären Konfigurationen kann der Roboter plötzlich mehr Kraft und Geschwindigkeit benötigen, um sich zu bewegen. Ein historisches Beispiel für übersehene Singularitäten, die Schwierigkeiten verursachen, ist die Trägheitsmesseinheit für Gyroskope bei der Apollo-Mission der NASA. Die mathematische Natur dieser Robotikfragen erforderte Computeralgebra. Zum Beispiel der kinematische Singularitätsraum eines Roboters kann aus vielen zusammenhängenden Komponenten bestehen. Bei typischen parallelen Manipulatoren, die z.B. zum Bewegen von Plattformen in Flugsimulatoren verwendet werden, wird vermutet, dass der Singularitätsraum aus einer einzigen zusammenhängenden Komponente besteht. Das Verständnis der Anzahl dieser Komponenten hilft bei der Identifizierung singularitätsfreier Pfade, was zu reibungsloseren Simulatorbewegungen führt. Die Untersuchung von zusammenhängenden Komponenten ist ein grundlegendes Problem der reellen algebraischen Geometrie und Computeralgebra. In diesem Projekt konnten wir die Singularitäten für 3RPR parallele Roboter kategorisieren und die Anzahl der Komponenten der Singularitäten bestimmte 6SPS-Roboter beweisen. Das Projekt hat die Erwartungen übertroffen und die interdisziplinäre Zusammenarbeit ist reibungslos verlaufen. Die Mathematiker respektierten die praktische Erfahrung und das technische Fachwissen der Ingenieure, während die Ingenieure sich auf komplexe mathematische Lösungen einließen. Dieses gegenseitige Verständnis zwischen Experten aus verschiedenen Bereichen war entscheidend für den Erfolg des Projekts. Zu den konkreten Ergebnissen gehören: > Eine Habilitation für einen Senior Postdoc > Zwei abgeschlossene Promotionsstudien > Zwei laufende Doktoratsstudien Die Zusammenarbeit förderte nicht nur das Lernen zwischen den Disziplinen, sondern auch zwischen Forschern aus verschiedenen Ländern, die ihr Fachwissen austauschten. Diese Erfahrung hat gezeigt, dass internationale und interdisziplinäre Zusammenarbeit sowohl machbar als auch für die Forscher von großem Nutzen ist.