Workshop E4a (WS2008)

Lego Minstroms NXT Workshop

Responsible:   Prof. Dr. Thomas Engel
Tutors:            Raphael Frank & Thomas Scherer

Overview

In last two Mindstorms Workshops, the focus was set on the sensing capabilities of the robots. Using the Labview Development Kit for Lego Mindstorms, the students had to implement different algorithms in order to complete a track with a given number of obstacles (cf. former Workshops).
The Labview API was a good way to start developing programs for the Mindstorms Robots. Basic commands are easy to implement without needing any programming skills. However to implement more complex algorithms, Labview quickly becomes unhandy and difficult to use. Another drawback was the difficulty to use low level mathematical operations that are sometimes needed to implement capabilities beyond the simple sensing functions of the robot.
In order to be able to use such operations in a more convenient way, the API of Mindstorms need to be changed. RobotC developed by the Carnegie Mellon University offers a robust platform to perform more advanced operations using a "C like" programming language. Even for student who do not have programming skills, RobotC provides a complete step-by-step documentation.
In this workshop the focus will be set on secure communication between the robots. Cryptographic functions will be used to enforce secure routing. However the sensing functions used in the former Workshops are still needed and will be extended in order fulfill the new requirements.

Details

Organization:
The class will the divided in "3 or 4 Teams" depending how many students will participate. Each team is composed of "2 Groups" with "2 Students" . Each group is in charge of "1 NXT Robot" .

Description of Work: (Updated)
The first think that needs to be done is to get in touch with the RobotC programming environment. Confer to the reference section below to to find the needed information.
Note: It is recommended to have a look at those documents/links before the actual start of the Workshop in order to get a basic knowledge.
After having done some basic tests, the implementation of the different operations can start. The realization sequence of the different operations does not matter and can individually be chosen by the groups. However, be sure to cooperate with the other group of the same team to define common encryption/routing pattern etc.
The pictures below illustrate the different steps that should be realized. One team is assigned to one track. The track will have a similar setup as shown below and can change from team to team. This track can be subdivided in two different parts:

• Black lines on the floor combined with different crossroads
• Small Labyrinth with wooden walls

The first robot (R1) send on track starts by following the black line until it detects a crossroad. A direction is then chosen using a search algorithm. All crossroads and the taken directions need to be remembered by the robot to avoid to take a path twice.
Arrived at the entrance of the labyrinth, the robots continues straight ahead until it reaches a wall (use the touch or ultrasonic sensor). Again it needs to take a decision which way to take (only two possibilities: left or right) and memorize it!
Arrived at the GOAL, the fun really begins! After having defined a common "routing message" between both groups of the same team, the routing information which was memorized by R1 during the trip needs to be encrypted using the RC4 stream cipher and saved in a file (unfortunately, the bluetooth functions are not yet available in the 1.05 release of RobotC). This file needs to be transferred via USB to R2 which decrypts this message and evaluate the received routing information in order to complete the track without any errors!

Note: The track properties have changed! Refer to the requirements below for more details.









The operations that the robot need to perform can be summarized as follows: (Updated)

• Follow a black line on the floor
• Detect Crossovers & Memorize the way taken (a graph search algorithm can be used for that)
• Detect Walls and take an alternative direction (which need to be memorized as well)
• Detect Dead Ends an take an alternative direction
• Detect the GOAL
• Encrypt/Decrypt Routing Data using the RC4 stream cipher
• Save/Load encrypted data in/from a file.

Requirements: (Updated)

• The Track will be composed of three crossroads with four directions
• The Start- and Endpoint (GOAL) can be chosen dynamically
• There is only one possible way from the START to the GOAL!
• The two robots of a team should be able to do both parts, meaning that the groups can be interchanged (Optional)

Example of a possible track: (New)

Marking

The final marking will be composed of:

• A demonstration (date and time can be defined individually)
• Evaluation of the source code (encryption/decryption, communication, sensing functions, etc)
• Small Report containing the explanation/motivation of the different steps
• Written test held during the last session (to be discussed)

Timetable

WS	Tutor	Date	Time	Room	Topic	Documents
1	Raphael Frank - Thomas Scherer	03/10/2007	11:30-15:30	AS28-Labo	Introduction to RobotC	-
2	Raphael Frank - Thomas Scherer	17/10/2007	11:30-15:30	AS28-Labo	Work session	-
3	Raphael Frank - Thomas Scherer	31/10/2007	11:30-15:30	AS28-Labo	Work session	-
4	Raphael Frank - Thomas Scherer	14/11/2007	11:30-15:30	AS28-Labo	Work session	-
5	Raphael Frank - Thomas Scherer	28/11/2007	11:30-15:30	AS28-Labo	Work session	-
6	Raphael Frank - Thomas Scherer	12/12/2007	11:30-15:30	AS28-Labo	Work session	-
7	Raphael Frank - Thomas Scherer	09/01/2008	11:30-15:30	AS28-Labo	Demonstration & Written test	-

Tools

RC4 Test Vector Tool

References

Useful information can be found on the websites of the former Workshops:

Workshop E4a (WS2007)
Workshop E3a (SS2007)

Related References:

RobotC Homepage

• http://www.robotc.net/

RobotC Forum

• http://www.robotc.net/forums/index.php

RobotC Quickstart Guide

• http://www.robotc.net/lego/quickstart/index.htm

The C Library Reference Guide

• http://www.acm.uiuc.edu/webmonkeys/book/c_guide/

RC4 Stream Cipher (Wiki)

• http://en.wikipedia.org/wiki/RC4

Tree Search Algorithms (Wiki)

• http://en.wikipedia.org/wiki/Tree_search_algorithm

Bluetooth Transmission Protocol (Wiki)

• http://en.wikipedia.org/wiki/Bluetooth

"Workshop E4a (WS2008)" is mentioned on: Christophe Weis | Raphael Frank (Teaching) | Teaching | Telecom Workshop I (SS2008) | Thomas Scherer (Teaching)