{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T15:55:40Z","timestamp":1778255740793,"version":"3.51.4"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2015,7,23]],"date-time":"2015-07-23T00:00:00Z","timestamp":1437609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soft Comput"],"published-print":{"date-parts":[[2016,10]]},"DOI":"10.1007\/s00500-015-1750-1","type":"journal-article","created":{"date-parts":[[2015,7,22]],"date-time":"2015-07-22T07:50:39Z","timestamp":1437551439000},"page":"4149-4171","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":128,"title":["Relaxed Dijkstra and A* with linear complexity for robot path planning problems in large-scale grid environments"],"prefix":"10.1007","volume":"20","author":[{"given":"Adel","family":"Ammar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hachemi","family":"Bennaceur","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Imen","family":"Ch\u00e2ari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anis","family":"Koub\u00e2a","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maram","family":"Alajlan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,23]]},"reference":[{"key":"1750_CR1","doi-asserted-by":"crossref","unstructured":"Alajlan M, Koubaa A, Chaari I, Bennaceur H, Ammar A (2013) Global path planning for mobile robots in large-scale grid environments using genetic algorithms. In: 2013 international conference on individual and collective behaviors in robotics ICBR\u20192013, Sousse","DOI":"10.1109\/ICBR.2013.6729271"},{"key":"1750_CR2","unstructured":"Andreas K, Kaindl H (1992) A new approach to dynamic weighting. In: Proceedings of the 10th European conference on artificial intelligence (ECAI-92), Vienna, pp 16\u201317"},{"key":"1750_CR3","unstructured":"Antsfeld L, Harabor DD, Kilby P, Walsh T (2012) Transit routing on video game maps. In: AIIDE"},{"key":"1750_CR4","doi-asserted-by":"crossref","unstructured":"Cazenave T (2006) Optimizations of data structures, heuristics and algorithms for path-finding on maps. In: CIG, pp 27\u201333","DOI":"10.1109\/CIG.2006.311677"},{"key":"1750_CR5","doi-asserted-by":"crossref","unstructured":"Chaari I, Koubaa A, Bennaceur H, Trigui S, Al-Shalfan K (2012) Smartpath: a hybrid ACO-GA algorithm for robot path planning. In: 2012 IEEE congress on evolutionary computation (CEC), Brisbane, pp 1\u20138","DOI":"10.1109\/CEC.2012.6256142"},{"key":"1750_CR6","first-page":"1898","volume":"2","author":"N Choubey","year":"2013","unstructured":"Choubey N, Gupta MBK (2013) Analysis of working of Dijkstra and A* to obtain optimal path. Int J Comput Sci Manag Res 2:1898\u20131904","journal-title":"Int J Comput Sci Manag Res"},{"issue":"1","key":"1750_CR7","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1(1):269\u2013271","journal-title":"Numer Math"},{"issue":"1","key":"1750_CR8","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1109\/100.580977","volume":"4","author":"D Fox","year":"1997","unstructured":"Fox D, Burgard W, Thrun S (1997) The dynamic window approach to collision avoidance. IEEE Robotics Autom Mag 4(1):23\u201333","journal-title":"IEEE Robotics Autom Mag"},{"key":"1750_CR9","doi-asserted-by":"crossref","unstructured":"Fredman ML, Robert TE (1984) Fibonacci heaps and their uses in improved network optimization algorithms. In: 25th IEEE annual symposium on foundations of computer science, pp 338\u2013346","DOI":"10.1109\/SFCS.1984.715934"},{"key":"1750_CR10","unstructured":"Gerkey BP, Konolige K (2008) Planning and control in unstructured terrain. In: Workshop on path planning on costmaps. Proceedings of the IEEE international conference on robotics and automation (ICRA)"},{"key":"1750_CR11","first-page":"323","volume":"7","author":"FO Hadlock","year":"1977","unstructured":"Hadlock FO (1977) A shortest path algorithm for grid graphs. Netw Int J 7:323\u2013334","journal-title":"Netw Int J"},{"key":"1750_CR12","doi-asserted-by":"crossref","unstructured":"Harabor D, Grastien A (2011) Online graph pruning for pathfinding on grid maps. In: Proceedings of association for the advancement of artificial intelligence","DOI":"10.1609\/aaai.v25i1.7994"},{"key":"1750_CR13","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"PE Hart","year":"1968","unstructured":"Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 4:100\u2013107","journal-title":"IEEE Trans Syst Sci Cybern"},{"key":"1750_CR14","first-page":"219","volume":"5","author":"P Ira","year":"1970","unstructured":"Ira P (1970) First results on the effect of error in heuristic search. Mach Intell 5:219\u2013236","journal-title":"Mach Intell"},{"key":"1750_CR15","unstructured":"Iroboapp (2015a) Design and analysis of intelligent algorithms for robotic problems and applications. http:\/\/www.iroboapp.org . Accessed 3 Feb 2015"},{"key":"1750_CR16","unstructured":"Iroboapp (2015b) Adding a global path planner as plugin in ROS. http:\/\/www.iroboapp.org\/index.php?title=Adding_A_Global_Path_Planner_As_Plugin_in_ROS . Accessed 27 Apr 2015"},{"key":"1750_CR17","doi-asserted-by":"crossref","unstructured":"Jigang W, Han P, Jagadeesh GR, Srikanthan T (2010) Practical algorithm for shortest path on large networks with time-dependent edge-length. In 2010 2nd international conference on computer engineering and technology (ICCET), vol 2, Chengdu, pp 57\u201360","DOI":"10.1109\/ICCET.2010.5485321"},{"key":"1750_CR18","unstructured":"Judea P (1984) Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley, New York"},{"key":"1750_CR19","doi-asserted-by":"crossref","unstructured":"Kanoulas E, Du Y, Xia T, Zhang D (2006) Finding fastest paths on a road network with speed patterns. In: Proceedings of the 22nd international conference on data engineering, ICDE\u201906, pp 10\u201319","DOI":"10.1109\/ICDE.2006.71"},{"key":"1750_CR20","unstructured":"Koenig S, Likhachev M (2002) D* lite. In: Proceedings of the 18th national conference on artificial intelligence (AAAI), pp 476\u2013483"},{"key":"1750_CR21","unstructured":"Likhachev M, Ferguson D, Gordon G, Stentz A, Thrun S (2005) Anytime dynamic A*: an anytime, replanning algorithm. In: Proceedings of the international conference on automated planning and scheduling (ICAPS)"},{"key":"1750_CR22","unstructured":"Maps:benchmark (2015). http:\/\/movingai.com\/benchmarks . Accessed 3 Mar 2015"},{"key":"1750_CR23","doi-asserted-by":"crossref","unstructured":"Masehian E, Amin-Naseri MR (2006) A tabu search-based approach for online motion planning. In: IEEE international conference on industrial technology, Mumbai, pp 2756\u20132761","DOI":"10.1109\/ICIT.2006.372662"},{"key":"1750_CR24","unstructured":"Maxim Likhachev GG, Thrun S (2004) Ara*: Anytime A* with provable bounds on sub-optimality. In: Advances in neural information processing systems (NIPS), vol 16. MIT Press, New York"},{"key":"1750_CR25","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/j.jda.2007.08.003","volume":"7","author":"S Peyer","year":"2009","unstructured":"Peyer S, Rautenbach D, Vygen J (2009) A generalization of Dijkstra\u2019s shortest path algorithm with applications to VLSI routing. J Discrete Algorithms 7:377\u2013390","journal-title":"J Discrete Algorithms"},{"key":"1750_CR26","unstructured":"Pohl I (1973) The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving. In: Proceedings of the third international joint conference on artificial intelligence (IJCAI-73), California, pp 12\u201317"},{"key":"1750_CR27","doi-asserted-by":"crossref","unstructured":"Potamias M, Bonchi F, Castillo C, Gionis A (2009) Fast shortest path distance estimation in large networks. In: Proceedings of the 18th ACM conference on information and knowledge management (CIKM 09), Hong Kong, pp 867\u2013876","DOI":"10.1145\/1645953.1646063"},{"key":"1750_CR28","unstructured":"Robot Operating System (ROS) (2015). http:\/\/www.ros.org . Accessed 15 Apr 2015"},{"key":"1750_CR29","unstructured":"ROS Wiki (2015) Writing a global path planner as plugin in ROS. http:\/\/wiki.ros.org\/navigation\/Tutorials\/Writing%20A%20Global%20Path%20Planner%20As%20Plugin%20in%20ROS . Accessed 4 June 2015"},{"key":"1750_CR30","unstructured":"Russell S, Norvig P (2009) Artificial intelligence: a modern approach, 3nd edn. Prentice Hall, New York"},{"issue":"4","key":"1750_CR31","first-page":"260","volume":"2","author":"NA Shiltagh","year":"2013","unstructured":"Shiltagh NA, Jalal LD (2013) Optimal path planning for intelligent mobile robot navigation using modified particle swarm optimization. Int J Eng Adv Technol (IJEAT) 2(4):260\u2013267","journal-title":"Int J Eng Adv Technol (IJEAT)"},{"key":"1750_CR32","doi-asserted-by":"crossref","unstructured":"Sturtevant N (2012) Benchmarks for grid-based pathfinding. Trans Comput Intell AI Games 4(2):144\u2013148. http:\/\/web.cs.du.edu\/sturtevant\/papers\/benchmarks.pdf","DOI":"10.1109\/TCIAIG.2012.2197681"},{"key":"1750_CR33","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/j.jda.2007.08.003","volume":"7","author":"JV Sven Peyera","year":"2009","unstructured":"Sven Peyera JV, Rautenbachb D (2009) A generalization of Dijkstra\u2019s shortest path algorithm with applications to VLSI routing. J Discrete Algorithms 7:377\u2013390","journal-title":"J Discrete Algorithms"},{"key":"1750_CR34","doi-asserted-by":"crossref","unstructured":"Tiwari R, Shukla A, Kala R (2012) Intelligent planning for mobile robotics: algorithmic approaches","DOI":"10.4018\/978-1-4666-2074-2"},{"key":"1750_CR35","unstructured":"van den Berg J, Shah R, Huang A, Goldberg K (2005) ANA*: anytime nonparametric A*. In: Annual conference of the association for the advancement of artificial intelligence (AAAI)"}],"container-title":["Soft Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-015-1750-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00500-015-1750-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-015-1750-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-015-1750-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,12]],"date-time":"2023-08-12T11:33:25Z","timestamp":1691840005000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00500-015-1750-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,23]]},"references-count":35,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2016,10]]}},"alternative-id":["1750"],"URL":"https:\/\/doi.org\/10.1007\/s00500-015-1750-1","relation":{},"ISSN":["1432-7643","1433-7479"],"issn-type":[{"value":"1432-7643","type":"print"},{"value":"1433-7479","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,23]]}}}