Sage Journals: Discover world-class research

Abstract

Coverage path planning for complex three-dimensional surfaces spray painting is one of the challenging problems in robotics. In this article, we propose a multiple chromosomes particle swarm optimization approach to address the coverage path planning problem for complex three-dimensional surfaces spray painting. Firstly, a layered segmentation method, which is composed of three-dimensional hole identification and region partition, is proposed to divide the complex surface into multiple simple regions with little curvature change and no holes. Secondly, a zigzag path is determined in each region by considering the practical aspects for spray painting. Thirdly, by taking short distance, few turns and high coverage rate into account, a multiple chromosomes particle swarm optimization algorithm is presented to connect the zigzag paths of the regions. Experimental tests are carried out on a complex surface, and the results validate the effectiveness of the proposed approach.

Keywords

Coverage path planning (CPP)complex three-dimensional (3D) surfaces spray painting layered segmentation MCPSO

Introduction

Spray painting is widely employed in the manufacturing industry, which plays an important role in automated production process, particularly in sectors such as the automotive industry.¹ In recent years, automated spray painting has become the mainstream painting process in workshops and factories, which has lots of advantages compared with the traditional manual spray painting.² Automated spray painting is performed by robotic manipulator and does not rely on the experience of the workers. There is no need for workers to be exposed to harsh environment for a long time. Moreover, automated spray painting enhances efficiency and precision, contributing to optimal paint utilization and reduced working time.

Coverage path planning (CPP) is one of the key technologies for automated spray painting. CPP is a challenging problem that involves finding a path that can effectively cover the entire task areas while avoiding obstacles.³ CPP of spray painting is easily applied to simple free surfaces while the application for complex surfaces is relatively rare since the geometry and topology of complex surfaces are complicated. Furthermore, the complex surfaces often contain many holes of different sizes and shapes, where obviously do not need to be painted. Consequently, it is necessary to study the CPP for complex surfaces spray painting.

The multiple chromosomes particle swarm optimization (MCPSO)-based CPP is proposed to address the CPP for complex surfaces spray painting problem. Multiple simple regions are generated by layered segmentation method which is composed of three-dimensional (3D) hole identification and region segmentation. Critical points are identified and recorded by the 3D identification algorithm. These critical points serve as boundaries, enabling the partitioning of the entire surface into several simple regions. For each region, a practical zigzag path is generated, considering the requirements for spray painting. It is important to highlight that each region presents four different types of zigzag paths, and the determination of each type is made with a consideration for the global optimization of paths.

To connect the zigzag paths, MCPSO algorithm is proposed to optimize the combination of paths. In the algorithm, a total reward function which is composed of four rewards, namely, Internal Path Length Reward, Connecting Path Length Reward, Fewer Turns Reward, and Coverage Rate Reward, is designed to achieve the optimal path for complex surface. Using the MCPSO algorithm, the optimal path with short path length, few turns, few overlaps, and high coverage rate can be generated.

The main contributions of this article can be summarized as follows:

A 3D hole identification algorithm is proposed to partition the complex surface hierarchically into regions that do not contain holes and have simple geometry and topology shapes. It is noteworthy that this algorithm utilizes a slicing method to identify holes after obtaining the surface model files, operating independently of sensors.

The CPP for waypoints within each region is simplified as the combinatorial planning of characteristic lines. Characteristic lines represent special line segments abstracted from waypoints. One zigzag path is obtained in each region by connecting these characteristic lines.

The MCPSO algorithm is proposed to connect the zigzag paths and generate the optimal path.

The rest of this article is organized as follows. The second section presents an overview of the research work related to CPP for complex surfaces. The third section provides a detailed mathematical description of the spray painting path planning problem. The fourth presents a layered segmentation method, which makes a preprocessing of the complex surface prior to the path planning. The fifth section introduces our novel MCPSO algorithm to address CPP for complex surface. Simulations are presented in the sixth section. A brief conclusion is given in the last section.

Related work

In this section, we present an overview of research work related to CPP for complex surfaces, which includes the CPP for 2D surfaces, the CPP for 3D surfaces, and combinatorial optimization.

CPP for 2D surfaces

There have existed many CPP methods for 2D surfaces, such as cellular decomposition-based coverage, landmark-based topological coverage, grid-based, and Voronoi-based coverage.^3,4 One of the most robust approaches is cellular decomposition-based coverage. Using cellular decomposition,^5
–7 complex regions are partitioned into several simple regions or cells, then heuristic optimization algorithms are proposed to perform global and local coverage planning. Boustrophedon decomposition,⁸ triangular-based,⁹ and Morse decomposition⁸ are alternative methods to perform coverage tasks, which play an important role in nondestructive inspection. However, these decomposition-based coverage methods have bad performance when the surfaces have large curvature variations. Moreover, it is difficult for these methods to perform the coverage tasks with unknown environment.

In the present studies, multirobot collaborative CPP and online CPP have been researched. Aiming to improve the efficiency of coverage planning, recent advances present collaborative CPP methods to speed up the coverage and reduce the time consumption. Multirobot forest coverage¹⁰ can improve the overall efficiency, especially when complex obstacles exist. Spanning tree coverage methods^11
–13 have great performance when arbitrary obstacle exists and robots start at random initial position. Other approximation heuristics approach⁷ achieves coverage by splitting the free space in smaller areas and performing efficient single robot coverage on each cell. Although these methods improve the efficiency of coverage, they still lack high robustness for complex surfaces path planning. Furthermore, the demand for a large number of robots significantly raises the cost of solution.

Online CPP methods tend to establish map using sensors or laser radars firstly, then perform the coverage tasks.¹⁴ With unknown environment, the accuracy of map building directly affects the quality of CPP. Therefore, some researches utilize machine learning^15,16 or neural network¹⁷ to establish and update map, then accomplish CPP based on it. As we can see, the quality of CPP is limited by the accuracy of sensors equipped on robots. Equipping with sensors will cause inconvenience and insecurity to some huge coverage tasks, such as spraying, blasting, and harvesting.

CPP for complex 3D surfaces

One effective CPP method for complex 3D surfaces is to decompose the surface into a set of regions or patches and then use a CPP algorithm to generate a path that covers all of the cells.¹⁸ Hierarchical decomposition based on the topology and normal directions of surfaces is one common decomposition method for complex surfaces.¹⁹ Subsequently, some functions or auxiliary models are proposed to guide the path planning of each patches, such as path fairness,¹⁸ seed curve,^20,21 and cylindrical coverage model.²² However, these methods do not consider the optimization of the path planning between patches that loses global optimal path.

Another possible approach is to perform some iterative methods^16,23

–26 to generate adaptive paths with restrictions such as minimizing the intersections, twists, and overlaps. However, these methods can be potentially suitable for small-size surfaces coverage planning but not for large complex surfaces, since the high curvature and edge effects are not fully captured with these methods.

Online and adaptive coverage for large complex surfaces with unknown environment is one of the challenging tasks. Most researches scan the environment to establish maps with cameras or sensors, then provide CPP methods based on established maps.²⁷ Wang et al.²⁸ modified a simple back-and-forth path to reduce time and energy consumption for Unmanned Aerial Vehicle (UAV) with camera under photogrammetric constraints. In other similar works, Hassan et al.^29
–31 proposed a predator–prey coverage path planning approach to perform CPP in complex environments where unexpected changes, for example, stationary and dynamic obstacles, can occur. These online coverage methods address the CPP problem in an unknown environment, but the robustness of generated path deserves further study.

Combinatorial optimization problem

Region segmentation is the common method of CPP approaches. The combinatorial path planning among regions is one of the key factors of CPP. A path among regions with short length, few turns, and few overlaps can greatly reduce the time and energy consumption of robots.³² Some popular intelligent optimization algorithms such as genetic algorithm (GA),³³ particle swarm optimization (PSO),³⁴ and ant colony optimization (ACO)³⁵ are regarded as the effective strategies for combinatorial optimization problems. Sheng et al.³⁶ modeled this combination problem as open-loop rural postman problem (Open-RPP) and employed GA to solve the Open-RPP. ACO is employed to modify the navigation points and find the shortest and safest coverage path for underwater gliders.³⁷ However, these single optimization algorithms are easily trapped in the local optimum and appear premature convergence. Moreover, these algorithms rely heavily on the parameters adjustment that bring inconvenience to optimization.

To improve the search performance and avoid local optimum, recent methods tend to utilize the group of evolutionary algorithms to perform combinatorial optimization. Improved ACO³⁸ is proposed by using GA to find the parameters combination for the best performance of ACO. Similarly, ACO enhanced by chaos-based PSO³⁹ is proposed to deal with the path planning problem for landfill inspection robots in Asahikawa, Japan. A hybrid PSO⁴⁰ is creatively proposed to solve global path planning. In these methods, one swarm intelligence algorithm is employed to optimize the parameters for another, which improves the optimization performance. Therefore, combined swarm intelligence algorithms have become one of mainstream methods for combinatorial optimization.

Problem description

CPP for spray painting has its own unique characteristics. Firstly, the robot arm is not necessary to end at the start point. Secondly, CPP for spray painting aims to cover the entire given area with the shortest path considering as few as turns and energy consumption of robots and smooth connections. For complex surfaces spray painting, multiple regions are obtained with hole identification and region partition taking into accounts of curvature change. Zigzag motion patterns of the spraying robot arm are implemented in each region. Zigzag motion paths in each region and the connections among these zigzag paths could be described as a combinatorial optimization problem known as the generalized traveling salesman problem (GTSP).

Similar to traveling salesman problem (TSP), GTSP is Non-deterministic Polynomial-time hard (Np-hard). In GTSP, we define the line segment with two endpoints named characteristic line (see “3D hole identification” section) as a city. A characteristic line represents one straight motion of the robot arm, abstracted by numerous spray painting path waypoints within that motion. Our objective is to traverse all cities to determine the optimal path with a short length, minimal turns, and high coverage rate. GTSP can be depicted using graph theory, as outlined below.

Here, a complete coverage graph $G = (V, E)$ is introduced to account for GTSP. $V = {V_{i}, i = 1, 2, \dots, n}$ denotes the vertex set, and the city is represented by V_i (characteristic line). In contrast to the traditional TSP definition, the city V_i in GTSP signifies a line segment with two endpoints A_i and B_i , that is, $V_{i} = {A_{i}, B_{i}}$ . We refer to A_i as the head endpoint and B_i as the tail endpoint. $E = {(V_{i}, V_{j}), i \neq j, V_{i} \in V, V_{j} \in V}$ denotes the edge set, which signifies the connection paths between two cities. $D = {d (V_{i}, V_{j}), i \neq j, V_{i} \in V, V_{j} \in V}$ is the set of distances between cities, where $d (V_{i}, V_{j})$ is the distance between city V_i and city V_j . Given that each city comprises two endpoints, there are four distinct values of $d (V_{i}, V_{j})$ , as illustrated in Figure 1. Two variables $c_{i} \in {0, 1} (i = 1, 2, ..., n)$ and $c_{j} \in {0, 1} (j = 1, 2, ..., n)$ are introduced to determine the value of $d (V_{i}, V_{j})$ . $d (V_{i}, V_{j})$ can be expressed by the following equation

d (V_{i}, V_{j}) = {\begin{cases} | B_{i} A_{j} |, c_{i} = 0, c_{j} = 1 \\ | A_{i} A_{j} |, c_{i} = 1, c_{j} = 1 \\ | B_{i} B_{j} |, c_{i} = 0, c_{j} = 0 \\ | A_{i} B_{j} |, c_{i} = 1, c_{j} = 0 \end{cases}

Figure 1.

Four distinct distances between adjacent cities: (a) A_j is connected with B_i (c_i = 0, c_j = 1); (b) A_j is connected with A_i (c_i = 1, c_j = 1); (c) B_j is connected with B_i (c_i = 0, c_j = 0); (d) B_j is connected with A_i (c_i = 1, c_j = 0).

Here, $| B_{i} A_{j} |$ represents the distance from B_i to A_j , and $| A_{i} A_{j} |$ represents the distance from A_i to A_j . The same definitions apply to $| B_{i} B_{j} |$ and $| A_{i} B_{j} |$ . If $c_{i} = 1$ and $c_{j} = 1$ , the distance between V_i and V_j is the length between the head endpoint A_i and the head endpoint A_j . If $c_{i} = 0$ and $c_{j} = 0$ , the distance between V_i and V_j is the length between the tail endpoint B_i and the tail endpoint B_j , The same definitions apply to $c_{i} = 0, c_{j} = 1$ and $c_{i} = 1, c_{j} = 0$ , as shown in Figure 1.

The objective of GTSP is to determine the optimal path among all possible combinations of paths. Consequently, the combinatorial optimization problem for spray painting path planning can be formulated as follows

min L (V, c) = \sum_{i = 1}^{n} \sum_{j = 1}^{n} x_{i j} d (V_{i}, V_{j})

\begin{array}{l} \begin{matrix} S.t. \sum_{i = 1}^{n} x_{i j} = 1, \forall j \in {1, 2, \dots, n} \\ \sum_{j = 1}^{n} x_{i j} = 1, \forall i \in {1, 2, \dots, n} \\ with x_{i j} = 0 or 1 \end{matrix} \end{array}

Here, n is the number of cities, and $d (V_{i}, V_{j})$ is the distance between the ith and jth city. The decision variable $x_{i j} = 1$ means the robot arm moves from city V_i to city V_j , otherwise not. Equation (3) ensures that each city can be only traversed once.

Proposed method

Figure 2 illustrates the workflow of the proposed CPP approach for complex surfaces spray painting. In essence, the approach includes three parts. Firstly, multiple regions are obtained by 3D hole identification and region partition. Secondly, Path planning is performed in each region. Thirdly, MCPSO algorithm optimizes the connecting path between regions. In the subsequent sections, we describe details of the three modules.

Figure 2.

The workflow of the proposed CPP approach. CPP: coverage path planning.

3D hole identification

Unlike simple surfaces, complex surfaces exhibit frequent changes in curvature and may contain some areas need not to be planned such as holes. To avoid the influence of curvature variation and holes, we propose a 3D hole identification algorithm to partition the surfaces.

The 3D hole identification algorithm operates on tessellated surface files, as depicted in Figure 3. A lot of intersection points are obtained by intersecting the sweep plane with triangles in the tessellated surface. The sweep planes, illustrated in Figure 4, consist of a series of tangent planes perpendicular to the sweep direction, facilitating the intersection process with the complex 3D surface.

Figure 3.

Intersection of sweep plane and tessellated surface.

Figure 4.

Region partition for complex 3D surface. 3D: three-dimensional.

We first sort and record intersection points from smallest to largest along the direction perpendicular to the sweep direction. Subsequently, we connect these intersection points on each triangle end-to-end, forming an intersection line. If the sweep plane does not intersect a hole, the latter point of the previous intersection line is connected to the former point of the next intersection line, indicating the absence of a hole. Conversely, if the sweep plane intersects a hole, the adjacent intersection lines situated on either side of the hole remain unconnected. And these unconnected points on either side of the hole are recorded as critical points. Multiple groups of critical points are obtained by intersecting the sweep plane with tessellated surface along the sweep direction. As a result, the hole polygonal contours can be generated by fitting the critical points with nonuniform rational B-splines (NURBS) curves, as shown in Figure 5. It is important to note that this algorithm identifies holes using a slicing method after obtaining the surface model files, operating independently of sensors. The proposed hole identification algorithm is described in detail as follows.

Calculate and obtain the intersection lines $l_{i} = {(p_{i}, q_{i}), i = 1, 2, \dots k}$ by intersecting one sweep plane with k triangles in the tessellated surface. Here, p_i and q_i are the two endpoints of ith intersection line. k is the number of intersection lines. Particularly, if sweep plane intersects the triangle with only one endpoint, we regard it as a line of length 0, that is, $p_{i} = q_{i}$ .

Adjust the position of the endpoint pair ${(p_{i}, q_{i}), i = 1, 2, \dots k}$ to ensure that the y-coordinate value of p_i is less than the y-coordinate value of q_i .

Sort the y-coordinate value of p_i from smallest to largest to ensure that the intersection lines $l_{i} = {(p_{i}, q_{i}), i = 1, 2, \dots k}$ increase sequentially.

The distance between $p_{i + 1}$ and q_i is defined as $d_{i} = p_{i + 1} - q_{i}, i = 1, 2, \dots, k$ . Given a hole identification threshold e, $d_{i} > e$ denotes the endpoint $p_{i + 1}$ and q_i are critical points. In addition, the accumulated number of $d_{i} > e$ , denoted by $N_{holes}$ signifies the count of holes intersected by the current sweep plane. Theoretically, all holes can be identified if e is set to 0. However, in practical applications, the threshold e is often assigned to a positive empirical value to ignore some small holes.

Figure 5.

Segmentation of the bus rear model.

Region partition

The critical points of holes on complex surface can be identified by performing hole identification algorithm. The type of critical points on the hole boundary can be divided into two types according to the location of the critical points. Based on the two different types of critical points, we propose a region partition method consisting of coarse partition and precise partition. This method effectively divides the complex surface into multiple geometrically and topologically simple regions.

Coarse partition: Coarse partition aims to roughly partition the surface into multiple simple regions. To achieve this, we introduce an auxiliary plane named splitting plane, as depicted in Figure 4. Splitting planes occur where the count of holes $N_{holes}$ changes from zero to non-zero or vice versa. By considering the splitting plane as the dividing plane, the entire surface can be segmented into multiple simple regions along the sweep direction, labeled as region 1, region 2, and region 3. It is important to note that minimizing the curvature change of each region can significantly reduce the difficulty in CPP and result in uniform paint deposition. To minimize the curvature change of each region, the sweep direction is often determined by the geometric features of the surface. In this work, we choose the vertical direction as the sweep direction since surfaces have small curvature change in the horizontal direction.

Precise partition: Precise partition aims to further divide the region with holes into several hole-free regions. For instance, region 2 is expected to be partitioned into region 2-1 and region 2-2, as shown in Figure 4. Critical points play a crucial role in this process, and we categorize the critical points obtained by the hole identification algorithm into two types: upper critical points and lower critical points, as well as left critical points and right critical points. Taking left and right critical points as example, these refer to critical points located on the left and right sides of the hole, respectively.

To achieve precise partition, we employ NURBS to interpolate the left and right critical points separately. This results in the generation of several continuous critical curves, as depicted in Figure 5. Consequently, the coarse-segmented region with holes can be further divided into hole-free regions bounded by the generated critical curves.

After the hierarchical partition described above, the complex surface is segmented into multiple simple regions without holes, each containing numerous intersection points. To simplify the complexity of coverage planning, we abstract a group of intersection points into a characteristic line. It means that each characteristic line can be formed by connecting one group of intersection points sequentially. The definition of a characteristic line is based on the types of its first and last intersecting points, resulting in five distinct types: non-left critical point (type 1), right-left critical point (type 2), right-noncritical point (type 3), non-noncritical point (type 4), and left-right critical point (type 5). For example, a characteristic line belonging to type 1 represents a group of intersection points whose first intersection point is not a critical point, and the last intersection point is a left critical point. Consequently, each region can be viewed as covered by multiple characteristic lines, facilitating the complete CPP of the entire surface, as illustrated in Figure 5.

Path planning for each region

Movement patterns are usually used to design the spraying tool path. The two widely used movement patterns are zigzag, triangular, and spiral.¹⁸ Compared with a spiral path, a zigzag path is more operationally efficient for robotic manipulator and is more common choice for spray painting. Zigzag paths, characterized by shorter lengths and fewer turns, significantly reduce the energy consumption of robots and minimize paint waste in practical applications. It has been shown that the optimal spray path tends to be a zigzag spray path.^14,23
–25 Therefore, this article adopts the zigzag path as the movement pattern in each region.

As discussed in “Region partition” section, we know that each region contains multiple characteristic lines, and these characteristic lines can be considered as a unit, easily forming zigzag paths. It is noteworthy that the number of characteristic lines in each region varies, resulting in different types of zigzag paths. Importantly, we observe that although different regions contain different numbers of characteristic lines, they can be categorized into only two situations: odd numbers of characteristic lines and even numbers of characteristic lines. In each situation, there are four distinct ways to form zigzag paths, as illustrated below.

To distinguish between different zigzag paths, we label the two endpoints of the first characteristic line as A_i and B_i , and the two endpoints of the last characteristic line as A_j and B_j in a region. As depicted in Figure 6, if a region contains an odd number of characteristic lines, the zigzag path starting from one endpoint will end at the diagonal endpoint, such as the path from A_i to B_j in Figure 6(a). Conversely, if a region contains an even number of characteristic lines, the zigzag path starting from one endpoint will end on the same side of the endpoint, as illustrated by the path from A_i to A_j in Figure 7(a). Specifically, when a region contains only one characteristic line, the zigzag path starting from one endpoint will end at the other endpoint. The zigzag paths reduce the length of the connection path between characteristic lines within each region, thereby contributing to the overall shortening of the total coverage paths.

Figure 6.

Zigzag path in odd situation: (a) A_i in and B_j out; (b) B_i in and A_j out; (c) A_j in and B_i out; (d) B_j in A_i out.

Figure 7.

Zigzag path in even situation: (a) A_i in and A_j out; (b) B_i in and B_j out; (c) A_j in and A_i out; (d) B_j in B_i out.

The analysis of zigzag paths within regions reveals four possible path traversal ways for each region. While connecting regions, there are numerous possibilities to create a complete coverage path plan. The challenge lies in planning paths within and between regions to achieve a globally optimal path. Based on the characteristic lines abstracted by groups of waypoints, we transform the planning of waypoints for the entire surface into the combinatorial optimization of characteristic lines. Consequently, a novel optimization algorithm is proposed to address this combinatorial optimization problem.

Multiple chromosomes particle swarm optimization approach

MCPSO approach is described in this section. The MCPSO algorithm is employed to achieve an overall path for the complex surface, ensuring short length, few turns, and a high coverage rate.

Definition

Building on previous academic research, combinations of popular intelligent computation algorithms, such as GA and PSO, have been recognized as effective strategies for combinatorial optimization problems.³⁹ As a result, we propose the MCPSO algorithm, which retains the core mechanisms of PSO while incorporating the chromosome crossover and variation mechanisms of GA to optimize the zigzag paths. There are some definitions in MCPSO algorithm.

Definition 1: Three chromosomes, namely, X, Y1, and Y2, are introduced to represent an individual, as illustrated in Figure 8. Each chromosome represents a distinct full coverage path. In this context, each chromosome consists of multiple genes, with the number of genes equal to the number of regions after region partition. The gene on chromosome X denotes the sequence index of regions, and chromosome X can be represented by function $π_{1}$ , signifying a traversal order O^X of regions

π_{1} : O^{X} = {O_{1}, O_{2}, ..., O_{n}}

Figure 8.

Chromosomes X, Y1, and Y2.

Here, $O_{i} (i = 1, 2, \dots, n)$ denotes the sequence index of region, n means the number of regions. For example, $O^{X} = {4, 5, 3, 1, 2}$ represents the complex surface is divided into five regions and is visited sequentially in 4-5-3-1-2 order.

Definition 2: Chromosome Y is composed of chromosomes Y1 and Y2 as shown in Figure 8, whose genes represent different types of zigzag path in region. Similar to chromosome X, chromosome Y contains the same number of genes, and the values of these genes correspond to those on chromosome X. The genes on chromosome Y adopt values of 1 or −1, denoted as $v_{i} \in {1, - 1} (i = 1, 2, \dots, n)$ . Consequently, chromosome Y can be expressed by the function $π_{2}$ to represent various zigzag paths in each region

π_{2} : O^{Y 1} = {v_{1}^{Y 1}, v_{2}^{Y 1}, \dots, v_{n}^{Y 1}}

O^{Y 2} = {v_{1}^{Y 2}, v_{2}^{Y 2}, \dots, v_{n}^{Y 2}}

\begin{matrix} with v_{i}^{Y 1} \in {1, - 1} (i = 1, 2, \dots, n) \\ v_{i}^{Y 2} \in {1, - 1} (i = 1, 2, \dots, n) \end{matrix}

where $O^{Y 1}$ and $O^{Y 2}$ represent the gene sequence of chromosomes Y1 and Y2, respectively, and n denotes the number of regions. As illustrated in Figure 9, in the ith region, $v_{i}^{Y 1} = 1$ represents that the zigzag path enters from one endpoint of the first characteristic line. Otherwise, $v_{i}^{Y 1} = - 1$ signifies that zigzag path enters from one endpoint of the last characteristic line. $v_{i}^{Y 2} = 1$ signifies that the zigzag path enters from the right endpoint of the first or last characteristic line, while $v_{i}^{Y 2} = - 1$ means that zigzag path enters from the left endpoint of first or last characteristic line. Therefore, the binary value of v_i acts as a sign that determines from which endpoint the path enters. The combination ( $v_{i}^{Y 1}$ , $v_{i}^{Y 2}$ ) indicates which endpoint of region O_i the path enters from.

Figure 9.

The selection of in and out endpoint in the mth region with different gene values of chromosome Y.

In summary, different values of the ith (i = 1, 2,…, n) gene on chromosomes Y1 and Y2 correspond to various types of zigzag paths. For example, $v_{i}^{Y 1} = 1, v_{i}^{Y 2} = - 1$ , that is, (1, −1) in Figure 9 means that the zigzag path in the ith region enters from point A of the first characteristic line. The choice of the endpoint from which to leave depends on the number of characteristic lines in the ith region, as described in “Path planning for each region” section. For instance, the zigzag path will leave from point C/D if this region contains an even/odd number of characteristic lines. It is important to note that we can exchange $v_{i}^{Y 1}$ and $v_{i}^{Y 2}$ , as the pair $(v_{i}^{Y 1}, v_{i}^{Y 2})$ merely acts as a sign determining from which endpoint the path enters.

After determining the zigzag path in each region, a global path is obtained by connecting each region according to the traversal order specified in chromosome X.

Definition 3: The Dist in the MCPSO is a distance matrix that represents the length of connecting path between regions. The connecting path length between regions is a significant factor affecting the total path length. The formula of calculating the distance of connecting path is expressed as follows

D_{i j} = \sqrt{{(x_{i} - x_{j})}^{2} + {(y_{i} - y_{j})}^{2} + {(z_{i} - z_{j})}^{2}}

where $D_{i j}$ is the Euclidean distance between waypoint $p_{i} (x_{i}, y_{i}, z_{i})$ and $p_{j} (x_{j}, y_{j}, z_{j})$ in 3D space.

Definition 4: Crossover and mutation operations are introduced to explore the entire solution space. Crossover operation is used to exchange the substrings between selected chromosomes. The Order Crossover (OX)³⁶ operation is employed in the algorithm which guarantees the creation of legal permutation of the regions in the resulting offspring. Mutation operation is used to maintain the diversity of the population and prevent it from falling into the local optimum. In the algorithm, we apply the reciprocal exchange mutation³⁶ on chromosomes by selecting two positions at random and swapping the values at those positions.

MCPSO algorithm

The proposed MCPSO algorithm is as illustrated in Algorithm 1. Table 1 provides a list of symbols used along with their definitions.

Algorithm 1.

MCPSO algorithm.

Input: vertexes cities, distance matrix Dist, iterations n_max ,

max. allocated time t_max , regions number n.

1: Initialize: n_max ← 200, indiNum ← 500.

individual_X, individual_Y1, individual_Y2 ← random (indiNum*n).

P_best, G_best ← individual. %One individual consists of three chromosomes, i.e. individual_X, individual_Y1 and individual_Y2

2: F_best ← zeros (1*n_max ).

3: while n < n_max or t < t_max do

4: Fitness ← fitness (individual, cities, Dist).

5: if Fitness < P_best. Fitness then

6: P_best ← individual.

7: end if

8: if Fitness < G_best. Fitness then

9: G_best ← individual.

10: end if

11: F_best ← max. Fitness. %Record the optimal fitness in each generation

12: for i = 1 to indiNum do

13: new_individual ← crossover (individual, G_best).

14: if fitness (new_individual, cities, Dist) < Fitness then

15: update individual.

16: end if

17: new_individual ← mutation (individual, G_best).

18: if fitness (new_individual, cities, Dist) < Fitness then

19: update individual.

20: end if

21: end for

22: update P_best, G_best.

23: end while

24: return P_best, G_best.

Table 1.

Symbols and definition.

Symbol	Definition
cities	Target objects needed to be planned
Dist	Distance representing the path length between regions
n_max	Maximum number of iterations
t_max	Maximum time allowed to the path planning task
n	Number of regions
indiNum	Number of individuals
individual_X	Traversal sequence of regions matched with chromosome X
individual_Y1	Choices of different zigzag path matched with chromosome Y1
individual_Y2	Choices of different zigzag path matched with chromosome Y2
P_best	Best individual with min. reward of each generation
G_best	Best individual with min. reward of all generations
F_best	Optimal fitness judged by reward function of each generation
new_individual	Newly generated individuals after crossover and mutation operation
R	Total reward function associated with path length, turns, and coverage rate
ω^L	Weighting factor for the path length reward
ω^T	Weighting factor for the fewer turns reward
ω^CR	Weighting factor for the coverage rate reward

In the initial stage, the cities matrix records the information of characteristic lines in each region. An individual is initialized, with P_best and G_best assigned as the initial individual. During the iteration stage, crossover and mutation operations are performed in individuals. Note that we perform crossover and mutation with the global best individual, that is, G_best, ensuring the evolution of the populations toward a superior direction. Subsequently, we calculate the fitness of each individual in this generation and assign the optimal fitness to F_best. F_best provides a metric for the ongoing iteration. If the fitness of an individual surpasses G_best, we update G_best with this individual.

Remark 1

In the practical application of spray painting, the complex surfaces required to be sprayed are typically specific and do not change over time. As a result, the optimal spray painting path generated by the algorithm tends to remain consistent after iteration. In essence, there is often no need for path regeneration in the field of spray painting due to the nonvariable nature of the input surfaces.

Spraying quality is affected by various factors, such as path length, uniformity of paint thickness and coverage rate. To evaluate the optimal path with good quality, we introduce a reward function R. The reward function R is composed of four rewards: (1) internal path length reward $L (P_{I})$ ; (2) connecting path length reward $L (P_{C})$ ; (3) fewer turns reward $T (θ)$ ; (4) coverage rate reward C_R . Upon completing the iteration process, the best individual is determined, and the optimal global path can be obtained.

Reward function

(1) Reward for minimizing the internal path length of region (internal path length reward): One of the primary goals of spray CPP is to obtain the shortest or nearly shortest coverage path, aiming to conserve spraying paint and reduce energy consumption in robotic manipulators. The internal path length of a region is the total length of the zigzag path within this region. The function for calculating the internal path length reward is formulated as equation (8)

L (P_{I}) = \sum_{j = 1}^{n} (∥ p_{j}^{s} - p_{j 1} ∥ + \sum_{k = 1}^{N^{k} - 1} ∥ p_{j_{k}} - p_{j_{k + 1}} ∥)

Here, $∥ p_{j}^{s} - p_{j 1} ∥$ represents the distance from the start waypoint to the next waypoint in the jth region, $p_{j}^{s}$ denotes the start waypoint in the jth region, and $p_{j 1}$ denotes the first waypoint behind $p_{j}^{s}$ in the jth region. n and N^k represent the number of regions and the number of the waypoints in the jth region, respectively, with $∥ \cdot ∥$ representing the Euclidean distance in our work. This reward minimizes the path length of each region, making the global coverage path shorter. For example, Figure 10(a) shows the coverage path without utilizing the internal path length reward, which exhibits many overlaps and turns. In Figure 10(b), a shorter and smoother coverage path is generated in the same environment by utilizing the internal path length reward.

(2) Reward for minimizing the connecting path length between regions (connecting path length reward): The connecting path between regions is another important factor that significantly influences the length of the total coverage path. The length of the connecting path is expected to be as short as possible to ensure that the robotic manipulator traverses a short distance, thereby reducing energy consumption. The function for this reward is formulated as equation (9)

L (P_{C}) = \sum_{j = 1}^{n - 1} ∥ p_{j}^{l} - p_{j + 1}^{e} ∥

Figure 10.

(a) The coverage path without internal path length reward. (b) The coverage path with internal path length reward.

Here, n is the number of regions, $p_{j}^{l}$ denotes the leaving endpoint of the jth region, and $p_{j + 1}^{e}$ denotes the entering endpoint of the $(j + 1)$ th region. $∥ p_{j}^{l} - p_{j + 1}^{e} ∥$ represents the connecting path length between the adjacent jth and $(j + 1)$ th regions.

(3) Reward for minimizing turns (fewer turns reward): During the spraying process, the turning movement of the robotic manipulator significantly impacts the uniformity of spray paint thickness. Frequent turning movements can lead to nonuniform spray paint distribution, causing defects on the painted surface. In addition, frequent turning movements may contribute to the wear and tear of robot joints. Therefore, minimizing the number of turns is crucial for effective CPP. In this article, the turning movement is represented by the non-flat angle of the path. For example, when three waypoints p ₁, p ₂, and p ₃ are connected in order, as shown in Figure 10(a), the angle $∠ p_{1} p_{2} p_{3} \in (0 °, 180 °)$ represents a turning movement. The reward for minimizing turns can be expressed as the ratio of the number of waypoints with a non-flat angle to the total number of waypoints, formulated as follows

T (θ) = (\sum_{i = 2}^{P - 2} ϕ (θ_{i})) / P

ϕ (θ_{i}) = {\begin{matrix} 1, 0 < θ_{i} < π \\ 0, θ_{i} = π \end{matrix}

Here, P is the number of waypoints of the entire path, $θ_{i} (i = 1, 2, \dots, P)$ is the angle $∠ p_{i - 1} p_{i} p_{i + 1} \in (0 °, 180 °]$ formed between vectors $(p_{i - 1} - p_{i})$ and $(p_{i} - p_{i + 1})$ , and $ϕ (\cdot)$ is defined as a function used to determine whether $θ_{i}$ is a non-flat angle, that is, whether it represents a turning movement.

(4) Reward for maximizing coverage rate (coverage rate reward): Coverage rate is a crucial indicator for evaluating the quality of CPP. The coverage rate is defined as the ratio of the area covered by the generated path to the total area that needs to be covered. The coverage rate reward is formulated as equation (12)

C_{R} = \frac{\sum_{i = 1}^{n} {Area}_{i}}{{Area}_{all}}

where ${Area}_{i}$ represents the area covered by the generated path in the ith region, and ${Area}_{all}$ is the total surface area that needs to be covered.

(5) Total reward (sum of all rewards): The total reward for CPP on a complex surface is the sum of all rewards previously stated, that is,

R = ω^{L} (L (P_{I}) + L (P_{C})) + ω^{T} T (θ) + ω^{C_{R}} \frac{1}{C_{R}}

where $ω^{L}$ , $ω^{T}$ , and $ω^{C_{R}}$ are the weighting factors related to path length reward, fewer turns reward, and coverage rate reward, respectively. These three weighting factors affect the importance of the corresponding rewards, and the values are determined after several experimental optimizations. Based on equation (13), the optimal coverage path, that is, the optimal sequence of waypoints $w^{*}$ , can be found.

w^{*} = argmin (R)

Simulations

In this section, several case studies are employed to validate the proposed approach. In addition, the approach has been performed on a professional robot simulation software named PQArt to assess its performance.

Experiment setup

The model employed in this study is an actual car rear model presented in STL format. The car rear has dimensions of 2.5 × 3 × 0.3 m, as depicted in Figure 11. In our study, these very small holes distributing on the four corners of the bus rear are ignored for the purpose of reducing planning resources, and this is also a common practice in industrial settings.

Figure 11.

(a) The coverage paths generated by GA. (b) The coverage paths generated by PSO. GA: genetic algorithm; PSO: particle swarm optimization.

Regarding parameters setting, the optimized weighting factors are obtained based on the experience gained from several experiments and previous researches. The weights of the reward function are set as $ω^{L} = 0.52$ , $ω^{T} = 0.24$ , and $ω^{C_{R}} = 0.24$ . The population size is 500, the maximum number of generations is 200, the crossover fraction is 0.9, and the mutation fraction is 0.05. The development environment is MATLAB R2020a on a 64-bit windows 10 system. All experiments are conducted on a PC with an Intel core (TM) i7-4790 CPU @ 3.6 GHz processor and 16 GB RAM.

Simulations and comparative analysis

Numerous studies have identified swarm intelligence optimization algorithms, including GA, ACO, and PSO, as the most commonly employed methods for spray painting path planning. This section presents a series of simulation studies to validate the proposed approach.

Analysis of GA and PSO coverage path: GA and PSO are widely employed methods for solving the path planning problem. The coverage paths generated by GA and PSO are illustrated in Figure 11. It can be seen that there are numerous turns in the coverage path, significantly increasing the total length. In addition, frequent path transitions contribute to higher energy consumption and extended working time for robots. In this case, GA and PSO achieve the appropriate combination of characteristic lines but neglect the impact of holes. The details of GA and PSO performance are shown in Table 2.

Analysis of im-GA and im-ACO coverage path: In a comparative experiment, we integrate the hole identification and layered segmentation strategy into the GA and ACO algorithm. As shown in Figure 12, the improved versions, im-GA and im-ACO, exhibit shorter path lengths and smoother paths compared to the initial GA and PSO. This case study underscores the substantial improvement in the quality of coverage paths achieved through the hole identification and layered segmentation strategy. The details of im-GA and im-ACO performance are presented in Table 2.

Analysis of CCIBA* coverage path: The Collaborative Coverage Improved BA* algorithm (CCIBA*) is a recently developed collaborative coverage algorithm, demonstrating a significant enhancement in path length, number of turns, number of units and coverage rate. However, CCIBA* executes the coverage tasks by planning units individually, overlooking global path planning, resulting in long connectivity distances between regions, as depicted in Figure 13(a). The details of CCIBA* performance are presented in Table 2.

Analysis of MCPSO coverage path: In Figure 13(b), it is evident that the proposed MCPSO algorithm efficiently traverse all regions with a shorter length and fewer turns. The occurrence of the trajectory crossover is rare, effectively reducing the energy consumption of robots. Furthermore, the total path length is significantly reduced, minimizing the movement path length of the robotic manipulator and saving working time. The proposed MCPSO algorithm outperforms both aforementioned algorithms, demonstrating quick convergence to optimal solutions through the combination of GA and PSO, and producing high-quality paths through the integration of hole identification and layered segmentation strategies.

Comparison and analysis of algorithm performance: To further illustrate the performance of the six algorithms, Table 2 provides a comparative analysis, including path length, turns, coverage rate, and running time. In the table, “avg” and “opt” represent the average and optimal values, respectively. Notably, the path length and the number of turns of the improved algorithms surpass those of the initial GA and PSO, attributed to the layered segmentation of the complex surface, facilitating coverage tasks. The path length of our MCPSO decreases by approximately 19.7% compared to that of improved GA and 16.2% compared to that of improved ACO. The number of turns of our MCPSO decreases by approximately 5.3% and 2.6% compared to that of improved GA and improved ACO, respectively. These results indicate that the MCPSO, combining the advantages of GA and PSO, outperforms individual bio-inspired algorithms. The MCPSO approach also outperforms CCIBA* in path length and turns due to global path optimization. It is worth mentioning that the coverage rate of these algorithms is similar, thanks to the zigzag movement pattern. Last but not least, the running time of MCPSO exhibits clear advantages over the aforementioned algorithms.

Table 2.

Performance analysis table of six algorithms.

Algorithm	Path length, mm		Turns		Coverage rate, %		Running time, s
Algorithm	Avg	Opt	Avg	Opt	Avg	Opt	Avg	Opt
GA	21,460.5	18,842.2	67	64	98.2	98.4	22.36	21.83
PSO	12,486.3	11,107.6	58	55	98.2	98.5	20.88	20.23
im-GA	3135.2	2963.3	40	40	98.3	98.3	23.47	22.37
im-ACO	3005.5	2715.2	39	39	98.2	98.3	14.83	14.56
CCIBA*	5507.6	4874.2	42	40	98.3	98.4	18.42	17.56
MCPSO	2518.5	2518.5	38	38	98.3	98.4	12.36	11.65

Figure 12.

(a) The coverage paths generated by improved GA. (b) The coverage paths generated by improved ACO. GA: genetic algorithm; ACO: ant colony optimization.

Figure 13.

(a) The coverage paths generated by CCIBA*. (b) The coverage paths generated by MCPSO. CCIBA*: Collaborative Coverage Improved BA* algorithm; MCPSO: multiple chromosomes particle swarm optimization.

In summary, the analysis of these performances indicates that the integration of hole identification and layered segmentation processes contributes to obtaining regular paths and a relatively high coverage rate. In addition, the proposed MCPSO algorithm exhibits significant improvements in path length, smoothness, number of turns, and running time.

As shown in Figure 14, the proposed MCPSO approach is applied to the real bus rear. The used simulation software is PQArt, a professional industrial robot offline programming software. The zigzag path width is set as 108 mm, equivalent to seven-eighths of the radius of the spray circle, to achieve uniform paint thickness.²⁵ In industrial settings, multiple robots are often employed for spraying to enhance painting efficiency. Consequently, the bus rear is evenly divided in half, with each part being sprayed by a separate robotic manipulator. The path for each part is generated using our proposed approach.

Figure 14.

Coverage path planning for the real bus rear model.

As depicted in Figure 14, the zigzag path is horizontally arranged due to the slight changes in bus surface curvature in the horizontal direction. This arrangement contributes to the generation of uniform paint thickness. The green points represent the path waypoints traversed by the robotic manipulator. Following these green waypoints, the coverage path is generated, as indicated by the orange lines. The position of the spray gun can be determined by offsetting the spraying height of these waypoints along their respective normal vectors. The simulation using the real bus rear model demonstrates that the generated path is smooth, with a short length, fewer turns, and a high coverage rate. These simulation results effectively validate the strong performance of our proposed approach.

Conclusion

In this article, a novel MCPSO-based CPP approach is proposed for complex 3D surfaces spray painting. The approach involves a layered segmentation of the surface prior to path planning. Utilizing the 3D hole identification algorithm, critical points around holes are identified and fitted into smooth boundary curves using NURBS. Subsequently, the entire surface is partitioned into several simple regions with the assistance of critical points. We discuss various movement patterns within each region to enhance CPP efficiency. The MCPSO algorithm is then applied to the partitioned regions, yielding the optimal zigzag path.

Experiments and simulation are conducted to evaluate the performances of the MCPSO algorithm and other improved heuristic algorithms. The results indicate that the MCPSO algorithm has preferable performance in path length, turns, coverage rate, and running time. In the future work, additional experiments on different complex 3D surfaces will be carried out, and multirobot collaborative CPP for complex surfaces will be studied.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Key Research and Development Plan of China under Grant 2018YFB1306303 and Key Research and Development Project of Shandong Province (Major Science and Technology Innovation Project) under Grant 2020CXGC010205.

ORCID iD

Xin Ma

References

Chen

Fuhlbrigge

. Automated industrial robot path planning for spray painting process: a review. In: 2008 IEEE international conference on automation science and engineering, Arlington, VA, USA, 23–26 August 2008, pp. 522–527. IEEE.

Sheng

Chen

, et al. Optimal tool path planning for compound surfaces in spray forming processes. In: IEEE international conference on robotics and automation, 2004. Proceedings of the ICRA ‘04. 2004 (ICRA), New Orleans, LA, USA, 26 April 2004–01 May 2004, pp. 45–50. IEEE.

Galceran

Carreras

. A survey on coverage path planning for robotics. Robot Auton Syst 2013; 61(12): 1258–1276.

Jensen-Nau

Hermans

Leang

. Near-optimal area-coverage path planning of energy-constrained aerial robots with application in autonomous environmental monitoring. IEEE Trans Autom Sci Eng 2021; 18(3): 1453–1468.

Wang

Chen

Cheng

, et al. Double heuristic optimization based on hierarchical partitioning for coverage path planning of robot mowers. In: 2016 12th international conference on computational intelligence and security (CIS), Wuxi, China, 16–19 December 2016, pp. 186–189. IEEE.

Janchive

Batsaikhan

Kim

, et al. Time-efficient and complete coverage path planning based on flow networks for multi-robots. Int J Control Autom Syst 2013; 11(2): 369–376.

Karapetyan

Benson

McKinney

, et al. Efficient multi-robot coverage of a known environment. In: 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS), Vancouver, BC, Canada, 24–28 September 2017, pp. 1846–1852. IEEE.

Olivieri

Birglen

Maldague

, et al. Coverage path planning for eddy current inspection on complex aeronautical parts. Robot Comput-Integr Manuf 2014; 30(3): 305–314.

Crosby

, et al. A triangulation-based coverage path planning. IEEE Trans Syst Man Cybern: Syst 2020; 50(6): 2157–2169.

10.

Zheng

Koenig

Kempe

, et al. Multirobot forest coverage for weighted and unweighted terrain. IEEE Trans Robot 2010; 26(6): 1018–1031.

11.

Dong

Liu

Ding

, et al. An artificially weighted spanning tree coverage algorithm for decentralized flying robots. IEEE Trans Autom Sci Eng 2020; 17(4): 1689–1698.

12.

Deng

Jing

, et al. Constrained heterogeneous vehicle path planning for large-area coverage. In: 2019 IEEE/RSJ international conference on intelligent robots and systems (IROS), Macau, China, 03–8 November 2019, pp. 4113–4120. IEEE.

13.

Gao

Xin

. A-STC: auction-based spanning tree coverage algorithm for motion planning of cooperative robots. Frontiers Inf Technol Electronic Eng 2019; 20(1): 18–31.

14.

Zhao

, et al. CCIBA*: an improved BA* based collaborative coverage path planning method for multiple unmanned surface mapping vehicles. IEEE Trans Intell Transp Syst 2022; 23(10): 19578–19588.

15.

Song

Gupta

. ε*: an online coverage path planning algorithm. IEEE Trans Robot 2018; 34(2): 526–533.

16.

Chen

Tucker

Kurfess

, et al. Adaptive deep path: efficient coverage of a known environment under various configurations. In: 2019 IEEE/RSJ international conference on intelligent robots and systems (IROS), Macau, China, 03–8 November 2019, pp. 3549–3556. IEEE.

17.

Chen

Zhang

, et al. A multi-robot distributed collaborative region coverage search algorithm based on Glasius bio-inspired neural network. IEEE Trans Cogn Dev Syst 2022; 15(3): 1449–1462.

18.

Sheng

Chen

, et al. Tool path planning for compound surfaces in spray forming processes. IEEE Trans Autom Sci Eng 2005; 2(3): 240–249.

19.

Atkar

Greenfield

Conner

, et al. Hierarchical segmentation of surfaces embedded in R3 for auto-body painting*. In: Proceedings of the 2005 IEEE international conference on robotics and automation (ICRA), Barcelona, Spain, 18–22 April 2005, pp. 572–577. IEEE.

20.

Atkar

Greenfield

Conner

, et al. Uniform coverage of automotive surface patches. Int J Robot Res 2005; 24(11): 883–898.

21.

Atkar

Conner

Greenfield

, et al. Hierarchical segmentation of piecewise pseudoextruded surfaces for uniform coverage. IEEE Trans Autom Sci Eng 2009; 6(1): 107–120.

22.

Cheng

Keller

Kumar

. Time-optimal UAV trajectory planning for 3D urban structure coverage. In: 2008 IEEE/RSJ international conference on intelligent robots and systems, Nice, France, 22–26 September 2008, pp. 2750–2757. IEEE.

23.

Gleeson

Jakobsson

Salman

, et al. Generating optimized trajectories for robotic spray painting. IEEE Trans Autom Sci Eng 2022; 19(3): 1380–1391.

24.

Wen

Jaeger

Pagilla

. Uniform coverage tool path generation for robotic surface finishing of curved surfaces. IEEE Robot Autom Lett 2022; 7(2): 4931–4938.

25.

Andulkar

Chiddarwar

Marathe

. Novel integrated offline trajectory generation approach for robot assisted spray painting operation. J Manuf Syst 2015; 37(1): 201–216.

26.

Andulkar

Chiddarwar

. Incremental approach for trajectory generation of spray painting robot. Industr Robot: An Int J 2015; 42(3): 228–241.

27.

Acar

Choset

Zhang

. Path planning for robotic demining: robust sensor-based coverage of unstructured environments and probabilistic methods. Int J Robot Res 2003; 22(7–8): 441–466.

28.

Wang

Zhang

, et al. A 3D coverage path planning approach for flying cameras in nature environment under photogrammetric constraints. In: Proceedings of 36th Chinese control conference, Dalian, China, 26–28 July 2017, pp. 6761–6766. IEEE.

29.

Hassan

Liu

. PPCPP: a predator–prey-based approach to adaptive coverage path planning. IEEE Trans Robot 2020; 36(1): 284–301.

30.

Hassan

Mustafic

Liu

. Dec-PPCPP: a decentralized predator–prey-based approach to adaptive coverage path planning amid moving obstacles. In: 2020 IEEE/RSJ international conference on intelligent robots and systems (IROS), Las Vegas, NV, USA, 24 October 2020 - 24 January 2021, pp. 11732–11739. IEEE.

31.

Hassan

Liu

. Simultaneous area partitioning and allocation for complete coverage by multiple autonomous industrial robots. Auton Robots 2017; 41(8): 1609–1628.

32.

Vandermeulen

Groß

Kolling

. Turn-minimizing multirobot coverage. In: 2019 International conference on robotics and automation (ICRA), Montreal, QC, Canada, 20–24 May 2019, pp. 1014–1020. IEEE.

33.

Tanese

. Distributed genetic algorithms for function optimization. PhD Thesis, University of Michigan, Ann Arbor, 1989.

34.

Kennedy

. Particle swarm optimization. In: Proceedings of ICNN’95 – international conference on neural networks, Perth, WA, Australia, 27 November 1995–01 December 1995, pp. 1942–1948. IEEE.

35.

Dorigo

Di Caro

. Ant colony optimization: a new meta-heuristic. In: Proceedings of the 1999 congress on evolutionary computation-CEC99 (Cat. No. 99TH8406), Washington, DC, USA, 06–09 July 1999, pp. 1470–1477. IEEE.

36.

Sheng

Tewolde

Chen

. Tool path integration for spray forming processes using a genetic algorithm. In: ICAR ‘05. Proceedings of the 12th international conference on advanced robotics, 2005, Seattle, WA, USA, 18–20 July 2005, pp. 159–164. IEEE.

37.

Han

Zhou

Zhang

, et al. Ant-colony-based complete-coverage path-planning algorithm for underwater gliders in ocean areas with thermoclines. IEEE Trans Veh Technol 2020; 69(8): 8959–8971.

38.

Yang

Liu

Xie

. Improved ant colony algorithm based on parameters optimization for AGV path planning. In: 2021 2nd international symposium on computer engineering and intelligent communications (ISCEIC), Nanjing, China, 6–8 August 2021, pp. 87–92. IEEE.

39.

Chen

Zhang

, et al. Hybrid chaos-based particle swarm optimization-ant colony optimization algorithm with asynchronous pheromone updating strategy for path planning of landfill inspection robots. Int J Adv Robot Syst 2019; 16(4): 1–11.

40.

Tang

Zhu

Luo

. Hybridizing particle swarm optimization and differential evolution for the mobile robot global path planning. Int J Adv Robot Syst 2016; 13(3): 86.

Multiple chromosomes particle swarm optimization-based coverage path planning for complex surfaces spray painting

Abstract

Keywords

Introduction

Related work

CPP for 2D surfaces

CPP for complex 3D surfaces

Combinatorial optimization problem

Problem description

Proposed method

3D hole identification

Region partition

Path planning for each region

Multiple chromosomes particle swarm optimization approach

Definition

MCPSO algorithm

Remark 1

Reward function

Simulations

Experiment setup

Simulations and comparative analysis

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References