Mr. Robot, a very nice young robot, feels that there is a soul mate female robot waiting for him somewhere in this world. Ms. Robot, feels the same. "We" know that they are soul mates, and were meant for each other. How can we help them finding each other in the most efficient way ?! Strange question, but has a lot of applications in the fields of computer science and robotics. For instance, if kid-Robot lost his mom-Robot, then how would they find each other with the minimum time required ? [Just kidding ! :p - although, in the work of robotics this is a real application]. The solution of the problem is used in situations where we need robots to gather at a single point and from there do a task in a collaborative fashion, such as walking in flocks to move an object, to protect an important person, or to play soccer or music.
In this post, I will give a brief idea of this problem and how to solve it in a distributed environment, using a distributed algorithm. It serves as an introductory example of distributed algorithms in general and specifically in the field of robotics. I will consider solutions that are either do not work or are not efficient, in order to better understand the problem in hand.
I will assume that the reader of this post has no previous knowledge of
distributed algorithms; which are what we will use to help the lovers find each other. We have no way of communicating with the robots, and we don't see them from above. We just want to teach them how to find each other, by giving them some
strategies (or
rules) to follow. These strategies are in the form of "if you find out ........ , then do ....... ". For example, one rule we can give to the robots would be "if you find out after walking straight for a long time a wall, then go left" or "if you find out that you walked 100 meters, then go back 200 meters ! " ... The first rule should start by "if you find out that you need start looking for your soul-mate then do ..... " [we will fill the blanks later]. These rules are called an
algorithm. These rules should be the same on every robot and this is why we call them
distributed algorithms.
The problem is a bet complicated, so we will assume a simple instance of it. We will assume that both Mr. Robot and Ms. Robot reside on a line. That is, they can only go froward and backward for as much as they want (infinite line), and they will meet each other only if they are close to each other. Yet, the problem is still hard to solve. Here are some reasons why:
- Both robots are totally identical (although one of them is Mr and the other is Ms - but in robotics word, we usually assume that all robots are identical and different only by name. I can write more about that later). Being identical means that both will have the same set of strategies and rules to follow. That is, whatever decision Mr.Robot will take given an input he sees, Ms. Robot will take the same decision if she also sees the same input. That is, if Mr. Robot decides to go forward with a certain speed given that he saw a certain thing, then Ms. Robot will do the same if she sees the same thing. Assume then that at the beginning of the search, both robots decides to start looking for each other, and both robots see the same thing, then as a result both robots will do the exact same steps, which means that the distance between the two robots never change, and sadly, they will never meet ! -- thank god the robots have different names, and they may use this difference, with a bet of our human intelligence, to avoid such situations.
- The robots cannot differentiate between foreword and backward. That is, Mr. Robot may think he is going foreword, and Ms. Robot may think the same, but still they are going on opposite directions ! This is caused because there is no reference point. The situation may happen to humans as well, and this is why we use a compass, and NORTH is our reference point there ! :)
- There are no signs on the line. If there is a unique sign on the line [already existing] then we may have the following rule that will solve our problem "If you start looking for your soul-mate, then wait for him/her at that unique point on the line".
- Robots cannot leave signs on the line. If they can, then we can let the robots keep signs on the line that says "follow me". This will facilitate the searching process.
- "We" are not there with them ! [if "we" were there, then we could simply match them ... but "we" can only help them by giving them a set of rules to follow -- i.e, a distributed algorithm -- and nothing more]
If they were not identical, then Mr. Robot, knowing that he is the male, will go backward and foreword increasing the range of his trips each time, while Ms. Robot will wait for him, until they will occasionally meet ! - but since they are identical, the two robots may stay still ! Because we have no means of letting one robot wait for the other, because the robots will be stuck on the question of "who should wait ? me or him/her ?! " - and if both wait, then they will never meet.
Also, let's say that we are going to solve the question by telling a robot to 1) pick to go either backward or forward, and keep going until you find your "other". Then in this case, Mr. robot may pick to go "his" backward and Ms. robot may follow "her" forward [which would probably lead them to go in opposite directions]. They will walk indefinitely on the opposite directions and never meet ! of course, there may go on meeting directions and find each other suddenly. [Remember: the robots are on one infinite line. They may have different definition of backward and forward. Note: meeting directions: they will suddenly meet, opposite directions, never meet].
If the robots know the distance between each other [let's call it the
maximum distance], then the robot will use this information to avoid a situation in which they search indefinitely for the other in one direction only. But knowing this information, we can give the robots the following rule [which does not work]: "Pick one random direction [foreword or backward]. Pass the maximum distance. If you find your soul-mate, then we are all happy ! If you did not find her/him, then go back to the point from which you started (the origin point), and pick the opposite directions, and pass the maximum distance". Yet, we will find a problem herein. I will explain why. Let set a reference directions which we call "our backward" and "our forward". The robots, again, may have their own definition of directions. That is, Mr. Robot backward is our foreword, but Ms. Robot backward is our backward. Let's say that for Mr. Robot to find Ms. Robot, then Mr. Robot will have to go our backward (his foreword), and Ms. Robot go our forward (her foreword). Then, let's say Mr. Robot decided to go our foreword, and Ms. Robot decided to go our foreword too. Then each will pass the maximum distance and they wont find each other. Then they will return to the origin point. Then, both will decide to go our backward and each will pass he maximum distance without finding each other. They will repeat this forever, never find each other !
These are the main difficulties we may face. The solution of the problem will be given in another post as soon as possible. If I am lucky enough, a reader [not necessarily computer science expert] will give me a good solution, and we can publish this solution together in a well-respect computer science journal; where most of the solutions of this problem are published !