Stu Black
30 January, 2009
The effectiveness of deterministic and randomized versions of ricochet, a simple algorithm for escaping an enclosure, is tested with a blind SMURV robot. This algorithm, which utilizes only bump sensor data, enables the robot to escape from convex enclosures. It is compared with a random walk for effectiveness, measured by the time it takes to escape from an enclosure.
Enclosure escape is a relatively simple task that may be used to assess the usefulness of a movement control algorithm. For this project, we considered primarily the relatively limited task of escaping from a convex enclosure that contained no obstacles. While randomly walking within the enclosure should guarantee escape (and may enable escape within a very short time), a randomized wall-following algorithm provides a better expectation of escape time.
The specific enclosure configurations were that of an isosceles triangle and a rectangle, with exits placed at a vertex and along a side, respectively.
|
| The triangular enclosure, with its exit located at one vertex |
 |
| The rectangular enclosure, with its exit located along one long side. |
To provide a baseline, we built a random walk algorithm that changed the robot's heading by rotating it a random number of degrees in response to collisions.
Empirical evaluation showed this random walk approach to lead to unacceptably long escape times for the triangular enclosure. For such an enclosure, the random walk algorithm has a very low probability of escaping because the robot is increasingly likely to hit a wall and move away from the exit the closer that it gets to it.
The ricochet algorithm was developed from this random walk algorithm in an attempt to overcome this shortcoming by incorporating wall-following behavior.
When a SMURV using the ricochet algorithm encounters a wall, it adjusts its heading until it is approximately parallel to the wall, at which point it proceeds until it encounters the wall again. This is a strong wall-following behavior, and, because the algorithm is deterministic, it may fall into infinitely looping behavior. When the algorithm was originally formulated, we conjectured that randomness would be introduced by the robot platform because of uncontrollable issues such as wheel slippage and timer granularity. In actual practice, this proved not to be the case, and the algorithm was quickly shown not to be effective in the rectangular enclosure, where it easily fell into infinitely looping behavior. As such, a randomized version of the ricochet algorithm was developed.
The specific numeric parameters presented here were obtained by tweaking based on observation. It is probable that they are somewhat tuned to the shape and scale of the enclosure environments.
The performance of these algorithms was tested by placing a SMURV in the two enclosures shown above. In the triangular enclosure, the SMURV began in the center with heading towards one wall. In the rectangular enclosure, it was started in a corner facing the center of the enclosure. It should be noted that, because these settings were symmetrical, a great variety of start positions is not needed.
Results for the algorithms with varying parameters are shown below. A trial was considered successful if the robot escaped within 5 minutes.
A brief film clip of the deterministic algorithm navigating a modified rectangular enclosure may be seen here.
| Parameters | Trials | Successful trials | Average escape time (successful trials) |
|---|---|---|---|
| Deterministic | 2 | 0 | n/a |
| Rotation speed randomized in [15, 20] degrees/second | 1 | 0 | n/a |
| Rotation speed randomized in [15, 20] degrees/second, reverse speed randomized in [0.25, 0.5] | 1 | 0 | n/a |
| Rotation speed randomized in [5, 35] degrees/second, reverse speed randomized in [0.25, 0.5] | 1 | 1 | 257 seconds |
| Rotation speed randomized in [5, 35] degrees/second, reverse speed randomized in [0.25, 1.0] | 3 | 3 | 72 seconds |
The above results were obtained in tuning the parameters of the randomized ricochet algorithm to the rectangular enclosure. The random walk algorithm was not given timed trials in the enclosure, but it was able to make it out with a high degree of success in time comparable to that of the final version of the randomized ricochet algorithm.
| Trial | Escape time |
|---|---|
| 1 | Did not escape in 5 minutes |
| 2 | 85 seconds |
| 3 | 65 seconds |
| Average of successes | 75 seconds |
| Trial | Escape time |
|---|---|
| 1 | 26 seconds |
| 2 | 74 seconds |
| 3 | 160 seconds |
| Average of successes | 87 seconds |
It became clear during development that the random walk algorithm had a high chance of spending a long time in the triangular enclosure before escaping. This is consistent with the behavior of a random walk algorithm, as it may take an unbounded amount of time to escape.
The randomized ricochet algorithm, being randomized with restrictions, is guaranteed at least to perform wall-following to a minimal degree. While it may also take a theoretically unbounded amount of time to escape, the expected amount of time it takes to escape should be lower. This is supported by the above data, in which the random walk algorithm fails to escape in one trial.
The two classes of enclosure which we considered offer two very different challenges to the robot. As noted above, the triangular enclosure offers a disadvantageous configuration for the random walk. The rectangular enclosure offers a similar disadvantageous configuration for the ricochet algorithm, as its tendency to follow walls means that it will move right past an exit located in the middle of a long section of wall.
The ricochet algorithm was originally designed with these shortcomings in mind. Its "back off and reorient" behavior is designed to place the SMURV on a trajectory nearly parallel to a wall. This makes it easy to trace the perimeter of an enclosure, but it makes it nearly impossible for a robot using the deterministic version of the algorithm to navigate through an exit along a wall.
The bug algorithm, described in class, presents a slightly different implementation of wall-following from the ricochet algorithm. Its use of curved path segments avoids the problem of missing an exit on a long wall, but it also introduces two pitfalls.
The first is that, without some sort of localization, the robot will trace a circle if the curvature of its path segments is sufficiently small that it does not collide with a wall before it drives in a complete circle. Secondly, if there are any internal walls not intersecting with an external wall (i.e., an obstacle in the enclosure), the robot may end up following the perimeter of the obstacle instead of the perimeter of the enclosure. The ricochet algorithm was so named because a robot using it will "ricochet" off of any obstacles and so try to find a true perimeter wall.
The random walk algorithm has a hard time with certain classes of enclosure. The ricochet algorithm has a hard time with a different class of enclosure. Incorporating randomness into the ricochet algorithm results in acceptable performance in both classes of enclosure. Furthermore, the randomized wall-following algorithm proved itself quite competitive with the simple random walk algorithm in both classes of enclosure.
Further comparison of randomized and deterministic enclosure escape algorithms is warranted. Rigorous theoretical analysis of the randomized ricochet algorithm and comparison with a randomized bug algorithm would be helpful in establishing whether one approach (straight-line wall-following or curved-path wall-following) is more useful in smaller enclosures.
Expansion of project focus to include more trials in more classes of enclosures would provide more meaningful data for comparison and analysis of the algorithms. The data presented here are not statistically meaningful.
Source code for the project should accompany this file.