Lead and Follow (or, making low-cost robots dance), Part 2

In part 1, I introduced my Edison robots, and my plans to get one of them to lead the other one in a choreographed dance. Now read on…

As I was saying, the key to solving this problem is getting the one of the robots to reliably send multiple-byte sequences to the other, which I’ve made responsibility of two methods: sendReliably() and readReliably(). How do we go about doing this?

It helps to think about what the problem is. Computers try very hard to appear reliable, but it’s largely an illusion crafted through careful hardware and software design. The truth is, whenever you have two pieces of electronics talking to each other then messages can go astray. Luckily, there is a standard way to handle this problem: an ACK protocol. So, if the Leader sends a byte, and the Follower echoes something about that byte back to the Leader, then the Leader will know that the Follower has received it, and can proceed to the next byte.

The simplest thing you could send back would be the byte you received:

    def readReliably():
        r = 0
        r = recv()
        send(r)
        return r
    
    def sendReliably(byte):
        echo = 0
        while echo != byte:
            send(byte)
            echo = recv()

The Leader will keep sending the same byte until it sees it echoed back by the Follower.

So, this approach has two problems. The first is, what if we want to send the same byte twice in succession? How can the Follower tell the difference between a repeat “I haven’t received a response yet” send, and the next byte? How do we tell that both of them have been received? I (lazily) haven’t tried to address this, and I’m going to leave it as an exercise for the reader. I have, for the moment, just cheated my way around this and made sure I never try and send the same byte twice in a row.

The other problem is more subtle. Infrared light bounces, which is something that the design of the Edisons exploits to allow them to message each other around obstacles. When an Edison sees a pulse of IR light, it might be its own signal reflected back to it. We need the Follower to send a different byte back, but one that is recognisably derived from the byte it received. How?

Well, we can take a hint from Edison’s own IR protocol:

The Follower can echo back the inverted byte. We can XOR the received byte with 255, which will flip 1s to 0s and vice-versa:

    def readReliably():
        r = 0
        while r == 0:
            r = recv()
        echo = r ^ 255
        send(echo)
        return r
    
    def waitForEcho(byte):
        echo = 0
        while echo != byte:
            echo = recv() ^ 255
        
    def sendReliably(byte):
        echo = 0
        send(byte)
        waitForEcho(byte)

Now readReliably() blocks until it receives a value, and then sends an echo. sendReliably() sends its byte, then waitForEcho() blocks until it’s received the expected acknowledgment. This code also the answers the question I posed in the first part:

[…] why the terminal byte is defined as 254 and not, for instance, 255

255^255 is 0, which is the special value that Edison uses to mean “no IR data received”!

So, does this work?

The problem is now one of deadlock. All that has to happen is for the Leader to miss one acknowledgement, and it will sit there forever waiting for an answer that will never come. The Follower will never be sent another byte. Logically, we need to give the Leader more chances to catch the echo, which we can do by introducing some redundancy:

    def readReliably():
        r = 0
        while r == 0:
            r = recv()
        echo = r ^ 255
        send(echo)
        send(echo)
        send(echo)
        return r

We also need to allow for the possibility that the Follower never received the byte in the first place. We can do this by having the Leader only wait for the echo for short time, give up and retry sending the byte:

    def waitForEcho(byte):
        tries = 0
        echo = 0
        while echo != byte and tries < 3:
            echo = recv() ^ 255
            tries = tries + 1
        return echo
        
    def sendReliably(byte):
        echo = 0
        while echo != byte:
            send(byte)
            echo = waitForEcho(byte)

So, does this work? Yep, kind of:

This was a fun little quick project. The next idea I’m playing with is getting one of the robots to learn the way through a maze, and then teach the other the solution. This will probably force me to stop being lazy about handling repeated bytes! It will also be quite a bit tricker: measuring distance travelled will almost certainly not work, because it’s hard to do that precisely. The code will probably have to be based on identifying distinguishing features (like barcodes on the floor?)

Anyway, if you’d like to know more, or have any questions, please leave a comment below.