Robotics: Udacity CS373 - Programming A Robotic Car - Week 4/Unit 4
Posted on 2012-05-15 @ 23:05:22 by r00t - Read the parent: Udacity CS373 - Programming A Robotic Car - Week 3/Unit 3
I'm not going to write up a very long article on this unit; it was a real butt-kicker for me. It started off fairly easy, but then got grueling. Somehow I made it through...
The whole unit was on essentially discrete methods of motion planning; everything was done on a 2D grid. A basic path planner was developed, nothing fancy, and not terribly efficient, but it worked. What got me most, though, was that my implementation and Professor Thrun's implementation were both fairly distinct, but mine passed the grader (and it passed all the tests I threw at it). From what I could tell between each set of code, they basically did the same thing, just in different manners. The next thing was showing the "expansion grid" the simple planner would produce; this was fairly easy as well - but once again, my code was different, but it passed. Then we had to write things to show the optimal path; my version turned out to be wildly different (I walked the path backwards from the goal to the start, and reversed the symbols for each step). Then it was on to learning about and implementing A* (pronounced "A-Star"); this was basically the same as our original planner, but with the application of a distance heuristic to make the planner "smarter" about the expansion of the nodes, so that it only expanded nodes that led it to the goal, and not away from it. Once that was done, we moved on to Dynamic Programming, computing optimal policies, etc; I got completely stuck on a problem called the "Left Turn Policy". Up until this problem, everything we had done depending on a 2D motion planner; that is, the robot only used 2-dimensional motion, having only an X and Y coordinate. For this problem, the simulation would try to simulate something like a real car, that still moved discretely, but also had an orientation parameter in addition to X and Y coordinates (fortunately, this orientation was constrained to Up/Down/Left/Right). In other words, this was our first 3D motion planner. My implementation would give me something, but it didn't work completely. After seven hours I gave in and looked at the answer; it wasn't an obvious solution, but it was something I hadn't tried (and I felt like I tried everything). Once I understood what was wanted, I continued with developing my code, and got it work after another half-hour. I then watched the complete explanation, and tried out Professor Thrun's code as well. Ugh. That was last piece, then it was on to the homework. I worked on that on Sunday; I got all the basic questions correct, then hit the final programming problem: Implementing stochastic motion in a dynamic programming planner. This was basically an implementation that makes it so that a robot (in the terms of a 2D discrete world, still) won't come close to the edge of the grid or to a wall, and will prefer a path that may be slightly longer to avoid such obstacles. I spent a long time on Sunday trying to get it to work, and while I had something (again) that would -almost- work, it still wasn't correct. I went to bed on Sunday, wondering if I would be able to complete the problem the next afternoon once I got home from work. Interestingly, after only a couple more hours, I had it working; I just had to re-watch the video explanation, go over my notes more, and look at things to make sure I was doing what was needed based on the implementation. I found that my original tries weren't -exactly- doing what was needed, so with a little tweaking, I got them in line and working smoothly. Professor Thrun's implementation was basically the same as mine, but the code was a little more elegant. Overall, that was a hard slog through the mud in a couple of spots. I'm not sure it was as insane as the monkey problem on Unit 2 or not, but it had its moments, most certainly. It was the first unit where I took more than a week to complete. I'm not into Unit 5, which is basically about making our discrete motion planners work so that they will output continuous motion paths. Today we looked at path smoothing using gradient descent (shades of the ML class here, which makes me wonder what other minimization techniques could be applied - path planning via ANNs?). So far, this unit has been fairly straightforward (famous last words)... /ok...that was longer than I planned <grin>
Questions or Comments?
If you have any questions or comments about this article, please contact me...