Aim

The aim of the project was building and programming two robots, which can seek and find each other. They were to communicate with each other through some medium (that happened to be infra-red, but is subject to be extended to bluetooth or wireless). To build the robots we were supplied with the following, which will be explained in detail:

• two LEGO MINDSTORMS RIS kits
• two HP JORNADA PDAs

Basic Structure

LEGO MINDSTORMS kits were the base of our robots and JORNADA PDAs were located on top of them. The MINDSTORMS was the 'slave', and we were to control it through the PDA.

LEGO MINDSTORMS General Information

The LEGO MINDSTORMS Robotics Invention System (RIS) is a kit for building robots. It consists of a programmable brick (with a Hitachi H8/3292 microprocessor) named the RCX, and a lot of other traditional LEGO building parts named TECHNICS.

The RCX has 3 input ports, 3 output ports, and an infrared transmitter/receiver. You can connect the inputs to sensors so that the RCX is aware of what is happening outside. There are many kinds of sensors that LEGO offers but only two kinds come with the RIS package. You must purchase the other ones separately if you want to use them. The sensors that come with the package are two bumpers (touch sensors), and a light sensor. The 3 outputs can be connected to motors, so that your robot can move.

The TECHNICS part is used for building the rest the robot, and connecting the RCX to sensors, motors, wheels, etc.. There are design suggestions for your robot in the manual coming with the package, but you are actually restricted by your creativity only. There are also many more design suggestions on the web.

The RCX can be programmed. Together with the RIS package comes a CD with an official SDK to program the RCX. It presents a visual environment, in which you drag and drop visual LEGO parts in order to form a flowchart. But that seems to be designed for children, so, an experienced programmer will not feel very comfortable with this kind of programming. And fortunately you have lots of other alternatives. From Scheme to Java, there are compilers (and corresponding firmware) for all of the popular PLs (These compilers are not offered or supported by LEGO; they are written by ‘mindstorm-lovers’ from all over the world, about whom we will be talking about). Either you use the official SDK or other ones, you must download your program to the RCX. That is done via the infra-red (IR) tower. You use the serial port (RS232) to connect the IR tower to your desktop computer (This was the case for us, but newer RIS kits have IR towers with USB connection). To download the program you have to place the tower against the RCX’s IR receiver-transmitter.

As we said, LEGO MINDSTORMS comes with an official SDK which you can use to develop software, and an official firmware which you must download to the RCX before downloading any programs to it. If you remove the batteries of the RCX, the firmware together with the programs will be lost. So you must download the firmware again before any programs. This is the same with other unofficial firmware. You must first download the firmware then the programs. And if you remove the batteries they are lost. The firmware is also downloaded via the IR tower. Every SDK has its own way of downloading its firmware, so you should look at the documents of the firmware-SDK couple you plan to use.

After the release of the LEGO MINDSTORMS, children were not the only ones who were happy. Robotics fans from all over the world started playing with it, and were not satisfied with what the official SDK offered. After Kekoa Proudfoot reverse engineered the RCX, the way was opened for the others. Now the internet is filled with pages about MINDSTORMS, some of which we will name here:

HP JORNADA 548 PDA General Information

HP JORNADA 548 PDA is a lightweight PDA that we used as the ‘brain’ of our robots. Windows CE (a version of Windows designed to run on PDAs) is the operating system of JORNADA. It has an Hitachi SH3 processor and 32MB RAM. For I/O it has an infrared port (which uses irDA as default), an RS232 serial port, and a CompactFlash Type1 card slot. JORNADA has a cradle which you use for both charging the battery and downloading data. The cradle has a USB connection to your desktop PC.

For software development you can use Embedded Visual C++, Embedded Visual Basic, or some other SDK like SuperWaba (for Java programmers). We used Embedded Visual C++.

You can get more information from the official site of HP JORNADA

Design Ideas

To achieve the goal of building robots capable of finding each other and communicating, we considered and analyzed several designs. There were some considerations; with LEGO MINDSTORMS being the hardware part of the robot, the PDA should be able send messages to the hardware below it.
At the same time it should be able to communicate with the other robot.

Our first design idea was to use a mirror to select the destination of message sent from the PDA. The mirror would be movable via a motor, controlled by serial port of PDA. It would have two states, up and down, which will decide on whether the IR signal would go to RCX, or to the other robot. If the mirror was up, the IR signal from the PDA would reflect from the mirror to reach RCX IR port. In this case, IR was to be used for the communication of the upper(PDA) part of a robot with the lower(MINDSTORM) part of it. If the mirror was down, IR signal would go unhindered and reach the other robot's IR port on PDA, if there was another robot nearby. In this case, IR was to be used for the communication of two robots.

With this design we could use the IR port for inter-robot communication and also for giving commands to robot's hardware. But it had these drawbacks:

• Moving a mirror would require extensive hardware, a complex mechanism in addition to the motor.
• There would be some delay between giving a command to hardware and sending messages to another robot, caused by mirror moving mechanism.
• A motor would require power to operate, which will be provided by MINDSTORM's batteries, or externally mounted batteries. First alternative would shorten the operating time of the robot with a given set of batteries. And the second alternative would introduce bulk mass to the robot.

Our second design was to use inputs of RCX to send commands to it. Commands would be sent from serial port of PDA to the input of RCX using bit sequences. This would not introduce bulk as the first design, and there wouldn't be delay between commands to hardware and messages to other robots. But drawbacks of this design were;

• Identifying different bit sequences was hard to implement.
• It would require crafting of a special cable to connect serial port of PDA to the input of RCX. It would not only require soldering, but modifying a LEGO brick to hold conducting cables.

But we preferred to implement our third design. We mounted the IR tower bundled with the MINDSTORM on to the back of the robot. IR tower was facing directly the IR port of the RCX. Commands sent by the PDA are transmitted through the path;
Serial port » IR tower » RCX

We chose this design because:

• It provided a means for assuring the destination of signals.
• It did not require complex hardware modification
• It was easy to implement as software

Implementation

Mindstorm Implementation

Building the Robot

We built the mechanical part of the robots using the design suggestions in the MINDSTORM manual. But upon it we had to place the JORNADA PDA. So we added some extra parts that enable us to place JORNADA on the MINDSTORM. Also we added some parts to carry the IR tower. For more informaiton see the Details of Building Process.

Mindstorm software

As we said earlier LEGO MINDSTORM comes with an official SDK but there are many other ones you can choose. We chose LeJOS, which is a java based replacement firmware and provides a good API for programming in Java.
Here are some useful links.

• LeJOS web site
• LeJOS API
• LeJOS tutorial

1. After you have downloaded the leJOS environment zip file, unzip it to an arbitrary directory - if you haven't a zip utility, you might try for example 7-Zip, which is available for free.
2. Add the SDK's bin directory to your PATH environment variable.
3. Set the LEJOS_HOME evironment variable to the directory you installed lejos into:
   set LEJOS_HOME=< your lejos directory >
4. Add leJOS's bin directory to your PATH environment variable:
   set PATH=%PATH%;%LEJOS_HOME%\bin
5. Add the leJOS classes to your CLASSPATH environment variable:
   set CLASSPATH=%CLASSPATH%;.;%LEJOS_HOME%/lib/classes.jar;%LEJOS_HOME%/lib/pcrcxcomm.jar
6. Set the RCXTTY environment variable to your 'tower' device:
   set RCXTTY=COM1 or set RCXTTY=USB "

Now you have to replace the firmware on RCX. We will start using the IR tower. Connect it to your desktop PC(via the serial port). Then, again quoting from the LeJOS web site: "

1. Place the IR sensor of the RCX in front of the IR Tower
2. Turn on the RCX
3. Open a command shell and change to the bin directory of your leJOS installation
4. call firmdl.bat
5. the progress of the download is displayed in the command shell and on the display of the RCX; the RCX will double beep when the download is complete and display the battery voltage. "

Now your RCX is ready to download programs on it. For instance, if you have a file named HelloWorld.java, you must first compile it by calling:
lejosjc.bat HelloWorld.java
Then link and download the program calling:
lejoslink.bat HelloWorld

Now you can run your program pressing the “RUN” button on the RCX.
If you have problems with downloading your program have a look at the LeJOS web site for possible reasons.

Mindstorm Code

LEGO MINDSTORMS can be programmed to do many things. Several robotics experimentations can be done only using mindstorms and nothing else. But we didn’t use the mindstorms as the ‘brain’ of our robot (There are reasons why we didn’t: our main purpose set by our professor was to find ways of controlling the mindstorm from the JORNADA PDA; and our future plans on using Bluetooth as a medium of communication between robots required using Jornada which has a CF slot). Rather we used mindstorm and programmed it in a way that it was a slave for JORNADA: listening to it and obeying the commands.

The code consists of a loop which listens for packets sent from JORNADA via the IR tower. (The sent packets must have the structure required by the RCX but JORNADA side of the code deals with it, so we will talk about the packet structure in the section where we explain JORNADA code). If it detects a packet it inspects inside it, to find out what action was requested. There are 7 kinds of actions that can be requested. These are:

• Stop
• Go Forward
• Go backward
• Turn right
• Turn left
• Align
• Play sound (Actually there are 3 kinds of sound that are played)

These should be obvious other than ‘Align’. By ‘aligning’ we mean the robots coming face to face before starting to dance. Although the main connection between robots is established by the IR ports of the PDAs, IR does not give us the information whether the robots are face to face or have a 50 degrees (sometimes even 90 degrees) misalignment. They can communicate via IR, but that doesn’t mean they are face to face. What we did was sending an ‘align’ command to the RCX so that it will go forward, bump the other robot with its bumpers, and turn to the side of the pressed bumper. This is repeated five times, the degree of turning to the bumped side decreasing every time. In the experiments we did, this alignment strategy gave pretty good results, so we kept with it (We actually tried other alignment strategies trying to use only IR, or both IR and the bumpers, but they gave out poorer results).

There is only one thing that the RCX does on its own. That is obstacle avoidance. If any of the bumpers is pressed at any time (other than when we are in ‘align’ state), without informing JORNADA, RCX goes backwards for a predetermined time. That is all it does. Then it resumes executing the commands sent from JORNADA.

Adapter Cable

In our design we had to connect serial port of PDA to the serial port on IR Tower. But the serial port of the tower is not easy to reach, it is buried deep into the tower, and the serial cable that comes with HP JORNADA has a very large connector. It was impossible to plug in the connector to the tower without modification.
We did not want to modify the bundled serial cable, so we looked for some other ways. The serial cable of LEGO MINDSTORMS was properly fitting into the tower, but its other end was not fitting to the PDA, because HP JORNADA used a special thin connector for serial port. We had to use some adapters but there were no ready-made adapters for this purpose. After searching for a ready solution and not being able to find it, we decided to craft the adapters we needed.

First we bought two serial jacks, and soldered a null-modem cable, crossing some connections to retain data transfer capability. We connected the JORNADA serial cable to PDA, connected its other end to the adapter cable we made, and connected one end of LEGO serial cable to IR Tower and the other end to the adapter cable. The output connector of JORNADA serial cable was proper for operating the tower, but LEGO serial cable was a cross cable, so it ruined the data transfer. That was the reason that we chose to make our adapter cable a cross cable. Inverting a signal twice did not change its operation. This design worked, but it was bulky, because we had 3 cables, one long LEGO cable, one long JORNADA cable and one short adapter cable.

Then we decided to simplify things by eliminating a cable, instead of plugging the LEGO serial cable, we cut cables from old serial mouse, which could be plugged into IR tower easily. Then soldered a serial jack to cable's other end. Then we connected JORNADA serial cable to this new adapter cable. As the JORNADA serial cable's outputs were properly operating the tower, the adapter cable we crafted did not need crossing of cables. This design was essentially the same as the first designed but it used one long cable less than the first design.

Jornada Serial cable	Normal serial adapter cable (using mouse cable)	Jornada cable + normal adapter cable
Null-modem(cross) adapter cable	Lego cable + null-modem adapter cable + Jornada cable

JORNADA Implementation

Com Ports

For reading and writing from com ports, WinAPI could be used. But we found the SerialPort wrapper class -written by Shibu K.V- especially handy to communicate with com ports, so we used it for communication.

As mentioned, we used two serial ports in our implementation. These are com1 and com4 ports, which are detailed below.

Serial Port

The serial port that is used to transmit commands to the RCX is the Com1 port. After opening the port, a command can be sent by writing each byte to the serial port. A command sent to the IR tower is transferred to the RCX, and these commands must follow a certain format.

As discovered by the reverse engineers of RCX, each command packet must begin with the byte sequence "0x55 0xff 0x00" This is some kind of header, meaning that a command is to follow, also, it is chosen such that it has equal number of zeros and ones. This is to prevent the infrared transmitters/receivers of IR Tower and RCX from becoming biased.

After the header, actual code for the command is sent. RCX has a standard set of commands, but we defined our own protocol between RCX and the PDA. It is an arbitrary mapping of single bytes to commands. After the command, bitwise inverse of the command is sent. The reason for this is as explained above, to prevent transmitters of IR Tower from becoming biased towards a voltage level.

If the command has a parameter, it is sent after the command, followed by its inverse.

As the last part of the command packet, the sum of transmitted bytes - command plus parameters - is added to packet, followed by its inverse. In our implementation there was no need for parameters, so we repeated the command itself in place of the sum.
As an example, to send 0x10 to the RCX (which meant ‘Go Forward’ in our protocol), all we did was writing the following byte sequences to com1:
0x55 0xff 0x00 0x10 0xef 0x10 0xef

Infrared Port

The infrared interface is a serial one, and its implementation on WINDOWS CE is just like another serial port, namely Com4 on the PDA models we have. Writing data to Com4 port results the data being sent via infrared.

There is a widely accepted standard for infrared, named IrDA in use, but this required one PDA to be a server and the other to be client. This is opposing the swarm robotics idea of every robot in the swarm being similar. We would have to decide which robot was going to be server. This may not have caused a problem for only two robots, but for larger number of robots, it would be the case that all the swarm would rely on the server and when it failed all the swarm would be useless. It would also be impossible for two clients to communicate. Thus, as with the serial port, we defined our own protocol for the infrared port. Bearing in mind the biasing of IR transmitters/receivers, we made the protocol use even number of zeros and ones.

Most important job we did using infrared was 'pinging' , sending packets to the environment, then 'listening' for pings of other robots, to see if any robot was in the range of its IR reciever. A robot would respond to ping by sending a signal that means it sensed the ping, and the pinging robot would send the acknowledgement signal to state that initial communication is established between robots.

Then robots roll for random numbers and tell each other their numbers. This determines the directions of the robots' dance, like which one will go back, which one will turn right etc.

Pictures

The PDA lies on top of the robots and its screen faces up. We displayed comic face bitmaps on the screen to impersonate the robots.

At the start of the program, we loaded all of the bitmaps into memory to speed up picture switching. Then according to the behavior chart, a picture was selected to be shown. We used WindowsCE API to display the bitmap

Behaviour of the Robots

Behavior of the robots can be seen in the chart.

Start State

The robots await in this state. Clicking the button on the JORNADA screen triggers the transition to ‘Search Forward’ state.

Search-Forward State

The robots advance forward, pinging and listening to the environment. If the robot receives a ping signal, it goes into ‘Establish Communication’ state. If the robot cannot receive any signal while pinging and listening, it goes into ‘Search Around’ state after 20 tries. We set the reading timeout for the infrared port to 200ms. So if the robot doesn’t read anything for these 20 cycles, it takes approximately 4 seconds to advance forwards and go to the ‘Search Around’ state.

Search-Around State

The robots stop and turn to a random side for duration of 5 to 8 seconds. This corresponds to 300-400 degrees of turning. This duration is also determined randomly. That is because, when an obstacle is directly ahead, turning 360 degrees runs the robot into the same obstacle. The robot may have turned 360 degrees according to battery level, if we used a constant time turn.

During turning, robots continue to ping and listen to the environment. If an IR signal other than ping is detected, the robot records the signal’s position as the start angle, and continues turning until it loses the signal, then records this as the ending angle. Then it stops, and turns its heading towards the middle of start and ending angles. If it gets a clear ping signal, robots make a transition to ‘Establish Communication’ state instantly. Otherwise it goes into ‘Search Forward’ state.

Establish Communication State

In this state robots assume they can communicate and send acknowledge signals. If they get the other’s ack signal, then they are ready for further communication and go to ‘Align’ state. If they cannot get the ack signal, they go to the ‘Search Around’ state.

Align State

In this mode, robots try to align themselves face-to-face by bumping into each other and considering the signal from bumpers. For example, if there is a signal in left bumper, the other robot must be at that side, so the robot turns a little to the left. This is done 5 times, and each time the turning angle is decreased. After this, robots become positioned face-to-face. Then the robots go into ‘Concurring’ state.

Concurring State

In this state, robots produce random numbers, and exchange their numbers. Then they check whose number is bigger. This information will be used in determining the directions of movements in the dance, but it is trivial to add other data to be transmitted if robots' purpose was different. Then robots go to ‘Dancing’ state.

Dancing State

Robots dance cheerfully and in a synchronized manner. They move and turn, if one is going backwards, the other is going forwards so they move together into one direction. Turning is the same, one turns left and one turns right, so their IR interfaces are in the range of each other during the dance. Additional data may be transmitted if necessary. In rare cases where robots roll the same number, they do not reroll but mimic each other.

End State

After the dance is finished, robots bump into each other, move backwards for state.

Obstacle Avoidance State

If a robot hits an obstacle, it simply moves backwards for 750 milliseconds. An obstacle may be a wall, or it may be another robot. Robots cannot identify other robots if they are not face to face, because they have IR interfaces only in the front. After this state, robot directly goes to ‘Search Around’ state.

Metu Fair

At METU there is an annual fair held in every July. All the departments of the university show up in this fair and give information about their departments to the prospective students.

At this year's fair we were in our department's stand with our robots. All day long, our robots performed their show. In a 1x1m arena, they tried to find each other and dance. After their dance is completed, they were taken apart and they started all over.

This activity attracted many people's attention. Students who came to see metu departments were impressed by our show. They asked questions about our study, and we were pleased to answer these questions. We hope that they will choose Computer Engineering as their major. :-)

Our robots attracted the press' attention as well. We gave an interview to a local television channel. And a news story was printed on two national newspapers, alas , they erred at our department! Some photos and a video shot at the fair can be found at Onur Tolga Sehitoglu's web page

The great appreciation from people motivated us a lot, and now we look forward to studying more in the robotics area.

METU Fair	From the newspaper

More information

• Details of the mechanical building of the robot are available here with close-up pictures at every step.
• Final report of the project (in English) is available as pdf and ps.