Avoiding building deadlocks

[ssilk]

With the block signals you are very fast in the problem to build deadlocks. This won't change, even if you path signals, because even there it is possible to build nice deadlocks.

So I suggest a mechanism, which checks for deadlocks.

I think to some kind of tool, which must be researched first. You can use this tool to touch rails and if you do that, it begins it's check.

The check works more or less like so:

It checks, which types of trains are sitting in the current network and how many. Then it uses this information to simulate all possible situations of incoming trains into this block and outgoing from this block.

If one of this situation leads to a deadlock, it stops and tries to figure out the "reason", why this happens and translates this into user understandable language. Optional plus something he can do to remove this problem in this situation.

In the ideal case the player will hold the tool on a crossing and game says "Will cause deadlock", and shows up in transparent the trains-situation, that causes the deadlock. You can switch to "next", to see the next cases, if you think, the current is too rare.

This can be used also to check, if trains can reach any train stop, cause the simulation technically needs to look for each train and each train stop, if the train can go to this stop or can come from this stop, to check, from which direction trains can come.

[The Lone Wolfling]

Unfortunately, deadlock detection in this fashion is in NP, and as such has no known polynomial-time algorithm. In other words, it's slow.

You have to try all lengths of trains that exist on all entrances and exits to/from the block. If you have 4 different length trains and 15 entrances / exits to/from the block, which is within the realm of feasibility for a large station, you'll need to try a billion (!) cases.

And it's actually worse than that. I was thinking about if I could convert the problem into an ISAT problem, and as it turns out you cannot even examine it at just the block level. You have to consider all crossings too. And worse than that, you need to consider which arrangements of trains can and cannot actually happen, given the current state of all trains. (Think of an oval track with 4 trains on it, A, B, C, and D. There is no way for A and C to be adjacent. If there's a deadlock that requires this, it cannot happen.) Ditto, you need to consider which arrangements of trains will not happen given the current train pathfinding.

[ssilk]

Unfortunately, deadlock detection in this fashion is in NP, and as such has no known polynomial-time algorithm. In other words, it's slow.

I know. It has not to calculate all possibilities through.

You have to try all lengths of trains that exist on all entrances and exits to/from the block. If you have 4 different length trains and 15 entrances / exits to/from the block, which is within the realm of feasibility for a large station, you'll need to try a billion (!) cases.

I mean with a normal train setup, the possibilities are quite limited. It has to calculate for any train, if he can come from any train stop to any entry of the "junkction" or block or whatever and if a train can drive from any rail of the junction to any train stop. For any found possibility, it can then mix all other found combinations and simulate what happens, if two or more trains will drive into/out of the junction at a time. It has to simulate until all trains have left the block.

It needs not to calculate all possibilities. It can estimate. Take the ugliest cases only, which are in general about using all trains. Lets say we reduce that to 100 tries only. If there is one situation, which leads to a problem, but the other 99 are ok it might show the block as "yellow". But in another case there are 50 situations. That will lock much more probable and it shows then "red".

And it's actually worse than that. I was thinking about if I could convert the problem into an ISAT problem, and as it turns out you cannot even examine it at just the block level. You have to consider all crossings too. And worse than that, you need to consider which arrangements of trains can and cannot actually happen, given the current state of all trains. (Think of an oval track with 4 trains on it, A, B, C, and D. There is no way for A and C to be adjacent. If there's a deadlock that requires this, it cannot happen.) Ditto, you need to consider which arrangements of trains will not happen given the current train pathfinding.

I admit, I didn't thought completely through it. For me also a 10% solution would work. Because the solution is thought especially for beginners, that they can learn, under which circumstances a junction may fall into deadlocks. That gives no guarantee! In the beginning of your rail network this is a solvable problem and later it is only somthing, which is "by chance".

Which is no problem, cause deadlocks always happens by chance.

[DerivePi]

Alternatively, program your trains not to smash into each other. Then you don't have to even bother with signals. We could call this researchable technology "Sudden Deacceleration Avoidance"

[The Lone Wolfling]

It has not to calculate all possibilities through.

Actually, yes, in the worst case it does, at least up to a constant. That's what being in NP means.

I mean with a normal train setup, the possibilities are quite limited.

Depends on what you mean by "normal". The 4/15 example I gave is from an actual block in one of my worlds.

It has to calculate for any train, if he can come from any train stop to any entry of the "junkction" or block or whatever and if a train can drive from any rail of the junction to any train stop. For any found possibility, it can then mix all other found combinations and simulate what happens, if two or more trains will drive into/out of the junction at a time. It has to simulate until all trains have left the block.

This doesn't change the algorithmic complexity. Let me put it this way: finding a polynomial-time solution for any problem in this category is one of the single hardest unsolved problems in computer science. (Although, that being said, I don't actually know if one can translate an arbitrary NP problem into a "does this train track have a deadlock" problem. I presume so, but I have not proven it.) As such, I am going to take any proposed solution with a grain of salt.

The proposed way you mention is not going to be any faster, algorithmically speaking, in the worst case, than the approach I mentioned.

It needs not to calculate all possibilities. It can estimate.

Oh, ok. So now you're talking about approximate answers.

Here's the problem with approximate answers for this problem, in general. Either you will be overly conservative, and say that there may be deadlocks where there isn't. Or you will be overly optimistic, and say there won't be deadlocks where there may be. Finding a close approximation of the first kind is really difficult. Not impossible, but difficult. (We already have simple approximations. But again, they will sometimes think that situations that cannot cause deadlocks will indeed cause deadlocks.)

Finding an approximation of the second kind, as you suggest, is a really bad idea. Partially because it is unintuitive - if such a tool was implemented I guarantee there would be bugs posted routinely about "this track deadlocked even though the tool said it wouldn't". But the other problem is that the search space is just so large that I very much doubt that in all but the simplest cases you'd get any useful information at all.

Which is no problem, cause deadlocks always happens by chance.

Again, see above.

[ssilk]

Perhaps I haven't explained this enough and have been going to deep into details: A deadlock happens by chance. Even if we found cases, which have a very big chance of deadlocking, it might never happen. And the other way around.

This suggestion is not about calculation exact chances. Or any chance, but some (the worst cases). And only in simple cases any.

It is not needed to think about every possibility. It's some simple tests which reduce the problem much. Following this philosophy I'm very sure, the devs find ways to reduce the the afford quite much.

[Tinyboss]

This doesn't change the algorithmic complexity. Let me put it this way: finding a polynomial-time solution for any problem in this category is one of the single hardest unsolved problems in computer science. (Although, that being said, I don't actually know if one can translate an arbitrary NP problem into a "does this train track have a deadlock" problem. I presume so, but I have not proven it.) As such, I am going to take any proposed solution with a grain of salt.

The fact of it being NP, by itself, doesn't mean that it's intractable for input sizes encountered in Factorio--it only means it gets too hard "eventually". Depending on the algorithm (and I know nothing about deadlock detection algorithms, so maybe someone else can chime in here), "eventually" could be right away, or it could be when the input size gets above 10^20. Plenty of NP problems are solvable in milliseconds on a modern PC for practical input sizes.

[The Lone Wolfling]

The fact of it being NP, by itself, doesn't mean that it's intractable for input sizes encountered in Factorio--it only means it gets too hard "eventually". Depending on the algorithm (and I know nothing about deadlock detection algorithms, so maybe someone else can chime in here), "eventually" could be right away, or it could be when the input size gets above 10^20. Plenty of NP problems are solvable in milliseconds on a modern PC for practical input sizes.

As I said before, it'll end up being intractable for problem sizes that I have encountered before in Factorio. And I know I'm not the most train-crazy person out there. One of the things about NP problems is that you end up hitting a "hard wall". Multiplying your speed - either through better hardware or a better algorithm - only gains you a constant increase in problem size that you can solve.

Of course, this assumes that it is actually a problem in NP. But it is, as you can encode the subset sum problem as a deadlock problem. (Have a track with station M. Then set up a series of segments before that where 1 segment can hold a train with a length of 1, 2 segments can hold a train with a length of 2 or two trains with a length of 1, and so on. Have a bunch of trains on stations at the start of this track all trying to go to the station at the end, such that they can feed into it in any order. Then set up a "detector" segment that will deadlock iff there is indefinitely a train at segment S but not at segment S+1. The only way the detector segment can deadlock is if there is some subset of the lengths of the trains that sums to S.)

[Tinyboss]

One of the things about NP problems is that you end up hitting a "hard wall". Multiplying your speed - either through better hardware or a better algorithm - only gains you a constant increase in problem size that you can solve.

Yes, I understand about exponential time. I think you're confusing NP with EXPTIME, since even polynomial problems are also NP (it doesn't stand for "not polynomial"). My question was essentially "what's the exponent?", since a tiny exponent is fine if the input size isn't huge. That's really the issue here, not whether EXPTIME is the best we can do for it. I take your word for it that the exponent makes this problem intractable in this setting, and in that case I have to read Ssilk's posts more carefully to understand what he's proposing.

[The Lone Wolfling]

I think you're confusing NP with EXPTIME, since even polynomial problems are also NP (it doesn't stand for "not polynomial").

Replace "NP" with "NP-complete", then. (As it's "easy" to reduce it to a BSAT problem, and it's possible to reduce a subset sum problem to a deadlock problem.) It's a common misusage of mine - I tend to use NP to refer to things that are in NP but haven't been shown to also be in P. My apologies.

My question was essentially "what's the exponent?", since a tiny exponent is fine if the input size isn't huge.

True. I finished a quick implementation of the simple version (read: no trying to figure out how trains interact) of a deadlock->BSAT translator (for minisat), and the aforementioned case didn't complete in 5 minutes, whereupon I killed it. So it's something that is decidedly non-trivial. It may be doable regardless, and/but if so, it'll require better minds than me. (This is not particularly surprising.)