Tilt Problems

Tilt Assembly: Building polyominoes

In this challenge, you are presented with a polyomino that must be constructed by inserting tiles exclusively from the north, south, east, or west. The initial tile can be placed freely, but subsequent tiles must be inserted without touching any existing tile. The concept is based on the principle that the tiles adhere to each other upon contact. They are propelled into position from the outside using magnetic fields.

You can play around with the example below:

Clearly, not every polyomino can be assembled using this method. However, we have developed an efficient technique to determine the constructability of polyominoes without holes. The complexity of constructing polyominoes with holes remains uncertain at this stage. For three-dimensional polyominoes, we have established that the assembly process is NP-hard.

• Chapter 8 of my dissertation contains a SAT-based approach to determine the constructability of 2D and 3D polyominoes. We also explored extensions for which the constructible part has to be maximized or the number of auxiliary tiles has to be minimized.
• Aaron T. Becker , Sándor P. Fekete , Phillip Keldenich , Dominik Krupke , Christian Rieck , and Christian Scheffer, Arne Schmidt. Tilt Assembly: Algorithms for Micro-factories That Build Objects with Uniform External Forces. In: Algorithmica, Sep 2020
• Phillip Keldenich , Sheryl Manzoor , Li Huang , Dominik Krupke , Arne Schmidt , and Sándor P. Fekete, Aaron T. Becker. On Designing 2D Discrete Workspaces to Sort or Classify Polynminoes In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2018, Madrid, Spain, October 1-5, 2018 , Oct 2018.
• A.T. Becker, S.P. Fekete, P. Keldenich, D. Krupke, C. Rieck, C. Scheffer, and A. Schmidt. Tilt Assembly: Algorithms for Micro-Factories that Build Objects with Uniform External Forces. In: 28th International Symposium on Algorithms and Computation (ISAAC).

Tilt Gather: Moving the particles in a polyomino onto the same field

Once the particles or robots have successfully accomplished their mission, the goal is to reconvene them all. If the polyomino is interconnected and there is at least one wall present, it can be demonstrated that gathering all particles is always feasible, provided that they can execute precise one-field movements and are permitted to overlap.

• Chapter 9 of my dissertation contains an improved and simplified variant of the reinforcement learning approach described in the following paper.
• Aaron T. Becker , Sándor P. Fekete , Li Huang , Phillip Keldenich , Linda Kleist , and Dominik Krupke, Christian Rieck, Arne Schmidt. Targeted Drug Delivery: Algorithmic Methods for Collecting a Swarm of Particles with Uniform, External Forces In: 2020 IEEE International Conference on Robotics and Automation, ICRA 2020, Paris, France, May 31 - August 31, 2020, Sep 2020
• A.V. Mahadev, D. Krupke, J.-M. Reinhardt, S.P. Fekete, A.T. Becker Collecting a Swarm in a 2D Environment Using Shared, Global Inputs. In: 13th Conference on Automation Science and Engineering (CASE 2016), 1231-1236.

Tilt Map: Mapping/Exploring an unknown polyomino

Magnetic resonance imaging (MRI) can sometimes yield images with insufficient contrast. To address this, contrast agents are used, but they have limitations, such as rapid diffusion and potential toxicity. An alternative strategy involves mapping tissue with a swarm of magnetically controlled particles. These particles, known for their high contrast, assist in delineating tissue boundaries. A boundary is identified when a particle collides with it and halts, despite the applied magnetic force.

Given the complexity of the continuous 3D scenario, let’s focus on a more manageable 2D version where particles move along a grid. In this challenge, you are presented with a polyomino, initially unknown, and a set of particles within it. The objective is to map the entire polyomino using the fewest possible moves. Each move shifts all particles one grid space in the same direction; however, blocked particles remain stationary.

To better understand this problem, engage with the interactive visualization provided. Use your mouse to click in the direction you wish to move the particles (represented as red circles).

• A.V. Mahadev, D. Krupke, S.P. Fekete, A.T. Becker Mapping, Foraging, and Coverage with a Particle Swarm Controlled by Uniform Inputs In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2017).