Publications

Abstract not provided.

This article discusses likely future contexts of, and options for, global threat-reduction activities to support nonproliferation goals over the next five to ten years. Threat-reduction activities span a continuum from unilateral actions that the United States might take with little cooperation and transparency at one end to cooperative actions associated with negotiated treaties and agreements at the other. This study focuses on cooperative approaches embodied in the Cooperative Threat Reduction (CTR) program, which has been the most visible program reducing the threats posed by weapons of mass destruction for over two decades. Here, we argue that CTR’s evolution can be described in terms of the relationship between the desired US influence on outcomes, the ability to generate a common threat definition, and appetite for collaboration on threat reduction. To that end, this article provides an introduction and overview of CTR initiatives over its twenty-seven-year history and a review of relevant legislation and trends. After introducing and describing the CTR Possible Futures Framework, this article offers five possible options for—and discusses the implications of—CTR’s future evolution.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

Abstract not provided.

The authors study the following problem: given a collection A of polyhedral parts in 3D, determine whether there exists a subset S of the parts that can be moved as a rigid body by an infinitesimal translation and rotation, without colliding with the rest of the parts, A/S. A negative result implies that the object whose constituent parts are the collection A cannot be taken apart with two hands. A positive result, together with the list of movable parts in S and a direction of motion for S, can be used by an assembly sequence planner. This problem has attracted considerable attention within and outside the robotics community. They devise an efficient algorithm to solve this problem. The solution is based on the ability to focus on selected portions of the tangent space of rigid motions and efficiently access these portions. The algorithm is complete (in the sense that it is guaranteed to find a solution if one exists), simple, and improves significantly over the best previously known solutions. The authors report experimental results with an implementation of their algorithm.

Despite intensive efforts in the area of dynamic graph algorithms, no efficient algorithms are known for the dynamic versions of some basic graph problems such as strong connectivity and transitive closure. We provide some explanation for this lack of success by presenting quadratic lower bounds on the strong certificate complexity of such problems, thereby establishing the inapplicability of the only known general technique for designing dynamic graph algorithms, viz., sparsification. These results also provide evidence of the inherent intractability of such dynamic graph problems. Some of our results are based on a general technique for obtaining lower bounds on the strong certificate complexity for a class of graph properties by establishing a relationship with the witness complexity. In many real applications of dynamic graph problems, a certain amount of lookahead is available. Specifically, we consider the problems of assembly planning in robotics and the maintenance of relations in databases which, respectively, give rise to dynamic strong connectivity and transitive closure. We exploit the (naturally available) lookahead in these two applications to circumvent the inherent complexity of the dynamic graph problems. We propose a variant of sparsification, viz., lookahead based sparsification, and apply it to obtain the first efficient fully dynamic algorithms for strong connectivity and transitive closure.

The authors consider the following problem that arises in assembly planning: given an assembly, identify a subassembly that can be removed as a rigid object without disturbing the rest of the assembly. This is the assembly partitioning problem. Specifically, they consider planar assemblies of simple polygons and subassembly removal paths consisting of a single finite translation followed by a translation to infinity. They show that such a subassembly and removal path can be determined in O(n{sup 1.46}N{sup 6}) time, where n is the number of polygons in the assembly and N is the total number of edges and vertices of all the parts together. They then extend this formulation to removal paths consisting of a small number of finite translations, followed by a translation to infinity. In this case the algorithm runs in time polynomial in the number of parts, but exponential in the number of translations a path may contain.