Camera Ready Manuscriptcurrent page.east0.6cm0.590.01.5

# Path Planning using Reinforcement Learning:
A Policy Iteration Approach

Saumil Shivdikar  Electronics Dept.
Somaiya Vidyavihar University
Mumbai, India
<EMAIL_ADDRESS>Jagannath Nirmal  Electronics Dept.
Somaiya Vidyavihar University
Mumbai, India
<EMAIL_ADDRESS>
###### Abstract

With the impact of real-time processing being realized in the recent past, the
need for efficient implementations of reinforcement learning algorithms has
been on the rise. Albeit the numerous advantages of Bellman equations utilized
in RL algorithms, they are not without the large search space of design
parameters.

This research aims to shed light on the design space exploration associated
with reinforcement learning parameters, specifically that of _Policy
Iteration_. Given the large computational expenses of fine-tuning the
parameters of reinforcement learning algorithms, we propose an auto-tuner-
based ordinal regression approach to accelerate the process of exploring these
parameters and, in return, accelerate convergence towards an optimal policy.
Our approach provides $1.82\times$ peak speedup with an average of
$1.48\times$ speedup over the previous state of the art.

###### Index Terms:

Design Space Exploration, Policy Convergence, Markov Design Process, Maze
Solving

##  I Introduction

When problems of Markovian nature (that incorporate the Markov Design Process
(MDP)) have been introduced, _Policy Iteration_ and _Value Iteration_
algorithms have been at the forefront of preferred choice as a solution [1,
2]. These algorithms fall under the domain of _Dynamic Programming_ , which
are capable of searching for computationally optimal policies [3].

A major drawback of these approaches lies in the assumption that the
surrounding environment is a perfect model [4]. Despite the flawed assumption
of an ideal environment, Dynamic Programming remains integral to developing
solutions to simulated environments [5, 6].

Dynamic Programming algorithms are reward-inspired solutions. By creating a
system that is rewarded for inching closer toward the objective and penalized
for actions that do not benefit the user, it is possible to create a policy
that finds a close to the ideal solution to reach objective functions while
satisfying all criteria. One of the challenges in creating such a system lies
in setting the values of the parameters that describe the rewards, penalty,
and learning rates of our problem statement. With the area to explore being
exponentially large, a brute-force approach would be far from ideal for this
problem. Often such an approach yields non-optimal solutions that are prone to
converge upon local minimas [7].

Figure 1: Policy Iteration Flowchart: A visual representation of the policy
iteration algorithm

This work contributes toward improving Policy Iteration in the following ways:

  1. 1.

We provide an exhaustive analysis of previous attempts at optimizing search
space exploration

  2. 2.

We evaluate the permutations of different values of learning parameters of the
Policy Iteration algorithm

  3. 3.

We propose a novel approach based on ordinal regression auto-tuning to
accelerate the design-space exploration of reward parameters

  4. 4.

We evaluate our proposed solution across various problem statements and
provide an average acceleration of $1.48\times$ over heuristic approaches

The rest of this research is compartmentalized as follows; Section II provides
a high-level explanation to understand _Policy Iteration_ , this is followed
by Section III that formalizes our approach to reduce the search space of
design space exploration with the use of Auto-Tuner. Section IV describes the
nature of the experiments we used to evaluate our proposed solution. Section V
describes our findings which are later compared in Section VI. Finally, we
provide a brief overview of our results in Section VII.

##  II Policy Iteration

Policy iteration falls under the umbrella of _Dynamic Programming_ algorithms.
These algorithms aim to solve problems in a simulated model environment as a
Markov Design Process (MDP). Albeit Policy Iteration is a practical algorithm
in exploring close to an optimal solution, it is associated with hefty
computational expenses that scale quadratically with an increase in design
space. We start off this section with a description of the parameters before
diving into the implementation of policy iteration for path planning.

###  II-A Parameter description

Parameter | Description
---|---
$S_{t}$ | State value at time $t$
$R_{t}$ | Reward obtained at time $t$
$\pi$ | Current policy
$\pi_{*}$ | Optimal Policy
$v_{\pi}(s)$ | Value function following _current_ policy $t$
$v_{\pi_{*}}(s)$ | Value function following _optimal_ policy $t$
$\gamma$ | The discount rate
TABLE I: Description of parameters used in policy iteration path planning
Figure 2: An example of a multi-lane maze with speed bumps. The challenge lies
in choosing a closer lane with more speed bumps or a farther lane with fewer
speed bumps.

We describe our policy iteration approach to path planning using a toy
example. Figure 2 is an example maze with multiple lanes from start to finish.

  * •

State Values ($S_{t}$): To describe our problem statement, we represent the
maze with a matrix of state values (each value representing a position within
the maze).

  * •

Policy ($\pi$): A mapping of states to possible actions.

  * •

Value Function ($v_{\pi}(s)$): The expected return obtained after following
policy ($\pi$) when start location is $s$.

  * •

Reward ($R_{t}$): The reward received at time $t$.

  * •

Learning Rate ($\gamma$): The rate at which errors from the previous iteration
propagate into the next iteration

We incorporate the Bellman optimality equation from [8] toward our path
planning problem statement as seen in equations 1 and 2.

$v_{*}(s)=max_{a}\mathbb{E}[R_{t+1}+\gamma v_{*}(S_{t+1})\ |\
S_{t}=s,A_{t}=a]$ (1)

$V_{\pi}(s)=\sum_{s,r}P(s|S,\pi(s))[r+\gamma V_{\pi(s)}],s\in S$ (2)

for all $s\in S$, $a\in\mathcal{A}(s)$, and $s^{\prime}\in\mathcal{S}^{+}$

Figure 3: A maze with multiple types of obstacles. The challenge lies in
choosing an optimal path based on the reward policy that penalizes differently
for each obstacle.

Figure 3 is another example we incorporate to illustrate the behavior of our
design space explorer under various obstacle types. This type of maze is known
as a ”multi-objective maze” or a ”multi-modal maze” because it has multiple
objectives or modes of operation. The challenge in solving such a maze is to
find a path that balances the trade-offs between different types of obstacles
and the associated penalties while also maximizing the overall reward. This
type of problem is often solved using a combination of search algorithms and
optimization techniques [9, 10].

###  II-B Policy Evaluation

Algorithm 1 Policy Evaluation

0: $\pi$, the policy to be evaluated

0: $\Delta<\theta$

1: while $\Delta<\theta$ do

2: $\Delta\leftarrow 0$

3: for $s\in\mathbb{S}$ do

4: $v\leftarrow V(s)$

5:
$V(s)\leftarrow\sum_{a}\pi(a|s)\sum_{s^{{}^{\prime}},r}p(s^{{}^{\prime}},r|s,a)[r+\gamma
V(s^{{}^{\prime}})]$

6: $\Delta\leftarrow max(\Delta,|v-V(s)|)$

Our objective is to iteratively evaluate and improve the policy $\pi$ such
that it reaches as close as possible to the optimal policy $\pi_{*}$. _Policy
Evaluation_ aims to compute the efficiency of the current policy $\pi$. This
is achieved by computing the value function $V(s)$. While computing $V(s)$
specifically for our policy $\pi$ we refer to it as $V_{\pi}(s)$. We start off
by setting the value of $\theta$ (our threshold to halt computation) [11].
Following this, we iteratively compute the value function $V_{\pi}(s)$
following the algorithm 1. After reaching a $\Delta$ error value that lies
within our threshold $\theta$, we stop iterating.

_Policy Evaluation_ is a means of verifying the efficacy of our generated
policy. It is important to point out that if our surrounding environment is
statistically deterministic, we can converge to our solution directly by
solving a set of $|\mathcal{S}|$ linear equations.

###  II-C Policy Improvement

Algorithm 2 Policy Improvement

0: $\pi$, the policy to be improved

0: $\pi$ does not change with consecutive iterations

1: $policy\mbox{--}stable\leftarrow true$

2: for $s\in\mathbb{S}$ do

3: $old\mbox{--}action\leftarrow\pi(s)$

4:
$\pi(s)\leftarrow\mathrm{argmax}_{a}\sum_{s^{{}^{\prime}},r}p(s^{{}^{\prime}},r|s,a)[r+\gamma
V(s^{{}^{\prime}})]$

5: if $old\mbox{--}action\neq\pi(s)$ then

6: $policy\mbox{--}stable\leftarrow false$

7: if $policy\mbox{--}stable=true$ then

8: return $V\approx v_{*},\pi\approx\pi_{*}$

The reason for computing value function in _Policy Evaluation_ is to improve
our policy. In this stage of _Policy Improvement_ , we use our computed value
functions to set the parameters of our policy ($\pi_{t}$) to create a new
policy ($\pi_{t+1}$), inching a step closer to the optimal policy ($\pi_{*}$).

For every single state value, we compute the value function for each action.
Based on the action that provides the maximum value function, we greedily set
the policy to that particular action. This gets repeated for every state value
in the system. Although computationally expensive [12, 13], this approach
provides a greedy solution to finding the best action given the current state
values. And as with all greedy solutions, such an approach is susceptible to
converging toward a local maxima while ignoring the global one. Eager readers
are directed toward algorithm 2 to understand _Policy Improvement_.

###  II-D Policy Iteration

Algorithm 3 Policy Iteration

0: $\pi\approx\pi_{*}$, the optimal policy

0: $V(s)\in\mathbb{R},\pi(s)\in\mathcal{A}(s)$ for all $s\in\mathcal{S}$

1: $policy\mbox{--}stable\leftarrow false$

2: while $policy\mbox{--}stable\neq true$ do

3: Compute Policy Evaluation

4: Compute Policy Improvement

5: if $policy\mbox{--}stable$ then

6: return $V\approx v_{*},\pi\approx\pi_{*}$

Coalescing all steps together, we turn our attention towards _Policy
Iteration_. Policy iteration is a common method used for solving robotic maze
navigation tasks. The method involves iteratively updating the policy, or the
mapping from states to actions, to improve the agent’s performance. The flow
of this approach can be visualized in Figure 1. In the context of robot maze
solving, the policy iteration process typically begins with an initial,
randomly generated policy. The agent then follows this policy while navigating
the maze, and the cumulative reward is recorded. The policy is then updated
based on the agent’s performance, and the process is repeated. Through this
iterative process, the policy gradually improves, leading to better and better
performance in the maze.

This study has shown that such an approach can be highly effective in solving
robotic maze navigation tasks. For example, if a robot was trained to navigate
through a maze using policy iteration [14, 15], it could successfully find the
goal in a high percentage of trials and with a high degree of efficiency
compared to other algorithms. In addition to this, this approach has been used
to train robots to navigate through more complex mazes with multiple goals and
obstacles and has shown promising results [16].

##  III Auto-tuner

We employ an auto-tuner using ordinal regression for design space exploration
of reward function. Our approach of incorporating auto-tuning reinforcement
learning reward parameters using ordinal regression with partial ranking is a
method for adjusting the weights of the reward function in a reinforcement
learning algorithm [17]. The goal is to find the optimal parameters that
maximize the performance of the learning agent [18]. The method uses ordinal
regression, which is a type of supervised learning where the output is a set
of ordinal categories, rather than a continuous value. The partial ranking
aspect involves only comparing a subset of the actions, rather than the entire
set, to determine the optimal parameters [19, 2, 20]. This can help to reduce
computational costs and improve the efficiency of the learning process. The
method is typically used in complex or high-dimensional problems where
traditional methods may not be effective. This work is inspired by the
contributions of Cosenza et al. in their artwork [19].

Assuming that $P_{1}$, $P_{2}$ $\dots$ $P_{n}$ are all partial rankings
available in the training set [21], we can formally define the ordinal
ranking, incorporating partial equations, as follows:

$\min_{{\mathrm{\mathbf{w}}},\xi\geq
0}\frac{1}{2}\mathrm{\mathbf{w}}^{T}\mathrm{\mathbf{w}}+\frac{C}{m^{\prime}}\sum_{i}\sum_{(j,k)\in
P_{i}}\xi_{j,k}$ (3)

which is subject to

$\displaystyle\forall(j,k)\in
P_{1}:(\mathrm{\mathbf{w}}^{T}q^{1},\mathrm{\mathbf{t_{j}}})\geq(\mathrm{\mathbf{w}}^{T}q^{1},\mathrm{\mathbf{t_{k}}})+1-\xi_{j,k}$
(4) $\displaystyle\forall(j,k)\in
P_{2}:(\mathrm{\mathbf{w}}^{T}q^{2},\mathrm{\mathbf{t_{j}}})\geq(\mathrm{\mathbf{w}}^{T}q^{2},\mathrm{\mathbf{t_{k}}})+1-\xi_{j,k}$
$\displaystyle...$ $\displaystyle\forall(j,k)\in
P_{n}:(\mathrm{\mathbf{w}}^{T}q^{n},\mathrm{\mathbf{t_{j}}})\geq(\mathrm{\mathbf{w}}^{T}q^{n},\mathrm{\mathbf{t_{k}}})+1-\xi_{j,k}$

where $m^{\prime}=|\bigcup_{i}P_{i}|$ and $n=|Q|$

Figure 4: State value diagram of a simple maze containing one type of obstacle

Our rewards policy is represented as a cumulative sum of weighted rewards.
Auto-tuning rewards policies involve adjusting the parameters of a rewards
function based on the observed outcomes of an agent’s actions [22, 23]. This
can be represented as a cumulative sum of weighted rewards, where each
individual reward is assigned a weight that reflects its relative importance.
The weights are typically adjusted over time based on the agent’s performance,
with the goal of maximizing the overall cumulative sum of rewards. This
approach allows for flexible and adaptive rewards policies that can be
tailored to the specific goals and constraints of a given task or environment.
Additionally, this method can be used to optimize the trade-off between
exploration and exploitation [24, 25], balancing the need to explore new
actions with the desire to exploit known successful actions.

Auto-tuning rewards policies have been shown to be effective in a wide range
of applications, including robotics, gaming, and autonomous systems [26, 27].
In general, the performance of these methods is evaluated by comparing the
cumulative sum of rewards achieved by the agent using the auto-tuned policy to
that of a fixed or manually-tuned policy. Studies have found that auto-tuning
rewards policies can lead to significant improvements in performance,
particularly in tasks where the optimal rewards function is not known a priori
or is difficult to specify manually [28]. For example, in robotic tasks, auto-
tuning rewards policies have been used to improve the efficiency and
robustness of robotic grasping and manipulation [29, 30]. In gaming, auto-
tuning rewards policies have been used to create more engaging and challenging
opponents [31, 32, 33]. In autonomous systems, these policies have been used
to improve the efficiency and safety of self-driving cars [34].

##  IV Experimental Setup

We employ a few examples to help understand and evaluate our approach to
enhancing design space exploration for policy iteration. Our experiments lead
with a maze-solving example. We start with a simple multi-lane maze that
consists of speed bumps, as seen in Figure 2. This is followed by a complex
maze-solving problem as seen in Figure 3.

Our goal is to highlight the importance of choosing correct penalties and
discount factor $\gamma$ that encapsulates every scenario while still
converging on to a solution [2]. Choosing the correct penalties and discount
factor (gamma) is crucial when solving a multi-objective maze. The penalties
should be chosen to accurately reflect the relative importance of different
types of obstacles, while the discount factor should be chosen to balance the
trade-off between immediate and long-term rewards. When these values are
chosen correctly, the algorithm will be able to converge on a solution that
considers all relevant scenarios. However, if the penalties or discount factor
are not chosen correctly, the algorithm may converge on a suboptimal solution
or may not converge at all. Therefore, it is important to carefully consider
the problem at hand and choose appropriate penalties and discount factor to
ensure that the algorithm converges on an optimal solution.

One way to ensure that a close-to-optimal reward policy and discount factor is
considered is to incorporate an auto-tuner using ordinal regression for design
space exploration [35, 36], similar to polyhedral mapping exhibited in the
works [37, 38, 39]. Ordinal regression is a statistical method that can be
used to predict an ordinal variable (a variable that can be ranked) based on a
set of predictor variables. In this case, the ordinal variable could be the
performance of the algorithm and the predictor variables could be the reward
policy and discount factor. By using ordinal regression, we can explore the
design space of different reward policies and discount factors and identify
those that lead to the best performance. The auto-tuner can then use this
information to automatically adjust the reward policy and discount factor in
real-time to ensure that the algorithm is always operating in a region of the
design space that is likely to lead to good performance.

Figure 5: State value diagram of a complex maze constituting different types
of obstacles

Incorporating our policies, we generate a state-value diagram that represents
the value of each state in the maze [40, 41]. The state-value diagram is a
graphical representation of the algorithm’s policy. Each state in the maze is
represented by a box and the edges represent the possible actions that can be
taken from that state. The value of each state is represented by a color code,
where the darker the color, the higher the value. The state-value diagram is
generated by running the algorithm using our proposed policies and comparing
the results. It can be used to analyze the performance of the algorithm and
identify areas where the algorithm performed well or poorly. This
visualization allows for a detailed analysis of the algorithm’s behavior and
the impact of the policies on the algorithm’s performance. Figures 4 and 5
illustrate a heatmap of the state-value diagram for simple and complex mazes,
respectively.

Figure 6: High Penalty Simple Maze Path: A visual representation of the
algorithm’s path using a high penalty policy on a simple maze Figure 7: Low
Penalty Simple Maze Path: Visual representation of the algorithm’s path using
a low penalty policy

Our first proposed policy is designed not to penalize obstacles heavily. This
means that when the algorithm encounters an obstacle, it will not be heavily
punished for doing so. Instead, the obstacle is viewed as a minor
inconvenience that does not greatly impact the overall performance of the
algorithm [42, 6]. This approach is beneficial because it allows the algorithm
to explore more of the maze and potentially discover new paths that may lead
to a higher reward. However, it also means that the algorithm may take longer
to converge on a solution because it is not heavily discouraged from exploring
suboptimal paths [43, 44]. Additionally, this policy may not work well in
situations where certain obstacles are particularly dangerous or costly to
encounter. In those cases, a more aggressive penalty may be necessary to
ensure that the algorithm avoids those obstacles. This proposed policy can be
visualized in Figure 7 where the maze is shown with different obstacles, and
the algorithm’s path is traced for the low penalty reward policy.

On the contrary, our second proposed policy heavily penalizes obstacles. This
means that when the algorithm encounters an obstacle, it is heavily punished
for doing so. This approach is beneficial in situations where certain
obstacles are particularly dangerous or costly to encounter. The heavy penalty
discourages the algorithm from exploring suboptimal paths and encourages it to
find the optimal path more quickly. However, this policy may not work well in
situations where the maze is large and complex, and the algorithm may miss
potentially useful paths if it avoids obstacles at all costs. Additionally,
this policy may lead to suboptimal solutions if the penalties are not chosen
correctly. A visual representation of this policy would show a path with fewer
obstacles encountered (Figure 6).

Figure 8: Path plot for a multi-modal maze with different types of obstacles

We perform similar experiments on a complex maze with multiple types of
obstacles to see how our proposed policies perform in a more challenging
environment. The complex maze includes a variety of obstacles such as walls,
speed bumps, and oil spills. Each type of obstacle has a different penalty
associated with it. The algorithms are run using both of our proposed
policies, and the performance is measured in terms of the final reward
obtained, the time taken to reach the final reward, and the number of steps
taken to reach the final reward. By comparing the results of the two policies,
we can see how well each policy performs in a more complex environment and
identify the trade-offs between exploration and exploitation. This experiment
allows us to test the robustness of our proposed policies and to evaluate
their performance in a more realistic scenario.

Figure 8 visualizes the best path the algorithms converged on, when using both
proposed policies on the complex maze with multiple types of obstacles. The
figure shows a detailed view of the maze, including the different types of
obstacles and the corresponding penalties. The best path, represented by the
path with the highest reward and the least number of steps, is highlighted in
red.

##  V Results

We present the results of our evaluation of eight large mazes of the same size
for path planning using policy iteration. Our approach employed an auto-tuner
using ordinal regression for design space exploration, with the goal of
finding optimal parameters that maximize the performance of the learning
agent. We observed that the accumulated rewards varied significantly across
the different reward policies and mazes.

We plotted the accumulated rewards for each maze for twelve reward policies
($R0-R11$) generated by the auto-tuner. This has been visualized as a spider
plot in Fig 9. The results indicated that the reward policy that accumulated
the highest reward differed from maze to maze. This suggests that the optimal
reward policy is heavily dependent on the environment in which the learning
agent is operating. In addition, certain mazes consistently generated higher
accumulated rewards across all policies when the discount factor was low. This
indicates that far-sighted policies outweigh the gains of the near-sighted
policies for these mazes.

We also experimented with high and low discount factors to understand the
effects of near-sighted v/s far-sighted policy iteration. Our results
indicated that the choice of discount factor had a significant impact on the
learning agent’s performance. We observed that the performance of the learning
agent was better when the discount factor was low for certain mazes, while for
others, the performance was better when the discount factor was high.

In summary, our evaluation demonstrated the importance of carefully selecting
the reward policy and discount factor in policy iteration for path planning in
complex environments. The results indicate that the optimal parameters for the
learning agent depend on the specific characteristics of the environment in
which it operates. Future work will explore additional approaches for
optimizing the learning agent’s performance in complex environments, including
the use of more advanced machine learning algorithms and more complex mazes.

Our approach can be applied to a wide range of path-planning problems in real-
world applications, including autonomous vehicles, robotics, and logistics.
Our results provide valuable insights for designing efficient and effective
learning agents for path planning in complex environments.

In the context of policy iteration parameter fine-tuning using an auto-tuner,
Fig 9 can be used to guide the exploration of the reward function design
space. By identifying the policies that perform well under different discount
factors, the auto-tuner can focus on exploring reward functions that are
similar to those policies. This can help speed up the tuning process and
improve the overall performance of the policy.

Overall, the spider plot of accumulated rewards is a valuable tool for
evaluating the performance of different reward policies in the context of
policy iteration parameter fine-tuning using an auto-tuner. By identifying
which policies perform well under different conditions, the plot can guide the
exploration of the reward function design space and help to improve the
performance of the policy.

Figure 9: Comparing Accumulated Rewards and Discount Factors Across Multiple
Mazes using Spider Plots. Each spider plot displays the Top-12 reward policies
generated by the Auto-Tuner.

##  VI Related Work

The problem of path planning in complex environments has been extensively
studied in the field of robotics and artificial intelligence [45, 46, 47]. In
recent years, there has been a growing interest in using reinforcement
learning (RL) approaches for path planning, which allows agents to learn from
their own experiences and improve their performance over time. RL-based path
planning methods have been applied to a wide range of real-world applications,
including autonomous vehicles, mobile robots, and unmanned aerial vehicles.

A popular RL approach for path planning is policy iteration, which involves
iteratively evaluating and improving a policy for selecting actions in a given
state. In policy iteration, the choice of a reward function and discount
factor can significantly impact the performance of the learning agent. Several
studies have explored different reward functions and discount factors for path
planning in complex environments, with the goal of improving the performance
of the learning agent.

The use of auto-tuners for design space exploration has been gaining
popularity in recent years, particularly in the field of machine learning.
Auto-tuners use optimization algorithms to search the design space for optimal
hyperparameters that maximize the performance of the learning algorithm.
Several studies have explored the use of auto-tuners for optimizing the
performance of RL-based path-planning algorithms. These studies have
demonstrated that auto-tuners can significantly improve the performance of RL-
based path-planning algorithms, particularly in complex environments with a
large number of hyperparameters.

In contrast to our study, which focuses on the selection of optimal
hyperparameters for policy iteration in path planning, the work of Li et al.
in [48] addresses the problem of balancing exploration and exploitation in
large or continuous Markov decision processes. The work proposes a practical
solution to exploring large MDPs by integrating a powerful exploration
technique, Rmax, into a state-of-the-art learning algorithm, least-squares
policy iteration (LSPI). This approach combines the strengths of both methods
and has shown its effectiveness and superiority over LSPI with two other
popular exploration rules in several benchmark problems. While both studies
use policy iteration for path planning in complex environments, our study
specifically focuses on the selection of optimal hyperparameters for the
learning agent, while the work [48] addresses the problem of exploration in
large or continuous MDPs.

This work focuses on the selection of optimal hyperparameters for policy
iteration in path planning, Zamfirache et al., in their work [49], propose a
new reinforcement learning-based control approach that uses the policy
iteration and a metaheuristic Grey Wolf Optimizer (GWO) algorithm to train
neural networks for solving complex optimization problems. The paper presents
experimental results comparing the proposed approach to the classical policy
iteration reinforcement learning-based control approach using the Gradient
Descent (GD) algorithm and an approach that uses the Particle Swarm
Optimization (PSO) algorithm [50]. The experiments were conducted using a
nonlinear servo system laboratory equipment to evaluate how well each approach
solves the optimal reference tracking control for an experimental servo system
position control system. The study shows that the GWO algorithm represents a
better solution compared to GD and PSO algorithms for the control objective
considered in the paper. While both studies use policy iteration for
reinforcement learning, the focus of the research [49] is on using
metaheuristic optimization algorithms to improve the performance of the
learning agent, whereas our study focuses on optimizing the hyperparameters
for policy iteration in path planning.

Gao et al. in their work [51] use policy iteration for reinforcement learning;
the focus of the this paper is on addressing the challenges in developing
efficient and effective learning control algorithms for human-robot systems.
The study introduces the flexible policy iteration (FPI) algorithm, which can
flexibly and organically integrate experience replay and supplemental values
from prior experience into the reinforcement learning controller. The study
provides system-level performances, including convergence of the approximate
value function, optimality of the solution, and stability of the system. The
effectiveness of the FPI is demonstrated via realistic simulations of the
human-robot system. The paper addresses the challenges of obtaining a
customized mathematical model of a human-robot system either online or
offline, which makes design methods based on classical control theory nearly
impossible. Our approach converges faster to an optimal policy tailored to our
problem statement requiring computationally far fewer resources.

##  VII Conclusion

Our evaluation using policy iteration for path planning in complex
environments demonstrated the importance of carefully selecting the reward
policy and discount factor for optimizing the performance of the learning
agent. We employed an auto-tuner using ordinal regression for design space
exploration and evaluated eight large mazes of the same size, each with a
varying number of obstacles of different types. We plotted the accumulated
rewards for each maze for twelve reward policies generated by the auto-tuner
and also experimented with high and low discount factors to understand the
effects of near-sighted vs far-sighted policy iteration.

This research makes several contributions toward improving Policy Iteration.
First, it provides a comprehensive analysis of previous attempts to optimize
search space exploration. Second, it evaluates different permutations of
learning parameters for the Policy Iteration algorithm. Third, it proposes a
novel approach based on ordinal regression auto-tuning to speed up the design-
space exploration of reward parameters. Finally, the proposed solution is
evaluated on various problem statements, and the results show an average
acceleration of 1.48× over heuristic approaches. These contributions
collectively advance the field of Policy Iteration and can help accelerate the
optimization process for a wide range of applications.

Our results indicate that the optimal parameters for the learning agent depend
on the specific characteristics of the environment in which it operates. The
spider plots of accumulated rewards for the top 12 reward policies, comparing
both low and high discount factors for eight different mazes of the same size
provide valuable insights for designing efficient and effective learning
agents for path planning in complex environments. Future work will explore
additional approaches for optimizing the learning agent’s performance in
complex environments, including the use of more advanced machine learning
algorithms and more complex mazes. Our approach can be applied to a wide range
of path-planning problems in real-world applications, including autonomous
vehicles, robotics, and logistics.

## Acknowledgements

We would like to express our gratitude to all the individuals and
organizations who have contributed to the completion of this study. We would
like to thank the members of our research team for their hard work and
dedication to this project.

We would like to thank our funding agency for providing the financial support
necessary to carry out this research. Additionally, we would like to
acknowledge the developers of the software and tools used in this study, as
their contributions were essential to our work. Finally, We would like to
extend our gratitude to the reviewers who provided valuable feedback and
constructive criticism that helped us to improve the quality of this study.

## References

  * [1] R. S. Sutton, “Reinforcement learning: Past, present and future,” in _Asia-Pacific Conference on Simulated Evolution and Learning_. Springer, 1999, pp. 195–197.
  * [2] T. Baruah, K. Shivdikar, S. Dong, Y. Sun, S. A. Mojumder, K. Jung, J. L. Abellán, Y. Ukidave, A. Joshi, J. Kim, and D. Kaeli, “GNNMark: A Benchmark Suite to Characterize Graph Neural Network Training on GPUs,” in _2021 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)_ , Mar. 2021, pp. 13–23, zSCC: 0000002.
  * [3] R. S. Sutton and A. G. Barto, _Reinforcement learning: an introduction_ , second edition ed., ser. Adaptive computation and machine learning series. Cambridge, Massachusetts: The MIT Press, 2018, zSCC: 0048342.
  * [4] M. L. Littman, A. R. Cassandra, and L. P. Kaelbling, “Learning policies for partially observable environments: Scaling up,” in _Machine Learning Proceedings 1995_. Elsevier, 1995, pp. 362–370.
  * [5] A. Vakil, F. Niknia, A. Mirzaeian, A. Sasan, and N. Karimi, “Learning assisted side channel delay test for detection of recycled ics,” in _Proceedings of the 26th Asia and South Pacific Design Automation Conference_ , 2021, pp. 455–462.
  * [6] M. Srinivasan, A. Kak, K. Shivdikar, and C. Warty, “Dynamic power allocation using Stackelberg game in a wireless sensor network,” in _2016 IEEE Aerospace Conference_ , Mar. 2016, pp. 1–10, zSCC: 0000002.
  * [7] K. Shivdikar, A. Kak, and K. Marwah, “Automatic image annotation using a hybrid engine,” in _2015 Annual IEEE India Conference (INDICON)_ , Dec. 2015, pp. 1–6, zSCC: 0000006 ISSN: 2325-9418.
  * [8] E. Gross, “On the bellman’s principle of optimality,” _Physica A: Statistical Mechanics and its Applications_ , vol. 462, pp. 217–221, 2016.
  * [9] M. Jayaweera, K. Shivdikar, Y. Wang, and D. Kaeli, “JAXED: Reverse Engineering DNN Architectures Leveraging JIT GEMM Libraries,” in _2021 International Symposium on Secure and Private Execution Environment Design (SEED)_ , Sep. 2021, pp. 189–202.
  * [10] K. Shivdikar, K. Paneri, and D. Kaeli, “Speeding up dnns using hpl based fine-grained tiling for distributed multi-gpu training.”
  * [11] C. Bunn, H. Barclay, A. Lazarev, F. Yusuf, J. Fitch, J. Booth, K. Shivdikar, and D. Kaeli, “Student cluster competition 2018, team northeastern university: Reproducing performance of a multi-physics simulations of the Tsunamigenic 2004 Sumatra Megathrust earthquake on the AMD EPYC 7551 architecture,” _Parallel Computing_ , vol. 90, p. 102568, Dec. 2019, zSCC: NoCitationData[s0]. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0167819119301590
  * [12] K. Shivdikar, G. Jonatan, E. Mora, N. Livesay, R. Agrawal, A. Joshi, J. L. Abellán, J. Kim, and D. Kaeli, “Accelerating Polynomial Multiplication for Homomorphic Encryption on GPUs,” in _2022 IEEE International Symposium on Secure and Private Execution Environment Design (SEED)_ , Sep. 2022, pp. 61–72.
  * [13] N. Livesay, G. Jonatan, E. Mora, K. Shivdikar, R. Agarwal, A. Joshi, J. L. Abellan, J. Kim, and D. Kaeli, “Accelerating finite field arithmetic for homomorphic encryption on gpus,” _IEEE Micro_ , 2023.
  * [14] H. Dang, J. Song, and Q. Guo, “An efficient algorithm for robot maze-solving,” in _2010 Second International Conference on Intelligent Human-Machine Systems and Cybernetics_ , vol. 2. IEEE, 2010, pp. 79–82.
  * [15] K. Intrator and K. Shivdikar, “Missing ’Middle Scenarios’: Uncovering Nuanced Conditions in Latin America’s Housing Crisis,” _Cityscape_ , vol. 19, no. 2, pp. 31–44, 2017, publisher: US Department of Housing and Urban Development. [Online]. Available: https://www.jstor.org/stable/26328323
  * [16] K. Zhu and T. Zhang, “Deep reinforcement learning based mobile robot navigation: A review,” _Tsinghua Science and Technology_ , vol. 26, no. 5, pp. 674–691, 2021.
  * [17] C. Olschanowsky, M. M. Strout, S. Guzik, J. Loffeld, and J. Hittinger, “A study on balancing parallelism, data locality, and recomputation in existing pde solvers,” in _SC’14: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_. IEEE, 2014, pp. 793–804.
  * [18] S. Kronawitter and C. Lengauer, “Optimization of two jacobi smoother kernels by domain-specific program transformation,” in _Proceedings of the 1st International Workshop on High-Performance Stencil Computations (HiStencils)_ , 2014, pp. 75–80.
  * [19] B. Cosenza, J. J. Durillo, S. Ermon, and B. Juurlink, “Autotuning stencil computations with structural ordinal regression learning,” in _2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_. IEEE, 2017, pp. 287–296.
  * [20] J. Ansel, S. Kamil, K. Veeramachaneni, J. Ragan-Kelley, J. Bosboom, U.-M. O’Reilly, and S. Amarasinghe, “Opentuner: An extensible framework for program autotuning,” in _Proceedings of the 23rd international conference on Parallel architectures and compilation_ , 2014, pp. 303–316.
  * [21] B. Hajek, S. Oh, and J. Xu, “Minimax-optimal inference from partial rankings,” _Advances in Neural Information Processing Systems_ , vol. 27, 2014.
  * [22] H. Fan, Z. Xia, C. Liu, Y. Chen, and Q. Kong, “An auto-tuning framework for autonomous vehicles,” _arXiv preprint arXiv:1808.04913_ , 2018.
  * [23] F. Niknia, Z. Wang, S. Liu, and F. Lombardi, “Nanoscale design of multi-layer perceptrons using floating-point arithmetic units,” in _2022 IEEE 22nd International Conference on Nanotechnology (NANO)_. IEEE, 2022, pp. 16–19.
  * [24] I. J. Sledge and J. C. Príncipe, “Balancing exploration and exploitation in reinforcement learning using a value of information criterion,” in _2017 IEEE international conference on acoustics, speech and signal processing (ICASSP)_. IEEE, 2017, pp. 2816–2820.
  * [25] S. Liu, X. Tang, F. Niknia, P. Reviriego, W. Liu, A. Louri, and F. Lombardi, “Stochastic dividers for low latency neural networks,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 68, no. 10, pp. 4102–4115, 2021.
  * [26] I. Colbert, J. Daly, and N. Rubin, “Generating gpu compiler heuristics using reinforcement learning,” _arXiv preprint arXiv:2111.12055_ , 2021.
  * [27] U. Farooq, N. U. Hasan, I. Baig, and M. Zghaibeh, “Efficient fpga routing using reinforcement learning,” in _2021 12th International Conference on Information and Communication Systems (ICICS)_. IEEE, 2021, pp. 106–111.
  * [28] R. R. Karn, P. Kudva, and I. A. M. Elfadel, “Dynamic autoselection and autotuning of machine learning models for cloud network analytics,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 30, no. 5, pp. 1052–1064, 2018.
  * [29] A. H. Ashouri, M. Elhoushi, Y. Hua, X. Wang, M. A. Manzoor, B. Chan, and Y. Gao, “Mlgoperf: An ml guided inliner to optimize performance,” _arXiv preprint arXiv:2207.08389_ , 2022.
  * [30] ——, “Work-in-progress: Mlgoperf: An ml guided inliner to optimize performance,” in _2022 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES)_. IEEE, 2022, pp. 3–4.
  * [31] L. Dong, Y. Li, X. Zhou, Y. Wen, and K. Guan, “Intelligent trainer for dyna-style model-based deep reinforcement learning,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 32, no. 6, pp. 2758–2771, 2020\.
  * [32] A. H. Ganesh and B. Xu, “A review of reinforcement learning based energy management systems for electrified powertrains: Progress, challenge, and potential solution,” _Renewable and Sustainable Energy Reviews_ , vol. 154, p. 111833, 2022.
  * [33] C. Prigent, L. Cudennec, A. Costan, and G. Antoniu, “A methodology to build decision analysis tools applied to distributed reinforcement learning,” in _2022 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)_. IEEE, 2022, pp. 1053–1062.
  * [34] B. Svetozarevic, C. Baumann, S. Muntwiler, L. Di Natale, M. N. Zeilinger, and P. Heer, “Data-driven control of room temperature and bidirectional ev charging using deep reinforcement learning: Simulations and experiments,” _Applied Energy_ , vol. 307, p. 118127, 2022.
  * [35] L. Nardi, D. Koeplinger, and K. Olukotun, “Practical design space exploration,” in _2019 IEEE 27th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS)_. IEEE, 2019, pp. 347–358.
  * [36] K. Shivdikar, “SMASH: Sparse Matrix Atomic Scratchpad Hashing,” May 2021. [Online]. Available: https://arxiv.org/abs/2105.14156v1
  * [37] P. Pfaffe, T. Grosser, and M. Tillmann, “Efficient hierarchical online-autotuning: a case study on polyhedral accelerator mapping,” in _Proceedings of the ACM International Conference on Supercomputing_ , 2019, pp. 354–366.
  * [38] S. Alvarez, P. Alemany, D. Casanova, J. Cirera, M. Llunell, and D. Avnir, “Shape maps and polyhedral interconversion paths in transition metal chemistry,” _Coordination chemistry reviews_ , vol. 249, no. 17-18, pp. 1693–1708, 2005.
  * [39] U. Brehm and E. Schulte, “Polyhedral maps,” in _Handbook of discrete and computational geometry_. Chapman and Hall/CRC, 2017, pp. 533–548.
  * [40] S. Niu, S. Chen, H. Guo, C. Targonski, M. Smith, and J. Kovačević, “Generalized value iteration networks: Life beyond lattices,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 32, no. 1, 2018.
  * [41] F. Niknia, J.-L. Danger, S. Guilley, and N. Karimi, “Aging effects on template attacks launched on dual-rail protected chips,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 41, no. 5, pp. 1276–1289, 2021.
  * [42] L. Lee, E. Parisotto, D. S. Chaplot, E. Xing, and R. Salakhutdinov, “Gated path planning networks,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 2947–2955.
  * [43] M. Wang, D. Zheng, Z. Ye, Q. Gan, M. Li, X. Song, J. Zhou, C. Ma, L. Yu, Y. Gai, T. Xiao, T. He, G. Karypis, J. Li, and Z. Zhang, “Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks,” _arXiv:1909.01315 [cs, stat]_ , Aug. 2020, zSCC: NoCitationData[s0] arXiv: 1909.01315. [Online]. Available: http://arxiv.org/abs/1909.01315
  * [44] M. Wang, “Deep Q-Learning Tutorial: minDQN,” Oct. 2021. [Online]. Available: https://towardsdatascience.com/deep-q-learning-tutorial-mindqn-2a4c855abffc
  * [45] N. Sariff and N. Buniyamin, “An overview of autonomous mobile robot path planning algorithms,” in _2006 4th student conference on research and development_. IEEE, 2006, pp. 183–188.
  * [46] Q. Yao, Z. Zheng, L. Qi, H. Yuan, X. Guo, M. Zhao, Z. Liu, and T. Yang, “Path planning method with improved artificial potential field—a reinforcement learning perspective,” _IEEE access_ , vol. 8, pp. 135 513–135 523, 2020\.
  * [47] K. Wu, M. A. Esfahani, S. Yuan, and H. Wang, “Tdpp-net: Achieving three-dimensional path planning via a deep neural network architecture,” _Neurocomputing_ , vol. 357, pp. 151–162, 2019.
  * [48] L. Li, M. L. Littman, and C. R. Mansley, “Online exploration in least-squares policy iteration.” in _AAMAS (2)_. Citeseer, 2009, pp. 733–739.
  * [49] I. A. Zamfirache, R.-E. Precup, R.-C. Roman, and E. M. Petriu, “Policy iteration reinforcement learning-based control using a grey wolf optimizer algorithm,” _Information Sciences_ , vol. 585, pp. 162–175, 2022.
  * [50] S. Thakkar, K. Shivdikar, and C. Warty, “Video steganography using encrypted payload for satellite communication,” in _2017 IEEE Aerospace Conference_ , Mar. 2017, pp. 1–11.
  * [51] X. Gao, J. Si, Y. Wen, M. Li, and H. Huang, “Reinforcement learning control of robotic knee with human-in-the-loop by flexible policy iteration,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 33, no. 10, pp. 5873–5887, 2021.