ai roads getting jammed a lot

[king of nowhere]

I noticed while playing my latest map (concentric rings) that AI will get hopeless traffic jams over time. I'm not talking just about wares taking a long time for delivery, I'm talking those kind of jams where no ware moves anymore and the whole economy is completely stuck. Words fail in front on the images I'll attach to this post.

And I'm playing the map again, and I see it happening again, this time with another ai player and even earlier in the game. Apparently a long and relatively narrow land is bad for the ai roadmaking process.

I know teaching ai to make good roads is a near impossible task, but hopefully a fix for the worst cases should be possible. I noticed that the AI response to jammed roads is to build more roads, which rarely will help. One possible solution would be, instead of building short road segments, to build long road segments, which may help bypassing the critical section entirely. Or, the AI could have some way to realize carriers are not moving, and cut roads until they start moving again.

[king of nowhere (lainluigi86)]

this is the biggest road jam i''ve ever seen, covering several screens

[king of nowhere (lainluigi86)]

And finally the end. Notice how none of those carriers is going anywhere.

[king of nowhere (lainluigi86)]

As you can see from the power graph, for the latest 20 hours of game the white player's economy has been completely stuck as some vital resource was in the jammed area.
I made all that ridiculously convoluted map to ensure that the last opponent would have time to build up a huge army and give a real epic fight, and it was quite a let-down to discover that instead it had sort of killed itself.

[TiborB (tiborb95)]

I was not able to load the game but based on screenshots....

I would say, there are two primary problems:

Transportation got stuck (this savegame could be used to debug and perhaps develop a fix, but this is not AI issue)
Too many grapes. We had similar problems with abundance of woods that used to cause traffic jams as well. But now, we have algorithm that stops rangers so the problem is gone I believe. But there is no algorithm that stops farm-like producers. So this could be a fix from AI side to mitigate this problem.

Improving the road algorithm - it is difficult to make the AI more intelligent, I have to admin....

[king of nowhere (lainluigi86)]

I considered this mosty an ai problem even if it's actually more of a traffic algorithm one because a human can manage traffic and solve those snags when they happen.
yes, stopping primary producers (buildings that produce something without requiring any input) when there are plenty of their wares would certainly reduce the chances of the problem arising. but it would not be a perfect fix, and would not have helped in this case. consider the beginning of the jam, on screenshot 06. this was done entirely with other resources, and then the wine could no longer go anywhere and it piled up for five screens. cutting a few roads there would solve the problem. I'm thinking of a way to let ai recognize that, but without knowing more of the routing algorithm it's hard to say.
Maybe a possibility could be that when a flag has the maximum 8 wares piled up on it, a timer starts, and if none of those wares are moved in the next five minutes, they get deleted. or maybe their destination is changed from the current one to another, and only if five more minutes pass they are deleted. ai could get an additional warning after two minutes where it would attempt to cut some road, which generally helps; a human could get a message that there is a bad traffic jam.
those kind of snags appear if there is a sort of circular block: there are flags A, B and C and all wares on A must go in B and all wares in B must go in C and all wares in C must go in A, and so none of the carriers can bring their ware at the flag and get another. Cutting some roads generally reroute enough of those wares that the problem is solved.

[TiborB (tiborb95)]

AI now can remove roads, when both flags are empty and alternative road is not that long. Generally it is not so big proglem remove also reads that are too busy. Only the problem is to find out it is busy. I dont like idea to keep list of wares on flag in AI and compare it periodically, it is too much overhead. And it is basically mimicking what flag is already doing.

 I would prefer if flags have some timer like last_time_ware_left, and then number of wares + this information + the fact whether there is a warehouse in economy would give reliable info if the transportation is stuck.... Then AI would dismantle such road.

Also this info could be used for possible 'traffic jam map', if there was an interest for this stuff.

But I still believe, there stopping some production sites would generally improve the situation. But this will not be done before build 19 probably.

[king of nowhere (lainluigi86)]

'I dont like idea to keep list of wares on flag in AI and compare it periodically, it is too much overhead. And it is basically mimicking what flag is already doing.

 I would prefer if flags have some timer like last_time_ware_left'

yeah, that's exactly what I was thinking. a timer on the flag that would activate only when the 8th ware is deposited on the flag, and would reset anytime a ware is removed. Since it is rare that flags get an 8th ware, it should not generate too much calculus. This would not be a function of AI, but a function of the program. The ai could then be thought to do something about it, while a human could receive a message.

Because those circular traffic snags that I described are relatively rare, but when they form there is no other way they can be removed except cutting some roads or destroying some of the destination of those wares.

[TiborB (tiborb95)]

That timer would need to be discussed and approved by SirVer and GunChleoc.

BTW you are not right with this:
> a timer on the flag that would activate only when the 8th ware is deposited on the flag, and would reset anytime a ware is removed. Since it is rare that flags get an 8th ware, it should not generate too much calculus.
The engine would need to calculate this every time a ware is received (to find out if it is eight ware) and when a ware is leaving to find out if timer* has to be reseted.

* Well - the "timer" is to be a gametime when an eight ware was delivered, this is static number - no special calculation here when this is "on".

Generally it means adding one uint32_t to each flag and two small tests when ware is delivered and is leaving the flag

[Albert Einstein (w-aaaaa)]

roads is always huge problem for AI. I really don't have any good solution except some small ideas for some of the buildings. For example warehouses should be surrounded by roads: small ring around with all possible connections with central warehouse flag will solve most of the problems there. In my games it always helps and there is no bottleneck there. :) But coding such ideas can be a bit complicated...

[king of nowhere (lainluigi86)]

as far as i know, the flag checks how many wares it has every time it receives a new ware, and that information is used to decide if it should receive a secondary carrier or not. So the only additional operation would need to be introduced when the wares are 8, by telling it to also start the timer.
Of course I may be wrong, or it may be that the way it checks how many wares it has is done in such a way that it would still need to check if they are 8 every time. But at least that was my assumption.
As for ai making better roads, I've thought about it a lot, and I simply cannot come up with anything that wouldn't risk doing an even worse mess. Especially because laying good roads for a large map requires either planning them from the start - which requires knowing that it will be a big map and how much you'll be able to expand, especially if you have to choose between making better roads or making more buildings, and the ai has no way to know that - or dismantling and remaking plenty of buildings to straighten your roads later in the game, which we cannot tell the ai to do without risking it screwing it up badly.
So for now I'm only thinking of circular snares.

[Albert Einstein (w-aaaaa)]

AI can do some calculations by itself and then predict if the map is good to make huge empire. On small maps predictions about roads are not so important (time loses there are smaller than 20% while on big ones it can be more than 100%). So there are very strict rules about "how to predict that the map is big".
But adding rules for AI how to predict the map type can cause other, bigger problems. That can be done not smart enough...
We can think about solving the road problem with existing terrain and building situation. If you have to link all buildings in smart way. Before that it is very easy to stop for a while part of the economy where terrible traffic jam is. Then wait about 2-3 minutes till traffic jam will no exists any more of mainly will disapear and dismantle the roads. Then link the buildings with building correct (and straight) roads around. Then the problem should be solved.
Of course rules for stopping the economy + dismantling the roads should be complex (for example counting some "points"). Also it should be considered if a foresters are nearby (problems with big woods which are unpassabel for roads).
But in my opionion it can be done after build-19. Too many bugs can happened there...

[GunChleoc (gunchleoc)]

I think after builg-19 is a good idea, since this is an old problem anyway. Adding a timer sounds like a good starting point to me.

[Albert Einstein (w-aaaaa)]

About timer:
I understand, that it is started when wares = 8. What about moving wares in jam? Sometimes in jams wares are moving quickly, but the road is jammed. So you have all workers moving wares in a line like:
7 -- 8 -- 8 -- 7 -- 8 -- 8 -- 7 -- 8 -- 8 -- 7 -- ...
What about this situation? Should we count it as "no jam", because 8 wares near flag is for less than 5 seconds? For me it is traffic jam and should count. (or maybe I don't get all the idea of this timer?)

[GunChleoc (gunchleoc)]

I think we were talking about deadlocks only here, where nothing will be moving again.

[king of nowhere (lainluigi86)]

yes, i was only referring to deadlocks. traffic jams will eventually resolve, and the wares will be transported, but in a deadlock nothing is moving. refer to image 006 that I attached for the concept. My timer idea would reset every time a ware is moved at the flag, so only flags with 8 wares and no movement for 5 minutes would be affected. And if there are 8 wares and none of them has moved in the last 5 minutes, it is almost certainly a deadlock. teaching ai to avoid traffic jams is something advanced that we may do in the future, but automatically solving deadlocks is a first step and it is easier.

[Albert Einstein (w-aaaaa)]

Ok, so my concerns are not very important now :)
Thanks for clarification!

[king of nowhere (lainluigi86)]

ah, well, concerning about trying to make ai build better roads are always welcome, and it would be great if you could find some viable algorithm that would work for all maps. as it stands, I can't think of any. anyway, a discussion on ai roadbuilding should be in some other place. here it was only about the low-hanging fruit of solving deadlocks.

[ypopezios (ypopezios)]

In a road between flags A and B, before deciding to carry a ware from A to B, the system should check if B already has a ware of the same type (or maybe a bigger number, but smaller than the available slots of B). If so, the carrying should wait, like if B had no empty slot, but leaving the carrier free to serve other wares. Moreover, if the said ware at B happens to be heading to A, then the two of them should get rerouted to each-other's destination, since they are of the same type and thus interchangeable.

[GunChleoc (gunchleoc)]

I think delaying ware transportation could cause a ripple effect backwards, so we do need to consider this carefully.

If we have some thing like A grape -> B and B grape -> A, swapping the routing is a good idea - I don't see any potential problems here.

Another thing that the AI might consider is amount in stock for wares that don't have a default target quantity. Stopping production for a bit if here is more than a certain threshold in the warehouses could help, let's say 150? That should be plenty as a stockpile.

[ypopezios (ypopezios)]

Concerning the threshold in the warehouse, I would instead prefer a maximum capacity (e.g. 99) for all players (and trigger a message when reached). If people want bigger stockpiles, they have to build more warehouses (or maybe upgrade the existing ones). This is good to have, but it doesn't cover all cases.

Concerning my proposal, yes, it would cause a ripple effect backwards, halting the excessive transportation of the ware that has the potential to choke the transportation system. In other words, blocking the problematic ware (or forcing it to choose a different route) so as the transportation system won't get blocked. Isn't this the goal?

Suppose that you are a carrier working in a road. How would you handle a similar situation? Stop working? Waiting orders from the HQ? I would try to do the best of the situation, given the limited information in my knowledge. That would be to serve the wares which leave my flags and not serve those which spam my flags.

[GunChleoc (gunchleoc)]

I don't think that human players will need a warehouse limit to solve the road issue - I'd like to keep that as part of the challenge. I know that the original Settlers had it though.

> Concerning my proposal, yes, it would cause a ripple effect backwards, halting the excessive transportation of the ware that has the potential to choke the transportation system. In other words, blocking the problematic ware (or forcing it to choose a different route) so as the transportation system won't get blocked. Isn't this the goal?

I'm not saying that your proposal is wrong, I only meant that we need to think about it carefully, because it's a complex issue. If it works, great! :)

[ypopezios (ypopezios)]

Swapping the routing has already been suggested by king_of_nowhere on the forum (algorithm #2):
https://wl.widelands.org/forum/topic/1549/

[kaputtnik (franku)]

The screenshots and the savegame was made with r7578. This revision was applied in Oktober 2015:

https://bazaar.launchpad.net/~widelands-dev/widelands/trunk/changes/7578?start_revid=7578

This version was between release 18 and release 19. From what i remember the new AI was implemented after releasing Build19. So it should be clarified if this bug is still valid.

@Tibor: Is the road system part of the genetic algorithm of AI? In other words: Is there a possibility that such a traffic jam would not appear anymore because the genetic algorithm has learned a lot in the meantime?

Just before some one puts too much time on this bug...

[TiborB (tiborb95)]

No, road system is not controlled by genetic algorithm and there is no way how AI would recognize and cope with such issue.

So yes, fixing it by ypopezios is highly welcomed

[ypopezios (ypopezios)]

Even if it was easy to teach the AI how to cope with traffic jams, "prolepsis is better than therapy". In coming fix I don't plan to touch the AI, I'll just make the flags a little smarter.

[kaputtnik (franku)]

The linked branch crashes here if i try to load the attached savegame. Error:

Fatal exception: [/home/kaputtnik/Quellcode/widelands-repo/congestion2/src/logic/map_objects/bob.cc:593] MO(1406): start_task_movepath(index): not on path

The savegame was created with current trunk. Loading with current trunk no crash happens.

I have tried to reproduce the crash with a savegasme created with the linked branch, but didn't get it.

[ypopezios (ypopezios)]

The crush happens because of incompatibility between the states of the old and the new carriers. If you have to test the attached savegame, one way is by inserting the following lines below line 426 of file tribes/carrier.cc :

if (carrier.get_state(taskWaitforcapacity)) {
 carrier.operation_ = WAIT;
} else if (carrier.operation_ == NOP && carrier.top_state().task != &taskRoad) {
 carrier.operation_ = INIT;
}

[kaputtnik (franku)]

Thanks, i didn't want to test the savegame, just stumbled over this.

So your branch will break savegame compatibility, just mentioned it here, because it was not clear to me.

[GunChleoc (gunchleoc)]

The fix caused more problems than it solved, c. f. https://bugs.launchpad.net/widelands/+bug/1797213

[hessenfarmer (stephan-lutz)]

I currently try to make the AI build a second carrier building. This might relax the issue a bit.

[hessenfarmer (stephan-lutz)]

Ok I finally made the Ai building second carriers. this might help in this case.
@ king_of_nowhere
could you retest concentric rings with the latest AI fixes branch?

[king of nowhere (lainluigi86)]

I don't see a second carrier building helping. all roads had a second carrier, but they were jammed anyway.

a study showed that an insoluble traffic jam is created when flows of wares from three different directions intersect. There can be ways to prevent that by coding, for example by recognizing that all carriers around a flag are standing still. but adding carriers won't do much.

Also, I hope you don't take it badly if I decline trying concentric rings again to check the fix: it toook 50 hours of gameplay to reach that point last time, and given the random nature of that kind of jams, it may not even help.

[GunChleoc (gunchleoc)]

Migrated to https://github.com/widelands/widelands/issues/3099