Communication-Aware Coordination of Multi-Agent Systems under Spatio-Temporal Constraints

QC 20251009

Abstract

Over the past decade, the rapid growth of computational power available in embedded systems has fueled increasing interest in autonomous systems with real-time planning and control capabilities, aimed at satisfying spatially and temporally defined goals. Many such systems have already become part of everyday life—for example, robotic vacuum cleaners, drone deliveries, and autonomous taxis. In this context, the control and robotics community has devoted significant effort to developing formal frameworks for rigorously defining system-level specifications and verifying progress toward their satisfaction. More specifically, when dealing with systems composed of possibly heterogeneous autonomous agents, the development of scalable and reliable coordination algorithms that can drive the agents toward the satisfaction of common objectives, while operating under limited communication capabilities, is of pivotal importance.

The work presented in this thesis lies at the intersection of multi-agent coordination and formal verification. The overarching goal is to develop task assignment, planning, and control algorithms for coordinating multi-agent systems subject to sparse communication topologies, with the objective of satisfying system-wide spatio-temporal goals. To this end, we adopt Signal Temporal Logic (STL) as the primary modeling framework, providing a precise and unambiguous language for specifying system-level objectives. In parallel, we leverage the framework of Control Barrier Functions (CBFs) to bridge high-level specifications with low-level control objectives, which can then be approached using tools from nonlinear and non-smooth analysis.

Building on this foundation, the first part of the thesis introduces a novel framework for representing inter-agent task dependencies through a task graph, where edges capture collaborative tasks among agents. Based on this representation, we design algorithms that allow task dependencies between non-communicating agents to be decomposed (or rerouted) through agents that are instead connected via communication links. This decomposition serves as a key enabler for feedback-based control approaches to achieve system-wide objectives in a scalable and reactive manner, by ensuring consistency between the given tasks and the communication dependencies imposed by the network topology.

The second part of the thesis presents a control architecture for driving a multi-agent system toward the satisfaction of a system-wide task, under the assumption that the associated task graph is acyclic. The controller we propose is implemented in a sampled-data fashion, as is typical in embedded systems, while we provide analytical results that guarantee task satisfaction in continuous time. This dual perspective bridges the gap between the digital nature of embedded control and the continuous-time dynamics of the physical system.

The third and final part of the thesis departs slightly from the content of the first two by focusing on trajectory synthesis. Specifically, we develop a sampling-based planning algorithm for generating trajectories that satisfy spatio-temporal goals for systems with linear dynamics. We will then address the extension of the proposed framework to multi-agent settings in future research endeavors.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-371346