100(1+1) - Lauren Kondratiev, Danijela Topić Vizcaya

The Task and the Robot

The goal of this project was to make the 100(1+1) robot learn a topological map. The robot was following the line on the map and learning locations across the map. After learning a location it would first choose the left crossing and after reaching the same location again, it would have to explore the next possibility. We communicated with the 100(1+1) robot via Bluetooth through the PuTTY program. The Robot has 8 sensors, which are numbered from 0 to 7 and it was using the sensors 2 and 5 that are surrounding the line in order to navigate the line and the sensors 0 and 7 to for detecting the crossings. After it detects a crossing, 100(1+1) would stop and ask for the location through the interaction with the user and based on the answer in the BT terminal and the learned map, it would act accordingly.

Topological Map

The topological map consists of black tape lines which enable the robot to follow them. It is represented as a mathematical multi-graph with bidirectional edges, allowing multiple edges between vertex pairs. The map consisted of 7 locations with threefold crossings and one starting point (see image below). The program would create an array with the locations (labels) and the possible destinations (dests).

Algorithm

We started by calibrating all of the sensors for the line following, as the robot's program has this possibility. The program saves the thresholds to the EEPROM and loads them when we start the program. The algorithm had many functions, of which some were:

travelToNext() - a function leading the robot to the next location (crossing),
feedback(int previous) - asks the operator for feedback,
ask_for_label() - a function where the program asks for the location,
learn_map() - first initialization and main loop of the learning algorithm,
print_map() - prints the current state of the learned topological map.

After reaching a location (travelToNext()), the robot would ask for feedback in the form of the question "What is my location?". The robot then adds the new location to the topological map, sets the location it came from as one of the exits and leaves the remaining two exits as unvisited. Then it takes the left path. If the location has already been learnt (i.e. it is present in the topological map), the robot determines whether it has some unvisited exits. If yes, then the robot will choose the unvisited exit (there can be at most one as all crossings have three exits). Otherwise, the user is asked to choose the next turn (L= left turn or R= right turn). If it was an unknown label, it is added to the topological map and the robot takes the left turn.

For more information, please check the Source code section.

Results

We managed to find a complete solution to the task. The challenge was posed by the difficulty of the map, which contained various turns at different angles. These angles, as can be seen in the image below, were sometimes quite small thus causing the function which is supposed to turn the robot to face left or right some difficulties. This means that the robot ran into some problems at these angles and would not always succeed to turn, so we had to help it manually (as can be seen in the video below). A suggestion for further implementations would be to construct a bigger map (or maze) with more accessible crossings of bigger angles so as not to interfere with the algorithm and the solution itself. The robot has successfully managed to learn the topological map.