6 Matching Results

Search Results

Advanced search parameters have been applied.

A generic algorithm for constructing hierarchical representations of geometric objects

Description: For a number of years, robotics researchers have exploited hierarchical representations of geometrical objects and scenes in motion-planning, collision-avoidance, and simulation. However, few general techniques exist for automatically constructing them. We present a generic, bottom-up algorithm that uses a heuristic clustering technique to produced balanced, coherent hierarchies. Its worst-case running time is O(N{sup 2}logN), but for non-pathological cases it is O(NlogN), where N is the number of input primitives. We have completed a preliminary C++ implementation for input collections of 3D convex polygons and 3D convex polyhedra and conducted simple experiments with scenes of up to 12,000 polygons, which take only a few minutes to process. We present examples using spheres and convex hulls as hierarchy primitives.
Date: October 1, 1995
Creator: Xavier, P.G.
Partner: UNT Libraries Government Documents Department

Shortest Path Planning for a Tethered Robot or an Anchored Cable

Description: We consider the problem of planning shortest paths for a tethered robot with a finite length tether in a 2D environment with polygonal obstacles. We present an algorithm that runs in time O((k{sub 1} + 1){sup 2}n{sup 4}) and finds the shortest path or correctly determines that none exists that obeys the constraints; here n is the number obstacle vertices, and k{sub 1} is the number loops in the initial configuration of the tether. The robot may cross its tether but nothing can cross obstacles, which cause the tether to bend. The algorithm applies as well for planning a shortest path for the free end of an anchored cable.
Date: February 22, 1999
Creator: Xavier, P.G.
Partner: UNT Libraries Government Documents Department

A configuration space toolkit for automated spatial reasoning: Technical results and LDRD project final report

Description: A robot`s configuration space (c-space) is the space of its kinematic degrees of freedom, e.g., the joint-space of an arm. Sets in c-space can be defined that characterize a variety of spatial relationships, such as contact between the robot and its environment. C-space techniques have been fundamental to research progress in areas such as motion planning and physically-based reasoning. However, practical progress has been slowed by the difficulty of implementing the c-space abstraction inside each application. For this reason, we proposed a Configuration Space Toolkit of high-performance algorithms and data structures meeting these needs. Our intent was to develop this robotics software to provide enabling technology to emerging applications that apply the c-space abstraction, such as advanced motion planning, teleoperation supervision, mechanism functional analysis, and design tools. This final report presents the research results and technical achievements of this LDRD project. Key results and achievements included (1) a hybrid Common LISP/C prototype that implements the basic C-Space abstraction, (2) a new, generic, algorithm for constructing hierarchical geometric representations, and (3) a C++ implementation of an algorithm for fast distance computation, interference detection, and c-space point-classification. Since the project conclusion, motion planning researchers in Sandia`s Intelligent Systems and Robotics Center have been using the CSTk libcstk.so C++ library. The code continues to be used, supported, and improved by projects in the ISRC.
Date: February 1, 1997
Creator: Xavier, P.G. & LaFarge, R.A.
Partner: UNT Libraries Government Documents Department

Fast swept-volume distance for robust collision detection

Description: The need for collision detection arises in several robotics areas, including motion-planning, online collision avoidance, and simulation. At the heart of most current methods are algorithms for interference detection and/or distance computation. A few recent algorithms and implementations are very fast, but to use them for accurate collision detection, very small step sizes can be necessary, reducing their effective efficiency. We present a fast, implemented technique for doing exact distance computation and interference detection for translationally-swept bodies. For rotationally swept bodies, we adapt this technique to improve accuracy, for any given step size, in distance computation and interference detection. We present preliminary experiments that show that the combination of basic and swept-body calculations holds much promise for faster accurate collision detection.
Date: April 1, 1997
Creator: Xavier, P.G.
Partner: UNT Libraries Government Documents Department

Simulation and off-line programming at Sandia`s Intelligent Systems and Robotics Center

Description: One role of the Intelligent Robotics and System Center (ISRC) at Sandia National Laboratories is to address certain aspects of Sandia`s mission to design, manufacture, maintain, and dismantle nuclear weapon components. Hazardous materials, devices, and environments are often involved. Because of shrinking resources, these tasks must be accomplished with a minimum of prototyping, while maintaining high reliability. In this paper, the authors describe simulation, off-line programming/planning, and related tools which are in use, under development, and being researched to solve these problems at the ISRC.
Date: November 1, 1997
Creator: Xavier, P.G.; Fahrenholtz, J.C. & McDonald, M.
Partner: UNT Libraries Government Documents Department

Coordinating robot motion, sensing, and control in plans. LDRD project final report

Description: The goal of this project was to develop a framework for robotic planning and execution that provides a continuum of adaptability with respect to model incompleteness, model error, and sensing error. For example, dividing robot motion into gross-motion planning, fine-motion planning, and sensor-augmented control had yielded productive research and solutions to individual problems. Unfortunately, these techniques could only be combined by hand with ad hoc methods and were restricted to systems where all kinematics are completely modeled in planning. The original intent was to develop methods for understanding and autonomously synthesizing plans that coordinate motion, sensing, and control. The project considered this problem from several perspectives. Results included (1) theoretical methods to combine and extend gross-motion and fine-motion planning; (2) preliminary work in flexible-object manipulation and an implementable algorithm for planning shortest paths through obstacles for the free-end of an anchored cable; (3) development and implementation of a fast swept-body distance algorithm; and (4) integration of Sandia`s C-Space Toolkit geometry engine and SANDROS motion planer and improvements, which yielded a system practical for everyday motion planning, with path-segment planning at interactive speeds. Results (3) and (4) have either led to follow-on work or are being used in current projects, and they believe that (2) will eventually be also.
Date: August 1, 1997
Creator: Xavier, P.G.; Brown, R.G. & Watterberg, P.A.
Partner: UNT Libraries Government Documents Department