Algebraic Methods in Collision Detection and Path Planning

When designing the motion of a robot or a mechanical structure, diverse criteria have to be taken into account. Most notably, the motion must avoid collisions, the robot must stay away from singularities and the robot must stay in the workspace component (translatorial, rotatorial) for which it was designed for. In addition, the motion should be fast and smooth. Our project addresses some of the issues related to collision detection and motion design for industrial robots and devices which are at the moment subject of research but have potential for industrial application. Of course, this is by no means a new topic. We believe, however, that recent results in motion design, algebraic geometry of robot manipulators, and Computer Aided Design allow and even demand new ways of thinking about robot path planning. Basically, we want to explore possibilities to create robot paths that avoid algebraic varieties or objects composed of pieces of algebraic varieties that represent unwanted components of a robot`s workspace or operation mode. Here, the word "object" may refer to physical obstacles in the surroundings of the robot as well as to singularities in the robot workspace or operation mode. The project is divided into several work packages, "Algebraic robot tolerancing", "Trajectory judgment", "Trajectory generation (two poses)", "Obstacle aware trajectory generation", "Trajectory generation (multiple poses)", and, finally, "Combined approaches".

The research project Algebraic Methods in Collision Detection and Path Planning aimed at improving the construction and performance of certain mechanical devices. Such linkages are ubiquitous in our lives, for example in machines that induce motion like cars or washing machines.But they are even more important in industrial applications as important parts in manufacturing machines, to aid human workers, or even to aid surgeons during a complicated operation. In order to ef?ciently and safely use linkages, several requirements must be met. The individual members of the linkage must closely follow previously de?ned paths in space, they must avoid collisions with other objects, and they also must avoid certain special con?gurations, determined by the linkages geometry, where the linkage evades external control. These latter con?gurations are somewhat mysterious but may have an enormous effect on the performance: The linkage may simply collapse or it may break due to a sudden increase of necessary forces in the joints.In our project, we used methods of algebra, algebraic geometry, and computer algebra to solve some of the described problems:We explored a novel idea to construct linkages of a certain type whose individual members follow advantageous paths. These paths can be designed easily on a computer and lend themselves well to certain algorithms for collision detection. Among the more theoretical results are new families of spatial linkages that can guide one point on a straight line. They constitute new solutions to a very old problem of mechanism science. The ?rst solution, Peaucelliers inversor, dates back to the 19th century. More practical applications include an algorithm for the construction of simple linkages to four prescribed poses.In order to detect possible collision for above linkages (and others as well), we developed a new algorithm that uses characteristic features of the linkage motion to give an absolute no-collision guarantee. This contrasts existing algorithms that work for more general mechanical devices but often make simplifying assumptions so that their no-collision predicate is fast and credible but not absolutely certain.Finally, we also made some contribution to the problems of avoiding dangerous con?gurations of mechanisms. We increased our understanding of the nature of these con?gurations and how they are related to each other. With this knowledge it was possible to design motions that avoid them in particular examples.