# Reinforcement Learning: Application of Value Iteration in Robotics Navigation Task > Source: > Published: 2026-07-15 03:01:47+00:00 Hello everyone 😀 Welcome to this blog post ! Today we are going to see a real world application of Dynamic Programming in a Robotics Task. In a previous [post](https://medium.com/@fousseyni.phd/rl-in-discrete-world-dynamic-programming-part2-generalized-policy-iteration-gpi-9a2624a7a349), I showed how to find the optimal policy of a Markov Decision Process (MDP) using an algorithm called ** Value Iteration. **I recommend to read that post before this one because this post is merely Application. That said, if you’re already familiar with value iteration, you’re good to continue reading this post ! Our targeted task in Robotics is mobile robot navigation. In navigation, a mobile robot must find its way from a starting point S to a final point F. The policy, often called the controller in Robotics and Automation, is the decision maker that must find the sequence of actions that can achieves this goal in the most efficient way. We will call this particular task of going to a point a “** Point Goal navigation**”. Of course there are other common tasks such as path following, trajectory following, speed tracking, parking, etc. Like we did for the TVShow game, in this [post](https://medium.com/@fousseyni.phd/rl-in-discrete-world-part-1-multi-armed-bandits-25466c1980f0), and in the toy [example](https://medium.com/@fousseyni.phd/rl-in-discrete-world-dynamic-programming-part1-deriving-the-value-function-from-scratch-bbdb7e411d28) , we must design an environment where the agent will have to interact with in order to find the optimal policy. This is the place to define the rules of the game. For instance, defining the action space, the state space, the reward function and the dynamic model, etc. Designing a realistic environment is one of the most critical step in the application of Reinforcement Learning. An RL policy, learning by trial-and-error, expects two things from the environment: when I take an action **1.** how good is it, that is, what ** reward** do I get? and It’s important to find the right reward model that will guide the RL policy to solving your task. The reward must be designed in such a way that maximizing the cumulative reward will achieve your goal. Care must be taken not to over-design the reward either, because that might lead to reward hacking or sub-optimal behavior. This quote from “Sutton & Barto” [1] says it better: […] In particular, the reward signal is not the place to impart to the agent prior knowledge about how to achieve what we want it to do. For example, a chess-playing agent should be rewarded only for actually winning, not for achieving subgoals such as taking its opponent’s pieces or gaining control of the center of the board. If achieving these sorts of subgoals were rewarded, then the agent might find a way to achieve them without achieving the real goal. For example, it might find a way to take the opponent’s pieces even at the cost of losing the game. The reward signal is your way of communicating to the robot what you want it to achieve, not how you want it achieved. […] Regarding the dynamics model, it needs to be realistic otherwise when the policy is deployed on a real robot, there will be a gap between the simulation environment where the policy was trained and the real world environment where it is deployed: that gap is called ** simulation to reality gap**, or famously known as In summary, what we have to do right away is: designing a world model for the RL agent to solve the Point Goal navigation task. Notes: You might have noticed that I use interchangeably policy, agent, robot in this post. The agent is the entity making decisions, which in our case can be replaced by the robot. The policy, I will say is like the brain controlling the body. I sometimes use these 3 words but I think of the same thing, the decision maker ! ** The Robot Kinematic Model**: The kinematic model defines the equation of motion of the robot. Indeed, it expresses the coordinates of the robot as a function of the speed and/or the acceleration. We will assume that our robot will run in a world that is a 2D plane. Therefore, the robot is represented by a 2D point whose pose is represented by the tuple ** (x, y, θ)** which are its x-axis on the horizontal axis; y-axis on the vertical axis; and orientation or heading which represents its angle with the horizontal x-axis. The different motions that the robot can do are At each time step, the position of the robot will be updated according to the simple Euler integration model where v = 1 ** m/s **for However, it is possible that we give it as a prior through the state transition model or it can just learn this on the fly on its own. So now that we know how our robot moves, we can define the MDP components namely the state space, the action space, the reward model and the state transition model. Obviously, the action space is ** {“move”, “stop”, “turn_left”, “turn_right”}.** What is the state space of the environment ? Well, that depends, I mean there are different possibilities. The state is whatever information is useful to the decision making process of the agent. In robotic navigation tasks, usually the state space may consist of In our case, a simple pose ** (x, y, θ)** of the agent is enough. We could as well add the position There isn’t a unique recipe for choosing the right state space, it’s an art and it depends on each problem. It’s up to you to find the right representation of the state. The simpler it is (i.e. low dimension), the more computation you’ll save, but remember, make sure you give the agent what it needs to make correctly informed decision making. In fact, there is whole sub-field of Machine Learning on learning the right representation for a task and one of the most influential ML conference is specifically dedicated to this matter called **International Conference on Learning Representation (ICLR)**. Notes: Very often, the data returned by a camera or a lidar contain information that are not necessarily useful to solve a given task (e.g. the image background when the model is learning how to stop or return a tennis ball is not useful for that task). Using the full image is computationally expensive and distracts the model during learning. Techniques like Joint Embedding Predictive Architecture (JEPA, popularized by Yann LeCun) or SimCLR, etc aim to learn what is useful to retain from this input data and the decision is made solely based on the small useful part. It remains two components, the reward model and the state transition model. The reward is basically our way to tell the RL agent what task we want it to solve. Here, in our navigation task, the goal is simply to reach the goal position (xg, yg). To simplify, the reward will be defined as ** r(s, a, s’) = -((x, y) != (xg, yg)) **😎 The fact of penalizing each step until the goal is reached urges the model to find the quickest path so that it can minimize the cumulative cost, therefore maximizing the cumulative reward. There are many ways to describe this task, I could give 1 when the goal is reached and 0 otherwise. Or even a dense reward, where the reward will be a function of the distance to the goal. We will see these techniques in future posts :) We now have a well described environment with state space, action space, the true reward and dynamic models of the environment. Notes: the reward and dynamic models that we have defined above are not necessarily known by the learning agent because it can learn them. However, since we are the programmer and we know everything, we can give this knowledge as prior to the RL agent. For example, the probability of transitioning from a state s to a state s’ can be well determined using the kinematic model of the robot. Same goes for the reward. For a quick reminder, I put below the algorithm of Value Iteration from the previous post. What is the transition probability function p(s’, r|s, a), that is, the probability of transitioning from state s’ to s, and receive reward r, by taking action a? Well, here it is quite simple because everything is deterministic. To have an intuition, let’s take a simple example. Suppose the current state is s = (1, 1, 180), basically the robot position (x, y) = (1, 1)and it’s oriented at angle of 180° with respect to the horizontal x-axis. So if the x-axis points toward the right, the robot is facing left. Let the goal position be (0, 0). If the robot takes the action “** turn_right**” and receives reward -1, what’s the probability Notes: p(s’=(1, 1, 135), -1|turn_right, s=(1, 1, 180)) means the probability transitioning from state = (1, 1, 180) to next state = (1, 1, 135) and receive the reward -1 when you have taken action “turn_right”. Basically, you are rotating by decreasing your angle by 45° which becomes 135°. No forward movement ! Only state possible ! For instance ** p(s’=(1, 1, 0), 0|move, s=(1, 2, 0)) = 0** because even though the state (1, 2, 0) is the next state of the robot, only when the goal is reached the reward is 0. If it were reward = -1, the transition would be correct. Or another one The pseudo code below shows one way to program the transition probability function. We will basically checks whether the next state is coherent with the kinematic model given the current action. One way to do that is to compute the ** new distance** to the goal if the current action is Hope these formulas are not too scary, if you use the equations of the kinematic above, you can arrive to the same. But, it’s not the most important here, that’s more robotics than RL and you might never have to do this unless you are in robotics, if that’s the case, you might already know how to derive this. Then we can compute the probability of the transition. It’s binary, 100% or 0. Below is an example pseudo code that implements this idea: ``` python def transition_prob(state, action, reward, next_state): true_transition = transition_matrix(state, action) candidate_transition = (state, reward, next_state) if true_transition == candidate_transition: return 1.0 # only possible transition else: return 0.0 # all other are impossible def create_transition_matrix(): transition = {} # {state: {action1: next_state_1, action2: next_state2, ...}, ...} for state env.state_space: transition[state] = {} for action in env.action_space: next_state = get_next_state(state, action) reward = env.reward_model(state, action, next_state) transition[state][action] = (next_state, reward) return transition ``` We are almost there to implement Value Iteration in Algorithm 1. One last thing that we must do is to discretize the state space. Right now, our state space is continuous, which poses a problem when we must loop over the whole state space in the Value Iteration algorithm. For the heading, it’s pretty simple we will discretize it into ** N discrete angles** between -180° and 180°. Therefore, every continuous angle will be mapped to an interval. Regarding X and Y axes, they will both be discretized into bins with a step of 0.5m between each bin. Every x and y coordinate will be mapped to the closest value in the discrete space. For instance a point of coordinates (-1.3, 2.6) will be mapped to (-1.5, 2.5) while (-1.2, 2.8) would be mapped to (1.0, 3.0). Hope that’s clear. The pseudo code below shows the algorithm to discretize ``` python def get_idx(v, min_v=0.0, step=0.5): # if you have an arithmetique sequence of step 0.5 and a first term v_0 # then the n^th sequence is given by Vn = V_0 + n*step, then the index n # is given by n = (Vn - V_0)/step; here V_0=min_v return round((v-min_v)/step) ``` Implement the Value Iteration algorithm to solve this task given that: The code to reproduce this solution can be found on my github page at [https://github.com/Fousseyni-Sang/rl-blog/tree/main/ch2/application](https://github.com/Fousseyni-Sang/rl-blog/tree/main/ch2/application) The figure above is very beautiful ! In ** Figure 1**., the yellow colors have higher value than the dark colors. Without surprise, the closer is a state to the goal position We can see that the value function reflects faithfully the geometry of the environment. For instance, take the first plot with ** ϴ=−180°** (the agent facing left side), the strongest yellow line By simply following the states with highest value, an RL agent is able to find the best path. I derived the optimal policy exactly with this strategy and plot some trajectories for visualization in ** Figure .2** below: Most of these trajectories are not a surprise once you understand the value function in ** Figure 1. **Some trajectories that I find interesting to look at are the ones at position (x = -4.0, y = -10.0) and (x = 3., y = 10.0) because they require the agent to deviate from a straight line and find the right orientation to the goal. And the manner this deviation is done changes beautifully with the starting orientation of the robot. I let you internalize these intuitions, but they usually are the optimal way in all cases. In my implementation, I made a lot of design choices that can affect the results that you observed. One of them is the discretization step. I don’t think that choosing a position discretization would change the strategy, but I believe that the orientation discretization may result in different deviation choices for positions like ** (x=-4, y=10), (x = 3, y = 10)**. The code I shared can help you try different discretization. One other design choice that can be changed of course is the reward function. Instead of ** -float((x, y)!=(xg, yg))**, one could take the negative distance between the robot and the goal (a Manhattan distance or euclidean distance both work). Or even add some penalty on the energy but that would be a bit nonsense here because our agent can only choosing one speed anyway! Another one that is not so obvious, is the way we loop over states in Value Iteration. In problems with few state space, this is fine, but if you have a huge state space, considering a clever strategy to choose states to update can accelerate the convergence. For instance, a random uniform selection strategy of the states can be made; or something that I just quickly tried myself and looks interesting is treating the state space itself as an action space for a multi-armed bandits agent that select to update the state with highest value. An epsilon-greedy policy will definitely be needed here, in order to avoid updating the same set of states over and over which will unavoidably converge to a sub-optimal value function. Figure 3. above showed some quick results with the different selection strategies above. For the “random” and “weighted” selection strategy, only half the states are updated. Of course, the same states can be selected in subsequent iterations (that’s the intended goal somehow). Interestingly, all of them finishes to converge ! Maybe after each state has been selected, not sure, but I don’t think that’s really required. At least, not the same amount of visits for each states is required to have convergence. The “normal” method converges faster of course because it sweeps every state. However, depending on the task, we may not really need to wait for absolute convergence (delta_v norm = 0) to obtain the optimal policy. Like, I could just stop the “weighted” version right at iteration 30 and the policy would stay the same ! No need to run the full 200 iterations to reduce the error to zero ! And it would save computation time thus energy: For the Sake of Planet, cut the value iteration 🙃 Anyway, the message here is that, in order to obtain a good policy or optimal policy, exhaustive sweeping over all states is not always necessary. This branch is called ** Asynchronous Dynamic Programming** in the literature. And some other techniques exist such as Something that you may ask yourself, a bit mysterious so far, is how can this be used on a REAL ROBOT ! I mean, this value only works in discrete space, but REAL ROBOTs live in a a continuous world and cannot teleport from one state to another ! Well, one solution is to use finer discretization, instead of 1m of spacing between position, you may want to use 0.1m for instance. And also maybe 5° for angle spacing. You see the issue with this sort of technique, your state space just explodes ! This is famously known as the ** Curse of Dimensionality** ! Another cool solution is to use to use your value function as a planner and use a lower level control method, for instance a Proportional Integral Derivative (PID), that is able to reach a given position by merely following a straight line. You then have a higher level planner that acts as a strategy ** Thinker** and a lower level Voilà, this is the end of this practical post and with it the end of the dynamic programming chapter ! Dynamic programming methods such as policy iteration and value iteration are fundamental and give the optimal solution to problems formulated as Markov Decision Process. Most of the other reinforcement learning methods only exist to tackle some of the practical bottlenecks that arise when you apply value iteration to some real world problems. For instance, there are more possible states in the game of Chess than the number of atom in the observable universe, 10⁸⁰ 😱 Good Luck to store a value array for that 😄 Let’s not talk the game of GO ! Looping through all next states … abyssal ! Compute their probabilities … nightmare ! Or imagine you are fine-tuning a Large Language Model (LLM) and your state space is the context (prompt included) given by the user and your action space is full token space, I shouldn’t even think of such thing, storing a value array of that sort is illegal, it’s literally of infinite size because there are infinite possible prompts ! So… even with guaranteed optimality, the possibilities offered by Dynamic Programing are limited in real life ! In the next chapter, we will take a step toward ** Model Free Reinforcement Learning** techniques. We will still stay in discrete space, still, but we will remove one component in Dynamic Programming: [1] [Sutton and Barto, Reinforcement Learning: an introduction](https://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf) [2] [https://github.com/Fousseyni-Sang/rl-blog/tree/main/ch2/application](https://github.com/Fousseyni-Sang/rl-blog/tree/main/ch2/application) [Reinforcement Learning: Application of Value Iteration in Robotics Navigation Task](https://pub.towardsai.net/application-of-value-iteration-in-robotics-navigation-task-free-friend-link-7f3cf48d3d58) was originally published in [Towards AI](https://pub.towardsai.net) on Medium, where people are continuing the conversation by highlighting and responding to this story.