@hagrid67 @aiAdrian is there a reason why svBlocked are not all marked red outsie of the loop?

yes I can't see any reason why we don't use some sort of bulk action to mark svBlocked as "red"; though it may not save much time as it looks like an O(n) operation.

Focus is on readability and not on performance, agreed.

@hagrid67 @aiAdrian if the loop only contained conflict resolution for the remaining nodes of indegree > 1, that would greatly reduce reading complexity - do you see a problem with that? And also drop the red-purple distinction?

Yes I think the suggestion that we only need to process indegree>1 in a conflict resolution loop sounds correct.

I think the intention of the red / purple distinction is that

• red is "temporary" ie blocked by a voluntarily stopped agent, or a slow one which is stepping in the same cell
• purple is the result of a deadlock, which here means a "swap" where two agents are adjacent and facing, ie they are trying to "swap" cells. Purple is therefore "permanent" for the rest of the episode. I don't think we make any use of this but it could be useful.

Purple should take precedence over red, but I don't think it does. eg in the following chain:
1East -><- 2West <-3West <-4West
1 and 2 are deadlocked, so 3 and 4 should also be deadlocked: there is nothing they can do now to escape the deadlock.

But if 2 or 3 also has a failure, or maybe even chooses a voluntary "pause/stop" action, I think this in effect "breaks" the purple chain, in the implementation as I remember it. I remember partial chains flicking from purple to red and back. I think this is visually misleading but harmless (because they still don't move).

What happens is that if say agent 3 above has a malfunction, then it's "desired motion" becomes a self-loop which breaks the chain in our representation. (When I wrote this, I think all agent speeds were 1)

We could somehow preserve purple chains from one timestep to the next: once an agent is purple, it remains purple for the episode. We could then prevent those agents stepping, and reduce the processing in the motion check. It may also be useful in the observation (if it isn't already there).

I suspect that the very poor performance of motioncheck in the profiling test case may be related to random actions which result in huge jams and this provokes a lot of traversing of predecessor trees. If these were marked purple and preserved and then skipped, there could be performance benefit.

@hagrid67 @aiAdrian why do we need weakly connected components at all? We could just reverse traverse the directed graph?

Yes I think you are right once again! We could just traverse the reverse* graph, starting from the "swaps and stops" (ie immediate deadlocks, and voluntary / failed / slow agents). There doesn't seem to be any need to break the graph down into weakly connected components first. The traversal will naturally terminate as it reaches the "boundaries" of WCCs.

When I wrote the motioncheck I tried to look for algos which did clever stuff, assuming they would be faster than my own implementation. Processing the WCCs separately seemed reasonable and my small-case performance checks did not expose the O(n^2) performance problems we seem to have.

See the comment below - I think we still need the reverse graph because the dfs traversal to read the tree of blocked agents can only progress in a forward direction.
(*You said reverse-traverse the graph, I'm saying traverse the reverse graph ;)

@hagrid67 @aiAdrian why do we need the reversed graph at all? Can we not just use the predecessors of directed graphs? Or does this have performance drawbacks?

We need to traverse the desired motion graph backwards, to find agents which are trying to move into a blocked cell.

I don't think there is a NetworkX call to do this. dfs_predessors does the wrong thing: it traverses the tree in the forward direction, and simply returns the predecessor of each node.

For example, if cell 4 is blocked, we want all the (branched) predecessors 0,1,2,3,5,6. But dfs_predecessors returns an empty set because 4 has no successors.

G = nx.DiGraph([ (0,1), (1,2), (2,3), (3,4), (5,6), (6,2) ])
nx.dfs_predecessors(G, source=4)
returns: {}

However we can get what we need using the reverse graph and dfs_postoder_nodes (as in the code):

H = G.reverse()
list(nx.dfs_postorder_nodes(H, source=4))
returns:  [0, 1, 5, 6, 2, 3, 4]

However this maybe raises the question, do we really need the forward graph? Maybe we should build only the reverse graph, because we only really need to follow the motion in reverse? We only seem to use G.succ in check_motion() and it doesn't seem to be doing much.

So if we built only the reversed graph Grev, we could use Grev.succ instead of G.pred.

Generally trying to navigate "upstream" in a Directed Graph seems like hard work in NetworkX.

@hagrid67 thought of:

g = nx.DiGraph([ (0,1), (1,2), (2,3), (3,4), (5,6), (6,2) ])
print(list(g.predecessors(4)))
# returns: [3]

@hagrid67 @aiAdrian why do we need find_stop_preds - couldn't we not just re-use mark_preds(swStops, color="red")?

Gosh yes, well spotted, this does seem to be pointless; I'm embarrassed for my younger self!

FWIW, the logic in mark_preds (called block_preds in my older version) does not match the comment "only color those not already marked" but it looks like it overwrites the color. In my older version it seems to count the ones it has to change, which would justify the check; but then the count is discarded anyway.

use numpydoc, see https://github.com/flatland-association/flatland-rl/blob/main/CONTRIBUTING.md#numpydoc