2.1. Classical approaches (CA)

Artificial intelligence (AI) and Heuristic techniques appeared recently to solve navigation problem for mobile robots whereas CAs were very popular for solving this problem long ago before. By using CAs to perform a mobile robot task, it was demonstrated that either a result could be obtained or does not exist. Cell Decomposition CD, Roadmap Approach RA, and Artificial Potential Field APF are some of the CAs which will be discussed.

Roadmap approach (RA): The Roadmap Approach, commonly known in literature as Retraction, Skeleton or Highway approach, is the strategy to navigate from the initial position to a desired position via the shortest path selected from a set of paths which are collision-free connections of area [Reference Choset and Burdick9]. The notion of nodes are used to define the robot optimal path. In literature, Voronoi and visibility graphs are two popular methods to develop a roadmap. The visibility graph method (cf. Fig. 2(a) [Reference Lulu and Elnagar37] connects the initial and the target position with nodes from the map. This path consists of the initial, target position, and vertices of polygonal obstacles. The Voronoi diagram (cf. Fig. 2) [Reference Choset, Lynch, Hutchinson, Kantor, Burgard, Kavraki, Thrun and Arkin38, Reference Takahashi and Schilling39, Reference Ó’Dúnlaing and Yap40] is based on the map division into tessellating polygons. The edges are defined by the use of points that are equidistant from the adjacent two points on the boundaries of the obstacle.

Figure 2. Roadmap Approach.

Figure 3. Cell Decomposition method.

A weak point of visibility graph is that the optimal paths are not safe as it collides with the vertices or even edges of obstacles. Voronoi diagrams are able to avoid this issue.

Cell decomposition (CD) approach: This approach is widely used for mobile robots path planning [Reference Conte and Zulli8, Reference Noborio, Naniwa and Arimoto41] and is based on space representation based on grids or cells (cf. Fig. 3). Then a connectivity graph is used to evolve from one cell to another to achieve a navigation of mobile robot. The space representative cells are labeled as pure or corrupted depending on the existence of obstacle or not. The optimal path is formed by a sequence of continuous pure cells from the initial position to the ending desired position [Reference Šeda42, Reference Regli43]. One important aspect in CD method is borders assignment between the cells which will differentiate between exact, approximate, and probabilistic CD approach. In excat CD method, the borders are defined as an environment structure function [Reference Barbehenn and Hutchinson44]. For approximate CD, the space decomposition is made as an approximation of the map [Reference Zhu and Latombe45]. And for probabilistic CD, the borders are defined as in the approximate CD but do not represent any physical meaning [Reference Lingelbach46].

Potential field (PF) approach: The Potential Field approach was introduced by Khatib [Reference Khatib10] in 1986 for mobile robot navigation. This methods takes into consideration the resultant force between two opposite attractive and repulsive forces. The Target and obstacles are acting like charged surfaces and the total potential creates the imaginary force on the robot. This generated force ensures the robot attraction towards the goal while keeping it away from the obstacle (cf. Fig. 4). The mobile robot reaches its desired position by following the negative gradient which allows obstacle avoidance. Many researchers applied this method for mobile robot navigation such as the work presented in refs. [Reference Garibotto and Masciangelo47, Reference Kim and Khosla48, Reference Borenstein and Koren49, Reference Ge and Cui50]. Donmez et al. [Reference Dönmez and Kocamaz51] used adaptive artificial potential field on acquired image based on vision system and combined a decision tree-based controller to ensure a safe mobile robotic system navigation in a static indoor environment.

Figure 4. Mobile robot navigation by PF approach [Reference Patle, G.Babu, Pandey, Parhi and Jagadeesh6].

One of the weakness points of Potential Field approach is getting trapped in local minima or being computationally intensive.

Other CAs: Other CAs exist in literature such as Subgoal Network (SN) [Reference Chen, Hwang and Sandros11] based on the use of a set of possible configurations to reach the goal from a starting position. Dijkstra’s Algorithm (DA) is also a classical algorithm used for path planning based on finding the shortest possible path within a cloud of nodes that represent spaces between obstacles [Reference Dijkstra52]. Rapidly Exploring Random Tree Method are developed to deal with an environment with obstacles and differential constraints. It is based on constructing in an incrementally decreasing way of the estimated gap of a selected arbitrarily point to the tree.

CAs appeared to be less performant in unknown and dynamic environment. It requires high computational cost to adapt the environment dynamics (changes) and for this it is not recommended for real-time implementation as they are dependent on the environment prior knowledge to generate an optimal path.

2.2. Heuristic approaches

Recently, HAs have gained more interest over conventional approaches thanks to their better efficiency for mobile robots navigation and control. HA algorithm have the advantage to take into consideration the robot environment uncertainties. HAs include genetic algorithm (GA), fuzzy logic (FL), neural network (NN), and other miscellaneous algorithms. These approaches are discussed below.

Genetic algorithm (GA): Introduced first by Bremermann [Reference Bremermann13] in 1958, GAs is a search-based optimization tool inspired from genetics and natural brain selection. The first use of these algorithms in the field of computer science was used first by Holland [Reference Holland53] in 1975. Recently its use is spread to a wide range of applications such as mobile robots navigation. It deals with optimization problems to maximize or minimize an objective function w.r.t given constraints. Mobile robots navigation control based on GAs has been introduced in ref. [Reference Shibata and Fukuda54] in a static environment. Simulation results for a simple specific obstacle shape (polygonal obstacle) have been presented. In case of unknown environment, GA are very robust and efficient real-time method which ensures processing of few data about the environment compared to CAs which are very slow for searching and optimization. Shing et al. [Reference Shing and Parker55] presented a real-time path planner using GA approach for mobile robot navigation. GA approach is used by Xiao et al. [Reference Xiao, Michalewicz, Zhang and Trojanowski56] for a navigation problem such as path planning and obstacle avoidance. The nonlinear environmental dead end navigation problem is addressed by ref. [Reference Kang, Yue, Li and Maple57] in uncertain areas. They developed an online training model to come out with the fittest chromosome that ensures obstacle collision free. In literature, scientists mostly worked on GA use for static environment navigation problems but navigation in dynamic environment with uncertainties has been proposed by Shi et al. [Reference Shi and Cui58].

Fuzzy logic (FL): For navigation problems including a high degree of uncertainty, complexity, and nonlinearity, FL algorithms are used. They were introduced by Zadeh [Reference Zadeh, Klir and Yuan59] in 1965 and then used in all areas of R&D. Data processing and classification, decision-making, image processing, pattern recognition, and control present some of these fields. The concept of the FL framework is built based on the noteworthy ability of people to make decisions based on processing perception-based information. It converts the human-supplied rules to its equivalent mathematical models. This simplifies the work of system designer and computer to extract valuable and exact information about the system performance way in real world and as consequence, it is used in mobile robot navigation and path planning. In ref. [Reference Raguraman, Tamilselvi and Shivakumar60], authors used FL controller to assist the sensor-based mobile robot navigation in an indoor environment. In ref. [Reference Omrane, Masmoudi and Masmoudi61], authors designed and implemented a trajectory tracking mobile robot controller using FL for indoor navigation.

Neural network (NN): the concept of artificial NN is based on simple and highly interconnected processing elements. The information is transferred by these elements based on their capabilities of dynamic state response to external inputs. NN architecture shown in Fig. 5 is presented by layers and interconnected nodes. These latter are an activation function. The input layer of the NN mechanism identifies the patterns which will be communicated to hidden layers for actual processing via a system of weighted connections. These layers communicate with the output layer in order to provide the required answer. What makes NN a useful method in mobile robot’s navigation problem are its very specific features such as generalization ability, massive parallelism, distributed representation, learning ability, and fault tolerance.

Figure 5. Architecture of NN [Reference Jinglun and Yuancheng62].

Janglova [Reference Janglová12] proposed a NN-based application for a wheeled mobile robot navigation in a partly undefined environment. He used two NN-based mechanisms for the development of a collision-free path. The first neural mechanism finds the free space using sensory data. The second NN finds a safe path by avoiding the nearest obstacle. Jinglun [Reference Jinglun and Yuancheng62] combined NN with Hierarchical Reinforcement Learning (RL) for optimal algorithm system. Experimental results of the proposed algorithm proved that it decreases the planning time, lowers the number of path steps, reduces the convergence time, and enhances the smooth as well as the movement capabilities of the robots.

Firefly algorithm (FA): Firefly algorithm, also known as the metaheuristics algorithm, has been introduced by Yang [Reference Xang63] in 2008 and was inspired from the fireflies flashing behavior. It is consisted of random states and general identification as trial and error of fireflies which is existing in nature. The firefly belongs to wing beetle family Lampyridae (commonly called lightning bug since they are able to produce light). The light is produced based on an oxydation process of Luciferin in the presence of enzymes Luciferase. This process of light production is known as bioluminescence. This light is used for mate selection, message communication, and sometimes to scare predators. The FA gained a lot of interest in the recent years as an optimization tool and is used in many engineering applications such as mobile robot navigation. Hidalgo-Paniagua et al. [Reference Hidalgo-Paniagua, Vega-Rodríguez, Ferruz and Pavón64] proposed a FA-based method for a mobile robot with fixed obstacle. They have accomplished the three elementary objectives of navigation which are: path length, smoothness, and safety. Firefly algorithms are very recent and have gained interest for mobile navigation problems. It is able to identify the best optimal path in short time which is very efficient. It also ensures safe navigation as the determined path may avoid all obstacles.

Particle swarm optimization (PSO): PSO, presented by Eberhart and Kennedy [Reference Eberhart and Kennedy14] in 1995, is a nature-based metaheuristic algorithm which adopts the social behavior of creatures such as fish schools and bird flocks. It is a fast growing optimization tool for solving the diverse problems of science and engineering. The PSO is based on mimicking social animal behavior but does not need any leader to reach the target. When a herd of animals goes to look for food, they go with one of the nearest members to food. Hence, the flock of animals reaches their required solution by their own communication strategy with the population members. The PSO algorithm consists of a group of members where each one represents a potential solution. Recently, PSO is commonly used for the mobile robot navigation. Tang et al. [Reference Tang, Li and Jiang65] discussed the mapping and localization problems of mobile robot navigation in the undefined environment by using a multiagent particle filter. PSO usage helped in calculation reduce and held more stable convergence characteristics.

Ant colony optimization (ACO): ACO is an algorithm presented by Marco Dorigo in 1992 [Reference Dorigo and Gambardella66]. It is a population-based approach developed to solve computational problems. This algorithm was inspired from the behavior of ants and its capability to find the best path to a food source from nest. Recently, the ACO is used to optimize mobile robots control for navigation and obstacle avoidance. Guan-Zheng et al. [Reference Guan-Zheng, Huan and Sloman67] have presented the ACO algorithms for mobile robots real-time path planning. The use of the ACO boosts the convergence speed, solution variation, computational efficiency, and dynamic convergence behavior when compared with other algorithms such as GA.

Reinforcement learning (RL): RL is an approach basically inspired from animal learning and which uses experience to determine the optimal decision-making plan from experience [Reference Zhu and Zhang68]. Its goal is to teach the robot how to act in its unknown surroundings by performing the most favorable Q-value function that commits the best results [Reference Altuntaş, Imal, Emanet and Öztürk69]. Deep Reinforcement Learning-based (DRL) navigation methods consist of determining the optimal plan to guide the robot to a target position while interacting with its surroundings [Reference Zhu and Zhang68]. An example of application of DRL for mobile robot end-to-end path planning method was presented in ref. [Reference Xin, Zhao, Liu and Li70]. A deep Q-network (DAN) is prepared and trained to estimate the robot’s state-action value function. In ref. [Reference Wang, Liu, Li and Prorok71], a Globally Guided Reinforcement Learning approach (G2RL) is introduced. G2RL is designed to answer the multirobot trajectory planning issues. Experiments proved that it demonstrates excellent generalization and performs likewise the fully centralized state of the art standards. Another DRL-based proof of concept for real autonomous robot navigation was introduced in ref. [Reference Surmann, Jestel, Marchel, Musberg, Elhadj and Ardani72]. It uses NN and combines a 2D laser scanner with a 3D-RGBD camera to produce needed network inputs.

Bio-Inspired Learning Control Approach (BILCA): the BILCA presented in ref. [Reference Mitić and Miljković73] is a novel approach dedicated to the evaluation of robot motion trajectories and visual control commands and it is based on the Learning from Demonstration (LfD) framework. LfD facilitates knowledge transmission from the guiding human to the robot. It depicts a group of supervised learning where the behavior is described as pairs of states and actions [Reference Argall, Chernova, Veloso and Browning74]. Two phases are involved in BILCA: (1) actuator commands are learned through Firefly Algorithm (FA) and demonstrations of desired behavior, and (2) real-world experiment used to evaluate the acquired wheel commands. This method merges metaheuristic method together with the LfD framework. This integration has several benefits: (1) robot motion persists uninterrupted even-though the existence of feature outliers, changing scene illumination, or image noise, (2) artificial markers in the environment are not required for the working of BILCA for vision-based control, and (3) proposed hybrid scheme resolves the absence of the homography plane. Despite these advantages, BILCA still has few limitations. First, the two phases of the LfD framework, learning and reproduction, cannot be executed at the same time. Gathering group of desired trajectories to learn and learning of actuator commands are essential in order to start the second phase. Second, the complexity of trajectory to generate, number of demonstrations of trajectories, algorithm population and the whole iteration amount, make the learning algorithm time-consuming.

Other algorithms: Many researchers gave different intelligent techniques to perform the task of mobile robot navigation in various environmental situations such as Shuffled frog leaping algorithm [Reference Eusuff and Lansey75, Reference Ni, Yin, Chen and Li76, Reference Hidalgo-Paniagua, Vega-Rodríguez, Ferruz and Pavón77], Cuckoo search algorithm [Reference Mohanty and Parhi78, Reference Mohanty and Parhi79], Artificial bee colony algorithm [Reference Karaboga80, Reference Contreras-Cruz, Ayala-Ramirez and Hernandez-Belmonte81, Reference Saffari and Mahjoob82, Reference Ma and Lei83], InvasiveWeed Optimization [Reference Mohanty and Parhi84, Reference Sengupta, Chakraborti, Konar and Nagar85, Reference Ghalenoei, Hajimirsadeghi and Lucas86], Harmony Search Algorithm [Reference Kundu and Parhi87, Reference Tangpattanakul, Meesomboon and Artrit88], Bat Algorithm [Reference Guo, Gao and Cui89, Reference Ghosh, Panigrahi and Parhi90, Reference Wang, Chu and Mirjalili91], Differential Evolution Algorithm [Reference Chakraborty, Konar, Chakraborty and Jain92, Reference Deyun93, Reference Parhi and Kundu94], reactive obstacle avoidance based on boundary following using sliding mode control [Reference Savkin and Wang95], collision avoidance based on geometric approach [Reference Thanh, Phi and Hong96, Reference Thanh and Hong97], and many more.

Patle presented a statistical comparison review of the use of the two approaches [Reference Patle, G.Babu, Pandey, Parhi and Jagadeesh6] in mobile robotics. Results resumed in Fig. 6 are based on the analysis of the percentage of published papers for both CAs and HAs.

Figure 6. Development of mobile robot navigation approaches. [Reference Patle, G.Babu, Pandey, Parhi and Jagadeesh6].

CAs have many limits such as the lack of decisive information about external environment, the limited computational capabilities, the need of an accurate sensing mechanism for real-time navigation, and others. Thus, the uncertainty and unreliability of these CAs makes them not convenient enough for real-time systems. Yet, HAs came up as a better solution to repel these restraints notably the real-time navigation problems. They are more efficient and most used for navigation in an undetermined environment.

3.1. Centralized control architecture versus distributed control architecture

Centralized control [Reference Adouane26, Reference Kanjanawanishkul27] is often synonym to the Top-Down approach. It is based on a single controller relocated from the physical structure of a robot that processes all the information needed to achieve the desired control objectives. Thus in a centralized control, both the individual member and the whole group can improve superior performance and optimal decisions. This architecture implies a global knowledge of each element of the system. It requires a high computational power and a massive information flow. Although, it is not robust due to the dependence on a single controller.

In contrast with centralized control, in a decentralized control [Reference Adouane26, Reference Kanjanawanishkul27], often synonym for the Bottom-Up approach, each element of the system has its own controller and is completely autonomous in the decision process. This implies a reduced number of communicated signals and information. Decentralized controllers are then more flexible and require less computational effort. It is also needed to provide some degrees of centralization for human operator for programming tasks and to monitor the system.

Twinning both control architectures makes a hybrid architecture where a central processor applies high-level control over autonomous entities.

For multimobile robots navigation, the main used approaches are discussed in the following section.

3.2. Navigation in formation

Formation control is more and more considered in recent literature [Reference Raghuwaiya, Singh and Vanualailai28, Reference Sadowska, van den Broek, Huijberts, van de Wouw, Kostić and Nijmeijer30, Reference Beard, Lawton and Hadaegh98, Reference van den Broek, van de Wouw and Nijmeijer29, Reference Benzerrouk, Adouane, Lequievre and Martinet31, Reference Peng34, Reference Consolini, Morbidi, Prattichizzo and Tosques99, Reference Wu and Jiang100] and is classified into three main approaches: the behavior-based approach, the leader–follower approach, and the virtual structure approach.

In the behavior-based approach [Reference Vilca, Adouane, Mezouar and Lebraly101, Reference Benzerrouk, Adouane, Lequievre and Martinet31, Reference Balch and Arkin102], primitives for each element is designed (e.g. obstacle avoidance, formation keeping, target seeking, trajectory tracking). Then, a more complex motion patterns can be generated by using a weighted sum of the relative importance of these behaviors and the interaction of several robots. Although, the main drawback of this approach is the complexity of the dynamics of the group and as a consequence, the desired formation configuration cannot be guaranteed.

Leader–follower approach [Reference Raghuwaiya, Singh and Vanualailai28, Reference Peng34, Reference Ghommam, Mehrjerdi and Saad103, Reference Consolini, Morbidi, Prattichizzo and Tosques99, Reference Ren and Sorensen104, Reference S.-C., D.-L. and G.-J.105] is a strategy in which a robot will be the leader while others act as followers. The main advantage of using this approach is the reduction of the strategy to a tracking problem where the stability of the tracking error is shown through standard control theoretic techniques: the leader will aim to track a predefined trajectories and the followers track its transformed coordinates with some prescribed offset. A disadvantage of this approach is that there is no feedback from followers to the leader so that if a follower is perturbed then the formation cannot be maintained which involve a lack of robustness to this strategy.

The final approach is Virtual-structure (VS) [Reference Hichri, Adouane, Fauroux, Mezouar and Doroftei17, Reference Hichri, Fauroux, Adouane, Doroftei and Mezouar16, Reference van den Broek, van de Wouw and Nijmeijer29, Reference Sadowska, van den Broek, Huijberts, van de Wouw, Kostić and Nijmeijer30, Reference Mehrjerdi, Ghommam and Saad106] in which the entire formation is considered as a rigid body and the notion of hierarchy does not exist. The control law for each entity is derived by defining the VS dynamic and then translated to the motion of the VS into the desired motion of each vehicle. The main advantages of this approach are its simplicity to prescribe the coordinate behavior of the group and the maintenance of the formation during maneuvers. However, the possible application will be limited if we aim to maintain the same VS especially when the formation shape needs to be frequently reconfigured.

In ref. [Reference Raghuwaiya, Singh and Vanualailai28], authors presented a control law for formation control for the flocking problem. A kinematic model for a car-like system was developed and a modeling for attraction to a target was achieved considering the obstacles avoidance problem. The proposed control law was developed based on a defined Lyapunov function. It was validated by simulation results. In refs. [Reference van den Broek, van de Wouw and Nijmeijer29, Reference Sadowska, van den Broek, Huijberts, van de Wouw, Kostić and Nijmeijer30, Reference van den Broek, van de Wouw and Nijmeijer107], the different approaches toward cooperative control of mobile robots were introduced and the aim was to develop and design a virtual structure controller using the so called mutual coupling terms between robots by introducing coupling parameters relating the robots in the control law function.

In ref. [Reference Benzerrouk, Adouane, Lequievre and Martinet31], a work combining behavior-based approach and virtual structure method to build a distributed control architecture is proposed. Obstacle avoidance and attraction to a dynamic target were considered (cf. Fig. 7). Unicycle robot model was used and navigation in formation problem was modeled to make a control law architecture based on Lyapunov function which was validated by simulation and experiments.

Figure 7. Triangular Virtual structure navigation using Khepera mobile robots [Reference van den Broek, van de Wouw and Nijmeijer29].

In ref. [Reference Kambayashi, Yajima, Shyoji, Oikawa and Takimoto108], a bio-inspired formation control algorithm for swarm mobile robots is presented based on ant agents (AA) and pheromone agents (PA). The communication is based on migration of PAs generated by the other AAs to drive and attract robots to compose the desired objective formation. A local information based on vector values linked to the PA is generated and specifies the desired locations to be occupied by the neighboring robots. Figure 8 illustrates the proposed algorithm.

Figure 8. A1 generates a pheromone agent and attracts A2 with its robot R2 [Reference Kambayashi, Yajima, Shyoji, Oikawa and Takimoto108].

In ref. [Reference Peng34], the leader–follower formation control for nonholonomic mobile robot was considered based on bioinspired neurodynamics-based approach. In this article, trajectory tracking for a single robot was extended to formation control based on backstrepping technique in which the follower can track in real time the leader by the proposed kinematic controller. In backstepping control, it was used the derivative of the reference orientation instead of the reference orientation. This technique ensures the tracking controller stability and simplicity. As a typical biological model, the shunting model was adopted for this work. Autonomous navigation of vehicle in an urban environment was considered in ref. [Reference Vilca, Adouane, Mezouar and Lebraly101]. This article presents a control law based on a novel definition of control variables and Lyapunov function based on the distance error, orientation, and a new parameter related to angle between robot and target positions. This control law was designed for point stabilization (reach a point with a certain orientation) and trajectory tracking problem (track a time parametrized reference). A modeling for tricycle was presented and the control law was developed based on Lyapunov function definition. This work was validated by simulation and experimentation. In ref. [Reference Ghommam, Mehrjerdi and Saad103] presents works for leader–follower motion coordination. Trajectory tracking controller was designed to make followers track a virtual vehicle using NN approximation in combination with backstepping and Lyapunov direct design techniques. In ref. [Reference Consolini, Morbidi, Prattichizzo and Tosques99] as well the leader–follower formation problem was studied and a control law was developed in which the control input were forced to satisfy suitable constraints between robots and which must be respected to maintain the desired formation. In ref. [Reference Ren and Sorensen104], authors presented a distributed formation control architecture that accommodates an arbitrary number of group leaders and arbitrary flow among vehicles. Authors in ref. [Reference S.-C., D.-L. and G.-J.105] presented the problem of modeling and controlling leader–follower formation control of mobile robots and developed a controller based on feedback linearization and a sliding mode compensator to stabilize the overall system including the internal dynamics.

In ref. [Reference Kim and Tsiotras109], various time-varying and time-invariant controllers for unicycle mobile robots were presented and implemented on Khepera robots. In ref. [Reference Deng, Inoue, Sekiguchi and Jiang110], the problem of controlling two-wheeled mobile robots is considered and a feedback control scheme is able to cope with dynamic environments. In ref. [Reference Mehrjerdi, Ghommam and Saad106] considered the creation of algorithm for a group of robot coordination. It employs coordination and trajectory following techniques. The developed control law was based on Lyapunov technique and graph theory embedded in the virtual structure. In ref. [Reference Pourboghrat111], it was considered the design of point to point control algorithm to drive a robot from any arbitrary position to another position. The control variables are derived using Lyapunov’s stability technique. In ref. [Reference Kanayama, Kimura, Miyazaki and Noguchi112], a new control law using an appropriate Lyapunov function was presented. The model of unicyle robot and the configuration of error were modeled to finally deduce a control law and to prove the stability of the Lyapunov function.