Reward function for grid based path planning deep Q-learning agent

Question

I'm really getting stuck on creating a good reward function for my agent and could use some advice. I'll explain the setting for my question first:

Agent Description

The agent in question exists in a square grid world (of size (M x N)) that needs to be searched. Each grid location has a 'searched' or 'unsearched' status, and when the agent visits a grid location, the status of that location is set to 'searched'.

Agent State Space

The state of the agent is modelled by a (M x N x 2) tensor where the first channel is the binary matrix of grid statuses (1 for unsearched and 0 for searched) and the second channel is the agent's location matrix (1 for the location of the agent and 0 elsewhere).

Agent Action Space

The agent can move to any location on the grid in one time step, giving an action space shape of (M x N). Therefore the actions available to the agent are the same in any state and the number of actions is equal to the number of locations in the grid.

I am using Deepmind's fully convolutional StarCraft network to map the input state to the output action utilities.

Objective

The agent is placed in the center of the grid with all locations initialized as 'unsearched' and the agent must move throughout the grid and search all the locations while limiting the total amount of actions taken and total distance traveled. So for example, in a 9x9 grid the agent will want to only make 81 actions and its travel distance should also be 81 (as it should not make any diagonal movements).

Attempted Rewards

Subgoal Only: give the reward to an agent based only on attributes of the current state and action. So:

reward = new_location_status - (distance_traveled / max_travel_distance)

This did make the agent complete the search in optimal number of actions but even with a large amount of training it could not get an optimal total travel distance.

Shaped Reward: Using the previous reward as a 'subgoal scalar' I multiplied this by a function that exponentially increases as the agent gets closer to the goal state. Closeness to the goal state is measured by the sum of unsearched locations. Additionally there is an extra reward for reaching the goal state.

if goal state:
    reward = 100
else:
    goal_dist = 1 - (sum_of_unsearched / max_num_of_unsearched)^0.5
    reward = goal_dist * subgoal_scalar

I thought this would improve my agent's incentive to converge to a goal state, but here the agent rarely reaches a goal state and many times chooses not to move for many actions.

So any input on improving the reward function would be great.

Testing Update

So as Matthew Graves mentioned below, it might be better to try using a more sensible $\alpha$ for the distance modifier of the subgoal only reward scheme.

Previously I had been using $\frac{1}{max\_travel\_dist}$ where $max\_travel\_dist$ was the maximum distance an agent could travel in one action given the grid size (i.e. the distance from one corner of the grid to the other). This caused the movement distance penalty to be very small in most cases.

After changing it to $\frac{1}{\sqrt{2}}$ I found that the agent was able to make much better decisions about its path trajectory for longer periods of time. This did not completely solve my issue, but it was definitely an improvement.

I also came to the realization that in my case, the movement of the agent should not be penalized differently just because it has a larger space. In my problem, the agent's optimal movement is always going to be one grid-cell at a time no matter the size of the grid. With the previous $\alpha$ I was constraining the distance modifier to be from 0 to -1, but by doing this I had created a construct that meant that a bad movement with travel distance of say 5 on a small grid would be extremely bad but on a larger grid would not be as significant and therefore the agent would not care as much to make such a movement.

Answer 1

Learning to complete the task in only 81 actions is easy, because the underlying policy is also very easy: only choose an action (teleport to location X) if the corresponding location is unsearched (which it can observe directly). The reward contribution of new_location_status provides that.

Learning to never hesitate requires some sort of baseline penalty. Note that if it chooses to stay where it is, under the first reward function it pays no travel cost and gets no reward, for a result of 0; under the second reward function, the goal_dist hasn't changed, and so it gains a positive reward for hesitating, which is larger the closer it is to the goal!

Learning to complete the task in only 81 traveled distance is hard, because it requires combining information about the current location and the observation, and then requires path planning to not get stuck in any dead ends that require a hop to escape. Let's ignore the path planning problem in the hopes that the RL agent will eventually memorize it through the state values, and just focus on whether or not we're communicating enough information that the model will pick up on close jumps being much better than far jumps.

max_travel_distance is, presumably, a constant, but even if it's a variable dependent on the location that won't matter too much (as it's twice as high in the corner, with the maximum distance, as it is in the center, with the minimum distance), and so you can view the reward as simply adding two factors--the distance, with weight $-\alpha$, and whether or not the target is unsearched, with weight $1$. But it seems to me like a sensible value of $\alpha$ is something like $1/2$ or $1/\sqrt{2}$. It should be less than $1$ so that it's worthwhile to travel at all (instead of just being indifferent between doing nothing and the optimal path), but we know that the optimal path doesn't involve any jumps higher than length $1$, and so jumps of length longer than $1$ should be discouraged (while still earning points on each 'optimal' step, such that it's still worth jumping out of a dead end you find yourself in). Also, setting this too high will discourage movement at all; it may be the case that $1/2$ leads to it taking a long time for the agent to escape the region near the center.

So try the subgoal-only reward again, but with a more sensible penalty for distance.