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: Flexible move_agent method that allows multiple movement strategies #1903

Open
EwoutH opened this issue Dec 11, 2023 · 5 comments
Open

Comments

@EwoutH
Copy link
Member

EwoutH commented Dec 11, 2023

The Mesa Space module allows a few specific agent movements and interactions within a grid environment. However, the current methods lack a consistent way to apply different movement strategies. This proposal suggests integrating a single, versatile move_agent method, accepting a parameter that can either be a tuple for specific coordinates, a string indicating a movement strategy (like "random" or "empty"), or an object defining a neighborhood.

In the future, it can be extended with movement strategies based on properties (see #1898).

Motivation

I was building a toy model, and

x = self.random.randrange(self.grid.width)
y = self.random.randrange(self.grid.height)
self.grid.place_agent(a, (x, y))

just looked weird and limited.

Proposed changes

  1. Unified move method:

    • move_agent(agent: Agent, destination) → None
    • The destination parameter is versatile:
      • It can be a tuple (x, y) for moving the agent to specific coordinates.
      • It can be a string, such as "random" for a random cell, "empty" for a random empty cell.
      • It can be an object or a dictionary defining a neighborhood, allowing custom definitions of neighboring cells. For this we need a formal neighborhood definition, see Proposal: Formal neighborhood definition for grids #1900.
  2. Retiring redundant methods:

    • Methods like move_to_empty and place_agent would be redundant and can be removed, as their functionalities are integrated into the new move_agent.
  3. Enhanced out-of-bounds and validity checking:

    • Maintain out_of_bounds method, but possibly enhance it to include checks for cell occupancy, ensuring valid movement destinations.
  4. Agent removal and position swapping:

    • remove_agent and swap_pos methods remain useful and unchanged.

Example Implementations

  • Moving to a Specific Cell:
    space.move_agent(agent, (x, y))
  • Moving to a Random Cell:
    space.move_agent(agent, "random")
  • Moving to a Random Empty Cell:
    space.move_agent(agent, "empty")
  • Moving to a Custom-Defined Neighborhood:
    (see Proposal: Formal neighborhood definition for grids #1900)
    neighborhood_def = {"type": "Moore", "radius": 2}
    space.move_agent(agent, neighborhood_def)

Conclusion

This proposal aims to simplify and unify the movement methods in the Mesa Space module. By consolidating various movement strategies into a single method, we enhance the API's usability and flexibility, allowing users to execute complex movements with minimal and more intuitive code.

Notes

Structural Pattern Matching in Python 3.10 might help a lot with the implementation.

@EwoutH
Copy link
Member Author

EwoutH commented Dec 11, 2023

I was thinking about how this would integrate with the _PropertyGrid introduced in #1898. That currently offers separate functions for the selection of target cells, and then moving to the target cells.

def select_cells_by_properties():
def move_agent_to_cell_by_properties():
def select_extreme_value_cells():
def move_agent_to_extreme_value_cell():

If move_agent would also take a list or mask of target cells, that could allow removing the two movement methods from #1898, and make the API more consistent. All movement goes through move_agents, and any amount of custom methods can be written to select some target cells.

Currently, #1898 also include two mask functions which limit the number of candidate cells to cells empty or in a neighborhood.

def get_empty_mask():
def get_neighborhood_mask():

We might also want to integrate that into the move_agent method. It could take a mask or a list of masks.

A utility method to combine a list of masks into a single mask could also be provided.

@EwoutH
Copy link
Member Author

EwoutH commented Dec 11, 2023

Maybe we can combine things:

def move_agent(agent, pos=None, empty=False, neighborhood=None, mask=None, selection="random"):
  • pos: A single position or list of possible positions
  • empty: False allows all cells, True only empty ones
  • neighborhood: Optional neighborhood (Proposal: Formal neighborhood definition for grids #1900)
  • mask: a mask or list of masks of allowed input cells
  • selection: Can be "random" or "closest". Maybe something else in the future (in the _PropertyGrid it could be highest or lowest maybe).

@EwoutH
Copy link
Member Author

EwoutH commented Dec 17, 2023

@jackiekazil @tpike3 Same story as with #1905, I would like to discuss and potentially implement this before moving on the PropertyLayer (#1898), since this is a more generalized solution for a problem that I specifically solve in that PR. So if we can implement this, it would make especially the _PropertyGrid in #1898 a lot simpler.

So my specific questions are:

  1. Do you agree we should expand the built-in move_agent() movement method to allow moving to an empty, random or neighbouring cell?
  2. What do you think of the current proposed API? Do you like the initial one better or the last one?

@EwoutH
Copy link
Member Author

EwoutH commented Dec 21, 2023

I went for a relatively simple implementation: The move_agent method now can take a list of positions and choose either one randomly or the closest:

Selecting neighborhoods and empty cells can be done with other functions, and support for masks will be added in #1898.

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
Copy link
Member Author

EwoutH commented May 6, 2024

There is still possibility for improvement here. The current most elegant way to place an agent on an empty cell I discovered is:

self.grid.place_agent(agent, pos=mesa.model.random.choice(list(self.grid.empties)))

This can't be the best way. The current problems are:

  • place_agent doesn't directly allow selecting an empty cell, or a random cell for that matter. It needs a single position, and doesn't allow a list of positions like move_agent
  • All move functions (move_to_empty, move_agent_to_one_of and move_agent) require a current position to be had, since they call remove_agent internally.

I would like to discuss how we can make placing an agent on a random empty cell more elegant.

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

1 participant