Revision as of 23:07, 6 February 2012 (view source) Dlaw (Talk | contribs) (→Effectiveness) ← Older edit		Revision as of 08:20, 7 February 2012 (view source) Jhurwitz (Talk | contribs) Newer edit →
Line 57:		Line 57:
	== Navigation code ==		== Navigation code ==
−	Coming soon	+	The basic idea of our navigation code is very simple: If the robot sees a red ball, it should try to possess it. If the robot sees no red balls, it should find a wall and follow it until another red ball appears in sight. Near the end of the game, find the yellow wall and approach it. Then, just before the 180 seconds are up, dump all possessed balls and then turn off all motors.
		+
		+	We originally started with closed loop control, so the code would issue commands such as "Drive 22 inches to reach the ball." However, we had issues with this at the Arduino level and eventually had to switch to open loop control. With open loop control, our commands look more like "The ball is far in front of us, so drive forward quickly."
		+
		+	We figured the best model for navigation would be to send a command to the motors every time we process a new frame from the Kinect. To accomplish this, we wrote a state machine that combines the current state of the robot with sensory inputs to obtain an action (such as drive commands to the motors) and a state transition.
		+
		+	However, from a given state, there should be multiple valid transitions. For example, pretend the robot has a ball in sight and is driving towards it. The typical transition edge should be to stay in the "drive to ball" state, but if a front bump sensor is triggered, the robot is probably stuck on a pillar so it should instead transition to a state that tries to free the robot by backing up.
		+
		+	So, before transitioning states, we first check if the robot is stuck. If it's not, we then (if the time is right) check to see if the yellow wall is in sight. Continuing on, we next check if the robot can see any red balls. And then, if none of those apply, the robot takes the default transition edge. This approach seemed risky because it means that seeing red for just a single frame can dramatically alter the state of the robot, but our vision code was robust enough that this proved to be a non-issue.
		+
		+	What was an issue, though, is that there are still other ways to get stuck in a state. If for some reason the robot catches on a pillar without triggering an IR or bump sensor, it could stay in the "drive to ball" state indefinitely! To prevent this, we set a timeout for each state.
		+
		+	Here's a high-level overview of the states from our state machine, with descriptions of all default transition edges plus a few other important edges.
		+
		+	=== States ===
		+
		+	*''LookAround'' – Rotate the robot in place, looking for (if applicable) red balls or yellow walls. After a couple of seconds (which we timed to be just longer than a full revolution), enter GoToWall.
		+
		+	*''GoToWall'' – Drive until the robot hits a wall, and then enter FollowWall.
		+
		+	*''FollowWall'' – Using a PDD controller, maintain a constant distance between the right side of the robot and the wall (as measured by an IR sensor). Periodically enter LookAway to look for red balls or yellow walls. (It's worth noting that we made our code very flexible so we could, for instance, override stick detection in FollowWall mode to ignore the right bump sensor; without this modification, we ended up accidentally triggering stick detection at every inside corner.)
		+
		+	*''LookAway'' – Turn away from the wall by half a revolution (as determined by IR) and then turn back. If applicable, look for red balls or yellow walls while turning away. Then return to FollowWall.
		+
		+	*''GoToBall'' – Using a P controller to keep the ball centered, drive towards a ball. When the ball is sufficiently high in the image (meaning the robot is close to it), enter SnarfBall.
		+
		+	*''SnarfBall'' – Drive forward (with the front roller on) in an attempt to pick up a ball.
		+
		+	*''DriveBlind'' – The idea behind this state is that we don't want to enter LookAround if we lose a ball for a single frame. When the robot is in GoToBall and loses the ball, it will enter DriveBlind and keep driving for a couple of frames before giving up.
		+
		+	*''GoToYellow'' – Using a P controller to keep the yellow wall centered, drive towards it. When the wall is close enough (measured by both front IRs reading a small distance, and the yellow blob in the camera being sufficiently large), enter DumpBalls.
		+
		+	*''DumpBalls'' – This is a slight misnomer because it doesn't actually dump. Instead, this state either proceeds to ConfirmLinedUp (if the robot isn't happy about where the yellow is) or WaitInSilence (if the robot is).
		+
		+	*''ConfirmLinedUp'' – Back up a bit, then try GoToYellow again.
		+
		+	*''WaitInSilence'' – Turn off everything (mainly to save battery power, but it has the side effect of suspensefully appearing as if our robot has died) and wait until 3 seconds before endgame, then HappyDance.
		+
		+	*''HappyDance'' – Turn on the roller on the third level, and rapidly shake side-to-side to eject all the balls.
		+
		+	*''Unstick'' – Figure out which IR or bump sensor indicates that the robot is stuck, and then move in the opposite direction (plus some random angle offset) in an attempt to unstick.
		+
		+	*''HerpDerp'' – Drive backwards in a random S-shaped curve.
		+
		+	=== Other details ===
		+
		+	To explain language like "If applicable, look for red balls or yellow walls," we need to dip a little into our robot's strategy. At the beginning, the robot should look for red balls and should ignore yellow walls. When there are 100 seconds to go, a flag is raised and the robot starts looking for yellow walls. If it sees a yellow wall, it reacts by "stalking" the wall. This means that the robot will still go for balls, but it will not follow walls out of fear of losing the yellow wall. (If however going for balls accidentally causes the robot to lose sight of yellow, it will temporarily ignore red balls and re-enable wall following until it finds yellow again.) Then, when there are only 30 seconds to go, the robot stops looking for red balls and focuses exclusively on approaching the yellow wall.
		+
		+	The theory behind the yellow stalking is that, while 30 seconds should be enough to find yellow no matter where the robot is, it's just a good idea not to lose sight of yellow just in case the robot gets stuck elsewhere on the field. We'd be happier dumping the balls already collected than spending more time picking up a few more. In practice, this also worked to our advantage because it meant that we were in a prime position to scoop up and return balls dumped by our opponent near the yellow wall. (We were the only team with the strategy of holding onto balls until the very end.)
		+
		+	One failure mode we noticed in our design was that, if a ball wedged itself into an inaccessible corner, we might spend arbitrarily long trying to snarf it. A timeout in a single state would not help because, in this example, the robot continually transitions between Unstick and GoToBall. To prevent this, we incremented a counter each time we entered Unstick and would temporarily ignore balls when this counter exceeded a given threshold. (Successfully snarfing a ball, as measured by the sensor on our third level, would reset the counter.)
		+
		+	That's about the entirety of our code, in a nutshell. There are a few other minor details (for example, we disabled our helix if we detected that the third level was full, and we pulsed the helix every couple of seconds to keep it from jamming), but those were mainly specific to the robot we built. In terms of applying a strategy to robots in general, the state machine architecture described above is probably more helpful.

---

Revision as of 08:20, 7 February 2012

Team pleit! competed in Maslab 2012 and won first place.

Contents 1 Robot 1.1 Mechanical design 1.2 Electrical concerns 1.3 Arduino functionality 1.4 Vision code 1.4.1 Design 1.4.2 Implementation 1.4.3 Performance 1.4.4 Effectiveness 1.5 Navigation code 1.5.1 States 1.5.2 Other details

Robot

Mechanical design

Coming soon

Electrical concerns

Coming soon

Arduino functionality

Coming soon

Vision code

The key to our successful vision code was its simplicity. As computer vision problems go, Maslab is on the easier side -- field elements are colored specifically to help robots detect them. In particular, red and yellow are very distinctive colors and easy for a computer to identify.

Design

The 640-by-480 color image from our Kinect was downsampled to 160-by-120. In order to minimize noise, we downsampled using area averaging rather than nearest-neighbor interpolation. The 160-by-120 image was then converted to the HSV color space in order to facilitate processing using distinct hue and lumosity information.

Pixels in the HSV image were then classified as red, yellow, or other. We found that the best metric for color recognition was distance in HSV space (sum of squares of component errors) rather than hue threshholding.

Flood fill was then used to identify all connected components of each color. For each connected component, we computed the average and variance of all x coordinates, the average and variance of all y coordinates, and the total number of pixels.

When navigating to a ball, we simply used the coordinates of the largest red blob in the frame. Similary, when navigating to a wall, we simply used the coordinates of the largest yellow blob in the frame. We did not attempt to track changes in the location of objects from frame to frame -- we just used the largest object in each frame.

We used a simple proportional controller to drive to target objects using vision data. This was necessary because our drive motors used open-loop control.

Implementation

The bulk of our vision code was written in pure Python, with the most CPU-intensive parts compiled using Cython. We had fewer than 200 lines of vision code overall. The image resizing and color space conversion used OpenCV, but all other code (including flood fill) was custom.

We wrote a GUI app with sliders to set color detection constants that displayed an image showing objects that had been recognized. We anticipated adjusting these constants before every match -- however, our color detection proved robust enough that we did not adjust color paramters at all after the second week.

We also wrote a speed tester that automatically profiled the code to help us find and eliminate bottlenecks.

Performance

The first iteration of our vision code ran at 10 frames per second. Using the Python profiler to determine which statements were bottlenecks, we increased it to 100 frames per second by the second week. Since the camera only provided 30 frames per second, we had plenty of time between frames to do other processing. This eliminated the need to use multiple threads of execution.

The most expensive part of our vision code was downsampling the .3 megapixel image to .01 megapixels. After that, everything else was very quick.

From a programming standpoint, it was very convenient to do everything in a single thread: get image, process image, update state machine, send new drive commands, and repeat.

Effectiveness

Our vision code was extremely effective at detecting red and yellow objects. We had very few false negatives and no false positives. Green detection was easy as well, but we got rid of it since we didn't use green object information at all. It was difficult to distinguish the carpet, blue tops of walls, and white walls.

Rather than implementing blue line filtering, we mounted our camera so that the top of its field of view was perfectly horizontal and 5 inches above the floor. It was physically unable to see over walls. In this configuration, it was not necessary to identify blue or white.

We were one of the teams using a Kinect for vision. We did not end up using the depth data at all, since it was only reliable for objects two feet or more from the robot. However, we still feel that it was advantageous to use the Kinect, since its regular camera (designed for video games) had better color and white balance properties than the cheap Logitech webcam.

Navigation code

The basic idea of our navigation code is very simple: If the robot sees a red ball, it should try to possess it. If the robot sees no red balls, it should find a wall and follow it until another red ball appears in sight. Near the end of the game, find the yellow wall and approach it. Then, just before the 180 seconds are up, dump all possessed balls and then turn off all motors.

We originally started with closed loop control, so the code would issue commands such as "Drive 22 inches to reach the ball." However, we had issues with this at the Arduino level and eventually had to switch to open loop control. With open loop control, our commands look more like "The ball is far in front of us, so drive forward quickly."

We figured the best model for navigation would be to send a command to the motors every time we process a new frame from the Kinect. To accomplish this, we wrote a state machine that combines the current state of the robot with sensory inputs to obtain an action (such as drive commands to the motors) and a state transition.

However, from a given state, there should be multiple valid transitions. For example, pretend the robot has a ball in sight and is driving towards it. The typical transition edge should be to stay in the "drive to ball" state, but if a front bump sensor is triggered, the robot is probably stuck on a pillar so it should instead transition to a state that tries to free the robot by backing up.

So, before transitioning states, we first check if the robot is stuck. If it's not, we then (if the time is right) check to see if the yellow wall is in sight. Continuing on, we next check if the robot can see any red balls. And then, if none of those apply, the robot takes the default transition edge. This approach seemed risky because it means that seeing red for just a single frame can dramatically alter the state of the robot, but our vision code was robust enough that this proved to be a non-issue.

What was an issue, though, is that there are still other ways to get stuck in a state. If for some reason the robot catches on a pillar without triggering an IR or bump sensor, it could stay in the "drive to ball" state indefinitely! To prevent this, we set a timeout for each state.

Here's a high-level overview of the states from our state machine, with descriptions of all default transition edges plus a few other important edges.

States

• LookAround – Rotate the robot in place, looking for (if applicable) red balls or yellow walls. After a couple of seconds (which we timed to be just longer than a full revolution), enter GoToWall.

• GoToWall – Drive until the robot hits a wall, and then enter FollowWall.

• FollowWall – Using a PDD controller, maintain a constant distance between the right side of the robot and the wall (as measured by an IR sensor). Periodically enter LookAway to look for red balls or yellow walls. (It's worth noting that we made our code very flexible so we could, for instance, override stick detection in FollowWall mode to ignore the right bump sensor; without this modification, we ended up accidentally triggering stick detection at every inside corner.)

• LookAway – Turn away from the wall by half a revolution (as determined by IR) and then turn back. If applicable, look for red balls or yellow walls while turning away. Then return to FollowWall.

• GoToBall – Using a P controller to keep the ball centered, drive towards a ball. When the ball is sufficiently high in the image (meaning the robot is close to it), enter SnarfBall.

• SnarfBall – Drive forward (with the front roller on) in an attempt to pick up a ball.

• DriveBlind – The idea behind this state is that we don't want to enter LookAround if we lose a ball for a single frame. When the robot is in GoToBall and loses the ball, it will enter DriveBlind and keep driving for a couple of frames before giving up.

• GoToYellow – Using a P controller to keep the yellow wall centered, drive towards it. When the wall is close enough (measured by both front IRs reading a small distance, and the yellow blob in the camera being sufficiently large), enter DumpBalls.

• DumpBalls – This is a slight misnomer because it doesn't actually dump. Instead, this state either proceeds to ConfirmLinedUp (if the robot isn't happy about where the yellow is) or WaitInSilence (if the robot is).

• ConfirmLinedUp – Back up a bit, then try GoToYellow again.

• WaitInSilence – Turn off everything (mainly to save battery power, but it has the side effect of suspensefully appearing as if our robot has died) and wait until 3 seconds before endgame, then HappyDance.

• HappyDance – Turn on the roller on the third level, and rapidly shake side-to-side to eject all the balls.

• Unstick – Figure out which IR or bump sensor indicates that the robot is stuck, and then move in the opposite direction (plus some random angle offset) in an attempt to unstick.

• HerpDerp – Drive backwards in a random S-shaped curve.

Other details

To explain language like "If applicable, look for red balls or yellow walls," we need to dip a little into our robot's strategy. At the beginning, the robot should look for red balls and should ignore yellow walls. When there are 100 seconds to go, a flag is raised and the robot starts looking for yellow walls. If it sees a yellow wall, it reacts by "stalking" the wall. This means that the robot will still go for balls, but it will not follow walls out of fear of losing the yellow wall. (If however going for balls accidentally causes the robot to lose sight of yellow, it will temporarily ignore red balls and re-enable wall following until it finds yellow again.) Then, when there are only 30 seconds to go, the robot stops looking for red balls and focuses exclusively on approaching the yellow wall.

The theory behind the yellow stalking is that, while 30 seconds should be enough to find yellow no matter where the robot is, it's just a good idea not to lose sight of yellow just in case the robot gets stuck elsewhere on the field. We'd be happier dumping the balls already collected than spending more time picking up a few more. In practice, this also worked to our advantage because it meant that we were in a prime position to scoop up and return balls dumped by our opponent near the yellow wall. (We were the only team with the strategy of holding onto balls until the very end.)

One failure mode we noticed in our design was that, if a ball wedged itself into an inaccessible corner, we might spend arbitrarily long trying to snarf it. A timeout in a single state would not help because, in this example, the robot continually transitions between Unstick and GoToBall. To prevent this, we incremented a counter each time we entered Unstick and would temporarily ignore balls when this counter exceeded a given threshold. (Successfully snarfing a ball, as measured by the sensor on our third level, would reset the counter.)

That's about the entirety of our code, in a nutshell. There are a few other minor details (for example, we disabled our helix if we detected that the third level was full, and we pulsed the helix every couple of seconds to keep it from jamming), but those were mainly specific to the robot we built. In terms of applying a strategy to robots in general, the state machine architecture described above is probably more helpful.