Teacher resources and professional development across the curriculum

Teacher professional development and classroom resources across the curriculum

Monthly Update sign up
Mailing List signup
Search
MENU

Unit 4

Topology's Twists and Turns

4.8 Robots

Imagine that you are the manager of an automated manufacturing facility. You have invested large sums of money in a pair of state-of-the-art robots to assist in the production of widgets. The production process is a five-step process, requiring each of your two robots to visit five separate locations on your manufacturing floor. The possible paths connecting the five stations are as shown:

K5

Now, the above graph displays all possible routes between the stations, but some routes are actually preferable to others. In particular, you probably don't want routes that could lead to the robots colliding with one another, resulting in costly and time-consuming repairs. So, you would like to restrict the movement of the robots somewhat, so that they can accomplish their tasks with the least chance of collision. In short, you wish to consider only those route configurations that are safe for the robots.

One way to ensure that the robots never collide with one another is to insist that they always maintain at least a one-full-edge distance between themselves. In such a system, if one robot (robot 1) were at station A, then robot 2 could not be on any of the edges that connect to station A.

Robot Positions

What's more, if robot 1 were on the edge between A and E, then robot 2 could not be at either A, or E, or on any edge that connects to either of them.

Robot Positions

With these rules in place, we can organize all the possible safe configurations into a topological object called a “configuration space.” A configuration space is a topological surface that represents all the possible arrangements or configurations of a physical system, such as that of our robots and their work stations. We can construct this surface by systematically cataloging all allowable positions of robots in real space and correlating them with the intrinsic cell decomposition of the surface.

The first thing to consider in describing this space is what happens when each robot is at a station. We can think of these configurations as discrete, in that a robot is either at a particular station or it is not. This suggests to us that the representation of these configurations in configuration space should be vertices. A vertex has no degrees of freedom, and this corresponds well to the idea that if both robots are at stations, neither is free to change position.

So, for every possible way that two robots can be at two different stations, we will have a unique vertex in our configuration space. If robot 1 is at station A, then robot 2 has four possible locations. Applying this thinking around the stations leads us to conclude that there are 5 ×(5-1) possible ways for the two robots both to be at stations. This means that our configuration space will have 20 vertices.

Let's consider now what happens when robot 1 is at a station and robot 2 is on an edge. This is no longer a nice, discrete situation, for although robot 1's position is fixed nicely, robot 2's precise position on any particular edge can vary. This suggests to us an object with one degree of freedom, which is a line segment, or because we are thinking in terms of graphs, an edge. So, how many ways are there for one robot to be fixed at a station as the other robot is traversing an edge? If robot 1 is fixed at a station, then robot 2 can be on any of six possible edges.

Vertex, Edge, Face

Following this reasoning around the graph, we find that there are 30 possible arrangements in which robot 1 is in a fixed position and robot 2 is “moving.” Applying the same logic, there must also be 30 ways for robot 2 to be fixed while robot 1 changes position. This means that there are 60 possible ways for one robot to be fixed at a station while the other robot is moving on an edge. We said earlier that each of these ways corresponds to an edge in configuration space, so in addition to the 20 vertices, our space has 60 edges.

The final situation to consider is when both robots are in transit—that is, neither is fixed, both are allowed to move. This arrangement suggests to us an object with two degrees of freedom, which is a face. So, each possible way that both robots can be in transit corresponds to a face in configuration space. We must still follow the “one-full-edge-apart” rule, however, to ensure that there are no collisions, so if we confine robot 1 to a particular edge, as in the third image in the diagram above, then robot two is restricted to three possible edges.

Going around the graph and applying this reasoning, we find that there are 15 ways for robot 1 to be confined to a particular edge and robot 2 to another edge. Consequently, as the roles of the robots are reversed, there must be another 15 possible scenarios. This translates into 30 total ways for both robots to be in transit, and each of these ways corresponds to a face in configuration space. So, in addition to 20 vertices and 60 edges, our configuration space has 30 faces.

To construct this space, it is necessary to label every vertex, edge, and face meticulously, and then to put these pieces together in some consistent manner. There are many ways to do this; here is a portrayal of one such way:

Configuration Space

Now that we have constructed this space, we can plot paths through it and be confident that those paths will correspond to sequences of safe movements for the robots on the manufacturing floor. One thing that we must recognize is that, when we mark a path in configuration space, we will inevitably come to a boundary of a face (as indicated by the blue point in the diagram). Note that a path that leaves a face will return (i.e., re-enter the configuration space) on some other face, just as with our intrinsic box diagrams that we explored earlier. The possible connections portrayed on this intrinsic representation of this striking shape are very hard to grasp intuitively. Here is where Euler's formula can be of help.

Because our configuration space has 20 vertices, 60 edges, and 30 faces, we can substitute these values into the V – E + F formula; doing so gives us an Euler characteristic of -10. Using this Euler number, we can find the genus of this object by using the formula Χ= 2 - 2g, where g is the genus and Χ is the Euler number. Substituting -10 for Χ and solving for g, we come up with a genus of six. Recall that a surface's genus is simply the number of holes that it has, so we have discovered that our configuration space is actually a six-holed torus! (We neglected to mention earlier that this configuration space is an orientable surface.)

Six-Holed Torus

It would have been difficult to say at the beginning that the possible configurations that enable two robots to visit five manufacturing stations safely would end up forming a space that is topologically equivalent to a six-holed donut. Nevertheless, the problem works out beautifully, and this is the reality of the situation.
In this problem, we reduced a physical situation to an intrinsic topological model. We then analyzed this model to find out what kind of a 2-manifold it was. In our final section, we will turn our attention to the larger question of 3-manifolds. We will come face to face with the challenge of understanding an object so large that even catching a glimpse of its intrinsic topology would be a great breakthrough. This object is our own universe.

back to top

Next: 4.9 The Shape of Space


HomeVideo CatalogAbout UsSearchContact Us

© Annenberg Foundation 2013. All rights reserved. Privacy Policy