CWave: Theory and Practice of a Fast Single-source Any-angle Path Planning Algorithm

作     者：Sinyukov, Dmitry Padir, Taskin 

作者机构：Worcester Polytech Inst Robot Engn Program Worcester MA 01609 USA Northeastern Univ Dept Elect & Comp Engn Boston MA 02115 USA 

出 版 物：《ROBOTICA》 (机器人学)

年 卷 期：2020年第38卷第2期

页      面：207-234页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0811[工学-控制科学与工程] 

基　　金：National Science Foundation Division Of Computer and Network Systems Direct For Computer & Info Scie & Enginr Funding Source: National Science Foundation 

主　　题：Any-angle path planning Single-source path planning High-performance algorithm Path planning on a grid Parallelized algorithms 

摘      要：Path planning on a two-dimensional grid is a well-studied problem in robotics. It usually involves searching for a shortest path between two vertices on a grid given that some of the grid cells are impassable (occupied by obstacles). Single-source path planning finds shortest paths from a given source vertex to all other vertices of the grid. Singles-source path planning enhances robot autonomy by calculating multiple possible paths for various navigation scenarios when the destination state is unknown. A high-performance algorithm for single-source any-angle path planning on a grid called CWave is proposed here. Any-angle attribute implies that the algorithm calculates paths which can include line segments at any angle, as opposed to standard A* that runs on an 8-connected graph, which permits turns with 45 degrees increments only. The key idea of CWave is to abandon the graph model and operate directly on the grid geometry using discrete geometric primitives (instead of individual vertices) to represent the wave front. In its most basic form (CWaveInt), CWave requires only integer arithmetics. CWaveInt, however, can accumulate the distance error at turning points. A modified version of CWave (CWaveFpuSrc) with minimal usage of floating-point calculations is also developed to eliminate any accumulative errors, which is proven mathematically and experimentally on several maps. The performance of the algorithm on most of the tested maps is demonstrated to be significantly faster than that of Theta*, Lazy Theta*, Field A*, ANYA, Block A*, and A* adapted for single-source planning (on maps with lower number of isolated obstacles, CWaveFpuSrc is 2-3 times faster than its fastest tested alternative Block A*). An N-threaded implementation (CWaveN) of CWave is presented and tested to demonstrate an improved performance (multithreaded implementation is 1.5-3 times faster than single-threaded CWave). The paper discusses foundations and experimental validation of CWave, and p