skip to main content

Title: Connected Reconfiguration of Polyominoes Amid Obstacles using RRT
This paper investigates using a sampling-based approach, the RRT*, to reconfigure a 2D set of connected tiles in complex environments, where multiple obstacles might be present. Since the target application is automated building of discrete, cellular structures using mobile robots, there are constraints that determine what tiles can be picked up and where they can be dropped off during reconfiguration. We compare our approach to two algorithms as global and local planners, and show that we are able to find more efficient build sequences using a reasonable amount of samples, in environments with varying degrees of obstacle space.  more » « less
Award ID(s):
2130793 1553063 1849303
Author(s) / Creator(s):
; ; ; ;
Date Published:
Journal Name:
2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
Page Range / eLocation ID:
6554 to 6560
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    Imagine t ≤ mn unit-square tiles in an m×n rectangular box that you can tilt to cause all tiles to slide maximally in one of the four orthogonal directions. Given two tiles of interest, is there a tilt sequence that brings them to adjacent squares? We give a linear-time algorithm for this problem, motivated by 2048 endgames. We also bound the number of reachable configurations, and design instances where all t tiles permute according to a cyclic permutation every four tilts. 
    more » « less
  2. Domain-specific languages that execute image processing pipelines on GPUs, such as Halide and Forma, operate by 1) dividing the image into overlapped tiles, and 2) fusing loops to improve memory locality. However, current approaches have limitations: 1) they require intra thread block synchronization, which has a nontrivial cost, 2) they must choose between small tiles that require more overlapped computations or large tiles that increase shared memory access (and lowers occupancy), and 3) their autoscheduling algorithms use simplified GPU models that can result in inefficient global memory accesses. We present a new approach for executing image processing pipelines on GPUs that addresses these limitations as follows. 1) We fuse loops to form overlapped tiles that fit in a single warp, which allows us to use lightweight warp synchronization. 2) We introduce hybrid tiling, which stores overlapped regions in a combination of thread-local registers and shared memory. Thus hybrid tiling either increases occupancy by decreasing shared memory usage or decreases overlapping computations using larger tiles. 3) We present an automatic loop fusion algorithm that considers several factors that affect the performance of GPU kernels. We implement these techniques in PolyMage-GPU, which is a new GPU backend for PolyMage. Our approach produces code that is faster than Halide's manual schedules: 1.65x faster on an NVIDIA GTX 1080Ti and 1.33x faster on an NVIDIA Tesla V100. 
    more » « less
  3. Controlling stray light at millimeter wavelengths requires special optical design and selection of absorptive materials that should be compatible with cryogenic operating environments. While a wide selection of absorptive materials exists, these typically exhibit high indices of refraction and reflect/scatter a significant fraction of light before absorption. For many lower index materials such as commercial microwave absorbers, their applications in cryogenic environments are challenging. In this paper, we present a new tool to control stray light: metamaterial microwave absorber tiles. These tiles comprise an outer metamaterial layer that approximates a lossy gradient index anti-reflection coating. They are fabricated via injection molding commercially available carbon-loaded polyurethane (25% by mass). The injection molding technology enables mass production at low cost. The design of these tiles is presented, along with thermal tests to 1 K. Room temperature optical measurements verify their control of reflectance to less than 1% up to65∘<#comment/>angles of incidence, and control of wide angle scattering below 0.01%. The dielectric properties of the bulk carbon-loaded material used in the tiles is also measured at different temperatures, confirming that the material maintains similar dielectric properties down to 3 K.

    more » « less
  4. We investigate motion planning algorithms for the assembly of shapes in the tilt model in which unit-square tiles move in a grid world under the influence of uniform external forces and self-assemble according to certain rules. We provide several heuristics and experimental evaluation of their success rate, solution length, and runtime. Video: Transcript: This animation shows colored tiles moved by a global signal so they all move in the same direction unless blocked. This simple example is solved using the Greatest Distance heuristic, which finds the shortest path in 21 steps. Each tile has glue on the four sides that only stick to compatible glues. Glue type is denoted by color. The objective is to manipulate the tiles to bond in the shape of the connected polyomino target outlined in red. The Polyomino Assembly Problem is PSPACE-hard, so optimal solutions are difficult to find. This more complicated workspace was solved using the Minimum Move to Polyomino or Target. This approach is not optimal, but is a best-first search that attempts to keep tiles not involved in the present construction step separated from each other. This is done by pruning configurations with undesired subassemblies from the search tree. The solution requires 473 steps. 
    more » « less
  5. Much of our knowledge of the North American lithosphere comes from imaging seismic velocities. Additional constraints on the subsurface can be gained by studying seismic attenuation, which has different sensitivity to physical properties. We produce a model of lateral variations in attenuation across the conterminous U.S. by analyzing data recorded by the EarthScope Transportable Array. We divide the study area into 12 overlapping tiles and differential attenuation is measured in each tile independently; and twice for four of the tiles. Measurements are combined into a smooth map using a set of linear inversions. Comparing results for adjacent tiles and for repeated tiles shows that the imaged features are robust. The final map shows generally higher attenuation west of the Rocky Mountain Front than east of it, with significant small length scale variations superimposed on that broad pattern. In general, there is a strong anticorrelation between differential attenuation and shear wave velocities at depths of 80–250 km. However, a given change in velocity may correspond to a large or small change in attenuation, depending on the area; suggesting that different physical mechanisms are operating. In the western and south‐central U.S., as well as the Appalachians, velocity variations are large compared to attenuation changes, while the opposite is true in the north‐central and southeastern U.S. Calculations with the Very Broadband Rheology calculator show that these results are consistent with the main source of heterogeneity being temperature and melt fraction in the former regions and grain size variability in the latter ones.

    more » « less