[This page is currently under construction and will be gradually supplemented.]
SpaceAnts is a research project investigating algorithmic foundations for the construction and reconfiguration of large-scale structures by simple autonomous robots. The project is led by the Technical University Braunschweig and carried out in collaboration with Bochum University of Applied Sciences, the University of Houston, the Stony Brook University, the MIT, and NASA. SpaceAnts has been funded by the German Research Foundation (DFG) since September 1, 2024 and is scheduled to run until August 31, 2027.
The central challenge of SpaceAnts is to enable a set of simple robots to solve complex construction tasks. In particular, the focus lies on constructions consisting of a large number of modular, lattice-based components. SpaceAnts aims to develop algorithmic foundations for the coordination of large swarms of simple robots without relying on individual robots with extensive capabilities. The project develops methods for optimization and coordination that take geometric aspects into account and are relevant for applications ranging from ultralight modular structures in space to microscopic environments.
Additional information about the project can be found on the project page at L3S and the project page at Bochum University of Applied Sciences.
Since SpaceAnts is still in its ongoing funding phase, final research results cannot yet be presented. The project addresses a wide range of research questions from different areas. In the following, two of these research directions are presented as examples.
One research focus of SpaceAnts is coordinated motion planning for large numbers of autonomous robots. The goal is to compute how a set of robots moving simultaneously in a shared environment can reach their individual target positions without colliding with each other.
This problem leads to various optimization objectives. For example, one objective is to plan robot movements such that all robots reach their target positions as quickly as possible. In this case, the total time until the last robot reaches its destination is minimized, also known as the makespan. Another objective is to minimize the total distance traveled by all robots combined.
Building on previous results, SpaceAnts investigates how coordinated motion plans for large robot swarms can be further improved. One focus is the extension of existing two-dimensional approaches to three-dimensional scenarios in order to enable applications in real-world environments. Another objective is the analysis and improvement of the so-called stretch factor, which describes the ratio between the time required by a parallel motion plan and the theoretical minimum time. The stretch factor however is closely related to the spatial distribution of robots. SpaceAnts therefore aims to better understand the relationship between robot separation and the efficiency of parallel motion plans, to formalize the relationships between the relevant parameters, and to translate the developed algorithms into practical control protocols.
A major bottleneck in efficient motion and reconfiguration planning can be the underlying structure on which these processes take place. In applications such as communication networks, logistics, or traffic control, this structure largely determines how efficiently information, materials, or robots can move. Therefore, it is not sufficient to optimize movements on a fixed structure; the structure itself should also be adapted and reconfigured to improve overall efficiency. An important model for such underlying structures are triangulations, i.e., planar connection structures that partition a set of points into triangles and thereby guarantee collision-free connections.
However, not all triangulations are equally suitable. Depending on how edges between points are chosen, the quality of the resulting structure can vary significantly. A central criterion is how efficient paths along the structure are compared to direct Euclidean connections.
Another focus of SpaceAnts is the reconfiguration of structures by robots with limited capabilities. The goal is to transform a given initial configuration into a desired target configuration by having individual robots perform local actions. The challenge lies in the fact that robots can only plan their actions based on local information. One example of this class of problems is the Tile Reconfiguration Problem, in which a single robot with the (limited) capabilities, e.g. those of a DFA, has to transform an initial tile configuration into a target configuration.
Within SpaceAnts, the focus lies on the parallel reconfiguration of triangulations, in particular Delaunay triangulations and minimum-weight triangulations. The project investigates how local structural changes can be performed in parallel in order to reduce total reconfiguration time, and how these changes affect the quality of the resulting structure.
In addition, dynamically changing reconfiguration structures are considered, where the underlying structure changes while it is being used. In such scenarios, robots move along a structure that is simultaneously being reconfigured. This requires new algorithmic methods that consider reconfiguration and movement simultaneously and enable efficient paths in dynamically changing structures.
In addition to the research directions described above, the SpaceAnts project includes several further topics related to algorithmic and geometric foundations for robotic systems and reconfigurable structures. These include, among others:
In collaboration with the Technical University Braunschweig, two videos were produced for SpaceAnts that illustrate the research topics addressed.
Prof. Dr. Sándor P. Fekete
Algorithmics Group
Technical University Braunschweig
Mühlenpfordtstraße 23
38106 Braunschweig
Phone: +49 (0)531 391 311 1
Fax: +49 (0)531 391 310 9
Email: s.fekete@tu-bs.de
Website: Prof. Dr. Fekete at TU Braunschweig