Intelligent Search of Values for a Controller Using the Artificial Bee Colony Algorithm to Control the Velocity of Displacement of a Robot

The optimization is essential in the engineering area and, in conjunction with use of metaheuristics, has had a great impact in recent years; this is because of its great precision in search of optimal parameters for the solution of problems. In this work, the use of the Artificial Bee Colony Algorithm (ABC) is presented to optimize the values for the variables of a proportional integral controller (PI) to observe the behavior of the controller with the optimized Ti and Kp values. It is proposed using a robot built using the MINDSTORMS version EV3 kit. The objective of this work is to demonstrate the improvement and efficiency of the controllers in conjunction with optimization meta-heuristics. In the results section, we observe that the results improve considerably compared to traditional methods. In this work, the main contribution is the implementation of an optimization algorithm (ABC) applied to a controller (PI), and the results are tested to control the movement of a robot. There are many papers where the kit is used in various domains such as education as well as research for science and technology tasks and some real-world problems by engineering scholars, showing the acceptable result.

Introduction
Today is the digitalization era, with robotics, artificial intelligence, IoT (Internet of Things) and automation. Since ancient times, the human being has sought to automate all its activities, avoiding the effort and intervention of the human hand. In recent years, the combination of different intelligent techniques helps different areas of science to improve and optimize time, performance, accuracy, and computational cost when solving any problems [1]. In this paper, an innovative proposal is presented where a combination of meta-heuristics and control are used for the intelligent search of values of the variables K p and T i and applied in a LEGO EV3 robot. K p represents the proportional gain and refers to the constant of proportionality in the action to proportional control. If the value of K p is small, the proportional action is small, but if K p is high, the proportional action is high. The variable T i refers to the time required for the integral action to contribute to the controller output. If T i is small, the integral action is high, but if T i is high, the integral action is small.
Today actually is the era of robotics, where, in conjunction with artificial intelligence, humanity has managed to achieve significant advances in some areas, for example: home robots, academics, medicine, agriculture, combat robots, scout robots in other planets (example: Mars exploration rover), and intelligence implemented in other entities such as autonomous land and aerial vehicles and virtual assistants [2], for mention of some areas. It is important to mention the new term that emerged recently: machine learning (ML). ML is the science of getting machines to learn and act like humans, and improve their learning over time autonomously, by feeding them data and information in the form of observations and real-world interactions [3].
Each of the entities mentioned above integrate some of the following: neural networks for learning in conjunction with other sciences for the collection and processing of information, audio and image, and some type of controller to coordinate and activate some actuators of the robot such as: arms, legs, engines, and others. There are several types of controllers that are used for the control of some system such as: proportional integral derivative control (PID) [4], fuzzy logic control (FLC) [5], and its extension, type 2 fuzzy logic control [6].
In this case, a proportional integral controller (PI) is used, where the values for the constants are adjusted in execution time using a bio-inspired algorithm in the behavior of bees in nature in the process of searching and collecting the nectar.
The objective of this work is to demonstrate that bio-inspired algorithms can significantly improve the results in solving optimization problems. It is important to mention that, in the literature, there are many published works with implementations of the ABC algorithm in control problems, for example: PID, type 1 and type 2 fuzzy logical control, and approximation of mathematical functions. However, a few studies have found that this algorithm can be used to optimize the parameters of a PI and observe the behavior. There are many bio-inspired algorithms in the literature, each with different characteristics. The selection of the algorithm for this proposal was determined after analyzing its characteristics and based on [7][8][9].

Related Work
There are multiple publications in the literature of different bio-inspired meta-heuristics in the behavior of the bees in the nature; for example, in [10], the authors present their proposal of a new powerful meta-heuristic for the resolution of complex problems, and years later, authors of [11,12] present a modification of the ABC algorithm for unrestricted searches. Other authors also present some variants similar to this meta-heuristic mentioned above (e.g., [7,[13][14][15]).
During the last several years, multiple variants of the algorithm proposed in this work have been developed. It is important to mention that each variant was developed to solve a specific problem: optimization of neural networks, optimization of fuzzy logic controllers type 1 and type 2, and optimization of mathematical functions, to mention some. The authors of this proposal consider that is important to mention in this paper.
The original version of the ABC algorithm proposed by [10] to dynamically adjust the values of the constants of a controller (PI) is used in this paper. There are also published works by other authors where they use different controllers applied to the LEGO MIND-STORMS EV3 kit, such as: proportional integral derivative controllers (PID) [16,17], fuzzy logic controllers (FLC) [18], fuzzy logic proposed by Zadeh [5], and proportional integral controllers (PI) [19].
It is also necessary to show the reader of this manuscript some works related to our proposal. For example, in [20], "Real-Time PID Control of Wireless Two-Wheeled Balancing LEGO EV3 Robot", a two-wheeled balancing LEGO EV3 robot is modeled in a state space and controlled by a PID controller, which we find very interesting. In [21], the authors present an application for mobile devices to operate and read the status of motors and controller of the LEGO robot and affirm that this app can operate with different sizes of motors. In [22], the authors use a LEGO robot NXT version with infrared sensor to follow a trajectory with reference to a line and use a control (PID) to control the motors. Furthermore, the use of fuzzy logic is present in the LEGO kits, for example.
In [23,24], a fuzzy logic controller is used as a controller to stabilize the two-wheeled EV3 LEGO robot. In recent years, fuzzy controllers in combination with meta-heuristics have had a great impact in different areas [24]. EV3 MINDSTORMS LEGO characteristics: The brick or block EV3 is the unit of control and electrical feeding of motors and sensors of the robot. It connects to the computer (via USB, Bluetooth, or Wi-Fi) to receive and execute the control programs, and it is the successor of LEGO MINDSTORMS NXT 2.0. The LEGO EV3 kit is the third generation of the LEGO robotics line and recommended for teaching and learning school robotics. It has a 300 MHz ARM9 processor, 16 MB of flash memory, 64 MB of RAM, and a Linux operating system, with an open-source license. The EV3 was implemented to test the optimized PI model with the ABC algorithm and observe the displacement behavior.
However, some researchers have used it for scientific purposes to test their models and observe behavior in different areas and types of problems [25,26].
Proportional integral controller (PI): There are two types of forms in a control algorithm to decide on an action. The open loop system and the parameters of the algorithm are pre-set and do not change. While the system is running, the closed loop system sensors measure the error between the desired state of the system and its real state, and this error is used to decide what action to take. To achieve speed control in a EV3 LEGO MINDSTORM, open circuit control systems were used. Figure 1 shows the general scheme of a loop control system [19,26], where the values of the constants K p and T i are calibrated at runtime using the ABC algorithm. In [23,24], a fuzzy logic controller is used as a controller to stabilize the two-wheeled EV3 LEGO robot. In recent years, fuzzy controllers in combination with meta-heuristics have had a great impact in different areas [24].
EV3 MINDSTORMS LEGO characteristics: The brick or block EV3 is the unit of control and electrical feeding of motors and sensors of the robot. It connects to the computer (via USB, Bluetooth, or Wi-Fi) to receive and execute the control programs, and it is the successor of LEGO MINDSTORMS NXT 2.0. The LEGO EV3 kit is the third generation of the LEGO robotics line and recommended for teaching and learning school robotics. It has a 300 MHz ARM9 processor, 16 MB of flash memory, 64 MB of RAM, and a Linux operating system, with an open-source license. The EV3 was implemented to test the optimized PI model with the ABC algorithm and observe the displacement behavior.
However, some researchers have used it for scientific purposes to test their models and observe behavior in different areas and types of problems [25,26].
Proportional integral controller (PI): There are two types of forms in a control algorithm to decide on an action. The open loop system and the parameters of the algorithm are pre-set and do not change. While the system is running, the closed loop system sensors measure the error between the desired state of the system and its real state, and this error is used to decide what action to take. To achieve speed control in a EV3 LEGO MIND-STORM, open circuit control systems were used. Figure 1 shows the general scheme of a loop control system [19,26], where the values of the constants and are calibrated at runtime using the ABC algorithm. The parameter SP represents the reference value; the variable transformed into a control value is represented by MV; and the parameter PV represents the output, which is calculated with the equation e = SP − PV.
Artificial Bee Colony Algorithm (ABC): The algorithm of artificial bee colony is a meta-heuristic inspired by the behavior of bees in nature and was created by Dervis Karaboga in 2005 [10]. The algorithm (ABC) uses the principle of collective intelligence where the individuals (bees) collaborate with each other to achieve an objective. After the proposal made by Dervis Karaboga in 2015, many variants and improvements have been developed in this work, the original version is used. This algorithm has very interesting characteristics. Bees are classified into three roles according to their fitness value. For example: 1. Initialization Phase: All the vectors of the population of food sources, ( )'s, are initialized ( = 1, … : population size) by scout bees, and control parameters are set.
Since each food source, ( ), is a solution vector to the optimization problem, each ( ) vector holds variables, ( , = 1 … ), which are to be optimized so as to minimize the objective function.
The following definition might be used for initialization purposes: The parameter SP represents the reference value; the variable transformed into a control value is represented by MV; and the parameter PV represents the output, which is calculated with the equation e = SP − PV.
Artificial Bee Colony Algorithm (ABC): The algorithm of artificial bee colony is a metaheuristic inspired by the behavior of bees in nature and was created by Dervis Karaboga in 2005 [10]. The algorithm (ABC) uses the principle of collective intelligence where the individuals (bees) collaborate with each other to achieve an objective. After the proposal made by Dervis Karaboga in 2015, many variants and improvements have been developed in this work, the original version is used. This algorithm has very interesting characteristics. Bees are classified into three roles according to their fitness value. For example:

1.
Initialization Phase: All the vectors of the population of food sources, (x m )'s, are initialized (m = 1, . . . SN : population size) by scout bees, and control parameters are set. Since each food source, (x m ), is a solution vector to the optimization problem, each (x m ) vector holds n variables, (x mi , i = 1 . . . n), which are to be optimized so as to minimize the objective function.
The following definition might be used for initialization purposes: where l i and u i represent the lower and upper bound of the parameter x mi , respectively. 2. Employed Bees Phase: New food origins are being searched (v m ); the one that has more nectar in the food neighborhood (x m ) is put in memory. Once the food origin neighbors are found, then rentability (aptitude) is evaluated. For example, a food origin can be determined by using the formula of the following Equation (1) [27].
where x k is a randomly selected food source, i is a randomly chosen parameter index, and φ mi is a random number within the range [−a, a]. After producing the new food source v m , its fitness is calculated, and a greedy selection is applied between v m and x m. The fitness value of the solution, f it m (x m ), might be calculated for minimization problems using the following Equation (2) [27].
where f m (x m ) represent the objective function value for solution x m .

3.
Onlooker Bees Phase: In this optimization algorithm, an observer bee chooses a food source based on the calculated fitness value with Equation (2). Data from food sources are provided by the bees employed. The roulette method is used for selection [28].
The probability value P m with which X m is chosen by an observer bee can be calculated using the expression given in the Equation (3) [27]: After choosing a food source x m for a spectator bee, a neighborhood source v m is determined using Equation (2), and the fitness value is calculated. As in the phase of bees used, a greedy selection between v m and x m is applied.

4.
Scout Bees Phase: The bees without jobs who choose their food origins randomly are called scout bees. Then the converted scouts begin to look for new random solutions. For example, if solution x m has been abandoned, the new solution discovered by the scout who was the used bee x m can be defined using Equation (4). Therefore, all food origins with a low fitness value are abandoned due to exploitation [27].
The population of food sources is generated by the exploratory bees. x m (m = 1 . . . , SN: population size) and the parameters of the algorithm are configured. In the solution vector for the optimization problem, each vector x m , represents each food source, x m , and contains n variables (x mi , i = 1 . . . n), which must be optimized to minimize the Objective Equation (4): where l i and u i represent the lower and upper bound of the parameter x mi , respectively. In summary, the ABC algorithm: 1.
Is inspired by the foraging behavior of honeybees; 2.
Is a global optimization algorithm; 3.
Can be also used for combinatorial optimization problems [22]; 5.
Uses only three control parameters (population size, maximum cycle number, and limit) that are to be pre-determined by the user; 7.
Is quite simple, flexible, and robust (some of the relevant publications expressing these merits of the ABC algorithm are [10,11]).

Proposed Approach
In this work, we present a dynamic adaptation of variables for a proportional integral controller using the algorithm of artificial bee colony modeling in a EV3 LEGO MIND-STORM robot. As mentioned above, the LEGO kit is used in multiple domains such as: research and education for science and technology tasks and some real-world problems by engineering scholars.
The main contribution is the use of a meta-heuristic to adjust the variables of a (PI) control in a runtime and, at the same time, to model it in a LEGO robot. This process is carried out in wireless mode using the language of MATLAB programming in conjunction with Simulink.
In Figure 2, a flow diagram is shown that represents the sequence of steps to follow to achieve an optimal communication between the algorithm, Simulink block diagram, and LEGO EV3 robot.
Algorithms 2021, 14, x FOR PEER REVIEW 5 of 13 7. Is quite simple, flexible, and robust (some of the relevant publications expressing these merits of the ABC algorithm are [10,11]).

Proposed Approach
In this work, we present a dynamic adaptation of variables for a proportional integral controller using the algorithm of artificial bee colony modeling in a EV3 LEGO MIND-STORM robot. As mentioned above, the LEGO kit is used in multiple domains such as: research and education for science and technology tasks and some real-world problems by engineering scholars.
The main contribution is the use of a meta-heuristic to adjust the variables of a (PI) control in a runtime and, at the same time, to model it in a LEGO robot. This process is carried out in wireless mode using the language of MATLAB programming in conjunction with Simulink.
In Figure 2, a flow diagram is shown that represents the sequence of steps to follow to achieve an optimal communication between the algorithm, Simulink block diagram, and LEGO EV3 robot. The algorithm consists of the following phases: The algorithm consists of the following phases: Step 1: the population of bees is initialized. Considering the search universe, this universe is defined by the problem to be solved; in this case, [−1, 9] is proposed, and the solutions generated so far are evaluated.
Step 2, 3, 4, 5: in these steps, each new solution is evaluated, and the best one found so far goes to the next iteration to be optimized.
The best solution is determined after simulating the path given by ABC in the robot, and its fitness value is calculated using the mean square error Equation (5).

Methodology
In Figure 2, we can see a general illustration of our proposal. For the development of the proposal, as mentioned above, the role of the meta-heuristic bee colony algorithm is to explore the search space in order to find the optimal values for the constants (K p , T i ) of the PI controller.
Each value found by the meta-heuristic is assigned to the variables of the controller and is modeled in the LEGO robot, and the fitness value is obtained for that model. The connection with the brick LEGO is performed by wireless mode using a block model in Simulink and a Wi-Fi router to obtain the values and calculate the error of the motors (see Figure 2).
Before starting with the dynamic adaptation of variables of the (PI controller), we decided to use a reference method to use it as a guide in this work, there are many open loop tuning methods for self-regulating process (reaches a steady-state value after a step change in the manipulated variable) that use a first-order plus dead time model of the process (FODT) [29][30][31]. The transfer function of a general first-order plus dead time model is where K = Gain Process θ D = Dead time τ = Time constant The graphical procedure for determining the model is based on Ziegler-Nichols, according to Kelvin T. Erickson in his book Programmable Logic Controllers [31]. The method consists of obtaining the features of the response in a step input of magnitude such as demonstrated by Figure 3. The response to this input is obtained experimentally. so far goes to the next iteration to be optimized.
The best solution is determined after simulating the path given by ABC and its fitness value is calculated using the mean square error Equation (5).

Methodology
In Figure 2, we can see a general illustration of our proposal. For the dev the proposal, as mentioned above, the role of the meta-heuristic bee colony to explore the search space in order to find the optimal values for the constan the PI controller.
Each value found by the meta-heuristic is assigned to the variables of t and is modeled in the LEGO robot, and the fitness value is obtained for tha connection with the brick LEGO is performed by wireless mode using a blo Simulink and a Wi-Fi router to obtain the values and calculate the error of the Figure 2).
Before starting with the dynamic adaptation of variables of the (PI co decided to use a reference method to use it as a guide in this work, there are loop tuning methods for self-regulating process (reaches a steady-state valu change in the manipulated variable) that use a first-order plus dead time m process (FODT) [29][30][31]. The transfer function of a general first-order plu model is The graphical procedure for determining the model is based on Zieglercording to Kelvin T. Erickson in his book Programmable Logic Controllers [31]. consists of obtaining the features of the response in a step input of magnit demonstrated by Figure 3. The response to this input is obtained experiment It is important to analyze the response obtained, since it must have an type of response has two parameters: the dead time and the time constan process reaches the steady state, the parameters could be determined by straight-line tangent to the inflection point of the response obtained, as show 4. It is important to analyze the response obtained, since it must have an S shape; this type of response has two parameters: the dead time θ D and the time constant τ. After the process reaches the steady state, the parameters could be determined by drawing a straight-line tangent to the inflection point of the response obtained, as shown in Figure 4.  The term 1 is the time at which the step change in the manipulated variable was imposed. 2 is the time at which the tangent drawn in the previous step intersects the time axis. To obtain the dead time, = 2 − 1 . The term 3 is the time at which the process variable response has made 63% of its total change. To obtain the time constant, = 3 − 2 .
The process gain is the change in the process variable divided by the change in the control variable; see Equation 6.
The values obtained are shown below: The first-order plus dead time model of the process (FODT) is presented in Equation  Table 1, we can see the tuning rule.  The term T 1 is the time at which the step change in the manipulated variable was imposed. T 2 is the time at which the tangent drawn in the previous step intersects the time axis. To obtain the dead time, The term T 3 is the time at which the process variable response has made 63% of its total change. To obtain the time constant, The process gain is the change in the process variable divided by the change in the control variable; see Equation (6).
The values obtained are shown below: The first-order plus dead time model of the process (FODT) is presented in Equation (7).
According to the Ziegler and Nichols open loop tuning method, values of K p , T i , and T d are established and calculated from the parameters θ D , τ, and K. In Table 1, we can see the tuning rule. The proposed controller for this test was PI, and the values obtained are shown below: The values for the variables of the PI were implemented in the Simulink model. In Figure 5, the three signals are shown: Yellow signal is the pulse input to the system (reference). The magenta and cyan signals are the responses of motor one and two. The type of input to the system was a pulse signal with an amplitude of 150 square. The values for the variables of the PI were implemented in the Simulink model. In Figure 5, the three signals are shown: Yellow signal is the pulse input to the system (reference). The magenta and cyan signals are the responses of motor one and two. The type of input to the system was a pulse signal with an amplitude of 150 square. The objective of this work is the implementation of a meta-heuristic to the automatic adjustment of the value of the variables of the PI. The method of Ziegler and Nichols is used to analyze the behavior of the block model and response of the LEGO robot EV3. Using Equation (5), an error of 16.6874 was obtained for this test.

Results Obtained from The Tests Performed
In this section the performance, stability and behavior of the robot is presented using the PI control with intelligent adjustment in the variables ( , ). Each experiment has 15 tests performed with the following configuration of parameters in the meta-heuristic ABC: population size = 20, iterations = 50, and search range [−1 9], using as a reference the results obtained with the Ziegler and Nichols method. The results obtained are shown in the Table 2. The objective of this work is the implementation of a meta-heuristic to the automatic adjustment of the value of the variables of the PI. The method of Ziegler and Nichols is used to analyze the behavior of the block model and response of the LEGO robot EV3. Using Equation (5), an error of 16.6874 was obtained for this test.

Results Obtained from The Tests Performed
In this section the performance, stability and behavior of the robot is presented using the PI control with intelligent adjustment in the variables (K p , T i ). Each experiment has 15 tests performed with the following configuration of parameters in the meta-heuristic ABC: population size = 20, iterations = 50, and search range [−1 9], using as a reference the results obtained with the Ziegler and Nichols method. The results obtained are shown in the Table 2. In Table 2, we can observe the results obtained from the tests performed on the robot. We consider it important to show the values found for the variables (K p , T i ) and the error obtained. The error was calculated using the equation of the root of the mean square error (RMSE); see Equation (8): where y re f represents the reference to follow, y data represents the data obtained from the motors of the robot, and N is the number of data. The behavior of the robot motors when following the reference for tests 19, 1, and 3 is shown in Figures 6-8. Observing the fitness value obtained, we determined that they are the best results obtained from the tests carried out with the robot and the meta-heuristics; moreover, the values for the constants of the controller (PI) are shown.
The yellow signal is the pulse of input to the system (reference); the magenta and cyan signals are the responses of motor one and two. The type of input to the system was a pulse signal with an amplitude of 150 square.
For greater ease for the readers of this work, in Table 3, we can observe a comparison of the results obtained with the different approaches. It is important to mention that the error obtained with "Integral proportional control (PI), traditional" used the values defined by [29][30][31], and the error was 16.6874, which is high. When the optimization is used with values 7.5682 in K p and 0.2836 in T i , the error decreases considerably.     For greater ease for the readers of this work, in Table 3, we can observe a comparison of the results obtained with the different approaches. It is important to mention that the error obtained with "Integral proportional control (PI), traditional" used the values defined by [29][30][31], and the error was 16.6874, which is high. When the optimization is used with values 7.5682 in Kp and 0.2836 in Ti, the error decreases considerably. The values shown for Kp and Ti with "Intelligent integral proportional control" were found in a dynamic and intelligent way by the proposed algorithm (ABC), as we can see in the comparison: the error difference is very significant compared with that obtained using the traditional PI control. As mentioned in the introductory section, bio-inspired algorithms provide a great variety of solutions to different problems in engineering and other areas with a low computational cost.

Discussion
Throughout this work, we have presented a proof of concept of bio-inspired metaheuristics in the behavior of bees in nature applied to the dynamic adaptation of values to control the speed of movement of a robot. In this work, the Artificial Bees Colony (ABC) algorithm is proposed for the intelligent search of values Kp and Ti for Equation (5).
Based on the results obtained, we can conclude the feasibility of implementing bioinspired optimization algorithms for the intelligent search of values for complex search  The values shown for K p and T i with "Intelligent integral proportional control" were found in a dynamic and intelligent way by the proposed algorithm (ABC), as we can see in the comparison: the error difference is very significant compared with that obtained using the traditional PI control. As mentioned in the introductory section, bio-inspired algorithms provide a great variety of solutions to different problems in engineering and other areas with a low computational cost.

Discussion
Throughout this work, we have presented a proof of concept of bio-inspired metaheuristics in the behavior of bees in nature applied to the dynamic adaptation of values to control the speed of movement of a robot. In this work, the Artificial Bees Colony (ABC) algorithm is proposed for the intelligent search of values K p and T i for Equation (5).
Based on the results obtained, we can conclude the feasibility of implementing bioinspired optimization algorithms for the intelligent search of values for complex search and optimization problems. In this case, the ABC is used to control the speed of movement of a mobile robot. As we can see in Table 2, the results obtained were better achieved using the values proposed by Ziegler and Nichols [29]; see the results with values proposed by Ziegler and Nichols in Figure 6.
This work can be used as a basis to show readers the implementation of a bio-inspired algorithm to optimize the trajectory in an EV3 MINDSTORMS LEGO robot. It is important to mention that there are many application areas of algorithms such as: electronics, finance, construction, and telecommunications, to mention some. The applications are numerous and very varied due to their great adaptability and generate acceptable results with a low computational cost. As future work on the proposal, machine learning techniques can be implemented, which allows us to improve the models (ABC).

Conclusions
In this paper, a dynamic optimization of the parameters in the PI was performed. In the optimization, the search space was based on Ziegler and Nichols (see Table 1). As we mentioned, values were between −1 and 9. One of the objectives is to reduce the error of 16.6874 found with the Ziegler and Nichols method. After the experiments with the implementation in the robot, results show that bee colony optimization can obtain good parameters to the PI and improve it.
In many applications, a simple conventional PI is used to control the application, but we can use the best parameters for the PI, improving the controller even more, and obtain better results than using static values. In Table 2, important results were obtained and were better than Ziegler and Nichols. We were confident in a statistical comparison using Ziegler and Nichols, as the results obtained in this paper show. That is because the values of the K p and T i can change. The main objective was obtained, because the results were less than the reference.


extfieldsofstudy:
Physics
Computer Science

text:
An Intelligent Mobile Application Testing Experience Report

Artificial intelligence applications provide tremendous opportunities to improve human life and drive innovation. AI systems/applications which operate in a real-world environment have to encounter an infinite set of feasible scenarios. Conventional testing approach to test the AI application allows only limited testing and does not allow taking the different contexts into consideration and may lead to insufficient validation and characterization. Therefore, to ensure robustness, certainty and reliability of AI applications, the authors applied classification-based AI software testing framework and 3D decision tables to generate test cases. Moreover, the authors compared the quality assurance metrics (accuracy, correctness, reliability and consistency) of AI and non-AI functions in the AI mobile application scenario. Our results indicate and confirm that complete AI function validation is not possible with conventional testing methods, but AI software testing strategy proposed based on classification framework and 3D decision tables has a good effect.

Introduction
Recent advancements and development in Artificial Intelligence (AI) and ML (Machine Learning) are greatly influencing our everyday life. Market forecast by Tractica [1] suggest that annual global AI software revenue is forecast to grow from $9.5 billion in 2018 to $118.6 billion by 2025. Implementing the AI and ML methods or technologies in mobile application development is becoming widespread to achieve intelligent functions, such as recommendation functional features, detection and recognition function, Natural Language Processing (NLP), question and answer functions, unman-controlled vehicles. Therefore, it is very important to test them adequately and assure its safety.
AI testing can be categorized into two kinds a) AI-based software testing: refers to the leverage and applications of AI methods and solutions to automatically optimize software testing process in test strategy selection, test generation, test selection and execution, bug detection and analysis, and quality prediction; b) testing AI software: refers to activities related to validating the AI system functions and features that are developed based on machine learning models, establishing AI function quality test requirement, detecting the AI function issues, limitations and quality problems. This paper focuses on the testing of AI software.
Testing of AI mobile applications poses many challenges and conventional methods of testing are not enough to establish quality and assurance of AI applications and functions. The major problems of AI application testing are due to a) Lack of well-defined and experience-approved AI system validation models and methods for AI applications developed based on big data and using machine learning and deep learning techniques; b) Lack of well-defined quality assurance standards and assessment methods; c) Lack of efficient and cost-effective automatic quality validation tools for machine learning based AI systems Major challenges include but not limited to a) how to identify and establish quality assurance and For the above-mentioned problems and challenges, the authors proceeded with classification-based AI software testing [2] for AI function inputs, contexts, and conditions to assure the adequate testing coverage. And in this paper, the authors are aiming at errors/bugs discovered using conventional testing methods to implement and analyze by classification-based AI function testing method.

AI-Software Testing
The real beginning of AI in the modern world has its foundation in the Turing test introduced by Turing as an "Imitation Game" in 1950 [3,4], which opened new doors for the AI field [5].
AI-software testing can be defined as testing activities with intent of finding errors in AI-based software using well-defined quality validation models, methods and tools. Its main objective is to validate system functions and features based on AI and ML models. The main obstacles of testing AI applications can be divided into four parts by Li L, et al [5]. a) Detailed description of tasks which can be quantitatively validated; b) How to make sure that the AI application is reacting accordingly to all possible tasks in the scenario. It can be straightforward if few variables exist in the case of simple intelligence but in complex intelligence tests this can be problematic and if there are continuous variables generated [6]; c) How to make the simulation-based test as "real" as possible. Simulation-based tests are an advantage because of higher cost and effort when compared to practical real-time tests but the question is how can we simulate the complex behaviors of certain animals and humans; d) How to establish the appropriate test performance evaluation indices for tasks. Performance indices are difficult to come up with because each human reacts differently, criteria can be complex and moreover, we expect machines to perform better than humans. In testing the intelligent vehicles [5], the authors give the definition and generation of intelligence test tasks for vehicles to combine the benefits of scenario-based testing and functionality-based testing approaches based on a semantic relation diagram definition for driving intelligence [7]. The authors applied the parallel learning method [8][9][10][11][12] to the vehicle intelligent test and proposed a parallel system framework that combined the real-world and simulation-world for the test.
In conclusion, conventional methods, strategies and tools do not accomplish the requirements of AIsoftware testing.

Classification Model and Decision Table
Classification-based AI software testing, in which classification models for inputs, contexts, and outputs and events are set up for AI software testing to assure the adequate testing coverage of diverse input data classes, classified contexts and conditions, and corresponding outputs and classes.
To leverage the testing effectively in a short time, the authors applied some basic standard testing methods into some divided testing business domains of the application.
Decision table testing is a kind of testing that is more like a cause-effect testing. This testing will determine what kind of output will be obtained on giving various kinds of input with different kinds of circumstances. Security holes can be detected in this method. Table  AI technique is applied in many applications that help to reduce human interaction, and then reduce manual working effort. Current testing methods and solutions are not adequate for testing AI software. AI-based software testing cannot be fully effectively executed by existing techniques and tools; therefore, we need to use other quality validation approaches and models that are different from conventional testing techniques and models. In this paper, the authors selected a testing LookTel Money Reader application that was introduced for enabling people experiencing visual impairments or blindness to quickly and easily identify and count bills [13,14]. It is a kind of Identification & Recognition System. The main features of the application are a) process a video or image and extract the information; b) use patented and proprietary object recognition technology; c) read and identify 21 different currencies; d) voice over support in 17 languages; d) instantly recognizes currency and reads the denomination and displays high contrast large numerals for partial vision loss people.

AI Function Testing Methods with the Necessary Criteria.
Without source code provided, the authors had to use Black Box testing with three main techniques: data-driven AI technique, classification and rulebased testing as our testing validation techniques to approach these above features. The authors designed scenarios in which banknotes are selected from some popular/specified currencies in the world to check whether Money Reader can provide exact recognition and read money information in the exact selected language. When testing on AI features, test coverage on all above defined AI functions is done by fulfilling all test cases that will be created in the next section of this paper. After doing some detailed analysis, the authors applied data-driven AI technique, classification testing and rule-based testing to create detailed test cases and perform testing.

AI Function Testing Modelling
AI testing is executed with some inputs under specific circumstances or context, and will result in some consequences. At the first step of AI testing, the authors will analyze and define the context, which data will be input and finally output of testing.

Context Modeling.
The authors divided the context in which the reading of money is executed in some specific conditions of equipment type, equipment position, currency type, state of object (people taking bank note), distance between equipment and bill, and environmental factors like: lighting and background placing bills. In which equipment type contains iPhone, iPad and Mac laptop. Currency type is a group of 4 main language systems: Naga language system, Middle Semit language system, Kanji language system and Latin language system. We defined the distance between the equipment and bills into 3 segments based on our empirical experiment: < 3 cm, > 48 cm, between 3 cm and 48 cm. Figure 1A represents the details of AI context modeling. The notation SELECT-1 means only one option can be selected, SELECT-M allows the combination of multiple conditions. XOR means one of the two options can be selected.

AI Function Input Classifications.
We separated the input data into 2 domains: bill state and bill classification as represented in Figure 1B and 1C. Bill state classification describes the various states of the bill used in testing such as, perfect condition, bill with missing parts, shaded bill and finally whether they are in what kind of physical condition such as folded, flat, scratched and wet conditions. Bill

AI Function Output Classifications.
Based on the diverse inputs of currency that are described above and execution in different contexts, the authors classified the output into two major categories that are represented in Figure 1D.

AI Function Classification Decision Table
With all classified spanning trees of AI context, AI inputs and outputs above (3. 3.1, 3.3.2, 3.3.3), the authors-built decision tables for each classification that are prerequisites for building test cases.      Table. Table 1 shows a random combination of all parameters that are described in Figure 1A, in which "T" means: "True" and "F" means "False". The total number of rules: 2^17 (2^number of conditions, in which we excluded 2 conditions of equipment type Dell laptop and Mac laptop due to money reader application cannot be installed on these two machines). Table. The next decision table represents the various states of the bill, which was developed based on the bill state context classification diagram as shown in Figure 1B. The bill state decision table was a random combination of all options. The authors selected 7 conditions and the total number of rules are 2^7 = 128 rules. Table. The final table represents the different bill classification decision  table was developed with bill classification context classification diagram as shown in Figure 1C. The authors selected a random combination of parameters described in Figure 1C, such as authentic, fraud, currency material type of the bill and/or coin to create the decision table. In this decision table the total number of rules are 2^12 = 4096 rules.  Figure 2 below represents the total number of AI test cases that the authors implemented with the number of passed/failed test cases and defects found in each business checking. Figure 2B shows the total number of test cases designed using decision table method and scenario test method in each business checking correspondingly. With the definition of 3D decision table, the authors built 21 test cases based on the combination of the first random 21 rules of input and context decision tables.

Test Complexity Comparison.
To get a general view of testing results, the authors do a comparison between conventional and AI testing in the figures below. Figure 3A consists of a total implemented 55 test cases in which 45 test cases passed and 10 test cases failed with 10 defects found. Meanwhile, 53 test cases passed and 20 test cases failed with 17 defects in AI testing. AI testing techniques work more effectively than Conventional testing techniques in detecting defects. Rate of defects found in AI testing is: 20/73 ~ 27.4%; In Conventional testing, this rate is: 10/55 ~ 19.2%. Besides that, the authors also collect the total number of test cases that were created in each test model using three major test methods and represent them in Figure 3B. In both models, the decision table is the method that is used the most to generate test cases; Scenario testing is used quite similar between AI testing & Conventional.

Bug Comparison.
In this experiment, some defects cannot be found in conventional testing but can be uncovered in an AI testing model and vice versa. This result is achieved by using 3D-decision table technique that supports the definition of a wide range of test cases. In Figure 4, we can observe that, in conventional testing we detected 10 defects, in which 3 defects we can uncover in AI testing, but 7 defects cannot be uncovered in AI testing. Meanwhile, 17 defects were found in AI testing, in which 16 defects are not uncovered in conventional testing.    Figure 4. Illustrate the bug comparison between conventional and AI.

Conclusions
In this present work, we focused on the challenges of using conventional software testing methods to test AI applications. The authors tested the currency denomination identifying AI application LookTel money reader using conventional approaches and comparing it with AI function testing. The quality assurance of AI functions is evaluated using metrics accuracy, correctness, reliability, and consistency. Our results confirm that indeed conventional testing approaches are not enough to validate the AI functions and using our proposed approach we found 16 defects out of 17 which cannot be found with conventional methods. Finally, we conclude that certainly AI application testing requires a different approach and in future studies should focus on validating the AI application using AI-based approaches so that the entire flow is automated.


Bitcoin Address Clustering Method Based on Multiple Heuristic Conditions

We analyzed the associations between Bitcoin transactions and addresses to cluster address and further find groups of addresses controlled by the same entity. It revealed the vulnerabilities of Bitcoin anonymity mechanism, which could be used by the law enforcement agencies to track and crack down illegal transactions. However, single heuristic method and incomplete heuristic conditions were difficult to cluster a large number of addresses comprehensively and accurately. Therefore, this paper reviewed a variety of heuristics, and used multiple heuristics comprehensively to cluster addresses to improve the degree of address aggregation and address recall rate, which laid a foundation for further inferring of entity identity. Keywords—Bitcoin, Blockchain, Anonymity, Heuristic, Address Clustering

Introduction
Since Bitcoin became a peer-to-peer digital payment system, it has attracted the attention of a legion of researchers. Currently there is a lot of research which has focused on various areas of the Bitcoin system, such as privacy security [1],transaction pattern [2], network analysis [3], price prediction [4] etc. In addition, many authors have also made detailed summaries about this field in their literature reviews [5]. Authors tended to expound the research issues, summarize the methods, and analyze the results and findings. Also, they presented the main challenges and several future directions in this area. Another thrust of Bitcoin entity research, closer to our own interest, has focused on the community discovery. At present, there is not much literature on the Bitcoin network community. Researchers mainly focused on analyzing the network graph property of various communities [8] and then speculating on the characteristics of large entities in the Bitcoin network [10]. Therefore, studying the network of the community, obtaining the structure of the community, and then explaining the transaction pattern of the large Bitcoin community are our research goals in the future. Blockchain technology is favored by many people, because it breaks the traditional centralization and establishes a trust mechanism. The birth of the Bitcoin system, based on blockchain technology, makes it easier and faster to transact among people. The anonymity and decentralization of the Bitcoin system play an important role when people use it to conduct peer-to-peer transactions. Meanwhile, the anonymity of Bitcoin also provides protection for some illegal transactions. Since anyone can create multiple Bitcoin accounts for transactions on the network where their identity is represented by a Bitcoin address consisting of numbers and letters, Bitcoin address cannot reflect the identity of the transaction entity. At the same time, some illegal entities rarely reuse addresses to avoid tracking from enforcement agencies, and instead, they create new addresses for each transaction to reduce their presence on the network. However, previous studies [13] indicated that with the combination of off-chain information [14], addresses could be clustered to the same transaction entity by analyzing the transaction records of addresses in the full ledger data of blockchain , which is beneficial to further identifying entities and inferring relationships between entities. On the other hand, it also exposes the problems of anonymous Bitcoin system mechanisms. Researchers have used these heuristics and off-chain information to develop blockchain analysis software, such as Bitlodine [15], Bitconeview [16], Bitconduite [17] and Bitextract [18]. In this study, we aimed to cluster the addresses using existing heuristic algorithm comprehensively based on the previous work, and to further explore the potential relationships between entities using community detection algorithm.

Contributions of this article
The main contributions of this paper are as follows.
(1). The current methods of Bitcoin address clustering are analyzed and summarized in detail. This paper also aims to explore the relationship among Bitcoin addresses comprehensively, so as to improve the degree of address aggregation.
(2). We analyze the reasons for the low accuracy of detection of Bitcoin change address, combine with a variety of limited conditions for detection of change address, and propose a change address detection process based on different number of output address transactions.
(3). We use the Louvain community detection algorithm and combine the idea of complex network to analyze the relationship among transaction entities, to detect the potential relationships between entities, which could not be identified by ordinary heuristic algorithm.
(4). The clustering rules of the well-known wallet analysis website(wallet explorer, a smart Bitcoin block explorer) are revealed for the first time, and the rules for marking the change address of the website are obtained. And all of these rules are confirmed by the website developer. (5). Through a large amount of data and experiments, we have proved the effectiveness of applying multiple heuristic algorithms, and we can analyze bitcoin transaction activities (e.g. mixing service ) using the research methods of the paper, thus laying a good foundation for the identification of transaction entities.
The remaining of the paper is organized as follows. In Section 2, we briefly introduce the traceability of Bitcoin transaction entities. In Section 3, we summarize the current heuristic algorithms, analyze the problems of the change address detection method in detail, and put forward the change address algorithm process after classifying in accordance with the number of output addresses. In Section 4, we use a variety of heuristic algorithms mentioned in Section 3 to carry out experimental implementation. We elaborate the experimental environment and data sources, give the algorithm flow of address clustering and entity community division, and analyze the performance of the experimental results and method. Finally, Section 5 is the conclusion and prospect of this paper.

Traceability of Bitcoin transaction entities
Blockchain technology makes the Bitcoin ledger public, immutable and stable, which provides a solid basis for inferring the identity of the entity.
Bitcoin transactions have the following important characteristics.
(1). Each transaction acquires the sender's private key to sign. (2). Every transaction will be recorded in the blockchain ledger and anyone can view its transaction details.
Transactions are conducted through Bitcoin address by Bitcoin holders. For scattered Bitcoin users, it is difficult for us to label the users who belong to these Bitcoin addresses. This is one of the reasons why it is difficult to trace the entity when a single user conducts illegal transactions. However, except for a single user, there are many large-scale transaction entities in the Bitcoin system, such as Exchanges, gambling companies, mining pools, currency mixing service providers, etc. Since large entities involve many transactions, it is possible for us to extract the transaction characteristics of these large entities through machine learning, and then use the model to identify other unknown entities that are similar but not labeled.
In general, the traceability of the transaction activities of Bitcoin transaction entities can be started from two aspects. On the one hand, cluster analysis of transaction addresses could be used to find the address groups controlled by each transaction entity. On the other hand, collecting off-chain data is also conducive to linking Bitcoin addresses with entity identities, such as the contextual information with bitcoin addresses appearing on various web pages, personal information filled in by users when registering in bitcoin forums, and website data that specifically analyze bitcoin address tags, etc. Through the methods mentioned above, the transaction activities in which the entity participates can be traced and the information dimension of the entity's identity increased as well.

Methodology
Multiple heuristics were used to address clustering to improve the degree of entity aggregation. In this section, we described a total of six heuristic algorithms, and some of the existing methods were improved. Louvain Community Detection Algorithm was used to divide the entities into communities for further analysis of the relationship among entities.

Multiple heuristic address clustering
Satoshi Nakamoto mentioned in his paper [19] Bitcoin: A Peer-to-Peer Electronic Cash System that in order to reduce transaction fees, no one is willing to make small transfers many times, but tends to combine the balances in his multiple accounts to meet the amount required for the transaction. Based on this statement, many scholars have carried out clustering studies on Bitcoin addresses. One of the most important methods is called the common-input-ownership-heuristic. Because the clustering accuracy of this method is truly high, most current analysis of Bitcoin transaction still relies on this method for clustering study of transaction addresses.

Heuristic algorithm (H1): A heuristic algorithm based on transaction input address, common-input-ownership heuristic
According to the protocol of the Bitcoin system, if you want to use the bitcoin of one address, the private key of that address must be provided, which means that the user of the address must sign for the transaction. Consequently, when multiple addresses are used as the input of a transaction together, we believe that all the input addresses of the transaction can be clustered into an address group. In other words, all the input addresses are controlled by the same transaction entity. The clustering accuracy of H1 can reach 100% without considering the fact that users use mixing services to avoid clustering analysis intentionally. A simple example illustrates the transaction process, as shown in the Figure1. In Figure1. (a), the three input addresses belong to the same transaction entity. In the output addresses, the transaction receiver's account is Address 4, the change amount is 0.4 BTC, and the handling fee for this transaction is 0.1 BTC. If a transaction requires no change, as shown in Figure1.(b), the input amount equals the output amount plus the transaction fee.
In addition to the common-input-ownership heuristic, another heuristic for address clustering is the change address detection heuristic algorithm. In the Bitcoin system, every time a transaction occurs, a node will package the transaction and record it on the blockchain ledger. After removing the transfer amount and transaction fees, the remaining bitcoins will be stored in the change address. Obviously, the bitcoin in the change address belongs to the entity where the input address in the transaction is located. Thus, there is an association between the current change address and the input address. That is to say, they are both controlled by the same entity. At the same time, the bitcoins in the change address will be used as the input amount for a later transaction. So, if you can detect the change address in a transaction record over time, you can link multiple transactions together, increasing the degree of aggregation between multiple different addresses. The research of Elli Androulaki [20] and Sarah Meiklejohn [21] et al. also indicates that change address is an important mechanism to enhance user privacy. The vulnerability existing in the anonymous mechanism of Bitcoin once again proves that the recognition of change

Figure1. Common-input-ownership Schematic diagram
Heuristic algorithm (H2): A heuristic algorithm based on transaction input address and output address, change address detection heuristic In previous studies, there were not many researches on bitcoin change address recognition alone, because the accuracy of the change address detected by the four constraints proposed by Sarah Meiklejohn et al is not high enough to be clustered into the same entity with the input address of the transaction. The four constraints for an output address to be determined as a change address are as follows [21]: (1). The address can only be used as the output of transaction once; (2). The transaction that this address participates in is not a Coinbase transaction; (3). The output address is different from the input address.(It is not a "self-change" transaction); (4). There is no other address in the output accounts which is different from the change address and only appears once in the blockchain ledger.
It should be emphasized that "self-change" refers to the fact that in the Bitcoin protocol, the system specifies the change address for the transaction automatically. The common practice is to provide a change address that is the same as the input address. We should eliminate this kind of "self-change" transaction when we detected the change address.
Consequently, we concluded that the cause of low accuracy of change address clustering mainly lies in: (1). The heuristic condition is based on empirical observation and has strong subjectivity； (2). Bitcoin transaction happens all the time. The first of the four qualifications proposed by Sarah Meiklejohn et al.
required traversal of the entire blockchain ledger transaction data to ensure the address is only used as the output of a transaction once. This process is quite time consuming. And the data set that people used to conduct the experiment could not have included the transaction records that were generated during the experiment. People usually tend to take a certain time node as the criterion and only analyze the transaction data within that time period； (3). The change address can be used as input for a subsequent transaction. When a non-change address is associated with the input address of multiple other transactions, the program cannot detect such an error. Then a large number of addresses are clustered through multiple iteration cycles, and they are wrongly assigned to the same entity. This makes it more troublesome to find and eliminate such false positives when we conduct data inspection in the later stage.
On the basis of previous studies about the detection method of change address, this paper synthesizes the limiting conditions of many scholars on the change address. At the same time, we classify the number of the output address of the transaction, and put forward the process of change address identification.
The change address detection algorithm proposed in this paper can be divided into the following two situations for discussion.
(1). There are only two output addresses for a transaction. a) In the blockchain ledger, address A1 appears only once, while address A2 appears more than once; b) The amount of A1 has more than three decimal places than A2.
If A1 meets the above two conditions, A1 is considered to be a change address.
(2). There are more than two output addresses for a transaction.
When the number of output addresses exceeds two, it can be marked as a change address if a certain output address meets the four qualification conditions proposed by Arah Meiklejohn et al.. The four conditions are described above and will not be repeated here.
In summary, this paper proposed the detection process of change address, as shown in Figure 2.
Output address A1 Determine whether A1 appears only once in all the outputs of the transaction ledger data  Figure 2. Change address detection process Next, combined with the common input ownership heuristic, the change address is used as a link to connect multiple transactions, and then the correlation clustering analysis is conducted for more addresses.
Heuristic algorithm (H3): A heuristic algorithm based on transaction output address, Coinbase transaction mining address clustering heuristic In the Bitcoin system, when a transaction occurs, a node will package the transaction and record it on the blockchain ledger. In this process, the full node is calculated by a random number to obtain the right to billing. When a full node completes transaction packaging first and passes the entire network verification, the node will receive a mining reward. This is a minting transaction belonging to the current block, also known as a Coinbase transaction or a mining transaction. Specifically, in the early days when the Bitcoin system was launched, mining could be divided into two situations: pit mining and single miner mining. However, with the development of technology, the situation of self-mining by users is disappearing gradually, and the trend of mining is evolving towards the emergence of large mining pools. The main reason is that individual miners not only need to spend more money when mining, but also need to purchase mining-specific Application Specific Integrated Circuit (ASIC) chips to get faster computing efficiency. On the other hand, he has to undertake other responsibilities besides mining as a full node, such as maintaining the UTXO set in memory and monitoring the transaction information on the Bitcoin network to verify the validity of the transaction. For pool mining, the owner of the pool will gather the miners together and use a full node to drive a number of mining machines, in which each miner is only responsible for calculating the hash value, and the income from mining belongs to the owner. In the later stage, the owner will conduct secondary distribution of the income according to the proof of work of each miner. As a result, more and more miners are inclined to join the mining pool to reduce the financial and time costs and obtain more stable income. To sum up, we can assume that the output address of a Coinbase transaction is controlled by the same entity. An example of a Coinbase transaction is shown in Figure 3. The difference between H4 and H3 is that the clustering objects of H4 are for multiple mining pools. The heuristic clustering rule is that if there are more than one hundred output addresses in a transaction, and one of the output addresses is known to belong to a certain mining pool, then we assign all output addresses to the mine owner of the certain mining pool [22]. Figure 4, if the Mining pool 1 in the output address is known to be Ant Pool, then the Mining income of all other Mining pools belongs to Ant Pool.

Entity relationship recognition Heuristic algorithm (H5): A heuristic algorithm based on equal currency multi-input multi-output, mixed transaction recognition heuristic
The anonymity of Bitcoin brings convenience for people's transactions and protects the privacy of both parties to the transaction at the same time. Although several heuristic algorithms mentioned above can identify the address group controlled by a single entity, this is a judgment without considering the mixed currency transactions. The mixing service exposes the pseudo anonymity of Bitcoin. The mechanism of the mixing service is that if someone wants to transfer illegally through Bitcoin, he can use the mixing service to hide the illegal proceeds. Mixing services enable users to mix with other users' funds quickly and efficiently and create random mapping relationships between existing user accounts and new accounts to achieve anonymity. Simply put, a mixed transaction is a transaction consisting of multiple inputs and multiple outputs, which makes it difficult to find a one-to-one mapping between the input address and the output address. Thus, it is necessary for regulators to identify mixed currency transactions to narrow the scope of investigation of illegal entities. Judging from the transaction characteristics, we assume that if there are more than four input addresses and output addresses of a transaction, there will be mixed transactions in the transaction [24]. The schematic diagram of mixing service is shown in Figure 5. Based on a large number of address groups clustered by the four heuristic algorithms (H1 to H4), we used Louvain community detection algorithm to further explore the relationship between entities, such as group activities between two different entities through intermediary, so as to achieve the purpose of community division of the transaction entity.
We used Louvain algorithm [25] , combined with complex network theory to identify entity relationships.
(1) Evaluation model  Modularity Louvain algorithm uses modularity to evaluate the quality of a community network division [26]. The physical meaning of modularity is the difference between the number of connected edges of nodes in the community and the number of edges under random conditions. Its value range is , and is generally taken as a measure of obvious community structure in the network. can be calculated as follows: The represents the weight of edges between and . When the network is not a weighted graph, the weight of all edges can be regarded as .
refers to the sum of the weights of all the edges connected to node .
represents the sum of the weights of all the edges in the network. is the community to which node belongs.

Function
indicates that if node is in the same cluster as , the return value is , otherwise returns .  The gain of modularity When a new node joins the community, for example, when node is assigned to community where neighbor node is located, the Louvain algorithm will recalculate the modularity of the community.
can be calculated as follows: represents the sum of the weights of all edges in the current community. represents the sum of the weights of all external edges connected to the community . For a single node, the sum of the weights of the edges connected to the external community is equal to the sum of the weights of all the edges connected to it, i.e., .
(2) Iterative process Step 1: Each node in Figure 6 is treated as an independent community. Corresponding to the Bitcoin network, the address group belonging to the same entity is regarded as an independent community, and the initial number of communities is the same as the number of nodes.
Step 2: For each node , we try to assign the node to the community where each of its neighbor nodes is located, calculate ∆Q before and after the assignment, and record the neighbor node with the largest ∆Q. If Max , node I is assigned to the community where the neighbor node of is the largest; otherwise, it remains unchanged.
Step 3: We repeat step 2 until the communities of all nodes no longer change.
Step 4: We compress all nodes in the same community into a new node and recalculate the weights of edges between nodes.
Step 5: We repeat step 1 until there is no change in the modularity of the entire diagram. In this paper, we use the clustering results of H1, H2, H3 and H4 methods as the input of H6.
Step 1: Groups of addresses belonging to the same entity were clustered by H1, H2, H3, and H4 were used as nodes of the network. At this point, a community corresponds to an entity.
Step 2: To consider the relationship among the entities in the experimental data set, we added an edge between the entities if they meet the following two conditions [27].
-There are less than 10 entities in the output of the transaction; -All recipients are different from the sender.

Experiments and results
In this section, we explained the experimental environment and data sources. We discussed the specific process of the experiment and analyzed the results of the experiment. This included the results of the address aggregation analysis, the effectiveness of the change address detection algorithm, and the entity relationship recognition results.

Experiental environment and data preparation
The experimental data used in this experiment is divided into two parts. One is the Bitcoin addresses to be clustered, and the other one is all transaction records in which these addresses participate. Firstly, we designed a web crawler to crawl Bitcoin addresses. We obtained the Bitcoin address filled in by the user from the user interface in the Bitcointalk forum 1 . The user interface with the bitcoin address is shown in Figure 7. As of February 2021, the forum has approximately 3.1 million user registrations. We crawled the information of the first 30,000 registered users since the establishment of the forum and saved it in csv format.
The record of all transactions that a Bitcoin address participates in comes from the blockchain ledger. We extracted the key fields of information such as the transaction hash of the experimental address, the transaction amount, the hash of the transaction record in which the experimental address participated, and the input and output addresses. And we saved the information in json format.
The operating environment of our experiment is shown in the Table 1.

Experiment process
In this section, we explained the algorithm process of experimental scheme clustering, including the multi-heuristic address clustering algorithm process and entity community division process respectively.

Address clustering process
We combined H1 with the improved change address detection algorithm H2, H3 and H4 to cluster the addresses we collected from the Bitcoin Forum. The clustering algorithm flow is as follows. m--; 26:return ClusterList. Since Bitcoin transactions occur all the time, to reduce the complexity of the experiment, we obtained all transactions involving addresses to be identified in the blockchain ledger (as of September 10, 2020). In the process of detecting the change address in the output of the transaction, we put the change address founded by the program into the list separately for subsequent analysis of the accuracy of the change address.

Community division process
In the initial stage, we regarded a single entity clustered by H1 + H2 + H3 + H4 as an independent community. The number of initial communities is the same as the number of entities. Then, using the complex network idea, edges are added between entities to form an entity transaction network under the two conditions mentioned above. Then we use Louvain algorithm to divide the community. The algorithmic process for dividing the entity community is as follows.

Algorithm 2:
The entity community division algorithm Input: The result of addresses clustering by H1 + H2 + H3 + H4; Output: Community user set. 1:Extract all transactions for the experimental address; 2:Build a transaction network diagram; 3: Initialize best_partition ; 4: while true: 5: while true: 6: for in : 7: Add node to neighbor node and calculate ∆Q; 8: Move into the community where ∆Q is largest; 9: if no vertex moves to new community: 10: break; 11: Rebuild the community, compress all nodes in the same community into a new node； 12: if best_partition not change: 13: break; 14:return communities.

Address clustering results analysis
We selected an address randomly from the experimental data set for analysis. We take the address 18yVghacMaDU8SzG487h2eQvj2SaUCbtXj as an example and iterate twice under the methods H1, H1 + H2, H1 + H2 + H3, and H1 + H2 + H3 + H4 respectively. Through experiments, we found that under different heuristic conditions, the number of addresses obtained was 35,39,120 and 6,469. The result was shown in Figure 8. We plotted them on a logarithmic 10-scale. From the experimental results, it can be seen that one more heuristic condition used, the number of clustered addresses increased with that. This is due to the fact that with each iteration, new addresses associated with the destination address are incorporated into the entity. Also, we need to traverse the transaction records of these new addresses in order to continue to associate with other addresses in the next iteration. By comparison, the number of clustered addresses in our method after two iterations is far more than the number of addresses marked for the wallet belonging to the experimental address in WalletExplorer.
In addition, we noticed that many previous works did not explain the clustering rules of WalletExplorer when comparing their experimental results with WalletExplorer. Therefore, we revealed the rules for address clustering of the website. We found that Walletexplorer adopt the first heuristic algorithm to cluster address that we mentioned in the previous section, so the clustering results of this website can only be used to verify the effectiveness of H1. You can find the interpretation from the website 2 .Besides, we found that the site also marked the change address in each transaction (if already present). Meanwhile, we also inferred the rules of the website for marking the change address through experiments, and obtained his confirmation by contacting the Author (Aleš Janda) of the website. The content of this part will be presented in the following chapters.

4.3.2.Validity analysis of change address detection algorithm
Since there is no perfect standard for the detection of change address, no one can say that his work can be absolutely 100% correct in finding change address. However, based on the previous work, we classified the number of different output addresses of transactions and hope it will be helpful to further improve the accuracy of change address detection. In order to prove whether the change address detection algorithm we proposed is more effective than the previous algorithm, we used two methods to verify.
Method 1:Compare and analyze the marking results of Walletexplorer.
Through a large number of experimental analysis on the change address marked in Walletexplorer and the data of its transaction, we found that the website's judgment on the change address is based on only one principle, that is, output is a change address if it belongs to the same wallet as sender. We still analyze the transactions involved in the experimental address selected in this article. After iterating twice through H1 + H2, we compared the experimental results with the change address marked in Walltexplorer, as depicted in Table 2. Obviously, our detection results for change addresses are more comprehensive than Walletexplorer's detection results, and the results identified by our method for each address all include the change address marked by Walletexplorer, and the coincidence rate is 100%.

Target address
Walletexplorer Our method 18y**j 16 18 Method 2: Compare the address reduction rate of different algorithms.
We compare the experimental results of the change address between the original change address algorithm and our improved algorithm. The results (tTable 3) indicated that the original algorithm found 8,821 change addresses, and our integrated algorithm detected 5,751 change addresses. The average contribution of our algorithm to the address reduction rate is 34.8%. By using the two methods above to analyze the effectiveness of change address detection, the experimental results indicated that our integrated algorithm is more effective than the original algorithm.

Analysis of entity relationship recognition results
(1) Mixed currency transaction recognition results We identified a total of 3,252 transactions using the heuristic conditions defined by H5 in the experimental data that may contain mixing services.
(2) Analysis of community division results Using the Louvain algorithm combined with the complex network, the entities clustered by H1 + H2 + H3 + H4 are further divided into communities. Through experiments, we divided 74,286 entity nodes into 1,247 communities. We used Gephi 3 ,a complex network analysis software, to map transaction networks to further visualize the relationships between entities. The entities incidence relation diagram is acquired as depicted in Figure 9.

Conclusion and futher work
This paper reviewed and summarized six heuristic algorithms for address clustering and entity relationship analysis on the basis of previous work. The comprehensive use of multiple heuristic methods to cluster addresses is conducive to clustering the addresses of large entities. We analyzed the reasons for the low accuracy of the detection results of the existing change address algorithm and improved it. The experimental results indicated that our algorithm is more effective than the original algorithm. In addition, we divided the address groups that have been clustered by the first four heuristic algorithms into communities. For future work, we will further expand the experimental data set and consider the conditions of the heuristic algorithm strictly to further improve the accuracy of address clustering. Moreover, we will collect more off-chain information to add more identity dimensions for the transaction entities, so as to achieve the purpose of tracing the transaction entities and some illegal transaction activities.


A new construction of anticode-optimal Grassmannian codes

In this paper, we consider the well-known unital embedding from $\FF_{q^k}$ into $M_k(\FF_q)$ seen as a map of vector spaces over $\FF_q$ and apply this map in a linear block code of rate $\rho/\ell$ over $\FF_{q^k}$. This natural extension gives rise to a rank-metric code with $k$ rows, $k\ell$ columns, dimension $\rho$ and minimum distance $k$ that satisfies the Singleton bound. Given a specific skeleton code, this rank-metric code can be seen as a Ferrers diagram rank-metric code by appending zeros on the left side so that it has length $n-k$. The generalized lift of this Ferrers diagram rank-metric code is a Grassmannian code. By taking the union of a family of the generalized lift of Ferrers diagram rank-metric codes, a Grassmannian code with length $n$, cardinality $\frac{q^n-1}{q^k-1}$, minimum injection distance $k$ and dimension $k$ that satisfies the anticode upper bound can be constructed.

Introduction
Let F q be the finite field of order q. The projective space of order n over F q , denoted by P q (n), is the set of all subspaces of F n q . Given an integer k such that 0 ≤ k ≤ n, the set of all k-dimensional subspaces of F n q is known as a Grassmannian, denoted by G q (n, k). A subspace code is a nonempty subset of P q (n), while a Grassmannian code is a nonempty subset of G q (n, k). Subspace codes are used in network coding, a method that is far more efficient than classical coding. This paper aims to generalize the results of [4], i.e. to construct maximum rank distance (MRD) codes whose generalized lifts form an anticode-optimal Grassmannian code.
The paper is organized as follows. The next section gives some preliminaries and the construction of subspace codes in [2]. Section 3 shows how to construct MRD codes from linear block codes. Given a specific skeleton code, these MRD codes turn out to be Ferrers diagram maximum rank distance (FDMRD) codes. In Section 4, anticode-optimal Grassmannian code will be constructed using these FDMRD codes and the multi-level construction in [2]. Instead of using pending dots, we will use the multi-level construction as presented in [6]. Lastly, we give our conclusion in Section 5.

Preliminaries
A [k × ] matrix code over F q is a nonempty subset of M k× (F q ). The rank distance between two k × matrices over F q , say A and B, is given by The minimum rank distance of a matrix code C, denoted by δ, is defined by rank-metric code C is a linear code in M k× (F q ) with dimension ρ and minimum distance δ.
The following theorem gives the relationship of the minimum distance of a rank-metric code with its minimum nonzero rank.
A code that attains the bound in Theorem 2.2 is called a maximum rank distance code or an MRD code.
Before we go to Grassmannian codes, we first give two definitions which are vital to our construction. Let A ∈ M k× (F q ). The lift of A, denoted by L(A), is the standard matrix (I k A). We adapted this definition from [4]. For a given matrix A, we denote the row space of A by A . It is well known that the cardinality of G q (n, k) is given by the q-ary Gaussian coefficient Consequently, |P q (n)| = | ∪ n k=0 G q (n, k)|. Furthermore, the subspace distance and the injection distance, defined as respectively, for any A, B in P q (n) are metrics on P q (n), and so in G q (n, k). It is clear that if A and B have the same dimension, then We say that C ⊆ G q (n, k) is an (n, M, d, k) q code in the Grassmannian, or a constant-dimension code, if |C| = M and the minimum injection distance of , then the minimum subspace distance of a Grassmannian code is twice of its minimum injection distance. Equivalently, one may opt to use the subspace distance instead of injection distance.
The next theorem gives the parameters of the resulting Grassmannian code from a lifted rank-metric code.
The maximum number of codewords in an (n, M, d, k) q code is denoted by A q (n, d, k). Bounds for A q (n, d, k) were given in [7], [3] and [11]. The lift of maximum rank distance (MRD) codes in [10] asymptotically attains the bounds given in [3] and [7]. The next theorem gives the bound that were used to check the optimality of our constructed code.
Etzion and Silberstein provided a multi-level construction of Grassmannian codes in [2]. The codes constructed using multi-level construction are called lifted Ferrers Diagram (FD) codes in [6]. Furthermore, an alternative form of the construction of lifted FD codes which uses matrices instead of the usual pending dots were presented in [6]. In this paper, we opt to use the alternative form of the said construction. As defined in [6], for a nonzero X ∈ M k× (F q ), there corresponds a vector prof(X) ∈ {0, 1} n , called the profile vector of X, in which supp(prof(X)) is the set of column positions of the leading ones in the rows of the row reduced echelon form of X. If X = 0, then we set prof(X) to be the zero vector. Associated with a vector space U ∈ G q (n, k), k > 0, is a unique k × n matrix X U in row reduced echelon form such that U = X U . Now define the profile vector of U , denoted by prof(U ), given by Some papers denote this set as prof −1 (b).
Given any binary vector b of length n and Hamming weight k, the permutation matrix with respect to b, denoted by P (b), is the n × n permutation matrix whose rows indexed by supp(b) form P (b) supp(b) = I k 0 k×(n−k) and the remaining rows of P (b) form P (b) supp(b) = 0 (n−k)×k I (n−k) , where b +b is the all one vector of length n. Example 2.7. Let b = (1, 0, 0, 1, 0). Sob = (0, 1, 1, 0, 1).
We changed some notations in the next definition to be consistent with our earlier notations but the essence is exactly the same.
Definition 2.8. [6] Let b be a binary vector of length n and Hamming weight k. For X ∈ M k×(n−k) (F q ), define the generalized lifting of X with respect to b, denoted by Λ b (X), as Definition 2.9.
[6] Let b be a binary vector of length n, Hamming weight k and let C b be a [k × (n − k)] rank-metric code. The set We now present some necessary conditions for the definition of lifted FD codes which were established in [6]. Let Q = [a ij ] be the n × n upper triangular matrix with a ij = 1 if j ≥ i and a ij = 0 otherwise. Given a binary profile vector b of length n and Hamming weight k, regarded as an element of Z 1×n , define the vector c(b) ∈ Z 1×n via Let X = [x ij ] ∈ M k×(n−k) (F q ). According to [6], Λ b (X) is guaranteed to be in the Schubert cell corresponding to b provided that for 1 ≤ i ≤ k and 1 ≤ j ≤ n − k, An FD(b) code is a rank-metric code C b ⊆ M k×(n−k) (F q ) in which each codeword satisfies (3) while the code Λ b (C b ) is referred to as lifted FD(b) code.
We now consider the minimum distance between elements in distinct Schubert cells. Let u, v ∈ F n 2 and u = v. Now define the logical AND of u and v, denoted by u ∧ v, as (u ∧ v) i = u i v i . Also the asymmetric distance between u and v, denoted by d a (u, v), is given by Theorem 2.10. [5] Let u, v ∈ F n 2 , u = v, U ∈ S q (u) and V ∈ S q (v) and d(U, V ) be the injection distance of U and V . Then d(U, V ) ≥ d a (u, v).
The following steps to construct an (n, M, d, k) q code C are from [5].
1. Choose a binary constant weight code B of length n, Hamming weight k, and minimum asymmetric distance d.

2.
For each b ∈ B, consider an FD(b) code with minimum rank distance d.

Construct the lifted FD
The cardinality M of C greatly depends on the choice of B.

Rank-metric codes and Grassmannian codes
The following well-known theorem will be the cornerstone of our construction.
be a monic irreducible polynomial and X be its companion matrix. Then the mapping induces a unital embedding Let n be a positive integer. Note that τ can be extended to the following monomorphism φ defined by φ : Lemma 3.2. If C is a linear block code of length n over F q k then C ∼ = φ (C) as F q −vector spaces.
The following theorem is a generalization of Theorem 3.7 of [4].
Theorem 3.3. Let C be a linear block code of length n over F q k and ρ its dimension as an F q -vector space. Then ii. Λ (φ (C)) is a (k + kn, q ρ , k, k) q code, iii. the pairwise intersection of codewords of Λ (φ (C)) is trivial.
Proof. Let C be a linear block code of length n over F q k and ρ its dimension as an F q -vector space. By Lemma 3.2, C and φ (C) are isomorphic as F q −vector spaces. Hence, the dimension of φ (C) is ρ. Consider the case n = 1. Since F q k is a field, then ∀α ∈ F q k − {0}, φ (α) = τ (α) ∈ M k (F q ) is a unit and thus has rank k, where τ is as defined in (5). Thus, τ (α 1 ) τ (α 2 ) ... τ (α n ) has rank k for any positive integer n where α i ∈ F q k − {0} for some i, 1 ≤ i ≤ n. Therefore, by Theorem 2.1, the minimum distance of φ (C) is k.
Clearly, ii. follows directly from Theorem 2.5 to be equal to 0. Therefore, the pairwise intersection of codewords of Λ (φ (C)) is trivial.
Note that for any positive integer n, the rank-metric code φ(F n q k ) meets the Singleton bound as given in Theorem 9 of [7].

Anticode-optimal Grassmannian code
Now we construct Grassmannian codes using the multi-level construction in [2] and the result in Theorem 3.3. Let n be a multiple of k and n > k. For the skeleton code B, choose Clearly, B is a binary constant weight code of length n, weight k, and minimum asymmetric distance k.
Let Q = [a ij ] be the n × n upper triangular matrix with a ij = 1 if j ≥ i and a ij = 0 otherwise. Then, . Lemma 4.1. Let n be a multiple of k, n > k and where 1 ≤ ≤ n−k k . Then, for 1 ≤ ≤ n−k k , C b is an FD(b ) code and has minimum rank distance k.
Proof. Recall that for a rank-metric code C to be an FD(b) code, C must be a subset of M k×(n−k) (F q ) and all of its codewords must satisfy (3). Let 1 ≤ ≤ n−k k . Clearly, Hence the entries in the first n − k − k columns of the elements of C b must be all zero. Clearly, C b satisfies this. Lastly, by Theorem 3.3, φ(v) has minimum rank distance k. Clearly, C b has minimum rank distance k. Although C b0 does not have a minimum distance k as required in [2] and [6], it will not pose any problem since the resulting Grassmannian will still have a minimum distance k. Ironically, b 0 is included in Example 10 of [2]. Note also that C b0 is the only rank-metric code that will satisfy b 0 . Now we are ready to construct the lifted FD(b) code Λ b (C b ). By Definition 2.8 and Definition 2.9, The lifted FD code, denoted by Ω(B), is given by As an immediate consequence of Lemma 4.1 and Theorem 4.2, we have the following theorem. Since C b0 does not have a minimum distance k and b 0 appeared only as an example in [2], we will separate the case of b 0 in our proof.
Proof. For 1 ≤ ≤ n−k k , C b is an FD(b ) code with minimum rank distance k by Lemma 4.1. Now, Note that Λ b0 (C b0 ) has only one codeword. Therefore, Ω(B) has minimum distance k.
Note that Ω(B) attains the Anticode bound. The following illustrates the construction of an Anticode-optimal Grassmannian code.
Theorem 4.3 is a generalization of Theorem 3.16 in [4] and is similar with the construction of spread codes in [8]. Note that by choosing v to be in a different linear block code C of length over F q k instead of F q k in Lemma 4.1, one may construct a Grassmannian code that is not a spread code.

Summary and conclusion
We presented two constructions of Grassmannian codes for any length, over any finite field and whose dimension is equal to its minimum injection distance. These two constructions are generalizations of some constructions in [4]. The first construction uses a linear block code to construct a rank-metric code. The resulting rank-metric code was then used to create a Grassmannian code that meets the Singleton bound. The second construction uses the results in the first construction together with the concept of Ferrers diagram to get an anticode-optimal Grassmannian code. The resulting code from the second construction is similar to the construction of spread codes found in [8].