curds01
commented
6 years ago Hi @alafi. Thanks for posting.
- You are correct that Menge currently has no dynamic replanning (based on density or any other issue). The interesting question is how to address that.
I've implemented this kind of system in the past (although, it predated Menge and I haven't adapted the idea to Menge yet -- http://gamma.cs.unc.edu/PLE/). It's a great idea and a logical feature to have. And the question is how to implement it in Menge.
There are two issues to address:
- What triggers the replanning?
- How does the planning account for congestion?
As an example, I'll touch on the PLEdestrian paper mentioned above providing a brief overview of how we did it. We changed the cost metric for path planning to include the expected cost of traversing "congested" links. We also had a per-agent view of those costs. Then we'd update the costs based on line of sight (i.e., the original plan assumes that there's no congestion, but as the agent changed what they could see they updated their mental model and would replan if things got expensive).
In Menge, this could be decomposed into two parts:
- A transition, such as you recommend, based on some congestion-based metric. The transition would lead to entering a state (possibly the same state) which would trigger a replan.
- A navigation structure (nav mesh or road map) that would take into account density. The first pass on this would be having global density knowledge; the second pass would be per-agent density knowledge.
Alternatively, like in the PLEdestrian paper, you could put the replanning trigger inside the nav mesh/road map. This might have the benefit of reducing redundant replanning and a more knowledgable trigger (for example, the difference between "It's congested now, I should replan" and "It's congested now, but it's been congested for a while and I don't believe there's a better solution, so it's not worth replanning until I have new information")
Here's a similar formulation of the idea: https://www.staff.science.uu.nl/~gerae101/pdf/crowd_density_cavw12.pdf
Why don't you look at the different approaches, see what style you'd like to tackle, and we'll figure out the best way to implement it in Menge.
alafi
I've been playing with Menge for a while now and noticed that for NavMeshes or RoadMaps there is no way to take in consideration the surrounding agents when calculating paths. Am I right?
What I was thinking of is to have some transition that will change agent state based on density of other agents standing on the way for the near sight or at least seeking a better path.
Or maybe consider Agents as low weight obstacles. This will make them look a little smart by trying to avoid crowded areas earlier. (I might be wrong but) Currently navmeshes and roadmaps are static and cannot be changed once loaded so there is no way to modify them on the fly to apply this feature.
Do you have any suggestions in this regard or does idea seem to you any good to be implemented.
Thank you.