[2017] Bidirectional Maze Solver: Pointer manipulation for flipping, Computer Vision ideas

In November 2017, I formed a group with 3 others to compete in Sri Lanka Robotics Challenge 2017 (to be held on January 2018). According to the task, the two teams must produce two robots each, one stationary and one mobile, which should coordinate via any wireless method to complete the task.

My Responsibilities

I was appointed the group leader and also I took the responsibility of designing and coding the mobile robot, which is a line maze solver. I also refined the concept and made final design of the stationary robot (which should be able to shoot a ball turning 360 degrees in horizontal plane and to about 10 degrees in vertical plane).

The Mobile Robot: Innovative Ideas

Since the task of mobile robot is relatively easy to perform, I realized the key for winning is the speed. When I considered different ways to reduce the time taken, I noted two factors:

1. The robot takes some time to make a U-turn at nodes of the maze. Also, a U-turn is dangerous as since the sensor panel moves completely out of the line, there is a chance the robot might get disoriented.
2. By traditional always-take-left algorithm, the robot visits empty nodes (where boxes are not kept), wasting time.

1. Bidirectionality: Eliminating U Turns

I proposed the idea to make the robot fully bidirectional. While increasing the cost, this needed some redesign of the body from traditional designs and the need for some innovative methods to be used in coding.

a) C pointers and OOP programming for bidirectionality

I have learnt the wonders of pointer & reference manipulations in C++ language and I have learnt OOP concepts through Java & PHP programming. I decided to combine them as a solution.

As shown below, I made classes for motors and created objects for each motor, sonar, IR panel and color detector. Then I defined references *pMotorLF, *pMotorLR...etc for front left, front right...etc motors from the POV of the robot. The rest of the code would be written in terms of the pointers, not of the objects themselves. 

eg: pMotorLF->drive(-100)

Using a custom flip function I could change the objects to which the reference is pointing to and this would effectively flip the entire robot internally.

A function definition for the motor class.

Flip function definition. Calling this function would immediately software-flip the robot by 180 degrees

b) Hardware issues & solutions

Due to bidirectionality, we decided to place the relatively expensive main line sensor panel (8-qtr) at the exact center of the robot. This has the disadvantage that the the small lag between sensing and acting would make the robot act too late and veer off the line. It was solved by (c)

2. Variable Speeds & variable PID constants

To solve this, I came up with the idea of using two sets of speed configurations. I proposed that we could use a relatively cheap 3-qtr at exact center of each front and back lines. 

• If the robot senses a line on the front 3-qtr, he assumes a a higher speed and the PID constants associated (and tuned) with respect to that speed. 
• If not, robot assumes a lower speed and associated PID constants.

Using this method, the robot moves at high speeds along straight lines and at lower speeds near junctions and curvy lines, reducing the error.

3. Loophole in the rules - Workaround for hard coding

According to the task, few nodes of the maze graph are left empty, without any boxes. A traditional take-left robot would visit them, wasting time. The solution would be to hard code the maze, but according to rules, the positions of the boxes are changed in every round and hard coding is a crime. 

As a workaround, I proposed the idea of manually inputting the maze using buttons before the round (which was not restricted, a loophole). I wrote an algorithms to always take left, but avoid the i-th left, where i is a member of an array (where  the turns to be avoided are stored). The array is initialized empty and it can be filled by pressing buttons on top of the robot. 

Before a round, when the boxes are placed, I would take down the turns that need to be avoided and press buttons according to the programmed protocol to fill the array with those numbers. The robot would then simply avoid those turns, saving time.

Ideas on Computer Vision

To avoid empty nodes, I also proposed a solution with machine vision. By that time, we were taking a module: "Fundamentals of Image Processing and Computer Vision" and I had some experience with image processing methods. 

I proposed, we could 

• Mount a camera module on the stationary bot (then the view and the projective transformation is known in advance)
• Apply projective transform, crop to the arena and get ImIn
• Skeletonize the thresholded ImIn to get the path
• Finding unique blobs in the R,G,B layers separately to identify boxes
• Using array navigation to find which nodes to be avoided
• Transmit an array full of "turns to be avoided" to the mobile robot

I proposed the above to Kanchana, my colleague who is actively researching in computer vision field and he agreed to join our team.

Project Discontinued

The group was highly active and as I wrote the algorithms, rest of the group started to build the prototypes for the robot. However, due to academic workload, the hardware guy in the group decided to quit. He needed to focus on the web development project which we needed to do for another module. Without a hardware guy, I could not continue this and finish it before deadline. Therefore, sadly the project was abandoned.

Github Repository

github.com/abarajithan11/bidirectional_bot