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
Relocation with uniform external control in limited directions
We study a model where particles exist within a board and move single units based on uniform external forces. We investigate the complexity of deciding whether a single particle can be relocated to another position in the board, and whether a board configuration can be transformed into another configuration. We prove that the problems are NP-complete with 1× 1 particles even when only allowed to move in 2 or 3 directions.
more »
« less
- Award ID(s):
- 1817602
- NSF-PAR ID:
- 10179129
- Date Published:
- Journal Name:
- The 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games, JCDCGGG
- Page Range / eLocation ID:
- 39-40
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We investigate algorithmic control of a large swarm of mobile particles (such as robots, sensors, or building material) that move in a 2D workspace using a global input signal (such as gravity or a magnetic field). Upon activation of the field, each particle moves maximally in the same direction until forward progress is blocked by a stationary obstacle or another stationary particle. In an open workspace, this system model is of limited use because it has only two controllable degrees of freedom—all particles receive the same inputs and move uniformly. We show that adding a maze of obstacles to the environment can make the system drastically more complex but also more useful. We provide a wide range of results for a wide range of questions. These can be subdivided into external algorithmic problems, in which particle configurations serve as input for computations that are performed elsewhere, and internal logic problems, in which the particle configurations themselves are used for carrying out computations. For external algorithms, we give both negative and positive results. If we are given a set of stationary obstacles, we prove that it is NP-hard to decide whether a given initial configuration of unit-sized particles can be transformed into a desired target configuration. Moreover, we show that finding a control sequence of minimum length is PSPACE-complete. We also work on the inverse problem, providing constructive algorithms to design workspaces that efficiently implement arbitrary permutations between different configurations. For internal logic, we investigate how arbitrary computations can be implemented. We demonstrate how to encode dual-rail logic to build a universal logic gate that concurrently evaluates AND, NAND, NOR, and OR operations. Using many of these gates and appropriate interconnects, we can evaluate any logical expression. However, we establish that simulating the full range of complex interactions present in arbitrary digital circuits encounters a fundamental difficulty: a FAN-OUT gate cannot be generated. We resolve this missing component with the help of 2 9 1 particles, which can create FAN-OUT gates that produce multiple copies of the inputs. Using these gates we provide rules for replicating arbitrary digital circuits.more » « less
-
Hierarchical Shape Construction and Complexity for Slidable Polyominos under Uniform External ForcesAdvances 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
-
Olanoff, D. ; Johnson, K. ; Spitzer, S. (Ed.)A key aspect of professional noticing includes attending to students’ mathematics (Jacobs et al., 2010). Initially, preservice teachers (PSTs) may attend to non-mathematics specific aspects of a classroom before attending to children’s procedures and then, eventually their conceptual reasoning (Barnhart & van Es, 2015). Use of 360 videos has been observed to increase the likelihood that PSTs will attend to more mathematics-specific student actions. This is due to an increased perceptual capacity, or the capacity of a representation to convey what is perceivable in a scenario (Kosko et al., in press). A 360 camera records a classroom omnidirectionally, allowing PSTs viewing the video to look in any direction. Moreover, several 360 cameras can be used in a single room to allow the viewer to move from one point in the recorded classroom to another; defined by Zolfaghari et al., 2020 as multi-perspective 360 video. Although multiperspective 360 has tremendous potential for immersion and presence (Gandolfi et al., 2021), we have not located empirical research clarifying whether or how this may affect PSTs’ professional noticing. Rather, most published research focuses on the use of a single camera. Given the dearth of research, we explored PSTs’ viewing of and teacher noticing related to a six-camera multiperspective 360 video. We examined 22 early childhood PSTs’ viewing of a 4th grade class using pattern blocks to find an equivalent fraction to 3/4. Towards the end of the video, one student suggested 8/12 as an equivalent fraction, but a peer claimed it was 9/12. The teacher prompts the peer to “prove it” and a brief discussion ensues before the video ends. After viewing the video, PSTs’ written noticings were solicited and coded. In our initial analysis, we examined whether PSTs attended to students’ fraction reasoning. Although many PSTs attended to whether 8/12 or 9/12 was the correct answer, only 7 of 22 attended to students’ part-whole reasoning of the fractions. Next, we examined the variance in how frequently PSTs switched their camera perspective using the unalikeability statistic. Unalikeability (U2) is a nonparametric measure of variance, ranging from 0 to 1, for nominal variables (Kader & Perry, 2007). Participants scores ranged from 0 to 0.80 (Median=0.47). We then compared participants’ U2 statistics for whether they attended (or not) to students mathematical reasoning in their written noticing. Findings revealed no statistically significant difference (U=38.5, p=0.316). On average, PSTs used 2-3 camera perspectives, and there was no observable benefit to using a higher number of cameras. These findings suggest that multiple perspectives may be useful for some, but not all PSTs’.more » « less
-
1. Description of the objectives and motivation for the contribution to ECE education The demand for wireless data transmission capacity is increasing rapidly and this growth is expected to continue due to ongoing prevalence of cellular phones and new and emerging bandwidth-intensive applications that encompass high-definition video, unmanned aerial systems (UAS), intelligent transportation systems (ITS) including autonomous vehicles, and others. Meanwhile, vital military and public safety applications also depend on access to the radio frequency spectrum. To meet these demands, the US federal government is beginning to move from the proven but inefficient model of exclusive frequency assignments to a more-efficient, shared-spectrum approach in some bands of the radio frequency spectrum. A STEM workforce that understands the radio frequency spectrum and applications that use the spectrum is needed to further increase spectrum efficiency and cost-effectiveness of wireless systems over the next several decades to meet anticipated and unanticipated increases in wireless data capacity. 2. Relevant background including literature search examples if appropriate CISCO Systems’ annual survey indicates continued strong growth in demand for wireless data capacity. Meanwhile, undergraduate electrical and computer engineering courses in communication systems, electromagnetics, and networks tend to emphasize mathematical and theoretical fundamentals and higher-layer protocols, with less focus on fundamental concepts that are more specific to radio frequency wireless systems, including the physical and media access control layers of wireless communication systems and networks. An efficient way is needed to introduce basic RF system and spectrum concepts to undergraduate engineering students in courses such as those mentioned above who are unable to, or had not planned to take a full course in radio frequency / microwave engineering or wireless systems and networks. We have developed a series of interactive online modules that introduce concepts fundamental to wireless communications, the radio frequency spectrum, and spectrum sharing, and seek to present these concepts in context. The modules include interactive, JavaScript-based simulation exercises intended to reinforce the concepts that are presented in the modules through narrated slide presentations, text, and external links. Additional modules in development will introduce advanced undergraduate and graduate students and STEM professionals to configuration and programming of adaptive frequency-agile radios and spectrum management systems that can operate efficiently in congested radio frequency environments. Simulation exercises developed for the advanced modules allow both manual and automatic control of simulated radio links in timed, game-like simulations, and some exercises will enable students to select from among multiple pre-coded controller strategies and optionally edit the code before running the timed simulation. Additionally, we have developed infrastructure for running remote laboratory experiments that can also be embedded within the online modules, including a web-based user interface, an experiment management framework, and software defined radio (SDR) application software that runs in a wireless testbed initially developed for research. Although these experiments rely on limited hardware resources and introduce additional logistical considerations, they provide additional realism that may further challenge and motivate students. 3. Description of any assessment methods used to evaluate the effectiveness of the contribution, Each set of modules is preceded and followed by a survey. Each individual module is preceded by a quiz and followed by another quiz, with pre- and post-quiz questions drawn from the same pool. The pre-surveys allow students to opt in or out of having their survey and quiz results used anonymously in research. 4. Statement of results. The initial modules have been and are being used by three groups of students: (1) students in an undergraduate Introduction to Communication Systems course; (2) an interdisciplinary group of engineering students, including computer science students, who are participating in related undergraduate research project; and (3) students in a graduate-level communications course that includes both electrical and computer engineers. Analysis of results from the first group of students showed statistically significant increases from pre-quiz to post-quiz for each of four modules on fundamental wireless communication concepts. Results for the other students have not yet been analyzed, but also appear to show substantial pre-quiz to post-quiz increases in mean scores.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
