Topological Complexity of Motion Planning

   Abstract. In this paper we study a notion of topological complexity TC (X) for the motion planning problem. TC (X) is a number which measures discontinuity of the process of motion planning in the configuration space X . More precisely, TC (X) is the minimal number k such that there are k different "motion planning rules," each defined on an open subset of X× X , so that each rule is continuous in the source and target configurations. We use methods of algebraic topology (the Lusternik—Schnirelman theory) to study the topological complexity TC (X) . We give an upper bound for TC (X) (in terms of the dimension of the configuration space X ) and also a lower bound (in terms of the structure of the cohomology algebra of X ). We explicitly compute the topological complexity of motion planning for a number of configuration spaces: spheres, two-dimensional surfaces, products of spheres. In particular, we completely calculate the topological complexity of the problem of motion planning for a robot arm in the absence of obstacles.     

Topological Complexity of Zero-Finding

The topological complexity of zero-finding is studied using a BSS machine over the reals with an information node. The topological complexity depends on the class of functions, the class of arithmetic operations, and on the error criterion. For the root error criterion the following results are established. If only Hölder operations are permitted as arithmetic operations then the topological complexity is roughly −log₂ε and bisection is optimal. This holds even for the small class of linear functions. On the other hand, for the class of all increasing functions, if we allow the sign function or division, together with log and exp, then the topological complexity drops to zero. For the residual error criterion, results can be totally different than for the root error criterion. For example, the topological complexity can be zero for the residual error criterion, and roughly −log₂ε for the root error criterion.     

Topological Complexity with Continuous Operations

The topological complexity of algorithms is studied in a general context in the first part and for zero-finding in the second part. In the first part thelevel of discontinuityof a functionfis introduced and it is proved that it is a lower bound for the total number of comparisons plus 1 in any algorithm computingfthat uses only continuous operations and comparisons. This lower bound is proved to be sharp if arbitrary continuous operations are allowed. Then there exists even a balanced optimal computation tree forf. In the second part we use these results in order to determine the topological complexity of zero-finding for continuous functionsfon the unit interval withf(0) ·f(1) < 0. It is proved that roughly log₂log₂?⁻¹comparisons are optimal during a computation in order to approximate a zero up to ?. This is true regardless of whether one allows arbitrary continuous operations or just function evaluations, the arithmetic operations {+, −, *, /}, and the absolute value. It is true also for the subclass of nondecreasing functions. But for the subclass of increasing functions the topological complexity drops to zero even for the smaller class of operations.     

Motion Planning of Robot Locomotion

Since the treatment of robot locomotion is quite closed with this one of human locomotion, the present paper treats the problems of modelling, simulation and motion planning of robot locomotion on the base of knowledge of the skeletal system, as well as on the base of multibody system modelling, simulation and control using some ideas from Lie group theory and differential geometry.     

Motion Planning for Multiple Robots

We study the motion-planning problem for pairs and triples of robots operating in a shared workspace containing n obstacles. A standard way to solve such problems is to view the collection of robots as one composite robot, whose number of degrees of freedom is d , the sum of the numbers of degrees of freedom of the individual robots. We show that it is sufficient to consider a constant number of robot systems whose number of degrees of freedom is at most d-1 for pairs of robots, and d-2 for triples. (The result for a pair assumes that the sum of the number of degrees of freedom of the robots constituting the pair reduces by at least one if the robots are required to stay in contact; for triples a similar assumption is made. Moreover, for triples we need to assume that a solution with positive clearance exists.) We use this to obtain an O(n ^d ) time algorithm to solve the motion-planning problem for a pair of robots; this is one order of magnitude faster than what the standard method would give. For a triple of robots the running time becomes O(n ^d-1 ) , which is two orders of magnitude faster than the standard method. We also apply our method to the case of a collection of bounded-reach robots moving in a low-density environment. Here the running time of our algorithm becomes O(n log n) both for pairs and triples. Received August 10, 1998, and in revised form February 17, 1999.     

Topological Complexity of the Relative Closure of a Semi-Pfaffian Couple

Gabrielov introduced the notion of relative closure of a Pfaffian couple as an alternative construction of the o-minimal structure generated by Khovanskii’s Pfaffian functions. In this paper, we use the notion of format (or complexity) of a Pfaffian couple to derive explicit upper bounds for the homology of its relative closure. We consider both the singular and the Borel–Moore homology theories.     

A Hybrid Systems Framework for Motion Planning with Motion Primitives of Mechanical Systems

Motion planning with motion primitives is a solution concept for the optimal control of mechanical systems based on a quantization of the search space. In this contribution, we write the resulting system as a hybrid automaton and discuss the arising structures. In this context, we focus on the exploitation of symmetries. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

用旋量方法规划机器人运动轨迹

以姿态旋量描述机器人的位置姿态,在对偶空间中通过姿态旋量映射的点规划机器人的终端轨迹,具有直观、简便的独特优点。规划中直接根据跟踪误差进行收敛,提高了轨迹运行的动态精度,并适合于冗余自由度操作器。     

On the Complexity of Isolating Real Roots and Computing with Certainty the Topological Degree

In this contribution the isolation of real roots and the computation of the topological degree in two dimensions are considered and their complexity is analyzed. In particular, we apply Stenger's degree computational method by splitting properly the boundary of the given region to obtain a sequence of subintervals along the boundary that forms a sufficient refinement. To this end, we properly approximate the function using univariate polynomials. Then we isolate each one of the zeros of these polynomials on the boundary of the given region in various subintervals so that these subintervals form a sufficiently refined boundary.     

Energy-Optimal Multi-Goal Motion Planning for Planar Robot Manipulators

In this work, the energy-optimal motion planning problem for planar robot manipulators with two revolute joints is studied, in which the end-effector of the robot manipulator is constrained to pass through a set of waypoints, whose sequence is not predefined. This multi-goal motion planning problem has been solved as a mixed-integer optimal control problem in which, given the dynamic model of the robot manipulator, the initial and final configurations of the robot, and a set of waypoints inside the workspace of the manipulator, one has to find the control inputs, the sequence of waypoints with the corresponding passage times, and the resulting trajectory of the robot that minimizes the energy consumption during the motion. The presence of the waypoint constraints makes this optimal control problem particularly difficult to solve. The mixed-integer optimal control problem has been converted into a mixed-integer nonlinear programming problem first making the unknown passage times through the waypoints part of the state, then introducing binary variables to enforce the constraint of passing once through each waypoint, and finally applying a fifth-degree Gauss–Lobatto direct collocation method to tackle the dynamic constraints. High-degree interpolation polynomials allow the number of variables of the problem to be reduced for a given numerical precision. The resulting mixed-integer nonlinear programming problem has been solved using a nonlinear programming-based branch-and-bound algorithm specifically tailored to the problem. The results of the numerical experiments have shown the effectiveness of the approach.     

Motion Planning in Environments with Low Obstacle Density

We present a simple and efficient paradigm for computing the exact solution of the motion planning problem in environments with a low obstacle density. Such environments frequently occur in practical instances of the motion planning problem. The complexity of the free space for such environments is known to be linear in the number of obstacles. Our paradigm is a new cell decomposition approach to motion planning and exploits properties that follow from the low density of the obstacles in the robot's workspace. These properties allow us to decompose the workspace, subject to some constraints, rather than to decompose the higher-dimensional free configuration space directly. A sequence of uniform steps transforms the workspace decomposition into a free space decomposition of asymptotically the same size. The approach leads to nearly optimal O(n \log n) motion planning algorithms for free-flying robots with any fixed number of degrees of freedom in workspaces with low obstacle density. Received October 17, 1995, and in revised form July 8, 1997, and February 23, 1998.     

Dynamics-Based Motion Planning for a Pendulum-Actuated Spherical Rolling Robot

This paper deals with the dynamics and motion planning for a spherical rolling robot with a pendulum actuated by two motors. First, kinematic and dynamic models for the rolling robot are introduced. In general, not all feasible kinematic trajectories of the rolling carrier are dynamically realizable. A notable exception is when the contact trajectories on the sphere and on the plane are geodesic lines. Based on this consideration, a motion planning strategy for complete reconfiguration of the rolling robot is proposed. The strategy consists of two trivial movements and a nontrivial maneuver that is based on tracing multiple spherical triangles. To compute the sizes and the number of triangles, a reachability diagram is constructed. To define the control torques realizing the rest-to-rest motion along the geodesic lines, a geometric phase-based approach has been employed and tested under simulation. Compared with the minimum effort optimal control, the proposed technique is less computationally expensive while providing similar system performance, and thus it is more suitable for real-time applications.     

机械臂运动路径规划的算法设计

我们对题目中所给的特定的六自由度机械手臂设计一整套通用的算法.让它能够实现点到点移动,有障碍的曲线跟踪,和避障点对点移动三种基本功能.并能自动生成控制台所需要的指令序列.最后我们会对模型的适用范围和准确性进行评价.     

Pseudo Approximation Algorithms with Applications to Optimal Motion Planning

We introduce a technique for computing approximate solutions to optimization problems. If $X$ is the set of feasible solutions, the standard goal of approximation algorithms is to compute $x\in X$ that is an $\varepsilon$-approximate solution in the following sense: $$d(x) \leq (1+\varepsilon)\, d(x^*),$$ where $x^* \in X$ is an optimal solution, $d\colon\ X\rightarrow {\Bbb R}_{\geq 0}$ is the optimization function to be minimized, and $\varepsilon>0$ is an input parameter. Our approach is first to devise algorithms that compute pseudo $\varepsilon$-approximate solutions satisfying the bound $$d(x) \leq d(x_R^*) + \varepsilon R,$$ where $R>0$ is a new input parameter. Here $x^*_R$ denotes an optimal solution in the space $X_R$ of $R$-constrained feasible solutions. The parameter $R$ provides a stratification of $X$ in the sense that (1) $X_R \subseteq X_{R}$ for $R < R$ and (2) $X_R = X$ for $R$ sufficiently large. We first describe a highly efficient scheme for converting a pseudo $\varepsilon$-approximation algorithm into a true $\varepsilon$-approximation algorithm. This scheme is useful because pseudo approximation algorithms seem to be easier to construct than $\varepsilon$-approximation algorithms. Another benefit is that our algorithm is automatically precision-sensitive. We apply our technique to two problems in robotics: (A) Euclidean Shortest Path (3ESP), namely the shortest path for a point robot amidst polyhedral obstacles in three dimensions, and (B) $d_1$-optimal motion for a rod moving amidst planar obstacles (1ORM). Previously, no polynomial time $\varepsilon$-approximation algorithm for (B) was known. For (A), our new solution is simpler than previous solutions and has an exponentially smaller complexity in terms of the input precision.     

自由下落猫的非完整运动规划最优控制研究

研究猫在自由下落时姿态运动规划问题．自由落体的猫在空中转体运动由于角速度不可积,姿态运动方程呈现为非完整形式．当系统角动量为0时,导出由两个对称刚体组成的自由下落猫的非完整姿态运动方程．利用该非完整方程系统的控制问题可转化为无漂移系统的非完整运动规划问题．基于Ritz近似理论,给出自由落体猫姿态运动规划的Gauss-Newton算法．最后对自由落体猫作了数值仿真实验,仿真结果验证了该算法的有效性．     

Motion Planning for a Convex Polygon in a Polygonal Environment

We study the motion-planning problem for a convex m -gon P in a planar polygonal environment Q bounded by n edges. We give the first algorithm that constructs the entire free configuration space (the three-dimensional space of all free placements of P in Q ) in time that is near-quadratic in mn , which is nearly optimal in the worst case. The algorithm is also conceptually simple. Previous solutions were incomplete, more expensive, or produced only part of the free configuration space. Combining our solution with parametric searching, we obtain an algorithm that finds the largest placement of P in Q in time that is also near-quadratic in mn . In addition, we describe an algorithm that preprocesses the computed free configuration space so that reachability queries can be answered in polylogarithmic time. Received September 9, 1997, and in revised form September 24, 1998.