{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T19:44:25Z","timestamp":1769715865131,"version":"3.49.0"},"reference-count":13,"publisher":"SAGE Publications","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IFS"],"published-print":{"date-parts":[[2023,6,1]]},"abstract":"<jats:p>In the cooperative multi-agent pathfinding and motion planning, given a unique start position and a unique goal position for each agent, all agents are able to pursue their own goals without colliding with each other. To aim at realizing the collision-free motion of the agents within the tractable time, this work proposes a polynomial-time solver, called the HBD-AOI, hybridizing centralized and decentralized schemes. Firstly, an algorithm of centralized pathfinding is utilized to plan the optimal paths of all agents. Afterwards, each of the agents updates the local motion pattern to tracks its own planned waypoints with the obstacle avoidance in a decentralized manner. Furthermore, to resolve unavoidable egoistic conflicts occurring in the decentralized scheme, a centralized intervener with the route replanning is invoked to coach the involved agents to abort the existing deadlocks. Bounded by an amount of time, the performances of the proposed and benchmarked algorithms are simulated on the same instance, from the evaluated testbeds that consists of various maps and scenarios. In the simulations, it is proved that this work outperforms other benchmarked algorithms for all presented instances in the term of the success rate. The experimental results are also demonstrated to verify the feasibility of the proposed methodology.<\/jats:p>","DOI":"10.3233\/jifs-223157","type":"journal-article","created":{"date-parts":[[2023,3,10]],"date-time":"2023-03-10T12:15:55Z","timestamp":1678450555000},"page":"8925-8941","source":"Crossref","is-referenced-by-count":0,"title":["A polynomial-time hybrid solver for multi-agent motion navigation against deadlocks"],"prefix":"10.1177","volume":"44","author":[{"given":"W.-C.","family":"Wang","sequence":"first","affiliation":[{"name":"Department of Power Mechanical Engineering, National Tsing Hua University, Hsinchu, Taiwan"}]},{"given":"Y.-W.","family":"Yeh","sequence":"additional","affiliation":[{"name":"Department of Power Mechanical Engineering, National Tsing Hua University, Hsinchu, Taiwan"}]},{"given":"R.","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Power Mechanical Engineering, National Tsing Hua University, Hsinchu, Taiwan"}]}],"member":"179","reference":[{"issue":"2","key":"10.3233\/JIFS-223157_ref3","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for theheuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEETransactions on Systems Science and Cybernetics"},{"key":"10.3233\/JIFS-223157_ref4","first-page":"533","article-title":"Theta*: Any-angle pathplanning on grids","volume":"39","author":"Daniel","year":"2010","journal-title":"Journal of Artificial IntelligenceResearch"},{"key":"10.3233\/JIFS-223157_ref5","doi-asserted-by":"crossref","first-page":"119310","DOI":"10.1109\/ACCESS.2021.3108177","article-title":"A comprehensive review ofcoverage path planning in robotics using classical and heuristicalgorithms","volume":"9","author":"Tan","year":"2021","journal-title":"IEEE Access"},{"issue":"7","key":"10.3233\/JIFS-223157_ref6","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1177\/0278364911406761","article-title":"Sampling-based algorithms for optimalmotion planning","volume":"30","author":"Karaman","year":"2011","journal-title":"The International Journal of RoboticsResearch"},{"key":"10.3233\/JIFS-223157_ref9","first-page":"40","article-title":"Conflict-basedsearch for optimal multi-agent pathfinding","volume":"219","author":"Sharon","year":"2015","journal-title":"ArtificialIntelligence"},{"key":"10.3233\/JIFS-223157_ref10","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/s10846-006-9113-x","article-title":"Decentralized navigationfunctions for multiple robotic agents with limited sensingcapabilities","volume":"48","author":"Dimarogonas","year":"2007","journal-title":"Journal of Intelligent and Robotic Systems"},{"issue":"1","key":"10.3233\/JIFS-223157_ref11","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1177\/027836498600500106","article-title":"Real-time obstacle avoidance for manipulators and mobilerobots","volume":"5","author":"Khatib","year":"1986","journal-title":"The International Journal of Robotics Research"},{"key":"10.3233\/JIFS-223157_ref13","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.robot.2016.12.008","article-title":"Optimal path planning and execution for mobile robotsusing genetic algorithm and adaptive fuzzy-logic control","volume":"89","author":"Bakdi","year":"2017","journal-title":"Robotics and Autonomous Systems"},{"issue":"12","key":"10.3233\/JIFS-223157_ref20","doi-asserted-by":"crossref","first-page":"13874","DOI":"10.1109\/TCYB.2021.3128051","article-title":"Distributed time-varyingoptimization of second-order multiagent systems under limitedinteraction ranges, in","volume":"52","author":"Hong","year":"2022","journal-title":"IEEE Transactions on Cybernetics"},{"issue":"7","key":"10.3233\/JIFS-223157_ref21","doi-asserted-by":"crossref","first-page":"7218","DOI":"10.1109\/TCYB.2020.3029825","article-title":"On distributed implementationof switch-based adaptive dynamic programming, in","volume":"52","author":"Liu","year":"2022","journal-title":"IEEETransactions on Cybernetics"},{"issue":"1","key":"10.3233\/JIFS-223157_ref24","first-page":"55","article-title":"Velocity obstacleapproaches for multi-agent collision avoidance","volume":"7","author":"Douthwaite","year":"2019","journal-title":"UnmannedSystems"},{"key":"10.3233\/JIFS-223157_ref25","doi-asserted-by":"crossref","first-page":"1225","DOI":"10.1002\/asjc.2431","article-title":"Coordinating multiple mobile robots forobstacle avoidance using cloud computing","volume":"23","author":"Song","year":"2021","journal-title":"Asian J Control."},{"issue":"1","key":"10.3233\/JIFS-223157_ref27","first-page":"55","article-title":"MAPP: a scalable multi-agent path planningalgorithm with tractability and completeness guarantees","volume":"42","author":"Wang","year":"2011","journal-title":"Journal of Artificial Intelligence Research"}],"container-title":["Journal of Intelligent &amp; Fuzzy Systems"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/JIFS-223157","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T07:50:07Z","timestamp":1769673007000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/JIFS-223157"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,1]]},"references-count":13,"journal-issue":{"issue":"6"},"URL":"https:\/\/doi.org\/10.3233\/jifs-223157","relation":{},"ISSN":["1064-1246","1875-8967"],"issn-type":[{"value":"1064-1246","type":"print"},{"value":"1875-8967","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,1]]}}}