Multi-objective optimization approach for coverage path planning of mobile robot

Abstract

Coverage path planning (CPP) is a subfield of path planning problems in which free areas of a given domain must be visited by a robot at least once while avoiding obstacles. In some situations, the path may be optimized for one or more criteria such as total distance traveled, number of turns, and total area covered by the robot. Accordingly, the CPP problem has been formulated as a multi-objective optimization (MOO) problem, which turns out to be a challenging discrete optimization problem, hence conventional MOO algorithms like Non-dominated Sorting Genetic Algorithm-2 (NSGA-II) do not work as it is. This study implements a modified NSGA-II to solve the MOO problem of CPP for a mobile robot. In this paper, the proposed method adopted two objective functions: (1) the total distance traveled by the robot and (2) the number of turns taken by the robot. The two objective functions are used to calculate energy consumption. The proposed method is compared to the hybrid genetic algorithm (HGA) and the traditional genetic algorithm (TGA) in a rectilinear environment containing obstacles of various complex shapes. In addition, the results of the proposed algorithm are compared to those generated by HGA, TGA, oriented rectilinear decomposition, and spatial cell diffusion and family of spanning tree coverage in existing research papers. The results of all comparisons indicate that the proposed algorithm outperformed the existing algorithms by reducing energy consumption by 5 to 60%. This paper provides the facility to operate the robot in different modes.

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 [1, 2] and coverage path planning (CPP) that determines the most efficient path to systematically cover an entire area, ensuring least cost value [3]. CPP becomes particularly crucial in scenarios where exhaustive exploration is required, such as in vacuum cleaning [4], lawn mowing [5], window glass cleaning [6], planetary exploration [7], and underwater exploration [8]. 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. [9–11]. 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. [12] 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. [13, 14] 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 [15]. 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. [16] 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 [17] 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. [18] 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. [19] published the backtracking spiral algorithm (BSA), in which the robot follows a wall to cover the previously unexplored region. Mitschke et al. [20] 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 [19, 20] are not optimal, and they can be improved using population-based methods such as a genetic algorithm (GA). Batsaikhan et al. [21] used the spatial cell diffusion (SCD) algorithm to cover the entire free region of a rectilinear workspace. José Prado et al. [22] published a paper in which the authors used oriented rectilinear decomposition (ORD) to traverse every accessible area. The algorithms in refs. [21, 22] employed the exact cell decomposition method to split the workspace into cells. Y Gabriely and E Rimon [23] 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 [24] 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 [25] used cell permeability-based coverage algorithm to solve a CPP problem of a mobile robot. The performance of the algorithms in refs. [24, 25] is compared to spiral and full STC-based algorithms, and a better coverage area is achieved with lower overlap. VG Nair and KR Guruprasad [26] 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. [27–29]. Schafle et al. [30] 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 [31] 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. [32] 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 [33] 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).

Figure 1. (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. [34] 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.

Figure 2. 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.

Figure 3 (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) [13, 14, 19, 20] 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 [35]. When the robot has completed the CPP, the A^* algorithm is used to return it to the starting point.

Figure 4. 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 ₂. 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.

(1) \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,

(2) \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 ₁ and f ₂. The constraint of the problem is 100% coverage of an entire free area. The MOO problem is stated as,

(3) \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 ₁ = 24 and f ₂ = 7 + 1.5 × 1 = 8.5. Hence, the values of the objective functions for the MOO problem are written as f = [24, 8.5].

Figure 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 P₁ and P₂ 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 p_locus1 is determined as the i ^th element of p ₁ and a vector O ₁ is generated containing the elements from the first index to the (i - 1)^th index of p ₁, as shown in Fig. 6(b). The first occurrence of p_locus1 is extracted from the second parent p ₂ and the index k is assigned to it. As shown in Fig. 6(c), the vector O₁ is modified by appending the elements from the k ^th index to the last element of P ₂. The number of elements (n = 9) in vector O₁ 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 O₁. The elements from index j to the last element of vector O₁ are deleted as shown in Fig. 6(d). The first occurrence of p _locus2 from p ₁ is extracted and its index is labeled as r. As shown in Fig. 6(e), the elements of p ₁ are appended from the r ^th index to the last element to the vector O₁. The path generated by the genetic offspring O₁ is depicted in Fig. 6(f), but the solution is not feasible.

Figure 6. 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 O₁’. 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 O₂’. Table I depicts two parents and offspring produced by crossover and further modified with TASP and A^* algorithms.

Table I. 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.

Table II. Example of the mutation operator.

3.4.4. Merging

In this paper, the number of individuals in each generation, N_par, is selected as 150. Where the number of offspring generated through crossover, O_nc, and mutation, O_nm, depends on the p_c and p_m, respectively. The entire population of parents, N_par, and offspring through crossover, O_nc, and mutation, O_nm, 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. [34].

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.

Table III. Motion types and energy.

Table IV. Energy parameters and value.

3.6. Calculation of energy

The value of the objective functions: total distance traveled by the robot, f₁ and the total number of turns by the robot, f₂, 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 [30] 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 [30].

(4) \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), n_t and n_ut represent the number of turns (right and left) and number of U-turns taken by the robot respectively whereas n_s = N_gc – 1 – n_t – n_ut, is the number of straight motions traversed by the mobile robot. J_s represents half the energy consumption by the robot moving along a straight motion. J_acc and J_dec signify the energy required to accelerate and decelerate by the robot respectively. J_t and J_ut 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 [21, 22, 30, 36].

Table V. 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 [30] and traditional GA (TGA) [36] 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.

Figure 7. Solutions generated with inverted E-shaped obstacle using (a) the proposed approach, (b) traditional genetic algorithm, and (c) hybrid genetic algorithm.

Table VI. 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.

Figure 8. Solutions generated with S-shaped obstacle, (a) using the proposed approach, (b) traditional genetic algorithm, and (c) hybrid genetic algorithm.

Figure 9. Solutions generated with G-shaped obstacle, (a) using the proposed approach, (b) traditional genetic algorithm, and (c) hybrid genetic algorithm.

Figure 10. 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.

Figure 11. 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 [30]

Schafle et al. [30] 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%.

Table VII. Comparison of energy consumption developed by the proposed method, traditional genetic algorithm (TGA), and hybrid genetic algorithm (HGA).

Figure 12. Solutions generated by (a) the proposed algorithm, and (b) hybrid genetic algorithm in [30].

Figure 13. 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 [36]

Sumit Gajjar et. al. [36] 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.

Figure 14. The solutions generated by the proposed method (a) and traditional genetic algorithm (b) in [36] in square shape of obstacles.

Figure 15. The solutions generated by the proposed method (a) and traditional genetic algorithm (b) in [36] in circular shape of obstacles.

Figure 16. The solutions generated by the proposed method (a) and traditional genetic algorithm (b) in [36] in irregular shape of obstacles.

Table VIII. Comparison of energy consumption by the mobile robot developed by the proposed method and hybrid genetic algorithm (HGA) in [30].

4.4. Comparison of the proposed method with SCD and ORD methods for the same environment given in [21, 22]

Prado et al. [22] presented work on the CPP problem using the SCD method on a mobile robot that covered an entire accessible environment. Batsaikhan et al. [21] 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.

Figure 17. 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.

Figure 18. The paths generated by (a) the proposed method, (b) spatial cell diffusion in [22], and (c) oriented rectilinear decomposition in [21] 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 [23]. The comparison is conducted in three simulation environments, with two of them being taken from [24, 25], 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.

Table IX. Comparison of energy consumption developed by the proposed method and traditional genetic algorithm (TGA) approach in [36].

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.

Table X. Comparison of energy consumption developed by the proposed method, spatial cell diffusion (SCD) in [22], and oriented rectilinear decomposition (ORD) in [21].

Figure 19. Solutions generated by the proposed method, spatial cell diffusion [22] and oriented rectilinear decomposition [21].

Figure 20. (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 [24].

Figure 21. (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 [25].

Figure 22. (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%.

Table XI. Comparison of energy consumption developed by the proposed method, spiral spanning tree coverage algorithm (STC), and full STC methods.

Figure 23. 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 [24, 25] 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.