by Carl Pierer
This column last month, here, provided a first glimpse at the fascinating field of braids. Beneath their obvious beauty – to which their widespread aesthetic use bears testimony – lies a deep complexity. They allow for explorations of many beautiful areas of mathematics. They branch into topology, group theory, and geometry, to give some examples. The previous essay explored the theoretical side of braids, the most important results of which were:
- A mathematical concept of braids: Consisting of a certain number of strands n, say, together with a specification of how and where these strands cross each other. Furthermore, these strands (if they are not crossing) run parallel and we may adopt the convention that they are running from top to bottom. To avoid ambiguity, we require further that there are no two crossings at the same horizontal level. It is clear that for the braid to have any crossings at all, it must have at least two strands. If a braid does not have any crossings, it is called the trivial braid.
- The word problem: Thus defined, a braid can be represented with a description of how the strands cross each other. Let σI mean the ith strand is crossing over the i+1th strand and a negative power, σi-1 (read: sigma i inverse), mean the ith strand crosses under the i+1th strand. Then, a description of a braid using σI's is called a braid word. The problem is: given two braids, how can we decide whether they are the same? More particularly, given a braid, how do we determine whether it is trivial?
- A solution to the word problem: The method of handle reduction. If a braid contains handles, it can be reduced. If the braid is the same as the trivial braid, this algorithm will return the trivial braid. If the braid is not trivial, this algorithm will return an equivalent braid that does not contain any handles.
It ended there with a very cursory glance at the connection between braids and dances. This idea deserves to be dealt with in greater depth, for it is not only in the abstract spheres of pure mathematics that braids demonstrate a fascinating depth. Rather surprisingly, their mathematical properties find unexpected applications to the more practical problems of motion planning for robots.
Imagine a set of dancers in a room with a very high ceiling. Each of the dancers holds a ribbon, all of which are fixed at the same point on the ceiling. In many regions in the Alps, there is a custom of dancing around a May pole, where each dancer holds a ribbon. The idea here is exactly the same. As the dance unfolds and as the dancers dance around each other, they will braid their ribbons. The particular braid that results from such a dance, will thus encode the movements of the dancers.
An example will help to make this more tangible. This method has been used to analyse and describe ceilidhs[i]. A suitable ceilidh for illustrative purposes is the dance called The Borrowdale Exchange. Here are videos of the dance. The following is a description of the dance. The initial line-up is 3 couples in a circle.
1. All 6 hands round and back; [1-8]
2. Retaining hands, all advance and retire; [9-12]
3. All dos-si-dos with partner; [13-16]
4. All take hands with opposite (now the new partner) for Right Hands Across, finishing by retaining hold and raising hands into an arch; [17-20]
5. Lady with lowest right hand dances under the arch to take promenade hold with partner; [21-22]
6. Next Lady repeats bars 21-22; [23-24]
7. New couples promenade anywhere in the room to find 2 other couples for the next Repeat [25-32] [ii]
This description gives the following braid word:
1. This movement, the dancers moving in a circle in one direction and back, cancels.
2. Advance and retire means the dancers move towards the centre and back, so this does not affect the braid.
3. dos-si-dos means the two dancers pass each other giving right shoulders, passing back to back and dance back to where they started from. The corresponding braid word is: σ12 σ32 σ52
4. Right Hands Across, in this movement the dancers put their right hands in the centre and dance around a circle in clockwise direction. The corresponding braid word is: (σ1 σ2 σ3 σ4 σ5)-3
5. Lady with lowest right hand dances under the arch to take promenade hold with partner. The corresponding braid word is: σ1-1 σ2-1 σ4 σ3 σ5 σ4.
6. Next Lady repeats bars 21-22; i.e. step 5. The corresponding braid word is: σ1-1 σ3 σ2.
7. For simplicity, the braid is only shown for one repeat and one set of dancers.
The total braid word is: σ12 σ32 σ52 (σ1 σ2 σ3 σ4 σ5)-3 σ1-1 σ2-1 σ4 σ3 σ5 σ4 σ1-1 σ3 σ2. (Fig. 2) gives the resulting braid.
This dance nicely illustrates some of the problems of modelling a dance using braids. Firstly, there are some movements that cancel immediately. This means one movement undoes the interleaving of the strings done by the previous movement. In the braid it is as if the two movements never happened. Secondly, there is some liberty to choose which strand represents which dancer in the braid. Different choices will give different braids. It is not clear how to make sure that these two braids are mathematically equivalent. Thirdly, some things are ambiguous in the description of the dance: how many positions do dancers move through in the right hands across movement? Who is the lady with the lowest hand? Such ambiguities require decisions that again will affect the braid. It is not obvious how to make sure that no matter what decision is taken, all the braids will be equivalent. Lastly, most intricately: a braid presumes that the strands always occupy the same positions unless they are involved in a crossing. In a dance, however, the dancers are not tied to certain positions and move around more smoothly. For example, they could start off standing in a line but then move into a circle. A braid model would always have to map the latter back to the former, as the positions of the strands in the braid are fixed. Despite these difficulties and simplifications, the model permits to translate dances into mathematical entities.
In a braid, two strings, although they may touch, are never allowed to pass through each other – there is no collision of strings. More mathematically, no two strings occupy the exact same position at any one time. This relatively obvious fact can be put to rather unexpected use.
A very general question of motion planning in robotics is: How can a certain number of robots move around a given area, without bumping either into each other or any obstacles? Topological concepts and ideas have found a curious application here. In particular, braids are also the focus of research on this and similar questions[iii].
As with the dance, we can take the strands of a braid to correspond to the objects we would like to move around without collision. At any time, the bottom of the strands specifies the positions of the objects at that time. Furthermore, because the strands are not allowed to pass through each other, the braid specifies a movement from an initial configuration of the objects in collision-free path to a final configuration. Note that the objects here are required to move only in a plane.
To illustrate the idea, take a braid (e.g. the right of Fig. 3)[iv]. Take a disk that cuts through horizontally this braid at a given point, say t. Then, looking at the disk (on the left in Fig. 3), we see the positions of the strings as points at this particular point. We can now conceive of these points as the objects at their relative positions in the plane. Taking the axis running from top to bottom to signify time, such a cut through the braid gives us the positions of the objects at time t. Then, the whole braid will give the total movements of the objects during the time of the movement. The projection of the braid onto the plane will give the paths in the plane.
Furthermore, braids of the same number of strands have an operation defined on them. This simply means that we can stick two braids together and we get another braid (which still has the same number of strands, unsurprisingly). But this fact means that by defining elementary braids (indeed, the σI'sthat make up the braid words), we can express a braid word of arbitrary length and complexity in terms of these elements, simply by specifying which elements are used and the order in which they are put together.
Taking together the two ideas allows to employ the rather abstract mathematical notion of braids to solve very practical problems in robotics efficiently. Be it in a factory, where a number of robots have to move around without bumping into one another or be it on screen, where animated points are required to follow a dance pattern, the properties of braids prove very useful. In the latter case, the combinatorial properties can be exploited to allow creative combinations of basic movements that recur in certain kinds of dances. It is thus relatively easily possible to create a programme that allows for designing and animating dances.
Starting from a fairly simple and everyday object via a detour through pure mathematics allowed for rather unexpected applications. Of course this is not the end of the matter, there is much more to braids than can be explored in the scope of this essay. But this second glimpse allows to appreciate the mathematical depths lurking behind braids.
They are very curious objects, indeed.
[i] It has been mentioned in the last essay as well, but for good measure: Ceilidhs are traditional Scottish Folk Dances, which are usual held at gatherings. The intention is that no prior knowledge should be needed and every dance at a Ceilidh will be explained by a caller at the beginning. Even if you are a very dispassionate dancer, do not miss out on the chance to attend a Ceilidh!