Topic: Congestion Competition
Tibor |
Posted at: 2018-05-30, 07:43
I had similar idea. We will see what ypopezios will come with Top Quote |
einstein13 |
Posted at: 2018-05-30, 12:30
Surprisingly, I came to the same idea, but I am not convinced that it is the best one. For sure the easiest one and the simplest to apply. But it won't solve the problem. Congestion will happen even faster (circle edition). Half-congestion will not happen any more. Circle congestion have to be solved somehow different. And it doesn't have to be solved by full change of the current algorithm. @ypopezios For example algorithm above (limit of wares near flag) can be seen by:
So if you are thinking about algorithm based on flags, it is OK, but probably we will have to transform it. And it is not a problem . einstein13 |
king_of_nowhere |
Posted at: 2018-05-30, 15:04
Why not? I think it should solve the circle congestion. Circle congestion happens because all wares on flag A are scheduled to go north, and carrier must bring there a ware from west to east, but can't and won't move anymore. Repeat it for the three corners, and you have circle congestion. But with this change, there will always be a place for a ware set to go west to east, so the road will never stop entirely. take the example the worker carrying hardwood would like to set the hardwood at the flag, but it can't because the flag is full of stones. IF there were a couple spots reserved for other wares, then that worker could carry hardwood to the flag. Similarly, the worker carrying stone could set the stone to the flag, and th eworker carrying logs could set the ware to the flag. Now, this won't allow the hardwood to immediately move again: the carrier that must take hardwood still has a stone in hand, and can't swap it for hardwood because that slot is reserved for wares not going north, and the stone is. But as carriers are moving again wares, the carrier that is carrying a stone in the three-step road will move again, and take out a stone. so the traffic would flow again. I see it's still not a perfect solution: the capacity of the carrier adjacent to the southwest warehouse to take up hardwood depends on him dropping the stone. the road could stilll get congested, if not as irreparably as in the example. But maybe a second solution could be to instruct carriers to not pick up wares if there is no place for them at a flag. that way the carrier could still move other wares in the other direction. I think those two measures taken together should fix everything as best as possible. the only traffic still remaining would be the one with too many wares in a bottleneck, and there's no way around that. Top Quote |
ypopezios Topic Opener |
Posted at: 2018-05-30, 15:12
@einstein13 Perspective matters.
So don't bother with other perspectives, cause flags is the way to go (and there are also other reasons, not directly related to congestion, e.g. improving routing).
As I said, you are right to think in terms of what flags accept, reserving some of its capacity. But check again the simplified version of the half-full congestion: The logs which arrive at the crossroad-flag (coming from the HQ), after that point they have the same direction with existing horizontal traffic. So a direction-based rule would not change their hopeless situation. Still this is the right ...direction to look for a solution, just find a better rule for serving/not-serving a ware. More specifically, I'm considering controlling that through a flag method Top Quote |
king_of_nowhere |
Posted at: 2018-05-30, 16:36
I assume you are referring to And yes, it would not really fix the matter. Now, teaching the carrier to not pickk up a ware if there isn't free space at the next flag would help with that, definitely. Assuming the logs are going east, as soon as the carrier on the long road picks up a hardwood, there is a free space to deliver a log. Still, that case is much better than the full circle congestion: wares are still moving. with time, that would solve itself. wares are still moving. in that case, the main problem is movement through a bottleneck, and there really isn't a true fix to that. Top Quote |
ypopezios Topic Opener |
Posted at: 2018-05-30, 19:55
We have to avoid circular reasoning ourselves. So here is the proper order of mandatory things in all kinds of congestion:
Therefore, although isolated ideas are always welcome, any realistic solution should take the above into consideration, and then focus on the last point, in particular the avoidance part of it (which is much easier and less costly). To avoid something, it means before any action to make the question: "By doing that action, how high is the risk of facilitating what I instead want to avoid?" In our case, wares/carriers should ask next flag: "Is coming to you safe enough concerning congestion?" (By the way, I have already implemented that part, which was not as simple as it sounds, because of the overall poor design of the system.) And the flag has to be smart enough to answer accordingly (the implementation of this is in progress):
Mind that with multiple roads and carriers there is some risk even in the case of an empty flag (it can suddenly get flooded from five roads with a total of 10 wares, thus getting at full capacity of 8 in a single moment, plus 2 carriers still waiting to get served, while waiting for the sixth road's carrier to come and give a minimum relief of 1, so staying congested for a considerable time), but we don't want to make the system too conservative. In any case, we are not talking here about a perfect solution (this is just an intermediate improvement, until the routing system gets smart enough to also consider traffic). Top Quote |
einstein13 |
Posted at: 2018-05-30, 23:09
Yes, you're right. I haven't thought of that. Also applying this will allow us to solve other problems, because we will have a capacity for other possibilities. Good point king! When I was thinking about stopping the carrier before he will take a ware, I don't think that it is a good idea. It can cause other congestions when you have two roads with different capacity (length), one can be never run while the another one will work always. That is why the first design of the game contains "always pick up a ware". My question is: should we allow the carrier to put the ware back to the flag? Because this is the main reason of all congestions.
You haven't got the point of transformation. Perspective doesn't matter from about 100 years. There are are many proofs of that .
I know that it is not obvious, but all the algorithms can be changed between those points of view. I don't know how the system is currently designed, but we don't have to change that. From my point of view, ware perspective is the best one, because most of the searches I would like to do is along the wares list. Also the path is assigned to the ware. The decision about how the path should look like is about big search along the data we have. It is not easy. I don't know how the system based on flags should work, but I know that they can be treated the same way. How? Imagine that you have exact function that will change one dimension to another with a bit complicated equation (ex. y = sin(x)+2x). So simple function z = 2y+3 will be changed to z = 2*sin(x) + 4x + 3. It is not as simple as it was before. But sometimes after transformations you get simple equations instead of complicated ones (for example Laplace transform: https://en.wikipedia.org/wiki/Laplace_transform). I don't know how your idea works, but for sure it can be transformed to any point of view. einstein13 |
ypopezios Topic Opener |
Posted at: 2018-05-31, 01:50
If a carrier should put the ware back to the flag, then he shouldn't have taken it from the flag in first place. Not to mention that meanwhile another carrier could have put his own ware there, leaving the first carrier in the same situation as before.
Of course not. For the reasons which enable congestion, read again the bold words of my previous post. And from those we can only change the last one, so currently the main reason of congestion is that we do nothing to avoid it. Now is time to do something about it, and flags can do it better than the rest.
Perspective matters and you are a living proof of that, as your mathematical perspective misleads you in this effort. The sooner you realize it, the sooner you will start using the best perspective for the given case. I explain the reason below.
Two algorithms may happen to produce the exact same results, and still one of them to be totally useless for any practical application. Mathematicians are happy with just proving their equivalence. But programmers have to care about their internals too. There is a simple algorithm that solves just about everything: "Try all combinations and measure which is the best." It is actually used in some real cases. But in most cases it is a bad algorithm, no matter it can produce correct results after some millennia of running. Discussing variations of that algorithm is a waste of time. If we want to do some useful work, we need a useful perspective, not any perspective that simply happens to apply. On another example, think about a maze. You can try solving it from inside it, or you can try solving it from above it. Both perspectives can solve it. But one of them is clearly better. In our case, flags have a better point of view. You may call all perspectives equivalent, but one of them is better. And being better matters.
"Perspective" means "point of view". Many times people disagree because their points of view differ. So before agreeing on the matter at hand, they have to agree on their perspective.
The wares list is long and searching in it wastes many resources. In general, searching is expensive. Some times it is unavoidable, but other times there are better alternatives.
This is one of the poor decisions of Widelands' design of code, and we have to live with it for some longer. Wares should store no information, other than their type and their destination. There are many reasons for that. The simplest reason is that wares are many. The more instances of something, the less those instances should contain (both in data and in code). Not only that saves resources, it also makes things easier.
Hopefully, after reading this post, you now understand that they cannot be treated the same way, unless maybe from a purely mathematical point of view. Such a point of view can be useful in the development of theories, but here we are after a practical solution.
That's the whole point of transformations, to make it simpler to find a solution. In our case, for a solution to the congestion problem, we have to transform into flag perspective.
Feel free to transform it afterwards. For now we have to make it work. Top Quote |
GunChleoc |
Posted at: 2018-05-31, 11:12
Maybe we should keep the design discussion just separate from the implementation discussion? First we need to understand what we need and find a concept that works, then map it to how it can be implemented later. Congested flags could increase the weight in our A* function, so that they will eventually become expensive enough to have wares pick a longer path that is not congested. Would that help? Busy indexing nil values Top Quote |
ypopezios Topic Opener |
Posted at: 2018-05-31, 12:36
In cases of congestion, not much. Alternative paths don't always exist. And when they exist, they can form their own circles of congestion. Moreover, by the time full congestion is reached, the carriers at the circle are no more able to serve any path at all and they need external help, so it is too late for redirections, unless new roads are added. But adding new roads (like the AI tries to do) isn't always possible. Still A* is an implementation detail, so it should stay out of the design discussion, right?
As you just noticed, this is easier to say than to do. In theory, non-programmers cannot participate in an implementation discussion. But in practice, the more they are aware of implementation details, the more useful their input is in the design discussion. I could skip both discussions myself and just produce a solution on my own, having it accepted simply because it would be the only implemented one. But that would be just an isolated improvement and wouldn't help much in the longterm. Increasing people's awareness of what is going on behind the scenes (in simplified terms) and engaging them in the process, prepares the ground for bigger changes which will need much help with testing and other kind of feedback. It also provides confidence that changes are reviewed in multiple levels by multiple people. Finally, it provides material for documenting the game's behaviour for future reference or use in the manual, the FAQ, the tutorials etc. Top Quote |