An improvement of Q-Learning based on attenuation oscillation curve for path planning

Authors: shiwen  sheng
yi  zuo
yuzhou  lu
wei  wu
Venue: IEEE_org_ICIST_2024_Conference
Published: 2024-07-30 13:53:30

Abstract: Abstract—Reinforcement Learning can be applied to many fields, but it is still a problem how to balance exploration and exploitation it reasonably in the strategy of action selection. In order to solve the problem of path optimization in unknown environment, a model based on Q-Learning algorithm is proposed to balance the exploration stage and the exploitation stage. In this paper, based on Q-Learning algorithm, attenuation oscillation curve combined with it. The algorithm can reasonably adjust the time allocation of exploration stage and exploitation stage according to the current iteration times and iteration states. Effectively avoid the problem of over- exploitation and over-exploration of algorithms. In the path optimization simulation experiment, Q-Learning algorithm based on oscillation attenuation is compared with classical Q-Learning algorithm. Experiments show that for the same environment full of obstacles, Q-Learning algorithm based on oscillation attenuation can carry out path planning with better number of steps in a shorter search time, and has the ability to jump out of the local optimal.

Main paper: 
 = 4: 
 1, 56/7 < & < 9: 0, ;<ℎ' 4When ε = 1, the algorithm is in the exploitation stage. When ε = 0, the algorithm is in the exploration phase. The balance between the exploration stage and the exploitation stage can be controlled by changing the value of the independent variable T and the change rate of the function value y. The attenuation oscillation curve is shown in Fig. 2 . When the agent passes through the area of the curve AOC indicated by the green bracketed arrow, the selection strategy of the action is random selection. Instead, the action selection strategy follows the Q table. As the number of iterations increases, the upper limit of switching threshold UP increases in the same direction as the number of iterations, which means that the random exploration time of the agent decreases. However, due to the lower limit of the switching threshold DOWN, the agent will also conduct some random exploration. If the algorithm does a lot of exploration in the early stage, that is, there are a lot of overflow times, the parameter DOWN will move down beyond AOC. In this case, the algorithm will converge completely in the later stage to avoid the selection of invalid actions.In the process of ε-decreasing, the ε value gradually decreases with the increase of the number of iterations, and the change of ε value in ε-first is first 1 and then 0, which is combined with the characteristics of the attenuation oscillation curve to form the AOCQ-Learning algorithm in this paper.The attenuation oscillation curve is introduced into Q-Learning algorithm, and the algorithm is divided into exploration stage and exploitation stage by comparing function value and switching threshold. According to the iteration state of the agent, the time proportion of the exploration stage and the exploitation stage is adjusted. The original Q-Learning algorithm is improved as follows.⑴ After initializing the Q(s,a) value table, in order to avoid blind random exploration by the agent, the greedy strategy (ε = 1) is used at the beginning stage. When the number of successful explorations is greater than the constant N, random exploration is added.⑵ In each iteration of the algorithm, the early warning signal K1 is set for the number of iteration steps. If the number of single steps exceeds K1, the exploration phase time will be reduced and the exploitation phase time will be increased.Step overflow limit signal K2(K1<K2) exists in each iteration of the algorithm. When the number of steps in a single iteration exceeds K2, the algorithm actively interrupts the exploration and starts the iteration again.⑷ Set parameters DOWN and UP to control the switch between the exploration phase and the exploitation phase. Specific AOCQ-Learning pseudocode such as Algorithm2: Where, the constant N represents the number of times that the Q table stage is fully exploited in the initial period; Parameters [DOWN, UP] represent the thresholds of the switch exploration stage and the exploitation stage in the attenuation oscillation curve. The upper threshold UP changes with the number of iterations episode, while the lower threshold DOWN is related to step overflow. The parameter T is the independent variable of the attenuation oscillation curve. By controlling the change rate of independent variable T, the proportion of exploration stage time and exploitation stage time in a single iteration can be controlled. Parameter K1 represents the early warning signal of the number of steps in a single iteration, which is related to the average number of steps in previous iterations; The parameter K2 represents the maximum limit on the number of steps in a single iteration; The episode parameter indicates the number of iterations. The parameters are described in TABLE. I.In AOC-Q-Learning algorithm, by changing the growth of threshold values UP and DOWN and the change rate of time variable T, the action selection strategy can be switched. Among them, the oscillation attenuation curve involves parameters / and / 0 . The parameter / controls the amplitude of the attenuation oscillation curve, as shown in Fig. 3 . The smaller the value of W_1, the faster the amplitude of the attenuation oscillation curve decreases. Therefore, if the value of |/ | is smaller, the convergence time of the algorithm will be shorter, and the risk of the algorithm falling into local optimal will be increased. The parameter / 0 controls the oscillation frequency of attenuation oscillation curve, as shown in Fig. 4 . The higher the value of / 0 , the higher the oscillation frequency of the attenuation oscillation curve. Therefore, if the value of / 0 parameter is too small, the switching period between the exploration stage and the exploitation stage is too long, the overflow times of the algorithm in the early iteration stage will increase, and the algorithm will converge in advance and easily fall into the local optimal. However, if the / 0 parameter is too large, the switching period between the exploration stage and the exploitation stage is too short, which leads to slow convergence in the later iteration of the algorithm and increases the exploration time. Identify applicable funding agency here. If none, delete this text box. 
i.introduction: 
 Reinforcement learning has received extensive attention, such as game theory, operations research, cybernetics, simulation optimization and so on. But some challenges come along. One of the challenges that arises in reinforcement learning is not other types of learning, but the tradeoff between exploration and exploitation. In order to get a large number of rewards, the agent must choose the behavior that it has tried in the past and found to be effective in generating rewards. But to discover such a behavior, it must try a behavior it hasn't chosen before. In order to be rewarded, the agent must take advantage of what it has already experienced, but it must also explore in order to make better choices of action in the future [1] Among them, reinforcement learning is applied to the optimization of path planning. The purpose of motion planning is to find a feasible path from the initial state to the target region in the configuration space without colliding with any obstacles [2] . At present, the main algorithms applied to path planning include artificial potential field method [3] , viewable method [4] , particle swarm optimization algorithm [5] , AMP-PSO [6] and so on. In this paper, Q-Learning [7] algorithm of reinforcement learning is applied to path planning. Q-Learning algorithm is a classical reinforcement learning algorithm. It uses Markov decision process (MDP) to describe the path planning problem [8] . For example, Q-Learning algorithm is applied to fuzzy output feedback tracking control problem [9] .Many researchers have improved the balance between exploration stage and exploitation stage in Q-Learning algorithm. Maozu Guo applied the criteria in the simulated annealing Algorithm to the SA-Q-Learning algorithm for exploration and exploitation [10] . It allows the agent to choose an action other than the strategy currently learned, and the probability of choosing the action increases with the increase of the proximity between its Q value and the optimal action Q value, that is, the probability of the agent choosing an action closer to the optimal action is greater than that of other actions. In addition, with the agent's continuous interactive learning of the environment, the set temperature parameter T approaches 0, and the algorithm approaches convergence. In addition, a number of other approaches have been applied to the exploration and exploitation balance of reinforcement learning, such as many approaches that utilize counters [11] , model learning [12] , or reward comparisons in a biologically inspired way [13] .The ε-greedy [14] is a common algorithm in Q-Learning algorithm. When selecting an action, the agent has a certain probability to explore the new environment, instead of always following the learned strategy. Compared with the traditional Q-Learning algorithm, ε-greedy has a certain probability to find the optimal action, but with the increase of learning time, the algorithm still refuses to select the optimal action with a probability of ε. This reduces the expressiveness of Q-Learning algorithm and increases the operation time. In order to solve the disadvantage of ε-greedy, the method of ε-decreasing [15] is proposed. In this method, the initial value of ε is large, and from the perspective of single iteration, the ε value increases with the increase of the number of steps in a single iteration, which enhances the ability of the agent to explore the new environment. From the perspective of the number of global iterations, the ε value decreases with the increase of the number of iterations to avoid over-exploration in the later stage. In addition, a new equilibrium idea ε-first [16] is proposed, which assigns the value of ε to 1 at the beginning of the main operation, and the agent is in a state of full exploration of the environment. After training for a certain number of times, ε is assigned to 0, and the agent is in the state of fully utilizing the Q table. In view of this, I combine ε-decreasing with ε-first to optimize Q-Learning by using the characteristics of the attenuation oscillation curve.We will propose a new optimization model. The balance between exploration and exploitation of Q-Learning algorithm is optimized based on oscillation attenuation curve(AOCQ-Learning). The time allocation of exploration stage and exploitation stage is controlled reasonably by using the oscillation attenuation characteristic of attenuation oscillation curve. In this paper, the change of ε value and the change of proportion time is mainly controlled by the attenuation oscillation curve and some constraint parameters. The algorithm is applied to the path optimization experiment, and it is found that it has better performance.The rest of this article is organized as follows. In the second part, the theory of reinforcement learning is introduced. The third part introduces the AOCQ-Learning algorithm model in detail. The fourth part introduces the experimental part of the application of several algorithms in path planning. The fifth part is the conclusion of this paper.The core elements of reinforcement learning include: strategy, income, value function and environment. The agent constantly interacts with the environment, the environment gives feedback to the agent's actions in the form of reward signals, and through continuous iteration, the strategy is gradually formed. The agent accomplishes the goal according to the learned strategy. The specific structure is shown in Fig. 1 . Q-Learning algorithm is a value iterative algorithm, which approximates the optimal strategy by constantly updating the Qtable . It is one of the most widely used algorithms in reinforcement learning.In the Q-Learning algorithm, the strategy established by the agent according to the income is represented by the Q(s , a) value table, which records the Q( s , a) value corresponding to all actions a under different states s, and guides the agent to complete the goal through the Q(s , a) value table. The update of the Q(s , a) value follows the Bellman formula [1] , as follows., ← , + + max , -, 1In the formula, Q(st , at) represents the Q value corresponding to the state-action (st , at); α represents the learning rate, indicating the degree to which the Q value learns from the updated Q value change; Gamma represents the discount rate, indicating how much the agent values future returns, and the discount rate γ→0 indicates that the agent is shortsighted and only cares about maximizing current return. The standard Q-Learning algorithm flow is as follows.Algorithm1. Q-LearningStep1.Initialize arbitrarily all Q(s,a) values;Step2.Repeat (for each episode):Step3.Define an initialization state s0, s = s0;Step4.Repeat (for each step in the episode):Step5.Select an action a ∈ A(st) according to the policy;Step6.Execute the action a,Observe the new state st+1,receive immediate reward rt+1 ;Step7.Update policy(Q-values table) according to:EQUATIONStep8.st = st+1;Step9. If st is one of the goal states,episode += 1;Else go to Step5;Step10.If the desired number of episodes have been investidated,END; Else go to Step3;The original Q-Learning algorithm uses greedy strategy, that is, the action corresponding to the maximum Q value is selected, which is completely dependent on the strategy that has been learned. This situation will make the algorithm very easy to fall into the local optimal, and with the increase of learning time can not jump out. The ε-greedy strategy is introduced.In the Q-Learning algorithm based on ε-greedy strategy, a greed coefficient factor ε(0<ε≤1) is set. It means that when the agent chooses an action, there is an ε probability that it chooses randomly among all the actions, and there is a probability of 1ε that it chooses the action with the greatest return. The algorithm indicates that the ε-probability of the agent does not depend on the learned strategy choice action, and if the agent falls into the local optimal, there is a certain probability of jumping out of the local optimal. However, Q-Learning algorithm based on ε-greedy strategy always explores with a certain probability in the later stage, and the convergence time will increase. Therefore, an algorithm for dynamic attenuation of greed factor is proposed.In the traditional Q-Learning algorithm based on ε-greedy strategy, the greed factor ε is a constant. Therefore, the εdecreasing algorithm was adopted [15] . Where the greed factor ε changes with the number of iterations and the number of steps in a single iteration, the specific formula is as (2) .ε = ε * 0.1 !"#$ " 2In formula (2), the parameter "episode" represents the number of iterations, and "step" represents the number of steps in a single iteration. At the early stage of iteration, due to less understanding of the environment information, the greed factor ε is set to a large size to ensure full exploration of the environment. From the perspective of single iteration, ε increases with the increase of the number of steps. With the increase of the number of iterations, the agent's mastery of environmental information more requires the agent to use the learned empirical knowledge for action selection, so the greed factor ε is in a gradual decline process.The idea of the ε-first method [16] is to initially set the value of ε to 1, so that the agent is in the full exploration state, and after a period of training, set the value of ε to 0, so that the agent is in the full exploitation environment state. The number of training acts is set according to the actual situation.In this paper, attenuation oscillation curve is introduced into Q-Learning algorithm, and its expression is shown as formula (3) . & = ' ( ) * × sin / 0 × 1 3Balance the exploration phase and the exploitation phase by changing the thresholds [DOWN,UP]. Take formula (4) as follows. 
 
 Appendix:  



Reviews: review: title: title: The paper is logically clear, the simulation results are credible. The following suggestions need to be considered:
main_review: main_review: 1. What impact will the inability to achieve this balance between exploration and exploitation of the Q-Learning algorithm have, and how does the proposed new optimization model achieve this balance?
2. How does the introduction of oscillation attenuation curves help with the execution of the Q-learning algorithm?
3. In the Abstract, the logic of the sentence “based on Q-Learning algorithm, attenuation oscillation curve is introduced into it” seems unreasonable.
4. Some grammar issues need to be checked and modified, such as "how to exploration and exploitation", etc.
title: title: This paper proposes a model based on Q-Learning algorithm to balance the exploration stage and the exploitation stage. Meanwhile, the experiment verified the effectiveness of the method. However, the following comments should be considered in the revision.
main_review: main_review: Question 1:
How does the attenuation oscillation curve (AOC) specifically improve the balance between exploration and exploitation in the Q-Learning algorithm compared to classical methods, and what theoretical foundations support its effectiveness?
Question 2:
What are the computational complexities introduced by incorporating the attenuation oscillation curve into the Q-Learning algorithm, and how do these complexities affect the overall performance and scalability of the proposed approach?
Question 3:
Please provide a more detailed analysis of the parameter tuning for the attenuation oscillation curve? How sensitive is the algorithm's performance to variations in these parameters, and what guidelines are provided for setting them in different types of environments?