CS 548 - Homework 1 - Implementing Bug Algorithms
Problem Definition : A point robot -namely a bug robot- must reach a certain goal point starting from any point of a given map. This task should be accoplished only with the distance sensor data and the coordinates of the start point and the end point and no data from the map should be used.
Available Tools : A sample Matlab environment is provided by our instructor. In that environment, the robot has a distance sensor which is able to collect 0-0.5 m range distance data in one scan. The robot is able to scan 0-360 degrees.
Approach to Solve the Problem : In a few alternatives like Bug1, Bug2 and tangentBug algorithms, I preferred to select Bug2 algorithm because I found it relatively simple to apply than the other two algorithms. As far as we learned in the course, Bug2 is more efficient than Bug1 in most of the cases. The only case that greedy Bug2 algorithm can be less efficient is with a one part obstacle with a complicated shape shown in figure below. In such a map, an always turn-right type Bug2 turns around the obstacle more than Bug1.
Bug2 can be description: Pls click here to view
Work Plan: In order to implement this algorithm to the provided sample environment, first I needed to analyse and understand the given Matlab functions. The given m files can construct a sample map with polygonal obstacles, display scanned data by the sensor and the obstacle edges that the distance sensor detects. First I checked out the init_arena function in CS548_HW1.m and realised that the input of start and goal points and the obstacle definitions are given here. Changing the map by modifying the polygonal data would be time consuming and I thought that the given map is challenging enough. However, in order to test my code under different conditions I changed the start point several times.
The sample draw_range_map.m scans the 360 degree data in 30 pieces,taking cross section in 12 degrees. I decided to use the same angle values. Later on, I realised that this resoution is enough to detect and follow the obstacles.
Deciding the step size was another important issue. Because if the step sizes were too large, the bug could easily miss the obstacles and intersect them. On the other hand, if the step sizes are too small, simulation time were increasing and after some point it was impossible for my PC to deal with such a small resolution. First I repeated the cycles 10-20 times, to debug the problems related to step size. After several trials I decided that the following step sizes fit well with this map.
Furthermore, after several trials, I decided the best angle for adjustment in cases where the robot does not go parallel to the wall is 4 degrees.
Wall Following :
In order to follow an obstacle, the perpendicular line to its gradient can be used. However, in our case the obstacles are polygonal, there is no curvature. Finding gradient could be complicating the problem and could be less efficient. In this case, first I applied two cosine theorems to find the incline angle of the followed obstacle from zero degree reference. However, the formula I constructed worked only for two quadrants because of the sign changes of angles. Therefore I needed a solution that could work for all four quadrants. I remembered what I previously I used in Excel; Atan2 function of Matlab could help me in this case since it returns the ubique angle with the given x and y values. My angle detection formula is given below:
function angInc = cosTheoIncline(minDist, tanDist, index, xx, yy);
xMin= xx+minDist*cos(12*(index)*pi/180);
yMin= yy+minDist*sin(12*(index)*pi/180);
xTan= xx+tanDist*cos(12*(index+1)*pi/180);
yTan= yy+tanDist*sin(12*(index+1)*pi/180);
angInc = atan2((yTan-yMin), (xTan-xMin));
Problems & Difficulties : Although I stated that Bug2 algorithm is rather easy to apply, I faced several difficulties. These difficulties were mainly related to catching the mLine. I couldn't find proper conditional statements for some of the cases and this has led the following results.
In the first picture it is seen that the bug cannot reach the goal because there is a slight difference between the mLine angle and the angle read from the sensor. In this case the robot gives an error message and stops. I could deal with this problem by increasing the sensitivity in the comparison between the sensor data and the calculated angle and added the command to follow mLine in case of an else statement. It may cause collision but when the cycle starts again the robot detects an obstacle and gets out of this else situation.
In the second picture the robot just passes the goal(!) and continues to follow next obstacle after the cycles end. I fixed this situation by increasing the proximity situation to the goal, increasing it from 0.1 m to 0.2 m. I don't think that it may cause a problem unless the obstacles have very thin edges. In such a condition, my step size choice could also be poor. After several runs I decided that the bug_planner works well and I removed the constraint in the number of cycles.
After fixing similar problems, I was able to reach the goal and then I increased the distance between goal and the start by putting the start point back to its original value [2 9]. It took 629 runs from this point.
Conclusion : Bug2 is implemented succesfully in this environment. With so few tools like a limited distance sensor, and without any map information it does not seem possible to get a higher performance. In the final case any always-turn-left robot would turn around the whole obstacle, there is no guarantee in any direction or to go in circles etc. The most logical way seems to follow the mLine as much as possible. As it is stated above there is only one extereme case that the Bug2 algorithm may lack efficiency.
Due to time limit, I couldn't put any condition to check whether the obstacle is in a closed loop. All of my solutions are based on that the goal is reachable. In further versions of my study I am going to add this condition in order to achieve full completeness.
The links for the codes (.rar files)
Bug2 Algorithm by Mine