Back in 2017, before a major geographical move and career change, I was working on a project where I built and wrote an A* based path planning algorithm for a nonholonomic robot:
http://buildingfriends.blogspot.com/2017/06/indoors-navigation-robot-driving.html
In the process of doing research for that project, I had come across the concept of Rapidly Exploring Random Trees:
https://en.wikipedia.org/wiki/Rapidly-exploring_random_tree
I tested one simple implementation on GitHub (I can't remember which) and thought about what would be involved for using it for my path planning approach. I decided I would need to consider an extension and probably would not be successful with a basic RRT alone. I identified Theta* RRT as a promising technique for solving my particular path planning problem.
http://idm-lab.org/bib/abstracts/papers/icra16.pdf
But I ran out of time and confidence in my ability and went with the what I already understood fairly well, which was A*, and wrote about it in this blog (but never got around to publishing it on GitHub).
Since I moved in 2017, nearly all my projects involve making makerspaces. Instead of making projects, I help other people create projects. And recently, rather than helping other people create projects, I create systems to help people help other people to create projects. A big theme in my life is institutional sustainability/long term institutional survival/development of infrastructure that is not highly dependent on a single individual's expertise, presence, and commitment. I am trying to automate my job (not that I don't enjoy doing it, but it feels like the responsible thing to do; too many makerspaces and other institutions have serious existential risk posed to them by there being one leader upon whose shoulders everything rests).
I haven't had too much time to collect my thoughts into a post, though I will keep trying in the future.
I revisited Theta* RRT nearly two years later in the context of a graduate level robotics class I signed up for, perhaps foolishly.
The robotics class was excellent, but a huge time sink. For the first time in two years I wasn't teaching a three hour lab based class once a week, so I figured that freed up about 10 hours a week to spend on this. The professor for this class said to expect to spend 5 hours a week on average on the class, so I figured I was good...
There were 5 assignments due over the 13 week semester. I spent only 15 hours from start to finish on at least two of them (but those were the easiest ones). If they had all each taken 15 hours, 15 hours * 5 assignments / 13 weeks is about 5.8 hours a week. But many of them took me much, much longer than 15 hours. I probably spent 50-60 hours on the Theta* RRT project. On top of that were required and optional readings. These weren't really enforced. I hate to admit I did nearly none of those readings. I was really struggling to balance my job and my desire to perform really really well in this class, and so I tried to limit my time expenditure to only those things that directly would affect my grade in this class. I guess when I was a kid I had to make compromises like 'do well in school' vs. 'socialize and have fun.' But now I make mostly compromises like 'do well in school' vs. 'spend more time on work' and I'm starting to really feel like an adult...
Fast forward to the end of the Spring 2019 semester. I'm trying to finish my final project, for which I've chosen to implement Theta* RRT in Python, and also my final other assignment, which is an implementation of RRTs in C++. I pushed all my other commitments forward and sat at my dining room table working for 15 hours straight on the last day, accidentally causing what might be permanent nerve damage to one of my legs (it has been a month and still I have a large area without much skin level sensation on my shin). I do feel that it was worth it, though if I had known I would have gotten a more comfortable chair which would have prevented that from happening. I would have also found a way to make more time for this project in the weeks prior.
The rapidly exploring random tree works like this (glossing over details):
There is a starting position and orientation for the car (red, above) and we want it to reach the goal position and orientation (green, above). The car can't steer very sharply; it has a limited turn radius. There are many ways it could reach the goal, but it is impossible to search them all, because the x and y position, as well as the angle of the car, are all continuous real variables, so infinite and uncountable.
So at every step of this algorithm, which we will repeat until we find some path that drives us to the goal within a tolerance, we will randomly choose some x,y position and car angle.
We're going to keep track of paths in this process in the form of a tree, branching from the red car (starting node). We'll identify the configuration in the tree nearest to the new random configuration (note that in the beginning, the only thing in the tree is the starting node).
Then we will try to drive to the new random configuration. We probably can't find a way to drive to the new configuration exactly, but we'll drive towards it and wherever we land, we'll add that to the tree, keeping track of that steering path we used to get there. We'll always check to see if we made it close enough to the goal, and if we did, we'll extract the path from the tree that got us there.
The entire tree is shown in black, and the extracted solution path in blue.
 |
| One of the very lucky trials for the plain RRT. Note how it considered backing up in one iteration, but otherwise explored directly to the goal. |
Parallel parking:
The Theta* RRT project took longer than expected and I didn't complete everything I wanted to put into it. So I'll leave a more in depth post about it for after I get around to revisiting it and completing all the parts I wanted to complete. You can follow along on GitHub:
https://github.com/eshira/theta-rrt
