Allowing agents to have size

[kavir1698]

One way is to Extend the SQLite database So that it has one more column, agent's diameter. This will be used to determine when agents interact with one another. Currently, only if the center of an agent is in interaction radius of another one's, they interact.

[Datseris]

Although this is an okay idea, I am not sure whether we should enforce agents to have a field diameter for any continuous space application... It is not always the case that agents in continuous space have size.

[Datseris]

To the best of my understanding, the search happens only in this function: https://github.com/JuliaDynamics/Agents.jl/blob/master/src/core/continuous_space.jl#L217 .

One can extend the left and right limiters by an agent diameter. But I want to propose an alternative than adding a field diameter to the agent, as this requires to add necessary strictness.

I propose to define a function

agentsize(a::AbstractAgent) = ntuple(x -> 0.0, length(agent.pos))

and invite users to extend this function via multiple dispatch for their agent. This is very Julia and will also allow scenarios where agents are not spheres. Then, in the space_neighbors function, we simply adjust the left, right borders based on the result of agentsize.

EDIT2: I realize now this is not the same thing as you say. Here we check the size of the given agent, in your approach we check the size of all other agents. Are these two things interchaengable I wonder?

---

Edit: in general the approach of enforcing structs to have too many specific fields is too much Pythonic and I think we can do better.

[Datseris]

@lhupe the bacteria of your simulations have physical size, and are not spheres. Would you mind telling us how you guys tackle this? How do you find nearest bacteria to a given bacterium? Do you take into account its orientation and shape?

[lhupe]

How do you find nearest bacteria to a given bacterium?

We don't. Since the interactions between two bacteria are completely described by a continuous force, we just find those that are closeish (by binning the bacteria spatially) and compute that force term (which is zero for all bacteria pairs that do not intersect). In order to simulate "hard" bacteria, we just use a very large force.

Do you take into account its orientation and shape?

Kind of. For the actual force computation, we do need a complete representation of the bacteria. For choosing the size of the bins that we use for finding closeish bacteria, we use a worst case approximation for the interaction radius.

[Datseris]

A follow-up question then: Do you find all pairs of bacteria in one-go? Or you go bacterium by bacterium, and find for a given bacterium all of its pairs?

[lhupe]

We loop over all bins, compute the forces of all pairs of bacteria within the bin, then loop over nearby bins and compute the forces of all pairs of bacteria from the one bin and bacteria from the other bin.

Since I don't really understand the previous sentence myself, have some pseudocode!

for firstbin in bins
    for (i, b1) in enumerate(firstbin)
        for b2 in firstbin[i:end]
            do_stuff(b1, b2)

    for secondbin in nearby_bins(firstbin)
        for b1 in firstbin
            for b2 in secondbin
                do_stuff(b1, b2)

where nearby_bins is designed so the same pair of bins is nevere considered twice

[Datseris]

This way of approaching the problem ties excellently with the alternative suggestion for representing a spatial structure. At the moment we use a database from SQLite. What I suggested in #137 to have a standard Array, with element type Vector{Int}. I.e. each bin of the array stores the ids of the vectors in that bin. Then doing what you said above I believe is quite straightforward.

I still wonder whether the database approach is more performant than the Array approach or not... At the moment I am spreading myself too thin over too many projects and decided to not implement it yet. When I get more free time I may be able to do it but it seems that comparing the two approaches is critical before releasing 3.0.

[kavir1698]

This way of approaching the problem ties excellently with the alternative suggestion for representing a spatial structure. At the moment we use a database from SQLite. What I suggested in #137 to have a standard Array, with element type Vector{Int}. I.e. each bin of the array stores the ids of the vectors in that bin. Then doing what you said above I believe is quite straightforward.

We can compartmentalize a real continuous space (as we have now) and retrieve agents within each compartment. But this is a model-specific approach. What if some bacteria have a larger radius of influence? Do we consider all agents in the neighboring nodes too? what if the radius of influence is one and a half nodes long?

Even if the network representation of space is as performant as the database representation, I am worried we may trap ourselves in a design decision that would lead to hacking different model implementations.

[Datseris]

But this is a model-specific approach. What if some bacteria have a larger radius of influence? Do we consider all agents in the neighboring nodes too? what if the radius of influence is one and a half nodes long?

I don't immediately follow here. In the Array approach there are two parameters:

1. The "size" of the array, equivalent with the size of the grid, e.g. 10 by 10 or whatever the user chooses. This is pretty much the "compartment amount".
2. The "radius" of influence, an integer, which chooses the neighboring grid points (i.e. compartments), in the same way that this is done with node_neighbors in GridSpace.

It makes sense for the user to choose these parameters appropriately, according to the physical system. Thus I don't see how " What if some bacteria have a larger radius of influence? " is an issue, as the user is the one that sets this.

what if the radius of influence is one and a half nodes long?

The database approach fails here as well: it finds neighbors in the cityblock metric only, and thus there are neighbors found that are not true neighbors in some other metric, e.g. Euclidean. The solution is to further filter the found neighbors according to some filtering process.

This is the same solution for the compartement approach we discuss here as well: we may filter the found agents based on some arbitrary metric that uses the agent positions. Thus I don't think it can serve as a basis of comparison between the two approaches, as both suffer from it.

Even if the network representation of space is as performant as the database representation, I am worried we may trap ourselves in a design decision that would lead to hacking different model implementations.

This is a very valid concern that I haven't thought about yet. Although I must state, that if the performance benefits are orders of magnitude, one should seriously consider it.

---

There is one more thing to realize. The current space interaction API is defined by the functions space_neighbors, and move_agent!. Nothing stops us from also offering a CompartmentSpace, a continuous space that bases its approach into the Array suggestion here. This other space could offer performance benefits in expense of having less accuracy in the spatial structure.

[Datseris]

Ah, something that we didn't say yet: with the database approach, is it possible to get all interacting pairs in one go? As @lhupe mentioned, and I imagine in continuous space this is of general use, they need to calculate some kind of interaction accross all pairs of neigbhors. To my understanding, in the database approach, this can only by done by looping agent by agent and finding all agent's neighbors, which finds the same neighbors several times over.

In the compartment approach, once two compartments A, B have been checked with each other during the run of A, you do not need to check them again in the run of B.

[kavir1698]

The database approach fails here as well: it finds neighbors in the cityblock metric only

No, because in the database approach, each agent defines its radius. So we can easily have heterogeneous agents. Whereas in the array approach, one has to choose a fixed grid size. What if agents evolve and become different? In the grid approach, there is a tight connection between the distribution of agents' radius and grid. Heterogeneous agents and evolving agents can cause problems along the way.

Although I must state, that if the performance benefits are orders of magnitude, one should seriously consider it.

I agree with that.

To my understanding, in the database approach, this can only by done by looping agent by agent and finding all agent's neighbors, which finds the same neighbors several times over.

It doesn't have to be like that. You could loop through sections of the space and get all agents within that section, and let all pairs interact.

[Datseris]

So we can easily have heterogeneous agents. Whereas in the array approach, one has to choose a fixed grid size. What if agents evolve and become different? In the grid approach, there is a tight connection between the distribution of agents' radius and grid. Heterogeneous agents and evolving agents can cause problems along the way.

Oh damn, you are right, this is a big point!!!

It doesn't have to be like that. You could loop through sections of the space and get all agents within that section, and let all pairs interact.

This seems useful, and we already have the function for it. The code of space_neighbors can be reused to create a function find_agents(left, right) that finds all agents in the space span. We should export this as well!

[Datseris]

A quick performance comment: I do believe that the Array approach will give orders of magnitude speed up, for the simple reason that there is no "search" when looking for neighbors. Of course, you need to first identify which compartment you are in, but once you do, you dont have to "search". Thus, this part will be for sure several orders faster.

What might not be several orders faster is moving agents. In the compartments case, one has to only check if we need to change the compartment of the agent. This is in general quite a trivial operation. I am not sure how much time it takes to update an entry of this database to a new position.

[kavir1698]

I do believe that the Array approach will give orders of magnitude speed up

Maybe not that much because a SQL has a binary search tree structure and finding a value is very fast.

[Datseris]

@kavir1698 if you want to add this, you can use optionally a size field of agent, that is either ::Float64 or ::NTuple{D}. Then entries can be added to the database if agent has this field, and these entries can be used in space_neighbors. Seems a reasonable and optional functionality.

Although it is still not clear to me how you would count neighbors as being inside the radius with non-zero size. Would you require part of it to be in the radius or all of it to be in the radius? Both have pros and cons.

[kavir1698]

Would you require part of it to be in the radius or all of it to be in the radius?

I would consider a agent inside radius even when it partially overlaps with it. This can be an optional.

[ghost]

Any way I can help with the pseudocode?

[ghost]

Have you considered tailoring the back end physics engine?

[Datseris]

Hi @mkstarr , thanks for the interest. There is no backend physics engine here and no pseudo code either. Everything is normal runnable Julia code. The "backend" is an SQLite database with columns the x, y and z coordinates of each agent. When we want to find an agent we simply search the database for agents whose x, y and z coordinates fit the search.

[ghost]

Thank you for the late assistance.

[Libbum]

https://github.com/JuliaRobotics/EnhancedGJK.jl

I've been looking into this as perhaps one method. Solutions like this will also need #155 to be done, so if we were to choose GJK for example, it would make sense to build off of GeometryTypes.

https://github.com/JuliaGeometry/Meshes.jl

Also seems like a project to track, although it looks a little too young for the moment to be building upon.

Originally posted by @Libbum in https://github.com/JuliaDynamics/Agents.jl/issues/402#issuecomment-770999334

[Datseris]

How does Meshes relate to here...?

[Libbum]

Size here does not just imply some radius, which can be given as agent property and dealt with accordingly.

For things like Crowd Dynamics simulations discussed in #277, size means shape which implies some ability to generate convex meshes to represent agents.

[Datseris]

I'm closing this because given the status of the library, any size-having agents would be implemented independently from the space (ContinuousSpace has changed massively from the original discussion in this issue).

Furthermore, it's perfectly possible for agents to have size at the moment. One increases the search radius by the agent radius and takes their size into account, if they are spheres. If not, an advanced filtering of the results of nearby_agents would do the trick for whatever shape.