From Non-Rigid to Rigid Safe Acquisition of Rigid Communication Graphs Under Limited Sensing

Jul 16, 2026

Upload by Ezra

Communication graph rigidity is essential for multi-robot formation control, yet real deployments make rigid topology maintenance difficult due to limited sensing ranges and changing operating conditions. The work develops a method to obtain an inter-robot collision-free, rigid time-varying communication graph formed by adding or removing links based on limited sensing, without requiring an initial rigid graph. It further ensures rigidity for heterogeneous nonlinear multi-robot systems using a distributed quadratic optimization controller with leader–follower hierarchical second-order consensus, validated via simulation and motion-capture hardware experiments.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages18

Reading Time45 min

Abstract

Introduction

Rigidity in formation control

Motivation: limited sensing and topology acquisition

Collision avoidance and control barrier functions

Challenges and research gap

FROM NON-RIGID TO RIGID: SAFE ACQUISITION OF RIGID COMMUNICATION GRAPHS UNDER LIMITED SENSING A PREPRINT S. Saharsh Department of Cyber Physical Systems Indian Institute of Science Bengaluru, 560012, India [saharsh2021@iisc.ac.in](saharsh2021@iisc.ac.in) Vedhas Talnikar Department of Cyber Physical Systems Indian Institute of Science Bengaluru, 560012, India [talnikarvedhas@gmail.com](talnikarvedhas@gmail.com) arXiv :2607 . 10170v1 [ cs .RO] 11 Jul 2026 Pushpak Jagtap Department of Cyber Physical Systems Indian Institute of Science Bengaluru, 560012, India [pushpak@iisc.ac.in](pushpak@iisc.ac.in) July 14, 2026 ABSTRACT Communication graph rigidity is a fundamental requirement in many multi-robot formation control approaches. However, ensuring and maintaining a rigid communication topology becomes challenging in practice due to limited sensing ranges and dynamic operating conditions. This paper provides a method for achieving an inter-robot collision-free, rigid time-varying communication graph, where communication links are established or broken according to limited sensing ranges, without assuming an initial rigid graph. In addition, the proposed approach guarantees the realization of a rigid graph for heterogeneous nonlinear multi-robot systems. A computationally lean, distributed quadratic optimization-based controller is developed for a leader–follower architecture, acquiring rigidity based on hierarchical second-order consensus among robots. Follower agents do not require global absolute positions of any agent, including their own. The proposed method is validated through both simulations and hardware experiments in a motion-capture environment, demonstrating reliable performance under the limited sensing capabilities of individual robots. For paper walkthrough: [https://youtu.be/PyHoO0E9oLg](https://youtu.be/PyHoO0E9oLg). Keywords Control barrier functions, inter-agent safety, limited sensing range, non-rigid communication graphs 1 Introduction Collective motion in nature, such as in flocks of birds, schools of fish, and colonies of ants, demonstrates how individuals can coordinate their movement while preserving spatial organization within a group. Inspired by such biological systems, multi-robot systems (MRS) have gained significant attention in civilian and military applications, including collaborative transportation, environmental monitoring, and border surveillance [1] . In these applications, multiple autonomous robots cooperate to achieve complex tasks more efficiently than a single robot operating alone. A key requirement in such cooperative missions is the ability to move the group as a rigid body or maintain a desired unique formation while ensuring safe operation in dynamic environments [2] . Formation maintenance in MRS [3] fundamentally depends on the underlying interaction topology among robots. Rigid graphs are essential to achieve unique formation shapes while using the least number of inter-robot connections [4] . This reduction in communication links directly reduces communication and sensing requirements, thereby improving scalability and energy efficiency in distributed multi-robot systems [5, 6] . However, the acquisition and maintenance of rigid communication remains the central problem in distributed formation control, and this can be illustrated through a simple example. Example 1. Consider four robots connected in a tree (chain) structure 1−2−3−4. Although the graph is connected with n − 1 = 3 edges, it does not preserve a unique formation shape through the tree edges alone, i.e., it is not rigid in R2. The formation can bend into a ring while preserving all existing edge distances, causing unconstrained distances, such as between agents 1 and 4, to vary. In general, rigidity in 2D requires at least 2n − 3 edges, carefully distributed across all agents, for n = 4, this means at least 5 edges are needed. □ Despite significant progress in formation cont

FAQs

What problem does the paper address in multi-robot formation control?

It addresses how to acquire and maintain a rigid communication topology in practice when robots have limited sensing ranges and when initial rigidity is not available.

How does the proposed method form or break communication links?

Links are established or broken according to limited sensing ranges, enabling a time-varying communication graph that becomes rigid without assuming a preexisting rigid graph.

How is collision avoidance integrated with rigidity acquisition?

A distributed safe control approach based on control barrier functions combined with quadratic programming enforces inter-agent safety while the robots pursue rigidity acquisition.

Jul 16, 2026

Upload by Ezra