$$D\_l^+ = \sqrt{\sum\_{j=1}^n (r\_{lj} - r\_j^+)^2} \tag{18}$$

$$D\_i^- = \sqrt{\sum\_{j=1}^n (r\_{lj} - r\_j^-)^2} \tag{19}$$

Step 4: Calculate closeness.

$$G = \frac{D\_i^-}{D\_i^- + D\_i^+} \tag{20}$$

Step 5: Use the value of G as the evaluation result. The larger the value, the better the evaluation result, and the smaller the evaluation value, the worse the result.

## **4 Data Acquisition and Result Analysis**

#### **4.1 Data Acquisition**

**Network Topology Index.** During data processing, we merged the data of Beijing Capital Airport and Beijing Daxing airport as one node, and so did Shanghai. The data in this paper includes the data volume from March 1 to 7, 2021. For the strength index, the number of flights between airports in a week is selected as the weight for calculation. The calculation of the network topology index of each airline is shown in the following table.

**Table 1.** Main indicators of each airline

(*continued*)

**Table 1.** (*continued*)

**Fig. 4.** Main indicators of each airline

From Table 1 and Fig. 4, it can be seen that China Cargo Airlines, China Post Airlines and SF Airlines have a large number of nodes, indicating that they have opened routes in more airports, and Yuantong Airlines has the least number of nodes, that is, fewer airports have opened on their routes. The two indicators of degree and strength generally have the same trend. The more edges a node has on the network, the more flights may be allocated to the node. Therefore, the greater the degree of the node, the greater its strength. China Cargo Airlines, China Post Airlines and SF Airlines are all relatively large in degree and strength, while Jinpeng Airlines has the smallest degree and strength. In terms of clustering coefficient, China Cargo Airlines is the largest, indicating that a node in China Cargo Airlines network has a higher degree of correlation with its neighboring nodes, while Longhao and Yuantong airlines have the smallest clustering coefficient. The characteristic path length is an indicator reflecting the convenience of transmission. The smaller it is, the more convenient the transmission. In terms of the characteristic path length, China Post Airlines is the largest and Jinpeng Airlines is the smallest.

**Economic Index.** The analysis of the aircraft growth of the 6 Chinese cargo airlines from 2017 to 2020, using the average value as the analysis data.

**Table 2.** Aircraft growth of different Cargo Airlines

**Table 3.** Cargo and mail turnover of different cargo airlines in 2018

Unit: 10000 tons-kilometers

#### **4.2 Evaluation Results**

Combine Table 1, Table 2 and Table 3 to form the original matrix data.

**Table 4.** Original matrix data

The matrix is obtained according to the data in Table 4, and then the data is standardized to form a standard matrix to eliminate the impact of the difference between each index on the final result. The information entropy of each index is calculated by entropy weight method. As shown in Table 5.

**Table 5.** Information entropy of each index

As shown in Table 6, the weight of each index can be calculated according to the formula.

Through the evaluation of the TOPSIS method, the optimal solution and the worst solution are calculated as follows:

$$\begin{aligned} X^+ &= \{0.11250, 0.08173, 0.17024, 0.77991, 0.31670, 0.24085\} \\ X^- &= \{0, 0, 0, 0, 0, 0\} \end{aligned}$$

**Table 6.** The weight of each indicator

The final calculated ranking result are: China Cargo Airlines 0.339, SF Airlines 0.290, China Post Airlines 0.201, Jinpeng Airlines 0.185, Longhao Airlines 0.112 and Yuantong Airlines 0.111. Compared with the results only considering topology indicators, China Cargo Airlines, SF Airlines and China Postal Airlines are still ranked high, indicating that they are not only outstanding on existing networks, but also excellent in future network development.

#### **4.3 Sensitivity Analysis**

TOPSIS method does not consider the weight of each index when calculating, assuming that all indexes are equally important. Therefore, it cannot reflect the difference between the weight of existing network and future network characteristic indicators. The weight setting of network topology index and economic index is changed from 1:1 to 1:2 and then to 2:1, so as to further analyze the impact of weight change on each airline. These three weight changes represent that airlines pay more attention to the development of future network, pay equal attention to the current network structure and future network development, and pay more attention to the structure of existing network, which are expressed as the initial stage, growth stage and maturity stage of each airline.

**Initial Stage.** When the ratio is 1:2, it is the initial stage of the airline. And the weight is recalculated, as shown in Table 7 below.

**Table 7.** The weight of each indicator when the ratio is 1:2

The calculation results are arranged as follows: China Cargo Airlines: 0.589, SF Airlines: 0.520, Jinpeng Airlines: 0.312, China Post Airlines: 0.270, Yuantong Airlines: 0.172, Longhao Airlines: 0.171.

**Table 8.** The weight of each indicator when the ratio is 1:1

**Growth Stage.** When the ratio is 1:1, it is the growth stage of the airline. And the weight is recalculated, as shown in Table 8 below.

The calculation results are arranged as follows: China Cargo Airlines: 0.634, SF Airlines: 0.506, China Post Airlines: 0.410, Jinpeng Airlines: 0.382, Yuantong Airlines: 0.222, Longhao Airlines: 0.221.

**Mature Stage.** When the ratio is 2:1, it is the growth stage of the airline. And the weight is recalculated, as shown in Table 9 below.

**Table 9.** The weight of each indicator when the ratio is 2:1

The calculation results are arranged as follows: China Cargo Airlines: 0.719, SF Airlines: 0.628, China Post Airlines: 0.568, Jinpeng Airlines: 0.451, Yuantong Airlines: 0.275, Longhao Airlines: 0.273.

According to the above three tables, the results of each index under different weights are different. No matter at any stage, China Cargo Airlines and SF Airlines have outstanding performance, while China Post Airlines has caught up from behind. The results of growth and maturity stages are consistent with those of TOPSIS method.

## **5 Conclusions and Recommendations**

#### **5.1 Conclusions**

This paper uses network topology index and economic index to evaluate the current situation and development potential of the network, so as to effectively evaluate different freight airlines in China. From the analysis of network topology index, it is concluded that each airline has its own different characteristics, merit and demerit. China Cargo Airlines has the most connected cities and has the greatest advantages. It also performs well in terms of flight density and network accessibility. Sf Airlines has a large number of navigable cities, and the flight density of its routes is good, but poor network accessibility and inconvenient transfer. Although China Post Airlines does not connect so many cities and has poor transit performance, the density of routes between the cities and airports that have already been connected is high, and the network connectivity is good. Jinpeng Airlines, Longhao Airlines and Yuantong Airlines are all connected to a relatively small number of airports. The network density of Longhao Airlines and Yuantong Airlines is general, but the network connectivity is not good. On the contrary, Jinpeng Airlines has the worst network density, but the connectivity is good, and the traffic between the two nodes is convenient. From the perspective of economic indicators, each airline has its own advantages and disadvantages, and only Longhao Airlines and Yuantong Airlines are relatively average.

### **5.2 Recommendations**

**Acknowledgement.** This work is supported by National Natural Science Foundation of China (71403225).

## **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

# **Exploration of Non-legacy Creative Product Development Based on Information Technology**

Kun Gao1(B) , Lijie Xun2, and Zhenlu Wu3

1 Chinese Song Art College, Guangdong Ocean University, Guangdong, China<EMAIL_ADDRESS>2 Changzhou Institute of Technology, Jiangsu, China 3 Software Engineering, Guangdong Ocean University, Guangdong, China<EMAIL_ADDRESS>
**Abstract.** With the development of The Times, the development of information technology is accelerating, rapidly into the life, learning in all fields. Under the background of information technology, the dissemination and development of intangible cultural heritage and the development of non-heritage products have been updated. Therefore, a new way of developing intangible cultural heritage should be set up to make it highly compatible with the development of cultural and creative products, so as to build a new development pattern of mutual promotion, integration and reciprocity between intangible cultural heritage culture and cultural and creative products. This paper analyzes the concept of non-heritage products and the value of the combination of intangible cultural heritage and cultural creation, and discusses the development strategy of non-heritage products based on information technology for reference.

**Keywords:** Information technology · Non-legacy products · Product experience · E-commerce platform · Intangible town

## **1 Introduction**

In the Internet era, the concept of "Internet Plus" has received unprecedented attention, especially when the concept of mass entrepreneurship and innovation is put forward. In this process, with the help of the "Internet plus" concept of compliance, different industries have achieved varying degrees of improvement. It can be said that the " +" in "Internet +" represents the infinite possibility of organic integration of information technology represented by Internet technology with different industries. In other words, relying on Internet thinking, in-depth innovation of industry development can be realized, and consumer experience and added value of products and services can be improved. By introducing the concept of "Internet +" into the field of intangible cultural heritage, the business structure of non-heritage creative products will be greatly changed, and the design mode, production mode and marketing mode of the industry will be reshaped, thus providing a better opportunity and path for the benign development of intangible cultural heritage culture.

## **2 Concept of Non-legacy Creation Products**

According to the Law of the People's Republic of China on Intangible Cultural Heritage, Intangible cultural heritage refers to "all kinds of traditional cultural expression forms handed down from generation to generation and regarded as part of their cultural heritage, as well as objects and places related to traditional cultural expression forms" [Zhu Bing. Main Content and System interpretation of Intangible Cultural Heritage Law of the People's Republic of China. China's Intangible Cultural Heritage, 2021(01): 6–14.] In the era of global integration, various cultures show a significant homogenization trend in the integration and collision, thus highlighting the uniqueness of intangible cultural heritage culture. Under the impact of the commodity economy, how to realize the better protection and national intangible cultural heritage is a realistic problem worthy of attention and thinking, how to grasp the social public cultural appeal, and in the process of implementation of heritage and its surrounding products and packaging, also is a key focal point question.

In recent years, with the continuous improvement of the national economic level, the social public is no longer satisfied with the rich material life, but attaches more importance to the rich spiritual world. Therefore, non-legacy products with unique forms of cultural expression and bearing unique cultural connotations have increasingly attracted the attention of the public. This consumption tendency also reflects the public's love and pursuit of a better spiritual life to a considerable extent. Different from ordinary commodities, non-heritage products are the design and creation inspiration that designers get from intangible cultural heritage. With unique visual symbols of regional culture as the design carrier, such cultural and creative products are endowed with profound cultural value connotation. Through the design, production and sales of non-heritage products, tourists can have a more profound sensory impression on intangible cultural heritage, and at the same time, it will help the inheritance and dissemination of intangible cultural heritage.

# **3 The Value of Combining Intangible Cultural Heritage with Cultural Creation**

Intangible cultural heritage is the outstanding cultural achievements created by the Chinese people of all ethnic groups in the long period of social practice, which can be regarded as an important representative of the manifestation of national culture. When we look at intangible cultural heritage, we can see that it not only shows the extraordinary memory, but also shows the unique national thinking and cultural thinking mode. It can be said that these characteristics are extremely scarce in the era of global integration and the serious homogenization tendency of culture. Each intangible cultural heritage project contains unique value, but due to the lack of effective communication channels, some outstanding intangible cultural heritage skills and traditional crafts are declining, and related non-inheritors and traditional craftsmen are facing the dilemma of no successor. How to combine the consumption habit and aesthetic orientation of contemporary people to make the ancient intangible cultural heritage enter the public life with a new attitude is the question of the era of intangible cultural heritage protection.

It should be noted that intangible cultural heritage originated from the agricultural era, so although it has attracted the attention of the public, it is incompatible with the inherent requirements of the commodity society. If this phenomenon cannot be dealt with and solved, it will inevitably lead to various difficulties in the process of non-inheritance.

Since the rise of cultural and creative industry, along with the trend of global integration, the industry has spread rapidly in different countries and regions, and in this process, it has connected with other industries based on its unique cultural form and operation mode. Figure 1 shows the operating income of China's cultural and creative industry from 2012 to 2019. It can be seen that the data is increasing year by year.

**Fig. 1.** Operating revenue of China's National Cultural Industry Enterprises (Chinese cultural and creative products) in 2021–2019. (The data comes from Ai Media website)

Culture is the foundation and carrier of cultural and creative industry, which can be called the source of cultural and creative industry. Non-legacy works are important forms of cultural expression. Through in-depth research and exploration of design materials by designers, intangible heritage will be ensured to become the design source and creative inspiration of non-legacy products. At the same time, non-legacy creation products and intangible cultural heritage are mutually reinforcing. The latter provides design and creation materials for the former, while the former provides communication carrier and opportunity for the latter.

## **4 The Development of Non-legacy Creative Products Based on Information Technology**

It has many advantages to develop non-legacy creative products based on information technology. We can take advantage of the information technology, and through careful investigation and research activities, realize the accurate grasp of user demand, to carry out the "Internet +" the papers and the product experience, relying on the digital technology to the depth development of papers and works, electric business platform was used to optimize the papers and product development, build a legacy town, set up corresponding technical team. Below, the author will combine their own understanding and understanding, respectively on the following aspects to talk about the development of non-legacy creative products based on information technology.

## **4.1 Accurate Grasp of Users' Demands Through Careful Research Activities**

Excellent wen gen products must be realized with precision to meet user demand, therefore, the formal product design development of the papers and, before the survey should be based on activities, realize to the demands of user research, the research content includes the user's age structure, professional distribution, gender, willingness to spend, consumption habits, consumer preferences, income level, etc., Only in this way can accurate analysis of user groups be achieved from the perspective of consumer psychology, thus providing scientific basis for the subsequent design and research and development of non-legacy creative products.

### **4.2 Developing the Experience of "Internet Plus" Non-legacy Creative Products**

In general, museums and art galleries are places for the exhibition of non-legacy products. Although these venues provide opportunities for the public to contact and understand non-legacy products, it should also be noted that some museums and art galleries are too serious about the display and exhibition of non-legacy products. This may cause the audience with the papers and psychological distance between products being expanded, leading to the audience hard to display and exhibition of papers and products to generate understanding and explore enthusiasm, for this reason, on the papers and the product display and exhibition, should be adhering to the "Internet +" thinking, with the aid of modern information technology to achieve visual display of the papers and the products, In this way, the charm of non-legacy creation products will be highlighted to the greatest extent, and the audience will have enthusiasm for appreciation and interest in exploration, so as to deepen their interest in intangible cultural heritage culture.

At present, with the development of information technology, modern information technology means such as VR and AR are improving day by day. The advantage of these modern information technology means is that they can break the limitation of time and space and create a scene organically combining virtual and reality, so that the audience can get a more intuitive appreciation experience. VR technology relies on computer technology, information technology and simulation technology to achieve, with the help of this technology, the audience can get a sense of immersion. AR technology can realize the deep integration of virtual information and the real world, and rely on the way of simulation processing, so that the audience can get an immersive sensory experience.

For example, in the fourth Non-heritage Expo, designers showed the intangible heritage lifelike to every audience through the application of VR technology and AR technology, so that every audience got an audio-visual feast. The exhibition also relies on information technology to build a database covering a large number of traditional literature and art resources, and provides free query and download services for the public. For example, when weifang kite is displayed with VR technology and AR technology, the intuitive display of kite making process can be realized, and the legend of kite origin can be displayed for the public with the aforementioned technology, and the audience can also experience the process of simulated kite flying. It can be said that such a comprehensive experience will leave a deep impression on the audience and generate a strong interest in non-heritage products and intangible cultural heritage culture in the process.

#### **4.3 Relying on Digital Technology to Realize the In-Depth Development of Non-legacy Works**

During the Shanghai World Expo, the China Pavilion used modern information technology to display the Riverside Scene at Qingming Festival. In this way, "Along the River During the Qingming Festival" is vividly and dynamically presented to the audience, thus making it the jewel of the China Pavilion during the World Expo. In recent years, the Palace Museum, Tencent and local museums have successively devoted themselves to the design and research and development of digital cultural and creative products. For example, relying on digital technology, the Palace Museum has produced cultural and creative products represented by Auspicious Signs in the Forbidden City, thus helping the public to have a more detailed understanding of the Palace Museum culture. This work is in the form of an APP. After the public installs this APP on their smartphones or tablets, they can appreciate various cultural relics of the Palace Museum with the help of information interaction technology. The mobile game APP "Search for Fairy" produced and launched by Tencent fully integrates traditional cultural elements in intangible cultural heritage, thus realizing the dissemination of traditional excellent culture in the form of game, and also giving young consumers, the target audience of mobile games, an opportunity to have an in-depth understanding of intangible cultural heritage and traditional culture.

#### **4.4 Optimize the Development of Non-legacy Creative Products by Using E-commerce Platforms**

Under the background of information technology, e-commerce platform plays an important role in the development of cultural and creative products. E-commerce platforms gather a large number of customer groups, which can further expand the customer group of non-legacy creative products, so that more young people can understand non-legacy creative products more conveniently and conveniently, and promote the publicity of non-legacy creative products.

In 2020, the number of videos related to national intangible heritage on Douyin increased by 188% year on year, and the cumulative broadcast volume increased by 107% year on year [Zhu Yinxia. Research on the communication effect of short videos of intangible heritage [D]. Nanchang University,2020.] E-commerce platforms have also brought huge sales for INTANGIBLE cultural heritage products. For example, Li Tinghuai, the representative inheritor of the national-level Ru porcelain firing technique, sold ru porcelain over 3 million yuan through Douyin e-commerce; Sun Yaqing, the representative inheritor of the state-level intangible cultural heritage fan-making technique, participated in more than 20 intangible cultural heritage e-commerce activities, with a total sales volume of more than 700,000 yuan. Visible, we can make full use of the advantage of electric business platform to optimize the papers and the product development. On May 3, for example, in 2021, in "trill 55 tide purchase season" "originality tide have fei" zone, trill electricity sale "shadow play printing T-shirt" and "yun" kite "condensed intangible craftsmanship in the two products, this is the trill genetic bearing electrical business hand in hand to the people, products, manufacturers such as power, together with the papers and the product. "Shadow play" printing T-shirt the papers and the products on sale in Japan, live trill platform, with the help of powerful propaganda trill platform, the once pushed on the papers and the product was a great success For young people who are keen on Douyin platform, they learn about Traditional Chinese shadow puppetry through watching live broadcast, enrich their knowledge, and deepen their understanding and appreciation of the history of national literature and art.

### **4.5 Build an Intangible Heritage Town and Set up a Corresponding Technical Team**

Intangible cultural heritage town is a town form formed in a certain space with the help of intangible cultural heritage resources, which has functions such as industry, town, human resources and culture. In such small towns, a large number of non-genetic inheritors are gathered. Relying on the guiding effect of policies, art practitioners are attracted to such small towns, thus achieving the benign interaction and in-depth communication between non-genetic inheritors and literary and art creators, and thus achieving the goal of attracting talents. A relatively successful example in this regard is Wutong Mountain Art Town, which greatly improves the creative vitality of non-legacy products by attracting art designers to enter and opening art studios.

### **Peroration**

Intangible cultural heritage is not only an important cultural heritage of the Chinese nation, but also a spiritual treasure belonging to the whole mankind and the whole world. It is not inherited, but the inheritance of traditional culture with a long history. In view of this, the protection of intangible cultural heritage is an important work. How to realize the effective inheritance and dissemination of intangible cultural heritage is related to the continuation of cultural blood. To do this, we need to do two things. First, regarding the protection and inheritance of intangible cultural heritage, relevant institutions should be aware of the significance and value of the "Internet+" concept for the protection and inheritance of intangible cultural heritage, and provide and create brand-new carriers for the protection and inheritance of intangible cultural heritage with the help of various modern information technology means. At the same time, the designers also shall be with the aid of modern information technology, as an effective way to design and research and development of papers and the product, in order to improve the papers and the products in the heart of the social public appeal, as a result, not only can achieve the purpose of the prosperity of socialist culture, will also realize the effective promotion of intangible culture, More importantly, the public will have a strong interest in intangible cultural heritage through the purchase and consumption of non-heritage products, thus contributing to better inheritance of intangible cultural heritage. Secondly, through the development of intangible cultural heritage + cultural creative products, it is an inevitable choice for non-inheritance and development to use non-heritage creative products to make intangible cultural heritage out of the minority and into life. Cultural and creative products are not only the embodiment of culture itself, but also a way of cultural inheritance. The integration of INTANGIBLE cultural heritage and cultural creation interprets the intangible cultural heritage culture and further promotes the development of art and culture. The intangible cultural heritage culture and cultural and creative products should be well integrated, with the help of products to spread traditional culture, constantly strengthen cultural confidence, promote noninherited inheritance and development, make Chinese traditional culture long lasting, and help intangible cultural heritage realize the dream of cultural inheritance.

**Acknowledgements.** This paper is the research result of zhanjiang Tourism "Non-legacy Creative Products" Development Strategy Research, project number: ZJ21YB18, which is the 2021 planning project of Philosophy and Social Sciences of Zhanjiang city, Guangdong Province.

# **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

# **Gait Planning of a Quadruped Walking Mechanism Based on Adams**

Gangyi Gao1(B) , Hao Ling2, and Cuixia Ou3

1 College of Mecanical Engineering, Jingchu University of Technology, Jingmen, Hubei, China<EMAIL_ADDRESS>
2 Suzhou Newcity Investment and Development Co., Ltd., Suzhou, Jiangsu, China 3 College of Mecanical Engineering, Hangzhou Dianzi University, Hangzhou, Zhejiang, China

**Abstract.** In this paper, the kinematics analysis and gait planning of quadruped walking mechanism are carried out. Firstly, a simplified four-legged mechanism model is established; then the kinematics of the walking mechanism is analyzed; On this basis, the gait planning of walking mechanism is studied, the forward motion (four step movement) gait is analyzed, the corresponding leg swing order of each gait is calculated; Finally, ADAMS software is used to simulate and analyze the gait planning.

**Keywords:** Quadruped mechanism · Motion analysis · Gait planning · Motion simulation

## **1 Introduction**

The research of quadruped robot began in 1960s.With the development of computer technology, it has developed rapidly since 1980s. After entering the 21st century, the application research of quadruped robot continues to extend from structured environment to unstructured environment, from known environment to unknown environment. At present, the research direction of quadruped robot has been transferred to the gait planning which has certain autonomous ability and can adapt to complex terrain. Based on the kinematics research of the quadruped mechanism, the gait of the walking mechanism is planned, and the corresponding leg swing sequence of the forward motion (four steps) gait is obtained. Finally, the gait planning is simulated and verified by ADAMS software, and good results are achieved.

# **2 Kinematic Analysis**

#### **2.1 Simplified Model**

In the initial kinematic analysis modeling of simplified model, it is not necessary to excessively pursue whether the details of the component geometry are consistent with the reality, because it often takes a lot of modeling time and increases the difficulty of kinematic analysis. The key at this time is to pass the kinematic analysis smoothly and obtain the preliminary results. In principle, as long as the mass, center of mass and moment of inertia of the simplified model are the same as those of the actual components. In this way, the simplified model is equivalent to the physical prototype. The simplified model is shown in Fig. 1.

**Fig. 1.** Simplized quadruped-leg robot model

### **2.2 Establish Coordinate System**

In order to clearly show the relative position relationship between the foot and the body of the walking mechanism and the three-dimensional space, three sets of coordinate systems are established, namely the leg coordinate system, the body coordinate system and the motion direction coordinate system.

**Fig. 2.** Body diagram and the coordinate of walking system

**Leg Coordinate System.** OLiXLiYLiZLi coordinate system is shown in Fig. 2, Coordinate origin OLi is the axis of rotation of the hip joint and the bar Li1 intersection; axis ZLi is downward along the rotation axis of the hip joint; axis XLi is in the leg plane and perpendicular to the axis ZLi; axis YLi is determined by the right-hand rule. Select ZLi down, the selection of downward is mainly to intuitively display the change of the height of the center of gravity. The walking mechanism has four legs. Therefore, there are four leg coordinate systems as shown in Fig. 3, i = 1,2,3,4.

**Fig. 3.** Body coordinate and leg coordinate system of walking mechanism

**Volume Coordinate System.** The body coordinate system is a coordinate system fixed on the body and moving with the movement of the walking mechanism. As shown in Fig. 3, a three-dimensional coordinate system ObXbYbZb is established. The coordinate origin Ob is located at the geometric center of the traveling mechanism; axis Xb starts from the coordinate origin, Along the horizontal direction of the body width of the traveling mechanism; Axis Zb vertical down; axis Yb is determined by the right-hand rule.

**Motion Direction Coordinate System.** Motion direction coordinate system when human beings walk, they always consider the difference between themselves and the target and how to move to reach the target. According to the thinking method of human walking, the motion direction coordinate system is established.OnXnYnZn. The establishment of the coordinate system of the motion direction system is as follows: The origin coincides with the origin of the volume coordinate system, axis Zn coincides with the axis Zb, axis Xn points in the direction of this movement,Yn is determined by the right-hand rule. This coordinate places the planner on the walking mechanism itself and thinks that the movement of the walking mechanism is equivalent to the movement of his own legs, which brings a lot of convenience to the gait planner. It not only reduces many transformations in walking and greatly reduces the amount of calculation, but also for the operator, the walking mechanism is equivalent to himself. How much is the difference between himself and the target, How to move to reach the target is clear in the eyes of the operator. The motion direction coordinate is set to solve the motion relationship between the quadruped walking mechanism and the environment. It has a certain relationship with the earth directly. It can also be said to be the geodetic coordinate system of a certain motion. It only works when the walking mechanism moves along a certain motion direction.

#### **2.3 Kinematic Calculation of Leg**

As shown in Fig. 2. The robot has three driving joints, that is, three degrees of freedom. The three joint angles are θi/αi/βi. The length of each rod is shown in Fig. 2. The position of the foot end in the leg coordinate system is *F*(*xFi*,*yFi*,*zFi*), axis *XLi* is always in the leg plane, *yFi* = 0.

**Forward Kinematics Calculation of Leg.** The forward kinematics of the leg calculates the forward kinematics of the leg, which refers to determining the position of the foot in the corresponding coordinate system according to the motion of the driving joint of the leg. The structural parameters and three joint angles of quadruped walking mechanism are shown in Fig. 3, foot end position:

$$\mathbf{x}\_{Fl} = l\_{l1} + l\_{l2}\cos\alpha\_l + l\_{l3}\cos(\beta\_l - \alpha\_l) \tag{1}$$

$$\mathbf{y}\_{\text{Fi}} = \mathbf{0} \tag{2}$$

$$\mathbf{z}\_{\rm Fi} = \mathbf{l}\_{\rm i3} \sin(\beta\_{\rm i} - \alpha\_{\rm i}) - \mathbf{l}\_{\rm i2} \sin \alpha\_{\rm i} \tag{3}$$

$$
\theta\_{\bar{\mathbf{i}}} = \theta\_{\bar{\mathbf{i}}} \tag{4}
$$

**Inverse Kinematics Calculation of Leg.** The inverse kinematics of the leg calculates the inverse kinematics of the leg, which refers to calculating the motion parameters of each driving joint of the leg according to the position of the foot in the coordinate system.

From Eq. (1):

$$\mathbf{x\_{Fi}} = \mathbf{l\_{i1}} + \mathbf{x\_{fi}} \tag{5}$$

$$\mathbf{x\_{fi}} = \mathbf{l\_{i2}} \cos \alpha\_{\mathbf{i}} + \mathbf{l\_{i3}} \cos(\beta\_{\mathbf{i}} - \alpha\_{\mathbf{i}}) \tag{6}$$

$$\mathbf{X}\_{\text{fi}}^2 + \mathbf{Z}\_{\text{Fi}}^2 = \mathbf{I}\_{\text{i2}}^2 + \mathbf{I}\_{\text{i3}}^2 + 2\mathbf{I}\_{\text{i2}}\mathbf{I}\_{\text{i3}}\cos\theta\_{\text{i}} \tag{7}$$

$$\cos \beta\_{\rm i} = \frac{(\mathbf{x}\_{\rm Fi} - \mathbf{I}\_{\rm i1})^2 + \mathbf{Z}\_{\rm Fi}^2 - \mathbf{I}\_{\rm i2}^2 - \mathbf{I}\_{\rm i3}^2}{2 \mathbf{I}\_{\rm i2} \mathbf{I}\_{\rm i3}} \tag{8}$$

ki = cos βi

$$
\beta\_l = \arccos k\_l \tag{9}
$$

from Eq. (3):

$$Z\_{\rm Fi} = -\sin\alpha\_{\rm i}(\mathbf{l}\_{\rm i2} + \mathbf{l}\_{\rm i3}\cos\beta\_{\rm i}) + \cos\alpha\_{\rm i}(\mathbf{l}\_{\rm i3}\sin\beta\_{\rm i})\tag{10}$$

$$\begin{split} \frac{\mathbf{Z}\_{\text{Fil}}}{\sqrt{(\mathbf{l}\_{\text{li}} + \mathbf{l}\_{\text{li}} \cos \beta \mathbf{i})^2 + (\mathbf{l}\_{\text{li}} \sin \beta \mathbf{i})^2}} &= -\frac{\mathbf{I}\_{\text{li}} + \mathbf{l}\_{\text{li}} \cos \beta \mathbf{i}}{\sqrt{(\mathbf{l}\_{\text{li}} + \mathbf{l}\_{\text{li}} \cos \beta \mathbf{i})^2 + (\mathbf{l}\_{\text{li}} \sin \beta \mathbf{i})^2}} \sin \alpha\_{\mathbf{i}} \\ &+ \frac{\mathbf{I}\_{\text{li}} \sin \beta \mathbf{i}}{\sqrt{(\mathbf{l}\_{\text{li}} + \mathbf{l}\_{\text{li}} \cos \beta \mathbf{i})^2 + (\mathbf{l}\_{\text{li}} \sin \beta \mathbf{i})^2}} \cos \alpha\_{\mathbf{i}} \end{split} \tag{11}$$

$$\begin{aligned} \sin\gamma\_{\mathbf{i}} &= \frac{\mathbf{I}\_{\mathbf{i}\mathbf{j}\sin\beta\_{\mathbf{i}}}}{\sqrt{(\mathbf{I}\_{12} + \mathbf{I}\_{13}\cos\beta\_{\mathbf{i}})^2 + (\mathbf{I}\_{13}\sin\beta\_{\mathbf{i}})^2}} \\ \cos\gamma\_{\mathbf{i}} &= \frac{\mathbf{I}\_{\mathbf{i}\mathbf{i}} + \mathbf{I}\_{13}\cos\beta\_{\mathbf{i}}}{\sqrt{(\mathbf{I}\_{12} + \mathbf{I}\_{13}\cos\beta\_{\mathbf{i}})^2 + (\mathbf{I}\_{13}\sin\beta\_{\mathbf{i}})^2}} \end{aligned}$$

$$\frac{\mathbf{Z}\_{\mathbf{F}\mathbf{i}}}{\sqrt{(\mathbf{I}\_{12} + \mathbf{I}\_{13}\cos\beta\_{\mathbf{i}})^2 + (\mathbf{I}\_{13}\sin\beta\_{\mathbf{i}})^2}} = -\sin\alpha\_{\mathbf{i}}\cos\gamma\_{\mathbf{i}} + \cos\alpha\_{\mathbf{i}}\sin\gamma\_{\mathbf{i}}$$

$$\sin(\gamma\_{\mathbf{i}} - \alpha\_{\mathbf{i}}) = \frac{\mathbf{Z}\_{\mathbf{F}\mathbf{I}}}{\sqrt{(\mathbf{I}\_{12} + \mathbf{I}\_{13}\cos\beta\_{\mathbf{i}})^2 + (\mathbf{I}\_{13}\sin\beta\_{\mathbf{i}})^2}}\tag{12}$$

$$\gamma\_{\rm i} - \alpha\_{\rm i} = \arcsin\left(\frac{\mathcal{Z}\_{\rm Fi}}{\sqrt{(\mathcal{I}\_{\rm I2} + \mathcal{I}\_{\rm i3} \cos \beta\_{\rm i})^2 + (\mathcal{I}\_{\rm i3} \sin \beta\_{\rm i})^2}}\right) \tag{13}$$

$$\alpha\_{\rm i} = \gamma\_{\rm i} - \arcsin\left(\frac{\mathbf{Z}\_{\rm FI}}{\sqrt{(\mathbf{I}\_{\rm I2} + \mathbf{I}\_{\rm i3} \cos \beta\_{\rm i})^2 + (\mathbf{I}\_{\rm i3} \sin \beta\_{\rm i})^2}}\right) \tag{14}$$

$$\gamma\_{\rm i} = \arcsin\left(\frac{\mathbf{I}\_{\rm i3}\sin\beta\_{\rm i}}{\sqrt{(\mathbf{I}\_{\rm I2} + \mathbf{I}\_{\rm i3}\cos\beta\_{\rm i})^2 + (\mathbf{I}\_{\rm B}\sin\beta\_{\rm i})^2}}\right)$$

#### **3 Analysis of Translational Gait of Walking Mechanism**

Gait refers to the movement process of each leg of the walking mechanism according to a certain order and trajectory. It is precisely because of this movement process that the walking movement of the walking mechanism is realized. The walking mechanism discussed in this paper is in a static and stable walking state, that is, at any time, the walking mechanism has at least three legs supported on the ground. This state belongs to the slow crawling of the robot.

#### **3.1 Static Stability Principle**

The static stability of multi legged robot refers to the stability that the robot does not flip and fall when walking and maintains the balance of the body. If the vertical projection of the center of gravity of the robot is always surrounded by polygons formed by alternating footholds, the robot is statically stable. If the center of gravity of the robot exceeds the stability range, the robot will lose stability. As shown in Fig. 5, legs 1, 3 and 4 are set as support legs, and O is the center of gravity of the robot. Triangular area ABC represents the stable area surrounded by three footholds of the robot. When the center of gravity o of the robot is located in this area, the robot is statically stable. If the center of gravity of the robot will exceed the stable area, it will lead to the instability of the robot. During static and stable walking, the vertical center of gravity of each part of the robot is required to always fall in the stable area, which makes the walking speed of the robot very slow, so it is called crawling or walking.

**Fig. 4.** Principle of the static stability **Fig. 5.** All the CFD of walking

mechanism

#### **3.2 Critical Direction Angle**

The critical direction angle ωc refers to the angle between the critical forward direction (CFD) of the walking mechanism and the axis *Xb* of the body coordinate system. The critical forward direction indicates the straight line direction formed by the vertical projection of the quadruped walking mechanism doing translational crawling along the diagonal at the current and next foothold, which is through the vertical projection of the center of gravity of the walking mechanism in a gait cycle. Therefore, as shown in Fig. 5, four critical directions can be obtained. These direction angles and axis *Xb* and axis *yb* of the body coordinate system divide the direction angle ω into eight regions to determine and select the leg swing sequence: 0 ≤ ω ≤ ωc1, ωc1 ≤ ω ≤ π/2,π/2 ≤ ω ≤ ωc2, ωc2 ≤ ω ≤ π, π ≤ ω ≤ ωc3, ωc3 ≤ ω ≤ 3π/2, 3π/2 ≤ ω ≤ ωc4, ωc4 ≤ ω ≤ 2π .

#### **3.3 The Swing Sequence of the Legs in the Translational Gait**

Taking one of the eight areas as an example, this paper expounds the selection process of leg swing sequence. According to the walking direction, the principle of total leg swing is to meet the principle of static stability of the walking mechanism. In addition, since the walking machine is symmetrically distributed and has a simple structure, when setting the swing sequence of legs, the stability of the walking mechanism is judged according to the position of the center of gravity of the walking mechanism. It is assumed that the traveling mechanism is at an angle with the X direction ω As shown in Fig. 6, the initial attitude of the walking mechanism is represented by a dotted line, the solid line represents the attitude of the walking mechanism after movement, and the dotted line represents the stable triangle formed by the support points of each foot of the walking mechanism. A gait cycle of the walking mechanism is divided into four stages. In each stage, one leg is lifted and dropped, and then the body moves. It is represented by four diagrams in Fig. 6 (a), (b), (c) and (d). If the step size of a gait cycle is s, the moving distance of the body in each stage is s/4.

As shown in Fig. 6 (a), the traveling mechanism moves s/4 along the direction angle ω, in which it moves along the X direction and along the Y direction. It can be seen that after the movement, the center of gravity of the body is in - P2P3P4 and - P1P2P4. It can be seen that both leg 1 and leg 3 can be lifted. However, considering that the stability

**Fig. 6.** Swinging leg selection of walking mechanism walk to the front

margin of leg 3 is greater than that of leg 1, leg 3 should be selected as the first swing leg.

As shown in Fig. 6 (b), after the leg 3 swings, the traveling mechanism moves s/4 again along the direction angle. If it moves S × cosω/4 and S × sinω/4 respectively along the X and Y directions, it moves cumulatively along the X direction S × cosω/2 and the Y direction S × sinω/2. According to the stability principle, only leg 4 can be selected as the second swing leg this time.

Similarly, the swing sequence of each leg of the walking mechanism in a gait cycle can be obtained when the walking mechanism moves at the direction angle in each area, as shown in Table 1.

**Table 1.** The legs' swing sequence in different walking direction

#### **3.4 The Swinging Sequence of Gait Legs with Fixed-Point Rotation**

In order to make the walking mechanism have greater mobility, it is necessary to further design the fixed-point rotation gait of the walking mechanism. The rotation angle conforms to the right-hand rule. When the traveling mechanism turns left γ > 0, when it turns right γ ≤ 0.

The swing sequence of the walking mechanism legs rotating around the geometric center of the walking mechanism is analyzed as follows:

As shown in Fig. 7, the selection of leg swing sequence is illustrated by taking the left turn of the body as an example. Because it rotates around the fixed point of the geometric center of the walking mechanism, the center of gravity of the body remains unchanged and is always at the geometric center of the body during the rotation. Assuming that the angle γ of a gait cycle is, a gait cycle of the walking mechanism is divided into four stages as shown in Fig. 7 (a), (b), (c), (d) and (e). The dotted line in the figure represents the stable triangle formed by the support points of each foot of the walking mechanism. The angle of each body rotation is. The solid line in figure (a) represents the initial attitude of the walking mechanism, the dotted line represents the attitude of the walking mechanism after a gait cycle, and the dotted line in Fig. 7 (b), (c), (d) and (e) represents the current attitude of the walking mechanism, The solid line represents the posture of the walking mechanism after a phase of gait rotation.

**Fig. 7.** Selection of swing leg for fixed-point rotation of traveling mechanism

The initial and final positions of the traveling mechanism are shown in Fig. 7 (a). Firstly, the initial posture of the walking mechanism is shown by the solid line in Fig. 7 (a). When the walking mechanism rotates to the left γ /4, it is feasible to lift any leg according to the stability principle. We select leg 4 as the first swing leg, as shown in Fig. 7 (b). After leg 4 swings, the posture of the walking mechanism is shown as the solid line in Fig. 7 (b). The traveling mechanism rotates to the left. According to the stability principle, only leg 2 can be selected as the second swing leg this time, as shown in Fig. 7 (c).

After leg 2 swings, the posture of the walking mechanism is shown by the solid line in Fig. 7 (c). The traveling mechanism rotates to the left γ /4 again. According to the stability principle, only leg 1 can be selected as the third swing leg this time, as shown in Fig. 7 (d).

After leg 1 swings, the posture of the walking mechanism is shown as the solid line in Fig. 7 (d). The traveling mechanism rotates to the left γ /4 again. According to the stability principle, only leg 3 can be selected as the fourth swing leg, as shown in Fig. 7 (e).

The final pose is shown by the solid line in Fig. 7 (e).

Similarly, the swing sequence of legs under fixed-point rotation gait is summarized in Table 2.

**Table 2.** The swinging sequence of gait legs rotating around a fixed point of the geometric center of the walking mechanism

## **4 Simulation (Take the Four Step Walking in Front as an Example)**

In order to verify the rationality of the mechanism design and gait planning of the walking mechanism, the simulation analysis is carried out by using UG and ADAMS software. After the simplified model of the walking mechanism is created in UG software, the model is imported into ADAMS software by using ADAMS/exchange module, and other environments (such as ground, etc.) are built in ADAMS software to form the large framework of the virtual prototype, and then the constraints and forces are applied to these components to establish the virtual prototype of the walking mechanism (Table 3).

**Table 3.** Motion planning of walking mechanism walking straight ahead (four steps)

#### **4.1 Determine Simulation Parameters**

According to the kinematics research of the walking mechanism, the size of the walking mechanism leg mechanism is substituted into the inverse kinematics calculation formula of the leg, and the rotation angle of each driving joint is calculated, as shown in Table 4.

**Table 4.** Rotation angle of each driving joint when walking straight ahead (four steps)

### **4.2 Simulation Result**

Input the parameters in Table 4 into the functions of each corresponding driver. The simulation process of the walking mechanism walking straight ahead is shown in Fig. 8.

**Fig. 8.** Screenshot of simulation process of walking mechanism walking straight ahead (four steps)

#### **4.3 Analysis of Simulation Results**

After simulation, the displacement of each point on the body of the walking mechanism along the axis Zn direction is small, that is, the movement of the platform is relatively smooth and stable on the whole. However, there are still some problems, such as slight deviation of the motion trajectory and instability of individual steps, which are summarized as follows (Fig. 9):

**Fig. 9.** Displacement curve of each point on the machine body along the axie Zn direction when the walking mechanism moves straight ahead (four steps)

**Acknowledgements.** Fund project: Hubei Provincial Department of Education Science Research Program Project (B2020196); Jingmen City Science and Technology Program Project (2020YFYB051).

## **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

# **Design and Implementation of Full Adder Circuit Based on Memristor**

Ning Tang1, Lei Wang1,2(B) , Tian Xia1,2, and Weidong Wu3

1 NARI Group Corporation / State Grid Electric Power Research Institute, Nanjing 211106,

China

<EMAIL_ADDRESS>
2 Nanjing University of Aeronautics and Astronautics, Nanjing 210000, China

3 North Information Control Institute Group Co., Ltd., Nanjing 211153, China

**Abstract.** In order to break through the traditional von Neumann architecture of computing and memory cell separation and speed up the computing speed, it is necessary to realize in memory computing, and memristor is an excellent carrier to realize in memory computing. Then, the development, principle, characteristics and application prospect of memristor are briefly introduced, and the characteristic curve of memristor is obtained by simulating the model of memristor. The principle and characteristics of memristor are explained more intuitively. Then, based on the memory resistor, the simple logic circuit design principle is described. The logic structure can be realized by using the memory resistor as the calculation element and adding a CMOS inverter, so as to realize the simple logic circuit. The paper designs the simple logic circuit including gate, gate, or gate by spice software, and simulates the circuit of gate, gate, gate, or gate. Then, based on the above logic gate, the circuit design of adder is carried out, the circuit diagram and design scheme are given, and the simple description and SPICE simulation are given. The design scheme is reviewed and summarized, its advantages and disadvantages are analyzed, and the optimization and improvement scheme is proposed.

**Keywords:** Full adder · Memristor · Logic computing

## **1 Introduction**

One-bit full adder is considered as an important case study of MRL (Memristor Ratio Logic) family [1]. The full adder consists of two half adder, while the half adder can be composed of an exclusive-OR gate and an AND gate. Based on the basic AND gate, OR gate and exclusive-OR gate, we can implement the circuit design of the adder [2].

In order to provide a standard cell design method, the standard cell is a NAND (NOR) logic gate. In a stable state, no current flows out from the output node because the output node of the AND (OR) logic gate is connected to the metal oxide semiconductor gate [3]. In this method, each standard cell needs to have two connections between the complementary metal oxide semiconductor layer and the memristor layer, one for intermediate level conversion and one for output. This method is robust, although it is inefficient in terms of power consumption and area compared with the optimized circuit. In the optimized circuit, CMOS phase inverter is applied only when signal recovery is needed or logic function needs signal inversion.

The research shows that for MRL logic family, linear memristor devices without current threshold is preferred, unlike other digital applications, which need threshold and nonlinearity [4–6]. Compared with nonlinear memristor devices, MRL gate based on linear memristor devices has faster speed, smaller size and lower power consumption. Memristor ratio logic series opens opportunities for additional memristor and complementary metal oxide semiconductor integrated circuits and improves logic density [7–11]. This enhancement can provide more computing power for processors and other computing circuits.

## **2 Design and Implementation of Adder Circuit Based on Memristor and Its SPICE Simulation**

The schematic diagram of one-bit full adder used in this case study is shown in Fig. 1 below. One-bit full adder consists of six OR logic gates based on memristor, three AND logic gates based on memristor and four complementary metal oxide semiconductor phase inverters.

According to the schematic diagram of adder circuit in Fig. 1, the circuit can be built by Hspice software for simulation. The adder calculation formula used in this paper is as follows:

$$S = A \oplus B \oplus C\_{IN} \tag{l}$$

$$C\_{OUT} = A \cdot B + A \oplus B \cdot C\_{IN} \tag{2}$$

**Fig. 1.** Schematic diagram of adder circuit

The practical meanings represented by each item in the above formula are: A stands for summand, B stands for addend, *CIN* stands for low carry, S stands for carry, C*OUT* stands for sum.

#### **2.1 Analysis of Simulation Results**

According to the circuit schematic diagram of adder shown in Fig. 1, simulation analysis is carried out by using Hspice. In this scheme, a voltage of 4 V (high level, i.e., 1) is applied to port A, a voltage of 0 V (low level, i.e., 0) is applied to port B, and a voltage of 3 V (high level, i.e., 1) is applied to C*IN* as an example to show the simulation results and analyze them.

The truth table of adder is shown in Table 1 below.

**Table 1.** Truth table of full adder

A voltage of 4 V (high level, i.e., 1) is applied to port A , and a voltage of 0 V (low level, i.e., 0) is applied to port B. The curve of voltage and time of node 1 after the first exclusive-OR gate is shown in the following Fig. 2. It can be seen that when a voltage of 4 V is applied to port A and a low level is applied to port B, the curve of voltage and time of node 1 after the first exclusive-OR gate is basically consistent with the curve of output voltage of exclusive-OR gate when a high level and a low level are input above.

**Fig. 2.** The curve of voltage and time of node 1 after the first exclusive-OR gate when a voltage of 4 V (high level, i.e., 1) is applied to port A , and a voltage of 0 V (low level, i.e., 0) is applied to port B.

When a voltage of 3 V (high level, i.e. 1) is applied to port C*IN* , the curve of output voltage and time of port S is shown in the following Fig. 3. It can be seen that the output voltage of port S decreases continuously from 0.2ns to 1.2ns, and the speed of taking effect is the fastest at 0.7s. In this period, it can be approximately considered that a high-level pulse voltage of 2 V is input from node 1 and a voltage of 3 V is applied to port C*IN* , and the change characteristic curve of the output voltage of port S is basically consistent with the output voltage curve of exclusive-OR gate when two high levels are input above. When 1.72 V is taken as the threshold voltage, the output voltage is equal to 1.72 V, which is regarded as the output low level (0).

**Fig. 3.** Curve of output voltage and time of port S

When a 3 V voltage (high level, i.e., 1) is applied to the C*IN* , the curve of the output voltage and time of port C*OUT* is shown in the following Fig. 4. It can be seen that the output voltage of port C*OUT* with 2.11 V remains stable at about 2.11 V during 0.2ns to 1.2ns, which can be regarded as an AND gate inputting a 2 V high level and a 3 V high level. Another AND gate inputs a 4 V high level and a low level, and the output voltages of the two AND gates can be regarded as high level (1) and low level (0) respectively, and then pass through an OR gate to obtain a curve. When 2.11 V is taken as the threshold voltage, the output voltage is equal to 2.11 V, which is regarded as the output high level (1).

**Fig. 4.** Curve of output voltage and time of port COUT

In other cases, the output level basically meets the requirements of the truth table of the adder, which will not be discussed in this paper.

## **3 Analysis and Improvement of This Scheme**

For the optimization method, when cascaded MRL gates based on memristor are connected, the current can flow from the output node to the input of the next logic gate. In this case, the currents flowing through two memristor devices of one gate are not equal, and the smaller current may drop below the current threshold of memristor devices, resulting in partial switching of logic gates. This phenomenon will reduce the output voltage and may cause the logic to fail after a single logic level.

One method to eliminate possible logic faults is to increase the voltage of high logic state to ensure that all currents in the circuit are greater than the current threshold of the device. The increase of voltage is limited by complementary metal oxide semiconductor process, because high voltage may lead to breakdown of complementary metal oxide semiconductor transistor (for example, drain and leakage of grid induction [12]), and also consume more power.

Another method to eliminate logic faults is to amplify signals with CMOS logic gate to prevent steady-state current leakage and perform signal recovery. In this case study, both methods are used. The voltage increases and the signal recovery is implemented by a complementary metal oxide semiconductor inverter. Note that these signal degradation problems are circuit-related, that is, the degree of signal degradation depends on the logic circuit structure and the parameters of memristor devices.

Memristor ratio logic is a hybrid complementary metal oxide semiconductor memory logic family. Compared with CMOS logic, this logic series uses less chip area. By using the standard cell library composed of NOR and NAND logic gates, the design workload of MRL circuit can be reduced. However, the standard cell limits the flexibility of the design process and the opportunity of saving area. Other optimization criteria, such as increasing the operating voltage and minimizing the number of connections between CMOS and memristor layer, are also possible.

# **4 Conclusion**

In this paper, a one-bit adder is designed with 18 memristors and 4 CMOS phase inverters. The circuit design diagram of the scheme is given, and the principle, design ideas and possible problems of the scheme are introduced. The designed full adder is simulated by Hspice software, and the output voltage values under various conditions are obtained and compared with the truth table. Then, according to the content of the design scheme, the advantages and disadvantages of the scheme are found out, and the shortcomings are optimized and improved.

**Acknowledgements.** This work is supported by the State Grid Corporation Science and Technology Project Funded "Key technology and product design research and development of power grid data pocket book" (1400-202040410A-0–0-00).

## **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

# **Multi-level Network Software Defined Gateway Forwarding System Based on Multus**

Zhengqi Wang1,2(B) , Yuan Ji1,2, Weibo Zheng1,2, and Mingyan Li3

1 NARI Group Corporation (State Grid Electric Power Research Institute), Nanjing, Jiangsu, China

<EMAIL_ADDRESS>
2 Nanjing NARI Information and Communication Technology Co., Ltd., Nanjing, Jiangsu, China

3 State Grid Henan Electric Power Research Institute, Zhengzhou, Henan, China

**Abstract.** In order to solve the problem that the data forwarding performance requirements of the security gateway are becoming higher and higher, the difficulty of operation and maintenance is increasing day by day, and the physical resource configuration strategy is constantly changing, a multi-level network software defined gateway forwarding system based on Multus is proposed and implemented. On the basis of kubernetes' centralized management and control of the service cluster, different types of CNI plugins are dynamically called for interface configuration, At the same time, it supports the multi-level network of kernel mode and user mode, separates the control plane and data plane of the forwarding system, and enhances the controllability of the system service. At the same time, the load balancing module based on user mode protocol stack is introduced to realize the functions of dynamic scaling, smooth upgrade, cluster monitoring, fault migration and so on without affecting the forwarding performance of the system.

**Keywords:** Software-defined · Kubernetes · Forward system · Multus

# **1 Introduction**

With the advancement of the construction of the Internet of things, the terminal equipment presents the development trend of large scale, complex structure and diverse types. The security services are facing many new problems [1]. First, the number of IOT network terminal equipment is increasing day by day, and the number of terminals is increasing exponentially. The requirements for the data forwarding performance of the border security gateway are becoming higher and higher. It is necessary to continuously expand and upgrade the equipment cluster, and the difficulty of operation and maintenance is increasing day by day. Second, with the continuous increase of security services, different types of services have different requirements for resources, resulting in the continuous dynamic change of the resource allocation strategy. The original gateway equipment of different types can not adapt to the dynamic changes of services, resulting in the shortage of resources for some services and a large number of idle resources for other services. Limited physical resources need to be allocated more effectively and reasonably.

The development of docker technology [2] has set off a new change in the field of cloud platform technology, which enables various applications to be quickly packaged and seamlessly migrated on different physical devices [3]. The release of applications has changed from a lot of environmental restrictions and use dependencies to a simple image, which can be used indiscriminately on different types of physical devices. However, container is only a virtualization technology, and simple installation and deployment is far from being able to be used directly. We also need tools to arrange the applications and containers on so many nodes.

Kubernetes [4] container cluster management platform based on docker has developed rapidly in recent years. It is an open source system for automatic deployment, expansion and management of container applications, which greatly simplifies the process of container cluster creation, integration, deployment and operation and maintenance [5]. In the process of building container cluster network, kubernetes realizes the interworking between container networks through container network interface (CNI) [6]. Different container platforms can call different network components through the same interface. This protocol connects two components: container management system (i.e. kubernetes) and network plugins (common such as flannel [7], calico [8]). The specific network functions are realized by plugins. A CNI plugin usually includes functions such as creating a container network namespace, putting a network interface into the corresponding network space, and assigning IP to the network interface [9].

For the gateway forwarding system, because it involves a large number of packet forwarding services, the underlying logic is mostly implemented based on the Intel DPDK (data plane development kit) [10] forwarding driver. DPDK's application program runs in the userspace, uses its own data plane library to send and receive data packets, bypasses the data packet processing of Linux kernel protocol stack, and obtains high packet data processing and forwarding ability at the expense of generality and universality. Therefore, for the virtualization deployment of gateway forwarding system applications, the selection of CNI plugins has strong particularity. The current mainstream CNI plugins are uniformly deployed by kubernetes management plane, and their management of network interface is based on Linux kernel protocol stack, which is not suitable for DPDK forwarding driven gateway business applications. In addition, the software defines that the gateway forwarding system is composed of data plane and control plane. The data plane is responsible for the analysis and forwarding of data packets based on DPDK forwarding driver, which belongs to performance sensitive applications. The control plane is responsible for receiving control messages and configuring the network system and various protocols. For control plane message, due to the small amount of data, the Linux kernel protocol stack can be used for communication during cluster deployment to obtain more universality. To sum up, when the software defined gateway forwarding system for cluster is deployed, it calls different CNI container network plugins to configure the network interfaces according to different use scenarios, and develops CNI network plugins based on DPDK forwarding driver for the corresponding DPDK forwarding interface, which are the two major problems to be solved urgently for such systems to support virtualization deployment.

In this paper, a multi-level network software defined gateway forwarding system based on Multus is proposed and implemented, and the CNI plugin and load balancing module based on DPDK network interface are implemented to ensure that the application performance based on DPDK is not affected. At the same time, for the control plane interface, because the kernel protocol stack is used to communicate with kubernetes, this paper constructs a multi-level network based on Multus, dynamically calls different types of CNI plugins for interface configuration, realizes the cluster deployment scheme compatible with kubernetes kernel protocol stack, and enhances the controllability of system services, It realizes the functions of dynamic scaling, smooth upgrade, cluster monitoring, fault migration and so on.

## **2 Design of Multi-level Network Gateway Forwarding System Based on Multus**

With the development of nfv technology, virtual network devices based on X86 and other general hardware are widely deployed in the data center network. These virtual network devices carry the software processing of many high-speed network functions (including tunnel gateway, switch, firewall, load balancer, etc.), and can deploy multiple different network services concurrently to meet the diversified, complex and customized business needs of users. OVS (open vswitch) [11] and VPP (vector packet processor) [12] are two virtual network devices widely used in industry.

OVS is an open multi-layer virtual switch, which can realize the automatic deployment of large-scale networks through open API interfaces. However, the definition of flow table rules is complex, which can be realized only by modifying its core software code, and its packet processing performance is not as good as that of traditional switches. VPP is an efficient packet processing architecture. The packet processing logic developed based on this architecture can run on a general CPU. In terms of packet processing performance, VPP is based on DPDK userspace forwarding driver and adopts vector packet processing technology, which can greatly reduce the overhead of data plane processing packets, and the comprehensive performance is better than OVS. Therefore, in the multi-level network software defined gateway forwarding system proposed in this paper, we choose VPP as its receiving and contracting management framework.

The overall architecture of the system is shown in Fig. 1, in terms of configuration management, it is mainly divided into the management of various gateway services and the management of container resources. The management of gateway service mainly includes business configuration management, policy management, remote debugging management, log audit management, etc. the business developer is responsible for packaging the management process into the container image of the business. When the service is pulled up, it can communicate with the master node to complete the business-related configuration. Container resource management is related to cluster deployment, mainly including deployment cluster management, resource scheduling management, service scheduling management, operation monitoring management, etc. this part of management is related to the operation status of service cluster. It is the basis for providing functions such as dynamic scaling, smooth upgrade, cluster monitoring and fault migration. Kubernetes cluster management framework is responsible for it. The secure service

**Fig. 1.** The overall architecture of the software-defined gateway forwarding system

process will be uniformly packaged as a business image and loaded into the host machine that can be deployed by the kubernetes management framework for scheduling by kubernetes. When you need to create or expand a certain type of service, you can create several service containers corresponding to the service in the host of the existing cluster. Similarly, when a certain kind of service resources are surplus and need to shrink, only a few service containers need to be destroyed. Compared with the traditional scheme of purchasing customized physical equipment at a high price and manually joining the network cluster, its cost and operation portability have been greatly improved. In the traditional kubernetes solution, Kube proxy component provides load balancing services for all business pods to realize the dynamic selection of traffic. Besides, we need a load balancing component based on DPDK user mode protocol stack, which will be introduced in Sect. 3.1.

The last module is the hardware network card driver responsible for sending and receiving data packets. The DPDK based userspace forwarding driver at the bottom of the VPP forwarding framework avoids two data copies from the user space of the traditional protocol stack to the kernel state by creating a memif interface, as shown in Fig. 2. Therefore, the network card responsible for forwarding traffic on the service data plane needs to load the DPDK forwarding driver, while the network card responsible for forwarding messages on the control plane can communicate through the kernel protocol stack. In the overall architecture shown in Fig. 1, the data plane network card and the control plane network card should adopt a multi-level network management scheme based on the Multus CNI plugin to meet the communication requirements of kubernetes cluster management and the high-speed forwarding requirements of various gateway service data packets.

# **3 Design of Core Components of Software Defined Gateway Forwarding System**

## **3.1 Design and Implementation of Load Balancing Module**

This paper proposes user mode load balancing DPDK-lb based on DPDK, which uses DPDK user mode forwarding driver to take over the protocol stack, so as to obtain higher data message processing efficiency. The overall architecture of DPDK-lb is shown in Fig. 3. DPDK-lb hijacks the network card, bypasses the kernel protocol stack, parses the message based on the user mode IP protocol stack, and supports common network protocols such as IPv4, routing, ARP, ICMP, etc. At the same time, the control plane programs dpip and ipadm are provided to configure the load balancing strategy of DPDK-lb. In order to optimize the performance, DPDK-lb also supports CPU binding processing, realizes the lock free processing of key data, avoids the additional overhead required by context switching, and supports the batch processing of data messages in TX/RX queue.

**Fig. 2.** Forwarding performance optimization of VPP memif interface

**Fig. 3.** Overall architecture of DPDK-lb load balancing

#### **3.2 Design and Implementation of Multi-level CNI Plugin**

Due to the gateway forwarding service based on VPP includes control message and data message, the data message runs in the user mode protocol stack, and all the above CNI plugins need to use the kernel protocol stack to analyze the data packet, so it can not meet the networking requirements of the data plane of the system. The control message is mainly used to update the service flow table and the distributed configuration management of kubernetes cluster. It is necessary to realize the cross host communication of pod in different network segments. Therefore, for the control plane, you can choose the mainstream CNI plugins that support overlay mode. As a result, in the software defined gateway forwarding system with the separation of control plane and data plane, the responsibilities of control plane and data plane are different, and the selection criteria of network plugins are also different. It is difficult to support the network communication of the system through a single CNI plugin. In order to meet the requirement of creating multiple network interfaces using multiple CNI plugins, Intel implemented a CNI plugin named Multus [13]. It provides the function of adding multiple interfaces to the pod. This will allow the pods connecting to multiple networks by creating multiple different interfaces, and different CNI plugins can be specified for different interfaces, so as to realize the separation control of network functions, as shown in Fig. 4.

Before using the Multus plugin, kubernetes container cluster deployment can only create a single network card eth0, and call the specified CNI plugin to complete interface creation, network setting, etc. When using Multus, we can create eth0 for the control plane of pod to communicate with the master node of kubernetes. At the same time, we can create net0 and net1 data plane network interfaces, and configure the data plane by using userspace CNI plugins to achieve cascade use of multi-level CNI plugins. Kubernetes calls Multus for interface management, and Multus calls the self-developed userspace CNI plugin to realize data plane message forwarding. In this way, it not only meets the separation of control plane and data plane required in the software defined gateway system, but also ensures that in the process of data plane message forwarding, the DPDK forwarding driver based on VPP completes the forwarding operation of data message without copying from operating system kernel state to userspace. To sum up,

**Fig. 4.** Comparison before and after using Multus

Multus' multi-level CNI plugin scheme is very applicable in the software defined gateway forwarding system.

**Fig. 5.** Software defined gateway experimental networking

#### **3.3 Design and Implementation of Userspce CNI Plugin**

In order to register the new service pod on load balancing, it is not enough to only use flannel to complete the control plane network configuration, but also rely on the userspace CNI plugin mentioned above. The plugin needs to complete two types of work: first, create several service interfaces on the local pod, assign the created interfaces to the corresponding IP, and then access the specific network on the host to ensure that the data plane traffic can reach. Second, after the interface is created in the pod, because the kernel protocol stack is not used, it is necessary to configure the interface in the VPP forwarding framework in the pod (such as completing memif port pairing, assigning memif port address, etc.), and connect the newly created interface to the current data plane container network. Memif interfaces created in VPP appear in pairs and communicate by sharing large page memory. Therefore, the memif interfaces in the pods will find two corresponding virtual memif interfaces on the VPP of the host. By using these two pairs of memif interfaces, we can realize the data plane communication from the host message to the service pod.

The traffic of the system cluster is shown in Fig. 5. Taking the working node as an example, the service pod creates three network interfaces, eth0 is used for control plane message communication with the master node, the network card is created and configured by flannel, and net1 and net2 are the two data plane network interfaces required by the service, which are created and configured by the userspace network plugin. All data packages (red in the figure) are taken over by the userspace protocol stack, which improves the overall data message processing capacity of the system. Flannel provides network services for control messages related to configuration and cluster management (blue in the figure), which realizes the functions of dynamic expansion, smooth upgrade, cluster monitoring, fault migration and so on.

## **4 Experimental Scheme and Results**

In this paper, we limit the resources of a single service pod to 1GB of large page memory. We will conduct three groups of comparative experiments. Firstly, we will compare and test whether there is a gap between the service capability provided by a single pod in the software defined gateway system and that provided by the traditional gateway device when it is limited to 1GB of available memory. Then, we will compare the maximum number of pods (16) run by a single physical device in the way of software defined gateway with the traditional way of running the service by a single device, so as to judge whether the performance of the original system is affected under the same hardware conditions after the introduction of kubernetes cluster management scheme. Finally, we will completely release the cluster system, no longer limit physical resources, and verify the overall performance and feasibility of the system. In the experiment, the connection request of real customers is simulated, and the number of access users is increasing. The overall resource consumption of the system is observed through the Prometheus component provided by kubernetes. The scheme comparison of the three experiments is shown in Table 1 and the results is shown in Fig. 6.

The experimental results are shown in Fig. 6. In the first group of experiments, 1GB memory can server about 7500 client terminals. When the number of clients reaches 7000, the connection failure begins to occur. The scheme provided in this paper is almost the same as that of traditional equipment. Therefore, the way of providing services through virtualization has no impact on the performance of the original service.In the second group of experiments, the scheme in this paper and the traditional single device begin to fail when the number of users is close to 110000. When the number of users is close to 120000, they can no longer accept more user access due to memory constraints. The overall performance of this scheme is not inferior to or even slightly better than that of the original single equipment. In the third group of experiments, when the number of users is close to 120000, the memory occupancy rate of each device in the cluster is about 50%. Eight pods are scheduled on each of the two nodes, and each pod provides services for nearly 7500 users. At this time, nearly 50% of the resources of the physical machine node can be used for the deployment of other services. When the number of clients continues to increase, kubernetes will continue to evenly allocate new resources on the two nodes and create new pods to provide services for more users. Until the number of users is close to 240000, the physical node tends to be saturated. However, the traditional single physical device can no longer provide services for so many users.

**Fig. 6.** Comparison of three groups of experiments

It can be seen that when the number of physical machines in the cluster continues to increase, the ability of the whole system to provide services will increase linearly. When the number of users decreases in a certain period of time, the physical machine resources are released and can dynamically provide services for other services. Therefore, the service provider only needs to ensure that the total amount of equipment for multiple services is sufficient. Since the peak usage of each service is different, the proportion of physical resources occupied by different services will be dynamically adjusted by kubernetes.

# **5 Conclusion**

In this paper, a multi-level network software defined gateway forwarding system based on Multus is proposed and implemented, and the CNI plugin and load balancing module based on DPDK network interface are implemented. The created gateway service container is based on VPP packet processing framework, and the corresponding DPDK interface can be created to associate with the host interface, It ensures that the packet processing efficiency of the data forwarding application based on DPDK is not affected. At the same time, for the control plane interface of the gateway forwarding system, because the kernel protocol stack is used to communicate with kubernetes, this paper constructs a multi-level network based on Multus, dynamically calls different types of CNI plugins for interface configuration according to the use scenario and attribute configuration of relevant interfaces, and realizes the cluster deployment scheme compatible with kubernetes kernel protocol stack, The controllability of system services is enhanced, and the functions of dynamic expansion, smooth upgrade, cluster monitoring, fault migration and so on are realized.

This paper was partly supported by the science and technology project of State Grid Corporation of China: "Research on The Security Protection Technology for Internal and External Boundary of State Grid information network Based on Software Defined Security" (No. 5700-202058191A-0–0-00).

# **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

# **An Improved Chicken Swarm Optimization Algorithm for Feature Selection**

Haoran Wang, Zhiyu Chen, and Gang Liu(B)

School of Computer Science and Engineering, Changchun University of Technology, Changchun 130012, Jilin, China<EMAIL_ADDRESS>
**Abstract.** In recent years, feature selection is becoming more and more important in data mining. Its target is that reduce the dimensionality of the datasets while at least maintaining the classification accuracy. There are some researches about chicken swarm optimization algorithm (CSO) applied to feature selection, the effect is extraordinary compared with traditional swarm intelligence algorithms. However, there is a complex search space in the challenging task feature selection, the CSO algorithm still has a default that quickly gets stuck in the local minimum problem. An improved chicken swarm optimization algorithm (ICSO) is proposed in this paper, which introduces the Levy flight strategy in the hen location update strategy and the nonlinear strategy of decreasing inertial weight in the chick location update strategy to increase the global search ability and avoid getting stuck in the local minimum problem. Compared with the other three algorithms on eighteen UCI datasets shows that the ICSO algorithm can greatly reduce the redundant features while ensuring classification accuracy.

**Keywords:** Chicken swarm optimization algorithm · Feature selection · Swarm intelligence algorithm

## **1 Introduction**

Feature selection problem, also named as feature subset selection problem, refers to the selection of N features in the range of the existing M features to optimize the system's specific objectives, thereby reducing the data dimension and improving the performance of learning algorithms. In recent years, with the development of big data, industrial internet, and financial data analysis, more and more high-dimensional datasets are used in various fields of information systems, such as financial analysis, business management, and medical research. The dimensional disaster brought about by high-dimensional datasets makes feature selection an urgent and important task.

Feature selection methods can be divided into filter, wrapper, embedded, and ensemble [1]. The filter feature selection algorithm and learning algorithm are not related to each other. All features are sorted by specific statistical or mathematical attributes, such as Laplacian scores, Constraint scores, Fisher scores, Pearson correlation coefficients, and finally, a subset of features is selected by sorting. The wrapper feature selection algorithm encapsulates the selected learner looks like a black box, evaluates the performance of the selected feature according to its predictive accuracy on the feature subset, and gets the better subset with search strategy to obtain an approximate optimal subset. The embedded feature selection algorithm is embedded in the learning algorithm, with the training process of the classification algorithm is over, a subset of features can be obtained, such as ID3, C4.5, CART, etc. The features used in training are the result of feature selection. The ensemble feature selection algorithm draws on the idea of ensemble learning, which trains multiple feature selection methods and ensembles the results of all feature selection methods to achieve better performance than a single feature selection method. By introducing Bagging, many feature selection algorithms can be improved to be the ensemble.

Swarm intelligence optimization algorithms are often used to solve the feature selection problem and achieved good results. For example, genetic algorithm (GA) [2], ant colony algorithm (ACO) [3], and particle swarm optimization algorithm (PSO) [4], and so on. The Chicken swarm optimization algorithm (CSO) [5] proposed in 2014 is a kind of swarm intelligence optimization algorithm, which is inspired by the foraging behavior of the flock, is obtained a good optimization effect by grouping and updating the population, and has been applied in some fields. Hafez et al. [6] proposed a new feature selection method by using the CSO algorithm as part of the evaluation function. Ahmed et al. [7] applied logistic and tend chaotic mapping to help CSO explore the search space better. Liang, et al. [8] proposed a hybrid heuristic group intelligence optimization algorithm for cuckoo search-chicken swarm optimization (CSCSO) to optimize the excitation amplitude and spacing between the excitation amplitude of the linear antenna array (LAA) and the array of arrays of the circular antenna array (CAA). CSCSO has better solution accuracy and convergence speed in the optimization of LAA and CAA radiation patterns.

In this paper, an improved chicken swarm optimization algorithm (ICSO) is raised, which brings in the Levy flight strategy in the hen location update strategy and the nonlinear strategy of decreasing inertial weight in the chick location update strategy to enhance the ability of global search and decrease the probability of the algorithm falling into a local minimum. There are 18 UCI datasets are applied to compare the of effectiveness the algorithm in this paper with the other 3 algorithms. It's apparent that the algorithm in this paper has huge advantages.

## **2 Chicken Swarm Optimization Algorithm (CSO)**

The chicken swarm optimization algorithm simulates the hierarchy of the chicken swarm and the competitive behavior in foraging. Within the algorithm, the chicken swarm is split into many subgroups, every as well as a rooster, many hens, and chicks. Completely different subgroups of the chicken swarm are subject to specific hierarchical system constraints, and there's competition within the foraging method. Positions of chickens are updated according to their respective motion rules. The behavior of chickens in the chicken swarm optimization algorithm is idealized with four rules, they are as follows:

i. The chicken swarm is divided into many subgroups, there are three types of chick in every subgroup: a rooster, several hens, and chicks.

Assuming that the search space is D-dimensional, the total number of chickens in the entire chicken swarm is N, the number of roosters is *NR*, the number of hens is *NH* , the number of chicks is *NC*, and mother hens is *NM* . Let *xt i*,*j* represents the position of the *i th* chicken, the t is the *t th* iteration, the j is the *j th* dimension searching space, where *i* ∈ (1, 2,...,*N*), j ∈ (1, 2,..., D), t ∈ (1, 2,..., T), the maximal iterative number is T.

(a) Rooster location update strategy. The roosters are the chickens with the best fitness value in the chicken swarm. The roosters with better fitness have the advantage over the roosters with poor fitness, so they can find food quickly than the roosters with poor fitness. At the same time can search for food on a larger scale in its position, realize the global search. Meanwhile, the rooters' location update is influenced by the location of other roosters randomly selected. The position update formulas of the rooster are as follows:

$$\mathbf{x}\_{i,j}^{t+1} = \mathbf{x}\_{i,j}^t \* \left(1 + Randn\left(0, \ \sigma^2\right)\right) \tag{1}$$

$$\sigma^2 = \begin{cases} 1, & \text{if } f\_l \le f\_k, \\ \exp\left(\frac{f\_k - f\_l}{|f\_l| + \varepsilon}\right), & \text{otherwise}, \end{cases} \, k \in [1, N], k \ne i \tag{2}$$

where *Randn* 0, σ2 obey a normal distribution with standard deviation σ. *k* is the index of a rooster randomly selected from the rooster group. *fi* is the fitness value of the corresponding rooster *xi*. ε is the smallest constant to avoid the divide 0.

(b) Hen location update strategy. The search ability of hens is slightly worse than that of the roosters. Hens search food following their group-mate roosters, so the location update of the hens is affected by the position of their group-mate roosters. At the same time, due to their food stealing and competition between them, other roosters and hens also affect the location update. The location update formulas of the hen are as follows:

$$\mathbf{x}\_{l,j}^{t+1} = \mathbf{x}\_{l,j}^t + S1 \ast Rand \ast \left(\mathbf{x}\_{r1,j}^t - \mathbf{x}\_{l,j}^t\right) + S2 \ast Rand \ast \left(\mathbf{x}\_{r2,j}^t - \mathbf{x}\_{l,j}^t\right) \tag{3}$$

$$S1 = \exp\left(\frac{f\_l - f\_{r1}}{abs(f\_l) + \varepsilon}\right) \tag{4}$$

$$S2 = \exp(f\_{72} - f\_l) \tag{5}$$

where Rand is a uniform random number between 0 and 1. *abs*(·) is an absolute value operation. *r*1 is the index of the rooster, and the *i th* hen search food following it. *r*2 is an index of the roosters or hens randomly chosen from the whole chicken swarm, and *r*1 = *r*2.

(c) Chick location update strategy. The chicks have the worst search ability. They follow their mother hen, and the search range is the smallest. The chicks realize the mining of the local optimal solution. The search range of the chicks is affected by the position of their mother hen, and their position update formula is as follows:

$$\mathbf{x}\_{l,j}^{l+1} = \mathbf{x}\_{l,j}^{l} + FL \ast \left(\mathbf{x}\_{m,j}^{l} - \mathbf{x}\_{l,j}^{l}\right) \tag{6}$$

where *m* is an index of the mother hen, and the *i th* chick follows it to search for food. *FL* is a random value selected in the range [0, 2], and its main role is to keep the chick searching for food rounding its mother.

### **3 Improved Chicken Swarm Optimization Algorithm (ICSO)**

Although the CSO algorithm can improve the population utilization rate through a hierarchical mechanism, the effectiveness of its location update method is low, which leads to a decrease in the overall search ability of the algorithm. Given this, this paper proposes an improved chicken swarm optimization algorithm (ICSO), which is based on the grouping idea of the CSO algorithm. The ICSO algorithm improves the position update method of the hens and the chicks respectively to enhance the algorithm's global search ability and decrease the probability of the algorithm falling into the local minimum.

#### **3.1 Hen Location Update Strategy of ICSO**

Levy flight is a strategy in the random walk model. In Levy flight, short-distance exploratory local search is alternated with occasional long-distance walking. Therefore, some solutions are searched near the current optimal value, which speeds up the local search; the other part of the solution can be searched in a space far enough from the current optimal value to ensure that the system will not fall into a local optimal [9, 10]. In the CSO algorithm, the number of hens is the largest in three types, so the hens play an important role in the entire population [11]. Inspired by this, the Levy flight search strategy is introduced to the hen location update formula, which can hold back falling into the local minimum while increasing the global search ability of the algorithm in a way. The improved location update formula of the hen is as follows:

$$\mathbf{x}\_{i,j}^{t+1} = \mathbf{x}\_{i,j}^t + \mathbf{S1} \ast \mathbf{R} \mathbf{and} \ast \left(\mathbf{x}\_{r1,j}^t - \mathbf{x}\_{l,j}^t\right) + \mathbf{S2} \ast \mathbf{R} \mathbf{and} \ast \mathbf{Levy}(\lambda) \otimes \left(\mathbf{x}\_{r2,j}^t - \mathbf{x}\_{l,j}^t\right) \tag{7}$$

where ⊗ is point-to-point multiplication. *Levy*(λ) is a random search path.

#### **3.2 Chick Location Update Strategy of ICSO**

In the CSO algorithm, the chicks only are affected by their mother hen, not by the rooster in the subgroup. Therefore, the location update information of the chicks only comes from their mother hen, and the location information of the rooster is not used. In this case, once the mother hen of a chick falls into the local optimal solution, the following chicks are easy to fall into the local optimal solution. Using a nonlinear strategy of decreasing inertial weight to update the position of the chick allows the chick to learn from itself while allowing the chick to be affected by the rooster in the subgroup, which can prevent the algorithm from falling into a locally optimal solution as soon as possible. The improved location update formulas of the chick are as follows:

$$\mathbf{x}\_{l,j}^{t+1} = \mathbf{w} \ast \mathbf{x}\_{l,j}^{t} + FL \ast \left(\mathbf{x}\_{m,j}^{t} - \mathbf{x}\_{l,j}^{t}\right) + C \ast \left(\mathbf{x}\_{r,j}^{t} - \mathbf{x}\_{l,j}^{t}\right) \tag{8}$$

$$
\omega = \omega \min \ast \left(\frac{\omega \max}{\omega \min}\right) \left(\frac{1}{1 + 10 \ast \frac{I}{\tau}}\right) \tag{9}
$$

where *w* is the self-learning coefficient of the chick, which is very similar to the inertial weight in particle swarm optimization algorithm. *wmin* is the minimum inertial weight, *wmax* is the maximum inertial weight, *t* is the current number of iterations, and *T* is the maximum iteration. Let *C* denote the learning factor, which means that the chick is affected by the rooster in the subgroup. *r* is the index of the rooster which is the chick's father.

#### **3.3 Experimental Results and Analysis**

To verify the effectiveness of the ICSO algorithm, a comparison experiment is set up. The algorithms in comparison are chicken swarm optimization algorithm (CSO), genetic algorithm (GA), and particle swarm optimization algorithm (PSO).

#### **3.4 Fitness Function**

Each particle in the chicken swarm corresponds to a solution of feature selection. The particles are coded by real numbers, as shown in Eq. (10). Each solution *X* contains *n* real numbers, and *n* represents the total number of features of the corresponding dataset, where each dimension *xi* represents whether to select this feature. To form a feature subset, it is necessary to perform a decoding process before decoding. The position of the particle can be converted into a subset of the following features:

$$\mathbf{X} = [\mathbf{x}\_1, \; \mathbf{x}\_2, \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; x\_n] \tag{10}$$

$$A\_{\rm d} = \begin{cases} 1, x\_d > 0.5\\ 0, else \end{cases} \tag{11}$$

where *Ad* represents the feature subset decoded from the *d*-dimension of each solution. *Ad* can be selected as 0 or 1, according to the value *xd* of the d-dimensional feature of the particle: if *Ad* = 1, it means that the d-dimensional feature is selected; otherwise, the dimensional feature is not selected.

The purpose of feature selection is to find a combination that has the highest classification accuracy and the smallest number of selected features. Although it is a combination, the classification accuracy is the first consideration. The fitness function is to maximize classification accuracy over the test sets given the train data, as shown in Eq. (12) at the same time keeping a minimum number of selected features.

$$Fitness(i) = \alpha \ast ACC(i) + (1 - \alpha) \ast \left(\frac{FeatureSum(i)}{FeatureAll}\right) \tag{12}$$

where α is a constant less than 1 and bigger than 0, which controlling the importance of classification accuracy to the number of selected features. The bigger the α, the more important the classification accuracy. *ACC*(*i*) is the classifier accuracy of the particle *i*. *FeatureSum*(*i*) is the number of features corresponding to the particle *i*. *FeatureAll* is the total amount number of features in the dataset.

### **3.5 Parameters Setting**

In this paper, all comparative experiments work on a PC that has 8GB of memory, and the programming environment is Python 3.8.5. Let set 50 is the population size, the α in the fitness function is set to 0.9999, 20 independent running experiments are performed on the datasets, and setting 500 is the maximum number of iterations. The KNN (K = 5) classifier is used to test the classification accuracy of the selection scheme corresponding to each particle. The hyperparameter settings of each algorithm are shown in Table 1. The information of the eighteen UCI datasets is described in Table 2. Most datasets are two-class, as well as there are multi-class datasets. It can be seen intuitively that the largest number of features is 9 and the lowest is 309 in datasets.

**Table 1.** Hyperparameter settings

**Table 2.** Datasets description

#### **3.6 Results and Analysis**

Table 3 shows the experimental results of the ICSO algorithm and the other three comparison algorithms on eighteen datasets. Where bold fonts represent the largest mean classification accuracy among all algorithms. It can be seen intuitively from Fig. 1 that the ICSO algorithm has obtained the best results on eighteen test datasets. And the mean accuracy of the ICSO algorithm is more excellent than the CSO algorithm, the mean accuracy of the CSO algorithm is more excellent than the PSO algorithm, the mean accuracy of the PSO algorithm is more excellent than the GA algorithm, the mean accuracy of the GA algorithm in feature selection is the worst. Through observation and calculation, the datasets with poor mean accuracy on full features, such as Wine, LSVT, Arrhythmia, etc., after the ICSO algorithm feature selection, the mean accuracy increases by 20% ~ 50%. Datasets with better mean accuracy on full features, such as Breast Cancer, WDBC, Zoo, etc., after the ICSO algorithm feature selection, the mean accuracy was improved by less than 10%. The experimental results fully verify the superiority of the ICSO algorithm.

**Table 3.** Mean accuracy for the different algorithms

**Fig. 1.** Mean accuracy line chart

Table 4 lists the mean features and dimension standard deviation of the four algorithms after feature selection for each dataset. It can be seen intuitively that, compared with the GA algorithm and the PSO algorithm, the CSO algorithm and the ICSO algorithm have obvious dimensionality reduction effects, and the dimensional standard deviation is low, indicating that the algorithm stability is relatively high. The experimental results directly verify that the ICSO algorithm has a strong superiority in eliminating redundant features, and can achieve better classification accuracy on datasets, while greatly reducing the number of redundant features.

**Table 4.** Mean and Std dimension after different algorithm feature selection

## **4 Conclusions**

Swarm intelligence optimization achieved good results in the feature selection problem. In the chicken swarm optimization algorithm, there is a weakness in that it is still easy to fall into the local minimum. To overcome this, this paper proposes an improved chicken swarm optimization algorithm. On the basis of the population grouping update mechanism of the CSO algorithm, the ICSO algorithm introduces the Levy flight strategy in the hen location update strategy and the nonlinear strategy of decreasing inertial weight in the chick location update strategy to enhance the algorithm's global search ability and decrease the probability of the algorithm falling into the local minimum. It can be seen from the experimental results that compared with the other three related algorithms, the ICSO algorithm can tremendously decrease the redundant features while ensuring classification accuracy in the feature selection.

# **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

# **A Method of UAV Formation Transformation Based on Reinforcement Learning Multi-agent**

Kunfu Wang, Ruolin Xing, Wei Feng, and Baiqiao Huang(B)

System Engineering Research Institute of China State Shipbuilding Corporation, BeiJing, China<EMAIL_ADDRESS>
**Abstract.** In the face of increasingly complex combat tasks and unpredictable combat environment, a single UAV can not meet the operational requirements, and UAVs perform tasks in a cooperative way. In this paper, an improved heuristic reinforcement learning algorithm is proposed to solve the formation transformation problem of multiple UAVs by using multi-agent reinforcement learning algorithm and heuristic function. With the help of heuristic back-propagation algorithm for formation transformation, the convergence efficiency of reinforcement learning is improved. Through the above reinforcement learning algorithm, the problem of low efficiency of formation transformation of multiple UAVs in confrontation environment is solved.

**Keywords:** Multi UAV formation · Formation transformation · Agent · Reinforcement learning

## **1 Introduction**

With the development of computer, artificial intelligence, big data, blockchain and other technologies, people have higher and higher requirements for UAV, and the application environment of UAV is more and more complex. The shortcomings and limitations of single UAV are more and more prominent. From the functional point of view, a single UAV has only part of the combat capability and can not undertake comprehensive tasks; From the safety point of view, a single UAV has weak anti-jamming ability, limited flight range and scene, and failure or damage means mission failure. Therefore, more and more research has turned to the field of UAV cluster operation. UAV cluster operation is also called multi UAV cooperative operation, which means that multiple UAVs form a cluster to complete some complex tasks together [1]. In such a multi UAV cluster, different UAVs often have different functions and play different roles. Through the cooperation among multiple UAVs, some effects that can not be achieved by a single UAV can be achieved. Based on the reinforcement learning algorithm of multi-agent agent, this paper introduces the heuristic function, and uses the heuristic reinforcement learning of multi-agent agent to solve the formation transformation problem of multi UAV formation in unknown or partially unknown complex environment, so as to improve the solution speed of reinforcement learning.

## **2 Research Status of UAV Formation**

With the limited function of UAV, facing the increasingly complex combat tasks and unpredictable combat environment, the performance of a single UAV can not meet the operational requirements gradually. UAV more in the way of multi aircraft cooperative operation to perform comprehensive tasks. Multi UAV formation is an important part of multi UAV system, and it is the premise of task assignment and path planning. But it has also been challenged in the dynamic environment of high confrontation, including: (1) the multi UAV formation constructed by the existing formation method can not be satisfied both in formation stability and formation transformation autonomy (2) When formation is affected, it is necessary to adjust, the formation transformation speed is not fast enough, the flight path overlaps and the flight distance is too long.

The process of multi UAV system to perform combat tasks includes: analysis and modeling, formation formation, task allocation, path allocation, and task execution. When encountering emergency threat or task change, there are formation transformation steps. Among them, the formation method of UAV is always used as the foundation to support the whole task. The formation control strategy of UAV is divided into centralized control strategy and distributed control strategy [2]. The centralized control strategy requires at least one UAV in the UAV formation to know the flight status information of all UAVs. According to these information, the flight strategies of all UAVs are planned to complete the combat task. Distributed control strategy does not require UAVs in formation to know all flight status information, and formation control can be completed only by knowing the status information of adjacent UAVs (Table 1).

The advantages of centralized control strategy are simple implementation and complete theory; The disadvantages are lack of flexibility and fault tolerance, and the communication pressure in formation is high [3]. The advantage of distributed control strategy is that it reduces the requirement of UAV Communication capability and improves the flexibility of formation; The disadvantage is that it is difficult to realize and the formation may be greatly disturbed [4].

Ru Changjian et al. designed a distributed predictive control algorithm based on Nash negotiation for UAVs carrying different loads in the mission environment, combined with the multi-objective and multi person game theory and the Nash negotiation theory of China. Zhou shaolei et al. established the UAV virtual pilot formation model and introduced the neighbor set, adopted distributed model predictive control to construct the reconfiguration cost function of multi UAV formation at the same time, and proposed an improved quantum particle swarm optimization algorithm to complete the autonomous reconfiguration of multi UAV formation. Hua siliang et al. studied the communication topology, task topology and control architecture of UAV formation, analyzed the characteristics of task coupling, collision avoidance and dynamic topology of UAV formation reconfiguration, and proposed a model predictive control method to solve the UAV formation reconfiguration problem. Wang Jianhong transformed the nonlinear multi-objective optimization model based on autonomous reconfiguration of multi UAV formation into a standard nonlinear single objective optimization model, and solved the optimal solution through the interior point algorithm in operational research. Mao Qiong et al. proposed a rule-based formation control method aiming at the shortcomings of existing methods in UAV formation control and the characteristics of limited range perception of UAV system [5–8].

## **3 Agent and Reinforcement Learning**

#### **3.1 Agent**

The concept of agent has different meanings in different disciplines, and so far there has been no unified definition. In the field of computer, agent refers to the computer entity that can play an independent role in the distributed system. It has the following characteristics:

1) Autonomy: it determines its own processing behavior according to its own state and perceived external environment;

2) Sociality: it can interact with other agents and work with other agents;

3) Reactivity: agent can perceive the external environment and make corresponding response;

4) Initiative: be able to take the initiative and show goal oriented behavior;

5) Time continuity: the process of agent is continuous and circular;

A single agent can perceive the external environment, interact with the environment and other agents, and modify its own behavior rules according to experience, so as to control its own behavior and internal state. In the multi-agent system, there are agents who play different roles. Through the dynamic interaction, they make use of their own resources to cooperate and make decisions, so as to achieve the characteristics that a single agent does not have, namely, emergence behavior. Each agent can coordinate, cooperate and negotiate with each other. In the multi-agent system, each agent can arrange their own goals, resources and commands reasonably, so as to coordinate their own behaviors and achieve their own goals to the greatest extent. Then, through coordination and cooperation, multiple agents can achieve common goals and realize multi-agent cooperation. In the agent model, the agent has belief, desire and intention. According to the target information and belief, the agent can generate the corresponding desire and make the corresponding behavior to complete the final task (Fig. 1).

**Fig. 1.** Agent behavior model

When there are multiple agents in a system that can perform tasks independently, the system is called multi-agent system. In the scenario of applying multi-agent system to deal with problems, the focus of problem solving is to give full play to the initiative and autonomy of the whole system, not to emphasize the intelligence of a single agent. In some scenarios, it is often impossible to simply use the reinforcement learning algorithm of single agent to solve the problem of multi-agent (Fig. 2).

**Fig. 2.** The structure of agent in combat simulation architecture

According to the classification of Multi-Agent Reinforcement learning algorithm, it can be divided into the following categories according to the types of processing tasks

(1) Multi agent reinforcement learning algorithm in the case of complete cooperation. All the participants in the system have the same optimization goal. Each agent makes its own action by assuming that the other agents choose the optimal action in the current state, or makes some combination action through the cooperation mechanism to obtain the optimal goal.

#### **3.2 Reinforcement Learning**

The standard reinforcement learning algorithm mainly includes four elements: environment, state, action and value function. The problem can be solved by constructing mathematical model, such as Markov decision process (Fig. 3).

**Fig. 3.** Basic concept map of reinforcement learning

At present, the research on agent reinforcement learning algorithm has built a perfect system and achieved fruitful results. However, the processing ability and efficiency of a single agent are always limited. It is an effective way to solve the problems in complex environment by using the Multi-Agent Reinforcement learning algorithm. When there are multiple agents in a system that can perform tasks independently, the system is called multi-agent system. In the scenario of multi-agent system, the key point of problem solving is to give full play to the initiative and autonomy of the whole system, not the intelligence of single agent. In some scenarios, it is difficult to use the reinforcement learning algorithm of single agent to solve the problem of multi-agent. Therefore, the research and attention of experts and scholars on the reinforcement learning algorithm of multi-agent is improving.

## **4 A Method of UAV Formation Transformation Based on Reinforcement Learning Multi-agent**

#### **4.1 Description of UAV Formation Transformation Model**

The core model of reinforcement learning: Markov decision-making process is usually composed of a quadruple: M = (*S*, *A*, *Psa*, *R*). S represents the states in finite space; A represents the actions in finite space; P\_sa represents the probability set of state transfer, that is, in the current s ∈ S state, the probability that action a ∈ A will be transferred to other states after action a ∈ A is selected; R represents the return function, which is usually a function related to state and action, which can be expressed as r(s, a). The agent takes action a under state s, and performs the following actions. The expected return can be obtained as follows:

$$\mathbf{R\_{sa}} = \mathbf{E} \left[ \sum\_{\mathbf{k}=0}^{\infty} \mathbf{\gamma}^{\mathbf{k}} \mathbf{r\_{k+1}} | \mathbf{S} = \mathbf{s}, \mathbf{A} = \mathbf{a} \right] \tag{1}$$

γ is a discount factor with a value between 0 and 1, which makes the effect of the later return on the return function smaller. It simulates the uncertainty of the future return and makes the return function bounded.

In this paper, four tuples (S, A, P,R) are used to represent the Markov decision process model for formation transformation of multiple UAVs. Where S is the state space set of UAV, A is the action space set of UAV, P is the state transition probability of UAV, and R is the action return function of UAV.

Let the UAV move in the constructed two-dimensional grid, and use Z(Z > 0) to represent a positive integer, then the two-dimensional grid space is Z2, and the UAV coordinate in the two-dimensional grid space is xti, yti , indicating the state s of UAV sti ∈ Z2, and toward the corresponding target point Gi(i = 1, 2, 3, .. N) motion, the target point of each UAV will be given in advance according to the conditions. During the flight of UAV I, action set Ai(s) ={up, down, left, right, stop}.

#### **4.2 A Method of UAV Formation Transformation Based on Reinforcement Learning Multi Agent Agent**

The fundamental goal of reinforcement learning is to find a strategy set S, Aso that the expected return of agent in any state is the largest. The agent can only get the immediate return of the current step each time. We choose the classical Q-learning algorithm state action value function Q(s, a) instead of Rsa. According to a certain action selection strategy, the agent makes an action in a certain state and gets immediate feedback from the environment. The Q value increases when it receives positive feedback, and decreases when it receives negative feedback. Finally, the agent will select the action according to the Q value. The action selection function of traditional Q-learning algorithm is as follows:

$$\pi(\mathbf{s}) = \begin{cases} \arg\max \left[ Q(\mathbf{s}, a) \right], \text{ if } q < 1 - \varepsilon \\ a\_{random} & \text{otherwise} \end{cases} \tag{2}$$

ε is a parameter of ε − greedy, When the random number q is less than 1 − ε Choose the behavior a that makes the Q value maximum, otherwise choose the random behavior a. In the practical algorithm design, the iterative approximation method is usually used to solve the problem:

$$\mathcal{Q}^\*(\mathbf{s}, a) = \mathcal{Q}(\mathbf{s}, a) + a \left[ r(\mathbf{s}, a) + \gamma \max Q(\mathbf{s}', a) - \mathcal{Q}(\mathbf{s}, a) \right] \tag{3}$$

where a is the learning factor, the larger the value of a is, the less the results of previous training are retained; *maxQ s* , *a* is the prediction of Q value, as shown in algorithm 1:

#### **Algorithm 1** Q-learning algorithm

In this paper, the multi UAV formation problem based on reinforcement learning can be described as: UAV interacts with the environment, learning action strategy, so that the whole UAV group can reach their respective target points with the minimum consumption steps without collision. In the process of learning the optimal action strategy, when all UAVs arrive at the target point, the group will get a positive feedback r+, otherwise it will get a negative feedback r\_.

The reinforcement learning algorithm of multi-agent needs to change the action of each agent in each state to *asi*(i = 1, 2,... n) is regarded as a joint action →*asi* can be considered. The learning process of the algorithm is complex, consumes more resources and is difficult to converge. Therefore, we introduce heuristic function H to influence the action selection of each agent. Formula 1.2 can be changed as follows:

$$\pi^H(\mathbf{s}) = \begin{cases} \operatorname\*{argmax}\limits\_{a} \Big[ Q(\mathbf{s}, a) + \beta H(\mathbf{s}, a) \Big], \text{if } q < 1 - \varepsilon \\ a\_{random'} & \text{otherwise} \end{cases} \tag{4}$$

where β is the real number that controls the effect of the heuristic function on the algorithm. The heuristic function H needs to be large enough to affect the agent's action selection, and it should not be too large to prevent the error that affects the result. when β is 1, the mathematical expression of heuristic function H can be defined as:

$$\pi^H(\mathbf{s}) = \begin{cases} \operatorname\*{argmax}\limits\_{a\_{random}} [Q(\mathbf{s}, a) + \beta H(\mathbf{s}, a)], \text{if } q < 1 - \varepsilon\\ a\_{random}, & \text{otherwise} \end{cases} \tag{5}$$

where δ is a relatively small real number, which makes the heuristic function H larger than the difference between Q values and does not affect the learning process of reinforcement learning. The whole process of improved heuristic reinforcement learning is as follows (Fig. 4):

**Fig. 4.** The whole flow chart of improved heuristic reinforcement learning

## **5 Summary**

In this paper, a reinforcement learning based multi-agent UAV formation transformation method is proposed. The heuristic algorithm is used to improve the traditional reinforcement learning algorithm, and the optimal path without collision is planned for the multi UAV system in the formation transformation stage, which solves the problem that the reinforcement learning algorithm consumes a lot of computing resources when facing the multi-agent problem.

# **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

# **A Formalization of Topological Spaces in Coq**

Sheng Yan, Yaoshun Fu, Dakai Guo, and Wensheng Yu(B)

School of Electronic Engineering, Beijing Key Laboratory of Space-Ground Interconnection and Convergence, Beijing University of Posts and Telecommunications, Beijing 100876, China<EMAIL_ADDRESS>
**Abstract.** It is a wish for Wu Wen-tsun to implement the mechanical proving of theorems in topology. Topological spaces constitute a fundamental concept of general topology, which is significant in understanding the essential content of general topology. Based on the machine proof system of axiomatic set theory, we presented a computer formalization of topological spaces in Coq. Basic examples of topological spaces are formalized, including indiscrete topological spaces and discrete topological spaces. Furthermore, the formal description of some wellknown equivalent definitions of topological spaces are provided, and the machine proof of equivalent definitions based on neighborhood system and closure is presented. All the proof code has been verified in Coq, and the process of proof is standardized, rigorous and reliable.

**Keywords:** Coq · Formalization · Axiomatic set theory · General topology · Topological spaces

## **1 Introduction**

The formal verification of mathematical theorems profoundly incarnates the basic theories of artificial intelligence, have also attracted more attention from researchers [1].

Some famous mathematical theorems have been already formalized. In 2005, Gonthier and Werner have given the formal proof of the "Four-color Theorem" in Coq [2]. After six years, formal verification of "Odd Order Theorem" has been achieved by Gonthier in [3]. Hales provided formal proof of "Kepler Conjecture" in Isabelle/HOL [4]. There has a list about Formalizing 100 Theorems on the web [5], which will keep track of theorems from this list that have been formalized.

The theorem prover Coq is a tool used to verify whether the proofs of theorems are correct, and the theorem can be taken from general mathematics, protocol verification or safety programs. The Coq system is extremely powerful and expressions in reasoning and programming. Moreover, the process of proofs is built interactively in Coq with the aid of tactics [6]. There are various tactics of available in Coq, which make it become the mainstream tool in the field of interactive theorem proving in the world [7].

Topological spaces constitute a fundamental concept of general topology. There are many ways to create the definition of topological spaces [8]. During the early periods of general topology, some scholar defined the topological spaces by axioms of neighborhood systems or axioms of closure. With the development of general topology, it was revealed that the definition of topological spaces from various basic concepts is equivalent, and one of the convenient tools for exploring topological spaces is to use the axioms of open sets [9].

Being such an elementary concept in general topology, the definition of topological spaces appears in several formalization works with a variable degree of details and generality. A definition of topological spaces has been already formalized by Schepler in Coq contribution libratory based on type theory [10]. The topological spaces theory has been developed based on theorem prover Coq by Wang in [11]. Another work involved the formal description of topological spaces has been carried out by Hölzl in [12], which formalize the development process of space in the history of mathematics, including topological space, metric space and Euclidean space.

This paper presented a computer formalization of topological spaces in Coq. The formal proof of two basic examples in topological spaces is given, including indiscrete topological spaces and discrete topological spaces. The key points of our work are to realize the formal description of equivalent definitions of topological spaces, and to present the machine proof of equivalent definitions based on neighborhood system and closure.

In the paper structure, we briefly give the formalization of set theory in Sect. 2, which act as preliminaries for the formalization of topological space. Section 3 introduces the concepts of topological spaces in Coq based on the axioms of the open sets. We present the formal proof of equivalent definitions of topological spaces based on neighborhood system and closure in Sect. 4. The conclusions are given in Sect. 5.

#### **2 Formalization of Set Theory**

Set theory is the foundation of modern mathematics [13]. The author has done the work about the formalization of axiomatic set theory in [14]. A formalization of naive set theory is introduced based on the axiomatic set theory.