In this post I’ll be explaining our task for e-Yantra Robotics Competition 2015 Puzzle Solver 1 GLCD, which won the competition from all over India.
First of all, I need to tell you what is e-Yantra Robotics Competition. e-Yantra Robotics Competition (eYRC) is a unique annual competition for undergraduate students in science and colleges. Selected teams are given a robotic kit complete with accessories and video tutorials to help them learn basic concepts in embedded systems and microcontroller programming. Abstracts of real world problems assigned as “themes” are then implemented by the teams using the robotic kits. The winners of this competition will be eligible for summer internship at IITB through e-Yantra Summer Internship Program .
In eYRC, our theme was “Puzzle Solver 1 GLCD”. I was doing my Diploma in APC Roy Polytechnic (Jadavpur) and it was final year. Our college faculty made a team and we were four of us selected from four different branches. Myself Arpan Das from Computer Science & Technology, Avick Dutta from Electronics & Instrumentation Engineering, Subhendu Hazra from Electrical Engineering, and Asesh Basu from Mechanical Engineering. We were the only Diploma team out of 44 finalist teams, rest of all 43 the others were B.Tech.
Problems, which exist all around us, are in fact the very fuel for our intellect. As long as problems exist, there will be engineers to solve them. However, solving these problems is not always an easy job and many a times, we need to devote a significant amount of time formulating the best practical solution to these problems.
Engineering, in a way, can be described as the meticulous art of solving problems in our daily life. As the popular saying goes, “Necessity is the mother of all invention”, however, Engineering is the tool, which when wielded, facilitates that invention.
e-Yantra Robotics Competition Plus 2015 introduces the “Puzzle Solver Robot” theme as a means to test the algorithm development skills of the participants. Such skills are mandatory to solve problems in a number of industrial as well as commercial applications like Warehouse Management, Air and Road Traffic Control, Shipyard Cargo Management, Automated Home Delivery, etc.
In this theme, teams have to solve a mathematical puzzle involving a variety of topics like Digital Image Processing, Motion Planning and Simple Arithmetic. The arena for this theme consists of two divisions – The first is a grid with each Cell in the grid containing a digit from 0-9; the second is a grid with a maximum of four numbers in the range 0-20 placed arbitrarily in any Cell of the grid. The robot has to choose the numbers in D1 such that they add up to each number in D2.
The challenge is to complete this task in the shortest time possible. The robot that performs the task best in accordance with the rules set for this task will be declared the WINNER of the competition.
- Prior to the start of theme execution, an input image of the arena is given to the team. An example is shown in Figure 1 that is used in this rulebook to explain the Theme. The arena represents a simplified abstraction of a puzzle with the following:
- There are two divisions: Division 1 (D1), and Division 2 (D2).
- D1 is a grid having 12 Cells and D2 is a grid having 24 Cells as shown in Figure 1.
- Each Cell in D1 contains a one digit number (i.e. number from 0 to 9) while any one or two digit numbers only upto 20 (i.e. numbers from 0 to 20) are present in some of the Cells in D2.
- The team analyzes the given image on computer by using image processing which generates the information regarding the numbers and their positions in D1 and D2 and then communicates this information to the robot.
The goal of this Theme is to choose numbers in D1 such that they add up to each number in D2. The robot starts from START position and does the following:
- Traverses the grid in D1 and picks up the number.
Pick up is considered when the number is displayed on GLCD (Graphics Liquid Crystal Display). While picking, the robot should be on the cell boundary of the corresponding number. The same is explained in detail in Section 6: Theme rules.
- Traverses the grid in D2 and deposits the number.
Deposition is considered when the message “Deposited” is displayed on GLCD. While depositing also the robot should be on the cell boundary of the number on which the picked number is deposited.
- Numbers deposited on a number in D2 must add up to that number.
- The robot buzzes the buzzer for 1000 ms indicating completion of the solution for that number in D2.
- Steps i – iv are repeated till all the numbers in D2 are solved.
FINISH line is NOT marked on the arena; the robot stops when it solves the puzzle and sounds a continuous buzzer as an indication to show that it has finished the task.
3. The Arena
- The arena represents a simplified abstraction of a puzzle. It is divided into two divisions D1 and D2 with a black line connecting them. D1 and D2 consist of grids having nodes at the intersections. D1 consists of 12 Cells, whereas D2 consists of 24 Cells.
- Each Cell in D1 contains a number while numbers are present in some of the Cells in D2. All the numbers which are used in arena are given in form of patches.
- Arena design is shown in Figure 2. It is divided into two sections,
- Arena section (top) and
- Patch section (bottom).
- A pdf file containing the arena design is given to the teams. Each team prints the arena design on flex sheet according to the directions given along with the file. Note: You must print the entire arena design having both the Arena and Patch
- Teams are not authorized to make any changes in the arena design. Any team making unauthorized modifications will be disqualified from the competition.
Details of Arena design (Refer to Figure 2):
- Dimension of arena is 243.84cm x 152.78cm.
- The arena consists of grids in D1 and D2, made of black lines of thickness 1 cm. Square nodes of dimension 3cm x 3cm are provided at the intersection of two lines.
- The dimension of each Cell in D1 and D2 is 30cm x 30cm.
Preparing and Placing the Patches:
- Once the arena design is printed, the team must cut along the indicated line to separate the Arena section and the Patch section.
- The dimension of Patch section is 30.5cm x 243.84cm with the numbers printed on it as shown in Figure 3.
- Cut along the dotted lines to get 42 individual numbered patches.
- Paste the number patches on to the arena as per the input image using transparent cello tape only.
- Figure 4 shows pasting the number patch using cello tape.
- For our example, after pasting all the patches in the appropriate locations, the arena looks like Figure 5.
Note: The arena shown in Figure 5 is specific to the example considered. During the
competition the numbers and their positions will be different (given as an input image)
and hence the placement of patches will vary accordingly.
4. Hardware Specifications
4.1 Use of Firebird V:
- All participating teams must use only the Firebird V robot sent to them in the kit.
Only one robot given in the kit is allowed per team.
- Team shall not dismantle the robot
- The robot should be completely autonomous. The team is not allowed to use any wireless remote or any other communication protocol or devices such as a camera while the robot is performing the task.
4.2 Use of additional components not provided in the kit:
- No other microcontroller-based board shall be attached to the Firebird-V robot.
- Teams may connect external actuators along with their driver circuits to the Firebird V robot only on the condition that the actuators must be controlled through the Firebird V robot.
- The team is not allowed to use any other sensors apart from those provided in the kit.
- The teams must use a laptop/computer capable of running OpenCV and Python.
4.3 Power Supply:
- The robot can be charged through battery or auxiliary power supply. These are shipped with the robot.
- The team cannot use any other power source for powering the robot.
- The team can use auxiliary power during practice but the final demonstration should only be made using only the battery powered robot.
5. Software Specifications
- e-Yantra has provided all teams with ATMEL STUDIO 6, a free software for programming AVR microcontroller. Participating teams are free to use any other open source Integrated Development Environment (IDE) for programming AVR microcontroller.
- The teams must use OpenCV and Python to write their code.
- Use of any non-open source libraries is not allowed and will result in disqualification.
- As per e-Yantra policy, all your code and documents are open-source and maybe published on the e-Yantra website.
6. Theme Rules
- The maximum time allotted to complete the task is 10 minutes. A maximum of two runs will be given to a team (the better score from the two runs will be considered as the team‟s score). A maximum of two repositions (explained below) will be allowed in each run.
- The team should switch ON the robot when told to do so by reviewer. This is the start of a run. The timer will start at the same time.
- Robot should be kept at the START line with the castor wheel of the robot positioned on the line.
- Once the robot is switched on, human intervention is NOT allowed.
- The following are the steps of the task:
- The input image is given before the start of the run.
- Robot is placed on the START position and turned on.
- The team must use OpenCV and Python to detect the numbers and their positions on the input image and display the same on python IDLE console.
- The teams must use the USB to serial cable to communicate the information from the computer to the robot.
- When the communication is completed, remove the USB to serial cable.
- Press the Boot key to start traversal of the robot.
- Note that the robot waits at the START position till the Boot Key is pressed.
- The robot must traverse the grid in D1 and pick up a number and deposit it in D2. Details are explained below.
- For each number in D2, the robot buzzes the buzzer for 1000 ms. when the numbers deposited adds to the number in D2.
- Repeat steps viii and ix for each number in D2. After completing all the numbers in D2, sound the continuous buzzer to indicate the end of the task.
- Displaying detected numbers and their positions :
- As in Task 1 in Stage 1 of this competition, for D1, display the entire array of numbers in the cells starting from 0 to 11 and for D2, display only the Cell number and the number contained in that corresponding Cell.
- For example, given the test image in Figure 1 as input, the output on the Python IDLE console will look like:
D1 = [8,6,1,5,2,0,7,2,3,9,1,3]
D2 = [ [2,10], [6,12], [22,14] ]
- Picking up the number :
- Picking up a number is represented by displaying that number on the GLCD.
- While picking, robot should be on the boundary of the cell. The position and direction of the robot can be on any of the four red dots given in Figure 6.
- The following are the steps of the task:
Two LEDs should be connected on either side (left and right) of the robot. To indicate the exact cell, robot must glow the LED on the corresponding side.
Suppose robot has to pick up the number 7.
Robot traverses to the cell; if the position of the robot is as per Figure 7 then it should glow the right LED and display „7‟ on the GLCD.
Disposing the number:
- Depositing a number is represented by turning off the LED at the appropriate Cell in D2 and displaying the message “Deposit” on the GLCD.
- While depositing also the robot should be on the boundary of the cell.
Note: When a LED is ON the robot should turn it off only when the number (on which the picked number is to be deposited) is on the same side as the lit up LED .
Example: In continuation of the example above, suppose robot has to deposit the picked number 7 on number 10 in D2.
Since right LED is ON, number 10 should be on Right Hand Side of the robot.
This is illustrated in Figure 8.
- Numbering in Divisions:
- In D1,
- Numbers are present in all the 12 Cells.
- Each cell may contain any one number from 0 to 9.
- In D2,
- Numbers are present in some of the 24 Cells.
- A maximum of 4 Cells contain any one number from 0 to 20.
Note: The numbers given in the input image are such that, at least one possible sum can be obtained for every number in D2 from the numbers given in D1.
- Buzzer sound for more than 5 seconds will be considered as continuous buzzer.
- A run ends and the timer is stopped when:
- The robot stops and sounds the continuous buzzer or
- If the maximum time limit for completing the task is reached or
- If the team needs repositioning but has used both repositioning options of that run.
- Second run will start once again whilst resetting the score, timer and arena. The score of both runs will be recorded and best of two runs will be considered as the team‟s score.
- Participants are not allowed to keep anything inside the arena other than the robot. The time measured by the reviewer will be final and will be used for scoring the teams.
- Time measured by any participant by any other means is not acceptable for scoring.
- Once the robot starts moving on the arena, participants are not allowed to touch the robot.
- The robot is not allowed to make any marks while traversing the arena. Any robot found damaging the arena will be immediately stopped; repositioning will be allowed as per the rules. The final decision is at the discretion of the e-Yantra team.
- In D1,
Repositioning of robot:
Suppose while traversing the arena robot strays off the black line (Refer to Figure 10), a member of e-Yantra team who will be monitoring the task will place the robot on the previous node (node already traversed by the robot) in such a way that both the wheels of robot are parallel to the node and castor wheel is on the black line (Refer to Figure 11). This is termed as a Reposition. Note that the timer used for measuring the task completion time in the competition will be continuously running during a Reposition and robot will not be switched off.
- We need to detect all the numbers and their positions from the arena given in JPEG image by performing OCR.
- Then we need find out the best possibles combinations of numbers from D1 by which adding them we can make the sum of all of the numbers in D2 using minimum number of operands.
- Then we need to calculate the minimal traversal path for the robot.
- After that, we need to assemble, configure, setup the GLCD. We also need to write a function to write big characters and images on the GLCD.
- Wee need to prepare code for the robot to follow black lines on white surface and detect the black square grids.
- Then we need format all the data generated previously.
- The formatted data is to be transmitted to the Firebird V bot using serial cable.
- We need to configure the interrupt button on the bot such way that the bot should start when we press the interrupt button.
- And then the bot must finish the task.
- All numbers are read from the given image, and positions are detected using Python and OpenCV.
- Best possibles combinations of numbers from D1 are calculated using Python and Numpy.
- Shortest traversal path is calculated.
- 128 x 64 GLCD kit is assembled by hand and connected to the bot. GLCD manipulation functions are written in embedded C.
- Robot’s movement responsible codes are written in embedded C.
- The data we got from 1 & 2 are formatted and ready to be transferred to the bot.
- The formatted data is transmitted to the Firebird V bot using serial cable.
- The interrupt button on Firebird V is configured.
- Bot is now ready for the task.
Solution in breif
How OCR is done?
If img is a string i.e. image's file name, then we read the image, else its already an image. Note that img1 is needle and img2 is haystack. We store height and width in img1 in h1 and w1 respectively. We iterate through variable i in range 0-9 and indented process below is for each iteration. (Please see the directory "data" which has numbers stored as images with the number as file name. This is the memory of the program). We read the image with file name and stores height and width in variables h2 and w2 respectively. Then we calculate average height and width and store them into hAvg and wAvg respectively. After that we resize both the images with average height and width i.e. hAvg and wAvg respectively. Then we calculates the image difference by XOR-ing two images using cv2.bitwise_xor() method and store the result into variable diff. Then we sum up all pixels of diff (black=0, white=255) and store the result in the variable sumOfDiff. After that we append pair of i and sumOfDiff into array matched_digit_list. After all abobe process, we sort the matched_digit_list in ascending order and stores the first element i.e. the least difference into variable retval and then we return retval.
How to get best possibles combinations of numbers from D1?
Iterate through each number present in D2_values and repeat the indented steps below: Call matcher(D1, number) If matcher.results is not empty then set variable result = matcher.results and reset matcher.results If result is found, then remove the result from D1 Make array of one element i.e. number and result and append the pair into result_set (result_set will have lists that each list contains list thatthe first element is the number , and rest of others [1:]are the operands used the make the sum of that number) Initialize new variable operand_used = 0, incomplete = 0, priority = 0, priority_one_var = 0, priority_two_or_more_var = 0, i.e. all equals to 0 initially. Now, iterate through each result present in result_set and follow the indented steps below: operand_used = operand_used + number of elements in result - 1 If number of elements in result is equals to 1, then incomplete = incomplete + 1 (i.e. no = incomplete (no operand)) Else if number of elements in result is equals to 2, then priority_one_var = priority_one_var + 1 (i.e. no = x (one operand)) Else priority_two_or_more_var = priority_two_or_more_var + 1 (i.e. no = x+y+... (two or more operands)) operand_used = 12 - operand_used (complement it as lower is better (12 = no of element in D1)) incomplete = number of element in D2_values - incomplete (complement it too as lower is better) incomplete = incomplete * incomplete (giving more -ve priority: as using more operands is better than leave incomplete) Then finally priority = (incomplete * operand_used) - priority_one_var + priority_two_or_more_var All after abobe process, we return result_set and priority.
How the shortest traversal path is calculated?
Prioritize D1 to get nearest number among ambigious numbers by manually sorting position-value pair in D1 and store the result pairs into D1_prioritized_kv. Then get only values from D1_prioritized_kv and store the result into D1_prioritized_v. Now we need to make values invalid, so the keys i.e. positions will be only valid. Copy D2_1D into D2_copy. Then iterate through D2_copy, for each element present in D2_copy and taking i as iteration counter repeat as indented steps follows: if i is even i.e. it a value, then set i-th element of D2_copy to -1 to make it invalid. Now we generate solution se in this form: D2 position, D2 value, D1 position, D1 value, D1 position, D1 value... (rest operands in D1); D2 value, D1 position, D1 value, D1 position, D1 value...; ... (rest solution set in D2, D1). e.g. - 1,16,3,8,10,8;10,14,1,9,2,5;23,10,6,7,7,3. To do that, terate through each element i.e. solution in results taking i as iteration counter repeat indention below: Iterate through each number present in each solution taking j as iteration counter repeat indention below: If j is equal to 0, then do as indention below: Get the position index of first occurance of y in D2_copy and stor it into variable pos. Concatenate pos-1 th element of D2_1D into output_str following a comma. Concatenate y into output_str. Set -1 to pos th element in D2_1D to make a used number invalid. Set -1 to pos th element in D2_copy mark the current D2 number as used so that the robot will not fill it again. Else, do as indention below: Get the position index of first occurance of y in D1_prioritized_v and stor it into variable pos. Get the actual position from D1_prioritized_kv and store it into variable actual_pos. Concatenate actual_pos into output_str following a comma then concatenate y into it. Set -1 to pos th element in D1_prioritized_v to make a used number invalid. If j is not equal to (number of elements in x) - 1, then concatenate comma into output_str. If j is not equal to (number of elements in result) - 1, then concatenate semicolon into output_str. Now we are going to generating the traversal path of the robot in comma separated format i.e. D1 position, D1 value, D2 position, D2 value, D1 position, D1 value ... e.g. - 3,8,1,16,10,8,1,16,1,9,10,14,2,5,10,14,6,7,23,10,7,3,23,10. To do that, we split output_str by semicolon and save the returned array into variable results_array and reset output_str. Now, we iterate through each result present in results_array and do the indented steps below: We split result by comma and save the returned array back into variable result. Initialize variable j = 0. We iterate through each number present in result[2:] i.e. 2nd element to last element if result, follow indention below: If j is even do as following indented steps: Concatenate 2+j th element of result into output_str following a comma. Concatenate 2+j+1 th element of result into output_str following a comma. Concatenate 0 th element of result into output_str following a comma. Concatenate 1 st element of result into output_str following a comma. j = j + 1 After that removing the last comma from output_str and return output_str.
How the robot can follow a black line?
White line sensors are type of localization sensor which consists of highly directional photo transistor. They can detect white line on black surface or black line on white surface by inverting the logic. White line sensors are used in our theme to detect and follow 1cm thick black line on white surface. We also used them to detect 3x3cm black boxes on each corner of cells.
Three white line sensors are used in our theme. As given in rulebook, borders of cell are 1cm thick and black squares on corner of cells are 3x3cm. But the distance between two white line sensors are more than 1cm. So, to follow a 1cm black line, we can linearly forward the robot if all three white line sensors are on white surface or the center white line sensor is on the black surface. We decrease velocity of the right wheel and increase velocity of the left wheel if right white line sensor is on the black surface and other twos are on the white surface. Similarly we decrease velocity of the left wheel and increase velocity of the right wheel if left white line sensor is on the black surface and other twos are on the white surface. This way the robot follows a 1cm thick black line as shown in the figure below.
Conditions for detecting 3x3cm black squares are below (Figure 3):
- If right and center white line sensors are on black surface and left white line sensor is on white surface, we also detect it as a 3x3cm black square.
- If left and center white line sensors are on the black surface and right white line sensor is on white surface, we detect it as a 3x3cm black square.
- Again, if all three white line sensors are on black surface, we also detect it as a 3x3cm black square.
Note: All information provided here are in very brief. The whole implementaion is too big to post on a single article. You can get full details and source code from my GitHub.
All source codes are open and available on my GitHub:
Our Score Card
The final result
Veni, vidi, vici!
I just cannot express in words how much we enjoyed through out the entier competition specially the final at IIT Bombay.
I would like to thank our teachers Mr. Biswanath Paul, Mr Arunangshu Das, and Mr. Anupam Chatterjee. for all the official help and support. And a very special thanks to our mentor Mr. Sudipta Mondal for all the support and he is the reason I get into robotics and embedded programming today. My heart is still smiling.
If you have any question, please comment below.