Correct-by-construction control synthesis for multi-robot mixing

Yancy Diaz-Mercado, Austin Jones, Călin Belta, Magnus Egerstedt2015 · DOI

Abstract

This paper considers the problem of controlling a team of heterogeneous agents to conform to high-level interaction (coordination, sensing, and communication) missions. We consider interactions that can be specified via symbolic inputs from the braid group. We define a novel specification language, called Braid Temporal Logic (BTL), that allows us to specify rich, temporally-layered tasks involving agents' locations in an environment, their relative positions to each other, and frequency of location swaps and information exchanges between agents. We use techniques from formal methods to generate symbolic inputs that conform to a given BTL specification and use recently developed hybrid optimal control synthesis techniques to enact the synthesized pattern. The generated trajectories are provably guaranteed to be collision-free, respect physical boundaries of the agents' mission space, and to satisfy the high-level mission. Results are validated via implementation on a team of wheeled robots.

Introduction

Coordinating multi-robot teams requires balancing high-level mission logic—such as conditional task sequencing and inter-agent communication—with low-level physical safety requirements. Traditional control methods often rely on absolute positioning or simple graph connectivity, which struggle to capture the nuances of relative interactions over time. Furthermore, as the number of robots ($N$) increases, the state space of possible configurations grows factorially ($N!$), leading to a computational bottleneck in standard formal synthesis. This research introduces Braid Temporal Logic (BTL) and a corresponding synthesis pipeline to provide a "correct-by-construction" solution that ensures both mission compliance and collision avoidance.

Methodology: Braid Theory and BTL

The core of this approach is the representation of robot trajectories as "strands" in a mathematical braid. In this framework, the paths of $N$ robots in space-time are viewed as a braid where crossings represent physical swaps or interactions between adjacent agents.

Braid generators and their compositions representing robot swaps.

As shown in Figure 1, complex interactions can be decomposed into fundamental braid generators ($\sigma_i$). This topological approach inherently encodes collision avoidance: because strands in a braid are defined as non-intersecting in space-time, any controller that successfully tracks a braid is guaranteed to be collision-free.

Building on this, the authors propose Braid Temporal Logic (BTL), a specification language based on syntactically co-safe Linear Temporal Logic (scLTL). BTL allows for the definition of predicates based on:

  • Location: Whether an agent is within a specific region.
  • Proximity: Whether the distance between two agents is within a defined threshold.
  • Interaction: Whether two agents have performed a specific "crossing" or swap.

Language-Guided Synthesis

To overcome the state-space explosion inherent in multi-robot systems, the paper introduces a language-guided synthesis algorithm. Rather than constructing a complete Braid Transition System (BTS) that accounts for every possible permutation of robots, the algorithm uses the BTL specification to guide a "backwards" search.

Formal methods pipeline: (a) Braid Transition System, (b) BTL formula automaton, (c) Product automaton, and (d) resulting braid.

By starting from the desired "accepting" states of the mission automaton (Figure 3b) and working backward to the initial configuration, the system can prune the vast majority of irrelevant states. This results in a product automaton (Figure 3c) that is significantly smaller and more computationally efficient than those produced by standard exhaustive methods.

Experimental Results

The framework was evaluated through both computational benchmarks and physical experiments with six Khepera III differential-drive robots.

Key findings include:

  • Computational Efficiency: In a 4-agent scenario, the language-guided algorithm synthesized a solution in 3.7 seconds, compared to 939 seconds for standard approaches—a 250x improvement.
  • Physical Safety: During tests with six robots, the system maintained a minimum inter-robot distance of 0.132m. Given the robots' 0.13m diameter, this demonstrates the system's ability to operate safely at the very edge of the physical margin.
  • Mission Complexity: The system successfully executed complex, 30-symbol BTL formulas involving conditional visits and sustained proximity constraints between specific agent pairs.

Conclusion and Future Work

BTL provides a robust framework for synthesizing complex, relative interactions in multi-robot teams. While the current approach significantly improves scalability, future work will address the "Mixing Limit" ($M^*$)—the physical boundary of how many swaps can occur in a given space—and the adaptation of BTL to dynamic environments with moving obstacles.

Summary updated

Abstract

This paper considers the problem of controlling a team of heterogeneous agents to conform to high-level interaction (coordination, sensing, and communication) missions. We consider interactions that can be specified via symbolic inputs from the braid group. We define a novel specification language, called Braid Temporal Logic (BTL), that allows us to specify rich, temporally-layered tasks involving agents' locations in an environment, their relative positions to each other, and frequency of location swaps and information exchanges between agents. We use techniques from formal methods to generate symbolic inputs that conform to a given BTL specification and use recently developed hybrid optimal control synthesis techniques to enact the synthesized pattern. The generated trajectories are provably guaranteed to be collision-free, respect physical boundaries of the agents' mission space, and to satisfy the high-level mission. Results are validated via implementation on a team of wheeled robots.
BibTeX
@misc{diazmercado2015correct,
  author = {Yancy Diaz-Mercado and Austin Jones and Călin Belta and Magnus Egerstedt},
  title = {{Correct-by-construction control synthesis for multi-robot mixing}},
  year = {2015},
  doi = {10.1109/cdc.2015.7402112},
}
Figure