Thursday, November 18, 2010

109. Harnessing "Anti-Gravity" for PRT Control

Recently astute reader Ken MacLeod suggested that we consider certain computer-generated steering behaviors for merging PRT vehicles, and included this link.When I looked at them, (He specifically referred to the queuing example) I was first reminded of a thought I expressed in post 41, where I touched on the possibility of flocking or schooling behavior to help alleviate traffic, although I really didn’t know what it was called at the time. And so I responded by saying that the behaviors seemed more suited to traffic management. Now I get it, however.

Flocking (and the other related behaviors) is actually extremely relevant to PRT because of how it is generated. It is the interaction of imaginary gravity and antigravity between objects in motion. Specifically, it happens when there is very strong close-range anti-gravity and weaker, longer-range gravity. The gravity creates a group or “flock” and the antigravity keeps the “birds” from hitting each other. A favorite demonstration of this is “Boids,” which, as it sounds, supposedly came from the word “birds” combined from someone’s strong (New York area?) accent. In this example, the programmer periodically changes the parameters, (number of fish) leading to stronger schooling or flocking (gravity) forces. Anti-gravity is localized to the area immediately around each fish.

When we drive our cars there is a similar effect going on, except that it is highly linear. The anti-gravity part is dominant and stems from driver reluctance to follow a vehicle too closely. The closer you get, the faster and harder you are likely to apply the brake. When you follow at a safe distance, you are liable to maintain an equilibrium between braking and accelerating. When you see the gap getting larger, you are free to apply the gas petal, discounting other factors like speed limit. In auto traffic, there is no appreciable gravity effect, however, as there is no benefit to clumping cars together, (with the possible exception of convoys of speeders.)

Note that the “anti-gravity” at extremely close range (like actually touching) can be set to infinity. Therefore brakes are applied to maximum extent possible to avoid touching bumpers. In PRT, it seems that something similar is almost unavoidable. The question is whether collision avoidance through some kind of proximity sensors should be an add-on for redundancy or emergencies only, or integrated directly into the control processes.

As I mentioned in the beginning of this post, it has been suggested that such algorithms could be used in PRT for merging as well as headway control. In such a scenario a computer could consider where, in a line of vehicles, the merging vehicle would be expected to eventually fit, and then gradually apply more and more anti-gravity to that spot. Thus it is like a ghost vehicle slowly materializing and repelling the vehicles around it. It increases this short-range anti-gravity toward mathematical infinity until it has forced a space for the merging vehicle. This is an interesting approach because all decision-making can be localized to the vehicles involved. It also doesn’t need too much or particularly fast communications. Each vehicle simply responds to the proximity-induced repelling forces while trying to maintain forward speed.

One problem with this approach, however, is that it lacks intelligence in the choosing of where, in a line of vehicles, a merging vehicle should be placed. For example, what if a single merging vehicle is near the front of a group of 15 vehicles with plenty of space in front of the group. It seems like it shouldn’t split them up, but rather speed up and merge in front them, if there is time. At least it should delay as few vehicles as possible. But then again perhaps the anti-gravity could be set so that the group collectively repels the single car into such a choice. Or perhaps the group is self-dispersing, because the anti-gravity’s range is sufficient to “de-clump” the 15 vehicles in the first place.

In such a system there is no problem controlling traffic in the event that a section of the system becomes “over-booked.” The traffic would simply slow down. In an earlier post I outlined a control method based on precisely synchronized timing, where vehicles could “book” a split-second “reservation” to go through a merge point without conflict. The system begins with fuzzy time estimates at the point of departure, and but reschedules with more and more precision as the vehicle nears a merge-point and utilizes track markers to time itself.  Such a system has automatic traffic control; it can be set to never allow overbooking of a route. It becomes more problematic, however, as fast and heavy traffic pushes the limits of communications and reduces the margin for error. Perhaps the two methods can be combined. Thanks again, Ken. You’ve reminded me again that many heads are better than one!

No comments: