Bug in continuous pathfinder? Erratic rather than straight routes

[mastrof]

Describe the bug While working on #879 I faced a behavior I don't really understand (https://github.com/JuliaDynamics/Agents.jl/issues/879#issuecomment-1718338297):

When moving along a route, the agent moves somewhat erratically rather than straight towards the target destination, unless the target has the same distance along all dimensions. My expectation would instead be that the agent always moves straight to the target destination (as long as it is allowed by the walkmap). Is my expectation wrong? Or is there a bug in the algorithm?

MWE (on main): n.b. it's independent of whether you set periodic=false or periodic=true

using Agents, Agents.Pathfinding
using CairoMakie

space = ContinuousSpace((5,5); periodic=false)
pf = AStar(space; walkmap = trues(50,50))
model = ABM(ContinuousAgent{2,Float64}, space; properties = (pf=pf,))
origin = SVector(1.0, 1.0)
a = add_agent!(origin, model, (0.0,0.0))
target = SVector(2.0, 3.0)
plan_best_route!(a, [target], model.pf)

d = euclidean_distance(origin, target, model)
n = 20
x = zeros(n+1); y = zeros(n+1)
x[1], y[1] = a.pos
for i in 1:n
    move_along_route!(a, model, model.pf, d/n)
    x[1+i], y[1+i] = a.pos
end

scatterlines(x, y; axis=(xlabel="x", ylabel="y"))

Same (maybe more shocking) happens also if target = SVector(1.0, 3.0), where it would be obvious to just move straight along the y direction:

But if target = SVector(3.0,3.0) then the agent moves perfectly straight:

[Tortar]

tagging @AayushSabharwal since I think he wrote the path-finding algorithms and so I hope he will find it easier to bisect the issue, always if he has the bandwidth to help

[AayushSabharwal]

Oh wow. I'll take a look soon, this is an interesting bug

[AayushSabharwal]

~This is an annoying issue. I haven't figured it out yet, but it seems to be in the core AStar algorithm and is not specific to continuous space.~ (EDIT: This doesn't seem to be an issue, read below). This is what I got with going from (10, 10) to (20, 30) in a (50, 50) grid space

EDIT: Actually wait. I think this path is technically correct in grid space, it just looks erratic because it's interspersing diagonal moves with straight up.

[AayushSabharwal]

If I plot the waypoints of the path (using the struct's internals) I get the following in continuous space:

Which is correct on the grid. The reason it turns back at the end is because the waypoints are on a grid and the destination isn't, but the interpolation deals with this as evidenced by the fact that it doesn't turn back in the first plot on this thread.

As for the second plot, it's also correct. The xaxis scaling is just skewed, it's barely moving along that axis

I think the interpolation for how agents move along discretized paths in continuous space might be worth improving, but this is working correctly.

I'm going to start checking plot axes before I even look at the middle part from now on lol

[mastrof]

Thanks for checking, I was also suspecting it was just a not-very-good interpolation of the underlying grid path (with which I don't have any problem).

As for the second plot, it's also correct. The xaxis scaling is just skewed, it's barely moving along that axis

I see what you mean but this is somewhat relative. I would be wary of saying that moving by 0.05 in a space of total extent 5, when you should really be moving 0, is "barely moving". It's true though that there is also a dependency on the walkmap coarseness.

[AayushSabharwal]

Yeah. Whenever an AStar pathfinder is created for ContinuousSpace, either the walkmap must be specified or the cost_metric must be a PenaltyMap, to indicate the size of the grid used for pathfinding. Thus, the granularity of the grid must be explicitly specified to however much is acceptable. We don't assume anything internally about what counts as "barely moving"

If you have any suggestions as to how we can improve the interpolation or documentation around this to make it more obvious why these sort of paths occur, please feel free to open a PR.

[mastrof]

If you can point me to the core of where the interpolation happens I can try to take a look at some point

[Tortar]

I think since it is not a bug we can close this one

[Tortar]

And maybe open a new issue for the interpolation and documentation update?