# Automatic Recharging Path Planning for Cleaning Robots

Authors: Bing Hao; He Du; Xuefeng Dai; Hong Liang
Journal: Mobile Information Systems
 (2021)

---

## Abstract

To solve the problem of automatic recharging path planning for cleaning robots in complex industrial environments, this paper proposes two environmental path planning types based on designated charging location and multiple charging locations. First, we use the improved Maklink graph to plan the complex environment; then, we use the Dijkstra algorithm to plan the global path to reduce the complex two-dimensional path planning to one dimension; finally, we use the improved fruit fly optimization algorithm (IFOA) to adjust the path nodes for shorting the path length. Simulation experiments show that the effectiveness of using this path planning method in a complex industrial environment enables the cleaning robot to select a designated location or the nearest charging location to recharge when the power is limited. The proposed improved algorithm has the characteristics of a small amount of calculation, high precision, and fast convergence speed.


---

## Body

## 1. Introduction

Since the first autonomous mobile robot came out in the 1960s, mobile robot technology has developed rapidly. Mobile robot technology not only involves multiple disciplines such as artificial intelligence, pattern recognition, and automatic control but also involves many research topics such as navigation and positioning [1], sensor information fusion [2], path planning [3–5], and motion control [6]. In recent years, due to the advantages of saving labor cost, reusability, and intelligence, mobile robots have been applied to various fields: automatic assembly [7], sorting [8], and maintenance [9] of mobile robots in industrial field; mobile robots for surgery and rehabilitation in medical field [10]; and UAV [11] and AUV [12] in the military field. Among them, cleaning robot is the closest mobile robot to human life, which liberates people from tedious cleaning work coming out.After decades of technological evolution, the development of cleaning robots is divided into three stages. The first phase started with the advent of the world’s first cleaning robot. It was developed by the Swedish home appliance company Electrolux in 2001. The Trilobite sweeping robot produced in 2016 will automatically find the wall closest to itself when it started to be used and scan along the wall to create a cleaning map. After the trilobite completes the scanning, the area of the map is used to calculate the cleaning time. When the battery is low, it will move to the charging stand for charging and then return to the original working position to continue cleaning. The second stage is to integrate positioning and navigation technology with SLAM to establish a map in real-time and design path planning to achieve. During the cleaning process, the Ecovacs series of cleaning robots combined with laser sensors can enable the robot to restore the room layout during the cleaning process, establish a real-time and accurate positioning system, and make the cleaning process more accurate and efficient. The third stage is to combine artificial intelligence with cleaning robots to realize the functions of human-computer interaction and recognition of complex obstacles and further realize the intelligence and efficiency of cleaning robots.At any stage, the cleaning robot needs to automatically return to the charging location when the remaining power is limited, and, therefore, it is necessary to plan the return path. In [13], a new optimal path planning algorithm based on convolutional neural network (CNN) is proposed to quickly and efficiently explore the state space. However, it only applies to sampling based algorithms and needs to train the parameters in advance. To solve the problem of convergence speed of ant colony algorithm, an improved ant colony optimization algorithm for mobile robot path planning based on grid method is proposed by Liu et al. [14]. The approach effectively generates good solutions quickly and lowers the risks of trapping in a local optimum. The disadvantage is that the convergence speed is too fast to get the optimal path. Ajeil et al. [15] propose a modification based on the standard ant colony optimization, which is implemented in association with grid-based modeling for the static and dynamic environments to solve the path planning problem. However, this algorithm has a large amount of computation and cannot quickly plan the path. Generally, the path planning algorithm is divided into two categories: heuristic algorithm [16] and artificial intelligence algorithm [3]. The traditional heuristic algorithm is determined according to the description situation of the established environment. It is usually based on the geometric mathematical model to complete the search of the robot path, and the solutions obtained are all definite values. This method increases exponentially with the complexity of the environment, resulting in very long computing time and inability to obtain a better solution, while the artificial intelligence algorithm applies the instinct of natural creatures to the robot path planning and uses the behavior of the group to find the global optimal solution in a complex space. The solution is not fixed. In complex industrial environments, robots often take a long time to calculate due to the complexity of the environment and cannot return to the charging place without collision and with a short path.The traditional cleaning robot path planning algorithm is based on the two-dimensional path calculation of the environment map. The amount of calculation increases exponentially with the complexity of the environment, resulting in too long calculation time to reach the designated location. On the other hand, the cleaning robot has collided with the obstacle, causing the loss of the robot. Therefore, this paper combines the Dijkstra algorithm in the heuristic algorithm [17] and the improved fruit fly optimization algorithm (IFOA) in the artificial intelligence algorithm [18] to reduce the amount of calculation and avoid colliding with obstacles. First, the coordinate system of the cleaning robot is established, and the complex environment is modeled; secondly, to simplify the model and reduce the amount of calculation, the improved Maklink graph planning model is adopted; finally, the above-mentioned algorithm is used on this basis to realize the automatic recharging path planning of the cleaning robot.The main contributions of this paper can be summarized as follows:(1)
The improved Maklink graph further simplifies the complexity of industrial environment on the basis of Maklink graph. It prevents the cleaning robot from colliding with obstacles and speeds up the computation for later charging path planning.(2)
It hybridizes the Dijkstra and IFOA to convert two-dimensional path planning into one-dimensional path planning and further reduces the computation. The IFOA improves the searching precision and avoids too fast convergence rate on the basis of FOA.(3)
Fixed and multiple charging locations are carried out by considering various complex environments to verify the effectiveness of IFOA. By comparing IFOA with FOA, ACA, and RRT in the same environments, it is proved that the proposed algorithm can make the cleaning robot return to the charging site without collision in a relatively short time.


## 2. Cleaning Robot Coordinate System

The cleaning robot studied in this paper adopts a moving structure of two standard wheels, each of which is equipped with an independent drive motor, and the purpose of changing the direction of movement of the robot is achieved by controlling the speed difference between the two wheels [19]. In the analysis process, the robot is modeled as a rigid body on wheels [20]. Take the ground as the global reference coordinate system: X and Y, robot local reference coordinate system: Xr and Yr. The Xr is the longitudinal axis of the robot; Yr is the lateral axis of the robot. The angle difference between the global reference system and the local reference system is determined by θ.The global reference system and the local reference system are shown by(1)P˙=x,y,θT,(2)P˙r=xr,yr,θT.The mapping relationship between the two reference systems can be represented by orthogonal rotation transformation [21], as shown by(3)Rθ=cosθsinθ0−sinθcosθ0001,(4)P˙=RθP˙r,(5)P˙=xrcosθ+yrsinθ−xrsinθ+yrcosθθ.Establishing the robot coordinate system is the primary condition for studying its specific position in the environmental area, judging the relative position of obstacles and the ending point, and laying the foundation for the next step of environmental modeling and path planning.


## 3. Environmental Modeling Method

Before the autonomous charging path of the cleaning robot is planned, it is necessary to know the specific locations of the cleaning robot, obstacles, starting point, and ending point in the environmental area. The robot is able to return to the charging place without collision with the obstacle [22] when the power is limited. Therefore, modeling the environment area has become the basic premise of the autonomy charging path planning of the cleaning robot. An appropriate environment model will help the robot to understand and recognize the environment and reduce the computational complexity of path planning.


### 3.1. Typical Environmental Modeling Methods

Environmental modeling is to transform the external environment of the robot into a form that can be recognized by the computer. It is usually divided into three typical methods: Cell Decomposition Approach, Visibility Graph, and Topological Method [23]. Cell Decomposition Approach [24] is divided into precise unit decomposition and approximate unit decomposition. The main idea is to decrease the working environment of the robot into regular base areas, and each area is usually a grid. The description of the grid is used to realize the environment modeling. The advantage is that the model is constructed according to the actual environment, so it is easy to expand and maintain. The description of the environment depends on the fineness of the grid. The finer the grid is, the more the robot can recognize the information in the environment; the disadvantage is the calculation of path planning based on this method. The quantity mainly depends on the unit decomposition and connected graph search operation. When the object density is high, and the environment is complex, the calculation quantity increases exponentially.Visibility Graph [25] abstracts the obstacles in the working environment as polygons and connects the mutually visible nodes of the starting point and the target point with the vertices of the obstacle polygon. The unobstructed path between these vertices is the shortest distance between them. The main advantage is that it is simple to implement and is suitable for working areas with simple environments and sparse obstacles, so the path planning in the two-dimensional space of robots is more common. There are two problems in path planning using visual views: one is that the number of nodes and obstacle edges will increase with the number of obstacle polygons; the other is that when used in a complex environment, invalid path efficiency may be significantly reduced. It is not suitable for high-dimensional space above three dimensions.The Topological Method [26] is a method of dimensionality reduction, in which path planning transforms high-dimensional geometric space into a connectivity problem. The topological graph is composed of nodes and arcs. The nodes represent a characteristic state or location in the environment. The arcs directly connected between the nodes are equivalent to the paths in the environment. The advantage of the topology method is that it simplifies the map’s requirements for precise location, deletes the details of the map, and changes it to a more compact expression, so it reduces the modeling time and storage space and can quickly realize path planning. The disadvantages are also obvious. This method is only suitable for environments with space obstacles; otherwise, it is difficult to perform stable navigation control. On the other hand, when the number of obstacles increases, the environmental information in the topology map is difficult to modify, and the topology is complicated.


### 3.2. Environmental Modeling Based on Improved Maklink Graph

When the above three typical environment modeling methods are used in a complex environment with dense obstacles, they will cause a large amount of calculation and the robot to collide with obstacles. To solve this problem, this paper proposes an improved Maklink graph modeling method, which transforms the complex environment into a simple graph theory algorithm to search path, effectively reduces the search, and provides a prerequisite for the next path planning.The cleaning robot needs to return to the charging location as soon as the remaining power is limited. To solve this problem, this article studies two environments: one is how the robot chooses the shortest path to return to the charging place when a charging location is specified; the other is when there are multiple charging locations, how does the robot judge which is the closest place and return to the charging place with the shortest path?Therefore, the establishment of a complex environment is shown in Figure1, a square area with a side length of 30 meters, in which the black area is the wall or obstacle in the environment, and the white area is the area to be cleaned by the cleaning robot. To increase the complexity of the environment, a number of return-type “dead zones” are established in the figure to detect whether the robot can return to the charging place smoothly.Figure 1
Return charging environment. (a) Map 1. (b) Map 2. (c) Map 3.
(a)(b)(c)


#### 3.2.1. Improved Maklink Graph Environment Modeling Method

The Maklink graph [27, 28] requires the following preconditions when modeling the working area of a cleaning robot:(1)
The robot only performs motion planning in a two-dimensional plane environment, without considering the height of the robot and the environment;(2)
Environmental boundaries and obstacles are approximated by convex polygons. The algorithm is based on accurate environment model and location.(3)
The robot is approximated by “points,” which can appropriately expand the range of obstacles, so that the robot does not collide with obstacles when it moves.The basic Maklink graph method divides the space to plan the free path that the robot does not collide with obstacles in the environment. It has the characteristics of simplicity and speed [29]. But there are two main disadvantages: one is that it is only suitable for convex polygonal obstacles; the other is that when dealing with the environment model of complex obstacles, the planned link lines are cumbersome and nonintrusive [30].Aiming at the above shortcomings, this paper proposes an improved Maklink graph modeling method, which is also suitable for concave polygons and complex obstacle environments, and reduces the number of link lines, thereby reducing the calculation and iteration of the path planning search space frequency. For concave polygons that can be split into two convex polygons that share vertices at the vertices, the purpose of taking the midpoint of the link line in the Maklink graph method is to plan a collision-free path with obstacles, so it is necessary to ensure that the adjacent midpoint is connected by a solid line. After connection, no matter how the robot moves at both ends of the dotted line at the midpoint, the connected solid line does not pass through the obstacle.The specific steps of the improved Maklink graph method for environmental modeling are as follows:(1)
Connect the vertices of the nearest obstacles in the environment with dotted lines one by one.(2)
Take the midpoint of the dotted line to connect with a solid line. When the two ends of the solid line move on the dotted line and cross the obstacle, increase the line from the obstacle to the vertical line of the boundary or the apex of the obstacle.(3)
For a concave polygon, split into two convex polygons sharing the vertex at the vertex.


#### 3.2.2. Environmental Modeling for One or More Charging Locations

When specifying a charging location, the improved Maklink map planning space is shown in Figure2, and the midpoint sequence of the link line is identified as p0, p1, p2...pn, p(n + 1). When the robot has low power when p0 = S (S coordinate is (0,0)), it needs to return to p(n + 1) = T (T coordinate is (30,30)) for charging, and connect S and T to the nearest midpoint to form the robot’s free movement path.Figure 2
Environmental modeling of designated charging locations. (a) Map 1. (b) Map 2. (c) Map 3.
(a)(b)(c)When there are multiple charging locations, the improved Maklink map planning space is shown in Figure3, and the midpoint sequence of the link line is identified as p0, p1, p2...pn...p(n + 4). Suppose that the cleaning robot needs to be charged when it is located at points S1, S2, S3, and the available charging locations in the environment are located at the four corners of the map: p(n + 1) = T1, p(n + 2) = T2, p(n + 3) = T3, p(n + 4) = T4. Connect S1, S2, S3 and T1, T2, T3, T4 to the nearest midpoint to form a free movement path of the robot.Figure 3
Environmental modeling of multiple charging locations. (a) Map 1. (b) Map 2. (c) Map 3.
(a)(b)(c)


## 3.1. Typical Environmental Modeling Methods

Environmental modeling is to transform the external environment of the robot into a form that can be recognized by the computer. It is usually divided into three typical methods: Cell Decomposition Approach, Visibility Graph, and Topological Method [23]. Cell Decomposition Approach [24] is divided into precise unit decomposition and approximate unit decomposition. The main idea is to decrease the working environment of the robot into regular base areas, and each area is usually a grid. The description of the grid is used to realize the environment modeling. The advantage is that the model is constructed according to the actual environment, so it is easy to expand and maintain. The description of the environment depends on the fineness of the grid. The finer the grid is, the more the robot can recognize the information in the environment; the disadvantage is the calculation of path planning based on this method. The quantity mainly depends on the unit decomposition and connected graph search operation. When the object density is high, and the environment is complex, the calculation quantity increases exponentially.Visibility Graph [25] abstracts the obstacles in the working environment as polygons and connects the mutually visible nodes of the starting point and the target point with the vertices of the obstacle polygon. The unobstructed path between these vertices is the shortest distance between them. The main advantage is that it is simple to implement and is suitable for working areas with simple environments and sparse obstacles, so the path planning in the two-dimensional space of robots is more common. There are two problems in path planning using visual views: one is that the number of nodes and obstacle edges will increase with the number of obstacle polygons; the other is that when used in a complex environment, invalid path efficiency may be significantly reduced. It is not suitable for high-dimensional space above three dimensions.The Topological Method [26] is a method of dimensionality reduction, in which path planning transforms high-dimensional geometric space into a connectivity problem. The topological graph is composed of nodes and arcs. The nodes represent a characteristic state or location in the environment. The arcs directly connected between the nodes are equivalent to the paths in the environment. The advantage of the topology method is that it simplifies the map’s requirements for precise location, deletes the details of the map, and changes it to a more compact expression, so it reduces the modeling time and storage space and can quickly realize path planning. The disadvantages are also obvious. This method is only suitable for environments with space obstacles; otherwise, it is difficult to perform stable navigation control. On the other hand, when the number of obstacles increases, the environmental information in the topology map is difficult to modify, and the topology is complicated.


## 3.2. Environmental Modeling Based on Improved Maklink Graph

When the above three typical environment modeling methods are used in a complex environment with dense obstacles, they will cause a large amount of calculation and the robot to collide with obstacles. To solve this problem, this paper proposes an improved Maklink graph modeling method, which transforms the complex environment into a simple graph theory algorithm to search path, effectively reduces the search, and provides a prerequisite for the next path planning.The cleaning robot needs to return to the charging location as soon as the remaining power is limited. To solve this problem, this article studies two environments: one is how the robot chooses the shortest path to return to the charging place when a charging location is specified; the other is when there are multiple charging locations, how does the robot judge which is the closest place and return to the charging place with the shortest path?Therefore, the establishment of a complex environment is shown in Figure1, a square area with a side length of 30 meters, in which the black area is the wall or obstacle in the environment, and the white area is the area to be cleaned by the cleaning robot. To increase the complexity of the environment, a number of return-type “dead zones” are established in the figure to detect whether the robot can return to the charging place smoothly.Figure 1
Return charging environment. (a) Map 1. (b) Map 2. (c) Map 3.
(a)(b)(c)


### 3.2.1. Improved Maklink Graph Environment Modeling Method

The Maklink graph [27, 28] requires the following preconditions when modeling the working area of a cleaning robot:(1)
The robot only performs motion planning in a two-dimensional plane environment, without considering the height of the robot and the environment;(2)
Environmental boundaries and obstacles are approximated by convex polygons. The algorithm is based on accurate environment model and location.(3)
The robot is approximated by “points,” which can appropriately expand the range of obstacles, so that the robot does not collide with obstacles when it moves.The basic Maklink graph method divides the space to plan the free path that the robot does not collide with obstacles in the environment. It has the characteristics of simplicity and speed [29]. But there are two main disadvantages: one is that it is only suitable for convex polygonal obstacles; the other is that when dealing with the environment model of complex obstacles, the planned link lines are cumbersome and nonintrusive [30].Aiming at the above shortcomings, this paper proposes an improved Maklink graph modeling method, which is also suitable for concave polygons and complex obstacle environments, and reduces the number of link lines, thereby reducing the calculation and iteration of the path planning search space frequency. For concave polygons that can be split into two convex polygons that share vertices at the vertices, the purpose of taking the midpoint of the link line in the Maklink graph method is to plan a collision-free path with obstacles, so it is necessary to ensure that the adjacent midpoint is connected by a solid line. After connection, no matter how the robot moves at both ends of the dotted line at the midpoint, the connected solid line does not pass through the obstacle.The specific steps of the improved Maklink graph method for environmental modeling are as follows:(1)
Connect the vertices of the nearest obstacles in the environment with dotted lines one by one.(2)
Take the midpoint of the dotted line to connect with a solid line. When the two ends of the solid line move on the dotted line and cross the obstacle, increase the line from the obstacle to the vertical line of the boundary or the apex of the obstacle.(3)
For a concave polygon, split into two convex polygons sharing the vertex at the vertex.


### 3.2.2. Environmental Modeling for One or More Charging Locations

When specifying a charging location, the improved Maklink map planning space is shown in Figure2, and the midpoint sequence of the link line is identified as p0, p1, p2...pn, p(n + 1). When the robot has low power when p0 = S (S coordinate is (0,0)), it needs to return to p(n + 1) = T (T coordinate is (30,30)) for charging, and connect S and T to the nearest midpoint to form the robot’s free movement path.Figure 2
Environmental modeling of designated charging locations. (a) Map 1. (b) Map 2. (c) Map 3.
(a)(b)(c)When there are multiple charging locations, the improved Maklink map planning space is shown in Figure3, and the midpoint sequence of the link line is identified as p0, p1, p2...pn...p(n + 4). Suppose that the cleaning robot needs to be charged when it is located at points S1, S2, S3, and the available charging locations in the environment are located at the four corners of the map: p(n + 1) = T1, p(n + 2) = T2, p(n + 3) = T3, p(n + 4) = T4. Connect S1, S2, S3 and T1, T2, T3, T4 to the nearest midpoint to form a free movement path of the robot.Figure 3
Environmental modeling of multiple charging locations. (a) Map 1. (b) Map 2. (c) Map 3.
(a)(b)(c)


## 3.2.1. Improved Maklink Graph Environment Modeling Method

The Maklink graph [27, 28] requires the following preconditions when modeling the working area of a cleaning robot:(1)
The robot only performs motion planning in a two-dimensional plane environment, without considering the height of the robot and the environment;(2)
Environmental boundaries and obstacles are approximated by convex polygons. The algorithm is based on accurate environment model and location.(3)
The robot is approximated by “points,” which can appropriately expand the range of obstacles, so that the robot does not collide with obstacles when it moves.The basic Maklink graph method divides the space to plan the free path that the robot does not collide with obstacles in the environment. It has the characteristics of simplicity and speed [29]. But there are two main disadvantages: one is that it is only suitable for convex polygonal obstacles; the other is that when dealing with the environment model of complex obstacles, the planned link lines are cumbersome and nonintrusive [30].Aiming at the above shortcomings, this paper proposes an improved Maklink graph modeling method, which is also suitable for concave polygons and complex obstacle environments, and reduces the number of link lines, thereby reducing the calculation and iteration of the path planning search space frequency. For concave polygons that can be split into two convex polygons that share vertices at the vertices, the purpose of taking the midpoint of the link line in the Maklink graph method is to plan a collision-free path with obstacles, so it is necessary to ensure that the adjacent midpoint is connected by a solid line. After connection, no matter how the robot moves at both ends of the dotted line at the midpoint, the connected solid line does not pass through the obstacle.The specific steps of the improved Maklink graph method for environmental modeling are as follows:(1)
Connect the vertices of the nearest obstacles in the environment with dotted lines one by one.(2)
Take the midpoint of the dotted line to connect with a solid line. When the two ends of the solid line move on the dotted line and cross the obstacle, increase the line from the obstacle to the vertical line of the boundary or the apex of the obstacle.(3)
For a concave polygon, split into two convex polygons sharing the vertex at the vertex.


## 3.2.2. Environmental Modeling for One or More Charging Locations

When specifying a charging location, the improved Maklink map planning space is shown in Figure2, and the midpoint sequence of the link line is identified as p0, p1, p2...pn, p(n + 1). When the robot has low power when p0 = S (S coordinate is (0,0)), it needs to return to p(n + 1) = T (T coordinate is (30,30)) for charging, and connect S and T to the nearest midpoint to form the robot’s free movement path.Figure 2
Environmental modeling of designated charging locations. (a) Map 1. (b) Map 2. (c) Map 3.
(a)(b)(c)When there are multiple charging locations, the improved Maklink map planning space is shown in Figure3, and the midpoint sequence of the link line is identified as p0, p1, p2...pn...p(n + 4). Suppose that the cleaning robot needs to be charged when it is located at points S1, S2, S3, and the available charging locations in the environment are located at the four corners of the map: p(n + 1) = T1, p(n + 2) = T2, p(n + 3) = T3, p(n + 4) = T4. Connect S1, S2, S3 and T1, T2, T3, T4 to the nearest midpoint to form a free movement path of the robot.Figure 3
Environmental modeling of multiple charging locations. (a) Map 1. (b) Map 2. (c) Map 3.
(a)(b)(c)


## 4. Cleaning Robot Charging Path Planning

After the improved Maklink graph environment modeling, the cleaning robot’s charging path planning problem is transformed into the shortest path to solve the graph, and the path is two-dimensional path planning [31, 32]. To further reduce the solution space and calculation amount of the algorithm, this paper uses Dijkstra algorithm to simply plan the shortest path in the improved Maklink graph, which converts two-dimensional to one-dimensional path planning, but the resulting path is composed of points in the improved Maklink graph, not the shortest path. Therefore, this paper uses the improved fruit fly optimization algorithm to finely plan the path points, so that the cleaning robot returns to the charging point by the shortest path when the remaining power is limited.


### 4.1. Preliminary Planning Based on Dijkstra Algorithm

The Dijkstra algorithm was proposed by the Dutch mathematician E.W. Dijkstra in 1959. It is a typical shortest path algorithm for solving the shortest path of a directed graph [33]. Its main feature is the breadth-first preliminary traversal search algorithm, with the starting point at the center and being extended to the ending point. It can solve the shortest path of the node from the starting point to the ending point in the figure. The starting point S is specified when calculating, and divides the points into two sets: H and U, H is to record the vertex of the calculated shortest path and the corresponding shortest path length. U is to record the vertex of the shortest path that is also solved and the distance from the vertex to the starting point S [34].The specific steps of Dijkstra algorithm are as follows:(1)
In initialization, specify the starting pointS; H only includes the starting point S, and U includes other vertices except for S(2)
Select the vertexP with the shortest distance from U, add the vertex P to H, and remove the vertex P from U(3)
At this time, update the distance of each vertex inU to the starting point S, and use P to update the distance of other vertices(4)
Repeat steps (2) to (3) until all vertices are traversedDijkstra algorithm is used to generate a suboptimal path, which successively passes through the path nodesS, P1,P2,…,Pd and T. The Maklink lines corresponding to nodes are Lii=1,2,…,d. Let A and B be the two ends of C, and the mathematical model of other points on the chain route is(6)Pihi=Pi0+Pi1−Pi0∗hi,hi∈0,1,i=1,2,…,d,where hi is the proportional parameter and d is the Maklink’s path node.It can be seen from equation (6) that when the path obtained by the Dijkstra algorithm passes through the Maklink lines, as long as a set of parameters (h1,h2,…,hd) is given, a new path from the starting point to the end point can be obtained, and the solution of the fruit fly algorithm is expressed as (h1,h2,…,hd).The preliminary path planning by Dijkstra algorithm of the designated charging location in Map 1 isS⟶p1⟶p2⟶p3⟶p4⟶p5⟶p6⟶p10⟶p11⟶p13⟶p19⟶p20⟶p30⟶p31⟶p32⟶p33⟶p34⟶p35⟶p36⟶T. In Map 2, it is S⟶p1⟶p2⟶p3⟶p4⟶p5⟶p6⟶p7 ⟶p10⟶p11⟶p12⟶p23⟶p37⟶T. In Map 3 is: S⟶p1⟶p3⟶p6⟶p7⟶p8⟶p9⟶p10⟶p12⟶p26⟶p24⟶T. As shown in Figure 4, the path experienced by the black dot is the preliminary path planned by the Dijkstra algorithm, with a total length of 116.2120 m in Map 1, 81.4383 m in Map 2, and 80.0383 m in Map 3.Figure 4
Preliminary path of charging location designated by Dijkstra algorithm. (a) Map 1. (b) Map 2. (c) Map 3.
(a)(b)(c)The method of path planning for multiple charging locations is to use Dijkstra algorithm to first determine the distance from the starting point to the four charging locations and then select the shortest preliminary path based on the improved Maklink graph after sorting. The distance between the starting point and the four charging locations is shown in Table1.Table 1
Distance fromS1, S2, and S3 to the four charging locations.
Map 1T1 (0, 0)T2 (0, 30)T3 (30, 30)T4 (30, 0)S1 (12, 3.5)76.2913 m50.4909 m69.9310 m53.9134 mS2 (23, 10)92.2263 m61.8426 m80.2386 m64.2238 mS3 (6, 12)41.6665 m59.5753 m96.7111 m76.6636 mMap 2T1 (0, 0)T2 (0, 30)T3 (30, 30)T4 (30, 0)S1 (4.5, 15)84.0328 m74.8810 m78.8113 m87.6712 mS2 (12.5, 2.5)37.8648 m55.7663 m59.6965 m68.5564 mS3 (25.5, 20)124.1846 m109.0067 m45.8574 m107.9382 mMap 3T1 (0, 0)T2 (0, 30)T3 (30, 30)T4 (30, 0)S1 (13, 3)73.3489 m43.4753 m40.0499 m73.5339 mS2 (23, 28.5)72.6284 m29.0777 m21.3851 m65.5631 mS3 (22, 17)132.6538 m94.6245 m130.8422 m79.2115 mWhen the cleaning robot is inS1, the Dijkstra algorithm path of the four charging locations is shown in Figure 5. According to the relative distance, select the closest charging location T2 in Map 1: S1⟶p18⟶p17⟶p16⟶p14⟶p12⟶p13⟶p37⟶p43⟶p42⟶p41⟶p40⟶p39⟶T2, the path length is 50.4909 m. Select the closest charging location T2 in Map 2: S1⟶p17⟶p16⟶p15⟶p14⟶p13⟶p12⟶p18⟶p19⟶p20⟶p21⟶p22⟶T2, the path length is 74.8810 m. Select the closest charging location T3 in Map 3: S1⟶p11⟶p12⟶p20⟶p26⟶p24⟶T3, the path length is 40.0499 m.Figure 5
Dijkstra algorithm path when the starting point is inS1. (a) Map 1. (b) Map 2. (c) Map 3.
(a)(b)(c)When the cleaning robot is inS2, the Dijkstra algorithm path of the four charging locations is shown in Figure 6. According to the relative distance, select the closest charging location T2 through the improved Maklink graph for preliminary path planning in Map 1: S2⟶p26⟶p25⟶p24⟶p21⟶p20⟶p19⟶p37⟶p43⟶p42⟶p41⟶p40⟶p39⟶T2, the path length is 61.8426 m. Select the closest charging location T1 in Map 2: S2⟶p9⟶p8⟶p7⟶p6 ⟶p5⟶p4⟶p3⟶p2⟶p1⟶T1, the path length is 37.8648 m. Select the closest charging location T3 in Map 3: S2⟶p22⟶p26⟶p24⟶T3, the path length is 21.3851 m.Figure 6
Dijkstra algorithm path when the starting point is inS2. (a) Map 1. (b) Map 2. (c) Map 3.
(a)(b)(c)When the cleaning robot is inS3, the Dijkstra algorithm path of the four charging locations is shown in Figure 7. According to the relative distance, select the closest charging location T1 through the improved Maklink graph for preliminary path planning in Map 1: S3⟶p9⟶p8⟶p7⟶p6⟶p5⟶p4⟶p3⟶p3⟶p2⟶p1⟶T1, the path length is 41.6665 m. Select the closest charging location T3 in Map 2: S3⟶p46⟶p45⟶p44⟶p43⟶p42⟶p41⟶p40⟶p39⟶p38⟶T3, the path length is 45.8574 m. Select the closest charging location T3 in Map 2: S3⟶p35⟶p34⟶p33⟶p32⟶p31⟶p30⟶p29⟶p28⟶p36⟶p37⟶p38⟶T4, the path length is 79.2115 m.Figure 7
Dijkstra algorithm path when the starting point is inS3. (a) Map 1. (b) Map 2. (c) Map 3.
(a)(b)(c)


### 4.2. Fine Planning Based on IFOA

The path planned by the Dijkstra algorithm is only a preliminary plan based on the improved Maklink graph. The path can be further optimized by changing the position of the dotted line at the midpoint of the passing. In order to solve this problem, this paper proposes fine planning based on the fruit fly optimization algorithm (FOA). The reasons for using the FOA are as follows:(1)
The calculation is simple and easy to implement(2)
The global optimization ability is strong(3)
It is suitable for two-dimensional search optimization problems [35]The basic principle is based on the two stages of smell and vision during the foraging process of fruit fly. In the smell stage, the individuals in the fruit fly population choose the general direction and position to fly to the food according to the concentration of food pheromone in the air; the visual stage locates the specific position of the food according to the accurate visual position of the food and the position of the companion fruit fly and iterates the food continuously [36], as shown in Figure 8.Figure 8
The iterative process of FOA.Basic FOA have many advantages and disadvantages:(1)
The initial positionsX_axis and Y_axis of the fruit fly population are randomly selected on the global position, which may deviate greatly from the optimal solution, and the convergence speed is slow.(2)
The flight distance of individual fruit fly searching for food by smell is a fixed value, and the value determines the searchability, and it cannot take into account the global and local searchability. To solve the above problems, this paper proposes an improved fruit fly optimization algorithm that limits the initial position and variable flight distance of the fruit fly population, which effectively accelerates the convergence speed and improves the ability of fine optimization in the later stage. The improvement method is as follows:PositionX_axis andY_axis, limited to passing through the two ends of the dotted line at the midpoint p(k) of the path; change the single flight distance.Dist of individual fruit fly to a variable function with the number of iterations:(7)Dist=Len−tanh5∗genMaxgen+1,whereLen is a constant; gen is the current number of iterations; and Maxgen is the maximum number of iterations. When Len = 1 and Maxgen = 50, the function image is shown in Figure 9.Figure 9
Variable distance function image.It can be seen from the image that the larger search distance at the beginning of the iteration facilitates the movement of the optimal solution, and the smaller search distance in the later stage performs a fine search to improve the accuracy of the optimal solution.The specific steps of the IFOA are as follows:(1)
Initialize the parameters of the fruit fly optimization algorithm: population size:popsize, the maximum number of iterations: Maxgen. Initialize the position of the fruit fly population on the path of Dijkstra algorithm: X_axis and Y_axis.(2)
At the beginning of the fruit fly search, the individual fruit fly uses the sense of smell to find food:(8)Xp=X_axis+Dist2∗rand−1,Yp=Y_axis+Dist2∗rand−1,whererand is an arbitrary random number in the interval [0,1], and Dist indicates the distance of a single flight of the individual fruit fly as shown in equation (7).(3)
Determine the taste concentration determination function of individual fruit fly. Since the fruit fly population needs to find the location of the food source, but the specific location of the food is unknown, first calculate the distanceD from the origin (0,0) and calculate the reciprocal of D as a judgment function of taste concentration:(9)Di,j=sqrtXp^2+Yp^2,Si,j=1Di,j.(4)
Using the taste concentration judgment function to determine the taste concentration value of individual fruit fly,(10)Smellp=FunctionSi,j.(5)
According to the taste concentration value of each individual fruit fly, keep the individual with the highest taste concentration value:(11)bestsmell,bestindex=minSmell,wherebestsmell is the optimal taste concentration value in this iteration and bestindexis the position coordinates corresponding to the optimal taste concentration value in the iteration.(6)
According to the position of the fruit fly with a strong taste and the best taste in step (5), the fruit fly colony moves to the best position by vision.(12)if bestsmell<SmellBest,X_axis=Xbestindex,:,Y_axis=Ybestindex,:,SmellBest=bestsmell.(7)
Iterative optimization to the maximum number of iterationsMaxgen, repeat steps (2) to (5), according to whether the taste concentration value of the current iteration is greater than the optimal taste concentration value that has been retained; if yes, proceed to step (6); otherwise, proceed to the next iteration until the maximum number of iterations is reached, and output the optimal result.IFOA, compared with ant colony algorithm, genetic algorithm, and particle swarm algorithm, is simple and easy to implement, has fast convergence, and can get the optimal solution quickly, but the disadvantage of the algorithm is that it is only suitable for low dimensional solution and may fall into local minimum.The flowchart of the IFOA is shown in Figure10.Figure 10
IFOA flowchart.


## 4.1. Preliminary Planning Based on Dijkstra Algorithm

The Dijkstra algorithm was proposed by the Dutch mathematician E.W. Dijkstra in 1959. It is a typical shortest path algorithm for solving the shortest path of a directed graph [33]. Its main feature is the breadth-first preliminary traversal search algorithm, with the starting point at the center and being extended to the ending point. It can solve the shortest path of the node from the starting point to the ending point in the figure. The starting point S is specified when calculating, and divides the points into two sets: H and U, H is to record the vertex of the calculated shortest path and the corresponding shortest path length. U is to record the vertex of the shortest path that is also solved and the distance from the vertex to the starting point S [34].The specific steps of Dijkstra algorithm are as follows:(1)
In initialization, specify the starting pointS; H only includes the starting point S, and U includes other vertices except for S(2)
Select the vertexP with the shortest distance from U, add the vertex P to H, and remove the vertex P from U(3)
At this time, update the distance of each vertex inU to the starting point S, and use P to update the distance of other vertices(4)
Repeat steps (2) to (3) until all vertices are traversedDijkstra algorithm is used to generate a suboptimal path, which successively passes through the path nodesS, P1,P2,…,Pd and T. The Maklink lines corresponding to nodes are Lii=1,2,…,d. Let A and B be the two ends of C, and the mathematical model of other points on the chain route is(6)Pihi=Pi0+Pi1−Pi0∗hi,hi∈0,1,i=1,2,…,d,where hi is the proportional parameter and d is the Maklink’s path node.It can be seen from equation (6) that when the path obtained by the Dijkstra algorithm passes through the Maklink lines, as long as a set of parameters (h1,h2,…,hd) is given, a new path from the starting point to the end point can be obtained, and the solution of the fruit fly algorithm is expressed as (h1,h2,…,hd).The preliminary path planning by Dijkstra algorithm of the designated charging location in Map 1 isS⟶p1⟶p2⟶p3⟶p4⟶p5⟶p6⟶p10⟶p11⟶p13⟶p19⟶p20⟶p30⟶p31⟶p32⟶p33⟶p34⟶p35⟶p36⟶T. In Map 2, it is S⟶p1⟶p2⟶p3⟶p4⟶p5⟶p6⟶p7 ⟶p10⟶p11⟶p12⟶p23⟶p37⟶T. In Map 3 is: S⟶p1⟶p3⟶p6⟶p7⟶p8⟶p9⟶p10⟶p12⟶p26⟶p24⟶T. As shown in Figure 4, the path experienced by the black dot is the preliminary path planned by the Dijkstra algorithm, with a total length of 116.2120 m in Map 1, 81.4383 m in Map 2, and 80.0383 m in Map 3.Figure 4
Preliminary path of charging location designated by Dijkstra algorithm. (a) Map 1. (b) Map 2. (c) Map 3.
(a)(b)(c)The method of path planning for multiple charging locations is to use Dijkstra algorithm to first determine the distance from the starting point to the four charging locations and then select the shortest preliminary path based on the improved Maklink graph after sorting. The distance between the starting point and the four charging locations is shown in Table1.Table 1
Distance fromS1, S2, and S3 to the four charging locations.
Map 1T1 (0, 0)T2 (0, 30)T3 (30, 30)T4 (30, 0)S1 (12, 3.5)76.2913 m50.4909 m69.9310 m53.9134 mS2 (23, 10)92.2263 m61.8426 m80.2386 m64.2238 mS3 (6, 12)41.6665 m59.5753 m96.7111 m76.6636 mMap 2T1 (0, 0)T2 (0, 30)T3 (30, 30)T4 (30, 0)S1 (4.5, 15)84.0328 m74.8810 m78.8113 m87.6712 mS2 (12.5, 2.5)37.8648 m55.7663 m59.6965 m68.5564 mS3 (25.5, 20)124.1846 m109.0067 m45.8574 m107.9382 mMap 3T1 (0, 0)T2 (0, 30)T3 (30, 30)T4 (30, 0)S1 (13, 3)73.3489 m43.4753 m40.0499 m73.5339 mS2 (23, 28.5)72.6284 m29.0777 m21.3851 m65.5631 mS3 (22, 17)132.6538 m94.6245 m130.8422 m79.2115 mWhen the cleaning robot is inS1, the Dijkstra algorithm path of the four charging locations is shown in Figure 5. According to the relative distance, select the closest charging location T2 in Map 1: S1⟶p18⟶p17⟶p16⟶p14⟶p12⟶p13⟶p37⟶p43⟶p42⟶p41⟶p40⟶p39⟶T2, the path length is 50.4909 m. Select the closest charging location T2 in Map 2: S1⟶p17⟶p16⟶p15⟶p14⟶p13⟶p12⟶p18⟶p19⟶p20⟶p21⟶p22⟶T2, the path length is 74.8810 m. Select the closest charging location T3 in Map 3: S1⟶p11⟶p12⟶p20⟶p26⟶p24⟶T3, the path length is 40.0499 m.Figure 5
Dijkstra algorithm path when the starting point is inS1. (a) Map 1. (b) Map 2. (c) Map 3.
(a)(b)(c)When the cleaning robot is inS2, the Dijkstra algorithm path of the four charging locations is shown in Figure 6. According to the relative distance, select the closest charging location T2 through the improved Maklink graph for preliminary path planning in Map 1: S2⟶p26⟶p25⟶p24⟶p21⟶p20⟶p19⟶p37⟶p43⟶p42⟶p41⟶p40⟶p39⟶T2, the path length is 61.8426 m. Select the closest charging location T1 in Map 2: S2⟶p9⟶p8⟶p7⟶p6 ⟶p5⟶p4⟶p3⟶p2⟶p1⟶T1, the path length is 37.8648 m. Select the closest charging location T3 in Map 3: S2⟶p22⟶p26⟶p24⟶T3, the path length is 21.3851 m.Figure 6
Dijkstra algorithm path when the starting point is inS2. (a) Map 1. (b) Map 2. (c) Map 3.
(a)(b)(c)When the cleaning robot is inS3, the Dijkstra algorithm path of the four charging locations is shown in Figure 7. According to the relative distance, select the closest charging location T1 through the improved Maklink graph for preliminary path planning in Map 1: S3⟶p9⟶p8⟶p7⟶p6⟶p5⟶p4⟶p3⟶p3⟶p2⟶p1⟶T1, the path length is 41.6665 m. Select the closest charging location T3 in Map 2: S3⟶p46⟶p45⟶p44⟶p43⟶p42⟶p41⟶p40⟶p39⟶p38⟶T3, the path length is 45.8574 m. Select the closest charging location T3 in Map 2: S3⟶p35⟶p34⟶p33⟶p32⟶p31⟶p30⟶p29⟶p28⟶p36⟶p37⟶p38⟶T4, the path length is 79.2115 m.Figure 7
Dijkstra algorithm path when the starting point is inS3. (a) Map 1. (b) Map 2. (c) Map 3.
(a)(b)(c)


## 4.2. Fine Planning Based on IFOA

The path planned by the Dijkstra algorithm is only a preliminary plan based on the improved Maklink graph. The path can be further optimized by changing the position of the dotted line at the midpoint of the passing. In order to solve this problem, this paper proposes fine planning based on the fruit fly optimization algorithm (FOA). The reasons for using the FOA are as follows:(1)
The calculation is simple and easy to implement(2)
The global optimization ability is strong(3)
It is suitable for two-dimensional search optimization problems [35]The basic principle is based on the two stages of smell and vision during the foraging process of fruit fly. In the smell stage, the individuals in the fruit fly population choose the general direction and position to fly to the food according to the concentration of food pheromone in the air; the visual stage locates the specific position of the food according to the accurate visual position of the food and the position of the companion fruit fly and iterates the food continuously [36], as shown in Figure 8.Figure 8
The iterative process of FOA.Basic FOA have many advantages and disadvantages:(1)
The initial positionsX_axis and Y_axis of the fruit fly population are randomly selected on the global position, which may deviate greatly from the optimal solution, and the convergence speed is slow.(2)
The flight distance of individual fruit fly searching for food by smell is a fixed value, and the value determines the searchability, and it cannot take into account the global and local searchability. To solve the above problems, this paper proposes an improved fruit fly optimization algorithm that limits the initial position and variable flight distance of the fruit fly population, which effectively accelerates the convergence speed and improves the ability of fine optimization in the later stage. The improvement method is as follows:PositionX_axis andY_axis, limited to passing through the two ends of the dotted line at the midpoint p(k) of the path; change the single flight distance.Dist of individual fruit fly to a variable function with the number of iterations:(7)Dist=Len−tanh5∗genMaxgen+1,whereLen is a constant; gen is the current number of iterations; and Maxgen is the maximum number of iterations. When Len = 1 and Maxgen = 50, the function image is shown in Figure 9.Figure 9
Variable distance function image.It can be seen from the image that the larger search distance at the beginning of the iteration facilitates the movement of the optimal solution, and the smaller search distance in the later stage performs a fine search to improve the accuracy of the optimal solution.The specific steps of the IFOA are as follows:(1)
Initialize the parameters of the fruit fly optimization algorithm: population size:popsize, the maximum number of iterations: Maxgen. Initialize the position of the fruit fly population on the path of Dijkstra algorithm: X_axis and Y_axis.(2)
At the beginning of the fruit fly search, the individual fruit fly uses the sense of smell to find food:(8)Xp=X_axis+Dist2∗rand−1,Yp=Y_axis+Dist2∗rand−1,whererand is an arbitrary random number in the interval [0,1], and Dist indicates the distance of a single flight of the individual fruit fly as shown in equation (7).(3)
Determine the taste concentration determination function of individual fruit fly. Since the fruit fly population needs to find the location of the food source, but the specific location of the food is unknown, first calculate the distanceD from the origin (0,0) and calculate the reciprocal of D as a judgment function of taste concentration:(9)Di,j=sqrtXp^2+Yp^2,Si,j=1Di,j.(4)
Using the taste concentration judgment function to determine the taste concentration value of individual fruit fly,(10)Smellp=FunctionSi,j.(5)
According to the taste concentration value of each individual fruit fly, keep the individual with the highest taste concentration value:(11)bestsmell,bestindex=minSmell,wherebestsmell is the optimal taste concentration value in this iteration and bestindexis the position coordinates corresponding to the optimal taste concentration value in the iteration.(6)
According to the position of the fruit fly with a strong taste and the best taste in step (5), the fruit fly colony moves to the best position by vision.(12)if bestsmell<SmellBest,X_axis=Xbestindex,:,Y_axis=Ybestindex,:,SmellBest=bestsmell.(7)
Iterative optimization to the maximum number of iterationsMaxgen, repeat steps (2) to (5), according to whether the taste concentration value of the current iteration is greater than the optimal taste concentration value that has been retained; if yes, proceed to step (6); otherwise, proceed to the next iteration until the maximum number of iterations is reached, and output the optimal result.IFOA, compared with ant colony algorithm, genetic algorithm, and particle swarm algorithm, is simple and easy to implement, has fast convergence, and can get the optimal solution quickly, but the disadvantage of the algorithm is that it is only suitable for low dimensional solution and may fall into local minimum.The flowchart of the IFOA is shown in Figure10.Figure 10
IFOA flowchart.


## 5. Simulation

To select the optimal FOA initialization parameters, this paper tests the connection between iteration,popsize, time, and path length. Figure 11 is obtained by repeating the test 30 times from S to T on map 1. Through Figure 11, it can be seen that the distance gradually decreases with the increase of iteration and population, but the time increases exponentially. Taking into account the time cost, the optimal FOA parameters are set as popsize = 400, Maxgen = 40.Figure 11
Selection of initialization parameters.To evaluate the performance of path planning based on the IFOA, this paper conducts a comparison test of the basic FOA, the IFOA, Rapidly Exploring Random Tree (RRT), and ant colony algorithm (ACA) under the environment of designated one or more charging locations. The FOA and IFOA parameters are set aspopsize = 400, Maxgen = 40, Len = 0.5, the ACA parameters are set as popsize = 400, Maxgen = 40, Pheromone calculation parameters: 2, Pheromone selection threshold: 0.8, Pheromone update parameters: 0.1, the RRT parameters are set as Step = 2, MaxAttempts = 1000, and the experiment is repeated 30 times on the same map with different starting and ending points.The comparison of the optimal path and comparison of evaluation indicators on Map 1 is shown in Figures12 and 13.Figure 12
Comparison of optimal paths on Map 1. (a) S-T. (b) S1-T2. (c) S2-T2. (d) S3-T1.
(a)(b)(c)(d)Figure 13
Comparison of evaluation indicators on Map 1. (a) The best path length comparison. (b) The worst path length comparison. (c) Average path length comparison. (d) Average computing time comparison. (e) Average iterative convergence time comparison. (f) Standard deviation comparison.
(a)(b)(c)(d)(e)(f)The comparison of the optimal path and comparison of evaluation indicators on Map 2 is shown in Figures14 and 15.Figure 14
Comparison of optimal paths on Map 2. (a) S-T. (b) S1-T2. (c) S2-T1. (d) S3-T3.
(a)(b)(c)(d)Figure 15
Comparison of evaluation indicators on Map 2. (a) The best path length comparison. (b) The worst path length comparison. (c) Average path length comparison. (d) Average computing time comparison. (e) Average iterative convergence time comparison. (f) Standard deviation comparison.
(a)(b)(c)(d)(e)(f)The comparison of the optimal path and comparison of evaluation indicators on Map 3 is shown in Figures16 and 17.Figure 16
Comparison of optimal paths on Map 3. (a) S-T. (b) S1-T3. (c) S2-T3. (d) S3-T4.
(a)(b)(c)(d)Figure 17
Comparison of evaluation indicators on Map 3. (a) The best path length comparison. (b) The worst path length comparison. (c) Average path length comparison. (d) Average computing time comparison. (e) Average iterative convergence time comparison. (f) Standard deviation comparison.
(a)(b)(c)(d)(e)(f)It can be observed from average path length, computing time and iterative convergence time in Figures13 and 15 that IFOA is superior in the test environments. To check whether the algorithms are statistically different or not, the t-test is performed. The level 0.05 of significance is considered and shown in Table 2. The results indicate that IFOA outperforms all other methods in all test environments, because the p values are smaller than the level 0.05 of significance.Table 2
Comparison oft-test between IFOA, FOA, and ACA (significant difference is represented by “+”).
Map 1IFOAFOAACARRTS-T—7.50e − 05(+)3.51e − 07(+)3.51e − 09(+)S1-T2—1.14e − 03(+)1.04e − 06(+)5.18e − 11(+)S2-T2—1.68e − 05(+)8.17e − 07(+)6.93e − 06(+)S3-T1—7.90e − 04(+)1.43e − 05(+)1.12e − 13(+)Map 2IFOAFOAACARRTS-T—3.68e − 04(+)4.56e − 06(+)9.42e − 11(+)S1-T2—6.12e − 05(+)2.92e − 06(+)1.19e − 06(+)S2-T1—8.74e − 05(+)5.56e − 07(+)7.96e − 09(+)S3-T3—4.89e − 04(+)8.87e − 07(+)6.33e − 12(+)Map 3IFOAFOAACARRTS-T—6.17e − 05(+)5.32e − 03(+)4.50e − 09(+)S1-T3—1.87e − 03(+)1.62e − 04(+)1.93e − 12(+)S2-T3—3.68e − 07(+)4.68e − 05(+)7.53e − 08(+)S3-T4—5.41e − 05(+)3.43e − 03(+)5.69e − 05(+)The solid line is the IFOA, the dotted dashed line is the FOA, the dotted line is ACA, and the chain line is RRT.From Figures12 to 15, it can be seen that the path planned by IFOA is significantly better than FOA, and the smoothness of the path is also greatly improved. The path planned by IFOA is better than FOA planning. Although the path of ACA is short, the computing time is twice that of IFOA, and it converges after 40 times. Compared with RRT, IFOA has significant advantages in the path length and path smooth computing time. It can be seen from the eight sets of simulation experiments that, based on the improved fruit fly optimization algorithm (IFOA), the relative path has the fastest convergence speed, and the path obtained is better and smoother than FOA. In addition, it can be seen from the comparative test that the computing speed and convergence times of IFOA are better than those of ACA. The algorithm converges to the best in the number of iterations before 25 times. Compared with an enhanced genetic algorithm [37], the improved Maklink graph is more suitable for complex environment. Compared with the improved particle swarm optimization [38], the convergence times of IFOA are the third of it; however, the convergence speed of IFOA is too fast to find the optimal solution. In [39], the authors proposed an improved version of fruit fly optimization (FOA) to solve the path planning problem. It solves the problem that the convergence speed of FOA is too fast; however, the amount of calculation is too high.It proves the feasibility of using the IFOA to plan the return charging path of the cleaning robot, which can make the path without collision with obstacles and the shortest. It is guaranteed that the robot should choose the shortest path to the charging location under the condition of limited power.


## 6. Conclusions

Through eight sets of comparative experiments and analysis, the effectiveness and practicability of the proposed IFOA method are proved. The cleaning robot can return to the charging location as soon as possible without colliding with obstacles in a complex industrial environment. Through comparative experiments, it can be seen that the original algorithm has been greatly improved. The path obtained is not the shortest path, but the calculation time is shorter than other algorithms.There are also many possible avenues for future work. First, we will study how to plan a path for dynamic obstacle avoidance when the environment is unknown [40]. Second, we will combine IFOA with other algorithms to shorten the path length. Furthermore, we will consider the path planning problem when multiple cleaning robots charge [41].



---

*Source: 5558096-2021-09-08.xml*