Sunday, August 29, 2010

101> PRT Merge Control


Well, I didn’t say I wouldn’t post… Part of not having to post every week is to give me the time to explore ideas more fully before I write about them.  The matter of PRT control, however, is something that I have already written about extensively in draft form, both to clarify it in my own mind and to try to figure out a way to explain it.  Here is a little sample for your consideration that cuts right to the heart of the matter.

Consider the most critical maneuver in PRT, the merge.  Weaving PRT traffic can be done through exact scheduling, direct sensing/communications between merging vehicles or through an intermediary. Over a decade ago, When J. Edward Anderson wrote about the problem, using an intermediary was the only practical solution.  I believe that paradigm is no longer the only game in town.

Let’s compare a similar type of system, also designed many years ago, air traffic control.  Here, airplanes are controlled by an intermediary, the control tower, which I think is roughly analogous to Anderson’s “zone-controllers.”  Could we cut this intermediary out?  Consider what would happen if the tower went dark but the planes could communicate with each other directly, and they all had the airport’s schedule.  It would be a fairly simple matter for the first plane on the schedule to call the second when it was about to touch down, and again when it was clearing the runway, with the second giving similar guidance to the third, etc.  Moreover, if they synchronized their watches, they could simply make a schedule for themselves, landing a plane, say, every minute, so that the first might touch down at 4:00, the second at 4:01, and so fourth.  If they all knew who was in the air around them and what the landing order was, they could speed the process by all advancing their schedules each time the landing plane beat the scheduled time.

This is the essence of what I propose for PRT.  With PRT, at the inception of every trip, it is necessary to know if the trip can be completed and if so, by what route.  Since any trip can be broken down into pieces, dividing the trip into segments beginning and ending at merge points makes as much sense as anything else.  Since the travel time between merge points can be estimated, there should be, at the beginning of any trip, a knowledge of what time each merge point will be encountered.  This would be an opportune time to assess the traffic load through the various merge points and to consider alternative routing.

Furthermore, upon logging these plans at the boarding kiosk, a system-wide database can be generated which may be divided and sorted in different ways.  One such way would be to list all vehicles scheduled to pass through a given merge point, sorted by time of arrival.  A group of such lists (one for each merge point on a route) could be downloaded to every vehicle upon leaving the station and updated.  In this way, every vehicle in every stretch of track knows the identities of every other vehicle on that track segment, as well as those on the corresponding track segment that is connected at the next merge.  Now a  LAN can be established.  Furthermore, every vehicle knows which vehicles are the most relevant from that list, those being the ones that are closest chronologically.  This is not very different from the example of the pilot-to-pilot communication described above, with the most important conversations being between those first in line.

Now all of the vehicles in the two connected segments have each other’s “phone numbers” (so to speak) and can initiate communication as needed. There are a number of things that might be done to help things along, such as either distributing or “clumping” vehicles together, prioritizing vehicles by swapping merge schedules, or even pushing vehicles faster through the merge than would normally be acceptable, to help avoid an upcoming traffic jam, or even switching routes if there is a diverging track.
Listing all of the ways traffic could be shaped is too involved to get into here, and traffic shaping software would probably evolve over time anyway. 

It is worth noting that this system consists of smaller, faster, shorter distance, and more critical networks overlaid upon larger, slower, potentially less timely ones. For example, the kiosk booking and initial routing, it seems to me, could be done via the web, while last second communications between vehicles about to enter the merge should probably be circuit-switched (“hard-wired”) instead of packet based, and would include only those vehicles directly involved. Such a general architecture could offer excellent fault tolerance through the redundancy of multiple networks and independence from central control.

Two points to add  –  First, in regards to previous posts and comments about cameras and sensors and seeing around corners … I want to point out that if vehicles can broadcast location updates more or less continuously, this is functionally equivalent. “Dark” vehicles can be detected as missing from the network, and in the scheme above their relative location is also known. Second, in regard to previous discussions about variable speed, I used the example of catering to people who are prone to motion sickness as one benefit.  I think a far better example is that of empty vehicles. In a rush-hour situation, great numbers might need to be shuttled back empty to pick up new passengers.  These empties have no issues to restrict speed at all, and their lighter weight means they can have less headway.  In fact, I see no regulatory obstacles to coupling them into platoons.  (Platooning occupied vehicles would be a lot easier to sell after it has been widely used for empties.)  This is easily accommodated by the control system outlined above.  Anyway, it is adaptive, variable speed I am advocating, not gentle rides or fast empties or platooning or prioritized traffic.  These incremental improvements can evolve later, as long as the system architecture supports such tweaking. 

17 comments:

Ryan Baker said...

In the air traffic example, a tower can move planes up in a schedule at least as effectively as individual planes can.

If it's up to the individual planes then they have to play a competitive game to determine which plane moves up. It's not simply going to be the one behind, because it may not be able to get there in time. That type of competition requires playing through multiple scenarios, which if done by planes separated by significant distances is going to be far less efficient than if all those scenarios are played out in a CPU with millimeters between the different set of input data.

Now.. the only way that the independent systems can perform those calculations as efficiently and accurately as a central one is if they all receive the full set of data and independently all calculate the same results. Sounds interesting in principle, but in reality it's quite bad because if one system misses one piece of data, even assuming all the rules are controlled precisely between the different entities, the outcome could be significantly different and each entity would have to fact check it's results with at least 3 other entities.

All of this should raise some very serious concerns about the wisdom of an effort to eliminate authoritative systems.

Independent processing has it's place in the system, and there's certainly something to be gained there, but it's not an either/or question. Authoritative systems can orchestrate the scheduling of vehicles but do still allow some leeway to the independent vehicles to make decisions.

For example emergency stop procedures are likely to have a component that is partially independent. Merges are likely to have a "window" within which minor corrections are made.

Maybe you think an independent system can eliminate the need for windows, but they don't. Just look at automobiles. When you're entering a highway you look for a window before you commit to a merge.. unless you're crazy. Once you've seen a window, you accelerate or decelerate to match (usually accelerate) and hope the other cars agree with your decision.

It's a somewhat unfair comparison, but I would point out that the system you're modeling your control system on, the automobile, has accident rates many orders of magnitude higher than the one you're critical of (air traffic control).

Yes, the pilots are professionals and drivers are amateurs, but then again, your car isn't going to flip over if you touch down wrong.. isn't going several hundred miles per hour, and you don't need to worry about another car landing on top of you.. it's just front, back, left and right.

Dan said...

Dan the blogger responds with a two parter..
Ryan, first I need to say that I am flying out tomorrow to go to my land on a 7:00 AM flight. I will not have internet access at all for a few days, and only limited access for the next month, with even power to run my laptop being limited. So bear with me if I do not answer promptly. I go to the town library for internet and recharging but that’s mostly just if it’s raining.

Frankly, I do not understand your criticisms, and fear that I am miscommunicating rather badly. How is a clock-based merge system like an automobile? I also do not understand why you bring in hypothetical planes that are not in range, or have the pilots competing. I am not really advocating that level of autonomy, (some would call it flexibility) at least until someone much smarter than I figures out how to pull it off. I was describing planes already circling, already in order, just like vehicles on a track are in order.

I have never criticized the effectiveness of intermediaries, or authoritarian systems, or zone controllers, etc. My problem with zone controllers has absolutely nothing to do with the practicality of building a system that will work reasonably well. It might very well be easier. It’s the business model of too much wayside control, especially over time, that worries me.

I question its robustness in cases of natural disasters or even man-made situations like bankruptcies, strikes, neglect, poor training, communication with vehicle makers, etc. I also question the wisdom of creating what will someday be a legacy system, with standards and protocols that will forever need to be incorporated into subsequent generations of PRT vehicles. It’s like introducing a “Wintel” element that won’t go away. What is the business model that incorporates updating and improving an authoritarian based control system in, say, twenty years? Must a city be dependant on a single supplier forever for these parts? Will any problems be easily traceable to either the vehicle or the zone controller, or will there be finger pointing, like with BP and Transocean? I like eliminating the zone controller because it makes everything clean and simple organizationally, and, I think, much more salable to fearful public servants.

The traffic shaping algorithms that will work best will undoubtedly be extremely complex and take years to perfect. I am suggesting a system by which they may be incorporated in bits and pieces over time.

Dan said...

Let me try to explain the system this way. A centrally based synchronous system is set up in such a way that the performance can be enhanced by the ability of the vehicles to assess the situation and negotiate modifications to the timetable. If the modifications represent no conflict of scheduling, the timetable can be modified, the vehicles’ velocities can be changed accordingly, and the whole central database is updated to reflect the changes. The central database, through vehicle initiated as well as scheduled updates, is made to become more and more accurate with respect to any upcoming merge or docking.

There is always a point where traffic density makes any autonomy impossible, and all systems become synchronous. Equally, in low traffic density there are times where a synchronous system is ridiculously restrictive. In particular, it is the spaces in traffic that may be exploited by advancing vehicles within these voids. The larger the void, the higher the payback. Do not get all fixated on the possibility of vehicles of competing for incremental advantage in tight traffic. That is the tail wagging the dog – not what this is about at all. (Although the system I describe allows all kinds of such things in theory)

I am thinking of the much more modest goal (for example) of a gentle ramp up (to over normal cruising speed) and then ramp down, on straight, empty sections of track. In a case like that, the vehicle only has to make sure that getting there early will not put it in conflict, something it is in a position to know from updates. Many maneuvers would probably require permission. In this system such permission would generally be required in heavier traffic, and the rules would be more lenient if there is more room for error.
For example, I believe that the half-second headways that Anderson spoke of are attainable, which translates into a vehicle from each leg of a merge making passage in one second intervals. In practical application, however, there would often be many seconds of empty space to choose from. This would bode well for allowing some autonomy, keeping in mind that all vehicles periodically update the main database anyway, since this is the information used as a starting point to calculate subsequent maneuvers.

I was warned not to get too specific on my post, because it might create obstacles where none need exist, and I did not want to “paint myself into a corner.” I did not include network size and type, for example. Perhaps, though, this is too complex to deal with in generalities.

Ryan Baker said...

I wouldn't look at any of the control elements as "parts". It's really software. You get locked into software by having lots of highly complex interconnecting implementations, of which one or more is very difficult to replace.

Having ever vehicle have a more complex system necessary to make all these decisions in a peer model is going to promote complexity and lock-in more than having a hierarchal model.

Hierarchies (tiers) are a very common way to achieve higher scalability, and for all intents and purposes the intermediary zone controller is a tier optimized to that task. If we wanted to generalize further we would instead realize that it's not necessarily going to be just a three tier model (vehicle, zone, central), but maybe an n-tier model. Three has sounded like a good number so far, but as a system grows to a national level I could see justification for four.

What you should understand is there are two purposes for tiers (or any hierarchy). One possible purpose, less applicable here, is reduction (ever heard the term map-reduce?). This finds very common use in server architecture and enables a huge number of the applications you use on a daily basis to function. This process allows a central system to achieve an answer it would not have been capable of if it had to process all the data rather than a set of reductions. For the most part though, excepting very large systems I'd expect a central system could process all the incoming data.

The more relevant purpose is latency. Computers have gone from having just registers, to registers and RAM, to registers, RAM and disk, to registers, L1 cache, RAM ... L3 cache is common today.

The purpose of all those different tiers is to reduce latency at each step. We are talking about microseconds here, but the concept scales up just as well to networks of vehicles as it does to silicon pathways.

A fairly local system like a zone controller can reasonably process all of the distinct inputs from it's control zone in addition to communicating with the central system and the immediately nearby zone controllers. It also can reasonably provide feedback to vehicles in the zone for time sensitive operations such as merging.

Optimally the vehicles participate as well. I'm fairly certain we both agree on this last point, though to some degree it has appeared like you believed having a zone controller would prohibit it.

It's true I get concerned about the high traffic scenarios, but I'm not neglecting the low traffic scenarios, they're simply easier to deal with. If there is a 10 second gap, then having a delay of 100ms in the decision process will be trivial. A completely central system could optimize that to the degree that there wouldn't be any functional difference between it being an autonomous or central control. Now I'm not advocating completely central control, or even completely zone control. I'm advocating separation of concerns, where vehicles are concerned with making decisions within the next 100ms, zone controllers within the 100ms-15 second range, and central systems for anything greater than 15 seconds. You could have some overlap there, but I think you get the general idea.

By the way.. the air traffic controllers do attempt to not have planes circle airports. When things are running smoothly a plane would fly right in and land. The planning process for getting a plane land starts before it ever takes off. It's only the unexpected events that may happen in the 1-10 hours a plane is in the air that would cause circling to become necessary.

Anonymous said...

Dan wrote:

"Must a city be dependant on a single supplier forever for these parts? Will any problems be easily traceable to either the vehicle or the zone controller, or will there be finger pointing, like with BP and Transocean?"

I've been waiting for this discussion to come up. I think it is essential for PRTs to solve the provider trap dilemma and it requires both business model and technology.

The solution I'm favoring is selling a *service*, not the vehicles or the track. One company will sell and maintain the whole service. There's monetary penalties if i.e. capacity requirements or other service criteria are not fulfilled.

Projects are competed for initially (between incompatible PRT systems) and when they expire.

Yes, it should be possible to change providers. Unbuild the track. Remove the stations. The system must be designed so that "dropping" a track in place is not so time, material and labor intensive as it nowadays is (there was a tram route repair that took ~6 months in my neighbourhood). If we can have tracks that emerge and disappear within -say- 1 week, it allows competition on the whole service level.

This *is* the Apple approach, more or less. To guarantee best passenger experience and best reliability the parts should be integrated by one party. No Macs built by Dell.

Interestingly enough, this model of competition does allow for a multi-vendor shared system to compete, just like Linux and Windows compete with Macs. It's up to each city or community to select their choice and then stick to it for the duration of the contract. Our (as the service provider) responsibility lies in making them so pleased they won't change their mind.

It is even possible to have multiple vendors operating in the same city. Each network would run independently and if there's need to jump from one to the other (if their coverage meets, that is) it's a simple matter of jumping out and back in at connected stations (this should of course be rare since PRT tracks should be designed to cover people's natural area of transit).

Why is this model better than standardizing on certain technology and then competing within it?

We don't *have* the best technology, yet.

We need the next 20 years to see, which technology is best. Incidentially, patent lifespan is 20 years so eventually any (patented) in-house technology becomes available for standardization. Let's experiment and refine the systems in this first era of PRT and then we'll have truly good, maybe multi-vendor systems from 2030 onwards.

Anonymous said...

Dan wrote:

"Must a city be dependant on a single supplier forever for these parts? Will any problems be easily traceable to either the vehicle or the zone controller, or will there be finger pointing, like with BP and Transocean?"

I've been waiting for this discussion to come up. I think it is essential for PRTs to solve the provider trap dilemma and it requires both business model and technology.

The solution I'm favoring is selling a *service*, not the vehicles or the track. One company will sell and maintain the whole service. There's monetary penalties if i.e. capacity requirements or other service criteria are not fulfilled.

Projects are competed for initially (between incompatible PRT systems) and when they expire.

Yes, it should be possible to change providers. Unbuild the track. Remove the stations. The system must be designed so that "dropping" a track in place is not so time, material and labor intensive as it nowadays is (there was a tram route repair that took ~6 months in my neighbourhood). If we can have tracks that emerge and disappear within -say- 1 week, it allows competition on the whole service level.

...cont'd in part2...

Anonymous said...

...part 2...

This *is* the Apple approach, more or less. To guarantee best passenger experience and best reliability the parts should be integrated by one party. No Macs built by Dell.

Interestingly enough, this model of competition does allow for a multi-vendor shared system to compete, just like Linux and Windows compete with Macs. It's up to each city or community to select their choice and then stick to it for the duration of the contract. Our (as the service provider) responsibility lies in making them so pleased they won't change their mind.

It is even possible to have multiple vendors operating in the same city. Each network would run independently and if there's need to jump from one to the other (if their coverage meets, that is) it's a simple matter of jumping out and back in at connected stations (this should of course be rare since PRT tracks should be designed to cover people's natural area of transit).

Why is this model better than standardizing on certain technology and then competing within it?

We don't *have* the best technology, yet.

We need the next 20 years to see, which technology is best. Incidentially, patent lifespan is 20 years so eventually any (patented) in-house technology becomes available for standardization. Let's experiment and refine the systems in this first era of PRT and then we'll have truly good, maybe multi-vendor systems from 2030 onwards.

Andrew F said...

akauppi,

That model sounds like it has potential on the surface of it. But what kind of PRT provider could afford to offer some reasonable length contract, at a reasonable cost to the consumer, and have the costs of installing and removing the infrastructure fully amortized by the end of the contract? I'm not sure it's possible. Are you envisioning 25, 30 year contracts?

Even if you could put in and take out a system in a couple of weeks on any given street, switching from one system to another would be impractical as users would become dependent on it, and building an entire network would take months at minimum. The first vendor would have an enormous incumbent advantage, and would be able to extract large economic rents unless its technology became seriously outclassed over the term of the contract.

Anonymous said...

Well, Andrew.

I guess we have to create such a company. This challenge is at least as much economical as it is technical. Or maybe more. Technology changes business rules, as well. Think of how much computers have changed everything around us.

I don't intend the company to be making a bad business. But it won't rip off too much either. If the track is easy to build and recycle and there's scalability, this will certainly work.

We'll have to show it does. And I think we will.

Contracts would be 10 years, and most of the customers would gladly continue them. The timescale of rewards is slower than the financial world has been used to, but maybe also they are changing. We'll help the world come out from a debt based economy model. As a by-product. :)

It's true that the first vendor succesfully introducing this might have an advantage. Or maybe it would need to constantly challenge itself, like Apple has been doing with the iPod line-up. Wouldn't it be great to see a similar wave happen in PRTs during the next 10-15 years?

My 2c.

Andrew F said...

Maybe I was unclear: whoever put in the first system could charge much higher rates when it came time to renew the service contract. It's like a drug dealer offering free samples, and once you've acquired a taste charging exorbitant prices. A city entering into such an arrangement would be in a very poor bargaining position at renewal time.

Anonymous said...

You are right. Pricing could be modelled that way.

But if the plan is to make lots and lots of operation, as is our plan, pricing can also be "predatory" from day 1. Meaning we'll deliver a technically superior system that's also price competitive with *existing' transport solutions. That's buses, mostly.

I'm seeing this also from the climate point of view and the speed we introduce transportation change in the world matters. Our business models must be modelled accordingly, to adapt for a very expansive period. We're modelling after McDonalds in that respect.

One thing. I guess all you guys are from the U.S. You need to be able to look beyond what would work there. What kind of business model works in still urbanising economies? What kind of business model will work from now till 2060 - and beyond?

cmfseattle said...

Idea: each merge point has a box with a simple computer. I'll call it a Merge Box. As vehicles enter one of the 2 lines approaching a merge point, they report to the MB, and the MB replies with a list of all other vehicles on the 2 lines. These comms can take place on a different frequency from the one the vehicles use for negotiating amongst themselves.

The overall network computer can request updates from MBs as often as traffic necessitates.

Dan said...

Dan the Blogger Responds from the town library in Canaan NH, where he will be busy building an experimental frameless structure to use as a garage/shop/place hang an electrical meter.

Well, gents, I’m going to be in and out of touch this month, mostly out.

Ryan, I just want to say that it really isn’t about the best way to accomplish an objective from a coding point of view. If a particular methodology produces a business model that that nobody wants to be part of, then it’s worthless, no matter how good it is from the software point of view. Two multinationals have poured millions into developing systems along the lines you suggest, only to throw up their hands and walk away. They concluded that, in the end, it was a bad business model. For the hierarchical control system that you advocate, do you have a business model? Not that I have a great one myself, but putting control further toward the vehicle enables future vehicle makers to compete by improving performance with newer and better models that, over time, solve the incremental performance stuff that is too complicated to put into any initial iteration. What is the motivation, business-wise, to ever improve your system or even adequately maintain it? Obviously money, but whose and how much? And how is this locked in to protect the customer (the city) from mismanagement or bankruptcy etc.?

Akauppi, correct me if I am wrong, but it seems to me that you are advocating a lighter, perhaps a bit slower version of PRT that some of us are envisioning. This obviously has huge ramifications for the infrastructure costs and flexibility. PRT, is, I think, really on the edge in this regard. With us folks in the U.S. needing to deal with ADA compliance, our vehicles become necessarily sized to where 300 kg or more will fit. Moving that kind of weight around quickly involves track that is pretty stout to install on a non-permanent basis. At what point, in terms of payload/speed/line capacity does your business model break down? Also, I guess I am unclear as to what is in this for the city.

BTW I was exploring a track system for putting in the medians of highways (with weighted feet that would taper into the breakdown lane) and in the process was working around the edge of the kind of “drop in place” track system needed for your business model. Actually, at some time in the future, I plan to post on it, including pretty close cost estimates, since all anybody has ever seen are estimates that include vehicles and stations.

Ryan Baker said...

It's not so much about coding as performance. Latency isn't something you can code around, it's a simple physical fact determined by the speed of light or as close to it as we can get our conductors.

But you're right, the business model is still more important, especially in the short term. I wouldn't agree that there's a benefit business model wise.

For one, the main determinant of business model is going to be track. Installing the track, maintaining the track, designing the track, and getting zoning and permission for installing and using the track will trump any software concerns. If every one mile of track has a $10,000 controller, that's not going to have much impact.

You seem to envision a system where the track is already present and vehicles manufacturers are free to independently sell their vehicles. But who would be buying and maintaining them? There are a lot of unanswered questions there, but I don't see how a control device is going to make any of them more complex.

Really, I believe the autonomous system you propose complicates that possibility even further. Vehicles have to cooperate, that is an absolute. It may not seem this way, but driving is a cooperative activity. Every law you follow (or loosely follow), every line you stay within is a cooperative act. Turning on a blinker, or not slamming on the breaks at random points is cooperative.

Not just in driving, but in things as simple as walking in an urban environment people establish norms of behavior, and it's only by these norms that collisions aren't even more frequent than they are. Look at some tourists in Chicago, New York or Hong Kong. They come from a place with fewer norms and in that environment they are a disruption even when walking on the street!

With autonomous vehicles there would have to be something similar, and unlike human norms, unless you have an AI waiting around, it's unlikely to emerge organically. I would suggest that the rules of interoperability will be less complex if they are a set of rules for how a vehicle will report out status, take commands, and act within a limited independent range than a system in which vehicles just burst data and do whatever they feel best.

Anonymous said...

Dan:
You're right. My PRT proposal carries 2-3 people per vehicle whereas others seem to go for 4-5 and room for a wheelchair in the middle.

ADA compliance is not a concern because our main target area is India and countries like that. I've not seen a single wheelchair in India. Seen some fairly crippled people, though. They would usually travel by a skateboard instead.

That being said, we offer a possibility of separate wheel chair fitting vehicles on-demand, for clients where this would be necessary.

The website is launching soon.

archillout said...

Я очень долго думал и рассуждал на тему персонального автоматического транспорта и пришел к выводу, что все эти идеи не лучше существующий личных автомобилей, управляемые человеком. Самое важное на сей день - заменить двигатели, которые не сжигают углерод, а в городах лимитировать жителей. Простите за мой русский.

Dan said...

Ryan, I hope my latest post makes my thinking a little clearer. I would assume that vehicles would be purchased by a transit authority, similar to the purchase of buses. The "assumption that the track is already there" is a response to the permanent nature of track and stations, compared to those who might install them and their contracts. Also, presumably at some point most PRT work will be expanding existing systems. I want to underline that I am not thinking of the best way to expedite getting a PRT system up and working. If that was the object, I would just license an existing control system. The Cabin Taxi system, if I recall, has even met U.S. safety requirements. I am rather looking a couple of decades out, to what would be a system architecture that would work world-wide and under almost all circumstances, from inner city to suburban to high speed for 100+ mile trips. The unanswered questions are the ones I am designing for. There is no argument that designing in all that versatility makes the control architecture more challenging. As to the concept of wayside control per se, I don't mind it if it can be structured like a removable building block that can be always be maintained by easily hired outside people.

Akauppi, You are right about trying to keep it light. When I first read the ADA requirements, I thought it was a PRT killer. I think 2 adults and a wheelchair (or scooter) or 2 adults and 2 children are the way to go (for permanent track track at least) I think that a control system ideally should feature variable headway, both for safety and to control the weight on the track.

Archillout, Translate please, or the comment will be deleted.