Your problem is not that the environment is stochastic or dynamic. In fact you are using the terms slightly incorrectly. These terms do not usually refer to the fact that starting state can differ or goal locations can move episode-by-episode. They typically refer to behaviour of state transitions.
Although in your case you could view the initial state as stochastic, this is not a big deal, and not likely to be the cause of your problems.
From your questions, it seems to me that you are not really running a DQN algorithm yet. It is not 100% clear what your neural network is predicting, but my best guess is that you have 4 outputs to select "best" action and are treating the neural network as a classifier. This training approach seems closest to Cross Entropy Method (CEM) due to how you are selecting "successful" navigation only.
When training the DQN, how do i apply Q-values?
This question is the most revealing that you are not using DQN. This is too complex to describe in full in an answer, but the basics are:
Your neural network (NN) should be estimating Q values. Typically in DQN, you input the state and the NN outputs an array of estimates for Q of each action (although other architectures are possible). This should be a regression problem, so last layer of network needs to be linear.
Current best guess of optimal policy is to run the NN forward and find the maximising action.
In DQN you also have a "behaviour policy" - a simple and popular choice is to use $\epsilon$-greedy action selection, which just means to take the maximising action (as calculated above), except with probability $\epsilon$ (some small value, e.g. 0.1) to take a random action.
To figure out your training data to improve the NN, you need Q values to calculate a TD Target. In single-step Q learning that would be $r + \gamma Q(s',a*)$ where $r$ is the immediate reward $s'$ is the next state seen, and $a*$ is the maximising action in that state. You should force $Q(s', a*) = 0$ (i.e. not use the NN) if $s'$ is a terminal state.
This means you typically need to work with Q values in 2 or 3 places in your inner loop. Your inner loop should look something like this per time step, given a current state
# Figure out how to act
current_q_values = NN_predict(current_state)
current_action = argmax(current_q_values)
if random() < epsilon:
current_action = random_action()
# Take an action
reward, next_state, done = call_environment(current_state, current_action)
# Remember what happened
store_in_replay_memory(current_state, current_action, reward, next_state, done)
# Train the NN from memory
repeat N times: # This can be vectorised for efficiency
mem_state, mem_action, mem_reward, mem_next_state, mem_done = sample_replay_memory()
mem_q_values = NN_predict(mem_next_state)
mem_max_action = argmax(mem_q_values)
td_target = mem_reward
td_target = mem_reward + gamma * mem_q_values[mem_max_action]
target_q_values = NN_predict(mem_state)
target_q_values[mem_action] = td_target
# Maybe end an episode (this can include generating new map)
current_state = reset_environment()
current_state = next_state
You can see above,
NN_predict is called three different times to get Q values in slightly different contexts. I have ignored extras such as using a separate target network.
I train the network using only a short replay memory of the last move, or the last N moves that led to success. Is this the right way to approach this?
It is important to include moves that lead to failure so that the NN learns the difference. Typically you will need a replay memory with from a few hundred to a few hundred thousand entries. You would get away with a few hundred perhaps for your simple problem. The idea is to use this training data a bit like a dataset from supervised learning.
I use Keras, and am simply training the network every time it does something right - and ignoring failed attempts. - But is this anywhere near the right approach?
This is not the right approach for DQN, although perhaps could be considered a crude version of CEM.