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

Question

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).

Answer 1

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.