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.

Triboelectric Slide

Recently I've been thinking back to my time at Eaglebrook, which I attended for 7th-9th grade (more on why it's on my mind at a later date). A memory surfaced that seemed ripe for analysis here: I was on the Ultimate Frisbee team, and there was one day that our practice was rained out, so we went to exercise in the hockey rink, which had been drained for the Spring. We decided to play blob tag: In case it's been too long since grade school, any time the person who's It tags someone, they join hands and become a bigger It. By the end of the game, most of the players are joined in one long It chain. We realized that by playing in the hockey rink, we could stretch from one wall to the opposite and simply walk toward the remaining players, who were now cornered. The kids on the ends of the chain ran their fingers along the walls of the rink, and after a few seconds, a massive static discharge traveled down the line from each end, meeting at our coach in the center, who fell to his knees in pain, clutching his arms!

Naturally, thinking of this made me wonder whether I could model the situation. Static electricity is typically caused by the triboelectric effect, in which charges transfer between materials in contact due to differences in the energy states, though the precise mechanism is not fully understood. I decided to try modeling my situation as a circuit:

Made using circuit-diagram.org

Here we have the charged walls providing a voltage (circled arrows) and the players linked to each other (resistor Ts) and the ground (lined triangles). We can analyze this circuit using Kirchhoff's Laws: At each junction of wires, there must be a constant voltage, and all currents in and out must sum to zero. These seem simple, but when you have a tangled mess of components like this, it can get tricky. I worked out what I thought was the answer, doubted myself, worked it out again and got the same thing, so I think this is right. If the static from the wall produces a current I with a voltage V, then the nth person from the wall will discharge a current of

This seems to suggest that the current decreases as we move away from the wall, since the n(n+1) term will grow faster than the n. However, we also need to consider the charge coming from the opposite wall. For N people in the chain, the total will be

Note that we subtract the current from the opposite wall, since it's flowing in the other direction. It's a little hard to see what's going on here, so let's throw some numbers at it: The resistance of skin can vary a lot depending on how dry it is and other factors, but a typical value is 1000 ohms.

For the total current from each wall I, I found a paper on measuring the triboelectric charge transferred for different materials, which happened to include high-density polyethylene (HDPE), the substance commonly used in skating rink walls. Unfortunately, it does not have human skin, but I took their measurement of pigskin as a good representative (and appropriate for the day of the Super Bowl). The numbers they give are charge per area, but we want current, which is charge per time. We can imagine as the players walk forward dragging their fingertips along the wall, the total area will accumulate proportional to the width of the fingers contacting the wall, and the speed they're walking. Using the numbers from the paper, and assuming 1 cm width for each of 4 fingers moving against the wall at 1.5 m/s, we get (30 uC/m^2)*(4 cm)*(1.5 m/s) = 1.8 microamps.

We still need the voltage V, but we know from Kirchhoff's Laws all the individual currents need to sum to I, so we can sum In from 1 to N, set it equal to I, and solve for V:

Now we can plug this into the equation for the current discharge to see what each player gets:

Due to the flip in direction of the current at the far wall, it remains true that the highest current is on the ends, and the person in the center should feel nothing, so already things are looking bad for this model. What about the overall magnitude of the current?

According to OSHA, you start to feel a tingle around 1 milliamp, but below this would not notice anything. Our current is 5x smaller, so certainly not enough to cause the effects I saw (and felt myself)! I think one of the problems with this analysis may be the assumption of continuous discharging – If we let the charge build up for some time before being released, it could generate significantly higher currents, and may not be perfectly symmetric. Perhaps some intrepid Eaglebrook students can repeat the experiment, and gather more data!