Search

We consider algorithmic problems motivated by modular robotic reconfiguration, for which we are given $n$ square-shaped modules (or robots) in a (labeled or unlabeled) start configuration and need to find a schedule of sliding moves to transform it into a desired goal configuration, maintaining connectivity of the configuration at all times. Recent work from Computational Geometry has aimed at minimizing the total number of moves, resulting in schedules that can perform reconfigurations in $\mathcal{O}(n^2)$ moves, or $\mathcal{O}(nP)$ for an arrangement of bounding box perimeter size $P$, but are fully sequential. Here we provide first results in the sliding square model that exploit parallel robot motion, resulting in an optimal speedup to achieve reconfiguration in worst-case optimal makespan of $\mathcal{O}(P)$. We also provide tight bounds on the complexity of the problem by showing that even deciding the possibility of reconfiguration within makespan $1$ is NP-complete in the unlabeled case; for the labeled case, deciding reconfiguration within makespan $2$ is NP-complete, while makespan $1$ can be decided in polynomial time., Comment: 38 pages, 35 figures

We study Multi-Agent Path Finding for arrangements of labeled agents in the interior of a simply connected domain: Given a unique start and target position for each agent, the goal is to find a sequence of parallel, collision-free agent motions that minimizes the overall time (the makespan) until all agents have reached their respective targets. A natural case is that of a simply connected polygonal domain with axis-parallel boundaries and integer coordinates, i.e., a simple polyomino, which amounts to a simply connected union of lattice unit squares or cells. We focus on the particularly challenging setting of densely packed agents, i.e., one per cell, which strongly restricts the mobility of agents, and requires intricate coordination of motion. We provide a variety of novel results for this problem, including (1) a characterization of polyominoes in which a reconfiguration plan is guaranteed to exist; (2) a characterization of shape parameters that induce worst-case bounds on the makespan; (3) a suite of algorithms to achieve asymptotically worst-case optimal performance with respect to the achievable stretch for cases with severely limited maneuverability. This corresponds to bounding the ratio between obtained makespan and the lower bound provided by the max-min distance between the start and target position of any agent and our shape parameters. Our results extend findings by Demaine et al. (SIAM Journal on Computing, 2019) who investigated the problem for solid rectangular domains, and in the closely related field of Permutation Routing, as presented by Alpert et al. (Computational Geometry, 2022) for convex pieces of grid graphs., Comment: 21 pages, 14 figures, full version of an extended abstract that is to appear in the proceedings of the 35th International Symposium on Algorithms and Computation (ISAAC 2024)

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., Comment: 19 pages, 18 figures. This is the full version of an extended abstract that appeared in the proceedings of WG 2024

We study the stochastic hydrodynamics of colonies of flagellated swimming cells, typified by multicellular choanoflagellates, which can form both rosette and chainlike shapes. The objective is to link cell-scale dynamics to colony-scale dynamics for various colonial morphologies. Via autoregressive stochastic models for the cycle-averaged flagellar force dynamics and statistical models for demographic cell-to-cell variability in flagellar properties and placement, we derive effective transport properties of the colonies, including cell-to-cell variability. We provide the most quantitative detail on disclike geometries to model rosettes, but also present formulas for the dynamics of general planar colony morphologies, which includes planar chain-like configurations.

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., Comment: seven pages, eight figures, one table; revised version; to appear in the proceedings of the 2024 IEEE International Conference on Robotics and Automation (ICRA 2024)

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, 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 $\Omega(\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-complete 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., Comment: 32 pages, 22 figures, full version of an extended abstract that appeared in the proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

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., Comment: Nine pages, nine figures. (Updated) full version of an extended abstract that is published in the proceedings of the 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2022)

We consider the Bayesian approach to the linear Gaussian inference problem of inferring the initial condition of a linear dynamical system from noisy output measurements taken after the initial time. In practical applications, the large dimension of the dynamical system state poses a computational obstacle to computing the exact posterior distribution. Model reduction offers a variety of computational tools that seek to reduce this computational burden. In particular, balanced truncation is a system-theoretic approach to model reduction which obtains an efficient reduced-dimension dynamical system by projecting the system operators onto state directions which trade off the reachability and observability of state directions as expressed through the associated Gramians. We introduce Gramian definitions relevant to the inference setting and propose a balanced truncation approach based on these inference Gramians that yield a reduced dynamical system that can be used to cheaply approximate the posterior mean and covariance. Our definitions exploit natural connections between (i) the reachability Gramian and the prior covariance and (ii) the observability Gramian and the Fisher information. The resulting reduced model then inherits stability properties and error bounds from system theoretic considerations, and in some settings yields an optimal posterior covariance approximation. Numerical demonstrations on two benchmark problems in model reduction show that our method can yield near-optimal posterior covariance approximations with order-of-magnitude state dimension reduction.

Analytical formulas for effective drift, diffusivity, run times, and run lengths are derived for an intracellular transport system consisting of a cargo attached to two cooperative but not identical molecular motors (for example, kinesin-1 and kinesin-2) which can each attach and detach from a microtubule. The dynamics of the motor and cargo in each phase are governed by stochastic differential equations, and the switching rates depend on the spatial configuration of the motor and cargo. This system is analyzed in a limit where the detached motors have faster dynamics than the cargo, which in turn has faster dynamics than the attached motors. The attachment and detachment rates are also taken to be slow relative to the spatial dynamics. Through an application of iterated stochastic averaging to this system, and the use of renewal-reward theory to stitch together the progress within each switching phase, we obtain explicit analytical expressions for the effective drift, diffusivity, and processivity of the motor-cargo system. Our approach accounts in particular for jumps in motor-cargo position that occur during attachment and detachment events, as the cargo tracking variable makes a rapid adjustment due to the averaged fast scales. The asymptotic formulas are in generally good agreement with direct stochastic simulations of the detailed model based on experimental parameters for various pairings of kinesin-1 and kinesin-2 under assisting, hindering, or no load., Comment: 73 pages, 4 Figures

In many biological systems, the movement of individual agents is commonly characterized as having multiple qualitatively distinct behaviors that arise from various biophysical states. This is true for vesicles in intracellular transport, micro-organisms like bacteria, or animals moving within and responding to their environment. For example, in cells the movement of vesicles, organelles and other cargo are affected by their binding to and unbinding from cytoskeletal filaments such as microtubules through molecular motor proteins. A typical goal of theoretical or numerical analysis of models of such systems is to investigate the effective transport properties and their dependence on model parameters. While the effective velocity of particles undergoing switching diffusion is often easily characterized in terms of the long-time fraction of time that particles spend in each state, the calculation of the effective diffusivity is more complicated because it cannot be expressed simply in terms of a statistical average of the particle transport state at one moment of time. However, it is common that these systems are regenerative, in the sense that they can be decomposed into independent cycles marked by returns to a base state. Using decompositions of this kind, we calculate effective transport properties by computing the moments of the dynamics within each cycle and then applying renewal-reward theory. This method provides a useful alternative large-time analysis to direct homogenization for linear advection-reaction-diffusion partial differential equation models. Moreover, it applies to a general class of semi-Markov processes and certain stochastic differential equations that arise in models of intracellular transport. Applications of the proposed framework are illustrated for case studies such as mRNA transport in developing oocytes and processive cargo movement by teams of motor proteins., Comment: 35 pages, 6 figures

Mathematicians have been interested in non-periodic tilings of space for decades; however, it was the unexpected discovery of non-periodically ordered structures in intermetallic alloys which brought this subject into the limelight. These fascinating materials, now called quasicrystals, are characterised by the coexistence of long-range atomic order and 'forbidden' symmetries which are incompatible with periodic arrangements in three-dimensional space. In the first part of this review, we summarise the main properties of quasicrystals, and describe how their structures relate to non-periodic tilings of space. The celebrated Penrose and Ammann-Beenker tilings are introduced as illustrative examples. The second part provides a closer look at the underlying mathematics. Starting from Bohr's theory of quasiperiodic functions, a general framework for constructing non-periodic tilings of space is described, and an alternative description as quasiperiodic coverings by overlapping clusters is discussed., Comment: This article is made available for reference. It was written following the March 2006 workshop "The World a Jigsaw: Tessellations in the Sciences" at the Lorentz Center, and due to be published in a book entitled "Tessellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings" (eds R van de Weijgaert, G Vegter, J Ritzerveld and V Icke), but annoyingly this never happened

We study a bilinear multiplication rule on 2x2 matrices which is intermediate between the ordinary matrix product and the Hadamard matrix product, and we relate this to the hyperbolic motion group of the plane., Comment: One reference added

Self-propelled particles with hydrodynamic interactions (microswimmers) have previously been shown to produce long-range ordering phenomena. Many theoretical explanations for these collective phenomena are connected to instabilities in the hydrodynamic or kinetic equations. By incorporating stochastic fluxes into the mean field kinetic equation, we quantify the dynamics of a suspension of microswimmers in the parameter regime where the deterministic equation is stable. We can thereby compute nontrivial collective phenomena concerning spatial correlations of orientation and stress as well as the enhanced diffusion of tracer particles. Our analysis here focuses primarily on two-dimensional systems, though we also show how superdiffusion of tracers in three dimensions can occur by our framework.

Advertising is a crucial component of marketing and an important way for companies to raise awareness of goods and services in the marketplace. Advertising campaigns are designed to convey a marketing image or message to an audience of potential consumers and television commercials can be an effective way of transmitting these messages to a large audience. In order to meet the requirements for a typical advertising order, television content providers must provide advertisers with a predetermined number of "impressions" in the target demographic. However, because the number of impressions for a given program is not known a priori and because there are a limited number of time slots available for commercials, scheduling advertisements efficiently can be a challenging computational problem. In this case study, we compare a variety of methods for estimating future viewership patterns in a target demographic from past data. We also present a method for using those predictions to generate an optimal advertising schedule that satisfies campaign requirements while maximizing advertising revenue., Comment: 24 pages, 11 figures

We carry out the harmonic analysis on four Platonic spherical three-manifolds with different topologies. Starting out from the homotopies (Everitt 2004), we convert them into deck operations, acting on the simply connected three-sphere as the cover, and obtain the corresponding variety of deck groups. For each topology, the three-sphere is tiled into copies of a fundamental domain under the corresponding deck group. We employ the point symmetry of each Platonic manifold to construct its fundamental domain as a spherical orbifold. While the three-sphere supports an~orthonormal complete basis for harmonic analysis formed by Wigner polynomials, a given spherical orbifold leads to a selection of a specific subbasis. The resulting selection rules find applications in cosmic topology, probed by the cosmic microwave background., Comment: 29 pages, 4 figures

We present an extension of the spin-adapted configuration-interaction method for the computation of four electrons in a quasi two-dimensional quantum dot. By a group-theoretical decomposition of the basis set and working with relative and center-of-mass coordinates we obtain an analytical identification of all spurious center-of-mass states of the Coulomb-interacting electrons. We find a substantial reduction in the basis set used for numerical computations. At the same time we increase the accuracy compared to the standard spin-adapted configuration-interaction method (SACI) due to the absence of distortions caused by an unbalanced cut-off of center-of-mass excitations., Comment: 32 pages, 2 figures, updated list of references, extended introduction

We develop a numerical algorithm for computing the effective drift and diffusivity of the steady-state behavior of an overdamped particle driven by a periodic potential whose amplitude is modulated in time by multiplicative noise and forced by additive Gaussian noise (the mathematical structure of a flashing Brownian motor). The numerical algorithm is based on a spectral decomposition of the solution to the Fokker-Planck equation with periodic boundary conditions and the cell problem which result from homogenization theory. We also show that the numerical method of Wang, Peskin, Elston (WPE, 2003) for computing said quantities is equivalent to that resulting from homogenization theory. We show how to adapt the WPE numerical method to this problem by means of discretizing the multiplicative noise via a finite-volume method into a discrete-state Markov jump process which preserves many important properties of the original continuous-state process, such as its invariant distribution and detailed balance. Our numerical experiments show the effectiveness of both methods, and that the spectral method can have some efficiency advantages when treating multiplicative random noise, particularly with strong volatility., Comment: 49 pages, 8 figures

Random optical-pulse polarization switching along an active optical medium in the $\Lambda$-configuration with spatially disordered occupation numbers of its lower energy sub-level pair is described using the idealized integrable Maxwell-Bloch model. Analytical results describing the light polarization-switching statistics for the single self-induced transparency pulse are compared with statistics obtained from direct Monte-Carlo numerical simulations., Comment: 7 pages, 3 figures

Using the idealized integrable Maxwell-Bloch model, we describe random optical-pulse polarization switching along an active optical medium in the Lambda-configuration with disordered occupation numbers of its lower energy sub-level pair. The description combines complete integrability and stochastic dynamics. For the single-soliton pulse, we derive the statistics of the electric-field polarization ellipse at a given point along the medium in closed form. If the average initial population difference of the two lower sub-levels vanishes, we show that the pulse polarization will switch intermittently between the two circular polarizations as it travels along the medium. If this difference does not vanish, the pulse will eventually forever remain in the circular polarization determined by which sub-level is more occupied on average. We also derive the exact expressions for the statistics of the polarization-switching dynamics, such as the probability distribution of the distance between two consecutive switches and the percentage of the distance along the medium the pulse spends in the elliptical polarization of a given orientation in the case of vanishing average initial population difference. We find that the latter distribution is given in terms of the well-known arcsine law.

Harmonic analysis is a tool to infer cosmic topology from the measured astrophysical cosmic microwave background CMB radiation. For overall positive curvature, Platonic spherical manifolds are candidates for this analysis. We combine the specific point symmetry of the Platonic manifolds with their deck transformations. This analysis in topology leads from manifolds to orbifolds. We discuss the deck transformations of the orbifolds and give eigenmodes for the harmonic analysis as linear combinations of Wigner polynomials on the 3-sphere. These provide new tools for detecting cosmic topology from the CMB radiation., Comment: 17 pages, 9 figures. arXiv admin note: substantial text overlap with arXiv:1011.4274