-
On the Connectivity of the Flip Graph of Plane Spanning Paths
Authors:
Linda Kleist,
Peter Kramer,
Christian Rieck
Abstract:
Flip graphs of non-crossing configurations in the plane are widely studied objects, e.g., flip graph of triangulations, spanning trees, Hamiltonian cycles, and perfect matchings. Typically, it is an easy exercise to prove connectivity of a flip graph. In stark contrast, the connectivity of the flip graph of plane spanning paths on point sets in general position has been an open problem for more th…
▽ More
Flip graphs of non-crossing configurations in the plane are widely studied objects, e.g., flip graph of triangulations, spanning trees, Hamiltonian cycles, and perfect matchings. Typically, it is an easy exercise to prove connectivity of a flip graph. In stark contrast, the connectivity of the flip graph of plane spanning paths on point sets in general position has been an open problem for more than 16 years.
In order to provide new insights, we investigate certain induced subgraphs. Firstly, we provide tight bounds on the diameter and the radius of the flip graph of spanning paths on points in convex position with one fixed endpoint. Secondly, we show that so-called suffix-independent paths induce a connected subgraph. Consequently, to answer the open problem affirmatively, it suffices to show that each path can be flipped to some suffix-independent path. Lastly, we investigate paths where one endpoint is fixed and provide tools to flip to suffix-independent paths. We show that these tools are strong enough to show connectivity of the flip graph of plane spanning paths on point sets with at most two convex layers.
△ Less
Submitted 4 July, 2024;
originally announced July 2024.
-
Reconfiguration of a 2D Structure Using Spatio-Temporal Planning and Load Transferring
Authors:
Javier Garcia,
Michael Yannuzzi,
Peter Kramer,
Christian Rieck,
Sándor P. Fekete,
Aaron T. Becker
Abstract:
We present progress on the problem of reconfiguring a 2D arrangement of building material by a cooperative group of robots. These robots must avoid collisions, deadlocks, and are subjected to the constraint of maintaining connectivity of the structure. We develop two reconfiguration methods, one based on spatio-temporal planning, and one based on target swapping, to increase building efficiency. T…
▽ More
We present progress on the problem of reconfiguring a 2D arrangement of building material by a cooperative group of robots. These robots must avoid collisions, deadlocks, and are subjected to the constraint of maintaining connectivity of the structure. We develop two reconfiguration methods, one based on spatio-temporal planning, and one based on target swapping, to increase building efficiency. The first method can significantly reduce planning times compared to other multi-robot planners. The second method helps to reduce the amount of time robots spend waiting for paths to be cleared, and the overall distance traveled by the robots.
△ Less
Submitted 7 March, 2024; v1 submitted 16 November, 2022;
originally announced November 2022.
-
Efficiently Reconfiguring a Connected Swarm of Labeled Robots
Authors:
Sándor P. Fekete,
Peter Kramer,
Christian Rieck,
Christian Scheffer,
Arne Schmidt
Abstract:
When considering motion planning for a swarm of $n$ labeled robots, we need to rearrange a given start configuration into a desired target configuration via a sequence of parallel, continuous, collision-free robot motions. The objective is to reach the new configuration in a minimum amount of time; an important constraint is to keep the swarm connected at all times. Problems of this type have been…
▽ More
When considering motion planning for a swarm of $n$ labeled robots, we need to rearrange a given start configuration into a desired target configuration via a sequence of parallel, continuous, collision-free robot motions. The objective is to reach the new configuration in a minimum amount of time; an important constraint is to keep the swarm connected at all times. Problems of this type have been considered before, with recent notable results achieving constant stretch for not necessarily connected reconfiguration: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of $d$, the total duration of an overall schedule can be bounded to $\mathcal{O}(d)$, which is optimal up to constant factors. However, constant stretch could only be achieved if disconnected reconfiguration is allowed, or for scaled configurations (which arise by increasing all dimensions of a given object by the same multiplicative factor) of unlabeled robots.
We resolve these major open problems by (1) establishing a lower bound of $Ω(\sqrt{n})$ for connected, labeled reconfiguration and, most importantly, by (2) proving that for scaled arrangements, constant stretch for connected reconfiguration can be achieved. In addition, we show that (3) it is NP-hard to decide whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved.
△ Less
Submitted 22 September, 2022;
originally announced September 2022.
-
Connected Reconfiguration of Polyominoes Amid Obstacles using RRT*
Authors:
Javier Garcia,
Michael Yannuzzi,
Peter Kramer,
Christian Rieck,
Aaron T. Becker
Abstract:
This paper investigates the use of a sampling-based approach, the RRT*, to reconfigure a 2D set of connected tiles in complex environments, where multiple obstacles might be present. Since the target application is automated building of discrete, cellular structures using mobile robots, there are constraints that determine what tiles can be picked up and where they can be dropped off during reconf…
▽ More
This paper investigates the use of a sampling-based approach, the RRT*, to reconfigure a 2D set of connected tiles in complex environments, where multiple obstacles might be present. Since the target application is automated building of discrete, cellular structures using mobile robots, there are constraints that determine what tiles can be picked up and where they can be dropped off during reconfiguration. We compare our approach to two algorithms as global and local planners, and show that we are able to find more efficient build sequences using a reasonable number of samples, in environments with varying densities of obstacles.
△ Less
Submitted 26 October, 2022; v1 submitted 4 July, 2022;
originally announced July 2022.
-
Inverse Modeling of Climate Responses of Monumental Buildings
Authors:
R. P. Kramer,
A. W. M. van Schijndel
Abstract:
The indoor climate conditions of monumental buildings are very important for the conservation of these objects. Simplified models with physical meaning are desired that are capable of simulating temperature and relative humidity. In this paper we research state-space models as methodology for the inverse modeling of climate responses of unheated monumental buildings. It is concluded that this appr…
▽ More
The indoor climate conditions of monumental buildings are very important for the conservation of these objects. Simplified models with physical meaning are desired that are capable of simulating temperature and relative humidity. In this paper we research state-space models as methodology for the inverse modeling of climate responses of unheated monumental buildings. It is concluded that this approach is very promising for obtaining physical models and parameters of indoor climate responses. Furthermore state space models can be simulated very efficiently: the simulation duration time of a 100 year hourly based period take less than a second on an ordinary computer.
△ Less
Submitted 20 June, 2012;
originally announced June 2012.
