Source author record

Jannik Castenow

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Robotics

Catalog footprint

Research overview

3works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility

We consider a swarm of $n$ robots in \mathbb{R}^d. The robots are oblivious, disoriented (no common coordinate system/compass), and have limited visibility (observe other robots up to a constant distance). The basic formation task gathering requires that all robots reach the same, not predefined position. In the related near-gathering task, they must reach distinct positions such that every robot sees the entire swarm. In the considered setting, gathering can be solved in $\mathcal{O}(n + Δ^2)$ synchronous rounds both in two and three dimensions, where $Δ$ denotes the initial maximal distance of two robots. In this work, we formalize a key property of efficient gathering protocols and use it to define $λ$ -contracting protocols. Any such protocol gathers $n$ robots in the $d$ -dimensional space in $\mathcal{O}(Δ^2)$ synchronous rounds. Moreover, we prove a corresponding lower bound stating that any protocol in which robots move to target points inside of the local convex hulls of their neighborhoods -- $λ$ -contracting protocols have this property -- requires $Ω(Δ^2)$ rounds to gather all robots. Among others, we prove that the $d$ -dimensional generalization of the GtC-protocol is $λ$ -contracting. Remarkably, our improved and generalized runtime bound is independent of $n$ and $d$ . The independence of $d$ answers an open research question. We also introduce an approach to make any $λ$ -contracting protocol collisionfree to solve near-gathering. The resulting protocols maintain the runtime of $Θ(Δ^2)$ and work even in the semi-synchronous model.

preprint2020arXiv

Local Gathering of Mobile Robots in Three Dimensions

In this work, we initiate the research about the Gathering problem for robots with limited viewing range in the three-dimensional Euclidean space. In the Gathering problem, a set of initially scattered robots is required to gather at the same position. The robots' capabilities are very restricted -- they do not agree on any coordinate system or compass, have a limited viewing range, have no memory of the past and cannot communicate. We study the problem in two different time models, in FSYNC (fully synchronized discrete rounds) and the continuous time model. For FSYNC, we introduce the 3D-Go-To-The-Center-strategy and prove a runtime of $Θ(n^2)$ that matches the currently best runtime bound for the same model in the Euclidean plane [SPAA'11]. Our main result is the generalization of contracting strategies (continuous time) from [Algosensors'17] to three dimensions. In contracting strategies, every robot that is located on the global convex hull of all robots' positions moves with full speed towards the inside of the convex hull. We prove a runtime bound of $O(Δ\cdot n^{3/2})$ for any three-dimensional contracting strategy, where $Δ$ denotes the diameter of the initial configuration. This comes up to a factor of $\sqrt{n}$ close to the lower bound of $Ω(Δ\cdot n)$ which is already true in two dimensions. In general, it might be hard for robots with limited viewing range to decide whether they are located on the global convex hull and which movement maintains the connectivity of the swarm, rendering the design of concrete contracting strategies a challenging task. We prove that the continuous variant of 3D-Go-To-The-Center is contracting and keeps the swarm connected. Moreover, we give a simple design criterion for three-dimensional contracting strategies that maintains the connectivity of the swarm and introduce an exemplary strategy based on this criterion.

preprint2020arXiv

The Online Multi-Commodity Facility Location Problem

We consider a natural extension to the metric uncapacitated Facility Location Problem (FLP) in which requests ask for different commodities out of a finite set $S$ of commodities. Ravi and Sinha (SODA'04) introduced the model as the Multi-Commodity Facility Location Problem (MFLP) and considered it an offline optimization problem. The model itself is similar to the FLP: i.e., requests are located at points of a finite metric space and the task of an algorithm is to construct facilities and assign requests to facilities while minimizing the construction cost and the sum over all assignment distances. In addition, requests and facilities are heterogeneous; they request or offer multiple commodities out of $S$ . A request has to be connected to a set of facilities jointly offering the commodities demanded by it. In comparison to the FLP, an algorithm has to decide not only if and where to place facilities, but also which commodities to offer at each. To the best of our knowledge we are the first to study the problem in its online variant in which requests, their positions and their commodities are not known beforehand but revealed over time. We present results regarding the competitive ratio. On the one hand, we show that heterogeneity influences the competitive ratio by developing a lower bound on the competitive ratio for any randomized online algorithm of $Ω(\sqrt{|S|}+\frac{\log n}{\log\log n})$ that already holds for simple line metrics. Here, $n$ is the number of requests. On the other side, we establish a deterministic $O(\sqrt{|S|}\cdot\log n)$ -competitive algorithm and a randomized $O(\sqrt{|S|}\cdot\frac{\log n}{\log\log n})$ -competitive algorithm. Further, we show that when considering a more special class of cost functions for the construction cost of a facility, the competitive ratio decreases given by our deterministic algorithm depending on the function.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.