Geometric folding algorithms – linkages, origami, polyhedra【第二章翻译】Upper and Lower Bounds

GENERAL ALGORITHMS AND UPPER BOUNDS

Configuration Space Approach

One of the earliest achievements in the field is an algorithm by Schwartz and Sharir that can solve any “motion planning” problem, including essentially any linkage problem. The technique is to explicitly construct a representation of the free space for the mechanism and then answer all questions with this representation. For example, a reconfiguration decision question reduces to deciding if the initial configuration A is in the same connected component of the free space as the final configuration B. An example of the configuration space for a 2-link arm in the presence of obstacles is shown in Figure 2.1.

该领域最早的成就之一是Schwartz和Sharir提出的算法,它可以解决任何“运动计划”问题,包括基本上所有的链接问题。 该技术是为该机制显式构造自由空间的表示形式,然后用该表示形式回答所有问题。 例如,重新配置决策问题简化为确定初始配置A是否与最终配置B在自由空间的相同连接组件中。示出了存在障碍物的2连杆臂的配置空间的示例 如图2.1所示。

Because each configuration is mapped to a point in configuration space, the complex motion of the arm in (a) of the figure is reduced to the path of a point in configuration space (b). In this case the configuration space is a torus representing two angles θ1 and θ2, each with wrap-around ranges [0, 2π] (see p. 61). Their original algorithm, developed in the justly famous five “piano mover’s” papers,1 resulted in a doubly exponential algorithm. Subsequent research has improved this to singly exponential. Although we will not employ this algorithm subsequently, it is an important milestone and serves as a baseline for all subsequent work, and so it is worth stating the result more precisely. The complexities are best expressed in terms of three parameters:

因为每个配置都映射到配置空间中的一个点,所以图(a)中的手臂的复杂运动减少到配置空间(b)中的点的路径。 在这种情况下,配置空间是一个圆环,代表两个角度θ1和θ2,每个角度都具有环绕范围[0,2π](请参见第61页)。 他们的原始算法是在著名的五本“钢琴演奏者”论文中提出的,1导致了双倍的指数算法。 随后的研究将其改进为单指数。 尽管我们随后将不再使用该算法,但是它是一个重要的里程碑,并且是所有后续工作的基准,因此值得更准确地说明结果。 最好用以下三个参数来表示复杂性:

  • k, the number of degrees of freedom of the mechanism. This is the number of parameters necessary to fully specify the configuration of the mechanism, so that a configuration can be represented by a point in Rk.
  • k,机构的自由度数。 这是完全指定机制配置所必需的参数数量,以便可以用Rk中的点表示配置。
  • m, the number of “constraint surfaces,” each recording some distance or nonpenetration constraint, and each represented by a collection of polynomial equalities and inequalities.
  • m,“约束面”的数量,每个约束面记录一些距离或非渗透约束,并分别由多项式等式和不等式的集合表示。
  • d, the maximum algebraic (polynomial) degree of the constraint surfaces. We will reserve n for the number of links in a linkage. Note that the dimension of the space in which the linkage is embedded is not independently relevant; rather, this dimension is absorbed into k. To repeat our earlier example, for a n-vertex polygon in 3D, k =3n.
  • d,约束面的最大代数(多项式)度。 我们将为链接中的链接数保留n。 注意,嵌入链接的空间的尺寸不是独立相关的; 相反,此维被吸收到k中。 重复我们前面的示例,对于3D中的n个顶点多边形,k = 3n。

Schwartz and Sharir used a technique called “cylindrical algebraic decomposition” to achieve an algorithm that can solve any motion planning problem in O((md) 3k ) time (see Box 2.1). This was subsequently improved by Canny with his “roadmap” algorithm (Canny 1987) to be singly exponential in k, which can even run in polynomial space (Canny 1988). The latest improvements to roadmap algorithms (Basu et al. 2000) yield a general motion planning algorithm with time complexity O(mk+1d O(k2) ) (see Box 2.2). Study of configuration spaces continues. For example, the spaces representing the coordinated motion of several robots and/or mechanisms is especially rich topologically (Abrams and Ghrist 2002). However, we focus primarily on the simplest spaces.

Schwartz和Sharir使用一种称为“圆柱代数分解”的技术来实现一种算法,该算法可以解决O((md)3k)时间内的任何运动计划问题(见框2.1)。 随后,坎尼利用他的“路线图”算法(Canny 1987)对其进行了改进,使其在k上具有单指数性,甚至可以在多项式空间中运行(Canny 1988)。 路线图算法的最新改进(Basu等人,2000年)产生了一种通用的运动规划算法,其时间复杂度为O(mk + 1d O(k2))(见专栏2.2)。 继续研究配置空间。 例如,代表几个机器人和/或机构的协调运动的空间在拓扑上特别丰富(Abrams和Ghrist 2002)。 但是,我们主要关注最简单的空间。

2.1.1.1 Specialization to Planar Robot Arms

Let us specialize this complexity to the important case of a polygonal chain of n links, in an obstacle-free, planar environment, requiring non-self-intersection of the chain.2 We simulate the non-self-intersection by considering the arm itself as an obstacle, so that the configuration space becomes the free space and the general motion planning results apply. We need to compute m and k. One can represent the chain with k =n +1 parameters, two coordinates of one end (the “shoulder” of the arm) and one angle for each of the n −1 joints. However, the use of angles makes it more problematical to keep all constraints semialgebraic, which is the situation to which the theoretical results apply. So instead let us say that k =2n + 2, using two Cartesian coordinates for each joint. Factoring out the trivial rigid motions by specifying the coordinates for one point reduces this to k =2n − 2. The constraints come in two varieties: the link lengths must be constant and two links may not intersect. The former can be represented by n equations specifying the squared length of each link. The second constraint is provided by the obstacles, which are the links themselves. Each of the (n2) pairs must be specified to not intersect. This nonintersection condition can be written as inequalities involving

让我们将这种复杂性专门化为n个链接的多边形链的重要情况,在无障碍的平面环境中,需要链的非自相交。2我们通过考虑手臂本身来模拟非自相交作为障碍物,使配置空间成为自由空间,并应用总体运动计划结果。我们需要计算m和k。一个可以用k = n +1个参数表示链,一个末端的两个坐标(臂的“肩膀”)和n -1个关节的每个角度一个角度。但是,角度的使用使得将所有约束保持为半代数问题更大,这是理论结果适用的情况。因此,让我们说k = 2n + 2,每个关节使用两个笛卡尔坐标。通过指定一个点的坐标来剔除琐碎的刚性运动,可将其简化为k = 2n −2。约束分为两种:链节的长度必须恒定并且两个链节不能相交。前者可以由n个方程式表示,这些方程式指定每个链接的平方长度。第二个约束是由障碍本身提供的。 (n2)对中的每对都必须指定为不相交。这种不相交的条件可以写成涉及

Box 2.1: Cylindrical Algebraic Decomposition

A semialgebraic set is a subset of Rk defined by a Boolean combination of a collection F of polynomial equations and inequalities. A cylindrical algebraic decomposition (CAD) for F is a decomposition of Rk into finitely many cells, which have the property that each polynomial in F evaluates to the same sign {−, 0, +} for every point in the cell. For univariate polynomials, a CAD is realized by a partition of R1 at the real roots of the polynomials. A CAD for multivariate polynomials is achieved by Collins’ recursive algorithm by partitioning each cylinder over the lower-dimensional cells into sign-invariant sectors. The recursion leads to a doubly exponential number of cells: O((md ) 3k ). With cell adjacency stored in a connectivity graph, a motion planning problem can be solved by searching for a collision-free path through this graph between the cells containing the initial and final configurations of the mechanism, in “randomized expected time” proportional to the number of cells.a
半代数集是由多项式方程和不等式的集合F的布尔组合定义的Rk的子集。 F的圆柱代数分解(CAD)是Rk分解成有限数量的像元,其性质为F中的每个多项式对像元中的每个点求值都为{-,0,+}。对于单变量多项式,CAD是通过在多项式的实根处划分R1来实现的。柯林斯的递归算法通过将较低维单元上的每个圆柱体划分为符号不变的扇区,来实现多元多项式的CAD。递归导致单元格数量成倍增长:O((md)3k)。通过将单元格邻接存储在连接图中,可以通过在包含该机制的初始配置和最终配置的单元之间通过该图搜索无冲突路径来解决运动计划问题,该随机路径与数量成比例细胞数
Box 2.2: Roadmap Algorithm
Canny’s algorithm constructs a network of piecewise algebraic curves (the roadmap) that (a) preserves the connectivity of the free space F in that every component of F contains a connected roadmap component and (b) is reachable from any configuration. The constructiona sweeps a hyperplane H through the space and traces out all extremal points of the intersection of H with the obstacle surfaces, forming “silhouette” curves. These curves might not be connected within each component of F, violating (a). They are linked together at the “critical points” of the sweep, where new extrema appear or disappear. The connection is accomplished via a recursive call to the roadmap algorithm, this time within H and so one dimension lower. This recursion results in only singly exponential complexity. The initial and final configurations can be linked into the network by treating them as critical points. Motion planning is then reduced to searching the roadmap. Subsequently Canny (1988) strengthened the result by showing that the roadmap algorithm and path planning can be made to run in polynomial space, and so the path planning problem is in PSPACE. Canny’s work also relies on general position assumptions, which lead to an mk term in the complexity. Recent work of Basu et al. (2000) removed this assumption at the cost of increasing that term to mk+1, and leading to the quoted complexity, O(mk+1d O(k2) ).
Canny的算法构建了分段代数曲线(路线图)网络,该网络(a)保留自由空间F的连通性,因为F的每个组件都包含一个连通的路线图组件,并且(b)可以通过任何配置访问。构造a将超平面H扫过整个空间,并找出H与障碍物表面相交的所有极点,从而形成“轮廓”曲线。违反(a),这些曲线可能未在F的每个分量内连接。它们在扫描的“关键点”链接在一起,新的极端出现或消失。该连接是通过对路线图算法的递归调用来完成的,这次是在H范围内,因此降低了一个维度。此递归仅导致指数复杂性。通过将初始和最终配置视为关键点,可以将其链接到网络。然后将运动计划简化为搜索路线图。随后,Canny(1988)通过证明路线图算法和路径规划可以在多项式空间中运行来加强结果,因此路径规划问题就在PSPACE中。 Canny的工作还依赖于一般的职位假设,这导致了复杂性的mk术语。 Basu等人的最新工作。 (2000年)删除了这个假设,代价是将该项增加到mk + 1,并导致了引用的复杂度O(mk + 1d O(k2))。

the coordinates of the four endpoints.3 All equations have degree at most 2, so d = 2. Substituting into general motion planning result of O(mk+1d O(k2) ) yields a complexity of O(n4n+22O(n2) ) = 2O(n2) . For small n, this singly exponential complexity is manageable. And indeed, there are implementations that construct complex configuration spaces. For example, Halperin et al. (1998) implemented an “assembly planner” that has successfully solved a problem with more than m = 1,000 constraint surfaces in a configuration space of k =5 dimensions. But for arbitrary n, this algorithm provides only an upper bound on the problem complexity. Although the complexity might appear to be large, it is in some sense close to optimal, for there are environments with m obstacles and mechanisms with k degrees of freedom whose configuration spaces have (mk) (or nearly this many) connected components. For example, if the mechanism is a single link in 3D, k =5, and there is a construction with (m4) components (Ke and O’Rourke 1988). Thus the roadmap complexity of about O(mk+1) is not far from the best possible among algorithms that explicitly construct a representation of the full configuration space. Furthermore, it is PSPACE-hard to decide whether there is a motion between two configurations of a planar tree linkage or of a 3D open chain (Alt et al. 2004), so it is unlikely that subexponential algorithms can solve these general problems. Canny’s result (Canny 1988) establishes that general path planning is in PSPACE; so together these results determine the complexity of these problems as PSPACE-complete.

四个端点的坐标。3所有方程的度数最多为2,因此d =2。代入O(mk + 1d O(k2))的一般运动规划结果将得出O(n4n + 22O(n2) )= 2O(n2)。对于小n来说,这种单指数复杂度是可以控制的。实际上,有些实现构造了复杂的配置空间。例如,Halperin等。 (1998年)实现了一个“装配计划程序”,该程序已成功解决了在k = 5维的配置空间中m = 1,000约束面的问题。但是对于任意n,此算法仅提供问题复杂度的上限。尽管复杂性可能看起来很大,但是在某种意义上,它接近于最佳状态,因为存在具有m个障碍物和k个自由度的机制的环境,其配置空间具有(mk)个(或几乎这么多)连接的组件。例如,如果该机制是3D中的单个链接,则k = 5,并且存在具有(m4)个组件的构造(Ke和O’Rourke 1988)。因此,在显式构造完整配置空间表示形式的算法中,路线图复杂度大约为O(mk + 1)最好。此外,用PSPACE很难确定平面树链接或3D开放链的两种配置之间是否存在运动(Alt等,2004),因此次指数算法不太可能解决这些一般性问题。坎尼(Canny 1988)的结果表明,一般路径规划是在PSPACE中进行的;因此,这些结果共同决定了PSPACE-complete这些问题的复杂性。

2.1.1.2 Solving Problems with Configuration Spaces

Let us briefly sketch how the various problems mentioned in Chapter 1 can be solved with a representation of the configuration space (more specifically, the free space) in hand. 1. Reconfiguration decision question. As mentioned previously, this reduces to locating A and B in the space and asking whether they fall within the same connected component. 2. Reconfiguration path. All the general algorithms permit the construction of a piecewise algebraic path in the space connecting two given points, which we will sketch below. This path specifies a continuous reconfiguration from A to B. 3. Reachability decision question, and path. One can view a reachability question as only providing partial information about B. For example, for a robot arm, usually the coordinates of the “hand” pn are specified, say pn = (xn, yn, zn). Any configurationB = (…, xn, yn, zn) reaches pn, so the decision question reduces to asking if the component of space containing the initial configuration intersects this subspace of configurations. A path requires one point B0 in this intersection and then can be constructed as above. 4. Locked questions. Here the issue is simply this: Does the configuration space consist of more than one connected component? With any reasonable representation of the configuration space, all of these questions can be answered in time proportional to the complexity of that space, perhaps with a small additional overhead. For example, paths are often found as follows. The configuration space is partitioned into cells such that all points within the cell are surrounded by the same set of constraint surfaces. Two adjacent cells share a surface patch that represents a “criticality” of some sort. One then constructs a graph, with a node for each cell and arcs for adjacency, and searches this graph, say using depth-first search. Connectivity in the graph leads to a path in configuration space. The upshot is a generic exponential upper bound, roughly mk, for answering any specific question involving obstacles of complexity m and a mechanism of k degrees of freedom. We should note that this algorithm does not help answering the more general questions we will consider in Chapter 6, such as “Can any 2D chain lock?” because they

让我们简要地概述一下如何用手中的配置空间(更具体地说是自由空间)来解决第1章中提到的各种问题。 1.重新配置决策问题。如前所述,这简化为将A和B定位在空间中,并询问它们是否落入相同的连接组件内。 2.重新配置路径。所有通用算法都允许在连接两个给定点的空间中构造分段代数路径,我们将在下面进行概述。此路径指定了从A到B的连续重新配置。3.可达性决策问题和路径。可以将可到达性问题视为仅提供有关B的部分信息。例如,对于机械手,通常指定“手” pn的坐标,例如pn =(xn,yn,zn)。任何配置B =(…,xn,yn,zn)达到pn,因此决策问题简化为询问包含初始配置的空间分量是否与此配置子空间相交。一条路径在此相交处需要一个点B0,然后可以按上述方法构造。 4.锁定问题。这里的问题很简单:配置空间是否包含多个连接的组件?利用配置空间的任何合理表示,所有这些问题都可以与该空间的复杂性成比例地及时得到回答,也许只需很少的额外开销。例如,通常可以如下找到路径。将配置空间划分为多个单元,以使单元内的所有点都被同一组约束表面围绕。两个相邻的单元共享一个表面斑块,代表某种“临界”状态。然后构造一个图,为每个像元创建一个节点,并为相邻的弧创建一个图,然后使用深度优先搜索搜索该图。图中的连通性导致配置空间中的路径。结果是一个通用的指数上限,大约为mk,用于回答任何涉及复杂性m和k自由度​​机制的特定问题。我们应该注意,该算法无助于回答我们将在第6章中考虑的更一般的问题,例如“任何2D链锁可以锁吗?”

involve an arbitrary number n of links. Nor does the exponential upper bound show that the problems are truly hard; it only shows that the problems are not too hard. In fact we will see that many instances can be solved efficiently. We consider one more example before turning to lower bounds.

包含任意数量的链接。 指数上限也没有表明问题确实很难解决。 它只说明问题不是太难。 实际上,我们将看到许多实例可以有效解决。 在考虑下限之前,我们再考虑一个示例。

【参考 http://www.puzzlesolver.com/list.php?cat=2 ,这儿有很多好玩的谜题啊】

Example: Separation Puzzles

There is a class of puzzles, called “separation” or “take-apart” puzzles, which consist of an arrangement of a collection of distinct, rigid parts, with the goal to separate the parts, to take apart the object.4 Some of these puzzles are extremely difficult to solve, even those which have no hidden parts. Nevertheless all of these puzzles could in theory be solved by a general motion planning algorithm in “constant time,” because for any specific puzzle, the parameters are constant. Consider the clever “Hedgehog in a Cage” puzzle shown in Figure 2.2. It consists of just two rigid parts. The cage could be represented by two squares for the top and bottom and four segments for the bars. The hedgehog could be represented by, say, a dodecahedron and 14 segment spikes (8 short, and 6 long). In terms of the key complexity parameters, k = 6, because the hedgehog has 6 degrees of freedom, and m ≈ 502, because there are about 50 vertices, segments, and faces that pairwise interact to provide constraint surfaces. The combinatorial portion of the complexity of the roadmap algorithm (p. 19) is dominated by the term mk+1; in this case, 5014 > 1023. Regardless of the magnitude of this term, with sufficient time, the roadmap algorithm could create a map for the hedgehog to escape from the cage, as well as solving any other similar take-apart puzzle. We should note that one can generalize separation puzzles to have parameters that increases without bound. For example, the Towers of Hanoi puzzle with n disks, or n disks and k pegs, is such a parameterized puzzle. For such puzzles it does make sense to establish complexity bounds (see, for example, O’Rourke 1998, Section 8.7).

有一类难题,称为“分离”或“拿走”难题,它由一系列截然不同的刚性零件组成,目的是将零件分开,以分解物体。4这些难题非常难以解决,即使那些没有隐藏部分的难题也是如此。尽管如此,所有这些难题在理论上都可以通过通用的运动计划算法在“恒定时间内”解决,因为对于任何特定的难题,参数都是恒定的。考虑一下图2.2中所示的聪明的“笼中的刺猬”难题。它仅由两个刚性部分组成。笼子的顶部和底部可以用两个正方形表示,条形可以用四个部分表示。刺猬可以用十二面体和14个尖峰来表示(短8个,长6个)。就关键复杂度参数而言,k = 6,因为刺猬具有6个自由度,而m≈502,因为大约有50个顶点,线段和面成对相互作用以提供约束表面。路线图算法复杂度的组合部分(第19页)由术语mk + 1支配;在这种情况下,为5014>1023。无论此术语的大小如何,只要有足够的时间,路线图算法就可以为刺猬从笼子中逃脱创建地图,并解决其他类似的搭便车难题。我们应该注意,人们可以将分离难题概括为具有无限增加的参数。例如,带有n个磁盘或n个磁盘和k个钉的“河内塔之谜”就是这样的参数化难题。对于此类难题,建立复杂性界限确实有意义(例如,参见O’Rourke 1998,第8.7节)。

LOWER BOUNDS

In this section we review the early flurry of results that established that several key versions of linkage reachability questions are intractable in the technical, computational complexity sense, and report on the latest status. Four results were published in a period of 6 years, which together settled several basic lower bounds by 1985. Each successive result can be viewed as a strengthening of the one that preceded it. We first sketch the history before describing the constructions. History. Reif obtained the first result: that reachability for a tree-like object of polyhedra connected at point joints, in the presence of polyhedral obstacles, in 3D, is PSPACE-hard (Reif 1979, 1987). Together with Canny’s roadmap algorithm described in Section 2.1.1 and Box 2.2, which establishes that these motion planning problems are in PSPACE, the problem is PSPACE-complete. As a minitutorial, the four complexity classes we are concerned with in this book may be sorted as P ⊆ NP ⊆ PSPACE ⊆ EXP. Here P, polynomial time, is considered efficient or tractable, and EXP, exponential time, is intractable.

在本节中,我们回顾了早期的结果,这些结果确定了链接可达性问题的几个关键版本在技术,计算复杂性方面都是棘手的,并报告了最新状态。在6年内发布了四项结果,这些结果到1985年共同解决了几个基本的下界。每一个连续的结果都可以看作是对之前结果的增强。在描述结构之前,我们首先概述历史。历史。 Reif获得了第一个结果:在3D模式下,在存在多面体障碍的情况下,连接到点关节处的多面体树状对象的可达性是PSPACE困难的(Reif 1979,1987)。结合2.1.1节和框2.2中描述的Canny路线图算法,该算法确定这些运动计划问题在PSPACE中,该问题是PSPACE完整的。作为一个教程,我们在本书中涉及的四个复杂度类别可以分类为PPNPNPPSPACE⊆EXP。在这里,多项式时间P被认为是有效的或易处理的,而指数时间EXP则是难处理的。

Without resolution of the famous P ? = NP question, it remains unknown whether the intermediate classes are truly difficult, but it is widely presumed that they are. The suffix -hard is used to indicate “at least as hard as,” while -complete means “among the hardest questions in that class.” This leads to the following difficulty spectrum: P ⊆ NP-complete ⊆ NP-hard ⊆ PSPACE-complete ⊆ PSPACE-hard ⊆ EXP. We will follow the usual conventions in calling all but P intractable. Reif’s result is well out on this spectrum, and means that the complexity of his reachability question grows more than polynomially (and likely exponentially) with the degrees of freedom of the object, unless P = PSPACE (and in particular P = NP). Reif’s result left two important possibilities unresolved: it might be that a chain (rather than a tree) is easier to reconfigure; and it might be that reachability in 2D is easier than in 3D. Reif’s proof uses both the tree structure and 3D in essential ways. The second question was resolved by Hopcroft, Joseph, and Whitesides (henceforth, HJW), but at the cost of increasing the geometric complexity.

没有解析度的著名P? = NP问题,中间级是否真正困难仍然未知,但人们普遍认为它们确实是困难的。后缀-hard用来表示“至少与之一样困难”,而-complete表示“该类别中最困难的问题之一”。这导致以下困难范围:P⊆NP-完全⊆NP-hard⊆PSPACE- ⊆PSPACE硬⊆EXP。我们将遵循通常的约定称呼除P以外的所有字符都是难处理的。 Reif的结果在这个范围上是很好的,这意味着他的可达性问题的复杂性随着对象的自由度的增长而不是多项式(并且可能呈指数增长),除非P = PSPACE(尤其是P = NP)。 Reif的结果使两个重要的可能性无法解决:可能是链(而不是树)更易于重新配置;而且2D的可达性可能比3D容易。 Reif的证明以必不可少的方式同时使用了树形结构和3D。第二个问题由霍普克罗夫特,约瑟夫和怀特塞德斯(Henceforth,HJW)解决,但代价是增加了几何复杂度。

They proved that the reachability question for a planar graph-linkage, without obstacles and permitting selfintersections, is PSPACE-hard (Hopcroft et al. 1984). In a second paper (Hopcroft et al. 1985) they reduced the geometric complexity from a graph to a path/chain, and established a slightly weaker NP-hardness bound for reachability, this time with a few obstacles, and again permitting self-intersections of the chain. The final early result, by Joseph and Plantinga (1985), strengthens this in a slightly altered form: they prove that reachability, in the presence of many obstacles, is PSPACE-complete. Following this work nearly two decades later, Alt et al. (2004) extended the techniques of Joseph and Plantinga to prove two hardness results without obstacles. First,

他们证明,无障碍且允许自相交的平面图链接的可达性问题是PSPACE难题(Hopcroft等,1984)。 在第二篇论文中(Hopcroft等,1985),他们将几何复杂度从图形降低到路径/链,并建立了较弱的NP硬度以达到可及性,这时有一些障碍,并且再次允许自相交 的。 Joseph and Plantinga(1985)的最终早期结果以稍微改变的形式加强了这一点:他们证明,在有许多障碍的情况下,可达性是PSPACE完全的。 经过将近二十年的这项工作,Alt等人。 (2004)扩展了约瑟夫和普林丁加的技术,以证明两个硬度结果没有障碍。 第一,

deciding reconfigurability of a tree linkage in 2D between two given configurations is PSPACE-complete. Second, the same problem for a chain in 3D is PSPACE-complete. The six results mentioned above are summarized in Table 2.1, including some further details to be explained shortly. Missing from this table is what might be considered the most natural problem: deciding whether a 2D chain can be reconfigured without self-intersection between two specified configurations in the absence of obstacles. The reason for omitting this problem is that here the answer is always yes! This lockability issue is the topic of Chapter 6.

决定两个给定配置之间的2D树链接的可重新配置性是PSPACE-complete。 其次,对于3D链来说,同样的问题是PSPACE-complete。 上面提到的六个结果总结在表2.1中,其中包括一些稍后将要解释的进一步细节。 该表中缺少的是可能被认为是最自然的问题:确定2D链是否可以在没有障碍的情况下在两个指定配置之间没有自相交的情况下重新配置。 忽略此问题的原因是,这里的答案始终是肯定的! 此可锁定性问题是第6章的主题。

Three Constructions Sketched

Reif’s proof reduces acceptance by a particular type of Turing machine, an abstract “automaton” used to prove results in the theory of computation, to the solution of a reachability problem of a tree-linkage P in 3D. The machine M is a space-bounded symmetric Turing machine, whose technical definition need not detain us.5 M “accepts” a word w (that is, M reads w and eventually reaches a special “accepting” state) if and only if an initial configuration of P that depends on w can move through an obstacle course and reach the “exit.” See Figure 2.3 for one (small) section of the obstacle course. The motion of P simulates the Turing machine’s state transitions. Because the acceptance problem for these machines is known to be PSPACE-complete and because Reif’s reduction is not too expensive (technically, “log-space”), the reachability problem is established to be PSPACE-hard. The first HJW proof has a similar high-level structure, but its underlying details are different, and more interesting for our purposes. They reduce the acceptance question

Reif的证明减少了一种特殊类型的Turing机器的接受程度,该机器是用来证明计算理论中结果的抽象“自动机”,用于解决3D中树链接P的可达性问题。机器M是一台空间有界的对称图灵机,其技术定义不必拘泥于我们。5当且仅当以下情况时,M才接受w一词(也就是说,M读w并最终达到特殊的“接受”状态)。取决于w的P的初始配置可以穿过障碍物路线并到达“出口”。有关障碍物路线的一个(较小)部分,请参见图2.3。 P的运动模拟了图灵机的状态转换。由于已知这些机器的验收问题是PSPACE完整的,并且Reif的降低并不是太昂贵(从技术上讲,是“对数空间”),因此可到达性问题被确定为PSPACE困难的。第一个HJW证明具有类似的高级结构,但是其底层细节不同,对于我们的目的而言更有趣。他们减少了接受问题

for another type of machine, a “linear bounded automaton” (or LBA), which again is known to be PSPACE-complete, to a reachability question for a planar linkage. Because the construction is polynomial, again the reachability problem is established to be PSPACE-hard. Without obstacles, however, the complexity has to be embodied in the linkage itself. They require linkages that form a general graph structure. They use joint positions to encode variables and arrange the linkage to restrict the variables to have essentially binary values. At any one time, only one variable can “flip its bit,” so to speak (by moving continuously between two extreme positions). A key linkage used in their proof is one designed by Kempe in 1876 that constructs linkages to “solve” polynomial equations (Kempe 1876). Kempe was concerned with making a linkage to follow any algebraic curve; HJW extend his method to multivariate polynomials. This permits them to implement an AND-gate as x1x2 = 0, and in fact to build linkages to implement any Boolean function. This forms the basis of their LBA reduction. We will explain Kempe’s work, as much for its intrinsic interest as for its application to lower bounds, in Section 3.2

对于另一种类型的机器,“线性有界自动机”(或LBA)又被公认为是PSPACE完整的,它涉及平面连杆机构的可达性问题。由于构造是多项式,因此可到达性问题再次被确定为PSPACE-hard。但是,没有障碍,复杂性必须体现在连杆机构本身中。他们需要形成一般图形结构的链接。他们使用关节位置对变量进行编码,并安排链接以将变量限制为具有基本二进制值。可以这么说(在两个极限位置之间连续移动),在任何时候,只有一个变量可以“翻转其位”。证明中使用的关键链接是由肯佩(Kempe)在1876年设计的,它构造了链接来“解决”多项式方程式(肯佩(Kempe)1876)。肯培(Kempe)关心建立链接以遵循任何代数曲线; HJW将他的方法扩展到多元多项式。这允许他们以x1x2 = 0的方式实现“与”门,并且实际上可以构建链接以实现任何布尔函数。这构成了其LBA降低的基础。我们将在第3.2节中解释Kempe的工作,既出于其内在利益,也涉及其在下界的应用。

Deviating from historical order, the construction of Joseph and Plantinga is similar to Reif’s in its manner of simulation, and similar to HJW’s in that it simulates an LBA. But it accomplishes this with a planar polygonal chain, albeit in the presence of complex obstacles. See Figure 2.4 for a portion of their construction. As mentioned earlier, this thread of research was resumed most recently by Alt et al. (2004), who strengthened some intractability results to hold without obstacles. Their result on tree linkages in 2D follows the Joseph–Plantingua construction, but uses one rigidified portion of the tree to act like the obstacles (such as that in Figure 2.4) needed to construct the gadgets. The tree rigidification is obtained with a locked tree along the lines of Section 6.5 (p. 94). This enables them to prove PSPACE-completeness for trees in 2D. They also extend their 2D construction into a 3D “maze,” using interlocked 3D chains from Chapter 7 (p. 123), which leads to the natural endpoint of this line of research: deciding the reconfigurability of an open chain in 3D is PSPACEcomplete.

与历史顺序不同,Joseph和Plantinga的构造在模拟方式上类似于Reif,在模拟LBA方面则类似于HJW。但是,即使存在复杂的障碍物,它也可以通过平面多边形链来实现。有关其部分结构,请参见图2.4。如前所述,Alt等人最近恢复了这一研究思路。 (2004年),他加强了一些难解决的结果,以保持无障碍。他们在2D中树链接的结果遵循Joseph-Plantingua的构造,但是使用树的一个刚性部分来充当构建小工具所需的障碍(例如图2.4中的障碍)。使用第6.5节(p。94)的锁定树来获得树的加固。这使他们能够证明2D树的PSPACE完整性。他们还使用第7章(第123页)中的互锁3D链将其2D构造扩展为3D“迷宫”,这引出了这一研究领域的自然终点:确定3D中的开放链可重构性是PSPACEcomplete。

The moving chain is C. The backward and forward position of the “switch” whose tip is x encodes the bit 0 and 1. The gadget shown checks the bit in the sense that if C starts below the obstacle A with the switch backward as in (a), it cannot move to above A. If, however, the switch is initially forward as in (b), x can enter the circular well and open enough to shorten the chain, permitting passage to above A. (After Figure 5 of Joseph and Plantinga 1985.)

移动链为C。尖端为x的“开关”的前进和后退位置编码位0和1。所示小工具从以下角度检查该位,即C是否从障碍物A下方开始,且开关向后移动,如 (a),它不能移动到A上方。但是,如果开关最初如(b)所示是向前的,则x可以进入圆形孔并充分打开以缩短链条,从而允许到达A上方。(图5之后) 约瑟夫和普林廷加(1985)。

Ruler folding. The earlier proof of HJW that reachability for a planar polygonal chain is NP-hard is a simple and beautiful argument that has served as a model for several later proofs. It is the only one we present in detail. They start with the ruler folding problem: Ruler Folding: Given a polygonal chain with links of integer lengths 0, …, n−1 and an integer L, can the chain be folded flat—reconfigured so that each joint angle is either 0 or π—so that its total folded length is ≤ L? Here the chain may self-cross, and there are no obstacles. So any move is legal. And yet they prove the problem is difficult: Theorem 2.2.1 (Hopcroft et al. 1985).

标尺折叠。 HJW的较早的证明是平面多边形链的可达性是NP-hard,这是一个简单而优美的论据,已作为后来几个证明的模型。 这是我们详细介绍的唯一内容。 它们从标尺折叠问题开始:标尺折叠:给定一个具有整数长度0,…,n-1和整数L的链接的多边形链,可以将链折叠成扁平状—重新配置为使每个关节角度为 是0还是π-使其总折叠长度≤L? 在这里,链条可以自动交叉,没有障碍。 因此,任何举动都是合法的。 但是他们证明了这个问题是困难的:定理2.2.1(Hopcroft et al。1985)。

The ruler folding problem is NP-complete. Proof: The proof is by reduction from Set Partition (henceforth: partition), a known NP-complete problem:6 partition: Given a set of n positive integers, S = {x1, …, xn}, does there exist a partition of S into A ⊆ S and B ⊆ S so that xi∈A xi = xj∈B xj? (2.1) From a given instance of partition, a ruler is constructed as follows. Let s = n i=1 xi be the sum of all the elements in S. The ruler R consists of links of lengths (0, 1, 2, …, n+1, n+2, n+3) = (2s, s, x1, …, xn, s, 2s). The claim is that R can be folded into a length of at most 2s if and only if the instance of partition has the answer yes. 6 This problem isweakly NP-complete, meaning that it is NP-complete as a function ofn and the binary encoding of the input numbers, but if the integers were written in unary notation (thus inflating the input size), the problem might become polynomial, and so admit a “pseudopolynomial-time algorithm.”

标尺折叠问题是NP完全的。 证明:证明是通过减少一个已知的NP完全问题的Set Partition(以下称“ partition”)来完成的:6 partition:给定一组n个正整数,S = {x1,…,xn},是否存在 将S分为A⊆S和B⊆S,这样xi∈Axi =xj∈Bxj? (2.1)从给定的分区实例中,按以下方式构造标尺。 令s = ni = 1 xi是S中所有元素的总和。标尺R由长度为(0、1、2,…,n + 1,n + 2, n + 3)=(2s,s,x1,…,xn,s,2s)。 声称只有当分区实例的答案为“是”时,R才可以折叠为最多2s的长度。 6这个问题是弱NP完全的,这意味着它是n和输入数字的二进制编码的函数的NP完全,但是如果整数是用一元符号表示的(因此增大了输入大小),则问题可能变成多项式 ,因此接受“伪多项式时间算法”。

Consider the links directed from vi to vi+1, and fold the ruler along the real line, with v0 = 0 and v1 = 2s. The vertices v2 and vn+2 must both lie at s if all is to fit within [0, 2s]. This forces the links between to consume zero total displacement: so the sum of the leftward-pointing links must equal the sum of the rightward-pointing links (see Figure 2.5). Therefore R folds into 2s if and only if {x1, …, xn} can be partitioned into two equal-length halves. It is clear that it cannot fold to < 2s, because there are links of that length.

考虑从vi到vi + 1的链接,并沿着实线折叠标尺,其中v0 = 0,v1 = 2s。 如果所有顶点都在[0,2s]内,则顶点v2和vn + 2必须都位于s上。 这迫使链接之间的总位移为零:因此,向左链接的总和必须等于向右链接的总和(见图2.5)。 因此,当且仅当{x1,…,xn}可以分为两个等长的一半时,R才会折叠为2s。 显然,它不能折叠到<2s,因为存在该长度的链接。

So we have established the claim for L = 2s. Recently a “fully polynomial-time approximation scheme”7 has been found for finding the minimum folding length of a ruler (Calinescu and Dumitrescu 2005). ˇ This folding problem does not fit one of the “standard” varieties we outlined earlier (in Section 1.1), but it can be used to establish the intractability of planar arm reachability: Theorem 2.2.2 (Hopcroft et al. 1985). Whether a planar polygonal chain can reach a given point p, in the presence of obstacles but permitting the chain to self-intersect, is NP-hard.

因此,我们确定了L = 2s的要求。 最近,已经找到了一种“完全多项式时间近似方案” 7,用于寻找直尺的最小折叠长度(Calinescu和Dumitrescu 2005)。 folding这个折叠问题不适合我们前面(第1.1节)中概述的“标准”品种之一,但是可以用来建立平面臂伸直性的难处理性:定理2.2.2(Hopcroft等,1985)。 在有障碍物的情况下,平面多边形链是否可以到达给定点p,但允许链自动相交,这是NP困难的。

Proof: Let a ruler folding problem specify a ruler R of total stretched length L. We construct a reachability problem as follows. A chain C, anchored at the origin v0 = (0, 0), consists of 100L + 1 unit-length links, followed by links whose lengths are 100 times those in R. Call this latter portion of the chain R100. The obstacles consist of four segments, as illustrated in Figure 2.6: three sides of a 100(L + k) × (2 + ε) rectangle, forming a “tunnel,” and one long segment s of length 201L nearly touching v0. The tunnel width is 2 + ε for some small ε > 0 to permit unit-length segments to turn around in the tunnel avoiding contact with the tunnel walls. We now argue that the hand endpoint at the end of R100, call it v, can reach p = (200L, 1) if and only if R can be folded to length ≤ k.

证明:让标尺折叠问题指定总伸展长度L的标尺R。我们构造如下可达性问题。 链C锚定在原点v0 =(0,0)上,由100L + 1个单位长度的链接组成,后跟链接长度为R中的长度的100倍的链接。将其称为链R100的后一部分。 障碍物包括四个部分,如图2.6所示:一个100(L + k)×(2 +ε)矩形的三个边,形成一个“隧道”,一个长201L的长段s接近v0。 对于一些小的ε> 0,隧道宽度为2 +ε,以允许单位长度的段在隧道中转弯,从而避免与隧道壁接触。 现在我们争论,当且仅当R可以折叠成长度≤k时,R100末端的手端点称为v,才能达到p =(200L,1)。

The construction ensures that p can only be reached if the ruler enters the tunnel and passes through the 100k “gap” to the left of the origin. The shortest link of R100 has length 100 (because the links of R are integers); so once inside the thin tunnel, it is unable to rotate more than slightly. Thus only if R100 folds to at most 100k might p be reached. On the other hand, the unit-length links of C have enough room to rotate inside the tunnel. Thus, if R100 does indeed fold to gap length, then p may be reached by the following sequence: first fold R100 outside the tunnel, draw it inside the tunnel by crumpling the 100L unit links, unfurl 100k of them to position the folded R100 as illustrated in (b) of the figure, pass the folded ruler through the unit links into the upper half of the tunnel, and finally extend out toward p. The distance from v0 to p is  (200L)2 + 1, and C has length 200L + 1, more than enough to reach p.

这种构造确保只有在直尺进入隧道并穿过原点左侧的100k“间隙”时才能达到p。 R100的最短链接的长度为100(因为R的链接是整数); 因此,一旦进入细隧道,它就无法旋转得更多。 因此,只有R100折叠到最多100k时,才能达到p。 另一方面,C的单位长度链接具有足够的空间在隧道内旋转。 因此,如果确实将R100折叠到间隙长度,则可以通过以下顺序达到p:首先将R100折叠到隧道外部,通过将100L单元链节弄皱将其拉入隧道内部,解开它们的100k以将折叠的R100定位为 如图(b)所示,将折叠的直尺穿过单元链环进入隧道的上半部,最后朝p方向伸出。 从v0到p的距离为(200L)2 + 1,C的长度为200L +1,足以达到p。

Figure 2.6. (a) Initial configuration. The dashed segment starting from v0 represents a large collection of unit links. The slashes indicate interruptions. Note the tunnel is only 2 + ε units high. (b) Intermediate configuration, when R100 is folded and about to pass through the gap.

图2.6。 (a)初始配置。 从v0开始的虚线段表示大量的单元链接。 斜线表示中断。 请注意,隧道仅高2 +ε个单位。 (b)中间配置,当R100折叠并即将通过间隙时。

Path planning. The three intractability results that simulate automata with linkage problems all also establish an exponential lower bound on path planning versions of the problems, because they each require an exponential number of “elementary moves” of the linkage, under any reasonable definition of “elementary.” The ruler folding proof is fundamentally different: the number of moves needed to reach p is polynomial (in fact, linear) in n; what is difficult is finding the moves. Although the results in Table 2.1 establish that sufficiently rich linkage problems are intractable, room remains for efficient (polynomial-time) algorithms in at least two directions. First, all these results rely on arbitrarily long or complex linkages. As soon as the number of degrees of freedom is fixed, the Roadmap Algorithm (Box 2.2) shows there are polynomial algorithms.

路径规划。 模拟具有链接问题的自动机的三个难处理性结果,也都在问题的路径规划版本上建立了指数下限,因为在任何“基本”的合理定义下,它们每个都需要指数数量的链接“基本动作”。 标尺折叠证明从根本上是不同的:达到p所需的移动次数是n中的多项式(实际上是线性的)。 很难找到动作。 尽管表2.1中的结果表明,足够复杂的链接问题是棘手的,但仍有必要在至少两个方向上为有效(多项式时间)算法提供空间。 首先,所有这些结果都依赖于任意长或复杂的链接。 一旦确定了自由度的数量,路线图算法(框2.2)就会显示存在多项式算法。

Second, the various assumptions on the intersection conditions and the number and type of obstacles are often important to the proofs, and with different assumptions the complexity could change. For example, we will see in Section 5.1 that reducing the number of obstacles from four segments to none in Theorem 2.2.2 (line 3 of Table 2.1) drops the complexity from NP-hard to O(n)! Universality theorem. It remains true, however, that the most general linkage problems are intractable. This was recently given a strong form via a general “universality theorem,” established in slightly different forms by Jordan and Steiner (1999) and by Kapovich and Millson (2002). Theorem 2.2.3. Let X ⊆ Rd be a compact real algebraic variety, i.e., the locus of zeros of a polynomial in d variables. Then X is homeomorphic 8 to some components of the configuration space of a planar linkage.

其次,关于交叉路口条件以及障碍物的数量和类型的各种假设通常对证明很重要,并且在不同的假设下复杂性可能会发生变化。 例如,我们将在5.1节中看到,在定理2.2.2(表2.1的第3行)中将障碍物的数量从四个段减少到无,将复杂度从NP-hard降低到O(n)! 普遍性定理。 然而,最普遍的联系问题仍然是棘手的。 乔丹和斯坦纳(1999)以及卡波维奇和密尔森(2002)以略有不同的形式建立了一个通用的“大学定理”,从而为这提供了强大的形式。 定理2.2.3。 令X⊆Rd是紧实的代数变体,即d变量中多项式的零的轨迹。 那么X对平面连接的配置空间的某些分量是同胚的8。

Intuitively this says that the configuration space of a linkage can be as complicated as can be specified algebraically. See Connelly and Demaine (2004), O’Hara (2005), and Shimamoto and Vanderwaart (2005) for discussions of this complex topic. We will return to universality in a particularly appealing form (there is a linkage with a joint whose “orbit” follows any given algebraic curve) in Section 3.2.

从直觉上讲,这意味着链接的配置空间可以像代数指定的那样复杂。 有关这个复杂主题的讨论,请参见Connelly和Demaine(2004),O’Hara(2005)以及Shimamoto和Vanderwaart(2005)。 在第3.2节中,我们将以一种特别吸引人的形式(存在一个与关节的链接,其“轨道”遵循任何给定的代数曲线)回归普遍性。

【我借助google翻译看完第二章,大概知道了这本书大概是讲空间几何。刚好看到youtube上很多复杂精巧的机械结构,不知道怎么制作成,这本书讲了很多这背后的机械结构的数学原因,有点看matrix67的感觉。还不错,这本书还没有中译本。我是如何发现这本书的?在Arixv上搜索“机器学习”方面的论文,看到一个名词“Graph embedding”图嵌入,于是在知乎上搜图嵌入,看着看着,发现有个名词看不懂,即“卷积编码器”,于是又去搜博文, 这篇https://www.cnblogs.com/ncdxlxk/p/9240938.html 博主在其中提到了本文翻译自 ”MIT 6.02 DRAFT Lecture Notes, 2012”CHAPTER 8:Viterbi Decoding of Convolutional Codes。MIT lecture notes?好东西,上面一搜,于是这本书就是某计算机课程的教材(还是课外读物?忘了)。我搜索的能力太强了哈哈。】

收获

【参考 http://www.puzzlesolver.com/list.php?cat=2 ,这儿有很多好玩的谜题啊】

Wooden “Hedgehog in a Cage” puzzle ,youtube上貌似只有两个视频介绍这个,好冷门啊,不过好好玩,稍微聪明的初中生大概能花一节课解出?

Leave a Reply