Comments (20)
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 CSet
s 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.
Related Issues (20)
- No package 'argos3_simulator' found HOT 2
- ARGoS Checkpointing
- enh/actuator-enable-disable-interface
- Issue in building the doc in installation with Eclipse HOT 1
- gl.h not found in Mac OSX 11.4 Big Sur HOT 1
- Increasing the # cameras in ARGoS HOT 5
- EmodiedEntity init is called before successful place HOT 2
- Bugs in ARGoS cmdline HOT 8
- bugfix/34/stderr-redirect
- Black screen HOT 3
- Physics of gripping with the foot-bot
- Install MacOS glut not found HOT 9
- Not using threads on WSL2 (Windows 11) HOT 2
- Bugs and usability of ARGoS drone HOT 3
- footbot_encoder can not be reading. HOT 3
- include could not find requested file: ARGoSCheckQTOpenGL HOT 1
- argos visualization error when running CPFA: cannot find CPFA_qt_user_functions on Ubuntu 22.04 LTS HOT 1
- [Fatal] Can't load library "/usr/lib/argos3/libargos3plugin_simulator_media.so"...undefined symbol HOT 1
- How to dynamically create LEDs detectable by an omnidirectional camera HOT 1
- How to add a Drone?
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from argos3.