Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Proposal: Formal neighborhood definition for grids #1900

Open
EwoutH opened this issue Dec 6, 2023 · 44 comments
Open

Proposal: Formal neighborhood definition for grids #1900

EwoutH opened this issue Dec 6, 2023 · 44 comments
Milestone

Comments

@EwoutH
Copy link
Member

EwoutH commented Dec 6, 2023

When implementing #1898, I was inherently playing with spaces. A lot of times closeness (as a spatial relationship) is important, and a lot of time, there is a hard cut-off with a binary result: You are either a neighbor or not.

We have a few nice mechanisms built-in the current neighbor logic:

  • moore: If True, return Moore neighborhood (including diagonals)
    If False, return Von Neumann neighborhood (exclude diagonals)
  • include_center: If True, return the (x, y) cell as well. Otherwise, return surrounding cells only.
  • radius: radius, in cells, of neighborhood to get.

However, it's a bit tedious to pass all those specifications each time you want to use a neighborhood of something. So therefor I would like to have some formal neighborhood specification, so that you can pass one object or variable throughout Mesa and knowing consistently what you need to send and what you get.

@EwoutH EwoutH changed the title Formal neighborhood specification for grids Formal neighborhood definition for grids Dec 6, 2023
@EwoutH
Copy link
Member Author

EwoutH commented Dec 6, 2023

Now really full solution of this, but some thoughts:

  • In it's simplest form, a neighborhood definition can just be a dictionary:
neighborhood_def = {include_center: False, radius: 1, moore: True}
  • It could also be a simple object.
class NeighborhoodDefinition:
    def __init__(self, include_center=False, radius=1, moore=True):
        self.include_center = include_center
        self.radius = radius
        self.moore = moore
  • A dataclass could make this more elegant
  • However, we have to consider different grid types (like hex and network) that take different keywords
  • Each grid could have a get_neighborhood_definition() method that gives a definition that can be used in all methods of that grid type (whether it's a dict, object or something else).

@Corvince
Copy link
Contributor

Corvince commented Dec 9, 2023

An advantage of using a simple dictionary would be to directly use the definition via unpacking. So Imho we could do

grid.get_neighbirhood(pos, **neighborhood_def)

Whenever we need the values in a traditional function.
Or do you suggest changing the API to get_neighborhood(pos, neighborhood_def)?

@Corvince
Copy link
Contributor

Corvince commented Dec 9, 2023

But this issue has let me to think about how we define theesa space API and if we should switch to a more "chainable" API?

So for example instead of doing grid.get_neighbors(pos, moore, radius, center)

We do something like this

grid[pos] # get the current position (a Position)
    .neighborhood(moore, radius, center) # get the neighborhood (a PositionList)
    .agents # get the agents (an AgentList)

So we would have all those intermediate classes with their own attributes and methods.

In this case it might seem a bit verbose, but I think especially combined with properties we can have a much cleaner and more powerful way of extracting the things we want. I mean to say that we can have simpler functions as building blocks for complex logic and not having highly specialized functions like move_agent_to_extreme_value_cell.

What do you think?

@EwoutH
Copy link
Member Author

EwoutH commented Dec 9, 2023

Thanks for the insights!

I like both ideas of the dictionary unpacking and the chainable API (feels a bit like Pandas). I don't know yet which I prefer.

It might be useful to discuss this at the dev meeting.

@EwoutH EwoutH changed the title Formal neighborhood definition for grids Proposal: Formal neighborhood definition for grids Dec 12, 2023
@rht
Copy link
Contributor

rht commented Jan 11, 2024

What about specifying the default values of get_neighborhood params during the grid initialization?

neighborhood_config = {"include_center": False, "radius": 1, "moore": True}
mesa.space.MultiGrid(self.width, self.height, torus=True, neighborhood_config=neighborhood_config)
...
# if you want to deviate from the initial spec
self.model.grid.get_neighborhood(self.pos, moore=False)

Tangent: while writing #1953, I thought about the new API for space along the line of the AgentSet. Had similar conclusions to @Corvince's specification in #1900 (comment), which I assume that @quaquel had thought of as well. Thinking about having a unified consistent API as much as possible, instead of grid[pos], it might be grid.select(agent).neighborhood.shuffle().move(0) or something. But it is also possible to have an optimized separate API each for space, time, sensitivity analysis, data collection, and so on.

@quaquel
Copy link
Member

quaquel commented Jan 11, 2024

I have been thinking a bit about a PositionSet and even discussed it with @EwoutH. I think it is a good idea and should ideally mimic the API of AgentSet. As I indicated in #1953, if having a dedicated class for a GridCell is at least as performant as the current implementation of Grid, It would be quite straightforward, I believe, to create a PositionSet, or GridCellSet, or whatever it is named, class.

@Corvince
Copy link
Contributor

I was playing around with a dedicated GridCell a long time ago and from what I remember the performance was quite bad. But I don't think it is needed for a PositionSet, it should be enough to just store the coordinates. This way it is even independent of the used space, since coordinates are a defining feature of any place in space. The rest can be expanded on-demand.

But regarding GridCell, as I said, I did this years ago. If you have a solid implementation idea in mind it might be worthwhile to experiment.

@quaquel
Copy link
Member

quaquel commented Jan 11, 2024

I agree on the coordinates/tuples point. What keeps tripping me up, however, is the difference between the coordinates and the content at those coordinates. Having a dedicated object for this might help. In fact, multigrid does this already because each cell contains a list.

@quaquel
Copy link
Member

quaquel commented Jan 11, 2024

I was playing around with a dedicated GridCell a long time ago and from what I remember the performance was quite bad.

I have rigged up a very rough first draft and only tested random neighbor access with a neighborhood size of 1 using Moore neighborhood and non-torroidal spaces, but my grid cell implementation appears 2 orders of magnitude faster. This is evidently far from conclusive. Random access works against the caching that is currently in place. My implementation favors retrieval of direct neighbors, so I have no idea yet how it scales to larger neighborhood sizes.

My brain is fried by now because I have been at a workshop. I hope to get back to this over the weekend, but.
no guarantees.

@Corvince
Copy link
Contributor

That sounds promising! However, yes, the real problems slowdown start with torus handling and larger von Neumann neighborhoods. But hey even if it's just as fast as the current implementation it would be worth considering.

Although when the current implementation with positions and content can be confusing I am not sure if this will improve when we have position, cells and content. But I also think part of the confusion stems from our current API and its inconsistencies and ambiguous naming. So definitely room for improvement.

@EwoutH
Copy link
Member Author

EwoutH commented Jan 11, 2024

Honestly don’t know if this is the right direction, but very happy with the discussion and very curious to explore it further. Looking forward to a draft implementation!

My brain is fried by now because I have been at a workshop

Now I’m curious what kind of workshop is able to fry your brain.

@quaquel
Copy link
Member

quaquel commented Jan 13, 2024

That sounds promising! However, yes, the real problems slowdown start with torus handling and larger von Neumann neighborhoods. But hey even if it's just as fast as the current implementation it would be worth considering.

Although when the current implementation with positions and content can be confusing I am not sure if this will improve when we have position, cells and content. But I also think part of the confusion stems from our current API and its inconsistencies and ambiguous naming. So definitely room for improvement.

  1. Performance did not scale well. With radius of 2 it is about as fast as the current implementation, with radius 3 or larger it becomes slower.
  2. In my view, cells would replace positions. Positions are currently a tuple. All it would entail would replace the tuple with some other class with a bit more functionality. This class could still have the x and y coordinate, but also a neighbors attribute to all its neighbors (for fast size 1 lookups, or to make random walks easier as per #1953), as well as be a natural building block for agent behavior at cell level (e.g., grass in WolfSheep).

@quaquel
Copy link
Member

quaquel commented Jan 13, 2024

When implementing #1898, I was inherently playing with spaces. A lot of times closeness (as a spatial relationship) is important, and a lot of time, there is a hard cut-off with a binary result: You are either a neighbor or not.

We have a few nice mechanisms built-in the current neighbor logic:

  • moore: If True, return Moore neighborhood (including diagonals)
    If False, return Von Neumann neighborhood (exclude diagonals)
  • include_center: If True, return the (x, y) cell as well. Otherwise, return surrounding cells only.
  • radius: radius, in cells, of neighborhood to get.

However, it's a bit tedious to pass all those specifications each time you want to use a neighborhood of something. So therefor I would like to have some formal neighborhood specification, so that you can pass one object or variable throughout Mesa and knowing consistently what you need to send and what you get.

A slightly different direction would be to make at least Moore or von Neuman behave identical to torus. That is, they would be part of the arguments used to instantiate the space. Whether this makes sense boils down to a basic question: how often would a user wants to mix both neighborhood definitions in a single model?

@Corvince
Copy link
Contributor

That sounds promising! However, yes, the real problems slowdown start with torus handling and larger von Neumann neighborhoods. But hey even if it's just as fast as the current implementation it would be worth considering.

Although when the current implementation with positions and content can be confusing I am not sure if this will improve when we have position, cells and content. But I also think part of the confusion stems from our current API and its inconsistencies and ambiguous naming. So definitely room for improvement.

  1. Performance did not scale well. With radius of 2 it is about as fast as the current implementation, with radius 3 or larger it becomes slower.
  2. In my view, cells would replace positions. Positions are currently a tuple. All it would entail would replace the tuple with some other class with a bit more functionality. This class could still have the x and y coordinate, but also a neighbors attribute to all its neighbors (for fast size 1 lookups, or to make random walks easier as per #1953), as well as be a natural building block for agent behavior at cell level (e.g., grass in WolfSheep).

Re 1) i think that's still not too bad, given that radius 1 is the most common neighborhood. Was this on a toroidal or non toroidal space?

Re 2) how would that work? If I want to query the grid I can provide coordinates, but how would I provide a cell that I want to receive? Maybe I am missing something.

@quaquel
Copy link
Member

quaquel commented Jan 13, 2024

  1. The space (torroidal, hex, moore, von Neumann) does not really matter. The basic idea is to treat the space like a graph. So in a hexgrid, each cell has six neighbors. In a nontoroidal regular gridded space, a corner cell would have 2 or 3 neighbors. Getting neighborhoods for radius larger than one just involves repeatedly retrieving the neighbors and reducing the radius by 1 (in essence, a form of recursion but across cells). Most of the time goes into building up the network, but retrieving direct neighbors is easy once done.

  2. I guess the querying of the grid by coordinates should always be there. The main practical change would be to let neighborhood methods return a collection of cells while neighbor methods return an AgentSet. Each agent would have grid cell attribute instead or in addition to its pos attribute. So yes, you would have three instead of two things. However, the coordinates would only be used to query things, not per se as a return from any of the methods on the grid. There are various API advantages such as discussed #1953: A random walk would become a one-liner. self.grid.move_to_cell(self.random.choice(self.cell.neighborhood, 1)). A GridCell class would also be a logical basis for adding behavior to the space (although for performance, it would be good to have an ActivePropertyLayer as well for simple behavior.

@Corvince
Copy link
Contributor

Okay I finally get it. You precalculate all the (radius-1) neighborhoods on grid generation. That wasn't clear to me. But its pretty clever if the (one-time) cost isn't too high. But for larger neighborhoods I think its a bit more complicated than recursively reducing the radius, because you don't want to have the same neighbors more than once. And for von Neumann Neighborhoods you need to reduce the radius differently for straight and edge neighbors. Its probably doable but I think involves more logic.

Still I think it might be worthwhile. How does your class look like? Do you have a public branch? Maybe you did this already but since neighborhoods are fixed you I think it can be returned as a tuple instead of a list (probably negligible performance difference) and use slots (should be noticeable).

Regarding API advantages, I don't find your particular example very convincing. I would say its about the same length as
self.grid.move_agent(self, self.random.choice(self.grid.get_neighborhood(self.pos, 1)
But I do think a better API is possible. What about
self.cell.neighborhood.select(n=1).move_to(self)
So a Neighborhood could again be GridCellSet with a similiar query API as Agentset.

@quaquel
Copy link
Member

quaquel commented Jan 13, 2024

  1. multiple neighbors are easily fixed using an orderset via dict approach
  2. Moore and von Neumann just have a basic different neighborhood structure (4 vs. 8 neighbors). The rest solves itself. The same will also work for hexgrids (6 neighbors)
  3. I will clean up the code a bit tomorrow and share it in a public branch. I'll check the use of slots. I had not thought of doing that.
  4. I haven't thought through the API in great detail. Rather, I was thinking of taking a cell-based approach instead of a grid-based approach (sort of bottom-up vs. top-down). Then I saw a link to move_agent_to_neighborhood #1953. I like your suggested API even more. It fits even better with the bottom-up way of doing things.

@Corvince
Copy link
Contributor

Would be great to have a branch, I'll have some time tomorrow and would be interested to take a deep dive

@quaquel
Copy link
Member

quaquel commented Jan 16, 2024

I'll do my best to make a rough draft available by tomorrow. It likely will be more proof of principle rather than a full implementation within mesa.

@Corvince
Copy link
Contributor

Yeah that's fine and what I am looking for!

@quaquel
Copy link
Member

quaquel commented Jan 16, 2024

Yeah that's fine and what I am looking for!

this is the basic code. For a notebook, see here. The code is rough, and performance is fine for direct neighbors/neighborhoods but not for a larger radius. One advantage of having a grid cell like this is that this approach works for hex grids, triangular grids, Voronoi meshes, and any graph-based network. It would allow us to tie the API together across all these types of spaces (to the extent that this is currently not the case, I did not fully check).

from typing import List, Any
import random
from functools import cache

from mesa import Model, Agent

class GridCell:
    @property
    def neighbors(self):
        return [entry.content for entry in self.neighborhood if entry.content != None]
    
    def __init__(self, i:int, j:int) -> None:
        self.i = i
        self.j = j
        self.coords = (i, j)
        self._neighborhood = None
        self.content = None

        self.left: GridCell = None
        self.right: GridCell = None
        self.top: GridCell = None
        self.bottom: GridCell = None
        self.topleft: GridCell = None
        self.topright: GridCell = None
        self.bottomright: GridCell = None
        self.bottomleft: GridCell = None

    def _calculate_neighborhood(self):
        neighborhood = [self.topleft, self.top, self.topright, 
                              self.right, self.bottomright, self.bottom,
                              self.bottomleft, self.left]
        neighborhood = [entry for entry in neighborhood if entry != None]
        self.neighborhood = neighborhood


class Grid:
    def __init__(self, width:int, height:int, torus:bool = False) -> None:
        self.width = width
        self.height = height
        self.torus = torus

        self.cells: List[List[GridCell]] = [[GridCell(j, i) for i in range(width)] for j in range(height)]
            
        # connect within a row
        for row in self.cells:
            for cell1, cell2 in zip(row, row[1::]):
                cell1.right = cell2
                cell2.left = cell1

        if torus:
            for row in self.cells:
                row[0].left = row[-1]
                row[-1].right = row[0]

        # connect across rows
        for entry in zip(self.cells, self.cells[1::]):
            for cell1, cell2 in zip(*entry):
                cell1.bottom = cell2
                cell1.bottomleft = cell2.left
                cell1.bottomright = cell2.right

                cell2.top = cell1
                cell2.topright = cell1.left
                cell2.topleft = cell1.right

        if torus:
            for cell1, cell2 in zip(self.cells[0], self.cells[-1]):
                cell1.top = cell2
                cell1.topleft = cell2.left
                cell1.topright = cell2.right

                cell2.bottom = cell1
                cell2.bottomleft = cell1.left
                cell2.bottomright = cell1.right

        for row in self.cells:
            for cell in row:
                cell._calculate_neighborhood()

    @cache
    def get_neighborhood(self, coords, radius):
        i, j = coords
        
        neighborhood = {}
        if radius==0:
            return {self.cells[i][j]:None}
        else:
            radius = radius - 1
            for cell in self.cells[i][j].neighborhood:
                neighborhood = neighborhood | self.get_neighborhood(cell.coords, radius)
        
        return neighborhood

    def get_neighbors(self, coords, radius):
        neighborhood = self.get_neighborhood(coords, radius)
        
        return [content for entry in neighborhood if (content := entry.conten != None)]

    
    def place_agent(self, agent, pos):
        pass

@Corvince
Copy link
Contributor

Corvince commented Jan 17, 2024

So, I tested your implementation extensively on the Schelling Model and I have to say I am very impressed and excited! This has several advantages:

  1. It is a lot faster than our current Grid. I think one of the main benefits is that we can access the content of the grids much faster.
  2. It really is a lot simpler to support different discrete grid-likes, so it can potentially reduce the amount of code a lot.

I restructured the code a bit. Get_neighborhood and get_neighbors are now primarily functions of the GridCells, not the Grid. The Grid only holds references to the GridCells and is responsible for initially connecting them. This way for other "Grids" (like HexGrid) we only need to modify the get_neighborhood method and the _connect_single_cells method (see below).

3D Grids should also be straightforward to implement. Since we are no longer dependent on the added performance of a list-of-lists implementation we can just use a dictionary for all cells. This way we can always use the pos tuple and don't need to destructure into x, y in several places. Thus we can also swap definition of pos however we want without code changes for placing agents, etc.

Here is my adapted code

class GridCell:
    __slots__ = ["coords", "connections", "content"]

    def __init__(self, i: int, j: int) -> None:
        self.coords = (i, j)
        self.connections = None
        self.content = None

    def neighbors(self, moore=True, include_center=False, radius=1):
        return (
            entry.content
            for entry in self.get_neighborhood(moore, include_center, radius)
            if entry.content != None
        )

    @cache
    def get_neighborhood(self, moore=True, include_center=False, radius=1):
        if radius == 0:
            return {self: None}

        neighborhood = {}

        radius = radius - 1
        for cell in self.connections:
            if moore:
                neighborhood = neighborhood | cell.get_neighborhood(
                    moore, include_center, radius
                )
            else:
                if cell.i == self.i or cell.j == self.j:
                    neighborhood = neighborhood | cell.get_neighborhood(
                        moore, include_center, radius
                    )

        if not include_center:
            neighborhood.pop(self, None)

        return neighborhood


class Grid:
    def __init__(self, width: int, height: int, torus: bool = False) -> None:
        self.width = width
        self.height = height
        self.torus = torus
        self.cells = {
            (i, j): GridCell(i, j) for j in range(width) for i in range(height)
        }
        self._connect_all_cells()

    def _connect_all_cells(self):
        for coords, cell in self.cells.items():
            cell.connections = self._connect_single_cell(coords)

    def _connect_single_cell(self, cell):
        i, j = cell
        directions = [
            (-1, -1),
            (-1, 0),
            (-1, 1),
            (0, -1),
            (0, 1),
            (1, -1),
            (1, 0),
            (1, 1),
        ]
        connections = []
        for di, dj in directions:
            ni, nj = (i + di, j + dj)
            if self.torus:
                ni, nj = ni % self.height, nj % self.width
            if 0 <= ni < self.height and 0 <= nj < self.width:
                connections.append(self.cells[ni, nj])
        return connections

    @cache
    def get_neighborhood(self, moore=True, include_center=False, radius=1):
        return self.cells[coords].get_neighborhood(moore, include_center, radius)

@rht
Copy link
Contributor

rht commented Jan 18, 2024

It is a lot faster than our current Grid.

By how much? This information is critical.

A list of list, or an N-dimensional NDarray is a more compact representation for at least a square grid. As such, the memory consumption of the system after 100 steps (to account for the caching), needs to be compared.

@quaquel
Copy link
Member

quaquel commented Jan 18, 2024

Thanks, @Corvince, for looking at this. Could you share the Schelling example somehow? I might have time to look at this again over the weekend. Could it be an idea to start developing this further in the experimental folder?

@rht memory use should largely be a non-issue. Effectively, this grid implementation is a linked list. The memory use of a single grid cell is marginal: just a few references and the content (no different from the current MultiGrid). The caching is also a non-issue. First, we use functool.cache so you could always do functools.lru_cache if you are concerned about memory. Moreover, this caching solution is probably slightly more performant than a self-build solution, and the main thing you often use (direct neighbors) is not cached but just part of the data structure itself. Also, I have yet to encounter a situation where the model's memory use was the bottleneck. Datacollleciton is a different matter, but not related to this idea. Of course, once this idea is fleshed out more fully it is worth benchmarking its performance both in terms of runtime and memory use. But worrying about that at this stage is in my view an example of premature optimization.

@rht
Copy link
Contributor

rht commented Jan 18, 2024

That SGTM; my remaining concern would be that if it is easy to translate the implementation to Cython. With the cells just being a collection, I think it should be fine. Though I'm not sure how the cache decorator would work out of the box in Cython. I suppose the caching process would happen in the Python layer instead of C layer.

@quaquel
Copy link
Member

quaquel commented Jan 18, 2024

The caching seems to be written in C, so if we decide to move to cython that should not be a major concern.

@Corvince
Copy link
Contributor

Corvince commented Jan 18, 2024

Played around some more and had some interesting ideas, circling this discussion back onto its starting point.

Instead of a dedicated GridCell I now have just a Cell that can be used across all spaces.

class Cell:
    __slots__ = ["coords", "connections", "content"]

    def __init__(coords: Coordinates) -> None:
        self.coords = coords
        self.connections = []
        self.content = []

    def connect(self, other) -> None:
        """Connects this cell to another cell."""
        self.connections.append(other)

    def disconnect(self, other) -> None:
        """Disconnects this cell from another cell."""
        self.connections.remove(other)

    def __repr__(self):
        return f"Cell({self.coords})"

The generic Space class is responsible for creating the cells and connecting them (to be subclassed for concrete space classes like Grid)

class Space:
    def __init__(self):
        self.cells = {} # <= dict of cells, obviously needs some initialization dependend on the concrete Space

        for cell in self.cells.values():
            self._connect_single_cell(cell)

    def _connect_single_cell(self, cell): # <= different for every concrete Space
        ...

    def get_neighborhood(self, coords: Coordinates, Neighborhood: Neighborhood):
        return Neighborhood.of(self.cells[coords])

Here things get interesting. The get_neighborhood function of the Space uses a Neighborhood class, which is a formal definition of a neighborhood of cells. As an example here is a definition for a GridNeighborhood

class GridNeighborhood:
    def __init__(self, moore=True, include_center=False, radius=1):
        self.moore = moore
        self.include_center = include_center
        self.radius = radius

    @cache
    def of(self, cell, radius=None):
        """Heavily optimized. You don't need to understand it, just skip it"""
        radius = self.radius if radius is None else radius

        if radius == 0:
            neighborhood = {cell: cell.content}
        else:
            neighborhood = {}
            for neighbor in cell.connections:
                if (
                    self.moore
                    or neighbor.coords[0] == cell.coords[0]
                    or neighbor.coords[1] == cell.coords[1]
                ):
                    neighborhood.update(self.of(neighbor, radius - 1))
            if radius == self.radius and not self.include_center:
                neighborhood.pop(cell, None)

        return neighborhood

As you can see we move all the logic on how to receive a neighborhood into a dedicated class that has a single responsibility - return the neighborhood of a cell. It returns a dictionary like the following

{ Cell(0, 0): [Agent] 1, Cell(0, 1): [Agent2, Agent3]}

This means we get both the neighborhood as cells and the neighbors in once function call. No more confusion between neighborhood and neighbors. You want the cells? Use dict.keys(). You want the agents? Use dict.values().

With this basic setup we can achieve a very high amount of reusability. Since we always use the same cells with the same properties we can implement most space functions just once. Agent movements are just going from one cell to another. Empty cells are just cells which have an empty list of content.

Speaking of which its important that the content is a list or any other mutable object. This way we can simply cache the neighborhood including agents. The neighborhood dictionary is just a mapping of cell: cell.content, so just a reference to the content. Any changes are automatically reflected.

For the API usage this will look like this

# somewhere in your code
Neighborhood = GridNeighborhood(True, False, 1)

# For a Schelling agent:
for neighbors in Neighborhood.of(self.cell).values():
    if neighbors and neighbors[0].type == self.type:
        self.similar += 1

# Normal Access through grid
model.grid.get_neighborhood((17, 23), Neighborhood)
# Alternatively
Neighborhood.of(model.grid[(17, 23)])

Looking forward to your comments on this! Hope to publish my experiments in a branch tomorrow, but needs some cleanup

@quaquel
Copy link
Member

quaquel commented Jan 19, 2024

I am impressed by your improvements upon my first rough implementation. Some testing showed that the problem I ran into with bad scaling to higher radii is now gone. This is probably because of the heavy optimization in GridNeighborhood.off, which indeed took me twice to comprehend. Getting a Neighborhood class and getting rid of the current distinction between neighborhood and neighbors is also great. I look forward to seeing the full code in a branch later.

For some some quick thoughts (and I am happy to contribute wherever you want input).

  1. I guess Cell is useful for all discrete spaces. I don't see how you would use it in ContinuousSpaces.
  2. I like the logic of GridNeighborhood, but I am not entirely sure of the API of Space.get_neighborhood at the moment. It seems something is missing in the provided code.
  3. It seems you dropped Cells.neighborhood, or should Cell.connections return a GridNeighborhood instance?
  4. We have had various discussions about something like a PositionSet. Some of this seems close to GridNeighborhood. One possible extension might be to create something like a CellCollection class with methods like select_random, select, shuffle, and get_content. It could subclass dict to have the keys and values behavior you are describing. Next, GridNeighborhood might be or subclass CellCollection. The key difference is that GridNeighborhood is the neighborhood of a given cell and for a given radius, while CellCollection is just a collection of Cells. Grid.empties, for example, could be a CellCollection.

@Corvince
Copy link
Contributor

Corvince commented Jan 19, 2024

Thank you for your quick feedback! Even though it looks very different now you initial draft was invaluable for me! At first I tried together with ChatGPT to create a slightly different implementation for the neighborhood search, but it ended up much worse, so I took your solution and just incrementally improved it. On the comprehensiveness: I only got the cache to work on the last iteration. With the cache in place it could probably reverted to a more readable solution, but lets not hang on implementation details.

  1. I guess Cell is useful for all discrete spaces. I don't see how you would use it in ContinuousSpaces.

Probably yes and I won't think too much about ContinuousSpaces just yet - but internally ContinuousSpace already uses some form of discrete grid, so maybe it can actually can be made to interop nicely.

  1. I like the logic of GridNeighborhood, but I am not entirely sure of the API of Space.get_neighborhood at the moment. It seems something is missing in the provided code.

The implemenation is correct, but the naming is a bit off. Neighborhood here refers to the defintion of the neighborhood, like in GridNeighborhood class. But currently it only implements Neighborhood.of so maybe it should just be a factory function that returns a get_neighborhood function? Something like

get_neighborhood_of = create_neighbord_getter(moore=True, include_center=False, radius=1)
  1. It seems you dropped Cells.neighborhood, or should Cell.connections return a GridNeighborhood instance?

I mainly renamed neighboorhood to connections. I think this way its clearer, because in the example of a regular grid von Neumann and Moore neighboorhoods are different things, but the connections are the same. I mean it depends on how you connect your cells and this is somewhat arbitrary on purpose. But for this reason I found connections to be more general and hence the explicit connect and disconnect functions. So you could connect Cells dynamically. The type is just a list of connected Cells. Maybe this should be a private variable to be honest.

  1. We have had various discussions about something like a PositionSet. Some of this seems close to GridNeighborhood. One possible extension might be to create something like a CellCollection class with methods like select_random, select, shuffle, and get_content. It could subclass dict to have the keys and values behavior you are describing. Next, GridNeighborhood might be or subclass CellCollection. The key difference is that GridNeighborhood is the neighborhood of a given cell and for a given radius, while CellCollection is just a collection of Cells. Grid.empties, for example, could be a CellCollection.

I have been thinking about this too during breakfast. I think this is indeed the way to go. I think this will also be more intuitive to use than the currently returned dictionary. Because although its nice if you know how it works, its not imminent that cells are keys and content are values. So it would look more like

neighborhood = get_neighborhood_of(self.cell)
for agent in neighborhood.agents:
    pass

and for a random cell

agents = neighborhood.select_random().contents
# Maybe even return a random agent directly, across the CellCollection?
agent = neighborhood.select_random_agent()

In summary I think there are still some open naming questions but I really like the direction this is going

@Corvince
Copy link
Contributor

Just really quick since I am about to leave and wanted to drop you something for the weekend. Here is a branch with some implementations of the discussed things.
There are mainly 2 new files: gridspace.py and schelling.py, the latter with how its used
https://github.com/projectmesa/mesa/tree/experimental/cell-space

Pretty much work in progress, but I think I wont be able to continue work until next week

@quaquel
Copy link
Member

quaquel commented Jan 19, 2024

Thanks for that. I'll see what I can do over the weekend. First, I have an ABM MESA exam to make for my students.

@quaquel
Copy link
Member

quaquel commented Jan 19, 2024

I started playing with the code drawing on #1978. Below are my notes of what I run into. I hope to have my version of the code on GitHub by the end of the weekend.

It seems that create_neighborhood_getter which, in my impression, is your way of encapsulating formal neighborhood definitions, gives a substantial slowdown compared to your earlier code. I moved this to code back into the Cell class. When testing only getting a neighborhood in isolation, this reduces runtime by a factor of 5-7, close to where it was with your first draft. At the level of Schelling, using #1978, however, the performance difference seems smaller. So, I have no idea what is going on. Perhaps caching at a method call does not work correctly?

Another possible bottleneck is Cell.content. Currently, in @Corvince implementation, it is a list. Changing to a dict and testing with Schelling gives me a factor 4 speed up on the benchmark. Next, I changed it back to a list, but changed remove_agent to

        try:
            self.content.remove(agent)
        except ValueError:
            pass

which gives a similar speed up. So the current bottleneck is the if agent in self.content: check.

Another point is Grid.empties. This is a property that builds a CellCollection on the basis of Grid._empties. However, in for example, in move_to_empty there are multiple calls to Grid.empties. Changing num_empty_cells = len(self.empties) to num_empty_cells = len(self._empties) already gives a factor 2 to 3 speedup. I am trying to take a closer look at how empties is done as a whole and see if I can make it even cleaner.

I will continue to play with this over the weekend if time allows for it.

@quaquel
Copy link
Member

quaquel commented Jan 21, 2024

So an update. Below is the performance comparison as generated by @EwoutH benchmark. It contains both Schelling and WolfSheep, updated to use the new Grid class.

Model Size Init time [95% CI] Run time [95% CI]
Schelling small 🔴 +316.6% [+314.1%, +319.2%] 🟢 -9.1% [-9.6%, -8.5%]
Schelling large 🔴 +263.0% [+259.5%, +266.7%] 🟢 -15.5% [-17.0%, -14.1%]
WolfSheep small 🔴 +105.5% [+104.1%, +106.8%] 🟢 -22.2% [-22.9%, -21.6%]
WolfSheep large 🔵 -8.0% [-21.7%, +18.9%] 🟢 -36.5% [-37.9%, -35.2%]
BoidFlockers small 🔵 -2.2% [-3.0%, -1.2%] 🔵 -1.0% [-1.6%, -0.3%]
BoidFlockers large 🔵 +0.7% [-0.5%, +2.0%] 🔵 -0.1% [-0.4%, +0.2%]

My code can be found at https://github.com/quaquel/mesa/tree/cell-space. It is still very much WIP. But some key points

  1. Changes in move_to_empty to use a dict. This is an order of magnitude improvement compared to the previous version
  2. I changed create_neighborhood_getter back into a method on Cell. This is about a factor 2 speed up for Schelling. I am still wondering whether we should handle Moore vs. von Neumann like we handle torus (so at the grid level rather than in the neighborhood method).
  3. I fixed a radius error in create_neighborhood_getter .
  4. I played around with various other things. For example, using AgentSet for Cell.content or using a WeakRefDict. This is very slow and a bad idea. I tested Cell.connections as a CellCollection. This was not so bad performance-wise, but the code became a mess. I also played around with the responsibility of moving agents. I now handle most of it in the cell with the exception of move_to_empty, which has to be done at the grid level. I am still unsure about the cleanest API for this.
  5. I haven't looked at the grid initialization at all. But it would be worth looking to see what we can do.
  6. I contained all changes in the gridspace module (including the change to agent). I also did some renaming etc.
  7. For a sense of how to use the new Grid, look at the schelling and WolfSheep model in the benchmark folder.

@EwoutH
Copy link
Member Author

EwoutH commented Jan 21, 2024

Very interesting. I've been a fly on the wall for the last part of this discussion, I will try to properly read up on it tomorrow or Tuesday.

@Corvince
Copy link
Contributor

Thanks for the valuable feedback @quaquel ! I also modified some code and pushed an update to my branch. Some things we updated in parallel, I picked up some ideas from you and also made some changes based on ideas that have been floating around here and there (thanks to everyone for those).

As it is now, I find not only the potential performance gains interesting, but even more so I find the new syntax to be more expressive. I think thats an even better advantage. Plus this would give us a chance to remove a lot of code crust. A few changes I made:

  1. In Cells I renamed content to agents. I think agents are special enough to deserve their own name and handling.
  2. I also added a "capacity" attribute, so we can model SingleGrids and fine-grained MultiGrids.
  3. I added a "properties" dictionary to store any other information. Ideally this would also provide views into the propertylayer, but I haven't looked into it.
  4. Added is_empty and is_full properties
  5. In CellCollection added select_random_cell, select_random_agent and select function
  6. In Space Simplified the handling of empty cells. This still gives me some headaches and is currently only partially working - it just selects random cells until it finds an empty one. Needs some heuristic to stop looking and build a full list of empty cells. But I explicitly removed the _empties set, because I don't want to have a tight coupling between Space and Cells.

Performance difference is about 30% for the schelling example compared to main branch.

2. I changed create_neighborhood_getter back into a method on Cell. This is about a factor 2 speed up for Schelling. I am still wondering whether we should handle Moore vs. von Neumann like we handle torus (so at the grid level rather than in the neighborhood method).

The reason why I kept this outside is to make Cell as independent as possible of the concrete space. The current implementation is coupled to a Grid. I think it shouldn't be so much slower. Maybe you did the same "mistake" I did in the beginning and recreated the neighborhood_getter on each step? Because while creating the getter isn't costly in terms of performance, but you lose the cache. So you need to define the getter as a class or instance variable. Clearly this isn't ideal. Maybe we could define a default_neighborhood for the Cell constructor that is used for get_neighborhood?

The reason I used a create_neighborhood_getter btw is specifically to allow fine-grained optimizations like splitting moore vs von Neumann. Currently it just creates a single function to handle all cases, but it would be simple to rewrite to return either a moore or a von Neumann function. I think the name "neighborhood_getter" isn't optimal, because the basic idea is that you have a function that takes a cell as its first argument and does something to it. So getting the neighborhhood is just one of many examples (albeit probably the most common).

Thats it for now. I may post more later, but lets see how my work goes today.

@quaquel
Copy link
Member

quaquel commented Jan 23, 2024

Just some quick thoughts before I am in to meetings all day.

  1. I want to go back and figure out why I saw the massive performance difference in create_neighborhood_getter. I don't think it is the caching because I started from your code. But it would be good to figure out what explains it. In principle, I like the idea of using closures to encapsulate the neighborhood definition.
  2. I still want to know why we don't handle von Neumann vs. Moore like we handle torus. So, at the level of the creation of the grid. Is there any use case where you use both neighborhood definitions within the same model and on the same grid?
  3. Most other changes you made were on my to-do list, so it's good to see them done.
  4. The empties stuff was also giving me headaches. I have a few more ideas on this as well.
  5. Why do you want to avoid a tight coupling between cell and grid?
  6. It would be good to try to merge our disparate efforts into a single branch at some point in the near future to avoid duplicating efforts.

@Corvince
Copy link
Contributor

Corvince commented Jan 23, 2024

Just some quick thoughts before I am in to meetings all day.

  1. I want to go back and figure out why I saw the massive performance difference in create_neighborhood_getter. I don't think it is the caching because I started from your code. But it would be good to figure out what explains it. In principle, I like the idea of using closures to encapsulate the neighborhood definition.

Agreed this needs some investigating, before going forward. Again, I don' like the current semantics any way, so lets see where we go with this..

  1. I still want to know why we don't handle von Neumann vs. Moore like we handle torus. So, at the level of the creation of the grid. Is there any use case where you use both neighborhood definitions within the same model and on the same grid?

You are somewhat correct that this is rather unorthodox. It depends a bit on 1), but I just don't want to be unnecessarily restrictive. But performance wise its a single if statement, so it shouldn't really have an impact

  1. Why do you want to avoid a tight coupling between cell and grid?

Basically following the SOLID principles here and to have a clearer structure here. The space classes hold references to the Cell classes and may act upon them. But the cell class can exist independent of the space class. The usual benefits are that this makes the code easier to test and reason about.

  1. It would be good to try to merge our disparate efforts into a single branch at some point in the near future to avoid duplicating efforts.

Agreed. I think in my next work effort I'll put the code into the mesa experimental folder and open a draft PR. I will do this on my mesa fork and give you write access, so we can work on this together.

@quaquel
Copy link
Member

quaquel commented Jan 23, 2024

On 2, if you encode Moore/von Neuman in the connections, neighborhood getting becomes universal across all discrete grids (so excel like, hex, networks, triangular, voronoi, etc). Or you get the slightly strange conceptual issue that non "excel" discrete spaces use a Moore neighborhood. It also makes the need for a formal neighborhood definition less important because it reduces to the neighorhood of a cell for a given radius. I am not so worried about performance for exactly the reasons you have given.

On 5, clear and makes sense although I still wonder whether cells can exist outside of some DiscreteSpace. But from a coupling and testing point of view, I agree.

I quickly looked at your code as well. I noticed the use of a cached_property, which seems to imply that for you, CellCollections are immutable. Is this indeed your intention?

@EwoutH
Copy link
Member Author

EwoutH commented Jan 23, 2024

Finally had made time to read up! Maybe some stuff is already outdated (I tried to check for it), but here are my thoughts:

  1. The basic idea is to treat the space like a graph.

I like this. Would, and if so how, that work for continious? Or will GridCells be by definition discrete?

You precalculate all the (radius-1) neighborhoods on grid generation.

Can we make this optional?

        self.cells = {
            (i, j): GridCell(i, j) for j in range(width) for i in range(height)
        }

I like this above a list of lists. Would there still be ways to quickly access a row or column if needed, for example for torus (row[0], column[-1], etc.)?

The caching seems to be written in C

This would mainly be useful for keeping track of neighbours (as agents) in your neighbourhoods right? Can we expose this to users, that they can cache any type of neighbourhood they like?

Instead of a dedicated GridCell I now have just a Cell that can be used across all spaces.

Would be amazing!

    def _connect_single_cell(self, cell): # <= different for every concrete Space
        ...

Might this make it difficult to create optimized implementations that connects a whole grid together at once (on init for example)? Or could we use another method there?

The get_neighborhood function of the Space uses a Neighborhood class, which is a formal definition of a neighborhood of cells.

Really nice that we got back to the original issue!

This means we get both the neighborhood as cells and the neighbors in once function call. No more confusion between neighborhood and neighbors. You want the cells? Use dict.keys(). You want the agents? Use dict.values().

This is fucking brilliant.

I guess Cell is useful for all discrete spaces. I don't see how you would use it in ContinuousSpaces.

Was also thinking about that. I would really like support for Cells as Voronoi space. Just define a bunch of points in a continuous space, and whatever point is closest to you, in that space you are now. Neighbors of cells are all that share an edge/point.

It would also amazing to just support loading in a custom polygons as cells. But we might get into mesa-geo space, @wang-boyu what do you think?

I find not only the potential performance gains interesting, but even more so I find the new syntax to be more expressive.

Agreed, we can take minor performance hits (~10% on model level) for an better API. Man-hours are generally more expensive than compute-hours.

Plus this would give us a chance to remove a lot of code crust.

Really looking forward to this, the Space module is getting too big (I'm a part of it, sorry).

I added a "properties" dictionary to store any other information. Ideally this would also provide views into the propertylayer, but I haven't looked into it.

At some point we have to think about how they interface. Currently the PropertyLayer is an specialized tool mainly targeted at the square Grids, so maybe it can become a specialized implementation for that.

In CellCollection added select_random_cell, select_random_agent and select function

Maybe general select functions with random/closest as a keyword? Like how AgentSet.select() works?


I just want to say this right here is the pinnacle of open source. On of the most insightful and productive discussions I ever read. Most question I had when starting at the top of the discussion where addressed somewhere in it. Truly iterating on both's best ideas. You guys rock!

@Corvince
Copy link
Contributor

Thank you @EwoutH for your words, this is really really encouraging!

On 2, if you encode Moore/von Neuman in the connections, neighborhood getting becomes universal across all discrete grids (so excel like, hex, networks, triangular, voronoi, etc).

@quaquel
I think I finally understand what you are getting at. You mean Moore/von Neumann only determines how cells are connected and get_neighborhood with a radius of 1 just returns all the directly connected cells, with radius 2 the connected cells of the connected cells etc. And von Neumann cells have 4 Connections, Moore 8 connections.

I think that's a brilliant approach! It simplifies the neighborhood and makes it generally applicable.

Will try this out tonight.

@Corvince
Copy link
Contributor

On reading your comment again after I understood it, I realize I just repeated what you wrote 😅

@quaquel
Copy link
Member

quaquel commented Jan 23, 2024

Some quick replies

  1. Yes, it is, in essence, a graph, although the data structure we created is a variant of a doubly linked list, I guess. Torus is explicitly encoded in the data structure because the last cell refers back to the first. I would be inclined to handle Moore and von Neuman in the topology (so in the links) rather than in the neighborhood calculation.
  2. Any neighborhood you retrieve once is currently cached (so different radii, and across Moore/von Neumann, and for different cells).
  3. We deliberately use a dict to retrieve individual cells quickly. This structure is not optimized for fast row or column access. I also don't immediately see a need for fast row or column retrieval. In the worst case, you generate the coordinates and retrieve the cells one at a time.
  4. _connect_single_cell is how you define your topology (so "excel like" grids, hex grids, triangular meshes, Voronoi, or graphs). It should be optimized for each grid class and will always be called during the init.
  5. The beauty so far is that we have less code, more expressive API, and faster performance.
  6. No, don't try to make a generic select function. The code becomes a mess, and the arguments are impossible to remember. Having a few well-named methods with more focused usage is easier for implementation and users.

EwoutH pushed a commit that referenced this issue Feb 27, 2024
## Summary
This PR introduces an alteranative implementation for discrete spaces. This implementation centers on the explicit inclusion of a Cell class. Agents can occupy cells. Cells have connections, specifying their neighbors. The resulting classes offer a cell centric API where agents interact with a cell, and query the cell for its neighbors. 

To capture a collection of cells, and their content (_i.e._, Agents), this PR adds a new CellCollection class. This is an immutable collection of cells with convenient attribute accessors to the cells, or their agents. 

This PR also includes a CellAgent class which extends the default Agent class by adding a `move_to` method that works in conjunction with the new discrete spaces. 

From a performance point of view, the current code is a bit slower in building the grid and cell data structure, but in most use cases this increase in time for model initialization will be more than offset by the faster retrieval of neighboring cells and the agents that occupy them.

## Motive
The PR emerged out of various experiments aimed at improving the performance of the current discrete space code. Moreover, it turned out that a cell centric API resolved various open issues (_e.g._, #1900, #1903, #1953). 

## Implementation
The key idea is to have Cells with connections, and using this to generate neighborhoods for a given radius. So all discrete space classes are in essence a [linked data structure](https://en.wikipedia.org/wiki/Linked_data_structure).

The cell centric API idea is used to implement 4 key discrete space classes: OrthogonalMooreGrid, OrthogonalVonNeumannGrid (alternative for SingleGrid and MultiGrid, and moore and von Neumann neighborhood) , HexGrid (alternative for SingleHexGrid and MultiHexGrid), and Network (alternative for NetworkGrid). Cells have a capacity, so there is no longer a need for seperating Single and Multi grids. Moore and von Neumann reflect different neighborhood connections and so are now implemented as seperate classes. 

---------

Co-authored-by: Jan Kwakkel <j.h.kwakkel@tudelft.nl>
quaquel added a commit to quaquel/mesa that referenced this issue Apr 9, 2024
## Summary
This PR introduces an alteranative implementation for discrete spaces. This implementation centers on the explicit inclusion of a Cell class. Agents can occupy cells. Cells have connections, specifying their neighbors. The resulting classes offer a cell centric API where agents interact with a cell, and query the cell for its neighbors. 

To capture a collection of cells, and their content (_i.e._, Agents), this PR adds a new CellCollection class. This is an immutable collection of cells with convenient attribute accessors to the cells, or their agents. 

This PR also includes a CellAgent class which extends the default Agent class by adding a `move_to` method that works in conjunction with the new discrete spaces. 

From a performance point of view, the current code is a bit slower in building the grid and cell data structure, but in most use cases this increase in time for model initialization will be more than offset by the faster retrieval of neighboring cells and the agents that occupy them.

## Motive
The PR emerged out of various experiments aimed at improving the performance of the current discrete space code. Moreover, it turned out that a cell centric API resolved various open issues (_e.g._, projectmesa#1900, projectmesa#1903, projectmesa#1953). 

## Implementation
The key idea is to have Cells with connections, and using this to generate neighborhoods for a given radius. So all discrete space classes are in essence a [linked data structure](https://en.wikipedia.org/wiki/Linked_data_structure).

The cell centric API idea is used to implement 4 key discrete space classes: OrthogonalMooreGrid, OrthogonalVonNeumannGrid (alternative for SingleGrid and MultiGrid, and moore and von Neumann neighborhood) , HexGrid (alternative for SingleHexGrid and MultiHexGrid), and Network (alternative for NetworkGrid). Cells have a capacity, so there is no longer a need for seperating Single and Multi grids. Moore and von Neumann reflect different neighborhood connections and so are now implemented as seperate classes. 

---------

Co-authored-by: Jan Kwakkel <j.h.kwakkel@tudelft.nl>
@EwoutH EwoutH added this to the v3.0 milestone Sep 9, 2024
@EwoutH
Copy link
Member Author

EwoutH commented Sep 21, 2024

Sparked by #2309, maybe each Cell should have a neighborhood definition, which by default is inherited from the space it’s in, but can be overwritten. A space also has a default neighborhood definition for cells, which also can be overwritten.

So basically:

  1. Cell checks if it has own neighborhood def, it not, check from space
  2. Space checks if it has an definition, if not, use default

@EwoutH
Copy link
Member Author

EwoutH commented Oct 2, 2024

One idea Jan and I had in a call is letting the CellCollection (or a mask) represent a neighbourhood, and then writing a utility function that can take things like:

def_to_collection(include_center=False, radius: 1, moore: True):
    ...

or def_to_mask, etc.

@EwoutH EwoutH modified the milestones: v3.0, v3.1 Oct 2, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants