CSE 430W


Return Home

Last updated: 9/20/07 (power supply typo; an extra Tip on the cabinets)

Courtesy Bash.org:

<Patrician|Away> what does your robot do, sam
<bovril> it collects data about the surrounding environment, then discards it and drives into walls

This webpage will be dedicated to the collective knowledge I have gained in CSE 430W while attending Pennsylvania State University. This is intended as a supplement to those students who will be taking CSE 430W during their academic career. Essentially, it’s my hope to instill some of the knowledge I now have that I wished I would have known at the beginning of the semester.

Since Dr. Dunn often changes the goals of the project, I will first describe our problem. I will then dive into the more fundamental issues that are likely to appear on any future project. I will go into depth on movement and chassis of the robot, our special task, the sensors available, the issues of power, some tips on software development, and finally some overall tips for the course. Through this discussion I will interject the decisions we made, what other groups made, and the ones we wish we would have made.

If further information is desired on any topic discussed here, please first use Google as there is a wealth of information on robotics on the Internet. Otherwise, feel free to email me at brain.recall@gmail.com

Please, share this page with any poor soul you know of that is taking, or is planning to take CSE430W.

Our Problem

Our project required our robot to knock over four dominos on a game board. The game board was arranged into a grid of 8x8 cells, each 12” square. There are clear paths to three of the four dominos, with the fourth having two possible paths: moving a softball out of one cell or knocking over the domino through the hole. There is a red domino that once knocked over ends the game, so it must be avoided until last. The robot must operate independently and carry its own power. It cannot mark or damage the board, and climbing or knocking over walls in the game board is forbidden. You start the robot in an unknown location facing an unknown direction. Up to three walls can be changed. You have to use the supplied Technological Arts Adapt9S12DP256M1 microcontroller. There was a game time limit of 15 minutes. The budget was $250. You could order new parts that would be placed by the University, or you could use parts already in the lab. Your budget report needs to include the cost value of any parts that were not purchased but were used on the robot (and also parts that were purchased but not used). There is usually a discount for using in-lab parts, but I am unsure as to how much. Your group is also given a laptop for development (using a full version of ICC12) and programming (through a serial port).

Chassis

Movement around the game board is first dependant on the platform you are using. We used the ScooterBot II chassis from Budget Robotics. One of our first robot designs can be seen below:

This design allows for in-place turns, and a fairly small profile. Overall through our use, we found the design to be fair. The deck system worked pretty well for us, although we did need to expand from the two decks to three decks very quickly, with the final design requiring four decks.

Minor modifications had to be made to the chassis. The slots around the wheels were widened to allow for instances where dominoes could jump up and bind the wheels when a domino was run over. Also, we cut a section and epoxied two extrusions for the break beam. The deck with the arm required a slot and hole to be added. The decks themselves are made from extruded PVC, so they are both light and easy to modify. Other groups required extensive modification to their platforms (such as to make room for the softball, more on that later).

The motors included with the kit are trash, which I will explain shortly. The wheels are not very well manufactured, so they are slightly uneven through their rotation. We managed to get by with them and didn’t have many problems, but other teams removed an O-ring from the wheels to provide some better, more stable traction. One team did not use this chassis, and opted for a treaded tank robot. This design we seen nearly eliminates loss of traction on the game board (the board is old and in not so great condition), although it is extremely slow and rather rough during travel.

Movement

There are two primary modes of transportation used through the years: servo motors and stepper motors.

Servos

Servo motors are essentially highly controlled DC motors. They require a control signal, usually a train of 1.5ms duty-cycle pulses at about 50Hz. They come in two flavors, unmodified and modified for continuous rotation. For most modified motors, 1.5ms is the neutral point, where the servo will not rotate. Increasing the length of the pulse, to about 1.6ms, will cause the servo to rotate forwards. Decreasing the length of the pulse, to about 1.4ms, will cause the servo to rotate backwards. The speed at which they rotate is dependent on the pulse width.

If you are using servos, not all servos are built the same. In particular, the GW Servos that came with the ScooterBot II chassis are total junk. Not only do the consume excessive amounts of current, they also have a nasty “drifting neutral point” problem. We discovered the more the servos were used, the neutral point would begin to drift away from the previous setting. This was extremely annoying, as in the middle of a run when the robot should be stopped we discovered one, or both, were still slightly moving. This would go away after a few hours of rest and reappear again. We probably wasted a good month fighting with the bad motors until we switched them for the Parallax servos we found in the lab.

Parallax doesn’t actually manufacture the servos, but rather modify Futaba servos for continuous rotation. These consumed far less power, produced much less noise, and maintained solid operation for several continuous hours of use. These are highly recommended, even if your sensor package uses wheel encoders during movements (more on this later).

Steppers

Stepper motors are quite a different beast then servos. There movement is essentially guaranteed: you can control the stepper to move a given set of degrees, and the stepper will move that distance. Modified servos have no such guarantees; external sensors must be used to determine the amount of rotation. Steppers, however, have many limitations. Bipolar stepper motors require a stepper controller to control the direction of current through the coils. They are also heavier, more expensive, and pull more power than the servos. Unipolar steppers require a less complicated controller and are cheaper; however, they will probably not have enough torque to successfully move the robot.

We opted, as discussed, for Parallax servos in our design. Only one group attempted steppers, but their unipolar steppers could barely move the robot and they had to switch over to servos.

Special Task

To increase the difficulty of this course one extra level, Dr. Dunn will most likely have some sort of mechanical problem integrated into the competition. In our case, it involved devising a mechanism or method for gaining access to the fourth domino. One path to this domino was blocked by a softball. All but two groups decided to deal with the softball. The other two groups (mine included) decided to reach the domino through the hole.

The solutions for the softball fell into two categories. Two groups used a lift to pick up the softball when they encountered it and carry it with them. They both used a winch system driven by a servo. The other two groups attempted to push the softball out of the way to gain access to the cell.
The solutions to the hole fell into two categories as well. One team used a payload drop mechanism. They would back the robot the hole, which pushed on a lever and released a payload of marbles or dimes through the hole to hopefully knock over the domino.


Our group took a far different approach than anyone else. We used a Lego arm to extend through the hole to knock over the domino. It was driven back and forth by a gear mechanism attached to a non-continuous servo motor. It was mostly a failure, for which I will describe why next.

The only method that proved reliable was the softball lift mechanism. The two groups who both had the mechanism were the only ones to knock over all four dominos in the competition. All other groups suffered from other problems that ultimately prevented even the attempt at the forth domino. Our solution though looks impressive, lacked two fundamental systems that ensured its failure. We had no solution for lining the robot up to the hole and we had no reliable hole detection scheme. Our hole detection scheme only took place when we were attempting to find access to the hole. Our long-range sensor could see through the hole . However, our side-facing sensors would read the area around the hole. This worked most of the time, but if the sensor was slightly off, the long range would not detect the hole. Our quick solution to this was to throw the robot into an infinite loop, searching the three possible locations the hole could be until it found it. Once we found the hole, we had no way to tell we were even with the hole. Placing the robot just a half inch off would cause the arm to hit the wall and not extend through the hole. (I believe both solutions to the hole could have worked, but both solutions only managed to be integrated onto the robot two days before the competition. Neither groups had enough time to develop their methods.)
The moral to all of this is KISS (Keep It Simple, Stupid). The simplest mechanism worked the best. Although there exists problems with picking up and carrying the softball, they are not insurmountable and rather easy to deal with. I like my arm, but even I must admit going through the hole proved to be the most risky maneuver.

Sensors

There are five primary sensors used by all groups during this project. They include infrared range sensors, break beams, wheel encoders, contact switches, and a digital compass.

Before I begin, I would like to state what sensor didn’t work for anyone: SONAR. SONAR range sensors have the ability to see across the entire length of the game board. However, all groups discovered that they are useless in the game board environment. Their signal bounces and reflects far too much, producing wildly inaccurate measurements. Please avoid them.

Another sensor not used by any other group (but attempted by one, explained later) is the line follower. The line follower uses the same IR LED/phototransistor pair as the wheel encoders (to be described later), and like the wheel encoders they are used to tell transitions in color (mainly just black and white). If you look at the picture of the game board, you’ll see the white lines that Dr. Dunn intended robots to use a line follower on. This grid would work, except the grid is on 8” centers, while the walls are on 12” centers. This means the grid is practically worthless. Following one line in one area might keep you near the center of the cell and away from walls, but another line would drive you right into the edge of a wall. One group attempted a line follower mechanism. Their solution for the off-center lines was to mount the line follower on a bicycle-style chain to which they could move from side to side. This would allow the robot to find a line that wasn’t directly under them and to keep them away from the hazard I described. It would need to be adjusted after every turn to find a line on the off-center grid. They were unable to implement this design for unknown reasons.

Perhaps the most interesting sensor system tried by one group was an optical mouse. A standard optical mouse can track both X and Y directional movement. Their theory was this mouse therefore could be used as both their directional and drift sensors. The mouse talked over a standard serial interface, to which they plugged directly into the secondary serial interface on the microcontroller. The mouse was mounted with independent suspension on the bottom of the robot to keep it as close as possible to the game board surface. This system failed, for various reasons. I overheard them suffering from noise issues into the serial link. But perhaps the biggest issue is the mouse would loose counts while on the game board surface. Since optical mice have a fixed focal length, they have a limited range of usable height. Their independent suspension was ingenious, but proved to be not enough for the rough game board surface. By the end of the competition their mouse was nearly entirely substituted by other sensor packages.

Other sensor systems that could be tried, but were not by any group, include GPS and visual recognition. GPS doesn’t have enough accuracy indoors to provide any meaningful data. Visual recognition, though possible (thanks to yellow walls with green posts, and a mostly black floor) would constitute a massive coding effort with questionable accuracy, not to mention budget and microcontroller performance issues.

Infrared Range

Infrared range sensors come in two flavors, short range and long range. They are fairly cheap and easy to mount. Their beam is very narrow, meaning they will be unaffected by surrounding walls. The popular sensor is the Sharp GP2D12, which has a maximum range of about 35” and a minimum range of about 3”. They output data as an analog voltage that needs to be read by the Analog to Digital converter on the microcontroller. Their output is not linear and they have a minimum range. If an object is too close to the sensor, it will read it as farther away, causing potential errors. See this diagram to get an idea on how the short range works.

Care must be taken in mounting theses sensors as such. Mounting them towards the center of the robot ensures the sensor will not go past this minimum distance. The short range is really only practical for reading no more than two cells away. The long range sensors are really only good at about 4 cells away.

Also notice these are infrared devices. Such things as sunlight will affect them, but to varying degrees. Also, each sensor has an emitter and receiver. Therefore, the sensor can interfere with each other. Take a look back above to the 4-deck picture. One of the wall tracking sensors (which I will discuss later) on each side are flipped over. It was found that the front sensor could interfere with the back sensor when the robot was at certain angles, giving very incorrect readings. By flipping one over, I moved the receivers towards the middle of the robot, keeping the emitters from possibly interfering with each other. Also note from the above pictures that these sensors require proprietary connectors. I would suggest having at least one spare sensor and cable. We ordered the short IR sensors and cables from Robotics Connection and the long range sensor was used from the lab.

Break Beams

Break beams let the robot know if it was about to push over a domino. We used this to avoid all dominos during the initial discovery mode of the robot, where we didn’t know where we were. There were three different designs used this semester. The flashiest design had to be the laser break beams. These cost about $10-$15 and provided, from what I understand, a very reliable method of detection. The most interesting break beam used by two groups was a low mounted short range sensor. This was pointed at an angle to and constantly read to determine if a change occurred. Our design was by far the cheapest but also very reliable (and assembled in an hour the day before the competition). It consisted of an infrared LED/phototransistor from Radio Shack for $3. A diagram on how they were used is below:

At a reasonable distance the LED could not produce 0V-5V logic on the phototransistor. Therefore we read the output voltage through the A-to-D during our forward movements. We used the break beam only for domino detection; however, another group used another break beam for softball detection as well. The groups using an IR range sensor had the potential of using their sensor to also detect the softball. We attempted using our forward-facing long range IR sensor to detect the softball, but this would only work if it was correctly positioned. Looking back I would have liked to install a second IR break beam to detect the softball.

Wheel Encoders

Wheel encoders allow the robot to determine how far the wheels have rotated. They use a pattern on the wheel that is detected by an IR LED/phototransistor pair. These transitions happen at a very fast rate, especially if the encoder is set up to detect both white to black and black to white transitions. Therefore they must use interrupts to ensure the counts are accurate. Encoders allow for the stepper motor guarantee of a move to be applied to the servo motors.

Three groups did not use wheel encoders, including my group. One group tried using an optical mouse to track movement; however, this did not work as expected for them. The tank-bot did not use wheel encoders since it lacked any easy way to mount the encoders on the tracks. We used delay-based movements (which I will discuss in the Software section) and the long range sensor to correct ourselves. We realized later on that encoders would have made some things such as turns more accurate and easy.

Contact Switches

Simple contact switches played an important role in four groups. Two front mounted (or backwards mounted, in the case of the tank-bot) allowed the robot to move forwards towards a wall and continue moving until both switches have been pushed. This allows the robot to even itself up on a wall very effectively. In one robot they were used as the only forward facing sensors. We did, however, use a switch, in the form of a push-button for the robot to start with (this switch is required by all groups, and is considered the only user input to the robot).

Looking back, these are an extremely simple method for forward detection as well as correcting movements that I wished we implemented.

Digital Compass

We were the only group to use a digital magnetic compass (one group attempted to, but burned up their compass three days before the competition). The compass allowed us to determine our initial orientation with respect to the logical north on the game board. This made our initial discovery algorithm rather simple and dead accurate. We used the Dinsmore 1490, a simple $15 compass that can detect the 4 cardinal directions and the 4 intermediate directions.

We only use it initially and never again, since its accuracy is questionable for any movements. The compass worked amazingly well for us in the lab. However, during the competition the game board was moved to the upstairs in the IST building. The large steel beams proved disastrous to the compass, causing incorrect readings that mostly cost us the competition (we realistically only had a chance at second place, which we managed to get third). The problem could have been corrected with one extra step to the compass calibration code (adding one extra button push would have done it). I believe if we would have one extra day to test the robot at the place the game board was going to be, we could have corrected the problem easily.

Power

Power is an extremely important factor in the robot. Without proper power, you will be plagued by strange issues that keep coming back. Since everything on the robot is electrical, it makes sense to use batteries. The lab is stocked with AA size NiMH rechargeable batteries. I would highly suggest purchasing your own set of batteries, at least two sets, with a fast charger that can recharge in an hour or less. The batteries in the lab have been there for ages, and many of them are in sad shape. A fast recharger will be needed since many runs can kill the batteries and with the provided 13 hour chargers, that can kill a day.

There are several power considerations that must be met. First, your microcontroller (uC) has its own voltage regulator that can provide realistically just enough for the uC. I do not suggest powering anything else from the uC (the start button is the only thing that required uC power in our design). The uC voltage regulator requires at least 5.3V for it to regulate down to 5V. This means the uC needs five batteries in series to provide about 6V. The servos will operate from 6V without much issue. Sensors need 5V, so they need a regulator of their own. Servos also generate a considerable amount of noise in the system, which can greatly affect the sensors.

There are two schools of thought for the power supply. First is using two separate battery packs. One pack of five batteries power the uC and the sensor voltage regulator. Then another pack of four batteries power the servos unregulated. This comes to at least nine batteries, with most groups opting for this method. We, however, used one single battery pack. We used eight batteries in series powering the uC, the sensor voltage regulator, and a servo voltage regulator.

Since our movements are based on time, we need the servos to move at a consistent rate no matter the status of the batteries. Therefore, we opted to regulate them to 5V. Since we have only one battery pack, noise from the servos can potentially leak over into the sensors and uC. We used a design from Technological Arts to serve as a low-pass filter between the servos and the rest of the system. Our design can be seen as such:

Capacitors C1, C2, and C8 are Tantalum capacitors, with C1 and C2 being low-ESR Tantalums. Capacitor C3 is electrolytic. The Texas Instruments TPS7150QP supplies 500mA @ 5V. (NOTE: The diagram has the chips incorrectly labeled as the TPS7250QP. This chip is nearly identical, but can only deliver 250mA.) Since the uC has its own voltage regulator, we leave it unregulated. I constructed the power supply with simple connection headers so the servos and sensors could easily connect to it. All sensors are powered from the sensor voltage regulator, including the compass and break beam. All servos are powered from the servo regulator. This design proved to be stable when the batteries have enough supply voltage to them. Since the servos have heavy current draw, the regulators need a high supply voltage to keep the current supply stable (high as in at least 7V). The double-filtering caused by the low-pass filter and the very nature of the regulators kept 99.5% of all the servo motor noise on the servo motor side. The sensors can barely see any noise on their lines when looked through an oscilloscope.

This design could be improved, however, by the removal of some of the batteries. It is my belief this system would work better with just six batteries instead of eight. When the regulators drop the voltage, they dump the excess energy away as heat. The batteries would probably last just as long, if not longer, if only six were used. This should be enough voltage for the heavy servo swings, but we did not have a chance to test this (five in this configuration is almost stable, but we did encounter some problems with the uC with just five).

Software

Although the hardware for the robot is quite complex, the software is just as complex, if not far more. Our software design was not the most complex implementation. In fact, looking back, it’s rather simplistic. But its simplicity lead us to build very bug-free code that worked reliably. For this software section, I’m going to break it down into several sections. First, I will describe the tools needed to develop the software on the uC, next I will discuss the hardware/software interface, then dive into the movement algorithms, the overall algorithm, and finally our actual code. Since the software is highly proprietary to every group (and hard to observe) I cannot provide much detail on the methods and implementations that other groups use.

Tools

The uC uses ICC12 for programming the microcontroller. ICC is a rudimentary development environment, a specialized compiler, and a terminal interface rolled into one. Like convergent devices, it tries many things and fails all of them. It just plain sucks to edit and navigate code in ICC. It tries to do “smart tabs” but all that does is turn everything into a mess. The best part of it is scroll wheels don’t work in the main editing window (when I say best, I mean worst). The compiler does no optimization, so unused bits of code (like having stdio.h for printf(), but not using printf() anywhere) get linked right together. (Aside: The compiler may throw a warning that a function is not “elided.” This took us forever to figure out, but it means the return value of a function is not used. I heard this caused some problems for some groups, but all it did was annoy us. You could either dump the return value into an unused variable, or you can cast the function as a void function. Example: forward() returns a Boolean, so if you just want to call it without caring of the return, do (void) forward().) The terminal has the connection speed of the serial port buried in a dialog box from some menu. This is a big pain as well, since later on when the code becomes quite large, you have to increase the serial bus speed to speed up the transfer. The problem arises with the fact the uC will not remember the speed after a reset and will always default to 9600 baud. Therefore, you have to switch the speed back, change the speed from the terminal, and switch the speed back up to fast to do the transfer. Rinse and repeat 150 times and it becomes really annoying.

Download the ICC12 45-day demo here: icc12dem.zip

I have discovered a online textbook written by Dr. Jonathan Valvano called Developing Embedded Software in C Using ICC11/ICC12/Metrowerks. It contains a huge wealth of information on the matter and would be handy as a reference guide. This is something I wish I had.

For development, I highly recommend NOT using ICC12 to write the code in. I suggest building a Visual Studio project with your code. VS can have the more fancy things like jumping to specific functions in a file and auto-complete. I would also recommend finding and learning how to use one of the many source control packages out there. CVS seems like a good example. This makes changes done in the code easy to roll back and allows multiple developers easy access to the code. (I really, really, really recommend some decent development environment and some form of source control besides tons of commented-out code).

Interface

Inputs and outputs mostly happen through the A-to-D and Pulse Width Modulator, respectively. The A-to-D reads in a voltage level and converts it over into a digital value. The A-to-D has a high-precession 10 bit mode that I suggest be used. It requires some interesting bit shifting to read in the value since the 10 bit mode places the value in two registers. We used the raw values from the A-to-D in our code; however, some groups did convert the numbers over into inch readings. Sensor readings are mostly accurate and pretty reasonable. However, occasionally we encounter sensor glitches. Most of the algorithm to read the sensors took multiple samples, each sample after a brief delay (the sensors only update ever 50ms or so) and then averaged the result. It has been suggested, though, that taking the median instead of the mean is a more accurate method. We did not test median sampling, so we are unsure in this. The PWM required careful setup with clock divisions to ensure our duty cycle had enough range to be useful. The PWM will need to be operated in concatenated mode, where two channels are merged into one. This needs to be done to gain enough accuracy for the servos. The methods for setting up the registers are quite complicated, so I suggest reading over the manuals for the uC extensively. I know through somewhere on the Motorola website you can request hard copies of the manuals for the individual components.

It is also important to note the methods for setting PWM registers with variables. If you use some form of error correction and calculate a value to set the motors at, placing that value into the registers can be tricky. The registers only take 8 bit values, and moving something large (say, for example, a standard int) produces much unexpected results. PWM duty cycles need to be split into two registers for each channel. This can be done in one formula and later broken down, or two separate formulas calculate the two values. Either way, the variable holding the result that the register will be set as should be an unsigned char. The variable could be cast as that, or just declared as such.

Inputs and outputs can also be derived from the standard port pins. They provide standard logic levels to be easily set or read. Do note that as outputs they should probably be buffered. The uC voltage regulator only has about 20mA to spare, pretty much just enough to drive a single LED.

Movement

Moving forward 12” seems like a rather simple task. Generally, it is. Set the duty cycles on the PWM to have both motors drive forward, wait some delay, and then stop. The problems arise very quickly however. What happens if a wheel slips? Are your motors both going at the same rate? What are you going to do about turns and keeping it straight? This is where sensors come in.

First up are wheel encoders. During forward movements you can perform continuous checks of the counts the encoders are showing. If one wheel is falling behind the other, meaning its going slower, you can increase the speed on that wheel until the counts match back up. The correction algorithm will probably fall under either PID (proportional, integral, differential) or fuzzy logic. Please Google those two ideas to get an idea on how to error correct. As stated before, we did not use wheel encoders. Since the encoders count at a very fast rate, there arises the possibility of a count happening on one wheel while you are in the ISR from the other wheel. This can lead to a reduction of accuracy in the counts, so it is suggested to run the motors at a slower speed then full blast.

We used two IR short range sensors on either side to perform wall tracking. Wall tracking is used to keep us at a fixed distance to a nearby wall during a forward movement. While tracking a wall, we read the forward and back sensors and checked their difference and average to the ideal difference and ideal average (the ideal values are recorded off the A-to-D with the robot sitting at the desired position). We use rather simple logic then to determine if we are getting too far or going too close. We then adjusted the motors fixed amounts to correct (this is extremely crude, but it worked reasonably well since we did some 17 corrections for each movement). The same types of error correction (PID and fuzzy) can be used here as well to deal with wall tracking. Our algorithm could not handle half-cell situations, where the sensors were tracking a wall and the wall ends as we past it. We dealt with this by ignoring it (it would have been really nice if we could have gotten it to work). In our code we tried briefly half-cell tracking, however, we found our no-wall-tracking code to be pretty accurate, so we opted to use it because of the lack of time. Our code only does wall tracking on the perimeter walls where we know it will not end abruptly.

Wall tracking can be done using just one IR sensor per side. This requires keeping the previous samples to determine the amount of change that occurs. We still recommend the two sensor approach, since it allows the robot to square itself after a turn (as seen in evenUp()).

Since we did not have wheel encoders, we were not entirely sure of our turns or forward movements. Dealing with turns was done with the wall tracking sensors. After a turn, we use the sensors to read a wall. We check the difference value of the sensors, and adjust the robot until the difference matches the ideal difference. Forward movement corrections were done with cell cases using the long range sensor. At some 4 cells away, the scoot() function would be called. It would read the sensor and determine the most likely case for the number of cells away to a wall the robot is. Then, it would move to the ideal center for that cell slowly, checking the sensor during the movement. Every fourth move forward when we were moving with no wall tracking, we checked the left and right sensors. We turned the direction that read closer and performed a scoot(). This kept us near the center of the cell.

As mentioned, our movements were delayed-based. We set the motor values as desired, and then stayed in busy loops for some amount of time. The busy loops had different functions, like checking the forward sensor to determine how close we are to a wall as well as checking the break beam. Our system was mostly hacked together. Adding one line of code in the busy loop throws all of the delays off, so we had to be careful. A much better implementation, if we had the time, would be using the Real Time Interrupt. The RTI service routine could consist of nothing more than incrementing a global counter. In our busy loop we just check that counter until some value has been reached, then we can stop the loop. But, lack of time and an already working system kept us from getting RTI to work. If you plan to use wheel encoders, this busy loop could check the wheel counts instead.

Algorithm

First, I will describe some of the fundamental code decisions we made. Our code does not rely on interrupts at all. We check everything during busy loops. Other groups relied heavily on interrupts in their design (one group used nearly every available interrupt). Our code does not use any assembly. Some groups had an alarming amount of assembly for optimized code (one group had PAGES of assembly, unbelievable). Our code has no recursion. Some functions (such as moving around a wall) seem like the perfect candidate for recursion. Not having interrupts made it easy to determine where exactly in the code the robot was at any given time. With no recursion it made the algorithm more flexible by allowing the easy installation of special cases. There are, of course, very good arguments for interrupts and recursion. The key is not so much the design decision, but the actual implementation.

We modularized our code into a cell-by-cell method. Every forward movement took us forward only one cell. We would then stop, correct ourselves if needed, and then determine the next move before we either turned or moved forward again. As such, we then broke down the simple problems such as encountering an unexpected wall as a cell-by-cell method. We were the only group to do a stop-and-go method. Other groups used this method initially, but they moved on to continuous movement from one cell to the next. Because our wall-tracking algorithm was rather non-existent, we required the stops to correct ourselves. Our movements were rather jerky, but our overall speed was the fastest since we did not need to go slow to keep accuracy on the wheel encoders. One group in particular went extremely slow, roughly 1/4 of our speed. They used wheel encoders and wall-tracking IR, and as such they were extremely accurate in turns and movements.

A large portion of the algorithm will be dealing with unexpected walls. Our solution worked as such. 1. Turn a direction. For this example, lets assume we turn right. 2. Move forward one cell. If unable to move, go back to the first step. 3. Check to see if the left side has no wall. If one exists, go back to step two. 4. Turn left and move forward one cell. 5. Check to see if the left side has no wall. If one exists, go back to step two. 6. Turn left, move forward one cell, and finally turn right. This will take you to the other side of the wall in your original orientation. Draw these steps out on a piece of paper with different circumstances to get an idea how this should work. I'm pretty sure these six steps contain bugs, so for a solid example, check the code under getAroundRight() and getAroundLeft(). These two functions also keep track of the current goal cell as well as the next goal cell. This is done to prevent the robot from attempting to enter a blocked-off cell. We also implemented a path recording mechanism to perform backtracking when one of our initial turn guesses was not optimal or just incorrect (During our movements, we have a choice to determine what would be the best way to go around an unexpected wall, either to have the first turn be a right or a left). This prevents us from attempting to track around a perimeter wall when our initial guess and the given wall configuration work against us (if we guess wrong in some situations, our robot would track around the entire perimeter of the board without the backtracking).

The initial discovery algorithm (as seen in find_yourself()) finds a known corner of the board. When we begin, we know our orientation thanks to the compass. First, the robot turns to face logical north and tries to go forward. Every time it goes forward, it increments a counter counting the number of columns it has traveled. When it reaches a wall, it turns south and moves as far as possible, decrementing the column counter. When it reaches a wall, it attempts to travel around the wall using a set of functions called trackAroundRight() and trackAroundLeft(). They work in a similar fashion to the getAround functions, though they do not require the known position of the robot. This function will attempt to get around any wall. This includes perimeter walls. As we move, we continuously keep track of the row and column counters. If the robot discovers it tried going a direction 7 times and failed (meaning, for example, it tried to go logical west 7 times), it knows it was attempting to go around a perimeter wall. At the 7th attempt it has found a corner. Depending on which way it was trying to go determines which corner it has discovered. Our robot then sets its known location and follows a programmed path from that location.

I highly recommend modularizing the hell out of the code. Example: Any time you wish to set the motor speeds, set them in a function and call that function. In some parts of our software, like evenUp(), we merely want the robot to turn slight left. The problem we ran into is turning slightly left appears in multiple parts of the code. In evenUp(), we set the motor functions raw, so when we changed our motors we found all of these values to be incorrect. Instead of just changing one set of values in one small function, we found ourselves changing more than four sets. I would recommend keeping some large functions to a whole file by themselves to keep some form of organization.

Also, I REALLY recommend debugging statements. Use the preprocessing compiler statements (macros) to add and remove debugging statements that print out to the serial port. This is somewhat of a pain initially, but when the software isn’t doing quite what you expected, it’s always nice to be able to change one variable and kick on all of the debugging statements and remove them when not needed (printf() is a massive function that should not be on the robot when not needed).

Have a suite of testing software. These projects can be very simple, but they can also be life savers. For every piece of hardware, have a simple program that you can use to verify the operation of the device. For example: we had a simple program that would read out all the A-to-D values from the IR sensors in a constant loop. That way we could ensure proper operation of all the sensors on the robot.

Please mind C. This means follow safe C programming habits. Remember, initialize your variables! We ran into a bug where all of a sudden our robot refused to go forward. We had updated a completely unrelated piece of code, and could not debug the problem. The sensors were all working and after we rolled back our changes, the bug didn't go away. Two hours later, we came to realize we didn't initialize a variable to zero, causing our robot to stop because it thought a wall was directly in front of it all the time. This bug didn't develop until the right circumstances where a bad value was left over in the stack. Also, the compiler doesn't support dynamic memory. Although it will compile without error, it will do nothing. There are several other libraries that are simply incomplete, such as time.h (this took us awhile to figure out as well).

The only information about the other teams’ algorithms comes from the winning team. From what I gather, their algorithm was ridiculously complex. In some situations, they could determine exactly where they were within four moves (our best case was 7 moves, with an average of about 14 moves). They did tell us (after the competition, of course) if we blocked off the softball their algorithm required them to find all dominos first before knocking them down. That pushes the worst case to well over 40 moves (I believe our worst case is 28 moves, and that’s with an illegal game board configuration). The moral of the story is that if you have a huge weakness, be prepared for Dr. Dunn and your competition to exploit that weakness if they discover it.

Code

Our project required us to build a simulator for our algorithm. The simulator ran on C++ and was set up to be easily ported over to the robot. This was not entirely the case, however, since the compiler for ICC does not support dynamic memory. Our linked list for backtracking had to be converted over to a static implementation.

The simulated robot could move forward reliably. It had only one forward facing range sensor to tell if a wall was in front of it. It had a working digital compass that could tell its orientation at startup. These were the assumptions we made with the robot. Looking back, I wish we would have assumed some more. For example, with the addition of side sensors we wouldn’t need to turn as often to check to see if a wall was next to us. Also, it is important to keep the simulator code updated with the robot code. Some sensors may add additional functionality that you might want to explore, and the simulator is the perfect place for this. The code contains three primary functions: simulator only, simulator emulated, and robot only. Simulator only functions should not be seen on the robot and contain code such as the matrix display code. Simulator emulated functions emulate the movement functions. They must exist on the robot, but their internals cannot work on the robot. Robot only functions are design to be directly ported over to the robot.

Download the simulator code here: simulator.zip (5/16/07- fixed the executables)

Inside are two executables. One is a default layout with a default starting position. The other is a custom, illegal, game board configuration. Press a key to advance the robot one move.

Code on the robot was mostly the same as the simulator code. On the algorithm portion, special cases were implemented to reduce the number of moves. Simulator emulated functions, such as forward(), became quite complex and required their own file in order to maintain some organization. The preprogrammed path also changed to follow the perimeter walls as much as possible.

Download the robot code here: robot.zip

The code is commented to a reasonable level, but not entirely. If you have any specific questions, email me at the address above.

Tips

The first tip I can give is don’t take the course. I highly suggest taking a petition for EE403W or doing one of the Learning Factory projects that are an option at the beginning of the semester. Reasons for avoiding this course should be quite apparent by now (way, way, way, WAY too much work).

Having someone dedicated to the software of the robot, particularly the algorithm is probably a good suggestion. However, make sure at least one other group member also understands the underpinnings of the algorithm. Do not expect one person to handle ALL of the software, however, especially the interface and movement software.

Having someone dedicated to the hardware of the robot should not be expected. However, one person with good soldering skills is highly recommended. Neatness and organization for the wiring is essential (makes repairs easier and keeps Dr. Dunn happy).

Having someone dedicated to the report writing is not suggested. These reports are technical in nature, meaning the people who work on the robot should also write the reports. It is a good thing, though, to have a master of Word to do final editing to any report.

As with any project, starting early is important. Determine your overall design early, that way you can begin ordering parts early (within the first month your design should be well laid out and all parts ordered, at the latest).

Use all of the facilities available to you at PSU. The robotics lab does contain some components and test equipment, but the EE labs are far better stocked and equipped. The Learning Factory will provide tools and materials for any mechanical modifications/additions you require. Just make sure you have your own pair of safety goggles (borrow them from a ME that you know). Use ANGEL! It has a lot of group features that make perfect sense to use, such as a calender (for due dates and meeting times), chat rooms, file storage (perhaps as a backup, never trust the laptop), and group emailing.

Follow my mantra: Always check the cables first! I have found countless problems in computer related systems trace back to the cables or wires connecting the systems. The same rule applies to the robotics field. Although the wires themselves are unlikely to be the cause, the connections are. During this class you will learn how to crimp connections, wire-wrap and soldering if you have not done those before. I HIGHLY recommend practicing these at the earliest possibility. Dr. Dunn will provide an introduction to all techniques, but as with anything you probably wont learn them until you do them. If you find yourself having trouble (especially in soldering), I recommend the internet.

For some people, this will be their first (and probably only) college experience in doing a semester-long project with a group. Group dynamics become a huge factor in this project, as all of your talents and time will be required to successfully complete this course. I recommend grouping with both people that you personally know and people that you professionally know. Getting a group with solid, smart workers makes the project go far easier.

It is also important that all group members be FLEXIBLE, UNDERSTANDING, and DEDICATED. The members must be able to work around each others existing schedule. When you can't make it some day, make up for it and go in the lab to work when the others cant. Yes, this may not be your only class, but do realize the moment you signed up for this course all of your other classes just became secondary (see the first tip).

All of your grades will suffer (see the previous, and first, tips). I hope you have enough academic bouncy to wade it out. (As an example, I came into my last semester with 12 credits, the minimum load. I barely pulled out with a 3.0 to that semester, where before of workloads of 18 credits I had in excess of 3.7.)

Do not use the locked cabinet above your work area to store anything valuable! The latch for the lock is exposed underneath, meaning with a little playing it can be made to open VERY easily. Most people are decent, but sometimes someone may grab an entire parts bin and throw it in there, leaving everyone else without those parts. By moving latch slightly to the left or right (can't remember which way) and lifting straight up on the cover can cause it to open easily. Use the lockable set of drawers to keep your laptop/robot/parts.


Oh, please DON'T look at the HTML source to this page. Google Page Creator made a mess out of it.