A* is Born

I've mentioned before that I never learned to drive, but recently Marika and I have been discussing finally getting my license. I've always found the mechanics of parallel parking perplexing, and I wondered if I could make it clearer to myself with a simulation. Initially, I tried to work out a full kinematic model: Each tire is applying a force and torque on the car's center of mass, causing the car to move and turn. I couldn't get that to work properly though, instead ending up with the car skidding sideways crazily. I realized instead I could ensure the wheels stayed in line by looking at the perspective of the rear axel. During a turn, these wheels stay pointing straight, but can spin at different rates. We can therefore represent the motion of the car as a combination of forward (or back) and rotating around the back tires. I implemented this in Python, then as a test had it drive forward steering 45° to the left:

So now we have a representation of our car, but how can we get it to parallel park? I tried a couple series of commands based on my second-hand parking experience, but I still couldn't get the car to do what I wanted. Then I started thinking about the recent developments in self-driving technology, and decided to try finding the solution algorithmically. After reading a bit about different path-finding techniques, I chose A*, which tries to find a path that gets closest to the target, using the fewest steps. Wikipedia has a nice animation of an example search:

Wikipedia

The technique works by keeping a list of open points (blue), which can spawn new open points by trying all possible moves from a given point. Once all the new moves are generated, we move that point to the closed list (red). We keep the list of open points sorted according to how many steps we are from the start and an estimate of the distance to the target. That way, we can generate our new points from the best point so far – You can see that effect above when the search gets around the wall.

To limit the number of choices to feed into this technique, I chose to give steering options of 0°, 45° left, and 45° right, while driving forward or backward a fixed amount. Given that I didn't spend much time optimizing my code, I was surprised at how quickly it was able to get close to the target. The animation below shows the current best point in blue at each step of the search, with the target in red:

Looking at the distance each of those "best points" lands from the target shows the advantage of the A* search:

A* allows the car to get further from its goal temporarily, resulting in a better final position. This all looks very promising, so let's see that robo-chauffeur in action!

I'm getting some "nervous student-driver" vibes from this, but overall not bad. I think I may be better off with my mushy brain for now, but it's only a matter of time.