Same tasks, same scene, different conflict resolution

[RDaneelOlivav]

Hi,

I executed this task with hyper big vicinity_radius values to trigger collisions, and therefore conflicts.
Sometimes it resolves the conflict and sometimes doesn't. The word thing is that it happens in the same exact conditions.

Does someone know why? Is the CBS solver not deterministic and has some variability? Thanks in advance

[mxgrey]

I'll start by explaining the meaning of the vicinities and the footprints. The RMF traffic system does not operate in terms of "collisions", it operates in terms of "conflicts". The difference is subtle but important:

• a collision constraint implies that any path where the two agents are "too close together" (the footprint of one touches the vicinity of the other) at any instant in time is invalid
• a conflict constraint implies that any path where the two agents get any closer together instantaneously after any instant where they are already too close is invalid

A conflict is effectively the same as a collision if the initial positions of the robots are far enough from each other. But if the robots start in too-close proximity (like they do here) then the "conflict" constraint allows them to move away from each other, whereas the "collision" constraint would say that there is absolutely nothing that either robot can do.

This distinction is important because system integrators often want to maintain some separation between their robots in a deployment. To do so they may inflate the vicinity value like what you're doing here. However, RMF is targeted at highly distributed asynchronous systems which have imperfect knowledge of the world. Because of that imperfect knowledge (e.g. due to latency, localization errors, unanticipated obstacles, or robots being manually moved) it is possible for the robots to end up in a configuration that would yield no valid solutions when applying a collision constraint, but could be solved with a conflict constraint e.g. by having the robots simply move away from each other before continuing on their way.

Now for your question about determinism: RMF is implemented as a distributed async system in order to get the fastest possible resolution to traffic conflicts. In most ordinary cases the negotiations will yield consistent results because there will be one very obvious optimal solution for how the robots can navigate while avoiding conflicts. However the situation you've created here is pathological because you have two robots whose goals are close enough to violate the distance requirements given by the vicinities and footprints that you've set. As the robot's velocity approaches zero at its goal while the two robots are in the same vicinity as each other, the robots will be exactly on the precipice of violating that constraint. If the precision of the floating point arithmetic is not favorable, a conflict will be detected in this scenario. But you could also get lucky and the floating point arithmetic might see no problem with it.

So sometimes it will work because sometimes rounding errors are in your favor, but other times they won't be. The rounding errors may turn out different even if you've set up the same scenario because all the timing involved in the negotiation is non-deterministic, especially when you have simulation involved. The negotiation algorithms are implemented in the rmf_traffic library which can be used in a synchronous application and will then give deterministic output.

The situation you've presented is considered pathological because of the conflict between vicinities and goal positions. The negotiation system will always try to cope as best as it can with pathological scenarios, as long as it doesn't violate the traffic conflict constraints. But since this scenario is sitting directly on the boundary of being feasible, any slight error or numerical imprecision could yield a result that says it's actually infeasible.