Experimental/cell space

[Corvince]

An implementation based on the discussion in https://github.com/projectmesa/mesa/issues/1900

This should be a place to discuss implementation details and to collaborate on this experimental feature. Also this highlights the semantic changes as seen in the benchmark models.

[EwoutH]

There’s a lot in here that I like!

let me know when you want any input / a review.

[EwoutH]

If you add matplotlib here, the current error in the benchmarks is resolved.

https://github.com/projectmesa/mesa/blob/7b0d3f12f0fb2a0f2dc3ec1bcca4a95a82ff6cee/.github/workflows/benchmarks.yml#L31

[Corvince]

If you add matplotlib here, the current error in the benchmarks is resolved.

https://github.com/projectmesa/mesa/blob/7b0d3f12f0fb2a0f2dc3ec1bcca4a95a82ff6cee/.github/workflows/benchmarks.yml#L31

Thanks, I now tried to bypass the jupyter stuff, but I am not sure if this is working. If I change the benchmark.yml won't the action stop working? Because of the pull_request_target thingy?

[Corvince]

There’s a lot in here that I like!

let me know when you want any input / a review.

Feedback ist welcomed at all times!

[Corvince]

/rerun benchmarks

[EwoutH]

If I change the benchmark.yml won't the action stop working?

Yeah it might, honestly I don't know.

[rht]

Had 3 comments at https://github.com/projectmesa/mesa/commit/2e78940728f2b946abcdca571fd4e85343849a50#comments.

[rht]

/rerun-benchmarks

[github-actions[bot]]

Performance benchmarks:

Model	Size	Init time [95% CI]	Run time [95% CI]
Schelling	small	🔵 +0.0% [-0.3%, +0.4%]	🔵 -0.1% [-0.3%, +0.1%]
Schelling	large	🔵 -0.5% [-1.1%, +0.1%]	🔵 -3.9% [-6.4%, -1.2%]
WolfSheep	small	🔵 -2.4% [-2.8%, -1.9%]	🔵 -0.3% [-0.4%, -0.1%]
WolfSheep	large	🔵 -2.2% [-3.0%, -1.5%]	🔵 -3.5% [-4.4%, -2.3%]
BoidFlockers	small	🔵 -1.7% [-2.2%, -1.1%]	🔵 +0.4% [-0.0%, +0.9%]
BoidFlockers	large	🔵 +0.2% [-0.4%, +0.9%]	🔵 -0.5% [-1.0%, -0.0%]

[Corvince]

@EwoutH it looks like the benchmark wasn't run for this PR after the comment trigger. You can see that from the action. Maybe you can look into that?

[EwoutH]

it looks like the benchmark wasn't run for this PR after the comment trigger.

You forgot the dash between rerun and benchmarks. It has to be the exact string (see rht's one).

[Corvince]

it looks like the benchmark wasn't run for this PR after the comment trigger.

You forgot the dash between rerun and benchmarks. It has to be the exact string (see rht's one).

Ha, I see how my comment was completely miswritten. I already realized after @rht made the correct comment. But in the action that was actually triggered this PR isn't checked out, hence no difference in performance. Performance should actually be about 20% faster.

Here is the exact line of the Action. It should check out this PR, but instead creates a new branch "main" https://github.com/projectmesa/mesa/actions/runs/7632442972/job/20792667533#step:9:149

[EwoutH]

Looks like it checks it out differently when initiated from a PR opened then from a comment. Will check it out!

(current workaround it so mark PR as ready to review (and back to draft))

[quaquel]

Thanks for this! I will take a deeper dive at this, hopefully, tonight or otherwise over the weekend. I quickly checked the code this morning and have a few additional comments and suggestions in addition to the various points already raised

I will also move my versions of Schelling and WolfSheep into this (do I have write access)? So we can properly see the change in performance.

[EwoutH]

It should check out this PR, but instead creates a new branch "main"

I tried some stuff in #1998. Let's see if it works.

[EwoutH]

Merged, here we go: /rerun-benchmarks

[github-actions[bot]]

Performance benchmarks:

Model	Size	Init time [95% CI]	Run time [95% CI]
Schelling	small	🔵 +1.5% [+0.3%, +2.7%]	🔵 +0.8% [+0.1%, +1.5%]
Schelling	large	🔵 -0.4% [-2.0%, +0.9%]	🔵 -1.7% [-3.1%, -0.2%]
WolfSheep	small	🔵 +1.6% [+0.5%, +2.6%]	🔵 +1.9% [+1.2%, +2.7%]
WolfSheep	large	🔵 +6.4% [+1.7%, +11.7%]	🔴 +8.2% [+5.3%, +11.1%]
BoidFlockers	small	🔵 -0.8% [-2.5%, +0.8%]	🔵 -0.5% [-1.4%, +0.4%]
BoidFlockers	large	🔵 +0.1% [-3.0%, +3.3%]	🔵 -0.5% [-1.5%, +0.4%]

[EwoutH]

Doesn't work unfortunately. Will research further at a later point. For now, just do the "mark as ready for review" trick.

[Corvince]

I will also move my versions of Schelling and WolfSheep into this (do I have write access)? So we can properly see the change in performance.

I invited you as a collaborator just now, so you should have write access. Schelling and WolfSheep are already part of this PR, but the benchmarks are currently not working because I moved the CellSpace into experimental. That means on importing cell_space (for the benchmarks) jupyter_viz is also imported and this leads to a unresolved dependency. Quick solution would be to move cell_space into mesas main directory. Then we can properly retrigger the benchmarks and we should finally see the difference.

[rht]

I merged #2001. /rerun-benchmarks

[quaquel]

I have made some choices in light of all the comments and feedback. Feel free to discuss if you disagree. In short:

• added NetworkGrid
• Renamed various classes
• Added an intermediate Grid class from which OrthogonalGrid and HexGrid derive
• Added a CellAgent class. This isolates this experimental code from the rest of MESA. I also added a move_to method to this agent to handle movement.
• I changed the handling of empties closer to the old code. This does introduce coupling between a Cell and its owning "Space" with the various drawbacks that it entails. However, select_random_empty_cell now works across OrthogoonalGrid, HexGrid, and NetworkGrid.

compared to my code from last week, this is still a bit slower. I'll try to investigate later.

[quaquel]

compared to my code from last week, this is still a bit slower. I'll try to investigate later.

I fixed the performance issues. The code base is mainly complete. @EwoutH, if possible, let's take 5 minutes tomorrow to discuss property grids and how they might be made to work with this. It's not on the critical path (just as with named connections), but if there is a simple solution, it would be nice to have.

random number generation is still a problem. Once #1981 is addressed, we should use that solution here.

I still want to add at least some tests before even thinking about merging this.

[Corvince]

I have made some choices in light of all the comments and feedback. Feel free to discuss if you disagree. In short:

Thanks for all the changes!

• Added a CellAgent class. This isolates this experimental code from the rest of MESA. I also added a move_to method to this agent to handle movement.

I don't think this isolates it too much, this is something that has been on several wish lists. But if we manage to find an appropriate implementation for ContinousSpace that is also somewhat "cell-based" (im working on this issue) , these changes could also be propagated to the basic Agent. I know there are ABMs without a space component, but its cell-centric methods don't need to be used. and I don't think there will be too many.

However, I wonder how we will go along with distinguishing cells from positions, esp. in such methods. Currently it only supports cells directly, but you would have to go through model.space to get a reference. I guess thats another point for coupling cells to their owners space.

• I changed the handling of empties closer to the old code. This does introduce coupling between a Cell and its owning "Space" with the various drawbacks that it entails. However, select_random_empty_cell now works across OrthogoonalGrid, HexGrid, and NetworkGrid.

I still have hopes that we don't need this coupling. I think we can use raise your select_random_empty_cell function from NetworkGrid to the space base class, because it should work for all spaces. Then we can have more optimized implementations for the grids. But re: coupling. I don't like that the cells manipulates the owners attributes (_empties) directly. This is already based on some assumptions how the owner is implemented. This is basically a performance optimization, but those shouldn't dictate how we implement our methods. But yes, without it, it can be quite slow. Not sure how to proceed with this one.

[quaquel]

I don't think this isolates it too much, this is something that has been on several wish lists.

I just meant that it keeps all experimental code within a single location. That is, in this way, we don't touch any legacy code and thus don't have to worry about backward compatibility and breaking existing features. We can simply go to 2.4 with this as new experimental code.

I look forward to seeing your work on continous spaces and I agree that having some space based movement methods within the base agent class is not a problem perse.

I still have hopes that we don't need this coupling. I think we can use raise your select_random_empty_cell function from NetworkGrid to the space base class, because it should work for all spaces.

Will do.

But re: coupling. I don't like that the cells manipulates the owners attributes (_empties) directly. This is already based on some assumptions how the owner is implemented. This is basically a performance optimization, but those shouldn't dictate how we implement our methods.

Conceptually, I agree. Within the current structure I don't really see another good solution. Some possible directions I still see are (1) to track the number of tries and use this to estimate when we have to construct the full collection of empty cells; (2) base it on the number of agents in the model, but this introduces tight coupling between model and space; (3) pub/sup where Cells fire events when changing their occupancy. Spaces can then subscribe if needed.

[Corvince]

Conceptually, I agree. Within the current structure I don't really see another good solution. Some possible directions I still see are (1) to track the number of tries and use this to estimate when we have to construct the full collection of empty cells; (2) base it on the number of agents in the model, but this introduces tight coupling between model and space; (3) pub/sup where Cells fire events when changing their occupancy. Spaces can then subscribe if needed.

If you agree conceptually I think we shouldn't already break this concept at such an early stage. I tried 1) and think thats a good intermediate solution. Just didn't had the time to find good values. 2) is similar to what we already have, but that actually doesn't always work, because in a MultiGrid you can have lots of agents and still lots of empty cells (this is also problematic in the legacy implementation). 3) sounds like the best solution so far, but requires some work and depends on a general approach towards event sourcing.

Again, in my opinion we shouldn't break good concepts yet just for the sake of performance optimizations. Until the grid is starting to get full an unoptimized version of 1) already leads to good performance.

[quaquel]

If you agree conceptually I think we shouldn't already break this concept at such an early stage

It happened largely because of me trying to chase down the performance difference between this branch and my code from over a week ago. It turned out that this performance difference was unrelated to this code and I did not change it back.

I tried 1) and think thats a good intermediate solution. Just didn't had the time to find good values

I guess we can use the current legacy code to create a number. Will take a look once I have time. The current cutoff implies some expected value, so it should not be too hard.

[quaquel]

I have started adding tests for this code. Coverage is not complete yet. I have focused on the initialization of OrthogonalGrid, HexGrid, and NetworkGrid, as well as the neighborhood calculation for various radii and types of grids. This has resulted in a few minor changes in the code. I think this code is getting close to the point that it is ready for review. Still on my to-do list:

• [ ] make Cell and DiscreteSpace again independent and change Grid.get_random_empty_cell code as discussed above.
• [ ] add tests for CellCollection, Cell, and CellAgent
• [ ] make neighborhood tests more rigorous. At the moment I test explicitly the size and content of _connections, but I only test the size of the neighborhood for radius 1-3 on OrthogonalGrid (Moore, von Neumann) and HexGrids. I want to check explicitly the content of the return neighborhood as well.
• [ ] Add some tests for directed graphs and NetworkGrid.

Further down the line, we can worry about

1. the integration of property grids. I don't think it is overly complicated, but I don't have the bandwidth for it right now
2. make _connections a dict with named connections to enable funky space traversal. Again, see the ideas above

Did I miss anything? If so, please let me know.

[Corvince]

That's great, thank you for your effort! Tomorrow I want to restructure the file, or better to say divide it into different files, because I think it already has become quite unwieldy. Is that okay for you? I don't want to interfere with your efforts

[quaquel]

It's 400 lines, so 25% of the current space module. But indeed, it is getting to a point where it is a bit unwieldy. So I am okay with a reorganization. I am not sure, however, how to cut it up cleanly. Also, if possible can you then reorganize the tests as well so they follow whatever new organization you impose?

I won't work on this tomorrow daytime. I might start working on this again around 19:00 CET. Would that work for you?

[Corvince]

Yes that should work, otherwise I'll postpone it. Thanks for the reminder to also adjust the test structure