A discrete and continuous study of the \textsc{Max-Chain-Formation} problem

DOI10.1016/J.IC.2022.104877MaRDI QIDQ2672258zbMATH OpenOpenAlexFDO

Authors Jannik Castenow, Peter Kling, Till Knollmann, Friedhelm Meyer auf der Heide

Publication date 8 June 2022

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.02043

zbMATH Keywords

chain formationcontinuous timemax-chain formationmobile robotsruntime

Mathematics Subject Classification ID

Artificial intelligence for robotics (68T40) Analysis of algorithms (68W40)

Abstract: Most existing robot formation problems seek a target formation of a certain emph{minimal} and, thus, efficient structure. Examples include the Gathering and the Chain-Formation problem. In this work, we study formation problems that try to reach a emph{maximal} structure, supporting for example an efficient coverage in exploration scenarios. A recent example is the NASA Shapeshifter project, which describes how the robots form a relay chain along which gathered data from extraterrestrial cave explorations may be sent to a home base. As a first step towards understanding such maximization tasks, we introduce and study the Max-Chain-Formation problem, where $n$ robots are ordered along a winding, potentially self-intersecting chain and must form a connected, straight line of maximal length connecting its two endpoints. We propose and analyze strategies in a discrete and in a continuous time model. In the discrete case, we give a complete analysis if all robots are initially collinear, showing that the worst-case time to reach an $varepsilon$-approximation is upper bounded by $mathcalO(n^{2}cdotlog(n/varepsilon))$ and lower bounded by $Omega(n^{2}cdotlog(1/varepsilon))$. If one endpoint of the chain remains stationary, this result can be extended to the non-collinear case. If both endpoints move, we identify a family of instances whose runtime is unbounded. For the continuous model, we give a strategy with an optimal runtime bound of $Theta(n)$. Avoiding an unbounded runtime similar to the discrete case relies crucially on a counter-intuitive aspect of the strategy: slowing down the endpoints while all other robots move at full speed. Surprisingly, we can show that a similar trick does not work in the discrete model.

Recommendations

• A Discrete and Continuous Study of the Max-Chain-Formation Problem
• The Max-Line-Formation Problem
• Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms
• An Optimal Algorithm for the Maximum Two-Chain Problem
• Continuous Characterizations of the Maximum Clique Problem
• On the size of maximal chains and the number of pairwise disjoint maximal antichains
• An algorithmic approach to maximal unions of chains in a partially ordered set
• On the size of maximal antichains and the number of pairwise disjoint maximal chains
• An Optimal Algorithm for the Maximum Three-Chain Problem
• Extended and discretized formulations for the maximum clique problem

Cites work

• A continuous strategy for collisionless gathering
• A Discrete and Continuous Study of the Max-Chain-Formation Problem
• Book review of: D. A. Levin et al., Markov chains and mixing times. 2nd edition
• Discrete Dynamical Systems
• Eigenvalues and eigenvectors of some tridiagonal matrices
• Energy-efficient strategies for building short chains of mobile robots locally
• Fast Uniform Scattering on a Grid for Asynchronous Oblivious Robots
• Forming tile shapes with simple robots
• Gathering a Euclidean closed chain of robots in linear time
• Gathering of asynchronous robots with limited visibility
• scientific article; zbMATH DE number 2157777 (Why is no real title available?)
• Local Gathering of Mobile Robots in Three Dimensions
• Local spreading algorithms for autonomous robot systems
• On lower bounds for the largest eigenvalue of a symmetric matrix
• Optimal strategies for maintaining a chain of relays between an explorer and a base camp
• The Multi-Agent Rendezvous Problem. Part 1: The Synchronous Case
• Universally optimal gathering under limited visibility

Cited in

(7)

• Lost in self-stabilization: a local process that aligns connected cells
• Gathering a Euclidean closed chain of robots in linear time and improved algorithms for chain-formation
• A continuous, local strategy for constructing a short chain of mobile robots
• Energy-efficient strategies for building short chains of mobile robots locally
• A Discrete and Continuous Study of the Max-Chain-Formation Problem
• The Max-Line-Formation Problem
• Optimal strategies for maintaining a chain of relays between an explorer and a base camp

This page was built for publication: A discrete and continuous study of the \textsc{Max-Chain-Formation} problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2672258)