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
