Navigation broken for geometry with many skinny triangles in the navigation mesh

[Ozaq]

Our current navigation is broken for geometries with many skinny triangles.

This is a severe issue with no workaround and we will not be able to provide a quick fix. @JetteSchumann / @chraibi / @schroedtert we need to discuss what to do here.

Thanks @ytipocmk631 for finding this issue!

This was found on 1.2.x

Discussed in https://github.com/PedestrianDynamics/jupedsim/discussions/1404

^{Originally posted by **ytipocmk631** April 30, 2024} I set up some queuing areas and connected to the waypoint behind the queue, but when the agent arrived at the waypoint, it did not move as expected (the agents route plan did not seem to be updated) https://github.com/PedestrianDynamics/jupedsim/assets/129007821/f0291b80-b4bc-49bb-be6c-ba3eedc095d3

example.zip geo.wkt.zip

[Ozaq]

So far I was able to find the following issues:

• Calculating g/h values used the wrong edge for minimum distance calculation
• Algorithm terminated on first found path and did not continue to evaluate alternative paths

Still this does not fix all path calculations.

[behrisch]

Hi @Ozaq Can you elaborate a little which problems persist? Are they visible in the given example? Is there a general problem with the algorithm? Is the source for the algorithm the same as in #1373. so that we can maybe check the implementation together?

[Ozaq]

@behrisch See discussion #1404 for a description of the problem. The algorithm is still TA*. Feel free to have a look at https://github.com/PedestrianDynamics/jupedsim/blob/57461564199d7c6648605df7173a27b8a6fe0530/libsimulator/src/RoutingEngine.cpp#L276-L420 on branch 1411-navigation-broken-for-geometry-with-many-skinny-triangles-in-the-navigation-mesh

Right now the branch contains modifications to display all expanded (i.e. straightened paths) that have been considered by TA*.

examples/geometry contains the geometry shown above.

If you have a suggestion where the implementation is not following the Algorithm described in #1373 I would be very glad to know.

[behrisch]

I am not entirely sure but I suspect it might be necessary to add a search state not only for every face but for every combination of face and "entry edge". The reason to suspect that is that a) the thesis never talks about updating old states it only adds new ones and b) updating a g-value where the h-value actually refers to a different entry edge looks suspicious. To test that out, one could start with really only adding new states and never update old ones.

[behrisch]

@Ozaq Good news! I just tested it and yes if I remove the whole update part in https://github.com/PedestrianDynamics/jupedsim/blob/57461564199d7c6648605df7173a27b8a6fe0530/libsimulator/src/RoutingEngine.cpp#L392-L401, I get the right path. Shall I do a pull request here or against the rls branch (or not at all)?

[Ozaq]

@behrisch can you please make a PR with your changes with 1411-navigation-broken-for-geometry-with-many-skinny-triangles-in-the-navigation-mesh I think I have some time on Friday to do some testing and get the changes in if all works out.

[behrisch]

@Ozaq see #1422

[Ozaq]

Hmm ok, still cannot merge this. I have been doing some testing with an arena example from @JetteSchumann and there are way to many paths created and expanded

In the screenshot below you see the start and goal marked with the pink circle and blue denoting alternative routes, green optimal route. In total 2122 paths are computed

At the moment It is unclear to me if this is a general problem in the algorithm or if there is an issue somewhere else. Some of the alternate paths though look odd on first glance at I might very well be that there are more paths computed than it should but still the number of computed paths is computationally prohibitive.

[behrisch]

Can you share this scenario or is it already in the examples? And how do you do the drawing? I added two little optimizations to the branch but I am not sure it will improve things a lot. The paths do not look very implausible to me. What is the effect on runtime or how many paths would you deem acceptable?

[behrisch]

Looking at the Demyen thesis the example above might be an instance of the problematic cases mentioned in chapter 8.2. I think there are basically three options (which can be combined of course):

1. Implementing the full TRA* (it simplifies the search tree so it may reduce the number of paths but probably will not help with many small obstacles)
2. Simplifying the geometry (at least reducing the complexity (number of surrounding triangles) of small obstacles by using their bounding box)
3. Sacrificing optimality (discarding new candidates if they are not at least 5% better than the current best path or abort after a fixed number of extended paths). This can go together with the optimization mentioned in chapter 8.2 to find a first solution fast by using a secondary queue for faces which have been expanded before.