JPS+: Over 100x Faster than A* (2015) [video]

Re:JPS+: Over 100x Faster than A* (2015) [video] by user5994461 on Monday February 20, 2017 @07:06PM (#13692130)

Use Floyd Warshall if you can pre-compute.

It pre-computes all the paths from all nodes to all nodes, and it's incredibly efficient.

Most awesome algorithm ever :D

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorit...

[ Parent | on HN ]

Re:JPS+: Over 100x Faster than A* (2015) [video] by user5994461 on Monday February 20, 2017 @07:11PM (#13692159)

And if you need dynamic graph with variable weighting and nodes, that's a case for D*

Mostly used for drone/rover/robot navigation in open environments, with the graphs evolving as the robot discover the environment.

https://en.wikipedia.org/wiki/D*

[ Parent | on HN ]

Re:JPS+: Over 100x Faster than A* (2015) [video] by Schwolop on Monday February 20, 2017 @10:45PM (#13693118)

Only if the area changing is near the start of the search, not near the goal. (i.e. near the sensors of a mobile robot, rather than near the destination far from the robot).

D* can be pathologically slower than repeated A* searches under such conditions.

[ Parent | on HN ]

Re:JPS+: Over 100x Faster than A* (2015) [video] by kunaltyagi on Tuesday February 21, 2017 @02:34AM (#13693984)

I've been using a modified D*. It increases the grid size as the path moves out of the robot's observable area. This allows a fast search even when the goal is in a environment with known dynamic obstacles.

Ideally speaking, you need to plan in higher dimensions to get an optimal path in dynamic environments

[ Parent | on HN ]