Rapid Vector-based Any-angle Path Planning with Non-convex Obstacles

Overview

• Novel vector-based algorithms for optimal any-angle path planning
• Motivated by bug algorithms, bypassing free space with line-of-sight checks
• Searching along obstacle contours if line-of-sight check collides
• Outperform conventional free-space planners like A* for distant points
• Thesis presents new search methods to speed up vector-based algorithms in non-convex obstacles

Plain English Explanation

Vector-based algorithms are a new type of path planning algorithm that are inspired by "bug" algorithms. These algorithms don't just search through empty space, but instead directly check if there is a clear line-of-sight between two points. If the line-of-sight check hits an obstacle, the algorithm will then search along the edge of the obstacle to find a way around it.

These vector-based algorithms tend to perform better than traditional path planning algorithms like A* when the start and end points are far apart. The thesis discusses some novel search methods to make these vector-based algorithms even faster, especially when dealing with obstacles that have complex, non-convex shapes.

One notable method is the "best hull," which allows the algorithm to estimate the path cost without fully verifying the line-of-sight. It does this by placing "phantom" points on the non-convex corners of obstacles, which act as stand-ins for future turning points in the path. Building on these methods, the algorithms R2 and R2+ are introduced, which outperform other vector-based algorithms when the optimal path is expected to have few turning points.

The thesis also describes a versatile multi-dimensional ray tracer for occupancy grids, and discusses the concept of a three-dimensional angular sector for future work.

Technical Explanation

The paper presents novel vector-based algorithms for optimal any-angle path planning. These algorithms are motivated by bug algorithms, which bypass free space by directly conducting line-of-sight checks between two queried points, and searching along obstacle contours if a check collides with an obstacle.

The vector-based algorithms outperform conventional free-space planners such as A* especially when the queried points are far apart. The thesis presents novel search methods to speed up vector-based algorithms in non-convex obstacles by delaying line-of-sight checks.

The best hull is a notable method that allows for monotonically increasing path cost estimates even without verifying line-of-sight, utilizing phantom points placed on non-convex corners to mimic future turning points. Building upon the methods, the algorithms R2 and R2+ are formulated, which outperform other vector-based algorithms when the optimal path solution is expected to have few turning points.

Other novel methods include a novel and versatile multi-dimensional ray tracer for occupancy grids, and a description of the three-dimensional angular sector for future works.

Critical Analysis

The paper presents promising vector-based algorithms for optimal any-angle path planning, demonstrating their advantages over conventional free-space planners. However, the authors acknowledge that the algorithms may not perform as well when the optimal path is expected to have many turning points.

Additionally, the paper focuses on 2D path planning, and the authors mention the need to extend the concepts to 3D for applications like drone navigation. The discussion of the three-dimensional angular sector suggests this may be an area of future research.

Overall, the novel search methods and algorithms introduced in the thesis offer valuable contributions to the field of optimal any-angle path planning, but further research may be needed to address the limitations and expand the capabilities of the techniques to more complex environments and applications.

Conclusion

This thesis introduces a set of novel vector-based algorithms for optimal any-angle path planning that outperform traditional free-space planners, especially for distant start and end points. The key innovations include techniques to speed up the algorithms in non-convex obstacles, such as the "best hull" method and the R2 and R2+ algorithms.

These advancements in vector-based path planning have implications for a variety of applications, from robotics and autonomous vehicles to drone navigation and beyond. By leveraging line-of-sight checks and obstacle contour searches, these algorithms can find more efficient paths in complex environments. Further research to extend the techniques to 3D and address other limitations could unlock even more potential for these novel planning methods.