Utilities for spatially distributed properties

[AayushSabharwal]

Is your feature request related to a problem? Please describe. Having a property spatially distributed over GridSpace is trivial, but not so much with ContinuousSpace (such as in #519). This is especially because it requires converting between coordinates repeatedly.

This would also come into picture for implementing ContinuousSpace pathfinding, since walkable and heightmap would need to be discretised. The path would also be in grid coordinates, and then would need to be converted back.

Describe the solution you'd like It would be useful to have some features that enable such spatially distributed properties easily. I have two ideas for this:

• Functions such as to_grid_coordinates(continuous_pos, continuous_space_size, grid_size) (and the inverse?)
• A wrapper around AbstractArray that also stores the ContinuousSpace dimensions and can be indexed with continuous coordinates, converting them to the appropriate grid cell coordinates

I prefer the second approach, since it's much cleaner to interact with and can just be dropped into model.properties. It also allows the relevant AStar properties to be <:AbstractArray and agnostic of whatever is dropped in, which could even be AbstractArray wrappers from other packages.

[Datseris]

What benefit do you get by doing this? What's the benefit of pathfinding in continuous space if the path is in grid coordinates?

[AayushSabharwal]

The core of AStar works on a grid, and the algorithm (to my knowledge) is only really applicable on such graphs. The path will be calculated as a series of discrete waypoints, but actually travelling along the graph will be continuous. Agents will move between waypoints at a certain speed instead of jumping from waypoint to waypoint.

A potential benefit of this is if the grid is just a function evaluated over the space, they can pass in a wrapper that just evaluates the function at the point called. Alternatively, the grid could be read from a file (if it's too large to keep in memory). Even without external AbstractArray wrappers in AStar, this would greatly simplify having a property distributed over a space. Usually this entails writing some functions to convert between coordinates, and having to call those functions every time the array is indexed.

This would effectively allow model.some_property[1.23, 4.56] instead of model.some_property[to_grid_pos((1.23, 4.56), model.space.extent, size(model.some_property))...] or model.some_property[to_grid_pos((1.23, 4.56), model)...]

[Datseris]

You misunderstood my question.

What is the benefit of implementing a ABM that uses pathfinding, but on continuous space. I'm challenging the whole thing. Seems to me that GridSpace is the naturally suitable choice...? So, to make the question clearer: is there any reason to implement an ABM with pathfinding in continuous space instead of grid space?

[AayushSabharwal]

Continuous space allows more granularity in agent movement, whereas in grid space the agent has to be at one waypoint or the next. In continuous space, they can be in between and moving with a certain velocity. The notion of speed in GridSpace falls apart since you can only move in discrete steps, so for one agent to move faster than other, it can only really do so in a discrete multiple.

In continuous space, speed is a much easier concept to handle, since agents aren't restricted in their positions. To replicate this in grid space, it would require an extremely granular grid. For example, if I want agent A to move at 1m/s and agent B to move at 1.7m/s, this can only really be realised in grid space if each grid cell is 0.1m (So A moves at 10 steps per second and B at 17), which turns a 100x100m space into 1000x1000 grid. Not only is the extra granularity unnecessary for the pathfinding, it makes pathfinding as well as nearest neighbor searches much slower. Also worth noting is that it requires looping over and calling move_along_route! multiple times in one agent_step!. This also takes significantly more memory, both to store pathfinding data (walkable, heightmap) as well as actual agent paths (since the linked lists are much longer)

Continuous space also provides this disconnect between nearest neighbor searching and pathfinding. In continuous space, the space could be (100, 100) with a spacing of (1, 1) (dependent on nearest neighbor search radius) and a pathfinder granularity of (500, 500) (depends on how well the path needs to be approximated, and could definitely be even lower). This allows faster pathfinding as well as efficient nearest neighbor searches, and also enables the concept of speed to be realised much easier.

@Libbum and I also discussed the possibility of features such as restricted angular velocity, so agents can't instantly turn from facing one direction to their next waypoint, and instead need to turn gradually.

[Libbum]

There is a comparative design choice in this conversation that Netlogo had already made.

There, the underlying space is always a 2D grid. No questions, grids all the way down. They are called patches. There are four allowed agent types, patches being one, two are not relevant to this discussion and turtles. Turtles look in a direction and walk around wherever, although their position is not discrete, it's represented by a float. This is how Netlogo provides a ContinuousSpace-like environment—the turtle agent type.

We have recently moved our continuous space representation closer to MASON, where we have the underlying GridSpace taking care of the neighborhood question. Now we're considering moving closer to Netlogo, where turtle movement is a thing and lots of the continuous space properties are just transactions on a grid. Not saying this is a bad thing, just saying it's a conversation that's been had before by others many times.

You can clearly see what's happening in the ant simulations that we now have two examples of written by two separate authors. Both of which are most likely coming at this model from a Netlogo perspective. Their assumption that you can have a GridSpace agent and a ContinuousSpace agent in the same model is warranted there, since it's just patches and turtles. We have not considered this inevitability.

@Datseris posed the question: is there any reason to implement an ABM with pathfinding in continuous space instead of grid space? I would argue we're not asking that, we're actually asking something more fundamental: what is continuous space?

[Libbum]

Some direction from that last post:

Our @agents macro starts this process moving I feel. We have a GridAgent who must reside in a GridSpace (side note: I don't think we explicitly check that). All of the other agent types do the same.

There's no reason why we can't start creating sub classes of agents that have specific helpers or implementations that Aayush is proposing

mutable struct GridAgent{D} <: AbstractAgent
    id::Int
    pos::Dims{D}
end

mutable struct GridTurtle{D} <: AbstractAgent
    id::Int
    pos::Dims{D}
    heading::Dims{D}
end

mutable struct ContinuousTurtle{D} <: AbstractAgent
    id::Int
    pos::NTuple{D,Float64}
    vel::NTuple{D,Float64}
    heading::NTuple{D,Float64}
end

[Datseris]

I don't understand what information heading contains, and why this information isn't already contained in vel, which contains both the direction of an agent, as well as the speed its heading there.

[Datseris]

Personally I don't agree with much of the proposed design, e.g. being able to do model.property[1.5, 2.5]. One of the principles of good, simple code, is to avoid custom structs as much as possible, and this would definitely require a bunch of wrappers. Not only that, it would also increase the learning curve of Agents.jl. The alternative to_grid_coordinates(continuous_pos, continuous_space_size, grid_size) is simpler in every possible regard, with the expense of being more verbose.

But in any case, simply the argument of speed already convinces me about having pathfinding in continuous space, as birds fly at different speeds than rabbits. Just wanted to make sure we had convincing arguments, as my main job here is to play devil's advocate.

---

Re. Tim's comments: I think what's a continuous space is pretty clear. A space where agent position and velocity are Floats. An underlying discretization of space is done only for nearest neighbor optimization and doesn't really affect the continuous nature of the space. And in fact a high-level user can simply not care about this, in a small performance cost.

I believe NetLogo's "patches" design is bad and should be avoided. There are no "patches" in continuous space. Now what @AayushSabharwal says is different. Here we do have a true spatial field (e.g. the mountain map). The only reason is discretized is not because it is naturally "patches", but because of computational limitations: we don't know an analytic form for this field. In my eyes, all "true" spatial properties of ContinuousSpace would ultimately be functions of position f(x, y) = output. But of course in reality one often has to discretize that. So that's why I agree with having good support for "discretized quantities over continuous space", but the concept of "GridSpace agents in ContinuousSpace" does not convince me yet, nor have I seen yet a reason to have a GridAgent in continuous space. All cases I have seen that ask for a GridAgent in continuous space are actually much better of being standard Julia matrices as model properties, (definitely in the ant implementations).

So what I propose is a way for continuous space to handle well fields. If a given "field" is an Array, then we use the suggested function to_grid_coordinates(continuous_pos, continuous_space_size, grid_size) to aceess it. If the given field is a Function, we pass it the position arguments x, y. So, I believe, the best way forwards is to simply have a high level function get_spatial_property(continuous_pos, Property, model). This uses model.space (which is an instance of ContinuousSpace, and dispatches on Property: if it is Array it does all conversions to discrete indices and access and gives the value. If it is a function, it just passes the continuous_pos to the function.

---

What do you think of the above? Feel free to challenge it and invalidate it as much as possible. My idea is to have a more natural ABM software, that can truly support a truly continuous space.

[AayushSabharwal]

I agree with the comments on Continuous space. The underlying grid space feels like more of an implementation detail to me, rather than a part of the API. It simply facilitates nearest-neighbor searches.

The only reason is discretized is not because it is naturally "patches", but because of computational limitations: we don't know an analytic form for this field. In my eyes, all "true" spatial properties of ContinuousSpace would ultimately be functions of position f(x, y) = output.

Exactly.

get_spatial_property(continuous_pos, Property, model)

I think this is a good way to move forward. A nice addition to this would be getting it to work with ranges as well, instead of just single positions.

[Datseris]

A nice addition to this would be getting it to work with ranges as well, instead of just single positions.

Why? julia already has automatic support for this via broadcasting, get_spatial_property.(range, Ref(Property), Ref(model)).

[AayushSabharwal]

I don't think this would work with multidimensional coordinates. For example:

julia> f(x) = 3x
f (generic function with 1 method)

julia> f.((1:3, 4:7))
(3:3:9, 12:3:21)

julia> collect(f.((1:3, 4:7)))
2-element Vector{StepRange{Int64, Int64}}:
 3:3:9
 12:3:21

julia> collect.(f.((1:3, 4:7)))
([3, 6, 9], [12, 15, 18, 21])

Is there something I'm missing?

[Datseris]

nope youre right

[Libbum]

My point about heading in continuous space was wrong, spit out hastily this morning.

Georges recent comments are crystal clear and I agree on all points.

[Datseris]

Awesome, so I guess we have concluded on a design decision! Happy to do a PR on this myself, but I'll have to do it on my journey back from vacation on the train ride on the 13th