{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T15:37:37Z","timestamp":1772206657138,"version":"3.50.1"},"reference-count":33,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T00:00:00Z","timestamp":1557878400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Robotica"],"published-print":{"date-parts":[[2020,2]]},"abstract":"<jats:title>Summary<\/jats:title><jats:p>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). <jats:italic>Single-source<\/jats:italic> 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. <jats:italic>Any-angle<\/jats:italic> 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\u00b0 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 (<jats:italic>CWaveInt<\/jats:italic>), CWave requires only integer arithmetics. <jats:italic>CWaveInt<\/jats:italic>, however, can accumulate the distance error at turning points. A modified version of CWave (<jats:italic>CWaveFpuSrc<\/jats:italic>) 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, <jats:italic>CWaveFpuSrc<\/jats:italic> is 2\u22123 times faster than its fastest tested alternative Block A*). An <jats:italic>N<\/jats:italic>-threaded implementation (<jats:italic>CWaveN<\/jats:italic>) of CWave is presented and tested to demonstrate an improved performance (multithreaded implementation is 1.5\u22123 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.<\/jats:p>","DOI":"10.1017\/s0263574719000560","type":"journal-article","created":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T04:46:14Z","timestamp":1557895574000},"page":"207-234","source":"Crossref","is-referenced-by-count":3,"title":["CWave: Theory and Practice of a Fast Single-source Any-angle Path Planning Algorithm"],"prefix":"10.1017","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6786-9486","authenticated-orcid":false,"given":"Dmitry A.","family":"Sinyukov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ta\u015fkin","family":"Padir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2019,5,15]]},"reference":[{"key":"S0263574719000560_ref28","first-page":"89","article-title":"Optimal any-angle pathfinding in practice","volume":"56","author":"Harabor","year":"2016","journal-title":"J. Artif. Int. Res."},{"key":"S0263574719000560_ref25","doi-asserted-by":"publisher","DOI":"10.1145\/359423.359432"},{"key":"S0263574719000560_ref4","unstructured":"4. A. Nash , \u201cAny-Angle Path Planning,\u201d Ph.D. Dissertation (University of Southern California, 2012). Available: http:\/\/gradworks.umi.com\/35\/42\/3542296.html"},{"key":"S0263574719000560_ref12","first-page":"1177","volume-title":"Proceedings of the 22nd National Conference on Artificial Intelligence","volume":"2","author":"Nash","year":"2007"},{"key":"S0263574719000560_ref23","doi-asserted-by":"publisher","DOI":"10.1145\/160985.161156"},{"key":"S0263574719000560_ref16","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2994"},{"key":"S0263574719000560_ref20","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.93.4.1591"},{"key":"S0263574719000560_ref13","volume-title":"Proceedings of the 5th IFAC\/EURON symposium on intelligent autonomous vehicles","volume":"USA","author":"Nash","year":"2010"},{"key":"S0263574719000560_ref26","doi-asserted-by":"publisher","DOI":"10.1147\/sj.41.0025"},{"key":"S0263574719000560_ref11","doi-asserted-by":"publisher","DOI":"10.1109\/OCEANS.1984.1152243"},{"key":"S0263574719000560_ref7","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509725"},{"key":"S0263574719000560_ref5","first-page":"675","volume-title":"Proceedings of the 5th IFAC\/EURON symposium on intelligent autonomous vehicles","volume":"37","author":"Kraetzschmar","year":"2004"},{"key":"S0263574719000560_ref27","first-page":"308","volume-title":"Proceedings of the Twenty-Third International Conference on International Conference on Automated Planning and Scheduling","author":"Harabor","year":"2013"},{"key":"S0263574719000560_ref9","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v34i4.2512"},{"key":"S0263574719000560_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/359156.359164"},{"key":"S0263574719000560_ref3","first-page":"3526","volume-title":"2011 IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"van Toll","year":"2011"},{"key":"S0263574719000560_ref33","volume-title":"2017 IEEE International Conference on Robotics and Automation (ICRA)","author":"Sinyukov","year":"2017"},{"key":"S0263574719000560_ref30","volume-title":"C++ concurrency in action: Practical multithreading","author":"Williams","year":"2012"},{"key":"S0263574719000560_ref24","volume-title":"Calculus of Variations","author":"Elsgolc","year":"2007"},{"key":"S0263574719000560_ref18","volume-title":"ICAPS","author":"Uras","year":"2013"},{"key":"S0263574719000560_ref31","first-page":"3","volume-title":"ICRA Workshop on Open Source Software","author":"Quigley","year":"2009"},{"key":"S0263574719000560_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/rob.20287"},{"key":"S0263574719000560_ref17","volume-title":"Eighth Annual Symposium on Combinatorial Search","author":"Uras","year":"2015"},{"key":"S0263574719000560_ref21","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1961.5219222"},{"key":"S0263574719000560_ref2","unstructured":"2. D. A. Sinyukov , \u201cSemi-autonomous robotic wheelchair controlled with low throughput human-machine interfaces,\u201d Ph.D. Dissertation. https:\/\/web.wpi.edu\/Pubs\/ETD\/Available\/etd-050117-140934\/unrestricted\/sinyukov-phd-dissertation.pdf"},{"key":"S0263574719000560_ref22","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"S0263574719000560_ref1","doi-asserted-by":"publisher","DOI":"10.1109\/SMC.2014.6974059"},{"key":"S0263574719000560_ref19","unstructured":"19. T. Uras , ICAPS 2015: Speeding-up any-angle path-planning on grids (2010). https:\/\/youtu.be\/DduMITmi5Ekhttps:\/\/youtu.be\/"},{"key":"S0263574719000560_ref6","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2006.889486"},{"key":"S0263574719000560_ref8","first-page":"272","volume-title":"Game Programming Gems","volume":"1","author":"Rabin","year":"2000"},{"key":"S0263574719000560_ref29","doi-asserted-by":"publisher","DOI":"10.1109\/TCIAIG.2012.2197681"},{"key":"S0263574719000560_ref14","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2004.838026"},{"key":"S0263574719000560_ref32","volume-title":"IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS 2018)","author":"Sinyukov","year":"2018"}],"container-title":["Robotica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0263574719000560","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,13]],"date-time":"2020-01-13T07:42:34Z","timestamp":1578901354000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0263574719000560\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,15]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["S0263574719000560"],"URL":"https:\/\/doi.org\/10.1017\/s0263574719000560","relation":{},"ISSN":["0263-5747","1469-8668"],"issn-type":[{"value":"0263-5747","type":"print"},{"value":"1469-8668","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,15]]}}}