An official website of the United States government
Elementary students’ early development of embedding and disembedding is complex and paves the way for later STEM learning. The purpose of this study was to clarify the factors that support students’ embedding (i.e., overlapping shapes to form a new shape) and disembedding (i.e., identifying discrete shapes within another shape) through the use of filled shapes as opposed to shape frames. We recruited 26 Grade 1 students (~6–7 years old) and 23 Grade 3 students (~8–9 years old), asked them to work on two layered puzzle designs from the Color Code puzzle game, and interviewed them about their thinking processes. The first graders had higher success rates at fixing and embedding the tiles correctly, and students at both grade levels improved on the three-tile design when encountering it a second time about two months later. The four-tile design was more difficult, but students improved if they could identify a correct sub-structure of the design. Successful students used a combination of pictorial shape strategies and schematic location strategies, systematically testing tiles and checking how they could be embedded. The results suggest that helping students focus on sub-structures can promote their effective embedding.
more »
« less
On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles
In the 15-puzzle game, 15 labeled square tiles are reconfigured on a 4 × 4 board through an escort, wherein each (time) step, a single tile neighboring it may slide into it, leaving the space previously occupied by the tile as the new escort. We study a generalized sliding-tile puzzle (GSTP) in which (1) there are 1+ escorts and (2) multiple tiles can move synchronously in a single time step. Compared with popular discrete multi-agent/robot motion models, GSTP provides a more accurate model for a broad array of high-utility applications, including warehouse automation and autonomous garage parking, but is less studied due to the more involved tile interactions. In this work, we analyze optimal GSTP solution structures, establishing that computing makespan optimal solutions for GSTP is NP-complete and developing polynomial time algorithms yielding makespans approximating the minimum with expected/high probability constant factors, assuming randomized start and goal configurations.
more »
« less
- PAR ID:
- 10573387
- Publisher / Repository:
- ACM
- Date Published:
- Journal Name:
- Proceedings of the AAAI Conference on Artificial Intelligence
- Volume:
- 38
- Issue:
- 9
- ISSN:
- 2159-5399
- Page Range / eLocation ID:
- 10288 to 10296
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Seki, Shinnosuke; Stewart, Jaimie Marie (Ed.)The abstract Tile Assembly Model (aTAM) provides an excellent foundation for the mathematical study of DNA-tile-based self-assembling systems, especially those wherein logic is embedded within the designs of the tiles so that they follow prescribed algorithms. While such algorithmic self-assembling systems are theoretically powerful, being computationally universal and capable of building complex shapes using information-theoretically optimal numbers of tiles, physical DNA-based implementations of these systems still encounter formidable error rates and undesired nucleation that hinder this theoretical potential. Slat-based self-assembly is a recent development wherein DNA forms long slats that combine together in 2 layers, rather than square tiles in a plane. In this approach, the length of the slats is key; while tiles typically only bind to 2 neighboring tiles at a time, slats may bind to dozens of other slats. This increased coordination between slats means that several mismatched slats must coincidentally meet in just the right way for errors to persist, unlike tiles where only a few are required. Consequently, while still a novel technology, large slat-based DNA constructions have been successfully implemented in the lab with resilience to many tile-based construction problems. These improved error characteristics come at a cost however, as slat-based systems are often more difficult to design and simulate than tile-based ones. Moreover, it has not been clear whether slats, with their larger sizes and different geometries, have the same theoretical capabilities as tiles. In this paper, we show that slats are capable of doing anything that tiles can, at least at scale. We demonstrate that any aTAM system may be converted to and simulated by an effectively equivalent system of slats. Furthermore, we show that these simulating slat systems can be made more efficiently, using shorter slats and a smaller scale factor, if the simulated tile system avoids certain uncommon growth patterns. Specifically, we consider 5 classes of aTAM systems with increasing complexity, from zig-zag systems which grow in a rigid pattern to the full class of all aTAM systems, and show how they may be converted to equivalent slat systems. We show that the simplest class may be simulated by slats at only a 2c × 2c scale, where c is the freely chosen coordination number of the slats, and further show that the full class of aTAM systems can be simulated at only a 5c × 5c scale. These results prove that slats have the full theoretical power of aTAM tiles while also providing constructions that are compact enough for potential DNA-based implementations of slat systems that are both capable of powerful algorithmic self-assembly and possessing of the strong error resilience of slats.more » « less
-
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: https://youtu.be/VU1SZYzeaXw 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
-
In raised floor data centers, tiles with high open area ratio or complex understructure are used to fulfill the demand of today’s high-density computing. Using more open tiles reduces pressure drop across the raised floor with the potential advantages of increased airflow and lower noise. However, it introduces the disadvantage of increased non-uniformity of airflow distribution. In addition, there are various tile designs available on the market with different opening shapes or understructures. Furthermore, a physical separation of cold and hot aisles (containment) has been introduced to minimize the mixing of cold and hot air. In this study, three types of floor tiles with different open area, opening geometry, and understructure are considered. Experimentally validated detail models of tiles were implemented in CFD simulations to address the impact of tile design on the cooling of IT equipment in both open and enclosed aisle configurations. Also, impacts of under-cabinet leakage on the IT equipment inlet temperature in the provisioned and under-provisioned scenarios are studied. Finally, a predictive equation for the critical under-provisioning point that can lead to a no-flow condition in IT equipment with weaker airflow systems is presented.more » « less
-
Meeks, Kitty; Scheideler, Christian (Ed.)This work fully characterizes fractal generation in the seeded Tile Automata model (seeded TA), a model similar to the abstract Tile Assembly model (aTAM) with the added ability for adjacent tiles to change states. Under these assumptions, we first show that all discrete self-similar fractals (DSSFs) with feasible generators are strictly buildable at scale 1 and temperature 1 in seeded TA. We then show that these results imply the existence of a single seeded TA system Γ that can strictly build any DSSF infinitely at scale 1 and temperature 1.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1609/aaai.v38i9.28895
