# How do I design the rewards and penalties for an agent whose goal it is to explore a map

I am trying to train an agent to explore an unknown two-dimensional map while avoiding circular obstacles (with varying radii). The agent has control over its steering angle and its speed. The steering angle and speed are normalized in a $$[-1, 1]$$ range, where the sign encodes direction (i.e. a speed of $$-1$$ means that it is going backwards at the maximum units/second).

I am familiar with similar problems where the agent must navigate to a waypoint, and in which case the reward is the successful arrival to the target position. But, in my case, I can't really reward the agent for that, since there is no direct 'goal'.

## What I have tried

The agent is penalised when it hits an obstacle; however, I am not sure how to motivate the agent to move. Initially, I was thinking of having the agent always move forward, meaning that it only has control over the steering angle. But, I want the ability for the agent to control its speed and be able to reverse (since I'm trying to model a car).

What I have tried is to reward the agent for moving and to penalise it for remaining stationary. At every timestep, the agent is rewarded $${1}/{t_\text{max}}$$ if the absolute value of the speed is above some epsilon, or penalised that same amount if otherwise. But, as expected, this doesn't work. Rather than motivating the agent to move, it simply causes it to jitter back and forth. This makes sense since 'technically' the most optimal strategy if you want to avoid obstacles is to remain stationary. If the agent can't do that then the next best thing is to make small adjustements in the position.

So my question: how can I add in an exploration incentive to my agent? I am using proximal policy optimization (PPO).

Measure what you want to achieve as directly as possible, and reward that. Later you can add more sophisticated incentives for the type of motion etc, but the key to a good reward signal is that it measures the quality of a solution at a high level, without specifying how to achieve that solution.

If you want your simulated car to explore, you will want to give it a reward signal based on it encountering new unexplored areas. There are lots of reasonable choices here. I suspect a good one will depend on what sensors you can reasonably code for the car, and what you consider to count as exploration - e.g. is it a thorough search of an area, moving far from the original position, experiencing different "views"?

One likely component you will need to give your agent and incorporate into the state representation is a memory. In order to understand whether the agent is exploring, something will need to know whether the agent has experienced something before and how much. A very simple kind of memory would be to add counters to a grid map and allow the agent to know how many time steps it has spent in each position on the map. The reward signal can then be higher when the agent enters a point on the map that it has not been in recently. If you want a non-episodic or repeating tour of exploration you might decay the values over time, so that an area that has not been visited for a long time counts the same as a non-visited one.

A related concept that you might be able to borrow ideas from is curiousity. There have been some interesting attempts to encourage an agent to seek new/interesting states by modifying action selection. Curiosity-driven Exploration by Self-supervised Prediction is one such attempt, and might be of interest to you. In that case, the authors use an intrinsic model of curiousity that can solve some environments even when there is no external reward signal at all!

Alternatively, if you don't care to get involved in technical solution, you could create a maybe acceptable behaviour for your vehicle by setting a random goal position, then granting a reward and moving it to a new random location each time the car reaches it.

• Okay, thank you. What I am trying right now (as in running the experiment) is a distance-based reward. So the reward at a time $t$ is $k(d_t-d_{t-1})$ where $k$ is some multiplier. I've noticed that the cumulative rewards decreases after a bit of training; the agent just starts moving quick and colliding into obstacles. Why do you think this may be occurring? Is it because the agent is prioritizing moving away from the position, and the obstacle penalty is too low? – Shon Verch Aug 28 '20 at 17:51
• @ShonVerch: It could be that, I don't really know enough about the environment and what you are doingto say for sure. You will need to look at the behaviours and the total rewards that they generate. Also check your state values - does the agent have any way to predict the location of an obstacle in advance of moving? – Neil Slater Aug 28 '20 at 18:03
• Right! The observation consists of distance sensors, which is how the car knows if there are obstacles near it. It's interesting because after the agent has learned to go away from the initial position, even despite the fact that almost every episode ends in a collision, the reward is still going up. This is what I'm talking about. Though, this is also without memory, and I'm not randomizing the obstacles every episode (I read somewhere that PPO is not great in random environments?). – Shon Verch Aug 28 '20 at 18:10
• Looks like a fun project. Unless those animations are playing backwards, or you are deliberately not showing some of the sensors, it looks like the car is reversing away from obstacles it can see, but cannot see the ones it eventually hits? – Neil Slater Aug 28 '20 at 18:56
• Yea, that's exactly what's going on. I had hoped that the agent could learn to look around to see obstacles behind it. Not sure why it's always reversing though. I think it might be overfitting reversing behaviour because the environment is never changing. – Shon Verch Aug 28 '20 at 18:59