2
\$\begingroup\$

I've implemented Path Planning a few times, using A* on nav meshes, and also Continuum Crowds but now I am trying to plan paths in very chaotic environments.

In this environment, new routes and new blockages are created constantly, and chaotically. This is because the environment is fully destructible, and the debris can create new obstacles.

In such an environment, nothing can be pre-computed. What would be a good way to sense the traversability in such a world? There is no concept of a grid in my world, b.t.w, but I wonder if I should introduce an artificial one for the purpose of planning.

But if navigation could be achieved without a grid, that would be much better of course.

Note that the navigation is not merely dynamic in the sense that certain transitions get opened/closed, but actually chaotic. This stops me from a simple approach of enabling/disabling certain edges on the navigation mesh. That approach would be usable if, e.g. a gate gets locked/unlocked. But in my case, in a blink of an eye, the routes could be drastically changed where simple mutations of a pre-computed mesh are not doable.

An ever changing environment

\$\endgroup\$
  • \$\begingroup\$ Must AI be able to recognize paths and move from a place to another at all costs? If not, you may rely onto other solutions to emulate the ability of moving around. \$\endgroup\$ – liggiorgio Apr 6 '18 at 17:20
  • \$\begingroup\$ It doesn't have to always find the best path, it's fine if it is a little in-efficient, as long as it doesn't ignore obvious routes, or get stuck on an obstacle easily. \$\endgroup\$ – Bram Apr 6 '18 at 17:24
  • \$\begingroup\$ Possible duplicate of Real Time Dynamic Pathfinding? Note: there's a lot of variability in terms of possible problem constraints - if your problem is different than the link, please edit & draw attention to the differences. \$\endgroup\$ – Pikalek Apr 6 '18 at 19:07
  • \$\begingroup\$ When an agent needs to move, you can use a quick algorithm that moves in the general direction of the objective and avoids obstacles, meanwhile another system takes its time to figure out a path. This is the approach that the game Prototype takes. Of course you want it to react to a dynamic enviroment, or even work without complete knowledge, please take a look at goal oriented AI for inspiration. See also: 1 (paid membership required), 2 (low volume). \$\endgroup\$ – Theraot Apr 7 '18 at 1:12
1
\$\begingroup\$

With a robotic system needing to plan its movements quickly in a dynamic environment I have seen Rapidly-exploring random trees (or an adaption of them) being used for these approximations.

\$\endgroup\$
  • \$\begingroup\$ Out of curiosity - can you add some references to your claim? As far as I remember the original paper (and successors) make no mention of it - sounds rather aimed at navigation in high dimensional spaces. \$\endgroup\$ – wondra Apr 19 '18 at 18:50
  • \$\begingroup\$ @wondra Have only heard a presentation by someone working on this project. Now that I come to think of it, it may well be they oversimplified the problem for their audience. \$\endgroup\$ – TauCraft Apr 20 '18 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.