{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:06:30Z","timestamp":1760144790392,"version":"build-2065373602"},"reference-count":47,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2024,5,15]],"date-time":"2024-05-15T00:00:00Z","timestamp":1715731200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"\u201cApplied Research for Autonomous Robotic Systems\u201d","award":["MIS 5200632"],"award-info":[{"award-number":["MIS 5200632"]}]},{"name":"European Union\u2014NextGenerationEU","award":["MIS 5200632"],"award-info":[{"award-number":["MIS 5200632"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Multi-agent systems are utilized more often in the research community and industry, as they can complete tasks faster and more efficiently than single-agent systems. Therefore, in this paper, we are going to present an optimal approach to the multi-agent navigation problem in simply connected workspaces. The task involves each agent reaching its destination starting from an initial position and following an optimal collision-free trajectory. To achieve this, we design a decentralized control protocol, defined by a navigation function, where each agent is equipped with a navigation controller that resolves imminent safety conflicts with the others, as well as the workspace boundary, without requesting knowledge about the goal position of the other agents. Our approach is rendered sub-optimal, since each agent owns a predetermined optimal policy calculated by a novel off-policy iterative method. We use this method because the computational complexity of learning-based methods needed to calculate the global optimal solution becomes unrealistic as the number of agents increases. To achieve our goal, we examine how much the yielded sub-optimal trajectory deviates from the optimal one and how much time the multi-agent system needs to accomplish its task as we increase the number of agents. Finally, we compare our method results with a discrete centralized policy method, also known as a Multi-Agent Poli-RRT* algorithm, to demonstrate the validity of our method when it is attached to other research algorithms.<\/jats:p>","DOI":"10.3390\/s24103134","type":"journal-article","created":{"date-parts":[[2024,5,15]],"date-time":"2024-05-15T06:14:42Z","timestamp":1715753682000},"page":"3134","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Decentralized Navigation with Optimality for Multiple Holonomic Agents in Simply Connected Workspaces"],"prefix":"10.3390","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-1762-5129","authenticated-orcid":false,"given":"Dimitrios","family":"Kotsinis","sequence":"first","affiliation":[{"name":"Division of Systems and Automatic Control, Department of Electrical and Computer Engineering, University of Patras, Rio, 26504 Patras, Greece"},{"name":"Athena Research Center, Robotics Institute, Artemidos 6 & Epidavrou, 15125 Maroussi, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9850-2540","authenticated-orcid":false,"given":"Charalampos P.","family":"Bechlioulis","sequence":"additional","affiliation":[{"name":"Division of Systems and Automatic Control, Department of Electrical and Computer Engineering, University of Patras, Rio, 26504 Patras, Greece"},{"name":"Athena Research Center, Robotics Institute, Artemidos 6 & Epidavrou, 15125 Maroussi, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,5,15]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Xuan, P., and Lesser, V.R. (2002, January 15\u201319). Multi-Agent Policies: From Centralized Ones to Decentralized Ones. Proceedings of the First International Joint Conference on Autonomous Agents and Multi-Agent Systems, Bologna, Italy.","DOI":"10.1145\/545073.545078"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"2936","DOI":"10.1016\/j.automatica.2014.10.023","article-title":"Supervised Coverage Control of Multi-Agent Systems","volume":"50","author":"Stipanovic","year":"2014","journal-title":"Automatica"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"126871","DOI":"10.1109\/ACCESS.2022.3218653","article-title":"A Centralized Strategy for Multi-Agent Exploration","volume":"10","author":"Gul","year":"2022","journal-title":"IEEE Access"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.aei.2005.06.002","article-title":"Multi-Agent Robot Systems as Distributed Autonomous Systems","volume":"20","author":"Ota","year":"2006","journal-title":"Adv. Eng. Inform."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Romeh, A.E., and Mirjalili, S. (2023). Multi-Robot Exploration of Unknown Space Using Combined Meta-Heuristic Salp Swarm Algorithm and Deterministic Coordinated Multi-Robot Exploration. Sensors, 23.","DOI":"10.3390\/s23042156"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"10794","DOI":"10.1109\/LRA.2022.3192765","article-title":"MR-TopoMap: Multi-Robot Exploration Based on Topological Map in Communication Restricted Environment","volume":"7","author":"Zhang","year":"2022","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1016\/j.conengprac.2006.08.007","article-title":"Multi-Robot Exploration under the Constraints of Wireless Networking","volume":"15","author":"Rooker","year":"2007","journal-title":"Control Eng. Pract."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1000","DOI":"10.1177\/0278364917719333","article-title":"Multi-Robot Formation Control and Object Transport in Dynamic Environments via Constrained Optimization","volume":"36","author":"AlonsoMora","year":"2017","journal-title":"Int. J. Robot. Res."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Borate, S.S., and Vadali, M. (July, January 30). FFRRT: A Sampling-Based Path Planner for Flexible Multi-Robot Formations. Proceedings of the 2021 5th International Conference on Advances in Robotics, Kanpur, India.","DOI":"10.1145\/3478586.3480645"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1956","DOI":"10.1109\/TRO.2021.3072026","article-title":"Multiagent Planning and Control for Swarm Herding in 2D Obstacle Environments under Bounded Inputs","volume":"37","author":"Chipade","year":"2021","journal-title":"IEEE Trans. Robot."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1109\/TRO.2019.2943059","article-title":"Adaptive Multi-Robot Formation Planning to Enclose and Track a Target with Motion and Visibility Constraints","volume":"36","author":"Aranda","year":"2020","journal-title":"IEEE Trans. Robot."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"101293","DOI":"10.1016\/j.nahs.2022.101293","article-title":"Path Planning in Formation and Collision Avoidance for Multi-Agent Systems","volume":"47","author":"Cheng","year":"2023","journal-title":"Nonlinear Anal. Hybrid Syst."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"101755","DOI":"10.1016\/j.aei.2022.101755","article-title":"A Hybrid Formation Path Planning Based on A* and Multi-Target Improved Artificial Potential Field Algorithm in the 2D Random Environments","volume":"54","author":"Tong","year":"2022","journal-title":"Adv. Eng. Inform."},{"key":"ref_14","unstructured":"Banyassady, B., de Berg, M., Bringmann, K., Buchin, K., Fernau, H., Halperin, D., Kostitsyna, I., Okamoto, Y., and Slot, S. (2022, January 7\u201310). Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds. Proceedings of the 38th International Symposium on Computational Geometry, Berlin, Germany."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"100126","DOI":"10.1016\/j.ifacsc.2020.100126","article-title":"Multiagent Motion Planning with Sporadic Communications for Collision Avoidance","volume":"15","author":"Boardman","year":"2021","journal-title":"IFAC J. Syst. Control"},{"key":"ref_16","unstructured":"Petrovi\u0107, L., Markovi\u0107, I., and Seder, M. (2018, January 17\u201319). Multiagent Gaussian Process Motion Planning via Probabilistic Inference. Proceedings of the 12th IFAC Symposium on Robot Control, St Etienne, France."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Vlantis, P., Bechlioulis, C.P., and Kyriakopoulos, K.J. (2023). Navigation of Multiple Disk-Shaped Robots with Independent Goals within Obstacle-Cluttered Environments. Sensors, 23.","DOI":"10.3390\/s23010221"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"776","DOI":"10.1109\/LRA.2019.2893494","article-title":"Chance-Constrained Collision Avoidance for MAVs in Dynamic Environments","volume":"4","author":"Zhu","year":"2019","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1016\/0196-8858(90)90017-S","article-title":"Robot Navigation Functions on Manifolds with Boundary","volume":"11","author":"Koditschek","year":"1990","journal-title":"Adv. Appl. Math."},{"key":"ref_20","unstructured":"Loizou, S.G., and Kyriakopoulos, K.J. (October, January 30). Closed Loop Navigation for Multiple Holonomic Vehicles. Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, Lausanne, Switzerland."},{"key":"ref_21","unstructured":"Zavlanos, M.M., and Kyriakopoulos, K.J. (2003, January 18\u201320). Decentralized Motion Control of Multiple Mobile Agents. Proceedings of the 11th Mediterranean Conference on Control and Automation, Rhodes, Greece."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1002\/acs.921","article-title":"Cooperative Control of Multiple Vehicles with Limited Sensing","volume":"21","author":"Chen","year":"2006","journal-title":"Int. J. Adapt. Control Signal Process."},{"key":"ref_23","unstructured":"Loizou, S.G., and Kyriakopoulos, K.J. (2003, January 14\u201319). Closed Loop Navigation for Multiple Non-Holonomic Vehicles. Proceedings of the 2003 IEEE International Conference on Robotics and Automation, Taipei, Taiwan."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"5525","DOI":"10.1109\/TAC.2021.3119003","article-title":"Connectivity Preserving Formation Stabilization in an Obstacle-Cluttered Environment in the Presence of TimeVarying Communication Delays","volume":"67","author":"Loizou","year":"2022","journal-title":"IEEE Trans. Autom. Control"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1268","DOI":"10.1109\/TCST.2014.2363132","article-title":"Flocking, Formation Control, and Path Following for a Group of Mobile Robots","volume":"23","author":"Luis","year":"2015","journal-title":"IEEE Trans. Control Syst. Technol."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/j.automatica.2005.09.019","article-title":"A Feedback Stabilization and Collision Avoidance Scheme for Multiple Independent Non-point Agents","volume":"42","author":"Dimarogonas","year":"2006","journal-title":"Automatica"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1346","DOI":"10.1109\/TRO.2012.2210656","article-title":"Multiagent Navigation Functions Revisited","volume":"28","author":"Tanner","year":"2012","journal-title":"IEEE Trans. Robot."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1177\/0278364911406761","article-title":"Sampling-Based Algorithms for Optimal Motion Planning","volume":"30","author":"Karaman","year":"2011","journal-title":"Int. J. Robot. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"50933","DOI":"10.1109\/ACCESS.2019.2908100","article-title":"Systematic Literature Review of Sampling Process in Rapidly-Exploring Random Trees","volume":"7","author":"Medeiros","year":"2019","journal-title":"IEEE Access"},{"key":"ref_30","unstructured":"Rousseas, P., Bechlioulis, C.P., and Kyriakopoulos, K.J. (June, January 29). A Continuous Off-Policy Reinforcement Learning Scheme for Optimal Motion Planning in Simply-Connected Workspaces. Proceedings of the IEEE International Conference on Robotics and Automation, London, UK."},{"key":"ref_31","unstructured":"Vlachos, C., Rousseas, P., Bechlioulis, C.P., and Kyriakopoulos, K.J. (June, January 29). Reinforcement Learning-Based Optimal Multiple Waypoint Navigation. Proceedings of the IEEE International Conference on Robotics and Automation, London, UK."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Parras, J., Apell\u00e1niz, P.A., and Zazo, S. (2021). Deep Learning for Efficient and Optimal Motion Planning for AUVs with Disturbances. Sensors, 21.","DOI":"10.3390\/s21155011"},{"key":"ref_33","unstructured":"Chen, Y.F., Liu, M., Everett, M., and How, J.P. (June, January 29). Decentralized Non-communicating Multi-Agent Collision Avoidance with Deep Reinforcement Learning. Proceedings of the IEEE International Conference on Robotics and Automation, Singapore."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1109","DOI":"10.1177\/1077546320923279","article-title":"Smart Structures and Materials: Vibration and Control","volume":"26","author":"Benjeddou","year":"2020","journal-title":"J. Vib. Control"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Everett, M., Chen, Y.F., and How, J.P. (2018, January 1\u20135). Motion Planning among Dynamic, Decision-Making Agents with Deep Reinforcement Learning. Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, Madrid, Spain.","DOI":"10.1109\/IROS.2018.8593871"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"146264","DOI":"10.1109\/ACCESS.2019.2943253","article-title":"Joint Optimization of Multi-UAV Target Assignment and Path Planning Based on Multi-Agent Reinforcement Learning","volume":"7","author":"Qie","year":"2019","journal-title":"IEEE Access"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"2378","DOI":"10.1109\/LRA.2019.2903261","article-title":"PRIMAL: Path-Finding via Reinforcement and Imitation Multi-Agent Learning","volume":"4","author":"Sartoretti","year":"2019","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"2393","DOI":"10.1002\/int.22778","article-title":"MEMADDPG: An Efficient Learning-Based Motion Planning Method for Multiple Agents in Complex Environments","volume":"37","author":"Wan","year":"2022","journal-title":"Int. J. Intell. Syst."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Rousseas, P., Bechlioulis, C.P., and Kyriakopoulos, K.J. (2024). Reactive Optimal Motion Planning to Anywhere in the Presence of Moving Obstacles. Int. J. Robot. Res., 02783649241245729.","DOI":"10.1177\/02783649241245729"},{"key":"ref_40","unstructured":"Ragaglia, M., Prandini, M., and Bascetta, L. (2016). Modelling and Simulation for Autonomous Systems, Proceedings of the Third International Workshop, MESAS 2016, Rome, Italy, 15\u201316 June 2016, Springer International Publishing."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1109\/TRO.2008.918056","article-title":"A Complete and Scalable Strategy for Coordinating Multiple Robots within Roadmaps","volume":"24","author":"Peasgood","year":"2008","journal-title":"IEEE Trans. Robot."},{"key":"ref_42","first-page":"102","article-title":"Contributions to the Theory of Optimal Control","volume":"5","author":"Kalman","year":"1960","journal-title":"Bol. Soc. Mat. Mex."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1041","DOI":"10.1109\/TCYB.2015.2421338","article-title":"Off-Policy Actor-Critic Structure for Optimal Control of Unknown Systems with Disturbances","volume":"46","author":"Song","year":"2016","journal-title":"IEEE Trans. Cybern."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1992","DOI":"10.1109\/LRA.2022.3143308","article-title":"Trajectory Planning in Unknown 2D Workspaces: A Smooth, Reactive, Harmonics-Based Approach","volume":"7","author":"Rousseas","year":"2022","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"3861","DOI":"10.1109\/TAC.2016.2638961","article-title":"Control Barrier Function Based Quadratic Programs for Safety Critical Systems","volume":"62","author":"Ames","year":"2017","journal-title":"IEEE Trans. Autom. Control"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1016\/j.apm.2017.07.033","article-title":"Radial Basis Function Approximations: Comparison and Applications","volume":"51","author":"Majdisova","year":"2017","journal-title":"Appl. Math. Model."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Ragaglia, M., Prandini, M., and Bascetta, L. (2015, January 15\u201317). Poli-RRT*: Optimal RRT-based Planning for Constrained and Feedback Linearisable Vehicle Dynamics. Proceedings of the 14th European Control Conference, Linz, Austria.","DOI":"10.1109\/ECC.2015.7330917"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/24\/10\/3134\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:42:39Z","timestamp":1760107359000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/24\/10\/3134"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,15]]},"references-count":47,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2024,5]]}},"alternative-id":["s24103134"],"URL":"https:\/\/doi.org\/10.3390\/s24103134","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2024,5,15]]}}}