Final Project Report Document
Introduction to Robotics
Dr. Ayorkor Korsah
21st December, 2012
The overall concept of my final robotics project was to design and build an exploration robot that would scan its environment and build a map that accurately represents that environment. In the project proposal submitted, the focus of the project was on motion planning and mapping using the Histogramic In-Motion Mapping (HIMM) technique. However, this algorithm could not be implemented but rather a solution I developed based on my understanding of the concept of the HIMM technique and the CMU mapping technique from which the HIMM was developed from.
The motivation behind this project was the interest I got from reading about robot mapping and motion planning. Deeply thinking about the HIMM and SLAM (Simultaneous Localization And Mapping) techniques was thrilling especially comparing it to how easy it is for humans to get the sense of their environment and simply know where they are and move around flawlessly. Unlike the excitement from reading, actually executing this project was awesomely tedious.
The initial designs of the project after a few brainstorming sessions before drawing up the project proposal got outrageously out of scope with the concepts of autonomous localization of the robot. This idea just like the implementation of the actual HIMM technique required the whole project to accommodate a certain level of randomness and unpredictability that would make the project difficult to complete considering the limited time frame.
A more simple design concept was developed to eliminate the element of randomness and unpredictability. The design was
- To move in a calculated manner of one cell at a time using 8 point connectivity on an occupancy grid map.
- To scan the four main sides of the robot.
- To use a mathematical model to generate the senor output into information for the map.
- To visit every cell in the grid to generate the map representation.
- To send the map data from the robot to a remote site for visualization.
Building off from the designs used in the Wave Front planning task, the fundamental code for moving to a series of cells making a path was already available (i.e. the Movement module). This module had functions for moving one cell forward, turning 45 and 90 degree right and left, determining the bearing of valid neighboring cells and moving appropriately to them.
Also, the same robot architecture was used with slight modifications to accommodate the four sonar sensors. The sensors were placed in front, behind, on the left and on the right sides of the robot as illustrated in Figure 1. The positioning of the sensors gave a fairly complete view of the area around the robot though not a complete 360 degree panoramic view.
The next critical and ultimately the most challenging task was to develop a coverage algorithm that would allow the robot visit every cell in a given grid. I spent a lot of time searching for ideas and already existing algorithms that insured that every cell in a grid would be accurately covered in the most efficient manner. Most of the results of my search pulled up concepts that had to do with graphs like the Travelling Salesman Algorithm and other Graph Coverage Algorithms. Despite that, already existing implementations of these algorithms that suited the project I was working on proved futile. These algorithms did not use the idea of moving systematically from one cell to the other using only valid neighbor cells available but rather computing a path using a Bresenham’s line generation algorithm from a current cell to the next optimal cell in the coverage sequence. Also, the graph coverage algorithms did not accommodate the presence of dynamic obstacles present in the environment.
After, several attempts of designing, testing and redesigning of a model that would allow the robot efficiently cover every cell in a given grid while accommodating the presence or absence of obstacles, a solution was finally developed (i.e. the Path Module). The fundamental theory of this Path Module is
- To start at a given known location.
- Find all the valid neighboring cell of the current location i.e. cells that have not been visited, cells that have no obstacles and cells that are not outside the defined area of the map.
- Move to the first valid neighboring cell.
- Store all the valid neighbor cells that were not chosen into an unvisited cell data structure variable.
- Remove current cell from the list of unvisited cells.
- If no valid neighbors are found and the size of unvisited cell data structure variable is not empty, then backtrack to the most recent unvisited cell using a Wave Front planning algorithm that re-plans after every move to a destination cell.
- When all the unvisited cells have been visited, terminate the process.
This module was developed from scratch from simply experimenting with ideas that came up and fixing faults that arose from testing those ideas. Major fault encountered when developing the coverage algorithm was determining when to stop after every cell was covered without moving back and forth between two cells infinitely. Prior to using the Wave Front backtrack idea, the algorithm run over a 100 time in order to cover just a 5×5 grid map. This was because, the back track idea used then, was to keep track of all the covered cells and undo each move (by going back the path covered) until an unvisited neighbor cell is found. Because, the earlier algorithm retracted along the path already covered, when an obstacle gets in the way of the old path the algorithm failed. The Wave Front plan and re-planning backtracking concept catered from new obstacles that blocked already covered paths and provided options no matter the situation.
The next sub task was to translate the senor readings into a mathematical function that would be used in building the map. The approach used in the HIMM algorithm was understandable in theory but difficult in implementing. In this area also, I experimented with idea and the failures they brought up until a Scan and Map Building Module was developed. The theory underpinning this module was as follows;
- Take sonar readings from the four sensors (an average of 10 readings was always taken to make up for the noise encountered with the sensors).
- The readings are then converted into the grid cell range values by dividing the readings by the length of one grid cell. This meant that every obstacle was known not just by the distance in centimeter but also by the number of cells away.
i.e. So an obstacle that is detected 100cm away has a grid cell range value of 100/ 45 = 2.222, which is about 2 cells away
- With the grid cell range value and the current bearing of the robot (i.e. North, South, East or West) the appropriate immediate four neighboring cells (because only four sensors were mounted) of the current location were updated to the grid cell range values. As illustrated in Figure 2 and 3, the four neighbors of the current location are updated with values that represent the number of cells between an obstacle and the current location cell. When the robot moves to the next cell, the same procedure is repeated as shown in Figure 4 and 5 and Figure 6 and 7.
- The current cell is given a value of 7 to indicate that it is certainly free. A cell with a value of 7 cannot be re-updated except on the event when the grid cell value of that cell is determined to be 1 (i.e. certainly occupied) in building process.
- Continuously updating the four neighboring cells of each grid cell builds a map that adequately represents the environment. This technique also captures changes to the obstacle present or absent in the environment without erratically changing certainly free cells.
The next sub task of the project was to work on communicating with the remote Bluetooth server. I downloaded source code that implemented a java Bluetooth server from (http://www.miniware.net/mobile/articles/viewarticle.php?id=22). After studying the RobotC API and experimenting with the ideas used by other RobotC NXT Bluetooth communication projects online, a communication module was developed. This module did the following things;
- Turn on the Bluetooth functionality of the robot.
- Set the robot Bluetooth visibility feature to discoverable.
- Search for and pair with my laptop on port 2.
- Activate the communication stream to write raw bytes of data.
- Shutdown the Bluetooth server after completion.
The robot after establishing communication with the Bluetooth server sends initial data that is used to initialize certain parameters on the server side. The robot then sends frequent data updates about its current position in the map, its bearing and the latest version of the map being developed.
On the server side, the data packets are identified and approximately represented in text on the console display. Also, a color coded interface of the grid displays the information being sent from the robot for better visualization. This visual component was developed from java applet code used by Programming II student in one of their assignment. As illustrated in Figure 8, cells with the value of 0 are unexplored and have a gray color, cells with the value of 7 are certainly free and have the color green, cells with the value of 1 are certainly occupied and have the color red, the current cell location is color coded yellow while any other value between 2 and 6 have the color blue and are in the known unvisited cell list.
It is critical to point out that, I did not fully understanding the implementation of the HIMM technique I studied. The algorithms I developed were mostly my own understanding of the concepts presented in the readings and research I had done. After several test runs of the whole project, I realized that the robot constantly lost it sense of location whenever the emergency obstacle avoidance module was triggered in.
The robot used the generated map to avoid obstacles and the Wave Front planning algorithm allowed it capture changing obstacles very well. However, in case the robot detects an obstacle in a 10cm range in its path that was not initially detected before it starts moving, an emergency avoidance module is triggered to take it back to the cell it was moving from. Triggering this module repeatedly causes the robot to lose track of its current location in the map. The cause of this malfunction is still not known and thus has not being fixed.
One other major challenge encountered was actually getting already existing implementation of the various concepts that were described in the papers I read. Sample code or pseudo code of how the techniques presented in the research papers could be implemented, were not available to serve as a guide for the work I was doing. This is the main reason I moved towards implementing my own understanding of the concepts they presented.
In conclusion, I would say this was a very exciting challenge for me and I really got to appreciate the technical and mathematical skills needed to develop a fully functioning robotic project. Unlike programming where debugging only occurs in the code; with robotic projects, bugs could arise from mechanical faults when building the robot with the Lego kit, electronic faults from the sensors or NXT console, logical errors from the concept of the algorithm being implemented or syntax errors from the very limited RobotC language.
Despite the satisfaction from getting the robot to work, I was really excited about the fact that I designed and implemented my own algorithms that work quite well and that I could to a large extent predict every move of the robot. The ability to predict gave this feeling of control and help me really appreciate how complicated yet beautiful the human mind is. I believe, this was a successful job done and I am excited about taking on the next challenge of mapping the whole Ashesi University campus in my final year capstone project using the KINECT kit and the Roomba Robotic kit.