The expected reward for taking action $a_k$ in state $s_k$ at time $k$ and transitioning to $s_{k+1}$ is: \[ r_{k+1} = \sum_{s_{k+1} \in \mathcal{S}} P(s_{k+1} | s_k, a_k) R(s_k, a_k, s_{k+1}) \tag{1} \]

MDP Problem Objective:
$\rightarrow$ find optimal policy $\pi^*$ maximizing the expected discounted cumulative reward:

where $\gamma \in [0, 1[$ is the discount factor which weights rewards over time,
while $\pi : \mathcal{S} \to \mathcal{A}$ is the policy that maps states to actions: $\pi(s_k) = a_k$

Formal definition of the Path Planning Problem:

• optimal $\rightarrow$ given a chosen set of criterias
  such as shortest path, minimum energy consumption, minimum time, etc.
  Here, the optimality criteria is defined as the shortest path from state $s_0$ to the goal $s_g$
• collision-free $\rightarrow$ the path must not intersect with any obstacle in the environment

To affect agent learning to move towards the goal, we define the following reward function:

where:

• $d_{s_k}$: distance of the current state $s_k$ to the goal state
• $d_{s_{k+1}}$: distance of the next state $s_{k+1}$ to the goal state
• $d_o$: distance of next state $s_{k+1}$ to the closest obstacle
• $\alpha, \beta$: constant weighting parameters

The Action-Value Function $Q_{\pi}(s_k, a_k)$ describes the quality of transitions from state $s_k$ to the next, by immediately taking action $a_k$ and then following policy $\pi$.

The exact $Q_{\pi}$ values for all state-action pairs can be computed using the Bellman equation: \[ Q_{\pi}(s_k, a_k) = r_{k+1} + \gamma \sum_{s_{k+1} \in \mathcal{S}} P(s_{k+1} | s_k, a_k) \sum_{a_{k+1} \in \mathcal{A}} Q_{\pi}(s_{k+1}, a_{k+1}) \tag{2} \]

The optimal control policy $\pi^*$ can be obtained from the optimal action-value function $Q^*$: \[ \pi^*(s_k) = \arg\max_{a_k} Q^*(s_k, a_k) \]

$Q$-Learning is a model-free approach that be used to find the optimal action policy $\pi^*$

In the "learning phase", the agent explores the environment and learns the $Q$-values for all state-action pairs $(s_k, a_k)$ by iteratively updating the $Q$-table based on a greedy approach (off-policy):

\[ Q(s_k, a_k) \leftarrow Q(s_k, a_k) + \alpha \cdot \left[ r_{k+1} + \gamma \cdot \max_{a} Q(s_{k+1}, a) - Q(s_k, a_k) \right] \tag{6} \]

Assuming $n$ states and $m$ actions, the $Q$-table is a matrix of size $n \times m$

$Q$-learning is based on an episodic approach, where each episode ends when the agent reaches the goal state $s_g$ or an obstacle state $s_o$

In Reinforcement Learning techniques such as $Q$-Learning we need to balance:

• Exploration: trying new actions $a_k$ to possibly discover better Strategies
• Exploitation: using the current knowledge to maximize the expected reward

Two possible exploration strategies are:

In most cases, it takes a greedy approach and chooses the best action $a_k$ according to the current $Q$-values (exploitation), but with a small probability $\varepsilon$ it chooses a random action instead (exploration).

At the beginning of the learning, the probability of the random action is larger than the probability of the greedy action, but as the learning progresses, the probability $p$ of the greedy action increases.
The agent selects the best action $a_i$ with probability $p$ computed as:

\[ p(s, a_i) = \frac{e^{Q(s, a_i) / T}}{\sum_{a_k \in \mathcal{A}} e^{Q(s, a_k) / T}} \tag{4} \] with: \[ T_k = \lambda^k T_0 \tag{5} \] where $\lambda \in [0, 1[$ is a temperature discount rate.

A new exploration strategy is proposed, which combines the ε-Greedy strategy with probability $\varepsilon$ and Boltzmann strategy with complementary $1 - \varepsilon$ probability.

When ε-Greedy is not selected, we still allow exploration through the Boltzmann strategy, but converging to the greedy approach as the temperature decreases.
$\Rightarrow$ avoids local optimum and accelerates the expected $Q$-values convergence to optimality

$Q$-Learning easily suffers from the curse of dimensionality when the state space $\mathcal{S}$ and the action space $\mathcal{A}$ are large ($n \gg 1$ and $m \gg 1$)

To reduce the search space, we can use heuristic searching strategies that must be satisfied when selecting random actions in exploration strategies. Given current state $s_k=(x_k, y_k)$:

• If $(x_k < x_g) \land (y_k < y_g)$ $\Rightarrow$ $a_{k+1} = \text{rand}(1, 2, 3)$
  else if $(x_k > x_g) \land (y_k > y_g)$ $\Rightarrow$ $a_{k+1} = \text{rand}(5, 6, 7)$
• If $(x_k < x_g) \land (y_k > y_g)$ $\Rightarrow$ $a_{k+1} = \text{rand}(3, 4, 5)$
  else if $(x_k > x_g) \land (y_k < y_g)$ $\Rightarrow$ $a_{k+1} = \text{rand}(7, 8, 1)$
• If $(x_k = x_g) \lor (y_k = y_g)$ $\Rightarrow$ $a_{k+1} = \text{rand}(1,5) \lor \text{rand}(3,7)$
• Else $a_{k+1} = \text{rand}\{a_{k} - 1, a_{k}, a_{k} + 1\}$
  (limits the variation range within $0^{\circ} - 90^{\circ}$)

1. Obtain the optimal $Q$-table using the Improved $Q$-Learning (IQL)
   algorithm in a static environment with static obstacles
2. Apply the obtained $Q$-table to different dynamic environments
   with both moving and static obstacles

Fig. 3: Environment with static obstacles known a priori

Fig. 4: Environment with static obstacles not known a priori

Fig. 5: Environment with moving obstacles

Fig. 6: Environment with random initial point

Comparison of the execution times in diferent methods
"--" means that the method failed to plan the path