Lesson Curriculum

From FIRE Wiki
Revision as of 21:09, 26 February 2012 by 108.2.142.238 (Talk)

Jump to: navigation, search

Multi-Robot Communication Lessons

The main goal of these lessons is to provide the students with the understanding of how to have multiple robots communicate with each other towards the accomplishment of joint sensing and actuation tasks. The study of how to concretely use multiple robots opens important avenues of scientific thinking and practice, as information from distributed sources needs to be shared, interpreted, and merged towards effective coordination. We create several simple lessons to incrementally introduce the underlying concepts for multi-robot communication. We assume that the students are equipped with robot platforms programmable in RobotC, real or virtual, with communication capabilities, implemented virtually or through hardware wireless devices, in particular the Xbee modules.

Lesson 1 - Basic multi-robot communication language primitives and timing

As with any other communication process, in order for multiple robots to communicate with each other, we need to introduce a robot communication language. Our basic language consists simply of a general string. We include in RobotC new instructions to send and receive a general string of limited number of characters.

Sending strings

The basic ROBOTC instruction to send a string is:

  • SendString(string toSend)
Sending a string repeatedly

When one robot sends a string to another, the message may not be received on the other end, due to bytes being dropped on the network. This can be likened to someone shouting to another person from a large distance away, and the receiver is unable to hear all the words that are said.

One way to circumvent this problem, is to send the string multiple times. This increases the probability of the message getting through - however, messages can still go missing, and we will cover this case in a later lesson.

To send a string multiple times, the following function can be used:

void SendStringRepeated(string toSend, int timesToSend) {
  for (int i = 0; i < timesToSend; i++) {
    SendString(toSend);
  }
}

There are a few points to note from the above code sample:

  • The SendString function is called multiple times, to increase the probability of the string being received. If robots tend to receive messages consistently, timesToSend can be decreased. Conversely, if messages are not being received, the timesToSend can be increased.

Receiving a string

In order for robots to communicate, some robots send messages and other robots receive messages. The basic ROBOTC instruction to receive a string is:

  • int ReceiveString(string & received)

If a string is received, then the function ReceiveString will return a value greater than 0. The number returned corresponds to the length of the string received.

Waiting for a string

In multi-robot communication, it is common for one robot to wait for a string to be received from another. To do so, the following function can be used:

void waitForString(string toWait) {
  bool done = false;
  string received = "";

  while (!done) {
    // Check if any string is received
    int retVal = ReceiveString(received);

    // We did receive a string
    if (retVal > 0) {
      // Is this the string we are waiting for?
      if (strcmp(received, toWait) == 0) {
        done = true;
      }
    }
  }
}

The function above loops until the desired string is received: while (!done). Recall that the SendString function only increases the probability that strings are sent and received - it does not guarantee it. We will cover guaranteed message delivery in a later lesson.

The next line retrieves the string (if any) from the message buffer, and then checks that the received string matches: if (strcmp(received, toWait) == 0). If it matches, then done = true and the loop ends.

Exercises

  1. Send a message "Hello, I am ready!" from Robot 1 to Robot 2. Have Robot 2 print the message that it receives from Robot 1 on its screen.
  2. Send some message M from Robot 1 to Robot 2, and have Robot 2 display on its screen: "Robot 1 tells me M".
  3. Send a message M1 from Robot 1 to Robot 2, and have Robot 2 send back a message M2 to Robot 1, after it receives M1 from Robot 1.

Lesson 2 - Targeted multi-robot communication

The function SendString broadcasts information, i.e., any robot with an XBee receiver that is waiting for a message will receive a message sent by another robot, using ReceiveString. In order to achieve communication to a specific robot only, we assume that the robots have identifiers (id(s)) and extend the multi-robot communication primitives to process such identifiers. We introduce 2 primitives:

  • SendStringTo(string id, string toSend)
    • which creates a specialized message meant for the robot with the correct id.
  • int ReceiveForMe(string myID, string & received)
    • which matches the id on received messages with myID, and does not receive a string unless id and myID match.

Exercises

For these exercises, you will need 3 robots: Robot 1, Robot 2, and Robot 3.

  1. Have Robot 1 send the message "Hello, Robot 2" to Robot 2 and "Hello, Robot 3" to Robot 3. Have both Robot 2 and Robot 3 display the received messages. Robot 2 should not display the message sent to Robot 3, and vice versa.
  2. Have Robot 1 send the same message to both robot by using the primitives introduced in Lesson 1.

Lesson 3 - Sending strings consistently

From the exercises in lessons 1 and 2, you may have noticed that not all messages are received. This is due to noise in the environment that affects the radio transmission between the robots. Thus, in some situations, there is a need to send consistent messages, i.e., messages that you are sure will be received on the other robot. To do so, we introduce 2 new primitives:

  • SendStringConsistently(string toSend)
  • SendStringConsistentlyTo(string id, string toSend)

These functions are very similar to SendString and SendStringTo which we have described in the previous lessons. The question that comes to mind then is: why would you use SendString when you can use SendStringConsistently?

To answer that question, it is useful to know how consistent messages are being sent. Suppose Robot 1 calls SendStringConsistentlyTo("robot2", "hello") Robot 2. What is actually happening is that Robot 1 tries to send "hello" to Robot 2, and when Robot 2 receives the message, Robot 2 replies "I got the message". If Robot 1 doesn't hear that from Robot 2, it sends "hello" again and again until it is successful.

Thus, SendStringConsistently can take a long time to run, compared to SendString. Imagine if Robot 1 is sending a consistent message to Robot 2, but Robot 2 is switched off. In this case, Robot 1 will never stop sending it!

Exercises

  1. Have Robot 1 send the message "Hello" to Robot 2, waiting for 1 second, and then sending the message "How are you" to Robot 2. Have Robot 2 display the received messages from Robot 1.
    • First, use the SendString function and record how long it takes for Robot 2 to receive both messages.
    • Next, use the SendStringConsistently function and record the time.
    • Which function allows Robot 2 to receive the messages more quickly?
    • Does Robot 2 receive both messages regardless of the function used?
  2. Brainstorm about situations when you would need to use SendStringConsistently instead of SendString, and situtations when SendString is sufficient.

Lesson 4 - Mapping strings to actions

So far, we have been sending strings from one robot to another and having the strings printed out on the screens. However, besides being a list of characters, the strings can also mean something. For example, in our normal language, when we say "look there", we are actually communicating an action. In this case, we want someone to physically turn and look at something in particular.

In multi-robot communication, strings can also be used to represent actions. For example, when Robot 1 sends a message "turn" to Robot 2, the word "turn" means that Robot 2 should physically turn.

Exercises

  1. Create a library of 5 robot actions, such as moving forward a certain amount, turning a certain amount, etc.
  2. Associate each action with a unique word, e.g., "turnLeft90" means turning 90 degrees to the left.
  3. Program Robot 1 to send one of the 5 strings that you chose.
  4. Program Robot 2 to receive messages and print the action when it receives a string. For example, when Robot 2 receives "turnLeft90", it prints "Turn 90 degrees to the left".
  5. Now, update Robot 2, so that it executes the action when it receives the string. For example, when Robot 2 receives "turnLeft90", it physically turns 90 degrees to the left.
  6. Discuss whether SendString or SendStringConsistently is more suitable for the exercises in this lesson.

Lesson 5 - Parameterized strings to actions

In Lesson 4, we associated each action with a unique string. For example, "turnLeft90" meant turning 90 degrees to the left, and "straight100" meant moving forward 100cm. However, such a language has certain limitations. For example, if we wanted the robot to be able to turn 45 degrees to the left, we would need to add an additional string, "turnLeft45", into the language. While this may not sound too difficult, it involves programming both the sender and receiver robots. In addition, suppose now we want to turn 30 degrees, we would have to repeat the process to add another string.

So, to make the language easier, both in terms of understanding and programming, we will now introduce parameterized strings. Instead of having unique strings "turnLeft90" and "turnLeft45" etc, we have a string "turnLeftX", where X is a parameter. This is very similar to algebra, where symbols can have different values.

Sending/receiving parameterized strings on the robots

In terms of programming the robots, the sender has a relatively easier job: you can append the number to the end of the string! For example, if you wanted to turn 30 degrees, you can first create the string "turnLeft", and then add the string "30" to the end of it. To do so, you can use the function StringFormat, which helps to format strings:

int amountToTurn = 30;
string toSend;
StringFormat(toSend, "turnLeft%d", amountToTurn);

On the receiving end, you will need to parse the string to make sense of it. First, since you have a library of parameterized actions (such as "turnLeftX", "straightX" etc), you need to check the front of the string. You can do so by doing the following:

string received; // Suppose this was set by ReceiveString
bool isTurnLeft = (StringFind(received, "turnLeft") == 0);
bool isStraight = (StringFind(received, "straight") == 0);

Once you know the type of the message, e.g., turning left or going straight, you need to figure out what the parameter is. The sscanf function can then be used:

int amountToTurn;
sscanf(received, "turnLeft%d", amountToTurn);

Another approach is to convert part of the string into a number. Since we know that the string starts with "turnLeft" for example, we can ignore that part of the string, and convert the rest of it into a number using atoi:

int amountToTurn;
StringDelete(received, 0, 7); // Delete characters 0 to 7 from received, since "turnLeft" is 8 characters long
amountToTurn = atoi(received);

Exercises

  1. Update your library of actions and strings so that they are now parameterized, e.g., "turnLeftX" means to turn left X degrees.
  2. Update the code of Robot 1 and 2 from the previous lesson to send and receive parameterized strings.
  3. Come up with an action that would require 2 parameters, and update Robot 1 and 2 to use that action and parameterized string.

Lesson 6 - Sequence of strings

So far, we have been sending strings from one robot to another. In lessons 4 and 5, every string referred to some action to be performed on the robot. In this lesson, we will learn about sending sequence of strings.

Suppose we had the turnLeft and straight commands from the previous lesson. Now, we want to send a message to tell a robot to move straight 100cm and then turn left 90 degrees.

One way we could do this is to first send the straight100 command, wait for the robot to finish executing the action, and then send the turnLeft90 command. However, this has an inherent coordination issue: firstly, the sender has to know when the receiver finishes executing the action. To overcome this, the receiver could send a "I'm done" message back, but this adds a layer of complexity to the algorithms of both robots.

An alternative would be to create a new command straight100AndTurnLeft90, that commands the robot to do the 2 actions in sequence. This does achieve the goal, but suppose we wanted to then perform a right turn followed by a left. There would be many combinations of actions to be programmed in the robot, which makes it both more difficult to code and debug, and also the expand on in the future.

Instead, we can explore sending a sequence of strings. Conceptually, this means that the sender says to the receiver:

  1. This is the start of a sequence of actions
  2. straight100
  3. turnLeft90
  4. This is the end of the sequence

On the receiver robot, when it hears the first line, it enters a "record mode" where it stores the strings it receives next, until the message "This is the end of the sequence" is received, upon which the receiver executes the sequence of actions.

To implement it on the robots, we will need to define 2 new language terms, a "start sequence" and an "end sequence". The start and end messages correspond to the "Record" and "That's it" lines in the conceptual example above. Thus, the language between the robots now consist of 3 types:

  • Start sequence
  • End sequence
  • Actions

where there are many different actions such as going straight and turning.

Exercises

  1. Define the "start sequence" and "end sequence" messages in the robot language. Create a list of the messages the robots can send to one another, and group them into the 3 types described above.
  2. Have Robot 1 send a sequence of strings: e.g., "start sequence", go straight 100cm, turn left 90 degrees, "end sequence".
  3. Have Robot 2 receive the sequence and save the actions in between "start sequence" and "end sequence". When "end sequence" is received, Robot 2 should execute the actions one after another.

Lesson 7 - Creating a library of macro actions

In lesson 6, we sent sequences of actions for robots to perform. A sequence of actions is also called a "macro action", since it is a single non-stop action on the robot, that can be broken down into smaller actions. For example, "go straight and then turn right" is a single action in the sense that the robot moves forward and then turns right away, but at the same time, the whole movement can be broken into the 2 steps of moving forward, and turning.

Suppose we want to tell a robot to move straight and then turn left. From lesson 6, we can send a sequence to do just that. What if we want to do it again? We could just send a new sequence and have the receiver perform it. However, if we have a long sequence of actions, then sending everything again could take a long time. Put another way, if we had some simple actions like straight and turn, but we frequently want the robots to move straight and then turn, we would have to always send a sequence of actions each time.

There is actually a better way of doing things. Besides sending a sequence of strings, and having the receiver execute the actions right away, we can improve the language to save macro actions. So, instead of a generic "start sequence" and "end sequence", we now have:

  1. Start sequence "Straight100AndTurnLeft90"
  2. straight100
  3. turnLeft90
  4. End sequence

This looks very similar to the example in lesson 6, but with an important distinction: the "start sequence" message now includes a parameter, the name of the macro action ("Straight100AndTurnLeft90" in the example above).

On the receiver robot, when it receives this sequence of strings, it saves the list of actions (e.g., straight100 and turnLeft90) into a new macro action "Straight100AndTurnLeft90", and it does not immediately execute the actions.

Now, the sender robot can define new macro actions, but in order for the receiver to execute them, we need an additional type of message in our robot language - an "execute macro action" command. Such a message would be similar to the action messages we developed in lessons 4 and 5, except that the parameter is now the name of the macro action.

For example "executeStraight100AndTurnLeft90" would be a message to tell the receiver robot to execute the macro action called "Straight100AndTurnLeft90".

Exercises

  1. Update the robot language to have a parameterized "start sequence", and an "execute macro action" message.
  2. Have Robot 1 send a macro action to Robot 2, without sending the "execute macro action" message.
  3. Have Robot 2 receive the macro actions, and print that it saved a new macro action.
  4. Now have Robot 1 send the "execute macro action" message, and have Robot 2 execute it.
  5. Have Robot 1 send a different macro action (with a different name) to Robot 2, and then tell Robot 2 to execute the first macro action. Robot 2 should be able to differentiate between the 2 macro actions.
  6. Now have Robot 1 send a message to execute the second macro action.

Lesson 8 - Parameterized macro actions

Similar to what we did in lesson 5, we are now going to add parameters to macro actions. In lesson 7, we described how to create a macro action that consists of a sequence of smaller actions. For example, "Straight100AndTurn90" meant go straight 100cm, and then turn left 90 degrees.

However, it becomes unwieldy to create new macro actions for each combination of distances and angles. For example, if we wanted the robot to go straight 50cm and then turn left 45 degrees, we would have to create a new macro action. Or would we? We can define a parameterized macro action, which takes parameters of the actions it is composed of.

For example, we can create a macro action "StraightAndTurnLeftX,Y", where X is the distance to move straight, and Y is the angle to turn left. So, "StraightAndTurnLeft50,45" would mean go straight 50cm and then turn left 45 degrees.

Sending/receiving parameterized macro actions

The method to send and receive parameterized macro actions is very similar to parameterized strings in lesson 5, with a caveat - it is likely that there are many parameters, so care has to be taken to send and retrieve each parameter. In order to do so, we can use a comma "," to split each parameter.

Thus, to send a macro action to move straight a certain amount, and then turn left a certain amount, we can do the following:

int amountToMoveForward = 50;
int amountToTurn = 45;
string macroAction;
StringFormat(macroAction, "StraightAndTurnLeft%d,%d", amountToMoveForward, amountToTurn);
string toSend;
StringFormat(toSend, "execute%s", macroAction);

The first StringFormat command sets up the parameterized macro action with its 2 parameters. However, the message that needs to be sent is the "execute" command, with the macro action as its parameter, and so the second StringFormat function does that.

To receive a parameterized macro action, we need to retrieve each parameter separately. Firstly, we will need to retrieve the macro action (e.g., "StraightAndTurnLeft50,45"), and then get the parameters from it:

string received; // Suppose this was set by ReceiveString
bool isExecute = (StringFind(received, "execute") == 0);
if (isExecute) {
  string macroAction = received;
  StringDelete(macroAction, 0, 7); // Delete characters 0 to 6 from macroAction, since "execute" is 7 characters long

  bool isStraightAndTurnLeft = (StringFind(macroAction, "StraightAndTurnLeft") == 0);
  if (isStraightAndTurnLeft) {
    int amountToMoveForward;
    int amountToTurn;
    // Remove the name of the macro action
    string parameters = macroAction;
    // Delete characters 0 to 18 from macroAction, since "StraightAndTurnLeft" is 19 characters long
    parameters = StringDelete(parameters, 0, 18);
    sscanf(parameters, "%d,%d", amountToMoveForward, amountToTurn);
    // Execute the command here
  }
}

In our code samples above, we hard-coded the macro action name "StraightAndTurnLeft". From lesson 7, there should be a library of macro actions, so it is necessary to have code that is general to any macro action name.

Exercises

  1. Update the macro actions of the previous lesson so that they are now parameterized, e.g., "StraightAndTurnLeftX,Y" instead of "Straight100AndTurnLeft90".
  2. Update the sender and receiver code to send and receive parameterized macro actions.
  3. Have Robot 1 send a message to execute a macro action with one set of parameters (e.g., "executeStraightAndTurnLeft50,45") and have Robot 2 execute it.
  4. Now have Robot 1 send the same execute macro action, with a different set of parameters (e.g., "executeStraightAndTurnLeft90,70") and ensure that Robot 2 executes the macro action with the new parameters.
  5. Have Robot 1 send a message to execute a different macro action with another set of parameters.

Lesson 9 - String Array

To simplify the process of sending, receiving, and parsing multiple parameterized strings, we will introduce the Array.

Introduction to Arrays

An array is an indexed collection of variables of the same datatype. Indexed means that each variable or element of the array can be accessed using an integer index.

The syntax for declaring an array of variables is:

datatype  variable name [SIZE];

For complex tasks it becomes cumbersome to continually create parameterized macro actions. Similarly, it complicates the the job of the robot on the receiving end to parse the macro action down into what it actually wants.

For this lesson we will be using string arrays. The use of arrays allow us to us to send messages just as we did in Lesson 5. The only difference is how we receive and deal with strings once we have them.

Note: Array indices always start at zero and end with an index one less than the declared size of the array.

Defining Start and Stop Commands

As we mentioned in Lesson 6 - Sequence of strings, it is usually necessary for the receiving robot to execute commands in the order in which they were sent and wait until the sender has finished sending all the messages before it begins to execute them. An easy way to do this is with a For-loop which are syntactically designed to be used with arrays.

Here’s an example of how they work:

task main ()
{
 int i ;
 int cube_Operation [5];
 
 for ( i =0; i <=4; i ++) //cube every number from 0 to 4
 {
  cubeOperation [ i ] = i * i * i ;
  nxtDisplayCenteredTextLine(3,"%d", cubeOperation [ i ]); //display on NXT screen
 }
}

Below is an example of “recording messages”. Robot 2 is receiving and storing six strings sent to it by Robot 1 but not immediately executing them.

 string messageReceived;
 string message[6];
 
 int i ;
 for(i=0; i<=5; i++)
 {
   ReceiveString(messageReceived);
   message[i] = messageReceived;
 }

An array in combination with a for loop is a powerful and efficient way to store messages until they are needed.

Exercises

  1. Implement For-loops for executing commands sent by Robot 1 to Robot 2
  2. Update string array with start and stop commands
  3. Have Robot 2 store commands until Robot 1 sends Robot 2 a start command
  4. Have Robot 2 execute the commands in the order they were sent using a For-loop