# How do I solve this optimal control problem with reinforcement learning?

I am new to reinforcement learning. I would like to solve an optimal control problem with reinforcement learning.

The objective is for a wolf to catch a rabbit. The wolf and the rabbit run on a plane. The time is discrete. At every time step, the wolf can only run straight, change direction by 10 degrees to the right or left, change the speed by 0.1 m/s or remain at the same speed. It starts running in some random direction, and then sees the rabbit and starts chasing it. For the time being, let's assume that the rabbit sits still.

It looks like this problem is a continuous state space and discrete action space.

I have tried to use DQN in Keras, but I am not sure that I am using correct state variables/reward. Currently, the state variables are the velocity vector of the wolf, the distance vector from the wolf to the rabbit. The reward at each time point is the negative current time. When the wolf catches the rabbit, the reward is 1000 - current time (the wolf is penalized for running too long).

Can somebody provide me some guidance? Eventually, I would add brains to the rabbit so that it tries to escape the wolf and compare to the optimal control solution.

I have tried to use DQN in Keras, but I am not sure that I am using correct state variables/reward.

You have a wide range of choices that are all valid. As it is a simple control and learning scenario, provided you cover basics (described in a moment), then the difference in your choices are about how easy you make it for the agent to learn. You may actually want to set things up so that there is a certain difficultly level, so you get to compare different agent designs. You don't necessarily need the "best" state representation and reward function designs here. Just some that work.

## State representation

The most important factor is that your state has the Markov property - that it contains enough information that the agent really can predict expected future rewards.

It is OK for there to be randomness, but generally not OK for there to be important hidden variables that affect the outcome in a major way. If there are such variables in the environment, but not in the state representation, then a simple agent like DQN will struggle.

## Reward function

The reward function should capture the end goals that you are interested in, and ideally as simply and purely as possible given that. The purpose of most RL methods is to maximise the expected sum of reward, and they are built to deal with sparsity - you don't need to help or signal the same thing twice or give rewards for "getting close" etc, although sometimes this can improve learning speed if done well.

I have also written a more comprehensive answer about reward function design as an answer to Deciding on a reward per each action in a given state (Q-learning)

Currently, the state variables are the velocity vector of the wolf, the distance vector from the wolf to the rabbit.

This seems reasonable. Do consider that for a neural network you will want to keep the scale of these to within a nice range e.g. -1 to +1 for all features. So you may want to scale from whatever you are using for the values in the environment.

You can make this problem easier to learn by using polar co-ordinates. That removes the need for the neural network to solve the inherent trigonometry problem when deciding if turning left or right is better. I have solved a very similar pursuit RL problem and compared between cartesian and polar co-ordinates, and the difference is very large between the two representations for a DQN based agent.

Specifically for the easiest learning you want the difference vector between your agent's current heading and the target, expressed as a difference in heading plus distance to go. If you do this, sometimes the initial randomised neural network will already be efficient at solving the problem.

However, it may be interesting for you to see how well different agents do solve that trigonometry problem of converting a difference in vector coordinates and velocity, into a direction to turn. You could even make it harder and give absolute location coordinates for both agent and the target, plus the agent velocity (3 vectors instead of 2), requiring the neural network to approximate even more complex maths before it solves the problem.

The reward at each time point is the negative current time. When the wolf catches the rabbit, the reward is 1000 - current time (the wolf is penalized for running too long).

That should work, but seems more complex than you need. You are already penalising the wolf for each time step during the chase, so there is no real need to have any extra formula for the final reward. In fact you can just have a final reward of 0 for reaching a satisfactory goal (providing there are no unsatisfactory end points that you want it to avoid - perhaps yo umay make the environment trickier later on?). The agent will simply try to resolve the episode quickly because that will still maximise the (negative total) return.

An alternative might be to reward some value for catching the rabbit e.g. +10, and zero on each time step. Then to encourage a fast resolution you would need to use discounting, so that the agent values being nearer to the rabbit higher than being further away because the potential reward is fewer time steps away.

There is also no need to use large values. Values are relative, so if you have some minor issue to solve plus a main goal, sometimes it is worth having a wide range of values. Here you don't need it. Having a value of 1000 may challenge your neural network to learn properly (because error for the first time the wolf catches a rabbit would be so large it may cause a large step in weights - enough to destabilise learning in the NN), for no real benefit.

For your first reward scheme I recommend a fixed reward of e.g. -1 per time step, and to end the episode when the wolf catches the rabbit. No multiplications or offsets.

If you have a very large area for the wolf to explore compared to the distance that the wolf needs to be from the rabbit in order to catch it, it may help to give some reward for proximity to the rabbit. The simplest to implement and learn would just be the difference in distance between the wolf and rabbit between $$t$$ and $$t+1$$ multiplied some small factor to put this into a similar range to the penalty per time step. Note if you extend this reward out to any significant distance that it should make the learning problem far easier (combine polar coordinates and this reward system will make it very easy for the DQN to learn - it should take only a few episodes to get near optimal behaviour, if your learning hyperparameters are good for the DQN).

Without any proximity reward, you will rely on the wolf literally bumping into the rabbit through random behaviour, before it will have any data example that getting the vector between itself and the rabbit close to (0,0) is a good thing. You may need to have a relatively large capture radius, plus limit the area that the wolf (and eventually rabbit) can explore, in order to avoid very long sequences of random behaviour where nothing is learned initially.

• Thanks for extensive advice. I have some follow up questions. I have found that this problem is commonly known as a predator-prey pursuit problem but I wasn't able to find a continuous version. The papers are concentrating on the movement on the grid but in my case I have a continuous plane. Are there any papers that address continuous nature of movement? Based – TFbie Jul 29 '19 at 12:10
• @TFbie: You should ask your follow-up questions as new ones on the site. I am not sure if there are any papers on continuous control, but I think the predator prey prusuit problem sounds on-topic for AI stack exchange. Meanwhile, if this answer helped you, please mark it as accepted. – Neil Slater Jul 29 '19 at 12:15
• I don't know how to mark it accepted Sorry. – TFbie Jul 29 '19 at 12:42
• * Just to clarify - state = angle between predator's heading and the prey, predator's speed, distance to the prey. Do you recommend something else? * Is the neural network good enough: 2 relu layers of size 24 and 48, output linear. * What regularization would you suggest? L2/dropout – TFbie Jul 29 '19 at 12:42
• @TFbie You should ask a new question. But to save you from possible frustration: Use either no regularisation or a very small amount of L2. You don't need much as you have a near infinite data set as the agent keeps generating new data. In my experience, dropout will break your DQN, there's something about it that is not compatible with RL. I think it is to do the non-stationary dataset you get during polciy improvement, but have not found a good way to prove that. – Neil Slater Jul 29 '19 at 13:38