开云体育

Dear JMRI users and developers,

In my topic entitled Scripts I was asking for help in a problem that arose from my drinking in advance for the skin of the bear as we say in my native language, when I was installing fewer sensors on my layout than the general practice was, in the conviction that their RailCom capability will make up for their small number.

Let me describe below how I imagine in general saving sensors, i.e. hardware at the expense of more sophisticated software. I wonder if you are, maybe in the long run, interested.

Blocks - by a block I am meaning here and in the sequel an irreducible section of track, electrically isolated from the rest of the layout where trains change their movement or, more generally, trigger some action -
form a?? g r a p h . A graph in the sense of mathematics is just a collection of objects, called the v e r t i c e s?? of the graph, together with a selection of certain pairs of vertices. If a pair of two vertices is selected, we say that the two vertices are joined (virtually) by an?? e d g e , or? a d j a c e n t.

The graph I have in mind has the blocks as its vertices and we join two such vertices by an edge if there is a route leading from either of them to the other, not going through any other block. Let us call such a route
m i n i m a l .

Next we are?? c o l o u r i n g?? our graph, in other words partitioning the vertices into groups - vertices belonging to the same group are said to be of the same "colour" - in such a way that two adjacent vertices invariably have different colours.

Now we are connecting blocks belonging to the same group electrically to each other and attaching to each group a single detector capable of RailCom. A RailCom detector can send more detailed reports than an ordinary occupancy sensor can, among other things also the decoder address of the locomotive staying in the block being monitored by the detector.

I state that such a system can be fully automated by a computer, provided that it knows where the trains are located at the outset.

In fact, suppose that Train is in Block1 connected to Detector1 and we want to move it along a minimal route to the adjacent Block2 connected to Detector2. We set speed, turn-outs, etc as appropriate. Since Detector1 is different from Detector2 by definition, when Train arrives in Block2, Detector2 changes its status, so when it first reports the arrival of Train (owing to its RailCom capability) the computer knows that Train has arrived in Block2. True that, as far as Detector2 is concerned, Train could be in any other block being monitored by it, but the route of Train being minimal, it can only be Block2. This way the computer can keep track of each train both in regard to time and location.

And we have only used as many detectors as there are colours and they may be much fewer in number than the number of vertices, that is the number of blocks! In general it is a hard problem to find the best colouring for large graphs, i.e. the one needing the fewest possible colours, but there are reasonable algorithms. For example, I leave it to the reader as an exercise to colour a graph with k+1 colours, if each vertex has at most k neighbours, i.e. k vertices adjacent to it. (Hint. Use the so called greedy algorithm: colour the vertices in an arbitrary order, in each step taking care of not violating the condition with respect to vertices coloured already.)

Summary. If we want to find every train based on the current state of detectors then, of course, we cannot do with less detectors than there are blocks and no saving is possible. The system I have been describing determines occupancy by the entire past, thus allowing, in cases, substancial saving.

The devil lurks in the details, another saying in my language. For instance, a faulty turn-out may drive Train to an unknown destination or we may want to allow other controllers intervening in the computer program. In this case we impose the stricter condition on the colouring that even second neighbours, I mean neighbours of neighbours be of different colours. (This second neighbour colouring is equivalent to ordinary colouring of the graph having the same vertices but joining two vertices by an edge if they are neighbours or second
neighbours in the original graph.) You easily see that no matter which detector, say Detector3 catches sight of Train first, there is a unique block, say Block3 connected to Detector3 Train can arrive in along a minimal route. The result is the same, except that in order to locate Train the computer has to be watching all the detectors of neighbouring blocks like Detector3, not just Detector2 and due to the stricter condition on the colouring we may need more colours. However, in the exercise not more than k^2+k+1, for each vertex has at most k^2 second neighbours.

A hardware related problem is that as far as I know a RailCom detector can only take care of two (or four?) mobile decoders at a time. This can be helped, if I am not mistaken, by cyclically disabling RailCom capability in all but two of the decoders in the blocks connected to the detector - this is just a matter of setting a configuration variable in the decoders, also made feasible by RailCom - allowing any number of trains, restricted only by the time factor. (CV writing by RailCom is said to be very fast.)

I feel that one way or other one should be able to overcome any other difficulty, as well, that may arise.

Gabor Halasz

Gabor,

Right now they are tracking down the issues in the code for the rest of the
reporters to work. It's just a matter of time to get it right. From the
discussion, it will be fairly quick as software goes. The talk points to
seeing where some things were missing due to other implementations being
focused on very specific cases instead of the usual JMRI idea of start with
the general case and then have implementations off of that. Sensors and
turnouts, very global concepts and then specific vendor connections tweaks
from that base idea. It seems the code is showing that reporters didn't grow
up that way.

Your description of how to deal with the reporters and sensors by matrixing
may be accurate to show the goals, but for just about everyone on this list,
if you could restate it using layout terms or examples, it would help
everyone greatly.

-Ken Cameron, Member JMRI Dev Team
www.jmri.org
www.fingerlakeslivesteamers.org
www.cnymod.com
www.syracusemodelrr.org

This is a very interesting area, and it’s great that you want to think about it!

You might want to look at some of the existing code.

In particular, some of the complexity of the Path class ( or ) exists because “Block” on many railroads can’t be topologically condensed to a point: They can contain turnouts, sometimes more than one, that can lead to complicated relationships between i.e. turnout state(s) (c.f. ) and possible routings through the trackwork. They’re not even commutative: A local railroad uses spring switches, so the specification from A to B is not the reverse of B to A.

The train-following code has to deal with the cases you mention (c.f. ) but also cases like “a sensor goes active and none of the neighbors show active” (c.f. ) or the converse, where two neighbors show active (c.f. ), with and without directional information.

JMRI is by no means robust in all this. I’m sure that new ideas and eventually new code would be greatly appreciated.

Bob

On Aug 29, 2018, at 6:25 AM, halasz <halasz.gabor@...> wrote:

Dear JMRI users and developers,

In my topic entitled Scripts I was asking for help in a problem that arose from my drinking in advance for the skin of the bear as we say in my native language, when I was installing fewer sensors on my layout than the general practice was, in the conviction that their RailCom capability will make up for their small number.

Let me describe below how I imagine in general saving sensors, i.e. hardware at the expence of more sophisticated software. I wonder if you are, maybe in the long run, interested.

Blocks - by a block I am meaning here and in the sequel an irreducible section of track, electrically isolated from the rest of the layout where trains change their movement or, more generally, trigger some action - form a g r a p h . A graph in the sense of mathematics is just a collection of objects, called the v e r t i c e s of the graph, together with a selection of certain pairs of vertices. If a pair of two vertices is selected, we say that the two vertices are joined (virtually) by an e d g e , or a d j a c e n t.

The graph I have in mind has the blocks as its vertices and we join two such vertices by an edge if there is a route leading from either of them to the other, not going through any other block. Let us call such a route
m i n i m a l .

Next we are c o l o u r i n g our graph, in other words partitoning the vertices into groups - vertices belonging to the same group are said to be of the same "colour" - in such a way that two adjacent vertices invariably have different colours.

Now we are connecting blocks belonging to the same group electrically to each other and attaching to them a detector capable of RailCom. A RailCom detector can send more detailed reports than an ordinary occupancy sensor can, among other things also the decoder address of the locomotive staying in the block being monitored by the detector

I state that such a system can be fully automated by a computer, provided that it knows where the trains are located at the outset.

In fact, suppose that Train is in Block1 connected to Detector1 and we want to move it along a minimal route to the adjacent Block2 connected to Detector2. We set speed, turn-outs, etc as appropriate. Since Detector1 is different from Detector2 by definition, when Train arrives in Block2, Detector2 changes its status, so when it first reports the arrival of Train (owing to its RailCom capability) the computer knows that Train has arrived in Block2. True that, as far as Detector2 is concerned, Train could be in any other block being monitored
by it, but the route of Train being minimal, it can only be Block2. This way the computer can keep track of each train both in regard to time and location.

And we have only used as many detectors as there are colours and they may be much fewer in number than the number of vertices, that is the number of blocks! In general it is a hard problem to find the best colouring for large graphs, i.e. the one needing the fewest possible colours, but there are reasonable algorithms. For example, I leave it to the reader as an excercise to colour a graph with k+1 colours, if each vertex has at most k neighbours, i.e. k vertices adjacent to it. (Hint. Use the so called greedy algorithm: colour the vertices in an arbitrary order, in each step taking care of not violating the condition with respect to vertices coloured already.)

Summary. If we want to find every train based on the current state of detectors then, of course, we cannot do with less detectors than there are blocks and no saving is possible. The system I have been describing determines occupancy by the entire past, thus allowing, in cases, substancial saving.

The devil lurks in the details, another saying in my language. For instance, a faulty turn-out may drive Train to an unknown destination or we may want to allow other controllers intervening in the computer program. In this case we impose the stricter condition on the colouring that even second neighbours, I mean neighbours of neighbours be of different colours. (This second neighbour colouring is equivalent to ordinary coluring of the graph having the same vertices but joining two vertices by an edge if they are negighbours or second
neighbours in the original graph.) You easily see that no matter which detector, say Detector3 catches sight of Train first, there is a unique block, say Block3 connected to Detector3 Train can arrive in along a minimal route. The result is the same, except that in order to locate Train the computer has to be watching all the detectors of neighbouring blocks like Detector3, not just Detector2 and due to the stricter condition on the colouring we may need more colours. However, in the excercise not more than k^2+k+1, for each vertex has
at most k^2 second neighbours.

A hardware related problem is that as far as I know a RailCom detector can only take care of two (or four?) mobile decoders at a time. This can be helped, if I am not mistaken, by cyclicly disabling RailCom capability in all but two of the decoders in the blocks connected to the detector - this is just a matter of setting a configuration variable in the decoders, also made feasible by RailCom - allowing any number of trains, restricted only by the time factor. (CV writng by RailCom is said to be very fast.)

I feel that one way or other one should be able to overcome any other difficulty, as well, that may arise.

Gabor Halasz

--
Bob Jacobsen
rgj1927@...

Bob,

This may look like a conversation by lunatics, one of them says something, the other answers something else, except that there is only one lunatic here, me, commenting on, though not grasping what an expert has to say.

The first step, and that is my main interest for the time being, concerns the hardware, namely to reduce the number of detectors as much as possible.

Once this has been achieved, in the second step one moves trains by the software. Here there is no essential difference in the scheme I am proposing compared to earlier automation: At any given time, all the information needed in the latter is also available in the former, except that its source is different. (Having only few detectors, their current state must be complemented by information gathered in the past.) Thus undoubtedly, in this second step the five codes you are referring to will be highly featuring in my scheme, as well.

Two of these five specific situations have occurred to me, too.

In the presence of one way track segments, one would guess that oriented graphs - when between two adjacent vertices there is also given a direction from one to the other - should be the right model. This seems, however, not to be the case, orientation makes no more saving possible, and as far as the graph is concerned such an edge should be considered an ordinary two way one.

However complex the rail structure should be within what I mean in my first post by a block, for constructing the graph the block should be shrunk to a point.

In the second step ( i.e. moving trains) the full complexity of these two cases regains, of course, its significance.

Ken,

But you are probably right in implying that the 0th step should to convince people of the practical benefit of this approach.

I did convince myself: for my 8 or 10 blocks I need only 2 detectors. Installing 8 or 10 instead, would call for one more detector module and lots of additional wiring. But it is a small layout of special structure, no interest to others.

Here is another proof of my lunacy, not knowing what I am undertaking: If I get 3 - 4 layout drawings I try to figure out how many RailCom detectors they need. The drawings should be as simple as possible, reflecting only the topology of the layout, displaying the ramification of rails, where blocks and sensors are but nothing more. There is also a limitation on the size as I would do that by hand for the time being, but I am unable to specify it in advance.

Or as a first approximation I would need the following three numbers that are easier to supply.

The layout is probably divided into blocks I was defining in my first post? here. How many of them are there?

For each block count its neighbouring blocks, i.e. where one can go to or where? one can come from without going through any other block. I want the maximal such number. In a fortunate case, one sees right away which block has the most neighbours.

How many sensors are there? If there are more than one in a block, count only one of them.

I would even be interested in having a statistics of a number of such 3-tuples to see how a "typical" layout looks like.

Gabor

I understand the concept which is by tracking movements from a known starting position you can determine position. And the reason for doing this is that you need fewer detecting devices than detecting position directly. Each detector needs to be more capable - detecting not just "a loco" but "loco id xxx" but that additional capability is inherent in RailCom.

But there's no free lunch. Fewer detectors means less redudancy and a greater reliance on hardware reliabity. Or equivalently bigger location errors from a single hardware error. It also means less flexibility in that it will be far more difficult to write bug free software logic for a generic layout than for a specific layout.

This approach might work very well in some parts of a layout where there are relatively few permutations and combinations (and therefore fewer starting states to specify and fewer potential hardware mishaps to factor into the logic) but I doubt its practicality for more complex or more generic layouts.

Thinking through things like this is truly what hobbies are all about for me. Thanks Gabor.

Jan Carr

There is another factor that has not been discussed.

A “train” is more than its locomotive with a RailCom enabled decoder. The caboose could be 20 feet away and the rolling stock could be sitting on turnouts. Occupancy detection has to account for the entire train, regardless of its size.

Dave Sand

Dave,

No matter how you handle this situation at present - by additional sensors, I presume - you can do the same in the scheme I am proposing, except that maybe you cannot save those additional sensors.

All I am saying is that you may combine certain sensors watching mobile decoders, in order to reduce their number.

Gabor

I have no intention to eliminate any feed-back, the system provides all the feed-back information as before under the conditions stated, achieving this with a reduced number of detectors sensing mobile decoders, not effecting others.

Dear Jan,

I have left to answer you by my right to the last word before being convicted
by the jury. Do not expect of me any well founded argument, in that follows you
will mainly be finding general wisdom, my feelings and taste.

I take your thoughts to be a first reaction giving appropriate orientation for
someone wishing to have a go at it. I would be reluctant to accept them as a
final judgement.

There are two extremes. A graph can be coloured by as many colours as its
size, by size I mean the number of vertices. This trivial colouring corresponds
to the generally accepted concept "at least one sensor to every block". Unless
the graph is complete - and complete graphs are not likely occurring as a layout
graph - fewer colours suffice, their least possible number is called the
chromatic number that may be much less than the size, allowing, occasionally, a
drastic reduction of detectors. Any number of colours, that is any number of
detectors between the chromatic number and the size is feasible. (For specific
purposes more should be installed - this topic has been touched upon in this
series - but I am restricting myself here, just as in my first post, to the
simplest case, one detecting position in every block.) I cannot rule out the
possibility but would be much surprised if - even in a highly complex layout -
the maximal number were the optimal. (I willingly concede that this may hold for
the other extreme, the minimum, as well.)

I made it clear that it was not a free lunch I was offering. But I was offering
a pudding to end the lunch with and the proof of it is in the eating.

As to your concrete objections, none of them seems to present insurmountable
difficulties.

Bugs seem to be inevitable in a software, the more sophisticated it is, the
more so. For fear of them, no railroad automation would have come to life, in
the first place.

On the other hand, I am not at all sure that my scheme would call for much
additional sophistication. The first thing is to decide which blocks should
be watched by RailCom detectors and how to group them and add a single detector
to each group. There are ready-made computer programs for colouring a graph,
but you may do it manually, taking your specific needs into account. Next, when
it comes to actually moving trains, you are faced with the same problem with the
same feed-back information available. The only difference is in the way this
information is collected. This is a matter simpler than and independent of train
movement and I feel possible bugs could easily be located and corrected.

It is true that a detector will be responsible for a larger area. Suppose we
get rid of half of the detectors, then typically two blocks are being watched
by a single detector. Let F/year be the failing rate of a detector, I mean
there occur F failures in a year on the average. If either of the two blocks
has its own detector then it amounts to 2F failures for the two blocks together.
In my case the only detector fails F times, but then both blocks are effected
that again means 2F failures for the two of them. Which is the better and which
is the worse? (In another possible modeling I have thought of, calculating
the cost of replacing faulty hardware my scheme, needing fewer detectors, is
the winner definitely.) Not to mention that we are talking about purely
electronic devices and I guess it is not them that cause the most problems in
this respect.

As no one even tastes my pudding, for the time being anyway, our dispute remains
on a purely theoretical plane.

For all this, I consider your approach positive and I thank you for your
interest.

Gabor

Although I understand the graph-coloring argument itself, I don’t see how it applies.

Consider this case: Block B, with neighbors A and C, and block Y, with neighbors X and Z, are connected to a single sensor S. Now we start with A and X showing occupied, all others including S not occupied. Train 1 is in A and Train 2 is Y.

That’s a _completely_ general setup, applicable to any layout topology.

Now sensor S goes active, hence indicating that B or Y or both are now occupied.

Where are the trains? How do you know?

Bob

On Sep 5, 2018, at 1:46 AM, halasz <halasz.gabor@...> wrote:

There are two extremes. A graph can be coloured by as many colours as its
size, by size I mean the number of vertices. This trivial colouring corresponds
to the generally accepted concept "at least one sensor to every block". Unless
the graph is complete - and complete graphs are not likely occurring as a layout
graph - fewer colours suffice, their least possible number is called the
chromatic number that may be much less than the size, allowing, occasionally, a
drastic reduction of detectors. Any number of colours, that is any number of
detectors between the chromatic number and the size is feasible. (For specific
purposes more should be installed - this topic has been touched upon in this
series - but I am restricting myself here, just as in my first post, to the
simplest case, one detecting position in every block.) I cannot rule out the
possibility but would be much surprised if - even in a highly complex layout -
the maximal number were the optimal. (I willingly concede that this may hold for
the other extreme, the minimum, as well.)

--
Bob Jacobsen
rgj1927@...

Bob,

I am starting off from the assumption that

Train 1 is in A and Train 2 is Y.

is a misprint for "Train 1 is in A and Train 2 is in X". Even then you may think of two cases. Recall in both of them that S is a RailCom detector, it does not only go active, it can also recognize Train 1 and/or Train 2.

Case 1. We (by our computer) control the trains and we want to move Train 1 into B and Train 2 into Y. When S first catches sight of Train 1 then it is in B. When S first catches sight of Train 2 it is in Y. If S e.g. keeps seeing Train 1 when it first catches sight of? Train 2, as well, then both B and Y are occupied by Train 1 and Train 2, respectively.

Case 2. Trains do not obey us. This case is shortly discussed in the last but second paragraph of my post starting this topic. If it is S that, among all the detectors, first catches sight of Train 1 then it is in B. In fact, suppose that it is in another block, say B 1 attached to S. Then B 1 is a neighbour of A and A is a neighbour of B, hence B and B 1 are second neighbours of each other connected to the same detector S but in Case 2 we have agreed to attach different sensors to second neighbours. Similarly we see when Train 2 first arrives in the area of S, then necessarily in Y and the same way as in Case 1 we can see when both B and Y get occupied by the two trains.

In this context you are quoting a paragraph in my answer to Jan. Let me try to avoid a possible misunderstanding.

In this paragraph I am only pointing out that one may install any number of detectors greater than the chromatic number, granting that choosing the fewest possible detectors might not be the best solution? (but expressing? my feeling that, considering all possible angles of the problem, some saving will still be advantageous).

Gabor

EXAMPLE

I am glad to see the topic has not ended with what I thought to be my last word. I recall now Ken was asking for examples. There is one in my other topic Scripts but it is not readily seen to be a special case. Here is a simple example that can directly be understood without any general theory.

The layout is just a circular track divided into four blocks A, B, C, D in this order in clockwise direction. Two trains are following each other in clockwise direction.

At the outset Train 1 is in B and Train 2 is in A. First Train 1 goes to C and once it reaches C it stops. Then Train 2 goes to B and once it reaches B it stops. Then Train 1 goes to D and once it reaches D it stops. Then Train 2 goes to C, Train 1 goes to A, and so on cyclically for ever.

It is easy to automate this movement by connecting ordinary occupancy sensors - I mean ones having only two states, active and inactive - to A, B, C, D each.

The graph has four vertices: A, B, C, D and four edges: between A and B, B and C, C and D, D and A. Such a graph is called, not surprisingly, a circle. It can be coloured, as any circle having an even number of vertices, by two colours, painting every second vertex red and the remaining ones blue.

And in fact, having two RailCom detectors, Sensor 1 attached to A and C, Sensor 2 attached to B and D we can do the same automation instead of the four sensors as before.

We start Train 1 and when Sensor 1 first sees it we know it has just arrived in C and stop it. (If Sensor 1 were an ordinary occupancy detector it could not do that for its state remains active all the time since Train 2 is still in A.) Then? we move Train 2 to B and when Sensor 2 first sees it we stop it. And so on.

Gabor