A Study of Singularities in Homotopy Continuation for Kinematic Applications

Task requirements and positions of robotic kinematic systems can be represented by a system of polynomial equations. The use of homotopy continuation, a numerical method from algebraic geometry, solves these systems and analyzes their solution sets. However, these systems are plagued by branch points, and homotopy paths passing within proximity to these points experience ill-conditioning leading to computational burdens and even numerical failures. Although branch points negatively impact homotopy continuation methods, one can leverage knowledge regarding these points for solving and analyzing kinematic systems. First, we present a holistic consideration of the presence of branch points in homotopy systems of generic cases and an applied kinematic problem. We study the distribution of the image of branch points, ramification points, compactified to the Riemann sphere for select combinations of start and end systems of a homotopy. We compute metrics to assess the uniformity of the ramification point distribution and observe methods that impact that distribution, including the use of specially structured start systems and scaling coefficients. Next, we consider the complete computation of solution sets for the four-bar optimal path synthesis problem in kinematics. As task requirements become more complex, so do their resulting systems, ultimately leading one to consider an optimization formulation such as the least-squares approximation. Homotopy continuation methods, namely the use of random monodromy loops, can be employed to these polynomial formulations to yield a nearly, if not totally, complete solution set starting from a single seed solution. We consider three scenarios of the optimal path synthesis with no, one, and two pivots pre-specified and applied examples for each scenario. Lastly, we propose a method for kinematic path planning that incorporates topological ideas into computing a radius graph representation of the workspace for a five-bar mechanism. The workspace of a five-bar mechanism is a manifold possessing extra folds that, when projected into a 2D view, appears to admit additional internal boundaries. The mechanism satisfies additional constraints at these boundaries, but only a portion of those boundaries should be avoided due to unfavorable transmission qualities displayed by the five-bar. Our method identifies and removes these boundaries in a workspace discretization while preserving characteristics of the workspace manifold. We sample a sufficient number of points from the configuration space such that we preserve topological features of the manifold. Then, through homotopy applications, we identify and remove problematic boundaries from our viable workspace discretization for use in path-planning algorithms. We apply our method to two path-planning examples and show the resulting path and joint actuations taken by the five-bar mechanism.

机器人运动学系统的任务需求和位置可以通过一组多项式方程来表示。利用同伦连续性，一种来自代数几何的数值方法，可以求解这些方程并分析其解集。然而，这些系统受到分支点的困扰，而穿过这些点附近的同伦路径会经历病态条件，导致计算负担加重甚至数值失败。尽管分支点对同伦连续性方法产生负面影响，但我们可以利用对这些点的知识来解决和分析运动学系统。首先，我们对同伦系统中一般情况下的分支点存在进行整体考量，并探讨一个应用运动学问题。我们研究分支点、分叉点在将同伦系统的起始和结束系统选定的组合紧凑化到黎曼球面上的分布。我们计算度量以评估分叉点分布的均匀性，并观察影响该分布的方法，包括使用特别结构的起始系统和缩放系数。接着，我们考虑对运动学中四杆最优路径综合问题的解集进行完整计算。随着任务需求变得更加复杂，相应的系统也变得更加复杂，最终导致人们考虑使用最小二乘近似这样的优化公式。同伦连续性方法，即随机单连通回路的使用，可以应用于这些多项式公式，从而从单个种子解出发，提供几乎或完全完整的解集。我们考虑了无、一、二个预设支点的最优路径综合的三种场景，并为每种场景提供了应用实例。最后，我们提出了一种将拓扑思想融入计算五杆机构工作空间半径图表示的运动学路径规划方法。五杆机构的工作空间是一个具有额外折痕的流形，当投影到二维视图时，似乎允许额外的内部边界。该机构在这些边界处满足额外的约束，但由于五杆机构显示出的不利传动特性，只有部分边界应该避免。我们的方法在保持工作空间流形特征的同时，识别并移除这些边界。我们从配置空间中采样足够数量的点，以保持流形的拓扑特征。然后，通过同伦应用，我们识别并从可行的工作空间离散化中移除问题边界，用于路径规划算法。我们将该方法应用于两个路径规划实例，并展示了五杆机构所采取的路径和关节动作。