Robotic Mixing Using Braids

Convoy Protection Surveillance

A side objective of the convoy protection problem is for protecting agents to periodically surveil areas in the vicinity of the convoy. Due to limited sensor footprints, agents must coordinate their movements to maximize the area surveilled, while ensuring that these movements are collision free.

Motivational Application to Mixing

Consider the convoy protection scenario depicted above. In particular, consider the side objective of having a UAV team fly over and offer visual coverage of the surrounding area. It is of interest that a team of UAV is able to cover as much of the area to surveil as possible as they “sweep” across. Assuming the agents have a limited sensor footprint, they’ll need to have rich movement patterns in order to increase their coverage. However, these patterns will need to be coordinated to avoid collisions as the agents share the airspace. We approach the problem of having these robots mix, or interacting with each other consistently in the airspace, by borrowing concepts from algebraic topology, namely from the Braid Group.


Braids and Robotics

Two Robot Braid Setup

As depicted in the figure, if two agents beginning at two corners of a square need to move across to the remaining corners, they can accomplish this by moving straight across or by having their paths crisscross. This two movement patterns can be associated with elements in the braid group. Using this idea, we utilize the generators of the braid group together with the concatenation operation to form symbolic strings of movement patterns. We then interpret these symbolic strings and map them to braid controllers. The braid controllers then take the multi-agent system dynamics into consideration to generate control laws so the agents achieve these patterns while avoiding collisions.

The simulation result below demonstrates one of our proposed algorithms for a particular class of mobile agents performing a randomly generated braid. This seven agent system of unicycle robots is performing a braid of length 10. It can be observed that all the agents achieve the secondary objective of arriving at the intermediary way points (the bubbles on the paths) at the same times, and that collisions are avoided throughout their excursion.


Seven Agent Braid

Seven agents executing a randomly generated braid string.






  • Yancy Diaz-Mercado and Magnus Egerstedt. “Multi-Robot Mixing Using Braids.” Decision and Control (CDC), 2013 IEEE 52nd Annual Conference on. IEEE, 2013.



Comments are closed.