Knowledge in multi-robot systems: an interplay of dynamics, computation and communication
Giorgio Cignarale, Stephan Felber, Eric Goubault, Bernardo Hummes Flores, Hugo Rincon Galeana · 2025
Read Knowledge in multi-robot systems: an interplay of dynamics, computation and communication by Giorgio Cignarale, Stephan Felber, Eric Goubault, Bernardo Hummes Flores, Hugo Rincon Galeana (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18309.txt.
Introduction
Giorgio Cignarale and co-authors wrote this robotics and logic paper, published in two thousand twenty-five, on what teams of robots can be said to know. A robot swarm solves tasks like exploring a space or gathering in one place only if the right knowledge reaches the right robots.
The authors build a framework that joins the physics of moving robots with temporal epistemic logic, the formal study of who knows what, and when. Physical motion and on-board computation are kept in separate layers, so control theory and distributed computing tools each apply cleanly. A method converts a switched hybrid model of the robots into a logic model, step by step through an abstract machine. From that model they derive conditions under which exploring and gathering can be guaranteed. The authors offer the frame as a meeting ground for three fields that rarely talk.
Catalog record
| CREATOR | Giorgio Cignarale, Stephan Felber, Eric Goubault, Bernardo Hummes Flores, Hugo Rincon Galeana |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-18309
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Knowledge in multi-robot systems: an interplay of dynamics, computation and communication Giorgio Cignarale, Stephan Felber, Eric Goubault, Bernardo Hummes Flores, Hugo Rincon Galeana Abstract In this paper, we provide a framework integrating distributed multi-robot systems and temporal epistemic logic. We show that continuous-discrete hybrid systems are compatible with logical models of knowledge already used in distributed computing, and demonstrate its usefulness by deriving sufficient epistemic conditions for exploration and gathering robot tasks to be solvable. We provide a separation of the physical and computational aspects of a robotic system, allowing us to decouple the problems related to each and directly use methods from control theory and distributed computing, fields that are traditionally distant in the literature. Finally, we demonstrate a novel approach for reasoning about the knowledge in multi-robot systems through a principled method of converting a switched hybrid dynamical system into a temporal-epistemic logic model, passing through an abstract state machine representation. This creates space for methods and results to be exchanged across the fields of control theory, distributed computing and temporal-epistemic logic, while reasoning about multi-robot systems. TU Wien, Vienna, [email protected] TU Wien, Vienna, [email protected] École Polytechnique, Palaiseau, [email protected] École Polytechnique, Palaiseau, Francebernardo.hummes-flores@lix.polytechnique.fr0000-0003-2325-1497 TU Berlin, Berlin, [email protected] {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10010520.10010553.10010554¡/concept_id¿ ¡concept_desc¿Computer systems organization Robotics¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003790.10003793¡/concept_id¿ ¡concept_desc¿Theory of computation Modal and temporal logics¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003753.10003761.10003763¡/concept_id¿ ¡concept_desc¿Theory of computation Distributed computing models¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Computer systems organization Robotics ccs Theory of computation Modal and temporal logics ccs Theory of computation Distributed computing models keywords distributed computing, mobile robotics, temporal-epistemic logic, switched system, robot tasks † † runningtitle: Knowledge in multi-robot systems † † runningauthor: G. Cignarale, S. Felber, E. Goubault, B. Hummes Flores, H. Rincon Galeana 1 Introduction We formulate in this paper a framework connecting a hybrid systems approach to distributed multi-robot systems and temporal epistemic logic. This forms a bridge whose value is twofold: we bring the success of logical analysis of tasks in distributed computing [ 17 ] to distributed robotics, and we generalize the multi-robot model from state machines to dynamical systems [ 33 ] , drawing a much closer frontier to real-life applications. The distributed coordination of robots combines problems found in control theory [ 35 , 25 ] with the problems commonly found in distributed computing [ 30 ] . By clearly separating the roles of the physical and computational parts of a robot, we are capable of showing a translation layer from distributed computing and control theory. While robotics is traditionally concerned with physical entities that must behave in accordance to their dynamical constraints, the distributed computing perspective arises once the robots must exchange information under varying difficulties associated to their communication capacities [ 1 , 12 ] . For instance, understanding the impact of synchrony, coordination and message loss are essential for the efficient design and analysis of state-of-the-art multi-robot systems solving various tasks. Our modeling is extended for the multi-robot scenario, where we introduce the notion of a scheduler as a path in the space of executions, so to tie local to global time. Bridging these fields enables us to combine well-known methods and results from control theory, distributed computing and temporal epistemic logic in a simple and harmonious fashion. Our framework successfully captures the spatial information used to reason about multi-robot tasks, namely exploration and gathering, as it is constructed with the memory of the robots during their computations. We devise a logical model consisting of a variation of the runs and systems framework, which we construct by defining explicitly a distributed state machine for both the system dynamics and the robot protocols. We further demonstrate the usefulness of our approach by deriving the first ever sufficient epistemic conditions for solving the exploration, surveillance and approximate gathering robot tasks. In [ 1 ] the authors famously showed that exact gathering is impossible by reducing the robot task to the consensus problem in distributed computing and deriving its well understood impossibility borders from there. In essence, the present paper puts this reduction on a sound footing by deriving the distributed system implied by the control theoretic model and equipping it with the tools found in epistemic logic. The distributed computing community has approached the characterization of tasks in distributed robot systems [ 18 ] in various ways, such as according to the system space (continuous or discrete) [ 3 , 11 ] , communication capacities [ 37 ] and synchronicity [ 26 ] . Model checking using linear temporal logic is also a common tool in this computational perspective of robotics, where it has been used for gathering [ 14 ] , perpetual exploration [ 13 , 5 ] and terminating exploration [ 5 ] . The control theoretic view on multi-agent systems has been developed by a number of authors, see e.g. the survey [ 4 ] . Similarly, logical views on hybrid systems have been considered, see e.g. [ 32 ] . As we mentioned also, logics, in particular epistemic logic [ 22 ] and temporal-epistemic logic [ 27 ] have been developed and applied to multi-agent systems, through in particular epistemic planning [ 15 ] . Epistemic logic [ 23 ] is a powerful conceptual tool for reasoning about the uncertainty of agents in a system, both regarding facts and other agents’ epistemic states, making it especially suitable for the modeling of multi-agent systems, including distributed systems. It was adapted for and introduced to distributed systems in [ 22 ] , subsequently employed to characterize: the firing rebels with relay in [ 19 ] , two agent approximate consensus in [ 28 ] , sufficient conditions for stabilizing consensus in [ 8 ] , optimal consensus with respect to message transmission in [ 20 ] and different notions of knowledge in [ 31 ] , to name just a few. A crucial feature of epistemic logic in multi-agent systems is that it provides a precise and formal representation of higher order epistemic attitudes, such as nested and/or common knowledge, often crucial for the success of distributed tasks. For instance, coordinated actions are inevitably tied to nested knowledge, i.e., any agent needs to know to some extent what other agents know in order to successfully execute a coordinated behavior [ 31 ] . Another interesting feature of epistemic logic is that, when combined with temporal logic, it allows to express properties that must hold (and be known) throughout the execution, without focusing on the specific communication mechanisms leading to such knowledge. Thus, epistemic logic is a universal vehicle for expressing communication models, including those that rely on lack of explicit communication (also known as communication by silence) [ 19 , 20 ] . Our approach is the first one to seamlessly integrate these three complementary views: the ones from control theory, distributed systems and temporal epistemic logic. Contributions. We present, to the extent of our knowledge, the first interdisciplinary framework that connects all three fields of control theory, distributed computing, and temporal epistemic logic, in a general setting that enables a comprehensive and integral approach to multi-robot systems. We showcase the potential of our framework by defining a simple yet sufficiently expressive temporal epistemic language that allows us to express multi-layered