CS 548 - Robot Motion Control and Planning

Assignment #1: Implementing Tangent Bug Algorithm

Ali Nail İNAL

Bilkent University,Electrical&Electronics Engineering Department

Instructor: Asst. Prof. Uluç SARANLI

Introduction

In this project, we try to implement the tangent bug algorithm, that is a part of the basic motion planing algorithms family bug algorithms. These algorithms, generally used for motion plannig with sensor-based robots that only use basic sensor information to (such as touching sensors, range sensors, encoders, etc.) plan their path. Bug algorithms are complete algorithms, thus even though it may not be most efficient, they will give the solution if it exists. Bug algorithms, make assumption in order to make the plannig problem easier. They assume robot as a point and think that all sensors working perfectly, namely there is no error in any estimation or measurements.

The reason we use bug algorithms is their basic structures, and the view point they provide us for real life examples. Since we can put any object in to a circle with finite radius r, if we look into the congiguration space it can be observed as a point object. Thus we can use these algorithms on simple mobile robots that use cheap and basic sensors for navigation.

Figure1: Workspace and configuration space of a robot.

Details of the tangent bug algorithm and its assumptions will be introduced later.

Problem Description

First goal of this assignment is to obtain a simulation environment that can be used for algorithm simulations that has the following properties:

i. A bounded, rectangular workspace

ii. A configurable set of polygonal obstacles, not necessarily convex.

iii. “Virtual" sensors for measuring the positions of the robot and the goal

iv. A laser range sensor with a predetermined range limit (initialized before starting the simulation), returning an array of distance values for a discrete set of angles

5. The ability to accept either velocity, or discrete displacement commands from a "controller", that can be used to implement a particular planning algorithm.

After preparing the simulation environment, we hope to implement tangent bug algorithm and simulate it in this environment with a robot that do not know anything about environment but its own location, location of the the goal. It has a range sensor with finite range limit, and it can move in any direction.

A Brief Introduction: Tangent Bug Algorithm

Tangent Bug Algorithm is different from the other bug algortihms, since there is a more advanced sensor, range sensor, used in order to obtain data about environment. Sensor gives range data for 360^o with discreet steps. It measures the range between the obstacles and itself and if there is no obstacle in range it returns the range limit as the distance data. Using this info data, robot finds the ending points of the obstacles where it can move freely.

Figure2: Ending points

Algorithm makes robot move towards the goal if there is no obstacle in the way. If there is obstacle it move around it (move towards the ending points). However, if the ending point is not a real ending point but sensed as one as a result of the limited range and if it is shortest distance then, it follow the boundries of the object until either it past the object (robot closer to the goal than the ending point of the object) or it come to the same point again. The latter one means that there is no solution for the problem.

A short description of the algorithm is given below:

While(true)

Repeat Motion-to-Goal

· Compute continuous range segments in view

· Move toward the point n Î [T, Qi] that minimizes the heuristic, d(x, n)+d(n, q_goal) until

o Goal is encountered. Or

o The value of d(x, n)+d(n, q_goal) begins to increase: Continue with boundary following

Repeat Boundary following

· Update O_i ,d_follow, and d_reach

· follow boundary continuing in same direction as before until

o Goal is reached

o A complete cycle is performed(goal is unreachable)

o d_reach <d_follow

end

Implementation and Results

Implementation of the algorithm is done on MATLAB platform (code can be seen from the link in the end). We implemented the algorithm as it is told on the previous sections. However, we divide the motion to goal to several cases. In first case, if there is no obstacle seen in the range, robot will control the nearby angles(for the safety of the path, it tries to make sure that path is larger than one point) and goes directly through the goal point. In the second case, if there are objects on the direct path through goal, we find endpoints and the minimum heuristic distance, and go towards the best end point. At this point, it controls whether it is close to the object more than a safety distance or not, and it tries to control the minimum distance to the object, and goes accordingly. We assume that, the distance between two obstacles will be more than 2 safety distance. There are some examples for one and two obstacle cases. Note that when the range changes, path also changes.

Figure 3a: Range 1 unit 1 obstacle (video) Figure 3b: Range 2 unit(video)

Figure 3c: Range 6 unit(video) Figure 3d: Range 1.5 unit(video)

In boundry following cases, it also use safety distance in the algorithm. It control the minimum distance to object and try to go outside of the danger zone at every step. The following examples are boundary following examples with different ranges.

Figure 4a: Range 0.5 unit(video) Figure 4b: Range 1.5 unit(video)

When the range increases, path can stay outside of the danger zone easily. Additionally, as it can be realised from examples, if there is sharp corners, implemanted algorithm may cause errors if the resolution of the sensor is not large enough.

Additionally, if there is no solution for the case, such as no endpoint but an obstacle, a full cycle in boundary following, algorithm will return no solution message.

Conclusion

Our main goals in this assignment are to understand bug algorithms and implemention of tangent bug algorithm so that we can understand the difficulties about implementation of these algorithms. In this assignment by using perfect environment and sensors we obtain deterministic paths, however in real life we use sensors with errors, thus, there is a need for decreasing the sensitivity of the system against sensor errors. Thus our implementation should consider these situations and needed to be developed. Additionally, this implemantion would have difficulties to cope with sharp edges.

References

· "Principles of Robot Motion" by Howie Choset etal., MIT Press, 2005, ISBN: 0-262-03327-5.

· "Planning Algorithms" by Steven M. LaValle, Cambridge University Press, 2006, ISBN: 0521862051

Resources