Reduce computational complexity of env.step()
It was reported by Marc-Oliver Gewaltig that one performance bottle neck is currently the env.step()
function with computational complexity of at least O(N2).
The computational complexity comes from _check_action_on_agent()
which in turn calls _cell_free()
.
Because cell free has to loop over all agents to check whether the cell is free or not, this scales poorly with number of agents. The higher number of agents in the new examples lead to significant performance reduction.
def cell_free(self, position):
agent_positions = [agent.position for agent in self.agents if agent.position is not None]
ret = len(agent_positions) == 0 or not np.any(np.equal(position, agent_positions).all(1))
return ret
The suggestion by Marc-Oliver Gewaltig is thus to use a global dict to store the discretized positions of the agents, then we can check if cell is free with an operation of order O(1).
Attention: We have to be careful with this change. First refactoring to be safe would be just to add this dictionary without removing any other part and updating cell_free
function to do this check. We should also investiage all other loops over all agents.: