Assignment 1 - Enclosure Escape

Hefty

Ben Cohen (btcohen)

Introduction and Problem Statement

For this assignment we were instructed to program our robot to escape from an enclosed area using only the bump sensor. To put this in a human context, it's like trying to get out of a maze with a blindfold on; you can't see where you're going, and the only way to gather information is to walk into the walls. Trying to program a robot to escape from an enclosed space is hard enough, but trying to do it with only a bump sensor is a real challenge!

Approach and Methods

We initially programmed our robot to do a random walk of the enclosure until it escaped. Although it eventually made it out most of the time, we felt we could program a faster, more reliable algorithm. We ended up making Hefty follow the walls of the enclosure to freedom. Here's how our algorithm works:

	Hefty starts out in the enclosure.		He drives, curving until he hits the wall.
	He then rotates away from the wall....		...and then drives until he hits the wall again.

This algorithm is fairly simple, but it works quite well. To prevent Hefty from driving in a circle, the algorithm keeps track of how long its been since he last bumped into something. If Hefty goes for a long period of time without hitting something, then he must be driving in a circle (since he turns as he drives); in this case, he then starts driving straight until he hits a wall. He then resets his counter and begins following walls normally. Here's the algorithm in pseudocode:

while(true){
	if(bumper.hit){ 
		counter = 0;
		setVelocity(0,rotate);
	} else if(counter>COUNTER_MAX) {
		setVelocity(forward,0);
	} else {
		setVelocity(forward,rotate);
	}
	counter++;
}

Given the pseudocode above, this algorithm should be fairly easy for anyone to reproduce.

Experiments and Results

We tested Hefty in a variety of enclosures and got very good results. The images below show a simple enclosure we used for testing and the path Hefty took to escape it:

While Hefty did not take the fastest possible path out of the enclosure, his path is still shorter than a random algorithm would take in most cases. Additionally, it is much more consistent; if you start Hefty in the same location, you're guaranteed that he'll escape in almost exactly the same amount of time (this makes our results very reproducible).

Here's a video of Hefty escaping from a simple enclosure:

To test Hefty, we created a number of enclosures. He escaped all but one of them (more on that later). We also tested him in real-world enclosures, placing him in the middle of the floor in 404; he found his way to the wall and followed it to the door.

In addition to testing him in different enclosures, we tested him multiple times in the same enclosure, varying his starting position and rotation; he preformed very similarly for the various starting conditions, escaping in roughly the same time.

We were able to create one enclosure that did trap Hefty:

In this enclosure, Hefty was unable to turn sharply enough to make it out and as a result, he cycled indefinitely:

Except for this test, Hefty escaped the enclosures we created very rapidly (usually taking between 15 seconds to 1 minute).

Conclusion and Discussion

Overall, I think our algorithm worked very well. Hefty is able to escape from a wide range of enclosures and does so in a reasonable amount of time (especially compared to a random algorithm). However, unlike the random walk algorithm, which will always find a way to escape the enclosure (given an infinite amount of time), Hefty's algorithm can occasionally get him stuck. In addition to the example in the section above, certain other enclosures could get Hefty stuck retracing his steps forever. For example:
In the enclosure above, were Hefty to bump into one of the circles, he would follow it forever and never escape. One major improvement to our algorithm would be the ability to tell when something like this had occurred and break away.