A Discrete and Continuous Study of the Max-Chain-Formation Problem: Slow Down to Speed up

Abstract

Robot coordination problems deal with systems consisting of many autonomous, but simple, mobile agents that try to achieve a common, complex task. The agents' capabilities depend on the exact model and task but are typically very restricted. For example, there is usually no common coordinate system or sense of direction, and agents often have limited sensing capabilities. Among the most basic and well-studied type of tasks are GATHERING problems, in which initially scattered agents must gather at a single point. CHAINFORMATION problems represent another important formation primitive. Here, agents take the role of communication relays that, initially, form a winding chain connecting two base stations. The relays are to move such that the chain becomes straight, allowing for a more energy-efficient communication along the relay chain. Both GATHERING and CHAINFORMATION problems can be described as contracting: starting from an initially scattered formation, they seek to reach a smaller, more efficient structure. A natural complement are extension problems, where agents start in an initially dense formation and seek to reach an extended formation that covers as much area as possible. While there are some results about extension problems if agents move on grids or rings, results in standard discrete and continuous models for the Euclidean plane are scarce. Our work introduces the MAXFORM problem on the Euclidean plane and provides first analytical results for both the discrete and continuous case.