Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-17T17:23:17.193Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  15 May 2019

Dmitry A. Sinyukov Open the ORCID record for Dmitry A. Sinyukov [Opens in a new window]  and
Taşkin Padir
Dmitry A. Sinyukov*
Affiliation:
Robotics Engineering Program, Worcester Polytechnic Institute, Worcester, MA 01609, USA
Taşkin Padir
Affiliation:
Electrical and Computer Engineering Department, Northeastern University, Boston, MA 02115, USA E-mail: [email protected]
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

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° 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 presents future work to address the limitations of the current implementations and obtain further performance enhancements.

Keywords

Any-angle path planningSingle-source path planningHigh-performance algorithmPath planning on a gridParallelized algorithms
Type
Articles
Information
Robotica , Volume 38 , Issue 2 , February 2020 , pp. 207 - 234
Copyright
© Cambridge University Press 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Sinyukov, D. A., Li, R., Otero, N. W., Gao, R. and Padir, T., “Augmenting a voice and facial expression control of a robotic wheelchair with assistive navigation,” 2014 IEEE International Conference on Systems, Man and Cybernetics (SMC), San Diego, CA, USA (2014) pp. 1088–1094.CrossRefGoogle Scholar
Sinyukov, D. A., “Semi-autonomous robotic wheelchair controlled with low throughput human-machine interfaces,” Ph.D. Dissertation. https://web.wpi.edu/Pubs/ETD/Available/etd-050117-140934/unrestricted/sinyukov-phd-dissertation.pdf Google Scholar
van Toll, W., Cook, A. F. and Geraerts, R., “Navigation meshes for realistic multi-layered environments,” 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems (2011) pp. 3526–3532.Google Scholar
Nash, A., “Any-Angle Path Planning,” Ph.D. Dissertation (University of Southern California, 2012). Available: http://gradworks.umi.com/35/42/3542296.html Google Scholar
Kraetzschmar, G. K., Gassull, G. P., Uhl, K., Pags, G. and Uhl, G. K., “Probabilistic quadtrees for variable-resolution mapping of large environments,” In: Proceedings of the 5th IFAC/EURON symposium on intelligent autonomous vehicles, vol. 37 (2004) pp. 675–680.Google Scholar
Grisetti, G., Stachniss, C. and Burgard, W., “Improved techniques for grid mapping with Rao-Blackwellized particle filters,” IEEE Trans. Rob. 23(1), 34–46 (2007).CrossRefGoogle Scholar
Marder-Eppstein, E., Berger, E., Foote, T., Gerkey, B. P. and Konolige, K., “The office marathon: Robust navigation in an indoor office environment,” 2010 IEEE International Conference on Robotics and Automation, Anchorage, Alaska, USA (2010) pp. 300–307.CrossRefGoogle Scholar
Rabin, S., “A* speed optimizations,” In: Game Programming Gems, vol. 1 (Charles River Media, Boston, MA, USA, 2000) pp. 272–287.Google Scholar
Nash, A. and Koenig, S., “Any-angle path planning,” AI Mag. 34(4), 85–107 (2013).CrossRefGoogle Scholar
Carsten, J., Rankin, A., Ferguson, D. and Stentz, A., “Global planning on the mars exploration rovers: Software integration and surface testing,” J. Field Rob. 26(4), 337–357 (2009).CrossRefGoogle Scholar
Thorpe, C. and Matthies, L., “Path relaxation: Path planning for a mobile robot” OCEANS (1984) pp. 576–581.CrossRefGoogle Scholar
Nash, A., Daniel, K., Koenig, S. and Felner, A., “Theta*: Any-angle path planning on grids,” In:Proceedings of the 22nd National Conference on Artificial Intelligence, vol. 2 (AAAI Press, Vancouver, Canada, 2007) pp. 1177–1183.Google Scholar
Nash, A., Koenig, S. and Tovey, C., “Lazy Theta*: Any-angle path planning and path length analysis in 3D,” In:Proceedings of the 5th IFAC/EURON symposium on intelligent autonomous vehicles, Atlanta, GA, USA (2010).Google Scholar
Koenig, S. and Likhachev, M., “Fast replanning for navigation in unknown terrain,” IEEE Trans. Rob. 21(3), 354–363 (2005).CrossRefGoogle Scholar
Lozano-Pérez, T. and Wesley, M. A., “An algorithm for planning collision-free paths among polyhedral obstacles,” Commun. ACM 22(10), 560–570 (1979).CrossRefGoogle Scholar
Daniel, K., Nash, A., Koenig, S. and Felner, A., “Theta*: Any-angle path planning on grids,” J. Artif. Intell. Res. 39, 533–579 (2010).CrossRefGoogle Scholar
Uras, T. and Koenig, S., “An empirical comparison of any-angle path-planning algorithms,” Eighth Annual Symposium on Combinatorial Search, IL, USA (2015).Google Scholar
Uras, T., Koenig, S. and Hernández, C., “Subgoal graphs for optimal pathfinding in eight-neighbor grids,” ICAPS, Rome, Italy (2013).Google Scholar
Uras, T., ICAPS 2015: Speeding-up any-angle path-planning on grids (2010). https://youtu.be/DduMITmi5Ekhttps://youtu.be/ Google Scholar
Sethian, J. A., “A fast marching level set method for monotonically advancing fronts,” Proc. Natl. Acad. Sci.93(4), 1591–1595 (1996). pMID: 11607632.CrossRefGoogle ScholarPubMed
Lee, C., “An algorithm for path connections and its applications,” IRE Trans. Electron. Comput.EC-10(3), 346–365 (1961).CrossRefGoogle Scholar
Mitchell, J. S., Mount, D. M., and Papadimitriou, C. H., “The discrete geodesic problem,” SIAM Journal on Computing 16(4), 647–668 (1987).CrossRefGoogle Scholar
Mitchell, J. S. B., “Shortest paths among obstacles in the plane,” In:Proceedings of the Ninth Annual Symposium on Computational Geometry, Ser. SCG’93 (ACM, 1993) pp. 308–317. http://doi.acm.org/10.1145/160985.161156.CrossRefGoogle Scholar
Elsgolc, L. D., Calculus of Variations (Dover Publications, Mineola, NY, USA, 2007).Google Scholar
Bresenham, J., “A linear algorithm for incremental digital display of circular arcs,” Commun. ACM 20(2), 100–106 (1977).CrossRefGoogle Scholar
Bresenham, J. E., “Algorithm for computer control of a digital plotter,” IBM Syst. J. 4(1), 25–30 (1965).CrossRefGoogle Scholar
Harabor, D. and Grastien, A., “An optimal any-angle pathfinding algorithm,” In:Proceedings of the Twenty-Third International Conference on International Conference on Automated Planning and Scheduling, Ser. ICAPS’13, Rome, Italy (AAAI Press, 2013) pp. 308–311. http://dl.acm.org/citation.cfm?id=3038718.3038758.Google Scholar
Harabor, D., Grastien, A., Öz, D. and Aksakalli, V., “Optimal any-angle pathfinding in practice,” J. Artif. Int. Res. 56(1), 89–118 (2016).Google Scholar
Sturtevant, N., “Benchmarks for grid-based pathfinding,” IEEE Trans. Comput. Intell. AI Games 4(2), 144–148 (2012). http://web.cs.du.edu/sturtevant/papers/benchmarks.pdf.CrossRefGoogle Scholar
Williams, A., C++ concurrency in action: Practical multithreading. (Manning, NY, USA, 2012) oCLC: ocn320189325.Google Scholar
Quigley, M., Gerkey, B., Conley, K., Faust, J., Foote, T., Leibs, J., Berger, E., Wheeler, R. and Ng, A., “ROS: An open-source robot operating system,” ICRA Workshop on Open Source Software, vol. 3 (2009).Google Scholar
Sinyukov, D. and Padir, T., “A novel shared position control method for robot navigation via low throughput human-machine interfaces,” IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2018), Madrid, Spain (2018).Google Scholar
Sinyukov, D. A. and Padir, T., “CWave: High-performance single-source any-angle path planning on a grid,” 2017 IEEE International Conference on Robotics and Automation (ICRA), Singapore (2017).Google Scholar