Friday Facts #374 - Smarter robots

[jamiechi1]

I would like to see the Closest First mod built into the game.

[EustaceCS]

...and they say males can't have emotional climax... I just had one from reading this article.
That's what I really LOVE in your approach to development.
You don't bother with consequences - you go straight to the cause and completely demolish it. Without causing any collateral damage.
Uuuuuuuuuuh, can't wait to see it in action...

Sincerely,
a player who is so bad with logistics so logi bots are the only solution for him even with their current state.

[0xE1]

It could be interesting to have some of these changes be part of Research tree? So that old behavior is part of initial robot research, and their behavior is then upgraded either through research or some other means, perhaps quality of robots?

[Koub]

I'd rather not, but that's just my personal opinion.

[catpig]

I know I'm late, but...
First, let me say that I'm quite excited about the DLC. However, there's always SE and Bobangel for more content - but this... this is just awesome. Maintenance and QoL are where you can tell good devs from bad devs - bad devs just add more features (that are easily billed), but good ones also provide after-sales support in the form of this sort of stuff

[wizcreations]

Perchance we had some mod with higher quality worker robots, we can request the low quality ones and remove them with a filter inserter, over time removing the worse robots from circulation.

I see what you did there. Nice teaser.

[MeduSalem]

Huh. So it considers the chunks they will end up in to make a decision which bots to pick. Good to know. ^^

Currently I have the habit to place my Roboports exactly on the corners or edges of chunks. Basically, overlapping the corners of 4 chunks or at least 2 chunks.

I wonder how my approach to that would affect which bots are picked for a task in 2.0. Because I guess the roboport have something like a "center of interest" which will be taken as coordinates for bots that are stored inside the roboport. I would think that because of that Center of interest the robots will be registerd in one of the 4 chunks and not all 4?
But that would likely mean that a situation can arise where you have a task, but the closest robot is actually in the neighbor chunk and it will NOT be used because there are a robots stored in a roboport in the same chunk, just on the far corner/edge of it. :>
If the entire roboport network is kinda aligned like that, like is in my maps, it will be really funny because then that algorithm should actually become quite noticable.

I guess the best place for roboports with Factorio 2.0 will be actually exactly in the middle of a chunk instead? Then it has equal distance in every direction of that chunk.

[Deruwyn]

Why not have bots check the distance to their destination? They have to have a known range. Then the bots could only perform any kind of pathfinding when they're trying to go a distance greater than that range. Unless most of the bots in your base are trying to travel beyond their range, this shouldn't affect performance too badly since only a minority of the bots are performing the more expensive pathfinding operation. This should also work well with your other improvement since, when they report their estimated time to achieve a task, they could include slow-movement and charging times. This should further reduce the frequency of needing to calculate the more expensive paths.

Another idea: what about caching the pathfinding calculation results in the stationary objects that interact with bots? It won't help if a bot decides to change jobs while it's flying between spots, but most of the time, bots will be flying from one object to another. If you store it as a hash table where the key is the endpoint and the value is the estimated time to make the trip (and waypoints along the trip if necessary, like if it's too far to get there without charging). Only add entries when the hashtable does not already contain the key. This should significantly reduce memory footprint of this feature since most of the time, bots will be flying between objects that aren't too far from each other or have some intrinsic connection. You can also estimate the time based on general areas instead of individual objects, since the calculations shouldn't be all that different in a relatively small radius around the object. So, if you have a bunch of chests near each other, they could share a table. Update the values upon first estimation of the trip's travel time and when actual travel time is found based on how long it took to make the trip.

Store a timestamp of when the value was last updated as well. If that timestamp is greater than some value (say 10 or 30 seconds or whatever), allow the value to be updated. Until then, just use the stored values for the plans for any bot making the journey. No need to recalculate. Once the time has ellapsed, (and assuming the trip involves a charging step) you can recalculate the path if new roboports have been placed within a circle with the borders touching the start and endpoints. If you don't want to calculate for a circle, then you can calculate for a square (number of grids) with the length of the sides being the straight-line distance between start and finish.

A different option is to store a central table of long paths (with start and end points) that have been previously calculated. Every time a new roboport is placed or removed, delete the old calculations that include the roboport's grid square in that same square shape I mentioned before. Now we don't have to worry about the timestamp weirdness. The new route has to be recalculated, but it needed to be recalculated anyway since charging options have changed. Again, this table only needs to contain long paths (greater than maximum bot range) so it shouldn't be too large, since most paths are shorter.

In order to prevent possible memory issues, you can cap the table's size. If the limit is reached, then evict records that have the oldest access time, or perhaps the smallest access count.

Since paths are reversable, you can also treat endpoints as start-points. Really, the key is a pair; start and endpoint. Just have someway of ensuring that every time a path is calculated, when making the lookup key, any pair of start and endpoints always have the same order; or at least the same lookup value in a hash table. You might need to maintain start/endpoint order so that the order of waypoints on the path can be reversed when planning a path in the opposite direction.

Anyway, all of this can change the complicated pathfinding calculation overhead from an expensive calculation done every time a bot decides to travel from A to B, to a O(1) lookup table access that only has to be updated when new paths are taken for the first time and prunes itself when the charging landscape changes.

For travel time updates, doing some kind of running average would probably be the way to go. You don't have to store individual travel times, just the current average time and the count of reported times. You can cap the count at some number to keep the value fairly up-to-date and let it swing if things in the factory are changing. Maybe 20 would be a good number. Anyway, every time you want to add a new time to your running average, treat all previous times as if they were the average. The formula would be new_avg_time = (old_avg_time * count + new_time) / (count + 1).

But now that I've thought a bit, a central table with start and end regions (so that individual objects within don't make too much of a difference) is better. (And remember, only used for long trips.) Plus, then you don't have to worry about the object to object calculation, just a bot within the start grid thinking about going to a distant grid region. And since this is for long trips, you can assume the bot will be at 100% charge for your calculations. Any bot planning on going on a trip beyond its maximum range would be required to top-up (perhaps if below 90% or something) before heading out on its journey. Very few bots should be doing these kind of trips in a normal situation, so most of the time, none of this will need to be used. Since the bot is planning on taking a trip that it knows it will have to stop to charge on, the trip would be stored as a series of waypoints between charging stations on the way from the start to the finish. This will prevent the dumb behavior where the bot heads directly for a location it's not going to be able to reach, and instead heads directly for the next roboport along its path, no wasted backtracking/sidetracking.

Additionally, by doing it this way, you can also keep track of the number of robots that have died while taking a certain path. If more than N robots have been killed in the last M minutes along that path, determine where they died and plan paths that avoid traveling through that region. Maybe they plan paths where no biter nests exist along any leg of that journey. This will prevent the very frustrating behavior where they travel through a corner of your concave base shape and get killed over and over. If you do both of those things; avoid biter nests and places where bots have died recently; we also fix the issue of bots all rushing to their deaths to repair a wall actively being attacked, but they'll go try to repair it again once enough time has passed.

Another thing you could do, when calculating paths is, if a waypoint that you've calculated going to is part of a pair of that waypoint to the same endpoint you're heading towards, then you've already got the path calculated for the rest of your trip and you can just add what you've come up with so far to the beginning of that trip.

If you do all this, you'll have your bots behaving in a much more intelligent fashion without too much compute overhead and, really, not too much memory overhead either.

[Hares]

I have another idea. Why not create pathfinding maps for drones each time roboport enters the network (which is quite rare event) similar to how trains pathfinding maps are created? Since robots are allowed to travel strictly to targets within the green radius ("construction area"), and these areas are always greater (or equal) to the roboport connection area, there's always a path through the yellow zones ("supply area"), or yellow+green, but it's not that consistent. So I suggest creating a graph of the network with nodes on the roboports and select the shortest path through that graph. The algorithm is not that hard to implement, and is not computation-time-consuming (finding nearest roboport each time robot needs to recharge is harder if you multiply that by the number of recharges). This, by estimating the flight on charge range, would allow completely eliminate the mentioned search, unless something strange happens (i.e., the network is partially disconnected or so).

Yes, there might be cases when this approach would lead to increased flight times, but these are definitely rare cases and the robots will now follow the built highways instead of trying to cut corners.

[typecasto]

Will the charging heuristic also consider the charging speed of the roboport? I've been playing Krastorio 2, and recently I had to completely purge my base of normal roboports. because bots would often charge at them instead of the much faster large roboports.

[DarkShadow44]

A common thing I have is placing a blueprint, but then my personal robots finish because I lack one machine. If I then handcraft the machine, I still wait for the robots from the base. Will that smarter behavior also fix that annoyance?

[Maxvoss12]

Using all of these post launch is so nice but it seems that the personal construction robots havent been updated somehow. They seem to work like they did before in the sense that they place 1 thing for each bot and then wait for the roboport bots to build the rest and even the same thing with the trees (shown in the example in this FFF) That might be a bug or oversight or something but hopefully this gets fixes soon or for 2.1.

[retlom]

seems not to work as of now i observe almost all ways the old behavior instead of the new one.

[Hares]

seems not to work as of now i observe almost all ways the old behavior instead of the new one.

Agreed.

10-26-2024, 15-34-09.png (2.44 MiB) Viewed 580 times

[Koub]

seems not to work as of now i observe almost all ways the old behavior instead of the new one.

Feel free to file a bug report with ways to reproduce if you think they are bugged
[Edit] I see that Hares did file a bug report : viewtopic.php?f=29&t=117641

[FitterSkippy]

They may have removed infinite loops when flying outside a network, but im wondering why we can't have robots that stay inside the network period. In the example shown at the end of this Friday facts, why can we make it so the robots just go up and around instead of leaving the network? Even if they do keep themselves out of a loop, getting to a roboport after they've run out of charge at a snails pace seems much more inefficient than staying inside the network and not running out of power.

[DarkShadow44]

They may have removed infinite loops when flying outside a network, but im wondering why we can't have robots that stay inside the network period. In the example shown at the end of this Friday facts, why can we make it so the robots just go up and around instead of leaving the network? Even if they do keep themselves out of a loop, getting to a roboport after they've run out of charge at a snails pace seems much more inefficient than staying inside the network and not running out of power.

Because robots always fly the direct route, adding pathfinding would also add serious performance concerns.

[Hares]

Because robots always fly the direct route, adding pathfinding would also add serious performance concerns.

Yes & no, check my message above.
viewtopic.php?p=611679#p611679