{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T04:11:29Z","timestamp":1772770289300,"version":"3.50.1"},"reference-count":25,"publisher":"University of Zielona G\u00f3ra, Poland","issue":"2","license":[{"start":{"date-parts":[[2017,6,27]],"date-time":"2017-06-27T00:00:00Z","timestamp":1498521600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,6,27]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p> Searching for the shortest-path in an unknown or changeable environment is a common problem in robotics and video games, in which agents need to update maps and to perform re-planning in order to complete their missions. D* Lite is a popular incremental heuristic search algorithm (i.e., it utilizes knowledge from previous searches). Its efficiency lies in the fact that it re-expands only those parts of the search-space that are relevant to registered changes and the current state of the agent. In this paper, we propose a new D* Extra Lite algorithm that is close to a regular A*, with reinitialization of the affected search-space achieved by search-tree branch cutting. The provided worst-case complexity analysis strongly suggests that D* Extra Lite\u2019s method of reinitialization is faster than the focused approach to reinitialization used in D* Lite. In comprehensive tests on a large number of typical two-dimensional path-planning problems, D* Extra Lite was 1.08 to 1.94 times faster than the optimized version of D* Lite. Moreover, while demonstrating that it can be particularly suitable for difficult, dynamic problems, as the problem-complexity increased, D* Extra Lite\u2019s performance further surpassed that of D*Lite. The source code of the algorithm is available on the open-source basis.<\/jats:p>","DOI":"10.1515\/amcs-2017-0020","type":"journal-article","created":{"date-parts":[[2017,7,13]],"date-time":"2017-07-13T10:01:43Z","timestamp":1499940103000},"page":"273-290","source":"Crossref","is-referenced-by-count":18,"title":["D* Extra Lite: A Dynamic A* With Search\u2013Tree Cutting and Frontier\u2013Gap Repairing"],"prefix":"10.61822","volume":"27","author":[{"given":"Maciej","family":"Przybylski","sequence":"first","affiliation":[{"name":"Institute of Automatic Control and Robotics Warsaw University of Technology, ul. \u015bw. A. Boboli 8, 02-525 Warsaw , Poland"}]},{"given":"Barbara","family":"Putz","sequence":"additional","affiliation":[{"name":"Institute of Automatic Control and Robotics Warsaw University of Technology, ul. \u015bw. A. Boboli 8, 02-525 Warsaw , Poland"}]}],"member":"37438","published-online":{"date-parts":[[2017,7,8]]},"reference":[{"key":"2021040714155468359_j_amcs-2017-0020_ref_001_w2aab2b8c22b1b7b1ab1ab1Aa","doi-asserted-by":"crossref","unstructured":"Aine, S. and Likhachev, M. (2016). Truncated incremental search, Artificial Intelligence 234: 49-77.","DOI":"10.1016\/j.artint.2016.01.009"},{"key":"2021040714155468359_j_amcs-2017-0020_ref_002_w2aab2b8c22b1b7b1ab1ab2Aa","doi-asserted-by":"crossref","unstructured":"Belter, D., \u0141abecki, P., Fankhauser, P. and Siegwart, R. (2016). RGB-D terrain perception and dense mapping for legged robots, International Journal of Applied Mathematics and Computer Science 26(1): 81-97, DOI: 10.1515\/amcs-2016-0006.","DOI":"10.1515\/amcs-2016-0006"},{"key":"2021040714155468359_j_amcs-2017-0020_ref_003_w2aab2b8c22b1b7b1ab1ab3Aa","doi-asserted-by":"crossref","unstructured":"Hart, P.E., Nilsson, N.J. and Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems Science and Cybernetics 4(2): 100-107.","DOI":"10.1109\/TSSC.1968.300136"},{"key":"2021040714155468359_j_amcs-2017-0020_ref_004_w2aab2b8c22b1b7b1ab1ab4Aa","unstructured":"Hern\u00e1ndez, C., As\u00edn, R. and Baier, J.A. (2015). Reusing previously found A* paths for fast goal-directed navigation in dynamic terrain, 19th AAAI Conference on Artificial Intelligence, Austin, TX, USA, pp. 1158-1164."},{"key":"2021040714155468359_j_amcs-2017-0020_ref_005_w2aab2b8c22b1b7b1ab1ab5Aa","unstructured":"Hern\u00e1ndez, C., Baier, J.A. and As\u00edn, R. (2014). Making A* run faster than D*-Lite for path-planning in partially known terrain, Proceedings of the 24th International Conference on Automated Planning and Scheduling, Portsmouth, NH, USA, pp. 504-508."},{"key":"2021040714155468359_j_amcs-2017-0020_ref_006_w2aab2b8c22b1b7b1ab1ab6Aa","unstructured":"Hern\u00e1ndez, C., Meseguer, P., Sun, X. and Koenig, S. (2009). Path-Adaptive A* for incremental heuristic search in unknown terrain, Proceedings of the 19th International Conference on Automated Planning and Scheduling, Thessaloniki, Greece, pp. 358-361."},{"key":"2021040714155468359_j_amcs-2017-0020_ref_007_w2aab2b8c22b1b7b1ab1ab7Aa","unstructured":"Hern\u00e1ndez, C., Sun, X., Koenig, S. and Meseguer, P. (2011). Tree Adaptive A*, 10th International Conference on Autonomous Agents and Multiagent Systems, Taipei, Taiwan, Vol. 1, pp. 123-130."},{"key":"2021040714155468359_j_amcs-2017-0020_ref_008_w2aab2b8c22b1b7b1ab1ab8Aa","unstructured":"Koenig, S. and Likhachev, M. (2001). Improved fast replanning for robot navigation in unknown terrain, Technical Report GIT-COGSCI-2002\/3, Georgia Institute of Technology, Atlanta, GA."},{"key":"2021040714155468359_j_amcs-2017-0020_ref_009_w2aab2b8c22b1b7b1ab1ab9Aa","doi-asserted-by":"crossref","unstructured":"Koenig, S. and Likhachev, M. (2005a). Adaptive A*, Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems, Utrecht, The Netherlands, pp. 1311-1312.","DOI":"10.1145\/1082473.1082748"},{"key":"2021040714155468359_j_amcs-2017-0020_ref_010_w2aab2b8c22b1b7b1ab1ac10Aa","doi-asserted-by":"crossref","unstructured":"Koenig, S. and Likhachev, M. (2005b). Fast replanning for navigation in unknown terrain, IEEE Transactions on Robotics 21(3): 354-363.","DOI":"10.1109\/TRO.2004.838026"},{"key":"2021040714155468359_j_amcs-2017-0020_ref_011_w2aab2b8c22b1b7b1ab1ac11Aa","doi-asserted-by":"crossref","unstructured":"Koenig, S., Likhachev, M. and Furcy, D. (2004). Lifelong planning A*, Artificial Intelligence 155(1): 93-146.","DOI":"10.1016\/j.artint.2003.12.001"},{"key":"2021040714155468359_j_amcs-2017-0020_ref_012_w2aab2b8c22b1b7b1ab1ac12Aa","doi-asserted-by":"crossref","unstructured":"Koenig, S. and Sun, X. (2009). Comparing real-time and incremental heuristic search for real-time situated agents, Autonomous Agents and Multi-Agent Systems 18(3): 313-341.","DOI":"10.1007\/s10458-008-9061-x"},{"key":"2021040714155468359_j_amcs-2017-0020_ref_013_w2aab2b8c22b1b7b1ab1ac13Aa","unstructured":"Likhachev, M., Ferguson, D.I., Gordon, G.J., Stentz, A. and Thrun, S. (2005). Anytime Dynamic A*: An anytime, replanning algorithm, Proceedings of the 15th International Conference on Automated Planning and Scheduling, Monterey, CA, USA, pp. 262-271."},{"key":"2021040714155468359_j_amcs-2017-0020_ref_014_w2aab2b8c22b1b7b1ab1ac14Aa","unstructured":"Pods\u0119dkowski, L. (1998). Path planner for nonholonomic mobile robot with fast replanning procedure, 1998 IEEE International Conference on Robotics and Automation, Lueven, Belgium, Vol. 4, pp. 3588-3593."},{"key":"2021040714155468359_j_amcs-2017-0020_ref_015_w2aab2b8c22b1b7b1ab1ac15Aa","doi-asserted-by":"crossref","unstructured":"Pods\u0119dkowski, L., Nowakowski, J., Idzikowski, M. and Vizvary, I. (2001). A new solution for path planning in partilly known or unknown environment for nonholonomic mobile robots, Robotics and Autonomous Systems 34(2): 145-152.","DOI":"10.1016\/S0921-8890(00)00118-4"},{"key":"2021040714155468359_j_amcs-2017-0020_ref_016_w2aab2b8c22b1b7b1ab1ac16Aa","doi-asserted-by":"crossref","unstructured":"Przybylski, M., Koguciuk, D., Siemia\u02dbtkowska, B., Harasymowicz-Boggio, B. and Chechli\u00b4nski, \u0141. (2015).Integration of qualitative and quantitative spatial data within a semantic map for service robots, in R. Szewczyk et al. (Eds.), Progress in Automation, Robotics and Measuring Techniques. Volume 2: Robotics, Springer, Cham, pp. 223-232.","DOI":"10.1007\/978-3-319-15847-1_22"},{"key":"2021040714155468359_j_amcs-2017-0020_ref_017_w2aab2b8c22b1b7b1ab1ac17Aa","doi-asserted-by":"crossref","unstructured":"Przybylski, M. and Siemia\u02dbtkowska, B. (2012). A new CNN-based method of path planning in dynamic environment, in L. Rutkowski et al. (Eds.), Artificial Intelligence and Soft Computing, ICAISC 2012, Lecture Notes in Computer Science, Vol. 7268, Springer, Berlin\/Heidelberg, pp. 484-492.","DOI":"10.1007\/978-3-642-29350-4_58"},{"key":"2021040714155468359_j_amcs-2017-0020_ref_018_w2aab2b8c22b1b7b1ab1ac18Aa","unstructured":"Stentz, A. (1994). Optimal and efficient path planning for partially-known environments, Proceedings of the 1994 IEEE International Conference on Robotics and Automation, San Diego, CA, USA, Vol. 4, pp. 3310-3317."},{"key":"2021040714155468359_j_amcs-2017-0020_ref_019_w2aab2b8c22b1b7b1ab1ac19Aa","unstructured":"Stentz, A. (1995). The Focussed D* algorithm for real-time replanning, Proceedings of the 14th International Joint Conference on Artificial Intelligence, Montreal, Quebec, Canada, Vol. 2, pp. 1652-1659."},{"key":"2021040714155468359_j_amcs-2017-0020_ref_020_w2aab2b8c22b1b7b1ab1ac20Aa","doi-asserted-by":"crossref","unstructured":"Sturtevant, N.R. (2012). Benchmarks for grid-based pathfinding, IEEE Transactions on Computational Intelligence and AI in Games 4(2): 144-148.","DOI":"10.1109\/TCIAIG.2012.2197681"},{"key":"2021040714155468359_j_amcs-2017-0020_ref_021_w2aab2b8c22b1b7b1ab1ac21Aa","unstructured":"Sun, X. and Koenig, S. (2007). The Fringe-Saving A* search algorithm-a feasibility study, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, pp. 2391-2397."},{"key":"2021040714155468359_j_amcs-2017-0020_ref_022_w2aab2b8c22b1b7b1ab1ac22Aa","unstructured":"Sun, X., Koenig, S. and Yeoh, W. (2008). Generalized Adaptive A*, Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, Estoril, Portugal, Vol. 1, pp. 469-476."},{"key":"2021040714155468359_j_amcs-2017-0020_ref_023_w2aab2b8c22b1b7b1ab1ac23Aa","doi-asserted-by":"crossref","unstructured":"Trovato, K.I. (1990). Differential A*: An adaptive search method illustrated with robot path planning for moving obstacles and goals, and an uncertain environment, International Journal of Pattern Recognition and Artificial Intelligence 4(2): 245-268.","DOI":"10.1142\/S0218001490000174"},{"key":"2021040714155468359_j_amcs-2017-0020_ref_024_w2aab2b8c22b1b7b1ab1ac24Aa","doi-asserted-by":"crossref","unstructured":"Trovato, K.I. and Dorst, L. (2002). Differential A*, IEEE Transactions on Knowledge and Data Engineering 14(6): 1218-1229.","DOI":"10.1109\/TKDE.2002.1047763"},{"key":"2021040714155468359_j_amcs-2017-0020_ref_025_w2aab2b8c22b1b7b1ab1ac25Aa","unstructured":"van Toll, W. and Geraerts, R. (2015). Dynamically Pruned A* for re-planning in navigation meshes, IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Hamburg, Germany, pp. 2051-2057."}],"container-title":["International Journal of Applied Mathematics and Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/content.sciendo.com\/view\/journals\/amcs\/27\/2\/article-p273.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.sciendo.com\/article\/10.1515\/amcs-2017-0020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,15]],"date-time":"2024-05-15T22:56:27Z","timestamp":1715813787000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.sciendo.com\/article\/10.1515\/amcs-2017-0020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,27]]},"references-count":25,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2017,7,8]]},"published-print":{"date-parts":[[2017,6,27]]}},"alternative-id":["10.1515\/amcs-2017-0020"],"URL":"https:\/\/doi.org\/10.1515\/amcs-2017-0020","relation":{},"ISSN":["2083-8492"],"issn-type":[{"value":"2083-8492","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,27]]}}}