Latest Posts

Topic: Congestion Competition

Tibor

Joined: 2009-03-23, 23:24
Posts: 1377
Ranking
One Elder of Players
Location: Slovakia
Posted at: 2018-05-30, 07:43

king_of_nowhere wrote:

I have an idea that could fix those worst cases with little impact: train flags to not accept more than 3-6 wares going in the same direction.

I had similar idea. We will see what ypopezios will come with


Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1118
Ranking
One Elder of Players
Location: Poland
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
As I understood your ideas, you want to "see" the world from flag point of view. From mathematical/physic world I know that every time we have a transformation between "points of view", we can create the same equations for both situations. So: because we have a logic transformation between flags/wares/roads/carriers, we can create an algorithm for all of them that will work in the same way.

For example algorithm above (limit of wares near flag) can be seen by:

  • Flag: I can't allow to put more wares with special condition
  • Ware: don't put me (I have special conditions) there
  • Road: hold on (special conditions), don't move the ware there
  • Carreir: I can't put it there, because special conditions occurred

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 face-smile.png .


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top Quote
king_of_nowhere
Avatar
Joined: 2014-09-15, 18:35
Posts: 1668
Ranking
One Elder of Players
Posted at: 2018-05-30, 15:04

einstein13 wrote:

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.

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

Widelands Logo

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
Avatar
Topic Opener
Joined: 2018-04-20, 00:22
Posts: 220
Ranking
Widelands-Forum-Junkie
Posted at: 2018-05-30, 15:12

@einstein13

Perspective matters.

  • Ware-perspective is not the best, cause each ware is temporary and only bothers with its own routing. We could design some kind of competition between wares, but competition is not the optimal solution for the overall system (check real-life traffic-jams for a quick proof).
  • Road-perspective is not the best, cause each road can only "see" 2 flags and 2 carriers.
  • Carrier-perspective is not the best, cause each carrier is currently bounded within a single road, thus inheriting the road's limitations, plus being unable to handle more than one ware per time.
  • On the other hand, flags can "see" up to 6 roads, as well as their own queue of up to 8 wares, so out of the four perspectives this is the most informed one. Plus flags have direct access to their queue (everybody else has access only through flags), which is currently our ultimate measurement of traffic and the most reliable source of warning for a coming congestion. Moreover, they could hold traffic information over time (I don't consider that for the coming fix, but I mention it as a further clue that this perspective is the right one).

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).

king_of_nowhere wrote:

train flags to not accept more than 3-6 wares going in the same direction

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 destination_flag::allow_ware_from_flag(ware, source_flag), which will return a true/false answer. What exactly goes inside (i.e. the best criterion) is still being researched.


Top Quote
king_of_nowhere
Avatar
Joined: 2014-09-15, 18:35
Posts: 1668
Ranking
One Elder of Players
Posted at: 2018-05-30, 16:36

ypopezios wrote:

king_of_nowhere wrote:

train flags to not accept more than 3-6 wares going in the same direction

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 destination_flag::allow_ware_from_flag(ware, source_flag), which will return a true/false answer. What exactly goes inside (i.e. the best criterion) is still being researched.

I assume you are referring to

Widelands Logo

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
Avatar
Topic Opener
Joined: 2018-04-20, 00:22
Posts: 220
Ranking
Widelands-Forum-Junkie
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:

  • High traffic. It means a bigger number of wares than some critical value. A few wares cannot challenge a road-configuration, no matter how inefficient it may be. High traffic will happen from time to time, because wares don't get teleported and the road-system changes dynamically. This is part of the game and not expected to change.
  • Bottleneck. It means an intermediate point of wares accumulation (thus not a warehouse). Without a bottleneck, high traffic moves smoothly, no matter if its pace is slow. Bottlenecks will happen inevitably, because space for roads is limited in only two dimensions and both of them are also finite. This is also part of the game and not expected to change.
  • Denial of service. It means a permanent failure to serve some wares. If flags have infinite capacity or if traffic redirection is possible, wares are still served, no matter if their service is of low quality. Denial of service happens only in poor road-configurations, that are not well-thought in advance, which is the case for the AI and will remain like that for a long time. Denial of service is also and will remain a reality, as long as Widelands' road-system is based on flags. This thread has proved that it is not hard to reproduce, even with just three buildings and a few normal roads.
  • Lack of system's plan for either avoidance or resolution. It means no measures taken during congestion's early phases, and no change of action takes place after complete congestion. If a system has some means of detecting a forming or a formed congestion, there is still hope of saving itself, no matter the accompanying cost. Current system has no plan concerning congestion, it simply allows carriers to swap wares on flags when possible, thus preventing congestion from bidirectional traffic.

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):

  • An answer like "Feel free, cause I have plenty of space." is the easiest one, which is equal to no answer at all (what current system does).
  • An answer like "Don't bother, cause I'm already full." is an easy case (although dumb carriers have to be taught not to get short-circuited when hearing it).
  • The challenge remains for the middle cases, where the flag is like "Let me calculate the relevant risk..." On top of all that, we want the calculation to be simple, so as it won't stress the system. And that means to make most of the calculation beforehand and somehow integrate it in the algorithm of the flag's answer.

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
Avatar
Joined: 2013-07-29, 00:01
Posts: 1118
Ranking
One Elder of Players
Location: Poland
Posted at: 2018-05-30, 23:09

king_of_nowhere wrote:

einstein13 wrote:

But it won't solve the problem. Congestion will happen even faster (circle edition). (...)

Why not? I think it should solve the circle congestion. (...)

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! face-smile.png

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.

ypopezios wrote:

Perspective matters. (...)

You haven't got the point of transformation. Perspective doesn't matter from about 100 years. There are are many proofs of that face-wink.png .
How can I explain it better here?

  • Ware-perspective: check if on the next flag is limit of wares (check list of wares with the same spot=flag_x). Then decide what carrier should do.
  • Road-perspective: check the meeting of the roads and what is there. The order for the carrier will be decided by the road situation.
  • Carrier-perspective: check what is on the flags (start and end) and decide what can be done or not.
  • Flag-perspective: check nearby flags (flag-road-flag) for their situation and decide what order should be sent to the carrier.

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
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top Quote
ypopezios
Avatar
Topic Opener
Joined: 2018-04-20, 00:22
Posts: 220
Ranking
Widelands-Forum-Junkie
Posted at: 2018-05-31, 01:50

einstein13 wrote:

My question is: should we allow the carrier to put the ware back to the flag?

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.

Because this is the main reason of all congestions.

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.

einstein13 wrote:

You haven't got the point of transformation. Perspective doesn't matter from about 100 years. There are are many proofs of that face-wink.png .

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.

I know that it is not obvious, but all the algorithms can be changed between those points of view.

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.

einstein13 wrote:

From my point of view,

"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.

ware perspective is the best one, because most of the searches I would like to do is along the wares list.

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.

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.

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.

einstein13 wrote:

I don't know how the system based on flags should work, but I know that they can be treated the same way.

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.

einstein13 wrote:

But sometimes after transformations you get simple equations instead of complicated ones

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.

einstein13 wrote:

I don't know how your idea works, but for sure it can be transformed to any point of view.

Feel free to transform it afterwards. For now we have to make it work.


Top Quote
GunChleoc
Avatar
Joined: 2013-10-07, 15:56
Posts: 3324
Ranking
One Elder of Players
Location: RenderedRect
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
Avatar
Topic Opener
Joined: 2018-04-20, 00:22
Posts: 220
Ranking
Widelands-Forum-Junkie
Posted at: 2018-05-31, 12:36

GunChleoc wrote:

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?

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?

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.

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