Efficient Robot Routing in Factorio

[dexteritas]

After reading FFF #374 last week, I got to thinking about the last problem described (robots crossing a lake) and whether it might be possible to implement an intelligent yet efficient way of pathfinding. To describe my idea in a bit more detail and to directly address some common problems with pathfinding, I created the following PDF last weekend (see attachment). Note that it is still a theoretical consideration, and only an actual implementation would show the exact impact on runtime. I also realize that some details could be described in more detail, but this is the rough idea for now. What do you think of this idea?

[SoShootMe]

Some initial thoughts:

Precomputed routes obviously avoid pathfinding cost but a trivial routing table as described in your paper would grow in size with the square of roboports, which seems likely to be impractical. This growth can probably be significantly improved upon but this is likely to increase the time to recalculate routes, which may also be a problem.

The ability to recalculate routes in parallel with other update activity does not necessarily mean there is no impact on UPS, even assuming sufficient cores are available. Apart from memory-hierarchy-related effects, some updates will obviously depend on recalculation being complete.

Even if the roboport network is not changed, the fastest route is not fixed due to other robots charging. A means to select an alternate roboport when the ideal roboport is "too busy" might be OK though, even if it means routing isn't guaranteed to be optimal.

Finally, I can't find any mention of logistic chests or construction/deconstruction locations in your paper, which are obviously common destinations for robots.

[mmmPI]

I think in the conclusion is too small, and some people like it when they can read only it, because they don't want or can't dive in the math details.

Why is it promissing ? the proposed changes in robots bevahior would make them try to avoid running out of battery which would (hopefully) translate in faster item delivery at the cost of some estimated calculation and memory overhead ? The promises are more than just avoiding robots getting stuck in loop where they try to reach a far away roboport, run out of battery, and they go back to charge, try again, run out of battery and go back to charge in the same roboport forever. ( goes beyond solving the original problem toward a certain "confort").

The term "new routine approach" i find too generic and could be replaced by a name describing the approach itself because that would make it easier to refer to it later and qualify the iterations. I don't find "intelligent routine" much better since there could be different way of considering what should happen in the game for it to be "intelligent" ( although it is still possible to refer to it as this approach on the internet ).

What i think i see is an approach where robots would act as if they have informations for the whole path from start to end when getting a task to do, aimed at avoiding loss of battery while accomplishing said task. which reminds me of this one : viewtopic.php?p=243995

The pictures of proposed "optimal" trajectories seem fairly similar, I'm not sure i am capable of understandings the differences it would generate to consider your definition of what is an edge of the graph formed by the robotports vs the idea of considering roboport connexions as visible in the game as the yellow dotted lines.

I think it's a different discussion when discussing what should robots do, and how they could be programmed to achieve it, for the former, i think it's not necessary to try and provide too much "confort" as i think it's a player's task in a factorio as a videogame to design ergonomic factory i prefer situations where i find myself smart when making "dumb" bots works as i intended after a few adjustments, rather than feeling frustrated when the "smart" bots still fail at something due to my design.

For the later, i lack knowledge and i'm still interested in learning how it could be done and enjoyed reading the paper that i found informative in this regard, thanks for sharing , the referenced book is quite exhaustive and easy to find online

[dexteritas]

Thank you for your thoughts

Precomputed routes obviously avoid pathfinding cost but a trivial routing table as described in your paper would grow in size with the square of roboports, which seems likely to be impractical. This growth can probably be significantly improved upon but this is likely to increase the time to recalculate routes, which may also be a problem.

It is true that with very large logistics networks, the table size could eventually become too large due to the number of roboports. I had only touched on a possible solution for this:

In case of a very large number of Roboports, it could be useful to group them in the forwarding tables
based on their position. Thus there would be an assignment of target area to next Roboport.

After running the routing algorithm, the roboports could be divided into regions, so in a simple example, the final stored routing table could contain the following:

• x <= 0 & y <= 0 -> Roboport 1
• x <= 0 & y > 0 -> Roboport 2
• x > 0 & y > 50 -> Roboport 3
• etc.

The ability to recalculate routes in parallel with other update activity does not necessarily mean there is no impact on UPS, even assuming sufficient cores are available. Apart from memory-hierarchy-related effects, some updates will obviously depend on recalculation being complete.

I agree.

Even if the roboport network is not changed, the fastest route is not fixed due to other robots charging. A means to select an alternate roboport when the ideal roboport is "too busy" might be OK though, even if it means routing isn't guaranteed to be optimal.

Yes, the roboport utilization would ultimately have to be factored in somehow as well. Perhaps the roboport that is initially selected without taking the utilization into account could be used as a basis for this.

Finally, I can't find any mention of logistic chests or construction/deconstruction locations in your paper, which are obviously common destinations for robots.

That's right, I didn't mention them directly because I wanted to limit myself to the essentials. But in my imagination, for each target (logostic chest or construction site), you would select the roboport closest to it and then use the procedure to move to it first. This way the number of nodes in the graph is not increased by the chests, etc.

[dexteritas]

I think in the conclusion is too small, and some people like it when they can read only it, because they don't want or can't dive in the math details.

I totally agree. I kept it very short. The paper would need some elaboration in a few places for completeness and especially here.

Why is it promissing ? the proposed changes in robots bevahior would make them try to avoid running out of battery which would (hopefully) translate in faster item delivery at the cost of some estimated calculation and memory overhead ? The promises are more than just avoiding robots getting stuck in loop where they try to reach a far away roboport, run out of battery, and they go back to charge, try again, run out of battery and go back to charge in the same roboport forever. ( goes beyond solving the original problem toward a certain "confort").

True, not only is the lake problem solved here, but other scenarios would be optimized as well. It would prevent robots from ever flying slowly with a low battery (exception: the current roboport is removed). It would also limit flying over enemy territory.
I could add these points as motivation.

The term "new routine approach" i find too generic and could be replaced by a name describing the approach itself because that would make it easier to refer to it later and qualify the iterations. I don't find "intelligent routine" much better since there could be different way of considering what should happen in the game for it to be "intelligent" ( although it is still possible to refer to it as this approach on the internet ).

Yes, finding a name is always difficult Maybe I can still think of a good name.

What i think i see is an approach where robots would act as if they have informations for the whole path from start to end when getting a task to do, aimed at avoiding loss of battery while accomplishing said task. which reminds me of this one : viewtopic.php?p=243995

I did not know the thread yet, I will have a look.

The pictures of proposed "optimal" trajectories seem fairly similar, I'm not sure i am capable of understandings the differences it would generate to consider your definition of what is an edge of the graph formed by the robotports vs the idea of considering roboport connexions as visible in the game as the yellow dotted lines.

The result could be similar. But the difference is probably how to calculate the whole thing. I haven't read the other thread completely yet, but at the beginning it still assumes pathfinding for the individual robots, which would be a bit different for me.

In the defined graph not only the roboports directly connected with dashed yellow lines would be adjacent but also more distant ones, if a robot can travel the path between them without recharging.

I think it's a different discussion when discussing what should robots do, and how they could be programmed to achieve it, for the former, i think it's not necessary to try and provide too much "confort" as i think it's a player's task in a factorio as a videogame to design ergonomic factory i prefer situations where i find myself smart when making "dumb" bots works as i intended after a few adjustments, rather than feeling frustrated when the "smart" bots still fail at something due to my design.

Yes, the distinction between what you could do well software-wise and what you would like for game design makes sense. I could also include this in the introduction.

For the later, i lack knowledge and i'm still interested in learning how it could be done and enjoyed reading the paper that i found informative in this regard, thanks for sharing , the referenced book is quite exhaustive and easy to find online

Thank You

[SoShootMe]

The ability to recalculate routes in parallel with other update activity does not necessarily mean there is no impact on UPS, even assuming sufficient cores are available. Apart from memory-hierarchy-related effects, some updates will obviously depend on recalculation being complete.

I agree.

The point I made quoted above is related to the previous point I made: if you make recalculation time longer in order to reduce memory use for routing information, the problem is that makes an effect on UPS more likely due to the dependency issue.

Perhaps the roboport that is initially selected without taking the utilization into account could be used as a basis for this.

That's the sort of thing I had in mind.

[...] for each target (logostic chest or construction site), you would select the roboport closest to it and then use the procedure to move to it first. This way the number of nodes in the graph is not increased by the chests, etc.

That could mean additional travel up to the logistic connection range of a roboport (chest at the edge of logistics range of its nearest roboport, in the direction of the preceding roboport). To avoid this I think you need to choose the final roboport out of the roboports from which the destination is directly reachable (without charging), rather than just the nearest. The obvious solutions to that are a search (extra time) or alternatively, but only for a chest, maintain a list (extra memory, and extra time when things change); neither is particularly appealing...