Assignment 1: Enclosure Escape

CS148

Erich C. Deise (edeise)

Introduction:

The task given by assignment 1 was to create a Player controller capable of directing a SmURV robot to reactively respond to obstacles in its path. Specifically, we are given the task of constructing a control program that results in the SmURV escaping from enclosures of arbitrary geometric configurations utilizing only information provided by bumper-sensors. We conjecture that by implementing a very simple nondeterministic reactive control structures that the Smurv will be capable of negotiating (I.e., escaping from) most continuous enclosed spaces.

Approach and Methods:

Our general approach was to investigate three enclosure-escape algorithms – random walk, simple (deterministic) wall-following and simple randomized (nondeterministic) wall-following.

Random walk is implemented as a finite state machine in which the controller directs the SmURV to enter an initial forward state. The robots proceeds linearly until its bumper sensor is activated at which time it transitions to a second state whereby the SmURV reverses for a set amount of time. Once there, it transitions to a third state in which it rotates unidirectionally for a random amount of time. Once complete the initial state is revisited.

The second algorithm considered was a simple deterministic wall – following procedure. Implemented as a finite state machine the controller directs the SmURV to enter an initial – forward – state. Once a bumper strike is recorded the machine transitions to second state whereby the robot reverses for a fixed amount of time and speed. Once complete the third state iss invoked in which the SmURV is directed to undertake a simple 20 degree (left) turn and revisit the initial state.

Third, we considered a simple randomized (nondeterministic) reactive wall-following procedure. (Simple algorithms very similar to this are known to result in success when exploited in continuous mazes.) Implemented as a finite state machine, the controller directs the SmURV to enter an initial state with the result that it proceeds straight ahead until a bumper strike is recorded. Once the bumper is depressed the robot is transitioned into a new state and directed to reverse for a random amount of time at a set linear velocity. Once clear of the immediate obstacle, the SmURV is transitioned into a third state resulting in its undertaking a unidirectional turn (left) at set rotational speed for a random amount of time. This effectively results in the SmURV rotating at a randomly selected angle between 5 and 35 degrees. Once completed, the initial state whereby the robot is directed to proceed straight (until a bumper strike is registered) is revisited. By limiting the angle of rotation undertaken in response to each strike the robot (through iterative application of the control procedure) comes to (re)orient itself – eventually becoming (approximately) parallel to any wall that it strikes. This results in the SmURV engaging in a simple wall-following-type behavior. Given the simplicity and genericity of the algorithms outlined here, there is no reason to think any of them to be un-reproducible.

Experiments and Results:

Since the player/stage simulation environment disallows direct testing of bumper-sensor driven reactive systems, all testing was performed on actual SmURV robots. In order to test our conjecture, two test environments were constructed and the SmURV's elapsed time to escape was recorded. In condition 1, we tested the SmURV in the simple rectangular enclosure space shown below.

In Condition 2, an approximation of an isosceles triangle was constructed as depicted below.

It should be noted that the set of conditions considered is by no means exhaustive. Specifically, no enclosure spaces with internal convex corners were methodically examined.

Results:

Deterministic wall-follow

Five trials of the deterministic algorithm (go straight, backup, turn left 20 degrees, go straight) were undertaken by the SmURV in a rectangular enclosure. Following this deterministic procedure the robot failed to escape the enclosure in under 5 minutes in every trial – our operationalized failure condition. Clearly, success of this algorithm is tied directly to the particular geometry of the enclosure space.

Non-deterministic wall-follow

With the aim of increasing the SmURV's rate of success, randomness was injected into the simple deterministic procedure. So doing allowed for randomized variation in both the reverse velocity and rotational angles undertaken in states two and three respectively. So doing allowed for variation in both how far the SmURV reversed following a bumper strike and how much it turned. When tested in the same rectangular environment, this addition yielded significant improvement. Table 2 presents the results for the Randomized wall-following algorithm investigated.

Table 2. Randomized wall following

We then tested the nondeterministic wall following algorithm in a triangular shaped enclosure (an approximation of an isosceles triangle with the exit located at the corner with the narrowest angle as depicted above. To determine if the randomized wall-following algorithm could be relied upon to perform at better than chance levels, the random-walk algorithm was selected as a suitable control condition. Elapsed time required for the random-walk controlled SmURV to negotiate the enclosure were taken as the base for comparison. See table 3.a and 3.b for results.

Tables 3.a and 3.b present the results for the random-walk and randomized wall-following algorithms in the triangular enclosure space respectively.

Table 3.a Random walk

Table 3.b Randomized wall-following

Since no modifications were made to the iRobot plant nor the mini-ITX ( C.f. http://robotics.cs.brown.edu/projects/smurv for specifications and details of the SmURV platform) and the control procedures is reproducible, there is no reason to think that an identically constructed SmURV should behave any differently. We expect then similar results to be reproducible.

Discussion:

Our conjecture that nondeterministic (I.e.,randomized) walk and nondeterministic/randomized wall-following procedures should out-perform the deterministic algorithm appear to be supported. Both nondeterministic procedures were able to escape from enclosures of varied geometries – unlike the deterministic algorithm the success condition of which were tied inextricably to the shape of the enclosure and the SmURV's initial starting position.

We next considered two nondeterministic algorithms for contending with the enclosure escape space: random walk and randomized wall-following. While our data sample is insufficient to support any particular claim, it would appear that while random walk is faster in two of three trials, it fails to escape (in under five minutes) in the third. Exactly what this might mean, given the dearth of data, is unclear. Randomized wall-following, while slower than random walk (on those trials in which success was achieved) did succeed in escaping the enclosure in all trials. And so, we cautiously suggest that while randomized wall-following is slower it also a more robust strategy. In addition to the need to increase the sample size (sample size is inadequate for any meaningful statistical inferences to be drawn), additional findings are needed with regard to the elapsed escape time exhibited by the random-walk procedure when tested in the rectangular enclosure space.

The simple nondeterministic wall-following algorithm outlined here has a number of benefits over the simple deterministic version and the random-walk procedure. Specifically, unlike its deterministic predecessor, the nondeterministic version does not become trapped in fruitless looping behaviors on geometrically simple enclosures spaces. Compared to the random-walk algorithm, nondeterministic wall-following is, as discussed, a more robust (but potentially slower) approach. There are, however, several weakness inherent in this approach. Specifically, there are a number of (obvious) test conditions that will result in failure. The following is not intended to be an exhaustive listing but rather a representative set of geometries that will likely result in the SmURV's failure to negotiate an escape.

1. If the exit lies along a wall, there is a chance, given that the algorithm is designed to implement wall-following behavior, that the robot will simply repeatedly miss the exit if it succeeds in orienting itself parallel to the wall.

2. Chevron-shaped enclosures (e.g., V ) present a challenge for the current controller as well. Specifically, since the current design has the SmURV making only left turns and then proceeding forward linearly, there is a chance (depending upon the robots initial starting location) of it never reaching the exit. Rather, it may enter into a fruitless left directed wall-following loop that (effectively) ignores half of the “V” shaped enclosure space.

Seemingly both of these difficulties might be contended with by having the SmURV enter into an arc-ing forward state (as opposed to the initial state in which forward motion is linear). This would allow the robot to overcome the internal concave angle of the chevron – opening up the remainder of the enclosure space for exploration. So doing would also remove the possibility of the robot becoming (and remaining) parallel to the wall. Rather, by engaging in the arc-ing “bug-algorithm” behavior discussed, exits located along walls are discoverable.

The addition of the arc-ing behavior however does raise the problem of how to contend with discrete objects located within the enclosure space. That is, following this hypothesized variant, it would be possible for the robot to simply continuously “circle” an object located in the middle of the enclosure space – thus never finding the exit. Interestingly, the simple wall-following algorithm examined above (both deterministic and nondeterministic variants) by failing to arc, should contend well with this particular enclosure space problem instance.

Conclusion:

With the aim of constructing an automated enclosure escape controller for the SmURV, we considered three simple algorithms: random walk, deterministic wall-following and nondeterministic wall-following. We found that deterministic wall – following was a poor procedure for navigating enclosure spaces, resulting in failure in all but the most contrived environments. The random-walk and nondeterministic wall-following algorithms, it was found, fared much better. The data were insufficient for any claims to be supported with respect to the superiority of either of these however. Finally, a set of problems raised by our particular implementation of the simple nondeterministic wall following algorithm were considered and an avenue for further research considered.