3.1. Reinforcement learning

RL is a very dynamic area of machine learning in terms of theory and application. RL algorithms inspired by animal and human learning and make an agent connected to his environment via perception and action [Reference Mehta15]; that means the agent interacts with its environment without any explicit supervision, the reward function is positive when the agent takes “good” action or it can be negative when it takes a “bad” action. RL is based on MDP which is described by ref. [Reference Sutton and Barto16]:

• • State s and State space S

• • Action a and Action space A

• • Reward function R(s,a)

• • P is the transition state probability for $s \in S$ , and $a \in A$ .

• • $\gamma \in [0,1)$ is the discount factor which describes how the agent considers the future reward.

• • Policy ( $\pi$ ): The strategy that the agent takes to estimate next action based on the current state.

• • Value function (V):V $\pi$ (s) is defined as the expected long-term return of the current state s under policy $\pi$ .

• • Q-value (Q): Q-value is similar to Value V, but it takes an extra parameter. Q $\pi$ (s, a) refers to the long-term return of the current state s, taking action a under policy $\pi$ .

In RL, the agent uses its past experiences to learn the optimal policy; learning this policy involves estimating a value function Q-value; $Q_{\pi }(s,a)$ denotes the expected accumulated discounted future reward $R_{t}$ obtained by selecting action “a” in state “s” and following policy $\pi$ ; thereafter, we can express the return value as follows [Reference Tijsma, Drugan and Wiering3]:

(1) \begin{equation} Q_{\pi }(s,a)=E_{\pi }\Big [R_{t}\mid s_{t}=s, a_{t}=a \Big ] \end{equation}

3.2. Q-learning

Q-learning is one of the most challenging algorithm of RL, it is an off-policy temporal difference learning technique [Reference Sutton and Barto16], with an off-policy algorithm where the agent takes the action from another policy for learning the value function. The author of this paper [Reference Miljković, Mitić, Lazarević and Babić17] summarizes the concept of Q-learning algorithm.

If the agent visits all state-action pairs infinitely, Q-learning converges to the optimal Q-function and the agent can get a set of state-action with maximum cumulative reward. The basic Q-learning algorithm update rule of the value function $Q_{t+1}(s,a)$ at time step $t+1$ is given by the formula [Reference Tijsma, Drugan and Wiering3]:

(2) \begin{equation} Q(s_{t},a_{t})= (1-\alpha )(Q(s_{t},a_{t})+\alpha (r_{t}+\gamma \text{max}((Q(s_{t+1},a))) \end{equation}

$0 \leq \alpha \leq 1$ learning rate controls the learning speed, $\gamma$ discount factor. A pseudo-code of general Q-learning algorithm is present with Algorithm 1:

Algorithm 1 :

The pseudo-code of general Q-learning algorithm

As essential part of Q-learning in finding an optimal policy is the selection of action $a_{t}$ in the state $s_{t}$ , there is a tradeoff between choosing the currently expected optimal action or choosing a different action in the hope that it will yield a higher cumulative reward in the future. The step four of the algorithm 1 is the main idea of the contribution of this article. To solve this problem, we construct an unknown environment with many obstacles, in which there is a goal state, and the task of the mobile robot is to find an optimal path in the shortest possible time with a small convergence rate.

3.3. Path planning for mobile robot

Path planning is a difficult point in robot navigation. After specifying the environment, the robot must move while avoiding obstacles. An excellent planning technique that saves a lot of time and effort avoids collisions with obstacles. Over the past two decades, several scheduling techniques have been proposed. Each of these has had its own advantages and disadvantages over other methods. The different methods of path planning can be divided into Classical Control and Intelligent planning.

In ref. [Reference Anis, Hachemi, Imen, Sahar, Adel, Mohamed-Foued, Maram, Omar and Yasir18], they classify different path planning classes for mobile robots. According to the environmental knowledge, the nature of the environment, and the method of solving the problem, it can be divided into three categories, as shown in Fig. 2.

Figure 2.

Path planning categories.

3.4. Exploration strategies

This section contains a catalog of commonly used exploration strategies. The techniques outlined below can be divided into two categories: undirected and directed. Undirected exploration techniques are driven by randomness, independent of the historical exploration environment of the learning process. The simplest example is a random walk when an agent performs random actions [Reference Pang, Song, Zhang and Yang26]; the $\epsilon$ -greedy [Reference Kim and Lee11], and Boltzmann distribution [Reference Pan, Cai, Meng and Chen27] are other examples of undirected exploration techniques. In contrast to the undirected exploration techniques discussed above, directed exploration strategies consider the history of agents in the environment to influence which parts of the environment the agent will explore further, as example of basic directed exploration strategies: counter-based exploration, error-based exploration, and recency-based exploration [Reference Thrun5]. Figure 3 summarizes all exploration techniques mentioned in articles [Reference McFarlane4, Reference Thrun5].

There is an algorithm called upper confidence bound (UCB), which is an intelligent, targeted, counter-based exploration strategy that performs well in the RL multi-armed bandit problem [Reference Mahajan, Teneketzis, Hero, Castañón, Cochran and Kastella28]. In this paper, we study $\epsilon$ -greedy and Boltzmann distribution strategies.

4.1. Epsilon-greedy strategy

In Q-learning, we choose an action based on a reward. The agent always chooses the optimal action. Therefore, it generates the largest possible reward for a given state. In $\epsilon$ -greedy action selection, the agent uses both exploitation to exploit prior knowledge and exploration to find new options. The aim is to strike a balance between exploration and exploitation [Reference Kim, Watanabe, Nishide and Gouko29]. $\epsilon$ -greedy exploration is an exploration strategy in RL that performs an exploration action with probability $\epsilon$ and a exploitation action with probability $\epsilon -1$ .

The greedy strategy selects actions according to the following Eq. (3).

(3) \begin{equation} a(x)=\text{argmax} Q(s,a_{t}) \end{equation}

Now let us look at the implementation of the greedy strategy, which is a simple algorithm to understand and implement, the pseudo-code below that represents the principle of the algorithm.

Algorithm 2 :

Algorithm of ϵ-greedy policy

Figure 3.

Exploration-exploitation methods.

4.2. Boltzmann distribution strategy

A smooth transition between exploration and exploitation can be described using Boltzmann distribution which uses the Boltzmann distribution function [Reference Asadi and Littman30] to assign a probability P to the actions. $P(s_{t}, a)$ has the following form:

(4) \begin{equation} P(s_{t}, a) = \Big [ \text{exp}(Q(s_{t}, a_{t})/ T)\Big ]/ \Big [ \sum \text{exp}(Q(s_{t}, a_{t})/ T)\Big ] \end{equation}

where T is the temperature that controls the degree of randomness of the choice of action with the highest Q-value. When T = 0, the agent does not explore at all, and when $T \rightarrow \infty$ , the agent selects random actions. Using softmax exploration with intermediate values for T, the agent still most likely selects the best action, but other actions are ranked instead of randomly chosen.

4.3. Proposed method

In this paper, we propose a new approach to solve the exploration-exploitation dilemma, so we combine the Boltzmann distribution with the $\epsilon$ -greedy strategy. As an advantage, the new proposed strategy avoids the local optima and speeds up the entire Q-learning algorithm. The strategy is described with Algorithm 3:

Algorithm 3 :

Algorithm of proposed policy

This Q-learning-based enhanced strategy for solving mobile robot path planning problems in complex environments with many obstacles is a novel approach. We evaluate the method considering the number of steps, speed of environment exploration, finding the optimal trajectory, and maximizing the accumulated reward.

Our approach consists of a tradeoff between two exploration strategies according to $\epsilon$ of $\epsilon$ -greedy policy and P of Boltzmann distribution. To improve our strategy, let us create an algorithm with two modules: environment creation and application of the Q-learning algorithm.

In the environment creation function, we will simulate the block as follows:

• • Create environments, obstacles, start and end positions.

• • Define a list of possible actions.

• • Create a function that returns a list of states and reward value and predict the next state.

Applying the Q-learning algorithm, we simulate the following blocks:

• • Define Q-table with actions in columns and states in rows

• • Define an exploration strategy for choosing actions

• • apply the Q-learning algorithm with Bellman equation for path planning

As the last step of the path planning algorithm, we apply the Q-learning algorithm to the created environment, taking the number of steps of the mobile robot, the reward function, and the path founded. Finally, all results are presented graphically.

5.1. Simulation

Simulations were conducted in a virtual environment with obstacles, where a mobile agent is an object that moves around and studies it to find a path to a goal point. The program code is written in Python 3. We exploit Q-learning algorithm with different parameters and different action selection strategies. In all simulations, the total number of episode was set to 1000.

The discount factor affects how much weight it gives to future rewards in the value function. It is constrained to be less than 1 is a mathematical trick to make infinite sums finite. This helps prove the convergence of an algorithm. A discount factor $\gamma$ = 0 will result in states/actions values representing the immediate reward, and the agent will be completely myopic, while a higher discount factor $\gamma$ = 1 will result in an agent which evaluates each of its actions according to the sum total of all his future rewards [Reference François-Lavet, Fonteneau and Ernst31]. The convergence is influenced by the discount factor depending on whether it is a continual task or an episodic one. In a continual one, $\gamma$ must be between [0, 1). Since most actions have short-lived effects, $\gamma$ should be chosen as high as possible, so set the value $\gamma$ = 0.9.

A common problem faced when working on Q-Learning projects is the choice of learning rate. The learning rate or step size is a hyper-parameter that determines to what extent newly acquired information overrides old information.

When we give a perfectly configured learning rate, the model will learn to best approximate. Generally, as performed in this paper [Reference Kim, Watanabe, Nishide and Gouko32], a factor of 0 makes the agent learn nothing (exclusively exploiting prior knowledge), while a factor of 1 makes the agent consider only the most recent information (ignoring prior knowledge to explore possibilities). Unfortunately, we cannot analytically calculate the optimal learning rate for a given model. Instead, we have to find a good learning rate through trial and error. The traditional default value for the learning rate is between 0.1 and 0.9, and we pick the learning rate and fix it at $\alpha$ = 0.5.

To summarize the related parameters in our experiment, we set it in Table I.

Table I.

Initial parameter of simulation.

5.1.1. Epsilon-greedy

The epsilon ( $\epsilon$ ) parameter introduces randomness into the algorithm and forces us to try different actions. This will prevent you from getting bogged down in local optimizations. When epsilon is set to 0, we never explore and always use the knowledge we already have. Conversely, setting epsilon to 1 forces the algorithm to always perform random actions and never exploit past knowledge. Usually, epsilon is chosen as a decimal close to 0, so we choose $\epsilon$ = 0.01. The results of mobile robot path planning based on $\epsilon$ -greedy action selection are shown in Fig. 4.

Figure 4.

Results of Q-learning based $\epsilon$ -greedy action selection.

5.1.2. Boltzmann distribution

The convergence of the algorithm is highly dependent on the T parameter, so special attention should be paid to its range and rate of change. Choose T = 0.02 according to ref. [Reference Sichkar33] in which the author choose to work with this value and the results are performed invirtual environments. Figure 5 shows the results of Q-Learning path planning using the Boltzmann distribution.

Figure 5.

Results of Q-learning based Boltzmann distribution action selection.

5.2. Discussions

For each simulation, we plot the number of steps for the entire episode, the cost function for each episode, the paths found, and the cumulative reward for each episode. The results show that the three methods work well and complete the task of finding paths for mobile agents (4d, 5d, 6c). The graph (4b, 5b, 6b) shows that the number of step decrease faster for the proposed method than other methods in finding the path, even the shortest path for achieving the goal consists of 42 steps for both $\epsilon$ -greedy and proposed strategy and 48 step for Boltzmann distribution. The graphs in Figures (4d, 5a, 6a) illustrate the difference in performance of the above methods. It can be seen that compared with the Boltzmann distribution and the proposed method, $\epsilon$ -greedy requires more learning cost, which means that the $\epsilon$ -greedy policy requires more steps to reach the goal. The Figs. 4(c), 5(c), 6(b) represent a form of reward signal, from which we can see that at the beginning of learning, the reward signal is −1, which means that the robot did not reach the goal. Initially, the robot will make bad moves, which is normal because the RL system starts with no prior information about the environment. Then, it fluctuates between +1 and −1 with a high switching frequency. We find that the penalty (r = −1) decreases with the learning process, and the reward at the end of learning is stabilized at the value +1, proving that the system is learning the desired behavior.

Comparing the graphs, we find that $\epsilon$ -Greedy takes more time to learn and does not stabilize until the end; the proposed method and the Boltzmann distribution reach the goal almost simultaneously, although the proposed method stabilizes faster. If we compare the graphs of the $\epsilon$ -Greedy and Boltzmann distribution strategies, we can see that $\epsilon$ -Greedy has the slowest performance improvement and takes more time to reach the goal even with the shortest path. In the proposed method, we take advantage of each strategy; we take the shortest path of $\epsilon$ -Greedy and the speed of the Boltzmann distribution, so the proposed strategy performs better than the other two strategies.

The results of each algorithm are shown in Table II. The first line shows the $\epsilon$ -Greedy results, the second line represents the results obtained using Boltzmann distribution, and the third line shows the results of the proposed algorithm in this paper.

Table II.

Results of the simulation.

Figure 6.

Results of Q-learning based on proposed method.

The simulation of the reward function in different episodes shows that at the initial time, the robot cannot reach the goal and the reward function = 0, as shown in Fig. 7(a), then increasing the number of steps allows the robot to learn the location of obstacles and the environment structure, for example, in episode 200 presented with Fig. 7(b) the robot took over 1750 steps. But after episode 300 which is exposed in Fig. 7(c), the robot can reach the goal, the reward function becomes 1, but the path is still long, and surroundings 300 steps, the robot keeps using and exploring its knowledge to make the shortest reach way. So in episode 600 which is displayed in Fig. 7(d), the optimal trajectory of the robot is about 40 steps.

Figure 7.

Reward function for different episodes.