Ordering of CSet<CRABEquippedEntity*> returned by CRABMedium::GetRABsCommunicatingWith() is non-deterministic about argos3 HOT 20 CLOSED

Oh man. I never noticed this. Thanks for spotting this issue. I'll look at it and fix the code later today!

from argos3.

I've had a closer look at this, and I think the problem is caused by the for loop that iterates over m_tRoutingTable on Line 133 of rab_medium.cpp.

m_tRoutingTable is defined as an std::map:

typedef std::map<CRABEquippedEntity*, CSet<CRABEquippedEntity*> > TRoutingTable;

and iterating over an std::map will not process items in the order they were inserted by CRABMedium::AddEntity. Therefore, even if the implementation of CSet is deterministic, the order in which the CRABEquippedEntity pointers are inserted into it may be non-deterministic.

The simplest solution might be to redefine TRoutingTable as:

typedef std::vector<std::pair<CRABEquippedEntity*, CSet<CRABEquippedEntity*> > > TRoutingTable;

This would preserve the insertion order, but wouldn't allow access-by-key, so would result in O(n) time complexity when searching for elements - this might be unacceptable in terms of efficiency for large-scale swarm simulations?

Another solution I've seen recommended is the use of boost::multi_index container, but this would add a further library dependency to ARGoS.

Yet another solution might be to maintain a separate std::vector<CRABEquippedEntity*> alongside the std::map, to keep track of the insertion order, but this comes with the complication of having to keep two data structures in sync.

from argos3.

I just tried implementing the last solution above (maintaining a separate std::vector<CRABEquippedEntity*> alongside the std::map), and this indeed makes the for loop that iterates over m_tRoutingTable on Line 133 of rab_medium.cpp deterministic.

However, this does not entirely solve the problem, because m_pcRABEquippedEntityIndex->GetEntitiesAt(cOtherRABs, cRAB.GetPosition()) on Line 142 of rab_medium.cpp returns a CSet<CRABEquippedEntity*> cOtherRABs with non-deterministic ordering, thus causing a similar issue with the inner for loop on Line 144 of rab_medium.cpp.

Perhaps the best solution would just be to sort the CSet<CRABEquippedEntity*> returned by CRAB::GetRABsCommunicatingWith() inside CRangeAndBearingMediumSensor::Update(), as this is the only place that the non-determinism has an effect on robot behaviour?

from argos3.

I can confirm that modifying CRangeAndBearingMediumSensor::Update() such that it copies setRABs into a std::vector<CRABEquippedEntity*> and sorts it based on robot ID solves the problem.

I can create a pull request for this, but I'm not sure if it's the best solution.

from argos3.

Hello Alan! I finally have a little time to look into the issue myself. Thank you so much for all the work you've done to track down and propose a solution for this problem! Please do submit a pull request and I'll look into it. I thought about a different approach to achieve the same effect (implementing a faster, deterministic map replacement for std::map which is anyway long overdue), but having your implementation as a comparison for performance would be valuable. Thank you again!

from argos3.

On second thought: the culprit for m_tRoutingTable not to be deterministic actually is that pointers to CRABEquippedEntity* used as key cannot be the same across different executions of ARGoS. Every time you run a new experiment, the addresses will be different - and so will the order in the map. The solution could be as simple as using a different key. ARGoS already has a few vectors that are order-stable across executions. Using one of those could be the solution. This would obtain the same exact effect that you are obtaining with your proposed solution. I'm digging into that right now.

from argos3.

Hi Carlo, I've submitted a pull request for my fix: #49

This is a bit of a hack, though. The solutions you propose sound much better in the long-run. Making the inner-workings of ARGoS deterministic would be ideal, as long as it doesn't come at the expense of efficiency.

Let me know if there's anything more I can do to help. I'm keen to find a good solution for this, as it has a serious effect on the reproducibility of experimental results.

from argos3.

I am about to push my proposed solution. Can you check it for reproducibility? I'll make a performance comparison between yours and mine on my side.

from argos3.

Sure, I'd be happy to.

from argos3.

I pushed my proposed change. It's similar in style to yours, but it's faster. Can you check if it's repeatable on your system? Thanks!

from argos3.

Hi Carlo,

This still produces non-deterministic results on my system.

Your solution of maintaining a separate vector to keep track of the order in which entities are added is similar to the one I tried previously. This fixes the non-determinism of the outer for loop, but the ordering of the CSet<CRABEquippedEntity*> returned by m_pcRABEquippedEntityIndex->GetEntitiesAt(cOtherRABs, cRAB.GetPosition()) is still non-deterministic, so the inner for loop inserts elements into the CSets of m_tRoutingTable in a non-deterministic order.

It seems like it will be necessary to either sort cOtherRABs before iterating over it, or make the behaviour of CGrid<ENTITY>::GetEntitiesAt deterministic?

Either way, it would be nice to fix this at the level of RAB medium, rather than the sensor (as in my solution).

Cheers,
Alan

from argos3.

Thanks Alan! I am working on making the positional index capable of ordering the result of GetEntitiesAt() deterministic. This way, every call to it would be deterministic by design, and this would fix other places that are not being considered now.

from argos3.

I pushed another proposed change.

I added a field CEntity::m_unIndex for global ordering. This field is set in CSpace::AddEntity() every time a new entity is added. Then I added a generic SEntityComparator that uses the index to decide which entity comes first, instead of using the pointers as before. Then I extended CSet<> to accept a comparator, and modified CPositionalIndex<> and CGrid<> to use the new CSet<> along with SEntityComparator.

This change should ensure global ordering everywhere. Plus, it breaks compilation for code that does not comply with the change - a nice way to know which parts of the code should be modified.

I'm still fixing a couple of wrinkles here and there. After that, I'll also tidy up the code a little bit.

from argos3.

Excellent, this seems to fix the non-deterministic behaviour on my system :)

Thanks for the taking the time to dig through the internals of ARGoS and make these fundamental changes. It's exactly the kind of solution I was hoping for, but would have taken me considerably longer to figure out myself.

Once you're done ironing out the wrinkles, could you please release the changes as ARGoS 3.0.0-beta49 so that people can patch their installations without having to compile from source?

from argos3.

I just tried compiling this new code in my Ubuntu 16.04 VM (gcc 5.4.0), and I get the following error:

error: ‘unordered_map’ in namespace ‘std’ does not name a template type

I thought this might be something to do with std::unordered_map being a C++11 feature, so I tried adding -std=c++11 to CMAKE_CXX_FLAGS, but it didn't seem to help.

from argos3.

I've also just noticed that for certain ARGoS experiments on my Mac, these changes cause segmentation faults (either immediately, or during the experiment), or I get errors during initialisation like the following:

[FATAL] Failed to initialize the media. Parse error in the <media> subtree.
[FATAL] Error executing post-space initialization of medium "leds"
[FATAL] While updating the LED grid for LED ""
[FATAL] CGrid<ENTITY>::PositionToCell() : Position <-0.0636656,7.19056e+252,7.03545e+199> out of bounds X -> -2.5:2.5 Y -> -2.5:2.5 Z -> 0:2

[FATAL] Failed to initialize the media. Parse error in the <media> subtree.
[FATAL] Error executing post-space initialization of medium "leds"
[FATAL] While updating the LED grid for LED "w�v�

from argos3.

from argos3.

I'm done with the work. I tried on both Mac and Ubuntu 16.04 and it seems to work. If you could test it too, it would be great!

from argos3.

Just tested this on macOS Sierra (10.12.6) and in my Ubuntu 16.04.03 VM, and can confirm that the RAB sensor now behaves deterministically!

Thanks again for all your work on this Carlo. It's nice to know that entities now have a globally deterministic ordering throughout ARGoS.

from argos3.

Thank you for spotting this problem. The same issue was present in the kilobot plugin, and I couldn't figure out why. Your bug report was key to understanding and solving it!

from argos3.