{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T10:56:31Z","timestamp":1648810591637},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,11,1]],"date-time":"2012-11-01T00:00:00Z","timestamp":1351728000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2012,11,1]],"date-time":"2012-11-01T00:00:00Z","timestamp":1351728000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Braz Comput Soc"],"published-print":{"date-parts":[[2013,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>This paper presents a set of novel modifications that can be applied to any grid-based path planning algorithm from the A* family used in mobile robotics. Five modifications are presented regarding the way the robot sees an obstacle and its target to plan the robot\u2019s path. The modifications make it possible for the robot to get to the target faster than traditional algorithms, as well as to avoid obstacles that move as fast as (or even faster than) the robot. Some simulations were made using a crowded and highly dynamic environment with twelve randomly moving obstacles. In these first simulations, a middle sized 5DPO robot was used. Also, real experiments were made with a small-sized version of a 5DPO robot to validate the algorithm\u2019s effectiveness. In all simulations and real robot experiments the objects are considered to be moving at a constant speed. Finally, we present an overall discussion and conclusion of this paper.<\/jats:p>","DOI":"10.1007\/s13173-012-0091-5","type":"journal-article","created":{"date-parts":[[2012,10,31]],"date-time":"2012-10-31T22:18:31Z","timestamp":1351721911000},"page":"167-179","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A set of novel modifications to improve algorithms from the A* family applied in mobile robotics"],"prefix":"10.1007","volume":"19","author":[{"given":"Tiago Pereira","family":"do Nascimento","sequence":"first","affiliation":[]},{"given":"Pedro","family":"Costa","sequence":"additional","affiliation":[]},{"given":"Paulo G.","family":"Costa","sequence":"additional","affiliation":[]},{"given":"Ant\u00f3nio Paulo","family":"Moreira","sequence":"additional","affiliation":[]},{"given":"Andr\u00e9 Gustavo Scolari","family":"Concei\u00e7\u00e3o","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,11,1]]},"reference":[{"key":"91_CR1","doi-asserted-by":"crossref","unstructured":"Alejo D, Conde R, Cobano J, Ollero A (2009) Multi-UAV collision avoidance with separation assurance under uncertainties. In: 2009 IEEE international conference on mechatronics, pp 1\u20136","DOI":"10.1109\/ICMECH.2009.4957235"},{"key":"91_CR2","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1177\/0278364906069166","volume":"25","author":"DJ Balkcom","year":"2006","unstructured":"Balkcom DJ (2006) Time-optimal trajectories for an omni-directional vehicle. Int J Robot Res 25:985\u2013999","journal-title":"Int J Robot Res"},{"key":"91_CR3","doi-asserted-by":"crossref","first-page":"902","DOI":"10.1109\/TRO.2009.2022441","volume":"25","author":"F Belkhouche","year":"2009","unstructured":"Belkhouche F (2009) Reactive path planning in a dynamic environment. IEEE Trans Robot 25:902\u2013911","journal-title":"IEEE Trans Robot"},{"key":"91_CR4","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1109\/TRO.2009.2019145","volume":"25","author":"EJ Bernabeu","year":"2009","unstructured":"Bernabeu EJ (2009) Fast generation of multiple collision-free and linear trajectories in dynamic environments. IEEE Trans Robot 25:967\u2013975","journal-title":"IEEE Trans Robot"},{"key":"91_CR5","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1109\/MRA.2008.921540","volume":"15","author":"P Bhattacharya","year":"2008","unstructured":"Bhattacharya P, Gavrilova M (2008) Roadmap-based path planning\u2014using the Voronoi diagram for a clearance-based shortest path. IEEE Robot Autom Mag 15:58","journal-title":"IEEE Robot Autom Mag"},{"key":"91_CR6","doi-asserted-by":"crossref","unstructured":"Bruce J, Veloso M (2006) Safe multirobot navigation within dynamics constraints. In: Proceedings of the IEEE, vol 94, pp\u00a01398\u20131411","DOI":"10.1109\/JPROC.2006.876915"},{"key":"91_CR7","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1109\/TSMCB.2008.2008561","volume":"39","author":"C Cai","year":"2009","unstructured":"Cai C, Ferrari S (2009) Information-driven sensor path planning by approximate cell decomposition. IEEE Trans Syst Man Cybernet B Cybernet 39:672\u2013689","journal-title":"IEEE Trans Syst Man Cybernet B Cybernet"},{"key":"91_CR8","doi-asserted-by":"crossref","unstructured":"Conceicao AS, Moreira A, Costa P (2009) Practical approach of modeling and parameters estimation for omnidirectional mobile robots. In: IEEE\/ASME transactions on mechatronics, pp 377\u2013381","DOI":"10.1109\/TMECH.2009.2013615"},{"key":"91_CR9","unstructured":"Costa P, Moreira AP, Costa PJ (2009) Real-time path planning using a modified A* algorithm. In: ROBOTICA 2009\u20149th conference on mobile robots and competitions, pp 141\u2013146"},{"key":"91_CR10","unstructured":"Costa PJ (2012) Simtwo. http:\/\/paginas.fe.up.pt\/paco\/wiki\/index.php?n=Main.SimTwo"},{"key":"91_CR11","unstructured":"Ferguson D, Likhachev M, Stentz A (2005) A guide to heuristic-based path planning. In: Proceedings of the international workshop on planning under uncertainty for autonomous systems. International conference on automated planning and scheduling (ICAPS), pp 1\u201310"},{"key":"91_CR12","unstructured":"Ferreira JR, Moreira APGM (2010) Non-linear model predictive controller for trajectory tracking of an omni-directional robot using a simplified model. In: 9th Portuguese conference on automatic control"},{"issue":"7","key":"91_CR13","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1177\/027836499801700706","volume":"17","author":"P Fiorini","year":"1998","unstructured":"Fiorini P, Shiller Z (1998) Motion planning in dynamic environments using velocity obstacles. Int J Robot Res 17(7):760\u2013772","journal-title":"Int J Robot Res"},{"issue":"2","key":"91_CR14","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1109\/TSMCB.2004.842368","volume":"35","author":"SS Ge","year":"2005","unstructured":"Ge SS, Lai X, Mamun AA (2005) Boundary following and globally convergent path planning using instant goals. IEEE Trans Syst Man Cybernet 35(2):240\u2013254","journal-title":"IEEE Trans Syst Man Cybernet"},{"key":"91_CR15","doi-asserted-by":"crossref","unstructured":"Haro F, Torres M (2006) A comparison of path planning algorithms for omni-directional robots in dynamic environments. In: 2006 IEEE 3rd Latin American robotics symposium, pp 18\u201325","DOI":"10.1109\/LARS.2006.334319"},{"key":"91_CR16","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1109\/TMECH.2008.2000822","volume":"13","author":"G Jan","year":"2008","unstructured":"Jan G, Parberry I (2008) Optimal path planning for mobile robot navigation. IEEE\/ASME Trans Mechatron 13:451\u2013460","journal-title":"IEEE\/ASME Trans Mechatron"},{"key":"91_CR17","doi-asserted-by":"crossref","unstructured":"Khantanapoka K, Chinnasarn K (2009) Pathfinding of 2D& 3D game real-time strategy with depth direction algorithm for multi-layer. In: 2009 Eighth international symposium on natural language processing","DOI":"10.1109\/SNLP.2009.5340922"},{"key":"91_CR18","doi-asserted-by":"crossref","unstructured":"Kurihara K, Nishiuchi N, Hasegawa J, Masuda K (2005) Mobile robots path planning method with the existence of moving obstacles. In: 2005 IEEE conference on emerging technologies and factory automation, pp 195\u2013202.","DOI":"10.1109\/ETFA.2005.1612520"},{"key":"91_CR19","doi-asserted-by":"crossref","first-page":"1541","DOI":"10.1109\/TSMCB.2007.906577","volume":"37","author":"X-c Lai","year":"2007","unstructured":"Lai X-c, Ge SS, Mamun AA (2007) Hierarchical incremental path planning and motion planning considering accelerations. IEEE Trans Syst Man Cybernet 37:1541\u20131554","journal-title":"IEEE Trans Syst Man Cybernet"},{"key":"91_CR20","doi-asserted-by":"crossref","unstructured":"Latombe J-C (1991) Robot motion planning. Kluwer, Dordrecht","DOI":"10.1007\/978-1-4615-4022-9"},{"issue":"4","key":"91_CR21","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1109\/TSMCC.2009.2020789","volume":"39","author":"H Li","year":"2009","unstructured":"Li H, Yang SX, Seto ML (2009) Neural-network-based path planning for a multirobot system with moving obstacles. IEEE Trans Syst Man Cybernet C 39(4):410\u2013419","journal-title":"IEEE Trans Syst Man Cybernet C"},{"key":"91_CR22","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":"91_CR23","unstructured":"Nascimento TP, Concei\u00e7\u00e3o AGS, Moreira APGM (2010) Omnidirectional mobile robot\u2019s multivariable trajectory tracking control: a robustness analysis. In: 9th Portuguese conference on automatic control"},{"issue":"2","key":"91_CR24","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1109\/TRO.2004.838008","volume":"21","author":"P \u00d6gren","year":"2005","unstructured":"\u00d6gren P, Leonard NE (2005) A convergent dynamic window approach to obstacle avoidance. IEEE Trans Robot 21(2):188\u2013195","journal-title":"IEEE Trans Robot"},{"key":"91_CR25","doi-asserted-by":"crossref","first-page":"1201","DOI":"10.1109\/TRO.2005.853484","volume":"21","author":"K Pathak","year":"2005","unstructured":"Pathak K, Agrawal SK (2005) An integrated path-planning and control approach for nonholonimic unycycles using switched local potentials. IEEE Trans Robot 21:1201\u20131208","journal-title":"IEEE Trans Robot"},{"key":"91_CR26","unstructured":"Pearl J (1984) Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley, New York"},{"key":"91_CR27","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1109\/TRO.2008.918056","volume":"24","author":"M Peasgood","year":"2008","unstructured":"Peasgood M, Clark CM, McPhee J (2008) A complete and scalable strategy for coordinating multiple robots within roadmaps. IEEE Trans Robot 24:238\u2013292","journal-title":"IEEE Trans Robot"},{"key":"91_CR28","doi-asserted-by":"crossref","first-page":"1724","DOI":"10.1109\/TNN.2009.2029858","volume":"20","author":"H Qu","year":"2009","unstructured":"Qu H, Yang SX, Willms AR, Yi Z (2009) Real-time robot path planning based on a modified pulse-coupled neural network model. IEEE Trans Neural Netw 20:1724\u20131739","journal-title":"IEEE Trans Neural Netw"},{"key":"91_CR29","doi-asserted-by":"crossref","unstructured":"Rahman N, Jafri A (2005) Two layered behaviour based navigation of a mobile robot in an unstructured environment using fuzzy logic. In: Proceedings of the IEEE symposium on emerging technologies, pp 230\u2013235","DOI":"10.1109\/ICET.2005.1558886"},{"issue":"2","key":"91_CR30","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1109\/JSYST.2008.925270","volume":"2","author":"AK Ray","year":"2008","unstructured":"Ray AK, Behera L, Jamshidi M (2008) Sonar-based rover navigation for single or multiple platforms. Forward safe path and target switching approach. IEEE Syst J 2(2):258\u2013272","journal-title":"IEEE Syst J"},{"key":"91_CR31","unstructured":"Smith R (2010) Open dynamics engine. http:\/\/www.ode.org"},{"key":"91_CR32","doi-asserted-by":"crossref","unstructured":"Tang P (2001) Dynamic obstacle avoidance based on fuzzy inference and transposition principle for soccer robots. In: 10th IEEE international conference on fuzzy systems (Cat. No.01CH37297), pp 1062\u20131064","DOI":"10.1109\/FUZZ.2001.1008836"},{"key":"91_CR33","doi-asserted-by":"crossref","unstructured":"Wilkie D, Berg J, Manocha D (2009) Generalized velocity obstacles. In: IEEE\/RSJ international conference on intelligent robots and systems, New York","DOI":"10.1109\/IROS.2009.5354175"},{"issue":"3","key":"91_CR34","doi-asserted-by":"crossref","first-page":"884","DOI":"10.1109\/TSMCB.2008.921002","volume":"38","author":"AR Willms","year":"2008","unstructured":"Willms AR, Yang SX (2008) Real-time robot path planning via a distance-propagating dynamic system with obstacle clearance. IEEE Trans Syst Man Cybernet B: Cybernet 38(3):884\u2013893","journal-title":"IEEE Trans Syst Man Cybernet B: Cybernet"},{"issue":"4","key":"91_CR35","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1109\/TSMCA.2010.2044038","volume":"40","author":"J Yang","year":"2010","unstructured":"Yang J, Qu Z, Wang J, Conrad K (2010) Comparison of optimal solutions to real-time path planning for a mobile vehicle. IEEE Trans Syst Man Cybernet A: Syst Humans 40(4):721\u2013731","journal-title":"IEEE Trans Syst Man Cybernet A: Syst Humans"},{"key":"91_CR36","unstructured":"Yang S (2002) Real-time torque control of nonholonomic mobile robots with obstacle avoidance. In: Proceedings of the IEEE international symposium on intelligent control, pp 81\u201386"},{"key":"91_CR37","doi-asserted-by":"crossref","unstructured":"Yao J, Lin C, Xie X, Wang AJ, Hung C-C (2010) Path planning for virtual human motion using improved A* star algorithm. In: 2010 Seventh international conference on information technology: new generations","DOI":"10.1109\/ITNG.2010.53"}],"container-title":["Journal of the Brazilian Computer Society"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-012-0091-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13173-012-0091-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-012-0091-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-012-0091-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T20:14:17Z","timestamp":1630527257000},"score":1,"resource":{"primary":{"URL":"https:\/\/journal-bcs.springeropen.com\/articles\/10.1007\/s13173-012-0091-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,11,1]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["91"],"URL":"https:\/\/doi.org\/10.1007\/s13173-012-0091-5","relation":{},"ISSN":["0104-6500","1678-4804"],"issn-type":[{"value":"0104-6500","type":"print"},{"value":"1678-4804","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,11,1]]},"assertion":[{"value":"8 May 2012","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 2012","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 November 2012","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}