Multi-Robot Exploration and Optimization Methods

Version	Summary	Created by	Modification	Content Size	Created at	Operation
1		Ali El Romeh	--	2090	2023-07-09 15:53:44	\|
2	format change	Peter Tang	+ 1 word(s)	2091	2023-07-10 03:21:52	\| \|
3	acronyms	Ali El Romeh	-1 word(s)	2090	2023-11-20 04:08:16	\| \|
4	format change	Peter Tang	+ 1 word(s)	2091	2023-11-20 04:14:05	\|

This entry is adapted from the peer-reviewed paper 10.3390/math11112474

Exploring unknown environments using multiple robots has numerous applications in various fields but remains a challenging task. This entry proposes a novel hybrid optimization method called Hybrid Vulture-Coordinated Multi-Robot Exploration ( $H V C M E$ ), which combines Coordinated Multi-Robot Exploration ( $C M E$ ) and African Vultures Optimization Algorithm ( $A V O A$ ) to optimize the construction of a finite map in multi-robot exploration. The researchers compared $H V C M E$ with four other similar algorithms using three performance measures: run time, percentage of the explored area, and the number of times the method failed to complete a run. The experimental results show that HVCME outperforms the other four methods, demonstrating its effectiveness in optimizing the construction of a finite map in an unknown indoor environment.

Multi-Robot Exploration (HVCME) multi-robot exploration finite map

1. Introduction

Multi-robot exploration has garnered significant attention in contemporary times owing to its practical relevance across diverse domains ^[1]^[2]^[3]^[4]. In real-world deployment scenarios, such as exploring uncharted locations, human–robot teams provide numerous advantages. Multi-robot systems operated by a human operator may reach places that humans cannot, such as other planets or underwater, and can cover larger regions more effectively. As a result, how to efficiently develop and implement such systems is swiftly becoming a topic of study.

In such situations, swarm robots outperform single-robot systems, which are incapable of covering wide areas and present a key single point of failure for the mission. Although centralized multi-robot management is one option, robotic swarms with decentralized control have been found to be more efficient. The difficulties in programming swarm behaviors have already been discussed in several studies. Swarm control algorithms, also known as “behaviors”, are widely used, utilizing the processing power of all units together and significantly reducing the load on each robot. Furthermore, swarm robots rely on local interactions, both with their swarm neighbors and with their surroundings in the environment, which makes them more resilient to fluctuating mission circumstances ^[5].

Machine learning has recognized bio-inspired optimization algorithms in recent years as a way to address optimal solutions to complicated scientific and technical challenges with time and space constraints. These challenges are fundamentally nonlinear and are frequently constrained by path or terminal limitations ^[6]. The new trend is to use bio-inspired optimization algorithms, which offer a promising way to solve problems that standard optimization algorithms cannot handle efficiently.

Research in this field can be generally categorized into two main streams: deterministic algorithms and meta-heuristic algorithms. Deterministic algorithms are based on predefined rules that dictate the actions of robots, while meta-heuristic algorithms utilize search-based strategies to efficiently explore the environment. Unlike deterministic approaches, meta-heuristic algorithms draw inspiration from natural processes to optimize their search strategy.

2. Deterministic Methods

The field of robotics has recently shown considerable interest in multi-robot exploration due to its relevance in various practical applications. To address this, a method has been proposed for exploring such environments with multiple robots, which takes into account the trade-off between the cost of reaching a target location and its corresponding usefulness. This approach facilitates the allocation of appropriate targets to robots, allowing them to simultaneously explore different regions of the environment, especially in cases where communication ranges are limited. The effectiveness of the algorithm was assessed through experiments and simulations, which demonstrated its efficacy in efficiently distributing the robots throughout the environment and accomplishing their mission ^[7]. The research contributes to the growing body of research on multi-robot coordination for exploration tasks.

One of the earliest deterministic algorithms for multi-robot exploration is the coverage algorithm proposed by Galceran and Carreras ^[8]. The algorithm divides the environment into cells and assigns each robot to a cell. The robots explore their respective cells, and once they have completed their task, they move on to an adjacent unexplored cell. The algorithm was shown to be effective in small-scale environments, but its performance deteriorates in larger and more complex environments. Another deterministic algorithm for multi-robot exploration is the sweep algorithm proposed by Wang and Syrmos ^[9]. The algorithm assigns robots to different areas of the environment, and the robots explore their respective areas in a sweep-like manner. The algorithm was shown to be effective in environments with few obstacles, but its performance deteriorates in environments with more obstacles.

Andries and Charpillet ^[10] propose a new taboo-list approach for the multi-robot exploration of unknown structured environments that utilizes a distributed exploration algorithm, without being guided by frontiers, to guide agents on a globally shared map. The algorithm incorporates features such as robot perspective vision, variable vision range, and optimization to prevent agents from prematurely gathering at the rendezvous point. The performance of the algorithm is assessed via simulation using standardized maps.

Overall, deterministic approaches have proven to be effective in certain environments for exploration tasks. However, these approaches have a tendency to become trapped in local optima and repeat the same patterns, which can limit the efficiency of the exploration process. Unfortunately, changing the environment, such as the map, is not always a viable solution. Therefore, researchers have explored alternative approaches that involve randomized decision-making and distributed coordination among multiple robots, which can enhance the adaptability and scalability of the exploration process. These approaches have shown promising results in various scenarios, highlighting the importance of considering both deterministic and stochastic approaches in exploring unknown environments with multiple robots.

3. Metaheuristic Methods

Meta-heuristic algorithms have become increasingly popular in recent years due to their effectiveness in solving complex optimization problems. In this entry, the researchers explore several meta-heuristic algorithms: Grey Wolf Optimizer (GWO), Whale Optimization Algorithm (WOA), Salp Swarm Algorithm (SSA), Mountain Gazelle Optimizer (MGO), Sine Cosine Algorithm (SCA), Practical Swarm Algorithm (PSO), Genetic Algorithm (GA), and African Vulture Optimization Algorithm (AVOA).

The Grey Wolf Optimizer Algorithm proposed by Mirjalili and Lewis ^[11] is inspired by the social hierarchy and hunting behavior of grey wolves. The algorithm uses four types of grey wolves to model a hierarchical organization and the three primary stages of a search process to optimize problems. The algorithm has been tested on various optimization functions and classical engineering design problems, and the results show that the GWO algorithm is highly competitive compared to other well-known meta-heuristics. This algorithm has also been applied in the field of optical engineering.

The Salp Swarm Algorithm ^[12] is a meta-heuristic algorithm inspired by the foraging behavior of salps in the ocean, designed for solving optimization problems with both single and multiple objectives. Its effectiveness has been tested on various mathematical optimization functions, which have demonstrated that the algorithm can converge effectively toward the optimal solution. Additionally, the Salp Swarm Algorithm has been utilized to solve complex engineering design problems that require significant computational resources.

The Mountain Gazelle Optimizer ^[13] is a novel algorithm that takes cues from the social organization and hierarchy of wild mountain gazelles. Rigorous evaluations and tests have been carried out on this method using diverse benchmark functions and engineering problems. The results of these analyses demonstrate that the MGO outperforms comparable algorithms on most benchmark functions, indicating the algorithm’s excellent performance. Furthermore, the MGO’s search capabilities remain robust, even when faced with optimization problems of higher dimensions, thus cementing its effectiveness and versatility.

The Sine Cosine Algorithm ^[14] is a recent optimization method that leverages a mathematical model rooted in sine and cosine functions to generate a variety of initial random candidate solutions. The algorithm has undergone testing on several established test cases, which demonstrate its ability to explore diverse regions of a search space, avoid local optima, converge towards the global optimum, and capitalize on promising areas of a search space during optimization. Additionally, the Sine Cosine Algorithm has been employed to optimize the cross-section of an aircraft’s wing, highlighting its versatility and potential for real-world applications.

The Genetic Algorithm ^[15] is inspired by the process of natural selection and genetics. In this algorithm, a population of candidate solutions is evolved over successive generations through selection, crossover, and mutation. The algorithm has been applied to various optimization problems, such as function optimization, machine learning, and control system design. The GA has been found to be effective in finding optimal or near-optimal solutions in complex search spaces.

The Practical Swarm Algorithm ^[16] is a variant of the traditional Particle Swarm Optimization Algorithm that aims to improve the convergence and robustness of the algorithm. The PSO algorithm is inspired by the social behavior of bird flocking or fish schooling. The algorithm has been applied to several optimization problems, such as function optimization, parameter identification, and image processing. The Particle Swarm Optimization (PSO) Algorithm has demonstrated its efficacy in addressing complex optimization problems characterized by high dimensionality and non-linearity.

The Whale Optimization Algorithm ^[17] emulates the social behavior of humpback whales and their bubble-net hunting strategy. Extensive testing has been conducted on this algorithm using a range of optimization problems and structural design challenges, demonstrating its impressive competitiveness relative to both state-of-the-art meta-heuristic algorithms and conventional methods. Notably, the WOA algorithm has proven effective in tackling diverse real-world problems across multiple domains, including mechanical engineering, electrical engineering, and economics.

The African Vultures Optimization Algorithm proposed by Abdollahzadeh et al., ^[18], takes inspiration from the foraging and navigation behaviors of African vultures. This algorithm has undergone comprehensive testing on various benchmark functions and has been rigorously compared to several existing algorithms. The results of these tests reveal AVOA’s superiority in identifying optimal solutions for a wide range of optimization problems, including both single and multiple-objective optimization. AVOA has been successfully applied to problems in various fields, such as mechanical engineering, electrical engineering, and economics, demonstrating its versatility and efficacy. Notably, the Wilcoxon rank sum test was used for statistical evaluation, revealing the AVOA’s significant superiority at a 95% confidence interval.

Overall, a variety of meta-heuristic algorithms such as GA, PSO, GWO, SSA, MGO, SCA, WOA, and AVOA have shown great potential in addressing complex optimization problems. These algorithms have been applied to various applications, including robot exploration in challenging environments, to locate optimal or near-optimal solutions. The efficacy of these algorithms can be attributed to their ability to efficiently explore the search space, evade local optima, and converge towards the global optimum. Furthermore, these algorithms can handle diverse optimization problems, such as continuous, discrete, and mixed-integer optimization problems.

4. Hybrid Method

Several studies have explored the use of multi-robot systems for exploring unknown and cluttered spaces with the primary objective of efficient mapping and navigation. Previous studies have predominantly employed deterministic or meta-heuristic algorithms to optimize robot trajectories and minimize uncertainties. However, there is a lack of research on combining these techniques to consolidate their advantages and overcome their limitations.

Albina and Lee ^[19] proposed a hybrid algorithm that combines the Coordinated Multi-Robot Exploration Algorithm with the Grey Wolf Optimizer to optimize robot trajectories for exploration and mapping of the environment. Simulation results demonstrated that the hybrid algorithm outperformed the Coordinated Multi-Robot Exploration algorithm by enhancing the deterministic approach and achieving complete exploration and mapping of the environment. Another study by Gul et al. ^[20] proposed a new framework that combines the Coordinated Multi-Robot Exploration Algorithm with the Frequency Modified Hybrid Whale Optimization Algorithm to achieve optimal exploration and mapping of the environment. The proposed algorithm was found to outperform other contemporary optimization techniques.

Gul et al. ^[21] proposed a novel Aquila Optimization Algorithm for Multi-Robot space exploration in a barrier-filled environment. The proposed Coordinated Multi-Robot Exploration Aquila Optimizer (CME-AO) Algorithm demonstrated superior performance compared to contemporary algorithms such as conventional CME, CME Arithmetic Optimization Algorithm (CME-AOA), and Frequency Modified Hybrid Whale Optimization Algorithm (FMH-WOA). In another study, Gul et al. ^[22] introduced a Hybrid Stochastic Optimizer (HSO) that employs both deterministic CME and stochastic Arithmetic Optimization (AO) techniques for efficient multi-robot space exploration. The proposed algorithm is capable of enhancing the explored area and reducing the search time, leading to significant improvements in the exploration process.

Finally, Romeh and Mirjalili ^[23] introduced an innovative hybrid algorithm that merges the deterministic Coordinated Multi-Robot Exploration (CME) with the meta-heuristic Salp Swarm Algorithm (SSA) to enhance space search performance. The authors demonstrated through experimental results that the novel CME-SSA algorithm surpassed four other cutting-edge methods concerning exploration efficiency, encompassing metrics such as total area coverage, successful exploration rate, and time required to finish the exploration task. While the study’s strengths lie in the successful integration of CME and SSA, resulting in enhanced performance measures, it also faces limitations. These include the generalizability of the findings to various exploration scenarios and potential challenges related to scalability or computational constraints when implementing the method with larger robot teams or more expansive search spaces. Furthermore, the study’s experimental maps were limited to

20 m \times 20 m

, which raises concerns about the CME-SSA method’s performance in more complex and larger environments.

References

Chang, Y.; Ebadi, K.; Denniston, C.E.; Ginting, M.F.; Rosinol, A.; Reinke, A.; Palieri, M.; Shi, J.; Chatterjee, A.; Morrell, B.; et al. LAMP 2.0: A Robust Multi-Robot SLAM System for Operation in Challenging Large-Scale Underground Environments. IEEE Robot. Autom. Lett. 2022, 7, 9175–9182.
Alitappeh, R.J.; Jeddisaravi, K. Multi-robot exploration in task allocation problem. Appl. Intell. 2021, 52, 2189–2211.
Habibian, S.; Dadvar, M.; Peykari, B.; Hosseini, A.; Salehzadeh, M.H.; Najafi, F. Design and implementation of a maxi-sized mobile robot (Karo) for rescue missions. ROBOMECH J. 2021, 8, 1.
Dutta, A.; Roy, S.; Kreidl, O.P.; Boloni, L. Multi-Robot Information Gathering for Precision Agriculture: Current State, Scope, and Challenges. IEEE Access 2021, 9, 161416–161430.
St-Onge, D.; Levillain, F.; Zibetti, E.; Beltrame, G. Collective expression: How robotic swarms convey information with group motion. Paladyn, J. Behav. Robot. 2019, 10, 418–435.
Mir, I.; Taha, H.; Eisa, S.A.; Maqsood, A. A controllability perspective of dynamic soaring. Nonlinear Dyn. 2018, 94, 2347–2362.
Burgard, W.; Moors, M.; Stachniss, C.; Schneider, F. Coordinated multi-robot exploration. IEEE Trans. Robot. 2005, 21, 376–386.
Galceran, E.; Carreras, M. A survey on coverage path planning for robotics. Robot. Auton. Syst. 2013, 61, 1258–1276.
Wang, X.; Syrmos, V.L. Coverage path planning for multiple robotic agent-based inspection of an unknown 2D environment. In Proceedings of the 2009 17th Mediterranean Conference on Control and Automation, Thessaloniki, Greece, 24–26 June 2009; pp. 1295–1300.
Andries, M.; Charpillet, F. Multi-robot taboo-list exploration of unknown structured environments. In Proceedings of the 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Hamburg, Germany, 28 September–2 October 2015; pp. 5195–5201.
Mirjalili, S.; Mirjalili, S.M.; Lewis, A. Grey Wolf Optimizer. Adv. Eng. Softw. 2014, 69, 46–61.
Mirjalili, S.; Gandomi, A.H.; Mirjalili, S.Z.; Saremi, S.; Faris, H.; Mirjalili, S.M. Salp swarm algorithm: A bio-inspired opti-mizer for engineering design problems. Adv. Eng. Softw. 2017, 114, 163–191.
Abdollahzadeh, B.; Gharehchopogh, F.S.; Khodadadi, N.; Mirjalili, S. Mountain Gazelle Optimizer: A new Nature-inspired Metaheuristic Algorithm for Global Optimization Problems. Adv. Eng. Softw. 2022, 174, 103282.
Mirjalili, S. SCA: A Sine Cosine Algorithm for solving optimization problems. Knowl.-Based Syst. 2016, 96, 120–133.
Bonabeau, E.; Dorigo, M.; Theraulaz, G. Swarm Intelligence—From Natural to Artificial Systems; Oxford University Press: Oxford, UK, 1999.
Kennedy, J.; Eberhart, R. Particle swarm optimization. In Proceedings of the ICNN’95—International Conference on Neural Networks, Perth, WA, Australia, 27 November–1 December 1995; Volume 4, pp. 1942–1948.
Mirjalili, S.; Lewis, A. The Whale Optimization Algorithm. Adv. Eng. Softw. 2016, 95, 51–67.
Abdollahzadeh, B.; Gharehchopogh, F.S.; Mirjalili, S. African vultures optimization algorithm: A new nature-inspired metaheuristic algorithm for global optimization problems. Comput. Ind. Eng. 2021, 158, 107408.
Albina, K.; Lee, S.G. Hybrid Stochastic Exploration Using Grey Wolf Optimizer and Coordinated Multi-Robot Exploration Algorithms. IEEE Access 2019, 7, 14246–14255.
Gul, F.; Mir, I.; Rahiman, W.; Islam, T.U. Novel Implementation of Multi-Robot Space Exploration Utilizing Coordinated Multi-Robot Exploration and Frequency Modified Whale Optimization Algorithm. IEEE Access 2021, 9, 22774–22787.
Gul, F.; Mir, I.; Mir, S. Aquila Optimizer with parallel computing strategy for efficient environment exploration. J. Ambient. Intell. Humaniz. Comput. 2023, 14, 4175–4190.
Gul, F.; Mir, I.; Abualigah, L.; Sumari, P. Multi-Robot Space Exploration: An Augmented Arithmetic Approach. IEEE Access 2021, 9, 107738–107750.
El Romeh, A.; Mirjalili, S. Multi-Robot Exploration of Unknown Space Using Combined Meta-Heuristic Salp Swarm Algorithm and Deterministic Coordinated Multi-Robot Exploration. Sensors 2023, 23, 2156.

© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.

Upload a video for this entry

Information

Subjects: Robotics

Contributors MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :

Ali El Romeh

Seyedali Mirjalili

Faiza Gul

View Times: 265

Update Date: 20 Nov 2023

Table of Contents

Video Upload Options

Confirm