1. Introduction
Path planning is a field of robotics that solves the optimal route for a robot to travel from one point to another, its types include shortest path planning for efficient point-to-point motion [Reference Chembuly and Voruganti1, Reference Luo, Li, Liu and Liu2] and coverage path planning (CPP) that determines the most efficient path to systematically cover an entire area, ensuring least cost value [Reference Coelho, Pinto, Carvalho and Marcato3]. CPP becomes particularly crucial in scenarios where exhaustive exploration is required, such as in vacuum cleaning [Reference Pham, Moore and Truong4], lawn mowing [Reference Huang, Lian, Chen, Wu and Chen5], window glass cleaning [Reference Hong, Yoo, Joo, Kim, Hwa and Seo6], planetary exploration [Reference Endo, Endo, Nagaoka and Yoshida7], and underwater exploration [Reference Karapetyan8]. All of the aforementioned applications need to cover the entire accessible area while avoiding obstructions.
Regular cleaning in hospitals, offices, clinics, etc. is a crucial activity for reducing the risk to the safety of people. To reduce the workload of the cleaning team and the risk of direct contact with disinfectants, autonomous mobile robots would be the preferred option. Furthermore, a mobile robot can perform the cleaning task more precisely and cost-effectively than a human worker. In recent years, numerous researchers have proposed several methodologies in this domain. Survey of various methods of CPP is provided in ref. [Reference Tan, Mohd-Mokhtar and Arshad9–Reference Ahmadi, Kebriaei and Moradi11]. Based on cellular decomposition, CPP approaches can be categorized into two groups: (1) the exact cellular decomposition methods and (2) the grid-based methods. The exact cellular decomposition techniques break the entire environment into smaller sub-regions. Each sub-region is free from obstacles and is covered using simple algorithms such as zigzag, spiral, etc. Oksanen et al. [Reference Oksanen and Visala12] proposed a CPP algorithm based on the trapezoidal decomposition method for agricultural applications. A disadvantage of trapezoidal decomposition is that it produces numerous sub-regions that may not be necessary. Choset et al. [Reference Choset and Philippe13, Reference Howie, Acar, Rizzi and Luntz14] proposed boustrophedon cellular decomposition which is similar to the trapezoidal decomposition, with the exception that it only considers the vertices of an obstacle where a vertical segment can be drawn both above and below the vertex [Reference Bähnemann., Lawrance, Chung., Pantic, Siegwart and Nieto15]. In cellular decomposition methods, there is some overlapping generated in the path, which cannot be omitted as there is no guarantee that the endpoint of a cell is adjacent to the starting point of the next cell. Changxin et al. [Reference Huang, Li, Xiao, Liang and Han16] used an artificial potential field algorithm to solve a CPP problem and find a path that captures each environment cell. The method underperforms when covering the area near obstacles, and when the robot is trapped in a deadlock, it falls into the local optimum. Pham and Lam [Reference Pham and Lam17] presented a CPP problem based on a breadth-first search to determine the optimal path for a cleaning robot in a static environment. The method is simple to implement but struggles to find the optimal solution and consumes large memory in a large search space. Zengyu et al. [Reference Cai, Li, Gan, Zhang and Zhang18] proposed an enhanced A* algorithm for an autonomous mobile robot and studied the CPP algorithm. The method does not guarantee the optimal path and is difficult to implement in an environment with complex shapes of obstacles. E. Gonzalez et al. [Reference Gonzalez, Alvarez, Díaz, Parra and Bustacara19] published the backtracking spiral algorithm (BSA), in which the robot follows a wall to cover the previously unexplored region. Mitschke et al. [Reference Mitschke, Uchiyama and Sawodny20] proposed the turn-away starting point (TASP) algorithm, which reduces the number of turns on a path by proceeding straight until an obstacle or previously visited cell is encountered. The paths obtained by methods [Reference Gonzalez, Alvarez, Díaz, Parra and Bustacara19, Reference Mitschke, Uchiyama and Sawodny20] are not optimal, and they can be improved using population-based methods such as a genetic algorithm (GA). Batsaikhan et al. [Reference Dugarjav, Lee, Kim, Kim and Chong21] used the spatial cell diffusion (SCD) algorithm to cover the entire free region of a rectilinear workspace. José Prado et al. [Reference Prado and Marques22] published a paper in which the authors used oriented rectilinear decomposition (ORD) to traverse every accessible area. The algorithms in refs. [Reference Dugarjav, Lee, Kim, Kim and Chong21, Reference Prado and Marques22] employed the exact cell decomposition method to split the workspace into cells. Y Gabriely and E Rimon [Reference Gabriely. and Rimon23] presented a work based on spanning tree coverage (STC) approaches to solve the CPP of a mobile robot. The method enables the computation of a spanning tree graph and the robot visits each cell once in a given free space by following the spanning tree graph. K R Guruprasad [Reference Guruprasad24] reported an algorithm that is an extension of the spanning tree coverage (STC) algorithm for mobile robot coverage. The goal of the algorithm is to maximize the coverage area specifically to cover the sub-cells that are partially occupied by obstacles. K. R. Guruprasad and T. D. Ranjitha [Reference Guruprasad and Ranjitha25] used cell permeability-based coverage algorithm to solve a CPP problem of a mobile robot. The performance of the algorithms in refs. [Reference Guruprasad24, Reference Guruprasad and Ranjitha25] is compared to spiral and full STC-based algorithms, and a better coverage area is achieved with lower overlap. VG Nair and KR Guruprasad [Reference Nair and Guruprasad26] studied the CPP of multi-robots based on the hybrid Voronoi partition method. The authors combined geodesic-distance-based Voronoi partition and Manhattan-distance-based Voronoi partition to solve the optimum path with non-overlapping at the grid level. The CPP of a mobile robot based on a GA has been studied in refs. [Reference Ryerson and Zhang27–Reference Schafle, Mohamed, Uchiyama and Sawodny29]. Schafle et al. [Reference Schäfle, Mitschke and Uchiyama30] reported a CPP problem for grid-based environmental representation based on a hybrid genetic algorithm (HGA). They utilized TASP and BSA to conduct a local search if a path generated by crossover or mutation did not provide a feasible solution. Sharma and Voruganti [Reference Sharma and Voruganti31] published a work on the CPP of a mobile robot using different approaches of preference-based MOO methods. The authors adopted two objective functions which are minimization of energy consumption and maximization of coverage area and conducted case studies in two different environments. Shang et al. [Reference Gao-gao., Liu, Zhu and Jian32] solved a multi-objective CPP problem using an improved GA. The objective functions of the problem are the length of the driving path, the elevation height, and the number of turns. Using predefined weighting factors, the authors converted the multi-objective problem into a single-objective problem and obtained an optimal solution. Sharma and Voruganti [Reference Sharma and Voruganti33] published a similar work based on GA where the authors converted the MOO problem into an SOO problem using the weighted sum method. The results show that the completion time of the task is less than that of the constraint optimization technique. Almost all the methods except a few have focussed on finding a path to cover the area. There can be more than one path for a given environment that covers the entire area. The question of the optimal path arises in such cases. The interest of the present work is to find such an optimal path to multiple-optimal criteria (like energy consumption, length of the path, etc). This led to posing the problem as a MOO problem and finally providing a set of solutions instead of one feasible or optimal solution.
Work floors like offices and clinics are more likely static environments and it is required to generate multiple path plans according to user preference, which may be less energy consumption and effective coverage of the area. This paper presents a modified Non-dominated Sorting Genetic Algorithm-2 (NSGA-II) for solving the CPP problem and generating Pareto-optimal solutions for floor-cleaning by a mobile robot in a known environment with convex and non-convex-shaped static obstacles. The environment is expected as input for the proposed CPP method, which can be obtained using a camera or sensors. The environment is discretized into cells using a grid-based method and the size of the cell depends on the dimensions of a circular robot. The problem in this research belongs to the field of discrete optimization. In this research, every feasible solution obtained from each iteration satisfies three conditions: (1) the robot must cover all the free cells (100% coverage), (2) the robot avoids moving along the cell which is fully or partially occupied by any obstacle, and (3) the robot cannot skip a neighboring free cell while moving along a direction. The total distance traveled and the total number of turns taken by the robot to complete the task are employed as the two objective functions in this paper. Using an energy equation that will be explained in Section 3.6, the paths obtained by the proposed method are used to calculate the energy consumed by the robot. Among the Pareto-optimal solutions produced by the proposed method, an optimal solution is selected based on the minimum energy consumption (higher-level information). The optimum solution is compared to the solution presented in previous publications. The proposed algorithm’s optimal solution outperformed the existing results. The remaining sections are organized as follows: In Section 2, environment modeling and problem formulation are presented. The proposed method is presented in Section 3. In Section 4, results and discussion are presented. The results and future scope are discussed in Section 5.
2. Environment modeling and problem formulation
2.1. Environment modeling
To facilitate the movement of the mobile robot, workspace W is discretized into cells of a square grid. The area of each square cell in the working environment is equivalent to the area covered by the mobile robot. When a robot passes through a cell, it is considered that the cell is completely occupied by the robot. Each cell, C, is either completely occupied by an obstacle, C obs, or completely free of an obstacle, C free. The free cells and obstacle cells are represented by white and black colors in the grid map, respectively, as shown in Fig. 1. The robot is permitted to move in C free. C free cells that the robot has visited are known as visited cells C vis, whereas C free cells that the robot has not visited are known as unvisited cells C unv. The starting point of the robot for a given environment is signified by P start, which is denoted by green color as given in Fig. 1. Therefore, the initial and final positions are identical. Each cell is labeled with an integer value, beginning with the left bottom corner cell, which is assigned as integer “1” as shown with green color in Fig. 1(a). These integers are termed as decision variables for the problem in this work. The mobile robot considered in this study can only move in four directions. Fig. 1(b) illustrates the direction along which the robot can move by solid black lines (forward, backward, leftward, and rightward).
(a) An environment with decision variables, (b) Possible four directions of motion of a mobile robot.
2.2. Problem formulation
The problem is to find a path, p, which is a set of connected sequence cells (p i) from the start to the goal position. When C unv = Φ, where Φ is an empty set, the robot has finished covering the environment, and it moves back to the P start. The proposed algorithm creates a set of feasible solutions or paths in each iteration. The fitness evaluation is carried out after a path has been generated to determine the quality of the path. The two objectives of the proposed algorithm are (1) the total distance traveled by the robot and (2) the number of turns it makes (left, right, and U-turns). For each iteration of the algorithm, these two objectives are minimized in order to lower the amount of energy consumed by the robot.
3. Proposed method
The GA is an evolution-based algorithm that operates on the survival of the fittest principle. Deb et al. [Reference Deb, Pratap, Agarwal and Meyarivan34] developed the NSGA-II algorithm, which is an extension of GA to solve the MOO problem. A flowchart of the proposed method (modified NSGA-II) is illustrated in Fig. 2. This paper applies the modified NSGA-II algorithm to solve the CPP problem of a mobile robot. Moreover, a discrete optimization approach is adopted as the robot can only move to neighboring cells which are discretized using a grid-based method. The following notations are used in this paper to represent the proposed method. A chromosome is a single feasible solution that is a combination of the decision variables, and each bit of the chromosome is known as a gene or a decision variable. The set of solutions generated by each iteration is referred to as the population. Previous solutions that produce new solutions are termed as parents, and the new solutions are regarded as offspring. Unlike a continuous optimization problem, regular crossover and regular mutation do not guarantee to provide a feasible solution in the case of a discrete optimization problem. Hence, the crossover and mutation are modified by using TASP and A* algorithms. In the proposed method, the next generation of the population is obtained from the previous generation by following five steps, namely tournament selection, modified crossover, modified mutation, non-dominated sorting, and crowding distance sorting. It is considered that the solutions of the most recent generation represent the Pareto-optimal solutions.
Flowchart of the modified Non-dominated Sorting Genetic Algorithm-2 method.
3.1. Chromosome design
A gene in a chromosome signifies a cell traversed by a mobile robot in the environment depicted in Fig. 3. The solid black line in Fig. 3(a) represents the path traced by the robot in its environment. Fig. 3(b) demonstrates the arrangement of genes in the chromosome according to the path. The size of chromosomes is proportional to the distance traveled by the robot. Hence, the number of genes present on a chromosome may be the same or different from that of another chromosome.
(a). The path covered by a robot. (b). Chromosome design of the path.
3.2. Initialization
The initial paths belong to the first parents of the proposed method. The initial paths must possess two properties: (1) a wide variety of initial paths, and (2) the initial paths must already have good fitness values. For the first property to be satisfied, a large number of random paths are generated. In addition to random paths, four distinct methods (Spiral, Zigzag, TASP, and BSA) [Reference Choset and Philippe13, Reference Howie, Acar, Rizzi and Luntz14, Reference Gonzalez, Alvarez, Díaz, Parra and Bustacara19, Reference Mitschke, Uchiyama and Sawodny20] are employed to generate initial paths that satisfy the second property.
Fig. 4 shows the initial paths generated by the four different approaches in an environment. In the figure, the black solid line and the red solid line represent the non-repeated path and the repeated path, respectively, covered by a mobile robot. After the robot has traversed every accessible cell, it moves back to the starting point. The black dotted line and red dotted line indicate the non-repeated and repeated paths that traversed back to the starting point. When the robot is surrounded by visited neighboring cells and obstacles, the A* algorithm is used to traverse the robot to the nearest unvisited cell [Reference Wang, Lou, Jing, Wang, Liu and Liu35]. When the robot has completed the CPP, the A* algorithm is used to return it to the starting point.
Path generated by (a) turn-away starting point algorithm method, (b) backtracking spiral algorithm method, (c) Spiral method, (d) Zigzag method.
3.3. Fitness functions
The quality of the path is determined by the fitness functions of the proposed method. This paper employs two objective functions: (1) the distance traveled by the mobile robot, f 1, and (2) the number of turns by the robot, f 2. The mathematical formulation of the two objective functions is explained below.
3.3.1. The total distance traveled by the robot
The Manhattan distance method is employed to determine the total distance, f 1, covered by the robot as shown in equation (1). It is the sum of the absolute differences between the corresponding coordinates of two points in a grid.
\begin{equation}f_1 = \sum _{i = 1}^{{N_{gc}} - 1}\;\left( {\left| {{x_{i + 1}} - {x_i}} \right| + \left| {{y_{i + 1}} - {y_i}} \right|} \right) \end{equation}
where
$N_{gc}$
is the number of waypoints or positions visited by the robot. The position of the robot at i th waypoint is represented by p i(x i,y i).
3.3.2. Counting total turns and total U-turns
The number of turns (T) and U-turns (U) made by a robot during coverage path planning are calculated using the current, previous, and next positions of the robot, i.e. p i, p i-1, and p i + 1. There are only two types of turns possible i.e. either ±90 or 180 degrees turn because the robot considered in the study can move only in four directions (Fig. 1(b)).
The energy required for 180-degree turning is higher compared to 90-degree turning. Hence, the effective number of turns, f 2, is calculated by,
\begin{equation}\textrm{f}_2 = \textrm{T} + \textrm{w} \times \textrm{U}\end{equation}
where is w = 1.5 with an approximation that a U-turn takes 50% more energy than a 90-degree turn.
The problem is to minimize two objective functions f 1 and f 2. The constraint of the problem is 100% coverage of an entire free area. The MOO problem is stated as,
\begin{equation}\begin{array}{lll} &&{\rm Minimize}\ \textrm{f} = [\textrm{f}_1\quad \textrm{f}_2]\\[3pt] {\rm Subject\;to}:&&\\[3pt]&& \textrm{p}_{\textrm{i}}\;{\rm in}\;\textrm{C}_{\rm vis} \in \textrm{C}_{\rm free},\\[3pt] && \textrm{C}_{\rm unv} = \Phi. \end{array}\end{equation}
For example, the path shown in Fig. 5, f 1 = 24 and f 2 = 7 + 1.5 × 1 = 8.5. Hence, the values of the objective functions for the MOO problem are written as f = [24, 8.5].
Path produced by a random approach.
3.4. Operators of NSGA-II
Reproduction, mutation, and the survival of the fittest are the operators of natural evolution. In the proposed method, crossover, mutation, selection, non-dominated sorting, and crowding distance are equivalent to the natural operators. The operators are discussed in detail in the following sections.
3.4.1. Selection
Selection is the process of choosing parents to produce offspring for the next generation through other GA operators. Selecting only the best chromosomes in each generation may result in premature convergence. Therefore, it is essential to select parents with the most advantageous as well as diverse chromosomes.
This method employs tournament selection to achieve the desired chromosome diversity and convergence rate. In this method, a number of parents, (h), are selected at random from the entire population of chromosomes. The fittest parent is selected and added to a mating pool. The procedure of selecting parents and determining the optimal chromosome is repeated until the size of the mating pool matches that of the initial population. This method provides a chance for weaker chromosomes to be selected from the parent population and appends to the mating pool, as the set of parents is always different and is chosen at random.
3.4.2. Modified crossover for discrete optimization
The crossover operator works similarly to reproduction in nature, with parents mating to generate offspring. In this paper, a modified two-point crossover is employed to generate two offspring from two parents. Because, a regular two-point crossover of traditional genetic algorithm, TGA used in case of a continuous problem might not generate an offspring that consists of genes that are neighboring to each other and does not provide a feasible path due to the robot kinematics.
Fig. 6 depicts an example of a 3-by-3 simulation environment without any obstacles. Two parents P1 and P2 are chosen at random, and their paths and chromosomes are depicted in Fig. 6(a). Two random cutting points i and j where i < j are selected, for example, i = 4 and j = 6. A locus point plocus1 is determined as the i th element of p 1 and a vector O 1 is generated containing the elements from the first index to the (i - 1)th index of p 1, as shown in Fig. 6(b). The first occurrence of plocus1 is extracted from the second parent p 2 and the index k is assigned to it. As shown in Fig. 6(c), the vector O1 is modified by appending the elements from the k th index to the last element of P 2. The number of elements (n = 9) in vector O1 is determined and j is replaced with n if n < j; otherwise, the value of j is kept unchanged. Another locus point p locus2 is determined as the j th element of O1. The elements from index j to the last element of vector O1 are deleted as shown in Fig. 6(d). The first occurrence of p locus2 from p 1 is extracted and its index is labeled as r. As shown in Fig. 6(e), the elements of p 1 are appended from the r th index to the last element to the vector O1. The path generated by the genetic offspring O1 is depicted in Fig. 6(f), but the solution is not feasible.
Example of modified crossover.
Since such offspring members may not be feasible (i.e., coverage is not 100%), they are further appended by using TASP and A* algorithms. This entire crossover process is different from continuous optimization in the sense that here chromosome is a set of number of cells representing the path. The TASP and A* algorithms are employed to modify and transform it into a feasible solution O1’. The TASP algorithm enables the robot to traverse all free cells, as shown in Fig. 6(g). A star algorithm is applied to return the robot to its charging station after it has traversed all accessible cells, as depicted in Fig. 6(h). The same procedure is applied to develop the second offspring O2’. Table I depicts two parents and offspring produced by crossover and further modified with TASP and A* algorithms.
Example of a regular and improved crossover operator.
3.4.3. Modified mutation for discrete optimization
A probability factor called p m determines whether a mutation can be used. A mutation is a process in which changes are made to the chromosome to create a new solution to make the population more diverse. Since the problem is based on discrete optimization, a regular mutation of GA, which randomly replaces a gene, does not provide a feasible path. In this paper, a modified mutation is implemented to generate a feasible offspring from a parent, which includes a regular mutation followed by an improvement using the TASP and A* algorithms. A gene with an index of m from a parent chromosome is chosen at random. The selected gene is replaced by another gene which is neighboring to the gene with index m-1. All the genes from the chromosome following the index m are removed. The TASP technique is applied to allow the robot to pass through the remaining unvisited cells, and the A* algorithm is applied to return the robot to the charging position.
Table II illustrates an example where m = 5. Gene (5) with index m is replaced at random by another neighboring gene (9) of gene (6) with index m-1 as shown in bold. The TASP algorithm is applied to generate the path to cover the remaining unvisited cells, which are represented by the underlined genes in Table II, to complete the CPP process. The A* algorithm is applied to move the robot to the charging position or gene (1), which is indicated in italics.
Example of the mutation operator.
3.4.4. Merging
In this paper, the number of individuals in each generation, Npar, is selected as 150. Where the number of offspring generated through crossover, Onc, and mutation, Onm, depends on the pc and pm, respectively. The entire population of parents, Npar, and offspring through crossover, Onc, and mutation, Onm, are combined to form a new population. This newly formed population is known as the merged population.
3.4.5. Sorting operators of NSGA-II
Non-dominated sorting (NS) is a key component of the proposed method that is used to find non-dominated solutions in merged populations based on the dominance concept and to rank them accordingly. The best solutions are represented in the first-rank fronts and they are non-dominated by any feasible solution. Likewise, the second-rank fronts represent the second-best solutions that are only dominated by the solutions in the first-rank fronts. The crowding distance sorting (CDS) method of the proposed algorithm is used to maintain a diverse set of solutions in the population and enable the algorithm to efficiently explore the multi-objective search space. The concepts of NS and CDS were explained with examples in ref. [Reference Deb, Pratap, Agarwal and Meyarivan34].
3.5. Termination
The termination condition of the proposed algorithm is either a predefined fixed number of generations or the existence of desired solutions. In this study, the termination condition is determined by a predefined number of generations. However, if all the solutions of three consecutive generations remain unchanged before the maximum generation, the process is terminated.
Motion types and energy.
Energy parameters and value.
3.6. Calculation of energy
The value of the objective functions: total distance traveled by the robot, f1 and the total number of turns by the robot, f2, which are obtained from the optimal solutions of the proposed algorithm, are used to determine the energy consumption by the robot. The total energy consumption is calculated using equation (4) and data obtained from [Reference Schäfle, Mitschke and Uchiyama30] for a differential drive robot. Table III shows energy consumption for each type of motion. The energy parameters and energy values in joules are provided in Table IV [Reference Schäfle, Mitschke and Uchiyama30].
\begin{align}J=\left(J_{acc}+J_{s}\right)+2J_{s}n_{s}+\left(J_{dec}+J_{t}+J_{acc}\right)n_{t}+\left(J_{dec}+J_{ut}+J_{acc}\right)n_{ut}+(J_{dec}+J_{t})\end{align}
In equation (4), nt and nut represent the number of turns (right and left) and number of U-turns taken by the robot respectively whereas ns = Ngc – 1 – nt – nut, is the number of straight motions traversed by the mobile robot. Js represents half the energy consumption by the robot moving along a straight motion. Jacc and Jdec signify the energy required to accelerate and decelerate by the robot respectively. Jt and Jut denote the energy required for (right and left) turn and U-turn, respectively.
4. Results
The environments considered for the case studies are rectangular and discretized into square cells. The parameters of the proposed method are listed in Table V. The robot is used to clean the entire accessible free area in four complex environments with a range of obstacle shapes. The proposed algorithm is then compared with the results of other CPP algorithms developed in previously published papers [Reference Dugarjav, Lee, Kim, Kim and Chong21, Reference Prado and Marques22, Reference Schäfle, Mitschke and Uchiyama30, Reference Gajjar, Bhadani, Dutta and Rastogi36].
Algorithm parameters and its value.
4.1. Case studies in four complex environments
This section presents the comparisons of the CPP problem using the proposed method and the solutions developed by HGA [Reference Schäfle, Mitschke and Uchiyama30] and traditional GA (TGA) [Reference Gajjar, Bhadani, Dutta and Rastogi36] in four rectangular simulation environments. Fig. 7 depicts the path developed for the mobile robot through an inverted E-shaped obstacle in a rectilinear environment, which is discretized into 256 cells.
Solutions generated with inverted E-shaped obstacle using (a) the proposed approach, (b) traditional genetic algorithm, and (c) hybrid genetic algorithm.
Energy consumption of the mobile robot of the nine best solutions developed by the proposed method.
The total number of turns, U-turns, distance traveled, and energy consumed by the mobile robot of the nine best solutions among the Pareto-optimal solutions obtained by the proposed method of the environment are shown in Table VI. Using higher-level information, an optimal solution with the lowest energy consumption (solution 1) is chosen from the Pareto-optimal set generated by the proposed method. Figs. 8 and 9 show S-shaped and G-shaped obstacles in the same setting as the inverted E-shaped obstacles. Fig. 10 depicts the results in a complex environment with 400 square cells.
Solutions generated with S-shaped obstacle, (a) using the proposed approach, (b) traditional genetic algorithm, and (c) hybrid genetic algorithm.
Solutions generated with G-shaped obstacle, (a) using the proposed approach, (b) traditional genetic algorithm, and (c) hybrid genetic algorithm.
Solutions generated in complex-shaped obstacle, (a) using the proposed approach, (b) traditional genetic algorithm, and (c) hybrid genetic algorithm.
The objective functions of the solutions generated by the proposed method of all shapes of obstacles are represented in the objective space as shown in Fig. 11. The solutions obtained by HGA and TGA are also represented in Fig. 11 with red and green colors respectively. Based on the comparison, it can be concluded that at least one solution derived from the proposed method generated less energy than HGA and TGA. Table VII shows that the proposed method outperformed HGA and TGA in the four environments. The energy consumption by the proposed method is less than HGA by 6%, 3%, 2.8%, and 6% while the proposed method generates less energy than TGA by 32%, 37%, 34.3%, and 27.2% in the given environments. The computation time of the proposed method is 1.5–2 times more than that of the TGA and HGA methods. Even though the suggested method requires more computation time than the existing methods, this is not a significant drawback because the study’s application is to generate multiple sets of solutions in a static and known environment.
Solutions generated by the proposed method, hybrid genetic algorithm and traditional genetic algorithm in (a) E-shaped, (b) S-shaped, (c) G-shaped, and (d) complex-shaped obstacles.
4.2. Comparison of the proposed method with HGA for the same environment as [Reference Schäfle, Mitschke and Uchiyama30]
Schafle et al. [Reference Schäfle, Mitschke and Uchiyama30] published a study in which the HGA algorithm was used to solve the CPP problem with energy consumption as the objective. Fig. 12 depicts a comparison between the results of the proposed method and their paper. The nine best solutions among the Pareto set are shown in Fig. 12(a) which is developed by the proposed method. Fig. 12(b) represents the path generated by the HGA approach. Fig. 13 depicts the nine best solutions of the proposed method in objective space for clarity. The solution denoted by a red star is identical to the solution produced by the HGA approach. As shown in Table VIII, the energy consumed by solutions 1, 2, 4, and 5 is less than the energy consumed by the solution generated by HGA. It is observed from Table VIII that the number of turns developed by solutions 1, 2, and 4 is less than that of the HGA approach which decreases the energy consumption by 6.23%.
Comparison of energy consumption developed by the proposed method, traditional genetic algorithm (TGA), and hybrid genetic algorithm (HGA).
Solutions generated by (a) the proposed algorithm, and (b) hybrid genetic algorithm in [Reference Schäfle, Mitschke and Uchiyama30].
Solutions with blue and red marks are generated by modified Non-dominated Sorting Genetic Algorithm-2 and hybrid genetic algorithm, respectively.
4.3. Comparison of the proposed method with TGA for the same environment as [Reference Gajjar, Bhadani, Dutta and Rastogi36]
Sumit Gajjar et. al. [Reference Gajjar, Bhadani, Dutta and Rastogi36] proposed work on the CPP problem of the mobile robot that traversed the accessible working environment area with various types of obstacles using TGA. Fig. 14 displays a comparison between the paths generated by the proposed approach and TGA in a working environment with square shape of obstacles. The comparison of the proposed approach and TGA with circular and irregular shapes of obstacles in the same environment is represented in Fig. 15 and Fig. 16, respectively. An optimal solution with the lowest energy consumption is selected among Pareto set, which is generated by the proposed algorithm using higher-level information. As shown in Fig. 17, the objective functions of the solutions generated by the proposed algorithm for all types of obstacles are represented in the objective space. The solution produced by TGA is denoted in green color in Fig. 17. The energy consumed by the mobile robot using the TGA and the proposed method to complete the CPP task in a rectilinear environment with various shapes of obstacles are shown in Table IX. The number of turns of the optimal solution generated by the proposed method is much less than the TGA approach in all types of obstacles, hence the energy obtained is reduced by 47.2%, 43.8%, and 43.8% in environments with square, circular, and irregular shapes of obstacle, respectively.
The solutions generated by the proposed method (a) and traditional genetic algorithm (b) in [Reference Gajjar, Bhadani, Dutta and Rastogi36] in square shape of obstacles.
The solutions generated by the proposed method (a) and traditional genetic algorithm (b) in [Reference Gajjar, Bhadani, Dutta and Rastogi36] in circular shape of obstacles.
The solutions generated by the proposed method (a) and traditional genetic algorithm (b) in [Reference Gajjar, Bhadani, Dutta and Rastogi36] in irregular shape of obstacles.
Comparison of energy consumption by the mobile robot developed by the proposed method and hybrid genetic algorithm (HGA) in [Reference Schäfle, Mitschke and Uchiyama30].
4.4. Comparison of the proposed method with SCD and ORD methods for the same environment given in [Reference Dugarjav, Lee, Kim, Kim and Chong21, Reference Prado and Marques22]
Prado et al. [Reference Prado and Marques22] presented work on the CPP problem using the SCD method on a mobile robot that covered an entire accessible environment. Batsaikhan et al. [Reference Dugarjav, Lee, Kim, Kim and Chong21] proposed the same problem using ORD. Fig. 18 illustrates a comparison between the paths generated by the proposed method and those generated by SCD and ORD. Using higher-level information based on minimum energy consumption, solution 1 from the optimal solutions generated by the proposed algorithm is selected.
Solutions generated by the proposed method and traditional genetic algorithm with (a) square, (b) circular, and (c) irregular shapes of obstacles.
Fig. 19 illustrates the objective functions of the solutions generated by the proposed algorithm in the objective space. In Fig. 19, the solutions obtained by SCD and ORD are depicted in red and green colors, respectively. On the basis of the comparison, it can be concluded that at least one solution generated by the proposed method is less energy than SCD and ORD.
Table X depicts a comparison of the energy consumption of the mobile robot to complete the CPP task generated by the proposed algorithm with SCD and ORD. Although the distance traveled generated by the proposed method is more than SCD and ORD, the number of turns developed by the proposed method is less than SCD and ORD by 65% and 60.4%. As a result, the energy consumption by the proposed method is decreased by 41% and 35.3%, respectively.
The paths generated by (a) the proposed method, (b) spatial cell diffusion in [Reference Prado and Marques22], and (c) oriented rectilinear decomposition in [Reference Dugarjav, Lee, Kim, Kim and Chong21] in an environment.
4.5. Comparison of the proposed method with the family of STC algorithms
The results from the proposed algorithm are compared with the family of STC algorithms – the spiral and full STC [Reference Gabriely. and Rimon23]. The comparison is conducted in three simulation environments, with two of them being taken from [Reference Guruprasad24, Reference Guruprasad and Ranjitha25], while the third environment is a new case study with complex shapes of obstacles. The proposed method generates optimal solutions for the first environment as illustrated in Fig. 20. The two best paths in terms of energy consumption among these solutions are shown in Fig. 20 (a) and Fig. 20 (b). Further, Fig. 20 (c) and Fig. 20 (d) display the paths formed by spiral STC and full STC, respectively, and the spanning tree graph is represented by a thick blue line. The comparison of the solutions produced by the proposed technique, spiral STC, and full STC for the second and third environments is demonstrated in Fig. 21 and Fig. 22, respectively.
Comparison of energy consumption developed by the proposed method and traditional genetic algorithm (TGA) approach in [Reference Gajjar, Bhadani, Dutta and Rastogi36].
The algorithm in the first environment generates multiple-optimal solutions, which are indicated by blue asterisks in the objective space, as depicted in Fig. 23(a). The solution generated by the full STC approach is represented by a red asterisk in the figure. The optimal multiple solutions in the objective space produced by the proposed technique and the solution obtained by the full STC method for the second and third environments are illustrated in Fig. 23(b) and Fig. 23(c), respectively.
Comparison of energy consumption developed by the proposed method, spatial cell diffusion (SCD) in [Reference Prado and Marques22], and oriented rectilinear decomposition (ORD) in [Reference Dugarjav, Lee, Kim, Kim and Chong21].
Solutions generated by the proposed method, spatial cell diffusion [Reference Prado and Marques22] and oriented rectilinear decomposition [Reference Dugarjav, Lee, Kim, Kim and Chong21].
(a and b) Paths generated by the modified Non-dominated Sorting Genetic Algorithm-2, (c) Spiral spanning tree coverage algorithm (STC), and (d) Full STC methods for the first environment in [Reference Guruprasad24].
(a and b) Paths generated by the modified Non-dominated Sorting Genetic Algorithm-2, (c) Spiral spanning tree coverage algorithm (STC), and (d) Full STC methods for the second environment in [Reference Guruprasad and Ranjitha25].
(a and b) Paths generated by the modified Non-dominated Sorting Genetic Algorithm-2, (c) Spiral spanning tree coverage algorithm (STC), and (d) Full STC methods for the third environment.
Table XI presents a comparison of the proposed method with spiral and full STC algorithms in terms of energy consumption and coverage area by the mobile robot when completing the CPP task in three different environments. The proposed method reduces the energy consumption of the mobile robot in the first, second, and third environments by 33.8%, 5.8%, and 12.44%, respectively, compared to the full STC method. While the spiral STC method has the minimum energy usage across all the provided environments, its coverage rate is only 73.3%, 87.27%, and 71.6% in the first, second, and third environments, respectively. The proposed approach and full STC algorithm allow the robot to achieve complete coverage of 100%.
Comparison of energy consumption developed by the proposed method, spiral spanning tree coverage algorithm (STC), and full STC methods.
Solutions with blue and red colors are generated by the modified Non-dominated Sorting Genetic Algorithm-2 algorithm and full spanning tree coverage algorithm method, respectively, of the first and the second environments (a and b) in [Reference Guruprasad24, Reference Guruprasad and Ranjitha25] and (c) case study.
5. Conclusion and future scope
This paper proposes a modified NSGA-II approach for solving the MOO-CPP problem for an autonomous mobile robot in a variety of static rectilinear known environments. Using a grid-based approach, the working environment is discretized into cells, with the size and shape of each cell depending on the mobile robot. Unlike a SOO technique, a MOO method generates Pareto-optimal solutions that can be used based on the preference of user needs. The minimization of the total distance traveled and the total number of turns made by the mobile robot are the two objective functions employed in the proposed algorithm. The two objective functions are used to calculate the amount of energy the mobile robot requires to complete the CPP task. The energy consumption generated by the proposed algorithm is compared to that of the HGA, TGA, ORD, SCD, and family of STC methods. It is found that at least one solution among the multiple-optimal solutions generated by the proposed method consumes less energy than the solution generated by mentioned methods. It is observed that energy consumption by the mobile robot generated by the proposed method is approximately decreased by the range of 5%–60%. The conclusion is supported by previously published papers as well as case studies that were carried out in rectilinear environments with various shapes of obstacles. As the proposed method (modified NSGA-II) provides a diverse set of solutions (Pareto front results) compared to existing methods (TGA, HGA, ORD, SCD and STC), it (m-NSGA-II) takes higher computational time which is justified by the advantage and flexibility (multiple optimal solutions) it offers. It is to be noted that computational times are not a limitation as the proposed method is for offline path planning. Further, validation of an experiment can be conducted using a robot in a real-time environment. This research can be extended to environments of various non-rectilinear shapes and sizes. In addition to static obstacles, the environment can also contain moving obstacles. The studies can be extended with multi-agent robots with a larger scale of environments.
Author contributions
Conceptualization, methodology, and simulation environment design, Hari Kumar Vorugnati; methodology, develop MATLAB code, and analysis, Monex Sharma.
Financial support
This research received no specific grant from any funding agency, commercial, or not-for-profit sectors.
Competing interests
The authors declare no Competing interests exist.
Ethical approval
None.
