Search

Abstract: Approximate convex decomposition (ACD) is a technique that partitions an input object into approximately convex components. Decomposition into approximately convex pieces is both more efficient to compute than exact convex decomposition and can also generate a more manageable number of components. It can be used as a basis of divide-and-conquer algorithms for applications such as collision detection, skeleton extraction and mesh generation. In this paper, we propose a new method called Fast Approximate Convex Decomposition (FACD) that improves the quality of the decomposition and reduces the cost of computing it for both 2D and 3D models. In particular, we propose a new strategy for evaluating potential cuts that aims to reduce the relative concavity, rather than absolute concavity. As shown in our results, this leads to more natural and smaller decompositions that include components for small but important features such as toes or fingers while not decomposing larger components, such as the torso, that may have concavities due to surface texture. Second, instead of decomposing a component into two pieces at each step, as in the original ACD, we propose a new strategy that uses a dynamic programming approach to select a set of non-crossing (independent) cuts that can be simultaneously applied to decompose the component into components. This reduces the depth of recursion and, together with a more efficient method for computing the concavity measure, leads to significant gains in efficiency. We provide comparative results for 2D and 3D models illustrating the improvements obtained by FACD over ACD and we compare with the segmentation methods in the Princeton Shape Benchmark by Chen et al. (2009) [31]. [Copyright &y& Elsevier]

Abstract: Decomposition is a technique commonly used to partition complex models into simpler components. While decomposition into convex components results in pieces that are easy to process, such decompositions can be costly to construct and can result in representations with an unmanageable number of components. In this paper we explore an alternative partitioning strategy that decomposes a given model into “approximately convex” pieces that may provide similar benefits as convex components, while the resulting decomposition is both significantly smaller (typically by orders of magnitude) and can be computed more efficiently. Indeed, for many applications, an approximate convex decomposition (acd) can more accurately represent the important structural features of the model by providing a mechanism for ignoring less significant features, such as surface texture. We describe a technique for computing acds of three-dimensional polyhedral solids and surfaces of arbitrary genus. We provide results illustrating that our approach results in high quality decompositions with very few components and applications showing that comparable or better results can be obtained using acd decompositions in place of exact convex decompositions (ecd) that are several orders of magnitude larger. [Copyright &y& Elsevier]

Abstract: We propose a strategy to decompose a polygon, containing zero or more holes, into “approximately convex” pieces. For many applications, the approximately convex components of this decomposition provide similar benefits as convex components, while the resulting decomposition is significantly smaller and can be computed more efficiently. Moreover, our approximate convex decomposition (ACD) provides a mechanism to focus on key structural features and ignore less significant artifacts such as wrinkles and surface texture. We propose a simple algorithm that computes an ACD of a polygon by iteratively removing (resolving) the most significant non-convex feature (notch). As a by product, it produces an elegant hierarchical representation that provides a series of ‘increasingly convex’ decompositions. A user specified tolerance determines the degree of concavity that will be allowed in the lowest level of the hierarchy. Our algorithm computes an ACD of a simple polygon with n vertices and r notches in time. In contrast, exact convex decomposition is NP-hard or, if the polygon has no holes, takes time. Models and movies can be found on our web-pages at: http://parasol.tamu.edu/groups/amatogroup/. [Copyright &y& Elsevier]

"Variational Hilbert regression for terrain modeling and trajectory optimization", by V Guizilini and F Ramos, describes a novel regression methodology for modeling terrains. "Learning to calibrate: Reinforcement learning for guided calibration of visual-inertial rigs", by F Nobre and C Heckman, presents a calibration system that guides the operator by suggesting easy motions where calibration parameters can be observed. "Communicating and controlling robot arm motion intent through mixed reality head-mounted displays", by E Rosen, D Whitney, E Phillips, G Chien, J Tompkin, G Konidaris, and S Tellex, expresses the robot arm's intended motion to a collaborating human operator. [Extracted from the article]

In this paper, we present a framework for studying folding problems from a motion-planning perspective. The version of the motion-planning problem we consider is that of determining a sequence of motions to transform some configuration of a foldable object (the start) into another configuration (the goal). Modeling foldable objects as tree-like multilink objects allows us to apply motion-planning techniques for articulated objects with many degrees of freedom (many links) to folding problems. An important feature of this approach is that it not only allows us to study foldability questions, such as, can one object be folded (or unfolded) into another object, but it also provides us with another tool for investigating the dynamic folding process itself. The frame-work proposed here has application to traditional motion-planning areas such as automation and animation, to paper-folding problems studied in computational geometry, and to computational biology problems such as protein folding. Preliminary experimental results with paper folding and the folding of small proteins (approximately 60 residues) are quite encouraging. [ABSTRACT FROM AUTHOR]

Presents a comparative evaluation of different distance metrics and local planners within the context of probabilistic roadmap (PRM) methods for planning the motion of rigid objects in three-dimensional workspaces. Use of distance metrics and local planners; Recommendations for selecting appropriate combinations of distance metrics and local planners.

The author reflects on the issues covered in the August 2006 issue of the journal. It describes high-performance computational biology as the development and application of high-performance computing techniques for extending the reach or scale of investigations in computational biology. It presents an outline of the topics discussed that includes the scalable implementation of the widely used BLAST search program for homology detection between a query sequence and a database of known sequences.

An introduction is presented in which the editor discusses various reports within the issue on topics including an algorithm for producing a flight plan for an aerial robot; methods to prevent chattering by placing costs on switching in the industry; and approaches for multi-robot systems.

The article discusses various reports published within the issue including one by Leonard Jaillet and Thierry Simeon on traditional probabilistic roadmap motion planning methods and another by Yunfeng Wang and Gregory Chirikjian on error propagation in rigid-body in robotics.

Motion planning for constrained systems is a version of the motion planning problem in which the motion of a robot is limited by constraints. For example, one can require that a humanoid robot such as a PR2 remain upright by constraining its torso to be above its base or require that an object such as a bucket of water remain upright by constraining the vertices of the object to be parallel to the robot’s base. Grasping can be modeled by requiring that the end effectors of the robot be located at specified handle positions. Constraints might require that the robot remain in contact with a surface, or that certain joints of the robot remain in contact with each other (e.g., closed chains). Such problems are particularly difficult because the constraints form a manifold in C-space, and planning must be restricted to this manifold. High-degree-of-freedom motion planning and motion planning for constrained systems has applications in parallel robotics, grasping and manipulation, computational biology and molecular simulations, and animation. We introduce a new concept, reachable volumes, that are a geometric representation of the regions the joints and end effectors of a robot can reach, and use it to define a new planning space called RV-space where all points automatically satisfy a problem’s constraints. Visualizations of reachable volumes can enable operators to see the regions of workspace that different parts of the robot can reach. Samples and paths generated in RV-space naturally conform to constraints, making planning for constrained systems no more difficult than planning for unconstrained systems. Consequently, constrained motion planning problems that were previously difficult or unsolvable become manageable and in many cases trivial. We introduce tools and techniques to extend the state-of-the-art sampling-based motion planning algorithms to RV-space. We define a reachable volumes sampler, a reachable volumes local planner, and a reachable volumes distance metric. We showcase the effectiveness of RV-space by applying these tools to motion planning problems for robots with constraints on the end effectors and/or internal joints of the robot. We show that RV-based planners are more efficient than existing methods, particularly for higher-dimensional problems, solving problems with 1000 or more degrees of freedom for multi-loop and tree-like linkages. [ABSTRACT FROM AUTHOR]

Background: Simulating protein folding motions is an important problem in computational biology. Motion planning algorithms, such as Probabilistic Roadmap Methods, have been successful in modeling the folding landscape. Probabilistic Roadmap Methods and variants contain several phases (i.e., sampling, connection, and path extraction). Most of the time is spent in the connection phase and selecting which variant to employ is a difficult task. Global machine learning has been applied to the connection phase but is inefficient in situations with varying topology, such as those typical of folding landscapes. Results: We develop a local learning algorithm that exploits the past performance of methods within the neighborhood of the current connection attempts as a basis for learning. It is sensitive not only to different types of landscapes but also to differing regions in the landscape itself, removing the need to explicitly partition the landscape. We perform experiments on 23 proteins of varying secondary structure makeup with 52-114 residues. We compare the success rate when using our methods and other methods. We demonstrate a clear need for learning (i.e., only learning methods were able to validate against all available experimental data) and show that local learning is superior to global learning producing, in many cases, significantly higher quality results than the other methods. Conclusions: We present an algorithm that uses local learning to select appropriate connection methods in the context of roadmap construction for protein folding. Our method removes the burden of deciding which method to use, leverages the strengths of the individual input methods, and it is extendable to include other future connection methods. [ABSTRACT FROM AUTHOR]

In this paper we present feedback-based information roadmap (FIRM), a multi-query approach for planning under uncertainty which is a belief-space variant of probabilistic roadmap methods. The crucial feature of FIRM is that the costs associated with the edges are independent of each other, and in this sense it is the first method that generates a graph in belief space that preserves the optimal substructure property. From a practical point of view, FIRM is a robust and reliable planning framework. It is robust since the solution is a feedback and there is no need for expensive replanning. It is reliable because accurate collision probabilities can be computed along the edges. In addition, FIRM is a scalable framework, where the complexity of planning with FIRM is a constant multiplier of the complexity of planning with PRM. In this paper, FIRM is introduced as an abstract framework. As a concrete instantiation of FIRM, we adopt stationary linear quadratic Gaussian (SLQG) controllers as belief stabilizers and introduce the so-called SLQG-FIRM. In SLQG-FIRM we focus on kinematic systems and then extend to dynamical systems by sampling in the equilibrium space. We investigate the performance of SLQG-FIRM in different scenarios. [ABSTRACT FROM PUBLISHER]

We consider three related problems of robot movement in arbitrary dimensions: coverage, search, and navigation. For each problem, a spherical robot is asked to accomplish a motion-related task in an unknown environment whose geometry is learned by the robot during navigation. The robot is assumed to have tactile and global positioning sensors. We view these problems from the perspective of (non-linear) competitiveness as defined by Gabriely and Rimon. We first show that in 3 dimensions and higher, there is no upper bound on competitiveness: every online algorithm can do arbitrarily badly compared to the optimal. We then modify the problems by assuming a fixed clearance parameter. We are able to give optimally competitive algorithms under this assumption. We show that these modified problems have polynomial competitiveness in the optimal path length, of degree equal to the dimension. [ABSTRACT FROM AUTHOR]

The problem addressed is the distributed reconfiguration of a system of hexagonal metamorphic robots (modules) from an initial straight chain to a goal configuration that satisfies a simple admissibility condition. Our reconfiguration strategy depends on finding a contiguous path of cells that spans the goal configuration and over which modules can move concurrently without collision or deadlock, called an admissible substrate path. A subset of modules first occupy the admissible substrate path, which is then traversed by other modules to fill in the remainder of the goal. We present a two-phase reconfiguration strategy, beginning with a centralized preprocessing phase that finds and heuristically ranks all admissible substrate paths in the goal configuration, according to which path is likely to result in fast parallel reconfiguration. We prove the correctness of our path-finding algorithm and demonstrate its effectiveness through simulation. The second phase of reconfiguration is accomplished by a deterministic, distributed algorithm that uses little or no intermodule message passing. [ABSTRACT FROM AUTHOR]

The problem we address is the distributed reconfiguration of a planar metamorphic robotic system composed of any number of hexagonal modules. After presenting a framework for classifying motion planning algorithms for metamorphic robotic systems, we describe distributed algorithms for reconfiguring a straight chain of hexagonal modules to any intersecting straight chain configuration. We prove our algorithms are correct, and show that they are either optimal or asymptotically optimal in the number of moves and asymptotically optimal in the time required for parallel reconfiguration. [ABSTRACT FROM AUTHOR]

The brain''s extraordinary computational power to represent and interpret complex natural environments is essentially determined by the topology and geometry of the brain''s architectures. We present a framework to construct cortical networks which borrows from probabilistic roadmap methods developed for robotic motion planning. We abstract the network as a large-scale directed graph, and use L-systems and statistical data to ‘grow’ neurons that are morphologically indistinguishable from real neurons. We detect connections (synapses) between neurons using geometric proximity tests. [Copyright &y& Elsevier]

The problem addressed is the distributed reconfiguration of a metamorphic robotic system composed of an arbitrary number of two-dimensional hexagonal robots (modules) from specific initial to specific goal configurations. The initial configuration considered is a straight chain of robotic modules, while the goal configurations considered satisfy a more general "admissibility" condition. A centralized algorithm is described for determining whether an arbitrary goal configuration is admissible. We prove this algorithm correctly identifies admissible goal configurations and finds a "substrate path" within the goal configuration, along which the modules can move to reach their positions in the goal. A second result of the paper is a distributed algorithm for reconfiguring a straight chain into an admissible goal configuration. Different heuristics are proposed to improve the performance of the reconfiguration algorithm and simulation results demonstrate the use of these heuristics. [ABSTRACT FROM AUTHOR]

Simultaneous localization and planning (SLAP) is a crucial ability for an autonomous robot operating under uncertainty. In its most general form, SLAP induces a continuous partially observable Markov decision process (POMDP), which needs to be repeatedly solved online. This paper addresses this problem and proposes a dynamic replanning scheme in belief space. The underlying POMDP, which is continuous in state, action, and observation space, is approximated offline via sampling-based methods, but operates in a replanning loop online to admit local improvements to the coarse offline policy. This construct enables the proposed method to combat changing environments and large localization errors, even when the change alters the homotopy class of the optimal trajectory. It further outperforms the state-of-the-art Feedback-based Information RoadMap (FIRM) method by eliminating unnecessary stabilization steps. Applying belief space planning to physical systems brings with it a plethora of challenges. A key focus of this paper is to implement the proposed planner on a physical robot and show the SLAP solution performance under uncertainty, in changing environments and in the presence of large disturbances, such as a kidnapped robot situation. [ABSTRACT FROM AUTHOR]

The papers included in this special section were presented at the 11th Workshop on the Algorithmic Foundations of Robotics (WAFR), which was held at Bo?azi?i University, Istanbul, Turkey, during August 3?5, 2014. [ABSTRACT FROM AUTHOR]

The papers in this special section were presented at the 11th Workshop on the Algorithmic Foundation of Robotics (WAFR), which was held at Bo?azi?i University, Istanbul, Turkey, during August 3?5, 2014. WAFR is a prestigious biennial single-track workshop on algorithms for robotics and automation. It features cutting-edge research in a broad range of planning problems (such as manipulation, motion, path, multi-robot, and kynodynamic planning), geometric and topological computation, and novel applications like surgical planning, active sensing, and informative path planning. [ABSTRACT FROM AUTHOR]

Predicting protein structures and simulating protein folding are two of the most important problems in computational biology today. Simulation methods rely on a scoring function to distinguish the native structure (the most energetically stable) from non-native structures. Decoy databases are collections of non-native structures used to test and verify these functions. We present a method to evaluate and improve the quality of decoy databases by adding novel structures and removing redundant structures. We test our approach on 20 different decoy databases of varying size and type and show significant improvement across a variety of metrics. We also test our improved databases on two popular modern scoring functions and show that for most cases they contain a greater or equal number of native-like structures than the original databases, thereby producing a more rigorous database for testing scoring functions. [ABSTRACT FROM AUTHOR]

Abstract: Decomposing a shape into visually meaningful parts comes naturally to humans, but recreating this fundamental operation in computers has been shown to be difficult. Similar challenges have puzzled researchers in shape reconstruction for decades. In this paper, we recognize the strong connection between shape reconstruction and shape decomposition at a fundamental level and propose a method called . The generates a space of decompositions parameterized by , the diameter of a circle convolved with the input polygon. As we vary the value of , some structural features appear and disappear quickly while others persist. Therefore, by analyzing the persistence of the features, we can determine better decompositions that are more robust to both geometrical and topological noises. [Copyright &y& Elsevier]

Motion planning for spatially constrained robots is difficult due to additional constraints placed on the robot, such as closure constraints for closed chains or requirements on end-effector placement for articulated linkages. It is usually computationally too expensive to apply sampling-based planners to these problems since it is difficult to generate valid configurations. We overcome this challenge by redefining the robot's degrees of freedom and constraints into a new set of parameters, called reachable distance space (RD-space), in which all configurations lie in the set of constraint-satisfying subspaces. This enables us to directly sample the constrained subspaces with complexity linear in the number of the robot's degrees of freedom. In addition to supporting efficient sampling of configurations, we show that the RD-space formulation naturally supports planning and, in particular, we design a local planner suitable for use by sampling-based planners. We demonstrate the effectiveness and efficiency of our approach for several systems including closed chain planning with multiple loops, restricted end-effector sampling, and on-line planning for drawing/sculpting. We can sample single-loop closed chain systems with 1,000 links in time comparable to open chain sampling, and we can generate samples for 1,000-link multi-loop systems of varying topologies in less than a second. [ABSTRACT FROM AUTHOR]

Abstract: We present a general computational approach to simulate RNA folding kinetics that can be used to extract population kinetics, folding rates and the formation of particular substructures that might be intermediates in the folding process. Simulating RNA folding kinetics can provide unique insight into RNA whose functions are dictated by folding kinetics and not always by nucleotide sequence or the structure of the lowest free-energy state. The method first builds an approximate map (or model) of the folding energy landscape from which the population kinetics are analyzed by solving the master equation on the map. We present results obtained using an analysis technique, map-based Monte Carlo simulation, which stochastically extracts folding pathways from the map. Our method compares favorably with other computational methods that begin with a comprehensive free-energy landscape, illustrating that the smaller, approximate map captures the major features of the complete energy landscape. As a result, our method scales to larger RNAs. For example, here we validate kinetics of RNA of more than 200 nucleotides. Our method accurately computes the kinetics-based functional rates of wild-type and mutant ColE1 RNAII and MS2 phage RNAs showing excellent agreement with experiment. [Copyright &y& Elsevier]

• First theoretical and numerical demonstration of parallel transport-sweep algorithm that executes sweeps in minimum possible number of stages. • "Optimal sweep algorithm" allows given code to choose parameters that minimize execution time for given problem on given machine. • Excellent parallel scaling to > 1.M processes with simple grids and with polyhedral spatial grids that resolve fine details in a nuclear reactor. We have found provably optimal algorithms for full-domain discrete-ordinate transport sweeps on a class of grids in 2D and 3D Cartesian geometry that are regular at a coarse level but arbitrary within the coarse blocks. We describe these algorithms and show that they always execute the full eight-octant (or four-quadrant if 2D) sweep in the minimum possible number of stages for a given P x × P y × P z partitioning. Computational results confirm that our optimal scheduling algorithms execute sweeps in the minimum possible stage count. Observed parallel efficiencies agree well with our performance model. Our PDT transport code has achieved approximately 68% parallel efficiency with > 1.5 M parallel threads, relative to 8 threads, on a simple weak-scaling problem with only three energy groups, 10 directions per octant, and 4096 cells/thread. Our ARDRA code has achieved 71% efficiency with > 1.5 M cores, relative to 16 cores, with 36 directions per octant and 48 energy groups. We demonstrate similar efficiencies with PDT on a realistic set of nuclear-reactor test problems, with unstructured meshes that resolve fine geometric details. These results demonstrate that discrete-ordinates transport sweeps can be executed with high efficiency using more than 106 parallel processes. [ABSTRACT FROM AUTHOR]