September 25, 2011

Senior Project: Summer Update

My summer is finally over, bringing with it the start of a new year at school. I hadn't expected to do any more work on my car, but in the summer heat my thoughts drifted to the jumble of wires I'd spent my last weeks of High School playing with. Specifically, I was thinking about the IR sensor and how it could be improved. When I demoed my car, it didn't live up to its expectations (as the video I posted kind of shows). I blame this on how the car was driving on a different surface at a different speed: with changing speeds comes changing reaction times, causing the car to make its turns either too early or too late. Any other explanation for the car's misbehavior would have to be based on it reaching an intelligence level equivalent to that of a rebellious teen. These thoughts I've had about how to improve the IR sensor set up would have been helpful back when I was first building the car, but for now I'll just donate them to the pool of general knowledge.

Part of the issue with the car's reaction time derives from having to rely on a servo to take readings from each side of the car because servos take time to rotate. But what if I didn't need a servo? My summer modifications started with the remembrance that I actually had two IR sensors which I then plugged into holes I just happened to have on either side of the servo. This provides distance readings on either side of the car with the only delay between readings being dependent on the sensors and the software act of reading the sensors (which I think is insignificant, supposedly lying around 5ms).

In theory this works great. In reality, I don't know why it didn't. If I spent a little more time with the setup, maybe I could get it working; maybe the battery just wasn't charged. But that's irrelevant now as I can't work on this car until the end of the school year, and I don't want to. I'd prefer to start again building off whatever lessons I might have learned through this process.

But enough nostalgia, what didn't work? Obviously, I started by adjusting the code to use two sensors instead of one sensor and a servo; not too much work, mostly pressing ctrl-c and ctrl-v a few times. Mounting the two sensors also wasn't too much work; I just had to cut a piece of backing for the other sensor to drill into. Plugging the second sensor in, I decided to place it in parallel with the other sensor; this might have been my first mistake. More thought would need to be put into the matter, but by placing it in parallel (using the same filter circuit) might cause the readings to be inconsistent (which they were).

I first tested the car by placing it in my track, where I noticed that it was driving slowly, more slowly than I expected. That is probably evidence of a failure to charge the battery, which could well explain my results. The car, even though I knew the logic was sound, had terrible issues turning. Taking the car out of the track to test the sensors, my findings showed that the readings were inconsistent. Placing them the same distance from a wall, maybe 80% of the time they would have similar readings, but the rest of the time just complete garbage, and wouldn't match the distance set by my tape measure.

My setup should have worked - the two likely faults lie in a low-charge battery and paralleling the sensors, either or both of which could destabilize the voltages returned from the sensors. Instead of fixing those hardware errors and seeing if that solved the stability (or lack thereof), I set aside the car and started thinking of software fixes as I love software. And I came up with a couple possible solutions for any one interested.

The first wouldn't solve the stability, but it would (maybe greatly) increase the reaction time. My code translates the voltage readings from the sensors into inches, because (as an American) I like to think in inches. But what are those inches used for? The readings from the sensors are just compared to two values to determine when to turn or when to stop. The precise distance, in inches, doesn't matter. Instead, if I hardcode those two values (kill distance and turn distance) as volts instead of inches, it would eliminate the long, and cycle-heavy, conversion equation. The input to the Arduino code isn't in the form of volts, though, but in ten bits of data (0-1023), so I could even just store the values as an integer to avoid any conversions at all.

The second idea is much more complex and borrows some from my talk with the Stanford PhD student. One of my big takeaways from interviewing him, as well as listening to his thesis defense, is the usefulness of uncertainty. You can't trust the speed of the wheels or the readings from the sensors. You can't even trust what you see with your own eyes: you could be living in the Matrix, or this is Inception and you're living a dream. You are only able to guess their results. You could ignore uncertainty and say that the sensors are accurate 100% of the time. But they are not. Therefore, the proper way to make a vehicle intelligent is to not take any sensory reading at face value; you must analyze it to see if it is logical.

I already try to make the distance readings more accurate by applying a mode filter (or median if needed) to a set of consecutive readings. However, there are problems with assuming this filtering will produce precise and accurate results in the situation of my car, with the obvious one being that each reading takes place from a different state. Assuming the car is moving, each reading will be taken from a different distance (if only slightly different), and so they are supposed to be different. Due to low resolution you will get readings that are similar, and that is exploited to assume a mode filter will detect the correct distance. With a stable sensor, the mode filter might be accurate 99% of the time, but the current method assumes an accuracy of 100%, and even a difference that slight can produce problems.

The easy way to fix this will be to never assume complete accuracy, because as discussed there is no such thing. To start, scrap the mode/median filter. The filters will return the most likely distance from a set of distances, but using them will just waste clock cycles as I'm going to propose a different method of filtering. The goal of the system is to be able to take readings at set intervals and perform analysis to judge its accuracy. What I'm proposing is more simply called probability, akin to the methods behind Junior's (Stanford's second autonomous car) localization techniques. Not having formal teaching in that regard, my proposal is likely different, less efficient, and maybe outright wrong from the proper way to go about this.

Imagine a graph with time on the vertical axis and distance traveled across the horizontal. A straight (non-flat) line would represent a car moving over time, and the slope of the line is the car's velocity. A simple substitution can be made with replacing distance traveled with distance readings from sensors (we will just assume the car heads straight towards a wall), with the only effect being a flipping of the graph over the vertical axis. This provides a graph we can create from our car, just plotting the IR sensor data at periodic intervals, and the velocity is the negative of the slope (because of the flipping) of the generated line. The data from the car doesn't return a line, though, but a set of points. Linear regression is necessary to turn those points into a line, and while I've never been taught how to do that, it's surely available online.

To keep the data relevant and recent, a fixed period (or if you wanna get tricky, variable and adjusting period) should be chosen to regress, say only the last second of data. This will help adjust for any changes to velocity due to varying surfaces or a strong wind or dying battery or whatever. New readings can be compared to this graph and weighted based on how likely they are - if your last reading was twenty inches (and assuming it was reliable) and your next reading is fifty inches, you should be able to assume it is a fluke, and weight it much less. Weighting it less should simply effect its relevance to your regression algorithm; such a method is surely divinable somewhere.

Remember that we don't want to do anything with 100%, so we don't throw out that fifty-inch data point, we just say that it is unexpected. But say the next several readings also come out at fifty inches, or rather, forty nine and forty eight (to show that you are still moving towards something). Then we know something happened and the algorithm can restart the period at the new distance (regressing starting from the first fifty-inch reading) and adapt. This is also how turns work - when the car starts turning, the algorithm can adapt (I haven't put in enough thought to say if the regression should change to parabolic or probably depends on the type of corner).

The above five paragraphs explain, albeit poorly, a method of artificial intelligence for my car that would replace the structure currently in place. To attempt to summarize it, the premise is to never assume any measurement is correct. With enough measurements, though, you should get a clear trend equivalent to the path of the car. Using regression, you can come up with a line representing the path of the car that can be used to find the velocity. And then with more calculations you can figure out when to turn or stop the car. With a robust enough algorithm, you can have it visually plot the graph the sensors create, which provides a visual method of simulation. Essentially, this is a more proper though more difficult way to provide intelligence.

I suspect I rambled a bit, but I just wanted somewhere to put out these ideas. My method is probably a convoluted and simplified version of what real autonomous cars use. Feel free implement it, and let me know if you do. For now though, 'til next time.