Enclosure Escape using Randomized Wall-Following

Alexander Korzec <akorzec@cs.brown.edu>
Brown University

Abstract:

A program designed to enable the SmURV to escape an enclosure was written in order to become familiar with the implementation of the robot control loop and learn how to use feedback from the bumper proxies to generate useful information. It was observed that wall-following with randomized arc sizes created a more intelligent, more elegant, and usually more efficient solution than either a simple object avoidance (via backing up, turning, and moving forward) algorithm or a corner escape with curving algorithm.

INTRODUCTION

The problem presented was to design a controller that enabled the SmURV to escape from an enclosure it had no previous data about, and using only input from its bump sensors. The problem is interesting for several reasons, the first of which is the suggestion of reactive control. The level at which the robots are being programmed, along with the difficulty of the problem, hint that not very much information should be stored by the robot. The controller should react to events as they occur, with no past record of events.

The most interesting aspect of this problem is achieving the balance between randomness and intelligence that makes any possible enclosure not only possible but feasible. For example, an algorithm that moves the robot forward until it hits a wall, rotates a random amount, then repeats, will eventually escape any enclosure. Chances are the robot will make it out of the enclosure eventually but not very intelligently. At the same time, some randomness is required to enable a robot to escape any enclosure. If all the movement values are precomputed, then it is possible to design an enclosure to cause the program to enter a loop that it can't escape from.

APPROACH

Initially, the group had two different approaches. The first was an object avoidance system which, when a bumper was triggered, would back up, turn a random, but bounded, amount to face away from the obstacle, then proceed forward. If both bumpers were hit, it would back up, turn in the direction it had previously turned (or sometimes randomize direction), and proceed. This approach yielded fairly predictable, but not always elegant and not always intelligent results. The robot would frequently get in to a corner and take undesirably long to escape.

In the second approach, when the robot's bumper was triggered, it would stand still, then rotate until the bumper was no longer pressed, then continue with a slight, randomly directed arc. The results were promising and consistent in long hallway cases, but problematic in small box enclosures.

Eventually we were able to adapt the second method into a wall-following method. It was equipped it with steeper rotation values to arc it back into the wall, as well as a deterministic/planned, rather than random curve direction after a collision. If the left bumper is pressed, the robot will rotate to the right until it is released, then proceed forward and to the left (in a curve) until another wall is hit. If the wall following pattern is interrupted by an unexpected hit on the other bumper, the SmURV will continue along the new wall. A tapering factor was added that gradually tapers the arc of the curve to prevent circling in a large enclosure; the longer the robot travels without hitting a wall, the straighter it's path becomes. This was implemented by decreasing the rotation value slightly each time through the while loop. This setup could be easily replicated, and possibly even improved upon, as it is very few lines of code. The results were consistent (except for one outlier), and the robot's approach was the most intelligent and methodical of all three, as shown in videos 1.1-1.4, which can be viewed in the handin folder (they were too large to post on youtube).

Video 1.1 - SmallEscape.MP4

Video 1.2 - LargeEscape.MP4

Video 1.3 - CorridorEscape.MP4

Video 1.4 - BabysDayOut.MP4 (this one features Baby doing a little exploring on large scale enclosures)

EVALUATION

Diagrams 1.5-1.7 give a rough sense of the enclosure presented. In addition, though not recorded here, were more difficult enclosure tests, which Baby was able to pass using approach 3. In all tests, the elements held constant were the shape of the enclosure and the starting position and orientation of the robot. The variables were the randomness generated within the program, and any physical, real-world discrepancies. Given the consistency of most of our results and the methodical approach of the robot, these results are easily reproduced.

Diagram 1.5 - Small Box

_______________
|............................|
|............................|
|____.........._____|

Diagram 1.6 - Large Box

___________________________
|....................................................|
|....................................................|
|__________..........___________|

Diagram 1.7 - Narrow Corridor

__________________________
|....................................................
|__________________________

Approach 1, object avoidance via backing up, yielded the following results (Tables 1.5-1.7).

Table 1.5 - Small Box with Baby using approach 1 pointed into top left corner

Table 1.6 - Small Box with Baby using approach 1 pointed at back wall

Table 1.7: Long corridor with Baby using approach 1 pointed at side wall

Approach 2, rotating until bumpers were released and proceeding with a random, slight forward curve, produced these results (Tables 1.8-1.9)

Table 1.8: Long corridor with Baby using approach 2 pointed at side wall

Table 1.9: Small box with Baby using approach 2 pointed into top left corner

The final, integrated approach 3, wall-following with randomized arc lengths and tapering, produced the following results (Tables 1-1.0-1.12).

Table 1.10: Long corridor with Baby using approach 3 pointed at side wall

Table 1.11: Small Box with Baby using approach 3 pointed into top left corner

Table 1.12: Large Box with Baby using approach 3 pointed into bottom right corner

Trial 3 of Table 1.12 occurred when the Baby happened to pick its largest possible random arc when it was closest to the exit and needed a smaller arc - twice in a row. This demonstrates how the randomness, while ensuring an exit, can sometimes lead to a long one.

DISCUSSION

The strengths of our final approach is that it is methodical, yet random enough to not get trapped in cycles. It ensures relatively predictable behavior and handles even the most paranoid cases well. The only shortcomings is that perhaps our arc lengths in the wall-following process aren't as finely tuned as they could be. We may be wasting time with smaller arc, and missing important exits with the longer arc. But the randomness assures that we will get there eventually.

CONCLUSION
In conclusion, there are several possible ways to solve the enclosure escape problem, each with its own advantages and disadvantages. Though conservative at times, and occasionally unlucky, the wall-following method has proved to be the most consistent and reliable approach over a variety of different test situations.