{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:38:52Z","timestamp":1760240332532,"version":"build-2065373602"},"reference-count":25,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T00:00:00Z","timestamp":1557878400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We consider the use of multiple mobile agents to explore an unknown area. The area is orthogonal, such that all perimeter lines run both vertically and horizontally. The area may consist of unknown rectangular holes which are non-traversable internally. For the sake of analysis, we assume that the area is discretized into N points allowing the agents to move from one point to an adjacent one. Mobile agents communicate through face-to-face communication when in adjacent points. The objective of exploration is to develop an online algorithm that will explore the entire area while reducing the total work of all k agents, where the work is measured as the number of points traversed. We propose splitting the exploration into two alternating tasks, perimeter and room exploration. The agents all begin with the perimeter scan and when a room is found they transition to room scan after which they continue with perimeter scan until the next room is found and so on. Given the total traversable points N, our algorithm completes in total     O ( N )     work with each agent performing     O ( N \/ k )     work, namely the work is balanced. If the rooms are hole-free the exploration time is also asymptotically optimal,     O ( N \/ k )    . To our knowledge, this is the first agent coordination algorithm that considers simultaneously work balancing and small exploration time.<\/jats:p>","DOI":"10.3390\/a12050104","type":"journal-article","created":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T11:37:40Z","timestamp":1557920260000},"page":"104","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Balanced Parallel Exploration of Orthogonal Regions"],"prefix":"10.3390","volume":"12","author":[{"given":"Wyatt","family":"Clements","sequence":"first","affiliation":[{"name":"School of Electrical Engineering and Computer Science, Louisiana State University, Baton Rouge, LA 70803, USA"}]},{"given":"Costas","family":"Busch","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering and Computer Science, Louisiana State University, Baton Rouge, LA 70803, USA"}]},{"given":"Limeng","family":"Pu","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering and Computer Science, Louisiana State University, Baton Rouge, LA 70803, USA"}]},{"given":"Daniel","family":"Smith","sequence":"additional","affiliation":[{"name":"School of Biological and Agricultural Engineering, Louisiana State University, Baton Rouge, LA 70803, USA"}]},{"given":"Hsiao-Chun","family":"Wu","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering and Computer Science, Louisiana State University, Baton Rouge, LA 70803, USA"}]}],"member":"1968","published-online":{"date-parts":[[2019,5,15]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Alam, T., Bobadilla, L., and Shell, D. (2017, January 10\u201312). Minimalist Robot Navigation and Coverage using a Dynamical System Approach. Proceedings of the 2017 First IEEE International Conference on Robotic Computing, Taichung, Taiwan.","DOI":"10.1109\/IRC.2017.23"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1258","DOI":"10.1016\/j.robot.2013.09.004","article-title":"A survey on coverage path planning for robotics","volume":"61","author":"Galceran","year":"2013","journal-title":"Robot. Auton. Syst."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Pierson, A., Figueiredo, L.C., Pimenta, L.C.A., and Schwager, M. (2015, January 26\u201330). Adapting to performance variations in multi-robot coverage. Proceedings of the 2015 IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, USA.","DOI":"10.1109\/ICRA.2015.7139032"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/s10472-009-9126-9","article-title":"A framework for multi-robot node coverage in sensor networks","volume":"52","author":"Gasparri","year":"2008","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_5","unstructured":"Batalin, M.A., Sukhatme, G.S., and Hattig, M. (May, January 26). Mobile robot navigation using a sensor network. Proceedings of the IEEE International Conference on Robotics and Automation, New Orleans, LA, USA."},{"key":"ref_6","first-page":"2046","article-title":"Robot Assisted Wireless Sensor Network for Monitoring and Detection of Explosives in Indoor Environment","volume":"3","author":"Freeman","year":"2011","journal-title":"Int. J. Comput. Sci. Eng."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/MPRV.2004.17","article-title":"Robot and Sensor Networks for First Responders","volume":"3","author":"Kumar","year":"2004","journal-title":"IEEE Pervas. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Masoud, A., and Al-Shaikhi, A. (2015, January 15\u201318). Time-Sensitive, Sensor-based, Joint Planning and Control of Mobile Robots in Cluttered Spaces: A Harmonic Potential Approach. Proceedings of the 54th IEEE Conference on Decision and Control (CDC), Osaka, Japan.","DOI":"10.1109\/CDC.2015.7402634"},{"key":"ref_9","unstructured":"Reich, J., and Sklar, E. Robot-Sensor Networks For Search And Rescue In Proceedings of the IEEE International Workshop on Safety, Security and Rescue Robotics, Gaithersburg, MD, USA, 22\u201324 August 2006."},{"key":"ref_10","unstructured":"Ortolf, C., and Schindelhauer, C. (July, January 29). Online multi-robot exploration of grid graphs with rectangular obstacles. Proceedings of the Twenty-Fourth Annual Acm Symposium On Parallelism In Algorithms And Architectures, San Diego, CA, USA."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Ray, D., Mandal, A., Majumder, S., and Mukhopadhyay, S. (2011, January 7\u201311). Human-like Gradual Multi-agent Q-learning Using the Concept of Behavior-based Robotics for Autonomous Exploration. Proceedings of the IEEE International Conference on Robotics and Biomimetrics, Karon Beach, Thailand.","DOI":"10.1109\/ROBIO.2011.6181717"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"945","DOI":"10.1016\/j.robot.2006.06.003","article-title":"Distributed multi-robot coordination in area exploration","volume":"54","author":"Sheng","year":"2006","journal-title":"Robot. Auton. Syst."},{"key":"ref_13","unstructured":"Sharma, R., Honc, D., Du\u0161ek, F., and Kumar T., G. (June, January 31). Frontier Based Multi Robot Area Exploration Using Prioritized Routing. Proceedings of the 30th European Conference on Modelling and Simulation, Regensburg, Germany."},{"key":"ref_14","first-page":"1","article-title":"Multi Robot Area Exploration using Modified Frontier Algorithm","volume":"IX","author":"Agrawal","year":"2015","journal-title":"Int. J. Comput. Eng. Appl."},{"key":"ref_15","unstructured":"Fazli, P. (2010, January 3\u20138). Fault-tolerant multi-robot area coverage with limited visibility. Proceedings of the ICRA 2010 Workshop on Search and Pursuit\/Evasion in the Physical World: Efficiency, Scalability, and Guarantees, Anchorage, Alaska."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Palmieri, N., Yang, X., and Marano, S. (2016, January 24\u201327). Coordination Techniques of Mobile Robots with Energy Constraints. Proceedings of the International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS), Montreal, QC, Canada.","DOI":"10.1109\/SPECTS.2016.7570520"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1109\/MRA.2014.2304091","article-title":"Group Mapping: A Topological Approach to Map Merging for Multiple Robots","volume":"21","author":"Saeedi","year":"2014","journal-title":"IEEE Robot. Autom."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Zhou, Y., and Zincir-Heywood, A. (2004, January 21). Intelligent Agents for Routing on Mobile Ad-hoc Networks. Proceedings of the Conference on Communication Networks and Services Research, Fredericton, NB, Canada.","DOI":"10.1109\/DNSR.2004.1344735"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Rodriguez, A., Gomez, J., and Diaconescu, A. (2015, January 21\u201325). Foraging-Inspired Self-Organisation for Terrain Exploration with Failure-Prone Agents. Proceedings of the IEEE 9th International Conference on Self-Adaptive and Self-Organizing Systems, Cambridge, MA, USA.","DOI":"10.1109\/SASO.2015.20"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Veseras, A., Wiedemann, T., Manss, C., Magel, L., Mueller, J., Shutin, D., and Merino, L. (2016, January 16\u201321). Decentralized Multi-agent Exploration with Online-learning of Gaussian Processes. Proceedings of the 2016 IEEE International Conference on Robotics and Automation (ICRA), Stockholm, Sweden.","DOI":"10.1109\/ICRA.2016.7487617"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/s10514-012-9319-7","article-title":"Multi-robot repeated area coverage","volume":"34","author":"Fazli","year":"2013","journal-title":"Auton. Robots"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Kellett, M., Mason, P., and Santoro, N. (2009, January 23\u201329). Map Construction and Exploration by Mobile Agents Scattered in a Dangerous Network. Proceedings of the IEEE International Symposium on Parallel and Distributed Processing, Rome, Italy.","DOI":"10.1109\/IPDPS.2009.5161080"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/s10514-011-9249-9","article-title":"Exploration strategies based on multi-criteria decision making for searching environments in rescue operations","volume":"31","author":"Basilico","year":"2011","journal-title":"Auton. Robots"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1023\/A:1011219024159","article-title":"Collaborative Robot Exploration and Rendezvous: Algorithms, Performance Bounds and Observations","volume":"11","author":"Roy","year":"2001","journal-title":"Auton. Robots"},{"key":"ref_25","unstructured":"Hoog, J., Cameron, S., and Visser, A. (2009, January 15\u201320). Role-Based Autonomous Mulit-robot Exploration. Proceedings of the 2009 Computation World: Future Computing, Service Computation, Cognitive, Adaptive, Content, Patterns, Athens, Greece."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/5\/104\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:52:05Z","timestamp":1760187125000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/5\/104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,15]]},"references-count":25,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2019,5]]}},"alternative-id":["a12050104"],"URL":"https:\/\/doi.org\/10.3390\/a12050104","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,5,15]]}}}