An official website of the United States government
We investigate the problem of assembling general shapes and patterns in a model in which particles move based on uniform external forces until they encounter an obstacle. In this model, corresponding particles may bond when adjacent with one another. Succinctly, this model considers a 2D grid of “open” and “blocked” spaces, along with a set of slidable polyominoes placed at open locations on the board. The board may be tilted in any of the 4 cardinal directions, causing all slidable polyominoes to move maximally in the specified direction until blocked. By successively applying a sequence of such tilts, along with allowing different polyominoes to stick when adjacent, tilt sequences provide a method to reconfigure an initial board configuration so as to assemble a collection of previous separate polyominoes into a larger shape. While previous work within this model of assembly has focused on designing a specific board configuration for the assembly of a specific given shape, we propose the problem of designing universal configurations that are capable of constructing a large class of shapes and patterns. For these constructions, we present the notions of weak and strong universality which indicate the presence of “excess” polyominoes after the shape is constructed. In particular, for given integers h, w, we show that there exists a weakly universal configuration with O(hw) 1 × 1 slidable particles that can be reconfigured to build any h × w patterned rectangle. We then expand this result to show that there exists a weakly universal configuration that can build any h × w-bounded size connected shape. Following these results, which require an admittedly relaxed assembly definition, we go on to show the existence of a strongly universal configuration (no excess particles) which can assemble any shape within a previously studied “drop” class, while using quadratically less space than previous results. Finally, we include a study of the complexity of deciding if a particle within a configuration may be relocated to another position, and deciding if a given configuration may be transformed into a second given configuration. We show both problems to be PSPACE-complete even when no particles stick to one another and movable particles are restricted to 1 × 1 tiles and a single 2 × 2 polyomino.
more »
« less
Hierarchical Shape Construction and Complexity for Slidable Polyominos under Uniform External Forces
Advances in technology have given us the ability to create and manipulate robots for numerous applications at the molecular scale. At this size, fabrication tool limitations motivate the use of simple robots. The individual control of these simple objects can be infeasible. We investigate a model of robot motion planning, based on global external signals, known as the tilt model. Given a board and initial placement of polyominoes, the board may be tilted in any of the 4 cardinal directions, causing all slidable polyominoes to move maximally in the specified direction until blocked.We propose a new hierarchy of shapes and design a single configuration that is strongly universal for any w×h bounded shape within this hierarchy (it can be reconfigured to construct any w×h bounded shape in the hierarchy). This class of shapes constitutes the most general set of buildable shapes in the literature, with most previous work consisting of just the first-level of our hierarchy. We accompany this result with a O(n4logn)-time algorithm for deciding if a given hole-free shape is a member of the hierarchy. For our second result, we resolve a long-standing open problem within the field: We show that deciding if a given position may be covered by a tile for a given initial board configuration is PSPACE-complete, even when all movable pieces are 1×1 tiles with no glues. We achieve this result by a reduction from Non-deterministic Constraint Logic for a one-player unbounded game.
more »
« less
- Award ID(s):
- 1817602
- PAR ID:
- 10179110
- Date Published:
- Journal Name:
- ACM-SIAM Symposium on Discrete Algorithms
- Page Range / eLocation ID:
- 2625-2641
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In this video, we consider recognition and reconfiguration of lattice-based cellular structures by very simple robots with only basic functionality. The underlying motivation is the construction and modification of space facilities of enormous dimensions, where the combination of new materials with extremely simple robots promises structures of previously unthinkable size and flexibility. We present algorithmic methods that are able to detect and reconfigure arbitrary polyominoes, based on finite-state robots, while also preserving connectivity of a structure during reconfiguration. Specific results include methods for determining a bounding box, scaling a given arrangement, and adapting more general algorithms for transforming polyominoes.more » « less
-
Shape change enables new capabilities for robots. One class of robots capable of dramatic shape change is soft growing “vine” robots. These robots usually feature global actuation methods for bending that limit them to simple, constant-curvature shapes. Achieving more complex “multi-bend” configurations has also been explored but requires choosing the desired configuration ahead of time, exploiting contact with the environment to maintain previous bends, or using pneumatic actuation for shape locking. In this paper, we present a novel design that enables passive, on-demand shape locking. Our design leverages a passive tip mount to apply hook-and-loop fasteners that hold bends without any pneumatic or electrical input. We characterize the robot's kinematics and ability to hold locked bends. We also experimentally evaluate the effect of hook-and-loop fasteners on beam and joint stiffness. Finally, we demonstrate our proof-of-concept prototype in 2D. Our passive shape locking design is a step towards easily reconfigurable robots that are lightweight, low-cost, and low-power.more » « less
-
Abstract Given a graphon $$W$$ and a finite simple graph $$H$$ , with vertex set $V(H)$ , denote by $$X_n(H, W)$$ the number of copies of $$H$$ in a $$W$$ -random graph on $$n$$ vertices. The asymptotic distribution of $$X_n(H, W)$$ was recently obtained by Hladký, Pelekis, and Šileikis [17] in the case where $$H$$ is a clique. In this paper, we extend this result to any fixed graph $$H$$ . Towards this we introduce a notion of $$H$$ -regularity of graphons and show that if the graphon $$W$$ is not $$H$$ -regular, then $$X_n(H, W)$$ has Gaussian fluctuations with scaling $$n^{|V(H)|-\frac{1}{2}}$$ . On the other hand, if $$W$$ is $$H$$ -regular, then the fluctuations are of order $$n^{|V(H)|-1}$$ and the limiting distribution of $$X_n(H, W)$$ can have both Gaussian and non-Gaussian components, where the non-Gaussian component is a (possibly) infinite weighted sum of centred chi-squared random variables with the weights determined by the spectral properties of a graphon derived from $$W$$ . Our proofs use the asymptotic theory of generalised $$U$$ -statistics developed by Janson and Nowicki [22]. We also investigate the structure of $$H$$ -regular graphons for which either the Gaussian or the non-Gaussian component of the limiting distribution (but not both) is degenerate. Interestingly, there are also $$H$$ -regular graphons $$W$$ for which both the Gaussian or the non-Gaussian components are degenerate, that is, $$X_n(H, W)$$ has a degenerate limit even under the scaling $$n^{|V(H)|-1}$$ . We give an example of this degeneracy with $$H=K_{1, 3}$$ (the 3-star) and also establish non-degeneracy in a few examples. This naturally leads to interesting open questions on higher order degeneracies.more » « less
-
Abstract Many aquatic animals swim by undulatory body movements and understanding the diversity of these movements could unlock the potential for designing better underwater robots. Here, we analyzed the steady swimming kinematics of a diverse group of fish species to investigate whether their undulatory movements can be represented using a series of interconnected multi-segment models, and if so, to identify the key factors driving the segment configuration of the models. Our results show that the steady swimming kinematics of fishes can be described successfully using parsimonious models, 83% of which had fewer than five segments. In these models, the anterior segments were significantly longer than the posterior segments, and there was a direct link between segment configuration and swimming kinematics, body shape, and Reynolds number. The models representing eel-like fishes with elongated bodies and fishes swimming at high Reynolds numbers had more segments and less segment length variability along the body than the models representing other fishes. These fishes recruited their anterior bodies to a greater extent, initiating the undulatory wave more anteriorly. Two shape parameters, related to axial and overall body thickness, predicted segment configuration with moderate to high success rate. We found that head morphology was a good predictor of its segment length. While there was a large variation in head segments, the length of tail segments was similar across all models. Given that fishes exhibited variable caudal fin shapes, the consistency of tail segments could be a result of an evolutionary constraint tuned for high propulsive efficiency. The bio-inspired multi-segment models presented in this study highlight the key bending points along the body and can be used to decide on the placement of actuators in fish-inspired robots, to model hydrodynamic forces in theoretical and computational studies, or for predicting muscle activation patterns during swimming.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1137/1.9781611975994.160
