# Application of Artificial Intelligence Computer Intelligent Heuristic Search Algorithm

Authors: Fanghai Gong
Journal: Advances in Multimedia
 (2022)

---

## Abstract

In order to transform three-dimensional space path planning into two-dimensional plane path planning problem and greatly reduce the search time, an intelligent heuristic search algorithm based on artificial intelligence is proposed. The heuristic search algorithm is analyzed and introduced, and A is chosen. A two-dimensional spatial environment model of picking robot path planning is investigated, and a spatial model of picking robot path planning is established by raster method. Then, considering the whole day operation time, the whole day operation time is divided into several periods. With the help of heuristic search algorithm, the most reasonable operation time interval of each period is found, so as to provide reliable reference for the decision-making organization of urban rail transit operation on how to arrange the train rationally. The experimental results show that the improved A∗ algorithm can significantly improve the moving path of the picking robot and make the planned path smoother, which confirms the feasibility and superiority of the improved algorithm. The operation decision of urban rail transit is obtained through experiments. After 114 iterations of the heuristic search algorithm, the optimal value is 6.83353635e-001, while the average optimal value is 6.83551939e-001. After 231 iterations of particle swarm optimization algorithm, the optimal value is 6.83650785e-001. The average optimal value is 6.83745935e-001. After 789 iterations, the genetic algorithm obtains the optimal value of 6.83921100e-001, and the average optimal value is 6.84410765e-001. Through the comparative analysis, it can be seen that compared with the other two optimization algorithms, the heuristic search algorithm is significantly better than the other two optimization algorithms, both in terms of the optimal value and the number of optimization iterations. The results show that the heuristic search algorithm is a fast, accurate, and reliable optimization method to solve the problem of accurate scheduling of urban rail transit departure interval. It is proved that the intelligent heuristic search algorithm of artificial intelligence computer can realize the path planning effectively.


---

## Body

## 1. Introduction

Artificial intelligence (AI) was born in the middle of the 20th century and has experienced two important processes of ups and downs. As one of the most cutting-edge technologies in the 21st century, the major breakthrough of the artificial intelligence technology will affect the new round of industrial revolution [1]. At present, it has been widely used in medicine, education, research, and other fields. Now the problems facing artificial intelligence are more and more complex, most of which are unstructured problems. In the past, the blind search needs to search all nodes and consumes a lot of time, which will seriously limit the search ability. The reason lies in taking into account all possibilities, namely, to search blindly one by one. To solve this problem, one needs to use knowledgeable generators to avoid paths that are obviously impossible to search for the correct answer, called heuristic search. Heuristic search has become an important tool to solve intelligent programming problems, especially uncertain programming problems. In recent years, the exploration of relaxation planning in graph planning problems and the heuristic research based on single valued variables have all promoted the exploration of heuristic search. Using heuristic search thinking to construct problem solutions has become a common way of thinking, such as maximum weight independent set problem and universal shared cycling problem [2]. Heuristic search combined with fuzzy logic and spectrum allocation accelerates the development of search in many fields. At the end of the day, people want the search path to go in the direction they think is promising, so that the search time can be significantly reduced. The research first traces the research starting point and then discusses the heuristic search and its heuristic ability from the source to the application of man-machine war [3].


## 2. Literature Review

Li et al. believed that with the rapid development of computer technology, artificial intelligence had made great progress in more than 40 years since it was formally proposed in 1956 and had become a broad interdisciplinary and frontier science [4]. Mo et al. believe that search engines evolved from search algorithms. The search algorithm is specifically the search algorithm of soul return. It can be seen from the analysis that the search algorithm is very powerful, and many people can search for the results they want in many specific situations. In the search of the search algorithm, when people walk by in the search, if they want to pass this place, they cannot go any further, which shows that the algorithm is only a theoretical work and not much applied in practice [5]. Goh believes that a lot of research involves revisiting certain places. When creating an algorithm, it uses a “system” search, which leads to certain conditions. In this way, based on the original algorithm, the performance is very good [6]. According to Zhao et al.’s maze algorithm, when a traveler arrives at a location, they start searching around that location. The road is simple and not many. In the developed algorithm, this situation is identified, and the idea of searching multiple locations with different physical locations in a sequence is proposed [7]. According to Huang et al., research is a lifelong habit. So, if we can study and find out what they have in common and then simulate them on the computer and find a way to solve them, that is very important [8]. Chen et al. believe that research based on search engine optimization (an important branch of artificial intelligence) is based on the initial state of the system. The type of work of each member of the system, the right work, determines the desired goal. Because of its importance in terms of performance, it has attracted the interest of many experts and researchers [9]. Huang C and Huang Y argue that the pursuit of intelligence has come a long way in the past 40 years since the discipline was born in 1956, with competition and research ranging widely [10]. Yin et al. believed that intelligent search was already at the forefront of computer science. However, AI-based search technology was not perfect. First of all, although the application scope of search technology was very wide, they all operated independently, and there was no unified internal model. This made it difficult to concretize this widely applicable technology. Also, common search algorithms search for a certain point that was “gone and never returns.” That is, after visiting a certain point, it was difficult to return to that point from somewhere when actually needed. Path planning for mobile robots had been proven to be NP-hard in environments with complex obstacles [11]. Chai et al. proposed the method of quantum particle swarm optimization (Q particle swarm optimization) to solve the path planning problem of UAV avoiding obstacles in three-dimensional space. The space was modeled in a continuous manner. As a deterministic search algorithm, A∗ algorithm combined the characteristics of heuristic and shortest path search and had been successfully applied to various scheduling, automatic driving, circuit configuration, and other problems [12]. Becker et al. combined the A∗ algorithm with the ant colony algorithm and used the ant colony algorithm to optimize the shortest loop connecting multiple target points in three-dimensional space, similar to solving the traveling salesman problem. However, the shortest path between two target points was still implemented using the A∗ algorithm. Some scholars proposed a fast expanding tree algorithm to solve the path planning problem in an unknown continuous space. However, because the tree structure was too large and the tree nodes were randomly generated, it was difficult to search for a path in an environment containing narrow channels, resulting in a long shortest path [13].On the basis of the current research, in order to transform the three-dimensional space path planning problem into a two-dimensional plane path planning problem and greatly reduce the search time, the research proposes an intelligent heuristic search algorithm based on artificial intelligence. The heuristic search algorithm is analyzed and introduced, and A is chosen. A two-dimensional spatial environment model of picking robot path planning is studied, and a spatial model of picking robot path planning is established by raster method. Then, considering the whole day operation time, the whole day operation time is divided into several periods. And with the help of heuristic search algorithm, the most reasonable operation time interval of each period is found, so as to provide reliable reference for the decision-making organization of urban rail transit operation on how to arrange the train rationally.


## 3. Heuristic Search Algorithm

### 3.1. Branch and Bound Method

First, let us start with a special and simple case. WhenH∗p=Hp=0, that is, Fp=Gp, this is the condition that the simple branch and bound method satisfies. In this method, the path with the shortest distance is selected first, and the node expansion is carried out with the least distance as the goal. This method will also discard some nodes that are impossible to get the optimal solution, so as to shorten the search path distance. Figure 1(a) is the binary tree to be searched, and Figure 1(b) means that the search starts from the starting node A, but fails to reach the destination, so the search continues down and expands node A to get B and C [14]. In Figure 1(c), it is found that the path distance to B is short and the destination is not reached. It continues to expand B node to search for D and E. Similarly, it continues to expand to Figure 1(e). At this time, a path to the destination has been searched, and its distance is 16. Since there may be other paths that are less distant than 16, it will continue to extend the current distance to the point C that costs the least (it will follow the rule of starting from the right under equal costs). Until all paths whose distance may be smaller than 16 are searched, as shown in Figure 1(f), the path with the shortest distance is finally found [15]. Although the simple branch and bound method satisfies the condition that heuristic search is acceptable in Definition 2, in practice, H∗P often has many changes, let alone can not be fixed to zero, so this method obviously has great limitations.Figure 1
Branch and bound method satisfyingH∗P=0.
(a)(b)(c)(d)(e)(f)


### 3.2. Two Improvement Methods of Branch and Bound Method

#### 3.2.1. Using the Branch and Bound Method with Low Valuation

It is easy to know that the above simple and pure branch and bound method has defects in the processing ofHp, so the method of underestimating Hp is used to improve the branch and bound method, that is, H∗p=underestimateHp. Obviously, this heuristic is also acceptable and is stronger than branch and bound without heuristic search ability [16]. As shown in Figures 2(a)–2(f), let the value inside the rectangle represent the low estimate of the node to the destination Goal. Starting from the root node, it is found that it is not a target node, then extend the root node. As shown in Figure 2(c), the values 20 (6+14) and 23 (15+8) of the two evaluation functions are obtained, and the smaller one is selected to continue to expand until a path to the target node is found [17]. As shown in Figure 2(e), then it continues to search that other distance may be shorter path. As shown in Figure 2(f), all nodes that can reach the shortest path are searched. The use of low valuations effectively improves the quality of search, which is more realistic. But in terms of search speed, it does not significantly improve.Figure 2
Branch and bound method of low valuation.
(a)(b)(c)(d)(e)(f)


#### 3.2.2. Branch and Bound Method Based on Shortest Path

According to real-life experience, if two or more paths reach the same node, only the distance from the path with the smallest consumption needs to be stored. The principle is illustrated by an abstract example. If it is required to travel from point S city to point D city, the branch and bound method for storing the shortest path is described, as shown in Figures3(a)–3(f).Figure 3
Branch and bound method based on optimal path.
(a)(b)(c)(d)(e)(f)Starting from point S, when faced with the choice of A and C, point C is chosen because the distance between point C is shorter, as shown in Figure3(c). After reaching point C, it can only go to point B, and the distance from point S is 2, as shown in Figure 3(d). Similarly, continue to point E, as shown in Figure 3(e). At this time, the distance from point S is 4 [18]. Then, expand the path with a smaller distance than 4, namely, S → A → B (in fact, there is another way S → A → C, based on the principle of higher priority after the choice of point B). When this distance reaches B, the distance to point S is 3; at this time, it is the second visit to point B. So according to the shortest path principle, the shortest distance to point B 2 is chosen [19]. That is, the shortest path S → A → B is guaranteed to be stored. This is similar to dynamic programming, namely, to record the nodes that have been visited. When the next time it continues to visit the same node, it only needs to find the minimum cost to reach a certain point in the nodes that have been visited to use. Although this method only optimizes the situation of reaching the same node, it has also been seen in many related path problems, such as express logistics optimization path problem and urban path planning problem.


### 3.3. A∗ Algorithm

The above two optimization strategies are proposed for the simple branch and bound method. If the advantages of the two are combined, it is A∗ algorithm. In the following, the classic three-digit problem will be used to illustrate the A∗ algorithm. Suppose that the low valuation adopted is the Manhattan distance, and the operator used in it (simply understood, operator is the operation of each step, and more specifically, it can be understood as the step of each step) is the movement of the space in four directions, up, down, left, and right, as shown in Figure 4 for specific examples [20].Figure 4
Three digital problems.In Figure4, the reason why Fp=2+4=6 of the three-digit block marked with ∗ is explained as follows. The three-digit block marked with ∗ has completed two operator operations from the starting point, so Gp=2. Compared with goal, the number 1 can reach the goal by moving down at least one step. Similarly, the numbers 2 and 3 are two and one steps, respectively, so the number of steps adds up to four, namely, H∗p=4. In addition, the ∗ digit block is in the same state as the starting digit block, so the path is optimized by comparing the shortest storage distance. It can also be observed that the convergence is sometimes faster when Manhattan distance is used as the search low valuation [21]. In fact, moving the space up and down and left and right is similar to walking down an alley that twists and turns like a square alley, so the Manhattan path is also known as the taxi path. Although A∗ algorithm is already a method with strong heuristic search ability, it sometimes has the shortcoming of too long search time due to too large search scope when facing multiple minimum path selection.


### 3.4. Application of Intelligent Heuristic Search Algorithm in Picking Robot

A∗ algorithm is an algorithm for optimal path planning in static road network, which can be applied to metric or topological configuration space. The A∗ algorithm adopts the heuristic search method of shortest path, and since each unit in the configuration space has value evaluation, it is defined as the optimal path algorithm, i.e.,
(1)fv=hv+gv.In formula (1), Hv is the distance from the cell to the target state; Gv is the length of the path from the start state to the destination state through the selected cell system. The actual number of cells reaching each neighbor is calculated by fv, and the cell with the smallest value of fv is selected as the next cell of the system [22]. The advantage of A∗ algorithm is that it can modify the standard distance or add another distance, and it has been applied successfully in the path planning of mobile robots. However, its results are not completely satisfactory and good, and its computation time is very long. For a global map with 60,000 cells, the A∗ algorithm requires more computations on the computer than lh, which is fatal for autonomously moving robots. Therefore, the ∗ water algorithm is needed for upgrading and optimization.The heuristic search function is(2)hn=2d1n+d2n−d1n,d1n≥d2n,2d2n+d1n−d2n,d1n<d2n,(3)d1n=n,x−g,x,(4)d2n=n,x−g,x.In functions (2), (3), and (4), d1n and d2n are the absolute values of the difference between the horizontal and vertical coordinates of the current node and the target node of the picking robot, respectively.The heuristic function distance calculation of the improved A∗ algorithm is shown in Figure 2.The improved A∗ algorithm will lead to the path not being the optimal solution when the heuristic information is too strong. In order to solve this problem, a coefficient a is added to the heuristic function hn, and the evaluation function of the improved A∗ algorithm is
(5)fn=gn+a⋅hn.The traversal algorithm is used to traverse and solve the nodes, and many solutions with different efficiency can be obtained. For example, there is a problem of path duplication when passing through node A6, so these subregions need to be considered [23]. In the research, evaluation functions are used to calculate and screen multiple solutions to ensure the optimization of path planning efficiency. The heuristic search algorithm introduces the heuristic information into the whole path planning stage, evaluates the path planning strategy by using the evaluation function, solves the best node under the evaluation condition, and then takes the solved point as the basis point to continue to solve the next node, so as to ensure the efficient search to the destination. The evaluation function in path search is expressed as
(6)Fn=Gn+Kn.In function (6), Fn is the evaluation function, Gn is the actual distance from the starting point to the current node, and Kn is the sum of the turning angles of the picking robot. Assuming that the starting point is xs,ys and the current position is xg,yg; the expression of Gn is
(7)Gn=∑i=0nxi−xg2+yi−yg2.Assuming that the energy consumed by thei-th turn is wi, the expression of the sum of the turning angles Kn is
(8)Kn=∑i=0nwi.The evaluation function is weighted to ensure that the weight ofGn is the largest, so as to ensure the highest efficiency of the entire path planning, and the weight of Kn is the second, which can greatly reduce the repeated paths.


### 3.5. Application of Intelligent Heuristic Search Algorithm in Urban Rail Transit

In the whole heuristic search optimization algorithm, three operations mainly include chemotaxis operation, replication operation, and migration operation. The entire optimization cycle of the algorithm includes three layers of loop operations, and the main workflow is shown in Figure5. In the whole cycle structure, from the inside to the outside, there are chemotaxis operation, replication operation, and migration operation, and these three operations are nested in each other [24].Figure 5
Flowchart of heuristic search algorithm.In the research of urban rail transit scheduling strategy, the key is to determine the reasonable departure interval, which is an NP-hard problem of multiobjective nonlinear comprehensive optimization. Due to its large function solution space, high variable dimension, and complex constraints, it is difficult for traditional nonlinear mathematical methods to complete its solution. Therefore, many scholars have proposed many solutions to this problem.


#### 3.5.1. Research on Scheduling Problems and Design of Mathematical Models

The average waiting cost of all incoming passengers at stationj at time period k is
(9)∑k=1K∑j=1Jukj×hmax+hmin2.In formula (9), ukj represents the total number of people waiting for the train at the station j in the k period. hmax and hmin are the upper and lower limits of the departure interval during the operation period, respectively.In periodk, the actual waiting time consumed by all waiting passengers at station j is
(10)∑k=1K∑j=1Jmk×ρkjΔtk×Δtk2.In formula (10), ρkjΔtk is the number of passengers getting on the bus at station j in the k period. Δtk/2 is the average waiting time of the passengers in the k period.The total number of departures in periodk is
(11)∑k=1Kmk.The average total number of departures throughout the day is(12)Tshmax+hmin/2.Therefore, through the weighted proportional coefficientsa and β, the interest relationship between the urban rail operating enterprise and the passengers is realized, so as to obtain the final objective function:
(13)minf=α×∑k=1kmkTs/hmax+hmin/2+β×α∑k=1K∑j=1Jmk×ρkjΔtk×Δtk/2∑k=1K∑j=1Jukj×hmax+hmin/2.The constraints on the full load rate of urban rail trains are(14)ωkj=∑k=1K∑j=1JukjQ∑k=1Kmk×100%,75%≤wkj≤120%.In formula (11), wkj is the full load rate of the train at station j in the period k, and Q is the rated passenger capacity of the carriage. The comfort constraints of urban rail passengers are
(15)η=1,wkj≤1,(16)η=f1,1<wkj≤1.2.


## 3.1. Branch and Bound Method

First, let us start with a special and simple case. WhenH∗p=Hp=0, that is, Fp=Gp, this is the condition that the simple branch and bound method satisfies. In this method, the path with the shortest distance is selected first, and the node expansion is carried out with the least distance as the goal. This method will also discard some nodes that are impossible to get the optimal solution, so as to shorten the search path distance. Figure 1(a) is the binary tree to be searched, and Figure 1(b) means that the search starts from the starting node A, but fails to reach the destination, so the search continues down and expands node A to get B and C [14]. In Figure 1(c), it is found that the path distance to B is short and the destination is not reached. It continues to expand B node to search for D and E. Similarly, it continues to expand to Figure 1(e). At this time, a path to the destination has been searched, and its distance is 16. Since there may be other paths that are less distant than 16, it will continue to extend the current distance to the point C that costs the least (it will follow the rule of starting from the right under equal costs). Until all paths whose distance may be smaller than 16 are searched, as shown in Figure 1(f), the path with the shortest distance is finally found [15]. Although the simple branch and bound method satisfies the condition that heuristic search is acceptable in Definition 2, in practice, H∗P often has many changes, let alone can not be fixed to zero, so this method obviously has great limitations.Figure 1
Branch and bound method satisfyingH∗P=0.
(a)(b)(c)(d)(e)(f)


## 3.2. Two Improvement Methods of Branch and Bound Method

### 3.2.1. Using the Branch and Bound Method with Low Valuation

It is easy to know that the above simple and pure branch and bound method has defects in the processing ofHp, so the method of underestimating Hp is used to improve the branch and bound method, that is, H∗p=underestimateHp. Obviously, this heuristic is also acceptable and is stronger than branch and bound without heuristic search ability [16]. As shown in Figures 2(a)–2(f), let the value inside the rectangle represent the low estimate of the node to the destination Goal. Starting from the root node, it is found that it is not a target node, then extend the root node. As shown in Figure 2(c), the values 20 (6+14) and 23 (15+8) of the two evaluation functions are obtained, and the smaller one is selected to continue to expand until a path to the target node is found [17]. As shown in Figure 2(e), then it continues to search that other distance may be shorter path. As shown in Figure 2(f), all nodes that can reach the shortest path are searched. The use of low valuations effectively improves the quality of search, which is more realistic. But in terms of search speed, it does not significantly improve.Figure 2
Branch and bound method of low valuation.
(a)(b)(c)(d)(e)(f)


### 3.2.2. Branch and Bound Method Based on Shortest Path

According to real-life experience, if two or more paths reach the same node, only the distance from the path with the smallest consumption needs to be stored. The principle is illustrated by an abstract example. If it is required to travel from point S city to point D city, the branch and bound method for storing the shortest path is described, as shown in Figures3(a)–3(f).Figure 3
Branch and bound method based on optimal path.
(a)(b)(c)(d)(e)(f)Starting from point S, when faced with the choice of A and C, point C is chosen because the distance between point C is shorter, as shown in Figure3(c). After reaching point C, it can only go to point B, and the distance from point S is 2, as shown in Figure 3(d). Similarly, continue to point E, as shown in Figure 3(e). At this time, the distance from point S is 4 [18]. Then, expand the path with a smaller distance than 4, namely, S → A → B (in fact, there is another way S → A → C, based on the principle of higher priority after the choice of point B). When this distance reaches B, the distance to point S is 3; at this time, it is the second visit to point B. So according to the shortest path principle, the shortest distance to point B 2 is chosen [19]. That is, the shortest path S → A → B is guaranteed to be stored. This is similar to dynamic programming, namely, to record the nodes that have been visited. When the next time it continues to visit the same node, it only needs to find the minimum cost to reach a certain point in the nodes that have been visited to use. Although this method only optimizes the situation of reaching the same node, it has also been seen in many related path problems, such as express logistics optimization path problem and urban path planning problem.


## 3.2.1. Using the Branch and Bound Method with Low Valuation

It is easy to know that the above simple and pure branch and bound method has defects in the processing ofHp, so the method of underestimating Hp is used to improve the branch and bound method, that is, H∗p=underestimateHp. Obviously, this heuristic is also acceptable and is stronger than branch and bound without heuristic search ability [16]. As shown in Figures 2(a)–2(f), let the value inside the rectangle represent the low estimate of the node to the destination Goal. Starting from the root node, it is found that it is not a target node, then extend the root node. As shown in Figure 2(c), the values 20 (6+14) and 23 (15+8) of the two evaluation functions are obtained, and the smaller one is selected to continue to expand until a path to the target node is found [17]. As shown in Figure 2(e), then it continues to search that other distance may be shorter path. As shown in Figure 2(f), all nodes that can reach the shortest path are searched. The use of low valuations effectively improves the quality of search, which is more realistic. But in terms of search speed, it does not significantly improve.Figure 2
Branch and bound method of low valuation.
(a)(b)(c)(d)(e)(f)


## 3.2.2. Branch and Bound Method Based on Shortest Path

According to real-life experience, if two or more paths reach the same node, only the distance from the path with the smallest consumption needs to be stored. The principle is illustrated by an abstract example. If it is required to travel from point S city to point D city, the branch and bound method for storing the shortest path is described, as shown in Figures3(a)–3(f).Figure 3
Branch and bound method based on optimal path.
(a)(b)(c)(d)(e)(f)Starting from point S, when faced with the choice of A and C, point C is chosen because the distance between point C is shorter, as shown in Figure3(c). After reaching point C, it can only go to point B, and the distance from point S is 2, as shown in Figure 3(d). Similarly, continue to point E, as shown in Figure 3(e). At this time, the distance from point S is 4 [18]. Then, expand the path with a smaller distance than 4, namely, S → A → B (in fact, there is another way S → A → C, based on the principle of higher priority after the choice of point B). When this distance reaches B, the distance to point S is 3; at this time, it is the second visit to point B. So according to the shortest path principle, the shortest distance to point B 2 is chosen [19]. That is, the shortest path S → A → B is guaranteed to be stored. This is similar to dynamic programming, namely, to record the nodes that have been visited. When the next time it continues to visit the same node, it only needs to find the minimum cost to reach a certain point in the nodes that have been visited to use. Although this method only optimizes the situation of reaching the same node, it has also been seen in many related path problems, such as express logistics optimization path problem and urban path planning problem.


## 3.3. A∗ Algorithm

The above two optimization strategies are proposed for the simple branch and bound method. If the advantages of the two are combined, it is A∗ algorithm. In the following, the classic three-digit problem will be used to illustrate the A∗ algorithm. Suppose that the low valuation adopted is the Manhattan distance, and the operator used in it (simply understood, operator is the operation of each step, and more specifically, it can be understood as the step of each step) is the movement of the space in four directions, up, down, left, and right, as shown in Figure 4 for specific examples [20].Figure 4
Three digital problems.In Figure4, the reason why Fp=2+4=6 of the three-digit block marked with ∗ is explained as follows. The three-digit block marked with ∗ has completed two operator operations from the starting point, so Gp=2. Compared with goal, the number 1 can reach the goal by moving down at least one step. Similarly, the numbers 2 and 3 are two and one steps, respectively, so the number of steps adds up to four, namely, H∗p=4. In addition, the ∗ digit block is in the same state as the starting digit block, so the path is optimized by comparing the shortest storage distance. It can also be observed that the convergence is sometimes faster when Manhattan distance is used as the search low valuation [21]. In fact, moving the space up and down and left and right is similar to walking down an alley that twists and turns like a square alley, so the Manhattan path is also known as the taxi path. Although A∗ algorithm is already a method with strong heuristic search ability, it sometimes has the shortcoming of too long search time due to too large search scope when facing multiple minimum path selection.


## 3.4. Application of Intelligent Heuristic Search Algorithm in Picking Robot

A∗ algorithm is an algorithm for optimal path planning in static road network, which can be applied to metric or topological configuration space. The A∗ algorithm adopts the heuristic search method of shortest path, and since each unit in the configuration space has value evaluation, it is defined as the optimal path algorithm, i.e.,
(1)fv=hv+gv.In formula (1), Hv is the distance from the cell to the target state; Gv is the length of the path from the start state to the destination state through the selected cell system. The actual number of cells reaching each neighbor is calculated by fv, and the cell with the smallest value of fv is selected as the next cell of the system [22]. The advantage of A∗ algorithm is that it can modify the standard distance or add another distance, and it has been applied successfully in the path planning of mobile robots. However, its results are not completely satisfactory and good, and its computation time is very long. For a global map with 60,000 cells, the A∗ algorithm requires more computations on the computer than lh, which is fatal for autonomously moving robots. Therefore, the ∗ water algorithm is needed for upgrading and optimization.The heuristic search function is(2)hn=2d1n+d2n−d1n,d1n≥d2n,2d2n+d1n−d2n,d1n<d2n,(3)d1n=n,x−g,x,(4)d2n=n,x−g,x.In functions (2), (3), and (4), d1n and d2n are the absolute values of the difference between the horizontal and vertical coordinates of the current node and the target node of the picking robot, respectively.The heuristic function distance calculation of the improved A∗ algorithm is shown in Figure 2.The improved A∗ algorithm will lead to the path not being the optimal solution when the heuristic information is too strong. In order to solve this problem, a coefficient a is added to the heuristic function hn, and the evaluation function of the improved A∗ algorithm is
(5)fn=gn+a⋅hn.The traversal algorithm is used to traverse and solve the nodes, and many solutions with different efficiency can be obtained. For example, there is a problem of path duplication when passing through node A6, so these subregions need to be considered [23]. In the research, evaluation functions are used to calculate and screen multiple solutions to ensure the optimization of path planning efficiency. The heuristic search algorithm introduces the heuristic information into the whole path planning stage, evaluates the path planning strategy by using the evaluation function, solves the best node under the evaluation condition, and then takes the solved point as the basis point to continue to solve the next node, so as to ensure the efficient search to the destination. The evaluation function in path search is expressed as
(6)Fn=Gn+Kn.In function (6), Fn is the evaluation function, Gn is the actual distance from the starting point to the current node, and Kn is the sum of the turning angles of the picking robot. Assuming that the starting point is xs,ys and the current position is xg,yg; the expression of Gn is
(7)Gn=∑i=0nxi−xg2+yi−yg2.Assuming that the energy consumed by thei-th turn is wi, the expression of the sum of the turning angles Kn is
(8)Kn=∑i=0nwi.The evaluation function is weighted to ensure that the weight ofGn is the largest, so as to ensure the highest efficiency of the entire path planning, and the weight of Kn is the second, which can greatly reduce the repeated paths.


## 3.5. Application of Intelligent Heuristic Search Algorithm in Urban Rail Transit

In the whole heuristic search optimization algorithm, three operations mainly include chemotaxis operation, replication operation, and migration operation. The entire optimization cycle of the algorithm includes three layers of loop operations, and the main workflow is shown in Figure5. In the whole cycle structure, from the inside to the outside, there are chemotaxis operation, replication operation, and migration operation, and these three operations are nested in each other [24].Figure 5
Flowchart of heuristic search algorithm.In the research of urban rail transit scheduling strategy, the key is to determine the reasonable departure interval, which is an NP-hard problem of multiobjective nonlinear comprehensive optimization. Due to its large function solution space, high variable dimension, and complex constraints, it is difficult for traditional nonlinear mathematical methods to complete its solution. Therefore, many scholars have proposed many solutions to this problem.


### 3.5.1. Research on Scheduling Problems and Design of Mathematical Models

The average waiting cost of all incoming passengers at stationj at time period k is
(9)∑k=1K∑j=1Jukj×hmax+hmin2.In formula (9), ukj represents the total number of people waiting for the train at the station j in the k period. hmax and hmin are the upper and lower limits of the departure interval during the operation period, respectively.In periodk, the actual waiting time consumed by all waiting passengers at station j is
(10)∑k=1K∑j=1Jmk×ρkjΔtk×Δtk2.In formula (10), ρkjΔtk is the number of passengers getting on the bus at station j in the k period. Δtk/2 is the average waiting time of the passengers in the k period.The total number of departures in periodk is
(11)∑k=1Kmk.The average total number of departures throughout the day is(12)Tshmax+hmin/2.Therefore, through the weighted proportional coefficientsa and β, the interest relationship between the urban rail operating enterprise and the passengers is realized, so as to obtain the final objective function:
(13)minf=α×∑k=1kmkTs/hmax+hmin/2+β×α∑k=1K∑j=1Jmk×ρkjΔtk×Δtk/2∑k=1K∑j=1Jukj×hmax+hmin/2.The constraints on the full load rate of urban rail trains are(14)ωkj=∑k=1K∑j=1JukjQ∑k=1Kmk×100%,75%≤wkj≤120%.In formula (11), wkj is the full load rate of the train at station j in the period k, and Q is the rated passenger capacity of the carriage. The comfort constraints of urban rail passengers are
(15)η=1,wkj≤1,(16)η=f1,1<wkj≤1.2.


## 3.5.1. Research on Scheduling Problems and Design of Mathematical Models

The average waiting cost of all incoming passengers at stationj at time period k is
(9)∑k=1K∑j=1Jukj×hmax+hmin2.In formula (9), ukj represents the total number of people waiting for the train at the station j in the k period. hmax and hmin are the upper and lower limits of the departure interval during the operation period, respectively.In periodk, the actual waiting time consumed by all waiting passengers at station j is
(10)∑k=1K∑j=1Jmk×ρkjΔtk×Δtk2.In formula (10), ρkjΔtk is the number of passengers getting on the bus at station j in the k period. Δtk/2 is the average waiting time of the passengers in the k period.The total number of departures in periodk is
(11)∑k=1Kmk.The average total number of departures throughout the day is(12)Tshmax+hmin/2.Therefore, through the weighted proportional coefficientsa and β, the interest relationship between the urban rail operating enterprise and the passengers is realized, so as to obtain the final objective function:
(13)minf=α×∑k=1kmkTs/hmax+hmin/2+β×α∑k=1K∑j=1Jmk×ρkjΔtk×Δtk/2∑k=1K∑j=1Jukj×hmax+hmin/2.The constraints on the full load rate of urban rail trains are(14)ωkj=∑k=1K∑j=1JukjQ∑k=1Kmk×100%,75%≤wkj≤120%.In formula (11), wkj is the full load rate of the train at station j in the period k, and Q is the rated passenger capacity of the carriage. The comfort constraints of urban rail passengers are
(15)η=1,wkj≤1,(16)η=f1,1<wkj≤1.2.


## 4. Experimental Results and Analysis

In the experiment, the movement area of the picking robot is set as a two-dimensional plane environment, assuming that the position and shape of all obstacles are known. Then, the two-dimensional planar environment modeling method is used to raster the mobile area of the picking robot, and 0 and 1 are used to mark the movable area and the obstacle area.MATLAB software is used to program and simulate Table1, a two-dimensional raster map is established, and the starting point and end point are set, as shown in Figure 6. The black area is the obstacle, the picking robot can not pass, the white area is the free space, and the picking robot can walk at will.Table 1
Comparison of optimization results of the three algorithms.
AlgorithmThe optimal valueAverage optimal valueThe number of iterationsHeuristic search algorithm6.83353635e-0016.83551939e-001114Particle swarm optimization algorithm6.83650785e-0016.83745935e-001231Genetic algorithm6.83921100e-0016.84410765e-001789Figure 6
2D grid simulation map.The simulation results of the picking robot path planning are shown in Figure7. It shows the path planning of the picking robot in the presence of complex obstacles and confirms that the improved A∗ algorithm can significantly improve the moving path of the picking robot and make the planned path smoother.Figure 7
Path planning simulation diagram.In the research, taking the newly opened urban rail line in a city as the optimization object, the actual operation data of working days and nonworking days are, respectively, taken to optimize the scheduling plan of the departure time interval. The passenger flow distribution diagrams are shown in Figures8 and 9.Figure 8
Distribution of incoming passengers at different time periods on nonworking days.Figure 9
Distribution of incoming passengers at different times on working days.Through the iterative calculation, the final average optimal value is obtained, which is compared with the optimization results of the standard particle swarm optimization algorithm and the genetic algorithm as shown in Table1.As shown in Table1, it is obtained through experiments that after 114 iterations of the heuristic search algorithm, the optimal value is 6.83353635e-001, and the average optimal value is 6.83551939e-001. The particle swarm optimization algorithm has undergone 231 iterations. Iteratively, the optimal value is 6.83650785e-001, and the average optimal value is 6.83745935e-001. After 789 iterations of the genetic algorithm, the optimal value is 6.83921100e-001, and the average optimal value is 6.84410765e-001. Through the comparative analysis, it can be seen that compared with the other two optimization algorithms, the heuristic search algorithm is obviously better than the other two optimization algorithms in terms of optimizing the optimal value and optimizing the number of iterations [25]. This shows that the heuristic search algorithm is a fast, accurate, and reliable optimization method in solving the problem of precise scheduling of urban rail transit departure intervals.


## 5. Conclusions

The A∗ algorithm is selected as the research object, and an improved method is proposed. The path planning method of automatic picking robot is investigated for establishing grid, dividing subregions, and smoothing the path. The MATLAB simulation results show that the improved A algorithm can significantly improve the moving path of the picking robot and make the planned path smoother, which confirms the feasibility and superiority of the improved algorithm. Considering the all-day operating period, the all-day operating period is divided into several periods, and the heuristic search algorithm is used to find the most reasonable operating time interval in each period, so as to provide a reliable reference for the urban rail transit operation decision-making agency to reasonably arrange departures. Heuristic search has been implemented in many fields, such as path planning and intelligent robots. However, in the future tasks such as intelligent planning, innovative breakthroughs in theory and practice are still needed, such as more accurate search cost functions and timely detection of current status by machines. It is foreseeable that with more efficient and relatively low-cost search strategies, many fields will be greatly promoted.



---

*Source: 5178515-2022-09-24.xml*