Pathfinding extensions - Githubissues

AayushSabharwal commented 3 years ago

I had an idea about a possible implementation for this. It's a breaking change, however. I came across @Datseris' comment in src/spaces/grid.jl:66:

# TODO: This is bad design. `AStar` should not be mentioned here,
# nor any `Pathfinding` business. This file should be "pure".
astar = pathfinder === nothing ? nothing : Pathfinding.AStar(d, periodic, pathfinder)

The only reason this is here is because AStar takes its dimensions and periodicity from the space. Even for ContinuousSpace pathfinding, none of the functionality needs any relation to the space. What if this was moved to the model? This also eliminates having to modify ContinuousSpace in any way. The user passes in Pathfinder structs, which the model turns into AStar structs.

This also ties into the part of my proposal for allowing better control over pathfinding, and specifically having multiple "profiles" and allowing a choice of which to use. Let the existing Pathfinder struct be renamed to GridPathfinder. ABM then has a field of type Pathfinder, which is a new struct:

struct Pathfinder{P}
    profile_map::Dict{Int,Int}  # maps agent ID to profile
    profiles::P # `AStar` or `Vector{AStar}` if there are multiple profiles
end

The constructor takes a single/list of GridPathfinder along with dimensions and periodicity and initializes itself accordingly.

There's probably a way to eliminate profile_map in case there is only one profile.

set_target!, set_best_target!, heightmap, walkmap take an additional parameter profile::Int = 1 which only needs to be specified if there are multiple profiles
move_along_route!, is_stationary, kill_agent! use the appropriate profile from profile_map for the specified agent

To add support for ContinuousSpace, all that's needed is a ContinousPathfinder struct that the user can pass to ABM, which in turn passes it to the Pathfinder constructor. Then an additional method for move_along_route!, set_target!, since coordinates need to be converted to- and from- grid indices, and some edge cases in the path calculation.

It's a little complicated, and certainly needs both experimentation and profiling. Hopefully I've explained everything clearly

Libbum commented 3 years ago

Conceptually, this seems reasonable to me, and was essentially how things were implemented initially. @Datseris, I think your thoughts are needed here the most, since it was your perspective that swayed us to move to a pathfinder-in-the-space solution. Could you elaborate (or perhaps update us) on this design direction? Where are the pitfalls that you see?

AayushSabharwal commented 3 years ago

I tried writing a barebones implementation, and it quickly turned complicated. For this to work, ABM needs to know about GridSpace (to get the size and periodicity), and possibly Pathfinder too. Both of those are included after model.jl, which makes this difficult.

An alternative I thought is exposing AStarand allow the user to maintain all the profiles they want, and which agent uses which profile. Then all we need to do is refactor the API to optionally take the profile as a parameter of the relevant functions. The user calls the same functions they would normally, but pass an AStar struct too. The old API still remains, and dispatches to the new one. For example, move_along_route!(agent, model, profile) becomes a valid method, and move_along_route!(agent, model) = move_along_route!(agent, model, model.space.pathfinder) This has the advantage of not requiring as much reworking, and doesn't break serialization. However, if the user maintains their own profiles, they would probably also want to add methods for to_serializable and from_serializable for their properties

Datseris commented 3 years ago

I've put it in my to-dos to reply here, will do as soon as possible, some other responsibilities have caught up.

AayushSabharwal commented 3 years ago

I made a working example of the second method in the pathfinding_rework branch

Libbum commented 3 years ago

The 'need to know' question is something that a lot of packages get tangled in as they get larger.

https://github.com/SciML/SciMLBase.jl/blob/master/src/SciMLBase.jl

Is a decent place to look in terms of how we could think about designing here. We essentially define a bunch of abstract types that are empty, and we populate later on.

AayushSabharwal commented 3 years ago

The type isn't much of an issue, since that can just be a type parameter. Once the user passes in a GridPathfinder (or a vector of them) the ABM constructor needs to call the appropriate Pathfinder constructor, which it can't see/doesn't know about.

What if the user creates the Pathfinder, by passing in the space and profiles? The ABM then just takes that as a keyword argument

AayushSabharwal commented 3 years ago

I also propose renaming grid_pathfinder.jl to astar.jl, and have it only contain the core A-Star functionality. All the front-end user API (move_along_route!, set_target!, walkmap, etc.) can be in another file, so there's a clear separation between the two. This could be especially useful now that pathfinding won't just be for grid space.

AayushSabharwal commented 3 years ago

I managed to get the new API working, it's in pathfinding_newapi. Pathfinder structs are created by passing in the space, and Profile struct(s). This removes the necessity for GridPathfinder and ContinuousPathfinder structs.

Datseris commented 3 years ago

I will try to have a look tonight. I am extremely short of time due to DynamicalSystems.jl. Just an important point: a breaking release due to a specific, and minor, functionality of the package is in my eyes not something we should go for. It will result in a loss of trust (a package that has breaking releases all the time is not trustworthy and our 4.0 release wasn't so far in the past).

Any way this is resolved, it must be backwards compatible.

Datseris commented 3 years ago

@AayushSabharwal can you please write somewhere a description of your pathfinding_newapi branch? Would help me review. It would take me too much time to go through the entire source of the branch.

AayushSabharwal commented 3 years ago

Sure. I'll edit this comment with the summary

Summary:

grid_pathfinder.jl only contains the core pathfinding functionality. The API is in all_pahfinders.jl
What was previously Pathfinder is now Profile. Pathfinder now manages all pathfinding. It takes a GridSpace and a single Profile in a constructor, and in this case basically acts as a wrapper over AStar. If multiple Profile are passed in (currently just a vector, I shouldn't have made this type-specific though), agent_profiles::Dict{Int,Int} is a mapping from agent ID to the pathfinding profile it uses. All the profiles are AStar structs constructed from the Profiles stored in Pathfinder.profiles as a Vector.
GridSpace doesn't contain any pathfinding data now. That has moved to ABM. ABM.pathfinder is either nothing, or a Pathfinder passed in by the user.
All the API functions work as-is for a single-profile scenario (Pathfinder{Nothing}). If there are multiple profiles, set_target! requires a profile::Int to be passed in, the index of the profile to be used from Pathfinder.profiles. It sets the agent's mapping in Pathfinder to use that passed-in profile. move_along_route! then uses this mapping so agents can be moved along the path stored in whichever profile is applicable to them.

Before:

model = ABM(Foo, GridSpace((100, 100); pathfinder = Pathfinder(...)))
set_target!(model[1], (42, 42), model)
move_along_route!(model[1], model)

Can't use multiple pathfinding profiles

After:

space = GridSpace((100, 100))
model = ABM(Foo, space; pathfinder = Pathfinder(space, one_or_many_Profiles))
set_target!(model[1], (42, 42), model, profile_index)  # for multiple profiles
set_target!(model[1], (42, 42), model)  # for a single profile
move_along_route!(model[1], model) # either single or multiple. I haven't actually implemented this in the source for multiple profiles

Supports multiple profiles

AayushSabharwal commented 3 years ago

I have an idea for supporting multiple profiles without breaking changes. I'm working on fleshing it out to test feasibility

Introduce a type: AbstractPathfinder, define AStar <: AbstractPathfinder
Add a type such as MultipleAStar <: AbstractPathfinder (name needs work) which stores multiple profiles and acts as a drop-in replacement for AStar.
Let Pathfinder be a functor. Inside GridSpace, this just needs to be called and the grid dims and perioidicity passed in. It returns an AStar, which populates GridSpace.pathfinder. Let the pathfinder = nothing keyword argument be pathfinder = nopathfinder where nopathfinder(dims, periodic) = nothing. This allows creating the GridSpace without any reference to the Pathfinding submodule whatsoever.
Add a new MultiplePathfinder functor, which accepts multiple Pathfinders in its constructor and is also a functor. On being called the same way Pathfinder is, it returns a MultipleAStar which populates GridSpace.pathfinder
Add methods for MultipleAStar to the API, which are the same as the existing ones but also take an Int for the profile to use

Thus the API is maintained, and multiple profiles can be supported. ContinuousSpace can be practically identical in structure and API, with its own set of methods.

Datseris commented 3 years ago

Why do the pathfinder stuff need to be part of the model or space? Why can't they be their own business? I am just not happy with the approach we took puting something in gridspace. and we now put it in the model instead, which is even worse in my eyes.

Why can't we just have

set_target!(model[1], (42, 42), model, pathfinder)  # for a single profile or multiple, doesn't matter
move_along_route!(model[1], model, pathfinder) # either single or multiple. I haven't actually implemented this in the source for multiple profiles

?

obviously when you initialize pathfinder you would give it gridspace, or probably even better, the model directly.

AayushSabharwal commented 3 years ago

I think that's a good idea. It would also require a minor serialization rework, but that's a non-issue.

AayushSabharwal commented 3 years ago

Wouldn't this also be a breaking change? How should that be handled? Maybe dispatch the old methods to the new ones, and add a warning that it will be deprecated in the next major release?

Datseris commented 3 years ago

this is also breaking yes

AayushSabharwal commented 3 years ago

probably even better, the model directly.

If creating the pathfinder required the model, adding the pathfinder as a model property would end up being complicated. It doesn't require any data that isn't in the space

Datseris commented 3 years ago

This is a really tough story now. Moving the fields to model is breaking. Making them their own is breaking. Damn it. Lessons to be learned for all three of us, I think we should have spent more time before merging :( I won't have time tonight to go super deep on this, but definitely will have some time over the weekend.

I still stand that this functionality shouldn't "pollute" any of the major structs like the space or the model.

Datseris commented 3 years ago

I've thought about this more. This is really hard, I propose to discuss this live on Monday. From the current approaches, it seems like Aayush's one from here https://github.com/JuliaDynamics/Agents.jl/issues/515#issuecomment-867591198 is the best, and it would play best with IO checkpointing.

My main fear is: we really, really need to be careful making auxilary functionalities part of the main model. This can only go downhill, never uphill. How many more such functionalities would need to be made part of the model down the line...?

We should try as hard as we can to avoid it. Let's consider my suggestion of making the pathfinding business either external, or an argument of model.properties.

AayushSabharwal commented 3 years ago

I propose to discuss this live on Monday

Definitely.

play best with IO checkpointing

Most of the solutions above would require only minor reworks to checkpointing. I don't think that needs to be much of a factor.

We should try as hard as we can to avoid it. Let's consider my suggestion of making the pathfinding business either external, or an argument of model.properties.

Sure. I can see now why attaching such things to model/space structs is not a good idea. I'm working on trying ways to support the old API with reworked functionality

Libbum commented 3 years ago

Let's consider my suggestion of making the pathfinding business either external, or an argument of model.properties

Agreed George.

I think we have always had the underlying assumption that anything Agents.jl provides in terms of data structures must reside in model. As we add more and more features, this will not scale. Having Pathfinding provided by agents, something a model can consume, something serialisable, used in the spaces, used in plotting - all of this can be done from some struct within a user-added struct to model.properties for sure...

In addition, I think we'd be in the clear in terms of hard breaking changes with deprecating the Pathfinding-in-GridSpace methods to point to handles that deal with the externalised system as well.

JuliaDynamics / Agents.jl

Pathfinding extensions #515