“Build a fully autonomous image processing robot capable of navigating itself in an arena, detecting bombs and diffusing them.”
Contents
Introduction
Locomotion
Microcontrollers
Image Processing
Hardware Mechanisms
USART and Serial Communications
Conclusion
Resources
Introduction
How to Use this tutorial
This tutorial contains explanation of Robotix 2012 event, Nuke-Clear . It contains lessons and tutorials to go about making your own robot capable of competing in the event. Readers will get to learn:
How to create a differential drive
How to create an autonomous robot
The fundamentals and application of Image Processing
Communication between a robot and a computer
GPS-like navigation system
How to create robot fully capable of completing the tasks of the event, Nuke-Clear.
The main task to be completed by the bot is as follows:
The robot has to navigate itself to different rooms (bombsites) connected with multiple paths in the arena.
It has to detect the bombs located in bombsites by blinking an LED.
Once the robot locates a bomb, it has to diffuse it by pressing the correct button before it detonates. (The buttons will be differentiated on the basis of color which can be detected by an on board camera)
The explanation of the three tasks will be done under:
Locomotion
Image Processing
Hardware Mechanisms
Locomotion
Motion of the bot can basically be done by making a differential drive, which will be driven by a motor driver circuit, which gets Input from the microcontroller according to the processing done by the interaction of the bot with its surroundings.
For understanding how a differential drive works and how to make it, check the link given below: Differential Drive
Microcontrollers
The Microcontroller is the device which will control the robot and it is what makes the robot “autonomous”. Microcontroller enables you to program the robot and let it operate autonomously based on the inputs it senses.
For understanding how a microcontroller works and how to use it, check the link given below: AVR Microcontrollers
Image Processing
The most important and unique part of this event is the Image Processing part involved in it. The use of Image processing is inevitable in this event and hence, knowledge of it is of primary importance.
Image processing the frames of the video captured by a camera enables the computer to see and understand what is going on in the surroundings as perceived by the camera.
There can be multiple cameras used for this event. One overhead camera would be fixed over the arena and more cameras can be mounted on the robot based on the requirement.
A detailed tutorial on understanding and using image processing is given below: Image Processing
The overhead camera feed can be processed to view the arena live map. The white black areas are the inaccessible areas whereas white areas are traversable by the bot. Besides that, there will be multiple red and blue objects on the map. Out of those, the red squares are the bombs. Using image processing, blobs for different objects will be detected and colour and shape detection codes will be run for those blobs to differentiate the bombs from the bogus objects. The locations of these active bombs would be stored.
Moreover for live image processing, the bot’s location and orientation are also required. It is advisable to colour the top face of the bot with a colour (for detecting the location of the bot). For orientation, one can use multiple colours for head and tail of the robot or use a shape such as an arrow.
How to store the map
Two-Dimensional Array
Since the arena is made on a 12x12 unit square grid, the data blocks of unit square area can be stored in a two-dimensional array of [12][12] or [24][24]. The greater the size of the array, more the information can be stored. Each element of the array will contain the information (colour) of the map. Say, 0 represents black, 1 represents white, 2 represents red and so on.
Eg: First Room
Similarly, the whole information can be stored. More the information you process, more will be the details and more accuracy. But, do note that with increase of information, there will be more processing required which might toll the computer and reduce the time required to process each frame of the video.
Piece-wise Vectors
The paths can be represented as vectors. A vector can be represented as a structure. The structure may contain the initial position, the final position and the distance. All the possible straight paths can be stored in a linear array of such a structure.
While traversing from the initial position to a destination, possible paths can be found by checking these paths. à
Paths:
( {x1,x2}, {x2,y2}, root((x1-x2)^2 + (y1-y2)^2) }
This is a brute force method and does not involve any complicated algorithm. All the paths from a source to a destination are compared and the shortest path to the nearest destination is calculated.
Generate (recursively, perhaps) all the n! permutations of the n destinations (bombs). Each such permutation would be of the form 0,i1,i2,...,in, where i1,i2,...,in is a permutation of 1,2,...,n. For each permutation, compute the cost of the trip 0,i2,i2,...,in-1, and determine the minimum over all these permutations. This gives you the exact minimum cost, but takes O(n!) running time. The implication is that this algorithm can handle only small vales of n (like n <= 15) in a reasonable amount of time.
Divide and Conquer
Since the arena is divided into four rooms, and so can be the computation. Exact TSP algorithm can be applied to one room with exit of previous room to be the source, the entrance of the next room as the destination and the bombs as the set of all destinations the bot needs to go through.
A Greedy Algorithm
A possible greedy approach to construct a suboptimal TSP tour is to iteratively add one bombsite at a time to the tour. The initial tour starts and ends at 2 specified locations: s, the Start position and d,the End position without visiting any other city. When the partially constructed tour covers k bombsites, we identify an edge uv in the tour and a yet unvisited city w such that replacing uv by the two-leg travel uwv leads to the minimum possible increase in the cost. Here, the minimum is taken over all choices of u and w.
The Bellman-Held-Karp Dynamic-programming Algorithm
This algorithm outputs a shortest tour in O(2nn2) time.
Let X denote the set of bombsites, and let s be the specific starting zone and t be the finishing zone. A natural choice is X = {1,2,...,n}, and s = 0. Let x be a bombsite.
Now, let us define two functions. Let the function d(a,b) denote the cost of the path that goes from a to b directly. By B(s,X,t), we denote the cost of a shortest s-t path that goes through each bombsite in X once and only once. The best costs B(s,X,t) can be inductively defined as follows.
If X is the empty set (there are no bombsites), then B(s,X,t) is the distance d(s,t). Otherwise, B(s,X,t) is the minimum of B(s,X - {x},x) + d(x,t), taken over all choices of the city x in the subset X of C.
The best cost bt = B (s,C - {s,t},t) is computed by dynamic programming. Finally, the minimum of bt is the cost of the shortest TSP tour.
Dijkstra’s Algorithm
Suppose you want to find the shortest path between two intersections on a city map, a starting point and a destination. The order is conceptually simple: to start, mark the distance to every intersection on the map with infinity. This is done not to imply there is an infinite distance, but to note that that intersection has not yet been visited. (Some variants of this method simply leave the intersection unlabeled.) Now, at each iteration, select a current intersection. For the first iteration the current intersection will be the starting point and the distance to it (the intersection's label) will be zero. For subsequent iterations (after the first) the current intersection will be the closest unvisited intersection to the starting point—this will be easy to find.
From the current intersection, update the distance to every unvisited intersection that is directly connected to it. This is done by determining the sum of the distance between an unvisited intersection and the value of the current intersection, and relabeling the unvisited intersection with this value if it is less than its current value. In effect, the intersection is relabeled if the path to it through the current intersection is shorter than the previously known paths. To facilitate shortest path identification, in pencil, mark the road with an arrow pointing to the relabeled intersection if you label/relabel it, and erase all others pointing to it. After you have updated the distances to each neighboring intersection, mark the current intersection as visited and select the unvisited intersection with lowest distance (from the starting point) -- or lowest label—as the current intersection. Nodes marked as visited are labeled with the shortest path from the starting point to it and will not be revisited or returned to.
Continue this process of updating the neighboring intersections with the shortest distances, then marking the current intersection as visited and moving onto the closest unvisited intersection until you have marked the destination as visited. Once you have marked the destination as visited (as is the case with any visited intersection) you have determined the shortest path to it, from the starting point, and can trace your way back, following the arrows in reverse.
Animated Images: http://upload.wikimedia.org/wikipedia/commons/4/45/Dijksta_Anim.gif http://upload.wikimedia.org/wikipedia/commons/2/23/Dijkstras_progress_animation.gif
Hardware Mechanisms
Scissor Extension
A scissor extension controlled by a motor can be used to extend an arm from the robot to push the desired button. The mechanism would consist of basically a Fulcrumwhich is essentially a screw to hold two rods together, single or dual Arms , a Base and a Platform.
Rack and Pinion
A rack-pinion mechanism converts the rotating motion of a motor to linear motion.
- All you need is two sets of racks and pinions synchronized to move in opposite directions.
- This mechanism needs high torque motors of about 10-15 rpm.
- This mechanism can also be used for ‘Collection’
Such a mechanism is a linear actuator which can be extended to push a button
Rotating Arm
An arm rotating about a horizontal axis can be used which pushes the targeted button when turned on.
Charge the bot
The simplest way to push the button is by charging it towards the button board. An fixed extension can be made on the bot so it pushes a button when charged towards the button.
The only drawback of this mechanism is that it might damage the bomb in a way which penalizes the team. To implement this technique efficiently would be by writing a code with a safety mechanism or a feedback mechanism to prevent unintentionally damaging the bomb. Moreover, the traversing of the bot to the button board would not only waste time but, also deviate it from its route.
Spring Mechanisms
A spring is an elastic object used to store mechanical energy.
A spring mechanism can be devised to shoot an object such as a ball towards the button board. The accuracy required is very difficult to achieve and hence proves to be a cumbersome mechanism to effectively implement.
This is a very efficient design for a spring based launching mechanism. It can shoot up to 8 m/s. The design is very well-thought. The spring (2) is wound up by a spindle (7) with screw thread which is attached at a dc motor (6). A small mechanism (3) to lock and unlock the kicker (4) is placed inside the spindle with thread. In initial condition (before a kick) the kicker is locked on the spindle and holds the spring. In an elastic collision energy transfer is optimal with equal masses thus the kicker mass is almost equal to the ball mass. The motor starts turning and stops as the kicker is almost at maximum stroke. To fire, the motor starts again and presses the release-plate (1) against an obstacle. This unlocks the kicker and is driven forward by the spring. At the end of stroke is a simple damping mechanism of disc- springs (5) to prevent damage when the ball is not present in a shooting action. This system is very powerful, because much energy can be stored in a spring. For the Philips shooting device is this approximately in the order of 40 [J] It is able to shoot the ball with high velocity, 8 m/s. The number of shots is almost unlimited, because it works on battery power. However the system has also several disadvantages: It takes a lot of space, weights several kg’s and it takes about 6 [s] to reload. It is also very hard to control the shooting power. There are 2 ways to obtain variable shooting power, by varying the springs displacement or by taking energy away with variable damper. These are difficult solutions and is rather impossible to achieve variable shooting power “on demand” without any time lag.
Other Mechanisms
Other mechanisms such as the Pneumatic shooter and the Solenoid system can also be used for shooting something. But, creating such advance shooting mechanisms are essential for use in solving the problem statement of Nuke-Clear
USART and Serial Communication
A tutorial module for communication between the bot and the computer is provided. USART
After image processing, the bot needs to be given instructions how to operate the differential drive. Through USART, the computer tells the robot to traverse or press a button. The instructions can be sent by transfer of a single byte of data at regular intervals. The microcontroller installed in the robot would understand these instructions and send an output signal to the actuators and motors of the robot.
Conclusion
We have covered all essential aspects required for making an efficient robot for the problem statement of Nuke-Clear. The whole event involves the creation of a simple IP robot with an optimized TSP algorithm. Combined with the tutorial’s suggestions, your optimized implementation of hardware and software would ensure a Nuke-Clear bot.
There also exists scope of development of this system. Using image processing, any overhead image of a city, room or any region can be processed and converted into a digital map. With an optimized algorithm for a larger map and greater number of bombsites, we can implement this idea for real life situations into robots with a variety of functions.
à 
