Factorio Forums

www.factorio.com
https://forums.factorio.com/

3-Belt Balancer design challenge

https://forums.factorio.com/viewtopic.php?f=202&t=25080

Page 1 of 1

3-Belt Balancer design challenge

Posted: Sun May 08, 2016 9:43 pm
by Frightning
So, based on the somewhat lengthy investigations I've done on belt balancers as part of this thread:
viewtopic.php?f=5&t=25008
It seems that is difficult (maybe impossible?) to design a 3-belt balancer that is universally throughput unlimited.
By universally throughput unlimited, I mean the following:
Given any integer k between 1 and n (where n=3 in our case), and full throughput on any k of the n input belts (and none from the rest). If only any k of the output belts will accept any throughput (and those that do accept the full belt's worth of throughput), then the balancer will allow for full throughput on all available output belts (all belts are same speed).

Essentially, what the property is articulating precisely is the idea that the balancer will never be a bottleneck if only some of the inputs and outputs are receiving/accepting throughput (assume for simplicity full throughput). It also assumed for simplicity that all belts are the same speed (use basic belts for ease of creating a testing setup).

So...the challenge is: To create a 3-belt balancer that satisfies the universally throughput unlimited condition. Meaning that there is no k in 1 to n and no combination of k input belts and k output belts such that the throughput of the balancer will be less than k saturated belts worth of items.

If you think you have a design that will satisfy the required property, please test it using the method I describe in this post:
viewtopic.php?f=5&t=25008&start=20#p157698
If it checks out, post the design in here asking someone else to test it to confirm that does actually work in all cases (you can reduce cases to check via symmetry to save time, but if it looks to be working, it would be good to try all possible combinations just to be sure).
One last detail about the testing: use only one item type for throughput (apparently multiple item types can change the outcome because of subtleties about splitter behavior).

Re: 3-Belt Balancer design challenge

Posted: Mon May 09, 2016 8:27 am
by golfmiketango
Frightning wrote:So, based on the somewhat lengthy investigations I've done on belt balancers as part of this thread:
viewtopic.php?f=5&t=25008
It seems that is difficult (maybe impossible?) to design a 3-belt balancer that is universally throughput unlimited.
By universally throughput unlimited, I mean the following:
Given any integer k between 1 and n (where n=3 in our case), and full throughput on any k of the n input belts (and none from the rest). If only any k of the output belts will accept any throughput (and those that do accept the full belt's worth of throughput), then the balancer will allow for full throughput on all available output belts (all belts are same speed).
I think you need many more definitions to formally specify what you are asking for in mathematically rigorous terms, if that's your objective. In fact, I think it's painfully difficult. For starters, I think the harder you look at it, throughput is not so easily defined in a way that matches our intuitive sense of the term.... just try! Then the notion of "accepting" a throughput needs to be formalized somehow. You need a bunch of sets mapping vectors to other vectors, a definition of a balancer, some calculus that permits but constrains belt-buffers, and probably a bunch of other crap I haven't thought of.

The problem is that the perception that bandwidth has been compromised somehow can fail to take into account the intrinsic buffering a device has within itself. For that reason, a solid specification of this challenge needs to take into account the idea that given a transition from a circumstance with, say, no input, to a circumstance with, say, a bunch of fully compressed belts, a device will "stutter" in various ways before settling down into the behavior that, in practice, we are interested in.

Re: 3-Belt Balancer design challenge

Posted: Mon May 09, 2016 10:02 am
by Frightning
golfmiketango wrote:
Frightning wrote:So, based on the somewhat lengthy investigations I've done on belt balancers as part of this thread:
viewtopic.php?f=5&t=25008
It seems that is difficult (maybe impossible?) to design a 3-belt balancer that is universally throughput unlimited.
By universally throughput unlimited, I mean the following:
Given any integer k between 1 and n (where n=3 in our case), and full throughput on any k of the n input belts (and none from the rest). If only any k of the output belts will accept any throughput (and those that do accept the full belt's worth of throughput), then the balancer will allow for full throughput on all available output belts (all belts are same speed).
I think you need many more definitions to formally specify what you are asking for in mathematically rigorous terms, if that's your objective. In fact, I think it's painfully difficult. For starters, I think the harder you look at it, throughput is not so easily defined in a way that matches our intuitive sense of the term.... just try! Then the notion of "accepting" a throughput needs to be formalized somehow. You need a bunch of sets mapping vectors to other vectors, a definition of a balancer, some calculus that permits but constrains belt-buffers, and probably a bunch of other crap I haven't thought of.

The problem is that the perception that bandwidth has been compromised somehow can fail to take into account the intrinsic buffering a device has within itself. For that reason, a solid specification of this challenge needs to take into account the idea that given a transition from a circumstance with, say, no input, to a circumstance with, say, a bunch of fully compressed belts, a device will "stutter" in various ways before settling down into the behavior that, in practice, we are interested in.
Indeed, there is some irregular behavior at the start, but as long as your run enough items through it (from saturated input belts), those irregularities will stabilize and it can then be observed as to whether or not the full throughput of the output belts is able to be supplied (in practice, for small balancers 1500 iron plates/belt was enough in my tests, I needed more for a very large design I tested most recently; 2100 was the more than enough there). It's pretty simple what I am asking for: Which is that if any (nonempty, but not necessarily proper) subset of the input belts are selected, and any same size set of output belts are selected, the output belts can be saturated indefinitely (after the initial irregularities stabilize).

Re: 3-Belt Balancer design challenge

Posted: Mon May 09, 2016 10:11 am
by Frightning
golfmiketango wrote: I think you need many more definitions to formally specify what you are asking for in mathematically rigorous terms, if that's your objective. In fact, I think it's painfully difficult. For starters, I think the harder you look at it, throughput is not so easily defined in a way that matches our intuitive sense of the term.... just try! Then the notion of "accepting" a throughput needs to be formalized somehow. You need a bunch of sets mapping vectors to other vectors, a definition of a balancer, some calculus that permits but constrains belt-buffers, and probably a bunch of other crap I haven't thought of.
Nothing that complex is needed, the balancer can be modeled fairly simplistically by a directed graph (the only important structural aspects of a balancer are the splitters and which belts those splitters are on and in what order they are encountered by material moving through the balancer). The throughput on a given belt between two splitters on that belt (or to output/from input) can be modeled by a normalized weighting 0 for no items, and 1 for full saturation, with numbers in between representing the proportion of current items/sec over maximum items/sec. It's really quite simplistic (This is how I was doing theoretical calculations for the other thread, btw).

Re: 3-Belt Balancer design challenge

Posted: Mon May 09, 2016 2:40 pm
by MadZuri
Here's something I designed for another project that you might be interested in:
3to3
You should be able to ignore the belt tier differences. Also, in the previous thread, all you need to do is place 2 8-belt balancers sequentially. I haven't gotten around to designing a blancer that allows full throughput from any lane to any lane with all other lanes clogged or empty. Any solution I tried was more complicated to just stacking 2 sequentially. I thought, "A solution exists, why bother?"

Re: 3-Belt Balancer design challenge

Posted: Mon May 09, 2016 3:07 pm
by Frightning
MadZuri wrote:Here's something I designed for another project that you might be interested in:
3to3
You should be able to ignore the belt tier differences. Also, in the previous thread, all you need to do is place 2 8-belt balancers sequentially. I haven't gotten around to designing a blancer that allows full throughput from any lane to any lane with all other lanes clogged or empty. Any solution I tried was more complicated to just stacking 2 sequentially. I thought, "A solution exists, why bother?"
I might try and create one of those on my test save to see how it performs. However, two 8-belt balancers in a row isn't going to fix the throughput problem, because if one of them is bottlenecking, then the whole thing is bottlenecking (it's an interesting question if it's possible to avoid the problem and if so, how).

Re: 3-Belt Balancer design challenge

Posted: Mon May 09, 2016 3:55 pm
by pieppiep
I'm not 100% completely sure I understand the problem.
You want a 4-to-4 balancer where you can disable 1 input and 1 output so you get a 3-to-3 balancer that outputs 3 full compressed belts when input 3 full compressed belts?

I've just tried it, my solution is a 4-to-4 balancer connected to another 4-to-4 balancer, disable 1 input from the first balancer, disable 1 output from the second balancer.
The 3 remaining output belts are very close to a 100% compressed.

Re: 3-Belt Balancer design challenge

Posted: Mon May 09, 2016 3:57 pm
by MadZuri
Well, when you get to your test save, try using two 8-lane balancers in row anyway. I've scienced it, and it worked for me.

Re: 3-Belt Balancer design challenge

Posted: Mon May 09, 2016 4:56 pm
by pieppiep
I just did the math for the 4-to-4 balancer.

When one input lane is disabled, one of the first splitters can output 2 full belts, the other outputs 2 half belts.
For the next 2 splitters, both get full and half belt so it outputs 3/4 belt. The other wants to output 2 times 3/4 belt but can only output on one, so it outputs one full belt so it can only consume 1 of the 1.5 belts and so it take 2/3 of the full belt and 2/3 of the half belt.
The one of the first two splitters that wants to give a full belt can't give more to the other belt so this one blocks it's input.
The other that gives 2 half belts can only output 2/3 of the half belt to the blocking splitter, so it increases it's output to the non-blocked splitter from 1/2 belt to 2/3 belt.
The non-blocked splitter now get a full belt and a 2/3 belt so it outputs 5/6 belt (83.3%).

When you place 2 4-to-4 balancers, the first one outputs 4 belts 3/4 full.
This gives 3/4 after each splitter.
Because one splitter is half blocked, it can only output 1 full belt, not the 2 times 3/4 it gets. This again makes it only accept 2/3 of the input.
But because it gets the same amount from both start splitters, the start splitters both start to give 1/3 input to the blocked and 2/3 to the unblocked splitters.
Both start splitters receive 2 times 3/4 belt so 1.5 total.
1/3 input for each start splitter is 0.5 belt to the blocked splitter and 1 belt to the unblocked one for each, so 1 belt total for the blocked one and 2 for the unblocked.

So the very few missing items on the belt I saw before were just probably some factorio floating point rounding errors.

Re: 3-Belt Balancer design challenge

Posted: Mon May 09, 2016 5:17 pm
by Frightning
pieppiep wrote:I just did the math for the 4-to-4 balancer.

When one input lane is disabled, one of the first splitters can output 2 full belts, the other outputs 2 half belts.
For the next 2 splitters, both get full and half belt so it outputs 3/4 belt. The other wants to output 2 times 3/4 belt but can only output on one, so it outputs one full belt so it can only consume 1 of the 1.5 belts and so it take 2/3 of the full belt and 2/3 of the half belt.
The one of the first two splitters that wants to give a full belt can't give more to the other belt so this one blocks it's input.
The other that gives 2 half belts can only output 2/3 of the half belt to the blocking splitter, so it increases it's output to the non-blocked splitter from 1/2 belt to 2/3 belt.
The non-blocked splitter now get a full belt and a 2/3 belt so it outputs 5/6 belt (83.3%).

When you place 2 4-to-4 balancers, the first one outputs 4 belts 3/4 full.
This gives 3/4 after each splitter.
Because one splitter is half blocked, it can only output 1 full belt, not the 2 times 3/4 it gets. This again makes it only accept 2/3 of the input.
But because it gets the same amount from both start splitters, the start splitters both start to give 1/3 input to the blocked and 2/3 to the unblocked splitters.
Both start splitters receive 2 times 3/4 belt so 1.5 total.
1/3 input for each start splitter is 0.5 belt to the blocked splitter and 1 belt to the unblocked one for each, so 1 belt total for the blocked one and 2 for the unblocked.

So the very few missing items on the belt I saw before were just probably some factorio floating point rounding errors.
Splitters don't behave quite like that, if they did, then a single standard 4-belt balancer would work flawlessly (or nearly so in actual gameplay) with 3/4 belts saturated and nothing on 4th belt, and 1 output belt backlogged with 0 throughput and the rest wide open (full throughput available). But in game experiments show that doesn't happen.

Re: 3-Belt Balancer design challenge

Posted: Mon May 09, 2016 5:45 pm
by pieppiep
I made a screenshot, is't what I explained exactly what you see here?

Re: 3-Belt Balancer design challenge

Posted: Mon May 09, 2016 5:47 pm
by Frightning
pieppiep wrote:I'm not 100% completely sure I understand the problem.
You want a 4-to-4 balancer where you can disable 1 input and 1 output so you get a 3-to-3 balancer that outputs 3 full compressed belts when input 3 full compressed belts?

I've just tried it, my solution is a 4-to-4 balancer connected to another 4-to-4 balancer, disable 1 input from the first balancer, disable 1 output from the second balancer.
The 3 remaining output belts are very close to a 100% compressed.
Technically the OP is asking for a 3-to-3 balancer, but if you have a 4-to-4 that works for any single input on any 3 of the 4, and pair out of the same 3 (same 3 being 3/4 inputs and 3/4 outputs) then it is effectively also a 3-to-3 design.

Re: 3-Belt Balancer design challenge

Posted: Mon May 09, 2016 6:08 pm
by Frightning
Tested the double 4-belt balancer (2 in a row), and it does appear to be near perfect throughput (rare errors that are likely rounding/simulation related).
Such as:
20160509105728_1.jpg
20160509105728_1.jpg (374 KiB) Viewed 25537 times
with 2/4 inputs and outputs used.
This is part of why I made this thread: I wanted more examples to challenge my conjecture(s) with.

Re: 3-Belt Balancer design challenge

Posted: Tue May 10, 2016 7:30 pm
by golfmiketango
The tendency of splitters to have a "side" preference makes this hard to solve without making your eyes bleed. It won't be pretty, but I'd wager, if we split lanes first, i.e., by using underground belts (a design was posted recently, that did this more attractively, by splitting and then side-loading the splitter outputs), and then output the resulting six dedicated "lane-belts" into any number of standard balancers, and then finally recombine the balanced output lanes via a "T" junction or other side-loading mechanism, we'll get the desired outcome.

Re: 3-Belt Balancer design challenge

Posted: Wed May 11, 2016 1:08 am
by golfmiketango
golfmiketango wrote:The tendency of splitters to have a "side" preference makes this hard to solve without making your eyes bleed. It won't be pretty, but I'd wager, if we split lanes first, i.e., by using underground belts (a design was posted recently, that did this more attractively, by splitting and then side-loading the splitter outputs), and then output the resulting six dedicated "lane-belts" into any number of standard balancers, and then finally recombine the balanced output lanes via a "T" junction or other side-loading mechanism, we'll get the desired outcome.
Hmm, turns out that the asymmetries of standard three-lane balancers cause unequal outputs (haven't entirely worked out why mathematically, but seeing is believing) when one of the output lanes is blocked... so back to the drawing board. But now I think I have a solution which will fix this... anyhow I'll test first this time :)

Re: 3-Belt Balancer design challenge

Posted: Wed May 11, 2016 7:50 am
by computerdruid
So the earlier comment about how to measure throughput got me thinking, so I put together a throughput measurement tool.

Blueprint here: https://gist.github.com/ComputerDruid/e ... f6a365a116

Built out of a few combinators. It's set up to run on Iron plates, but changing the first combinator will make it run on whatever you have most of.

It runs in a 3-stage cycle.

Stage 1: wait for count of plates to settle (5sec by default)
Stage 2: count plates (60sec by default)
Stage 3: display result (difference of count 2 and count 1), and drain counting chest (to keep values low and to let it run forever) (60sec by default)

You can change the time of each stage by adjusting the values of 1, 2, and 3 in the constant combinator (values in seconds)

Ideally, set stage 3 based on your inserter stack size bonus, since that controls how fast you can drain the counting chests.

The blueprint has a small belt loop to show how it is intended to be set up, but basically, connect smart chests to red, and the draining smart inserters to green, and set smart inserters to activate on 0=3.

To get result, wait for stage 3 (light should come on by the subtraction combinator) and hover over the subtraction combinator to see the yellow output. This should be the throughput of the system in items/minute.

My testing indicates that 386 plates/minute is approximately the throughput of one side of a yellow belt. It should be no problem to set this up to measure the throughput of your 3-belt balancers.

I built this on 0.12.33 (lastest as of this writing). YMMV when loading this in another version of factorio. I'd be happy to write up how this works more a little later if anyone is interested.

Re: 3-Belt Balancer design challenge

Posted: Wed May 11, 2016 9:36 am
by golfmiketango
I believe this
monstrosity
actually does the job.

The key difficulty to adaptive output-side balancing with splitters is that if we jam up one, but not both outputs of a splitter, everything goes out the other side. Classic 3-3 balancers operate by taking a 4-4 balancer, and then looping one input into one output. The inputs from the feedback loop are distributed four ways too effectively! Consider the a scenario where we have one saturated belt's worth of input, but only one backed-up output in a standard 3-balancer:

Code: Select all

(25%)->|-> (feedback)
(25%)->|-> (A)

(25%)->|-> (B)
(25%)->|-> (C)
If we jam (B), then (A) gets 25%, but (C) gets fully 50%. Unless we have nearly two or more fully saturated belts worth of input, no mechanism exists to ever cause 66% of the input material to wind up going into the top splitter, which is what would be required to compensate. To fix this, the above mechanism distributes all three inputs equally into three balancers, split equally between the first position, the second position, and the third position, and then merges them likewise at the outputs. I'm pretty sure this way all biases we might induce by jamming the outputs get equally distributed. It takes a pretty long time to reach equilibrium when the inputs change but this is expected.

Just to make things even more insane*, it also splits lanes and works on the lanes individually, merging and then side-loading every bit of material back into the lane it originated from. Here's a
blueprint string
* Just kidding. It makes things less insane, since we don't have to worry about the splitters playing musical lanes if we isolate them.

Re: 3-Belt Balancer design challenge

Posted: Wed May 11, 2016 10:34 am
by golfmiketango
computerdruid wrote: Stage 1: wait for count of plates to settle (5sec by default)
That's not nearly long enough. Try maybe 300 seconds if you want to capture any useful result.

Consider a standard 3-lane balancer: it has two basic structures, a 4-4 balancer and a feedback loop, of approximately the same length (let's pretend, exactly the same length, to simplify this). Let's supply this beast with a non-saturating input of n items per second, arbitrarily distributed across its inputs.

First nothing is in the feedback loop:

Code: Select all

0 items in feedback area, n items in non-feedback area
After each iteration, one quarter of the items from the non-feedback area in the previous iteration find themselves in the feedback area, so for the second iteration:

Code: Select all

n/4 items in feedback area, n items in non-feedback area
Third time around, the stuff in the non-feedback area fed another n/4 items into the feedback area, which replaced an identical number of items which moved out of it:

Code: Select all

n/4 items in feedback area, n + n/4 items in non-feedback area
Fourth time around, one quarter of the 5n/4 items in the non-feedback area, or 5n/16 items, went into the feedback area, and the n/4 items from the feedback area once again found themselves in the non-feedback area:

Code: Select all

n/4 + n/16 items in feedback area, n + n/4 items in non-feedback area
Fifth time around, all the n/4+n/16 items in the feedback area once again went into the non-feedback area and a new n items were admitted to non-feedback from the inputs as well; meanwhile, one quarter of the n+n/4 items in the non-feedback area moved into the feedback area (same as last iteration):

Code: Select all

n/4 + n/16 in feedback area, n+n/4+n/16 in non-feedback area
Sixth time:

Code: Select all

n/4^1 + n/4^2 + n/4^3 feedback, n/4^0+n/4^1+n/4^2 non-
etc...

Well the good news is that n/4 is less than n/2, so these sums will not run off to infinity. I'm not going to bust out the taylor series and find the actual values but we could -- the actual numbers are not terribly important: in equilibrium we know what the output is going to be -- it will equal the input, and we don't necessarily care what is going to be buffered in the device itself, just the behavior it exhibits, which we can likely reason out with simple algebra given the assumption that have reached an equilibrium between outputs and inputs and various in-game observations about which belts are jammed or flowing freely, our understanding of splitters, etc.

What we can observe without bothering to do any integrals is that, because these are discreet, this infinite sum busniess is actually an upper bound on what will in practice be slightly smaller numbers.

And since we can't split a single item, and it takes two iterations for an input to feed back via the loop, we need no more than roughly log4(n)*2t seconds to reach equilibrium, if t is the time in seconds for an item to make it from the back to the front of the device. Note that faster belts accept more items per second and therefore will not quite be proportionately faster to reach equilibrium across the range of inputs they accept. So, Back-of-the-napkin looks to me like: basically, after the input dynamics change, take item travel time from input to output in the device and multiply it by 15 and wait that long, or more, if you want to be sure the thing will be near equilibrium when you start measuring.
All times are UTC
Page 1 of 1

Powered by phpBB® Forum Software © phpBB Limited