Computer Vision aided autonomous path finding and navigation for a ground robot using a grid based approach.The approach for navigation involves path finding as a computation performed by processing frames from an overhead camera, segregating distinct nodes each standing for a specific operation that the robot has to perform based on its characteristics such as shape and color of the nodes and their relative position with respect to each other. It involves condensing complex arenas or environments into simple grids consisting of nodes as described above to simplify navigation and path finding algorithms. Applications of this approach include indoor navigation for autonomous systems by mapping distinct real-world features to specific nodes to model the environment.
Introduction and Motivation
The project aims at guiding a ground robot by processing frames captured by the overhead camera in real time and direct the robot accordingly. The journey of the robot starts from a particular node designated as the start node and ends at a destination node both of which will be identified uniquely and programmatically.
The inspiration for this project is from a nationwide autonomous robotics competition held annually at IIT-Bombay called Pixelate. For more details on the competition visit:www.techfest.org/pixelate
The motivation also comes from exploiting the approach by using it in real world scenarios such as indoor path finding and robots which are meant to traverse on grids such as cleaner bots and robots used to stack products in warehouses.
The major domains that the project spans across includes computer vision, path finding algorithms, shape detection based on identifying contours, real time object tracking and error correction based orientation.
Inspirational prior researches
The field of computer aided navigation is growing immensely with robots both aerial and ground based being developed capable of complete autonomy and the project aims at using the preexisting research for providing a solution to path finding and camera aided navigation.
Some notable achievements in this field from which the project draws indirectly include the MIT Indoor Autonomous Flight Vehicle built for the AUVSI IARC Competition and the self-assembling Harvard Kilobots.
Finding one or more paths from a set of distinct node on a grid and making the robot move along the one of the path based on certain metrics. For a detailed and more specific problem statement refer to http://www.techfest.org/resources/pixelate.pdf
1) Aluminum robot chassis
2) 150 rpm gear motors (4 nos.) along with wheels.
3) 3-axis magnetometer/orientation sensor
4) Raspberry Pi
5) Wi-Fi dongle compatible with Raspberry Pi.
6) L293D based motor driver shield
7) Colored markers to identify front and end of the robot.
The robot chassis could be replaced by the Spark V robot hence further reducing the requirement of the chassis,Raspberry Pi and other shields and sensors.
The software requirements are completely open source and include:
1) Open Computer Vision Library(Dynamically Linked)
2) Code Blocks IDE
3) Raspbian Operation System(For Raspberry Pi)-preinstalled
4) Python IDLE(For Raspberry Pi)-preinstalled
The skeletal software modules of the project that is image processing, path finding and object tracking have been implemented such that they work for certain test maps and need to be made robust by intensive testing. The main step involved in generating a row-column matrix of nodes from one frame from the overhead camera involves:
1) Capturing a frame from the registered web camera using Open Computer Vision (OpenCV 2.4.11)
2) Thresholding and filtering (such as the Gaussian Filter) to separate differently colored nodes such as white,black,red,blue,yellow etc.
3) Classifying the detected nodes according to their color and shape and storing the same in dynamic memory in the form of an array.
4) Finding out and positioning each node in rows and columns based on relative positions.
5) Exploring the all possible digressions from a candidate node until all recursion branches are completed thereby building a graph of connected nodes.
(A custom data structure which is a rapidly growing graph was used to build the connections)
6) Finding a path or paths from the start node to the destination node using a recursive algorithm which traverses the graph already built in Step 5 and pushes each visited node onto a stack. Further nodes from which two or more branches are possible are stored with a special flag used specifically for backtracking (a better understanding of backtracking and custom data structures was obtained using reference ).
Using a stack enabled more than one possible valid path to be identified uniquely.
All of the above modules were implemented in C++.
Some screenshots of the software implementation (tested on one of the test maps):
Console output messages show status as program finds all possible pathsRow Column Matrix
-- 112 5 4
118 6 1 5
116 115 8
--5 107 5
116 5 3 5
--9 3 5 1
Created a link from 9(6,2)->3(6,3)
Created a link from 3(6,3)->5(5,3)
Created a link from 5(5,3)->10(4,3)
exploration reached end
Created a link from 9(6,2)->6(5,2)
Created a link from 6(5,2)->5(5,3)
travelled right at square
Created a link from 5(5,3)->3(5,4)
Created a link from 3(5,4)->7(4,4)
Created a link from 7(4,4)->5(3,4)
Created a link from 5(3,4)->1(2,4)
Created a link from 1(2,4)->6(2,3)
Created a link from 6(2,3)->8(2,2)
Created a link from 8(2,2)->11(2,1)
Created a link from 6(2,3)->2(1,3)
Created a link from 2(1,3)->5(1,4)
Created a link from 5(1,4)->4(1,5)
Created a link from 4(1,5)->5(2,5)
Created a link from 5(2,5)->8(3,5)
Created a link from 8(3,5)->5(4,5)
Created a link from 5(4,5)->5(5,5)
Created a link from 5(5,5)->1(6,5)
Created a link from 1(6,5)->5(6,4)
Created a link from 5(6,4)->3(6,3)
At up tri last dir=r
checking for loops at 5(5,3)
right chosen for backtrack
checking for loops at 10(4,3)
no backtrackable node so no loop exists!
exploration reached end
Created a link from 6(2,3)->11(3,3)
Created a link from 6(5,2)->11(5,1)
Created a link from 6(5,2)->5(4,2)
Created a link from 5(4,2)->6(3,2)
Created a link from 6(3,2)->11(3,3)
travelled right at square
Created a link from 6(3,2)->11(3,1)
Created a link from 6(3,2)->8(2,2)
Created a link from 8(2,2)->11(1,2)
2 paths found.
The hardware implementation is self-explanatory and involved aggregating all the components mentioned under the conventional hardware implementation. (Which can be better illustrated through pictures shown below)
The project is feasible because it can be realized using available components and in finite time.It is both scalable and novel because it can be applied to several hardware based implementations as the central support system rests on the algorithms and mildly on the specifics of components used.
The projects feasibility can be shown partially through the current stage of implementation which is a after about two weeks of effort and prolonged efforts will bring about more robust and accurate revisions.
OpenCV Tutorials by Shermal Fernando
Grid-Based Navigation for Autonomous, Mobile Robots by Carsten BUSCHMANN, Florian MULLER and Stefan FISCHER Link:https://www.ibr.cs.tu-bs.de/papers/Buschmann_etal_GridBasedNavigation.pdf
Data Structures: A pseudo-code approach by Gilberg and Forouzan.
 Official OpenCV documentation as a reference to functions
 A C++ Server Socket Example on Windows using