flatland.envs.agent_chains module

Agent-Close Following is an edge cose in mutual exclusive resource allocation, i.e. the same resource can be hold by at most one agent at the same time. In Flatland, grid cell is a resource, and only one agent can be in a grid cell. The only exception are level-free crossings, where there is horizontal and a vertical resource at the same grid cell.

The naive solution to this problem is to iterate among all agents, verify that their targeted resource is not occupied, if so allow the movement, else stop the agent. However, when agents follow each other in chain of cells, different agent orderings lead to different decisions under this algorithm.

MotionCheck ensures: - no swaps (i.e. collisions) - no two agents must be allowed to move to the same target cell (resource) - if all agents in the chain run at the same speeed, all can run (behaviour not depending on agent indices)

class flatland.envs.agent_chains.MotionCheck

Bases: object

Implementation based on Bochatay (2024), Speeding up Railway Generation and Train Simulation for the Flatland Challenge.

An alternative would be to introduce > 0 release times and then reject

Release times reflect physical or IT constraints for the system to be ready again, or buffer times ensuring safety constraints.

Release times known also in Job Shop Scheduling Problems in the Operations Research literature, see e.g. Bürgy (2014), Complex Job Shop Scheduling: A General Model and Method (https://reinhardbuergy.ch/research/pdf/buergy14_phd-Thesis.pdf)

add_agent(i: int, r1: Tuple[int, int] | None, r2: Tuple[int, int] | None)

Add agent holding resource r1 and trying to acquire r2 (or not release r1 if r1==r2).

check_motion(i: int, r: Tuple[int, int]) → bool

Returns

Will the agent move (either because it does not want to move or because it is stopped by conflict resolution)?

find_conflicts()

Find and resolve conflicts: - swaps aka. deadlocks (head-to-head collisions) - two agents same target

Correctness: - deadlocked agents are stopped - for each conflict, one of the agents is stopped.

Termination: The list of target_conflicts will eventually be empty as in every round, one agent is stopped.

class flatland.envs.agent_chains.MotionCheckLegacy

Bases: object

Class to find chains of agents which are “colliding” with a stopped agent. This is to allow close-packed chains of agents, ie a train of agents travelling at the same speed with no gaps between them,

Agent Chains: Unordered Close Following Agents

Think of a chain of agents, in random order, moving in the same direction. For any adjacent pair of agents, there’s a 0.5 chance that it is in index order, ie index(A) < index(B) where A is in front of B. So roughly half the adjacent pairs will need to leave a gap and half won’t, and the chain of agents will typically be one-third empty space. By removing the restriction, we can keep the agents close together and so move up to 50% more agents through a junction or segment of rail in the same number of steps.

We are still using index order to resolve conflicts between two agents trying to move into the same spot, for example, head-on collisions, or agents “merging” at junctions.

Implementation: We did it by storing an agent’s position as a graph node, and a movement as a directed edge, using the NetworkX graph library. We create an empty graph for each step, and add the agents into the graph in order, using their (row, column) location for the node. In this way, agents staying in the same cell (stop action or not at cell exit yet) get a self-loop. Agents in an adjacent chain naturally get “connected up”.

Pseudocode: * purple = deadlocked if in deadlock or predecessor of deadlocked (mark_preds(find_swaps(), ‘purple’)) * red = blocked, i.e. wanting to move, but blocked by an agent ahead not wanting to move or blocked itself (mark_preds(find_stopped_agents(), ‘red’)) * blue = no agent and >1 wanting to enter, blocking after conflict resolution (mark_preds(losers, ‘red’)) * magenta: agent (able to move) and >1 wanting to enter, blocking after conflict resolution (mark_preds(losers, ‘red’))

We then use some NetworkX algorithms (networkx/networkx):

• weakly_connected_components to find the chains.

• selfloop_edges to find the stopped agents

• dfs_postorder_nodes to traverse a chain

add_agent(iAg: int, rc1: Tuple[int, int], rc2: Tuple[int, int], xlabel=None)

add an agent and its motion as row,col tuples of current and next position. The agent’s current position is given an “agent” attribute recording the agent index. If an agent does not want to move this round (rc1 == rc2) then a self-loop edge is created. xlabel is used for test cases to give a label (see graphviz)

check_motion(iAgent: int, rcPos: Tuple[int, int]) → bool

Returns tuple of boolean can the agent move, and the cell it will move into. If agent position is None, we use a dummy position of (-1, iAgent). Called in env.step() after conflicts are collected in find_conflicts() - each agent now can execute their position update independently (valid_movement) by calling check_motion. :param iAgent: agent handle :param rcPos: cell :return: true iff the agent wants to move and it has no conflict

find_conflicts()

Called in env.step() before the agents execute their actions.

find_stop_preds(svStops: Set[Tuple[int, int]]) → Set[Tuple[int, int]]

Find the predecessors to a list of stopped agents (ie the nodes / vertices). Includes “chained” predecessors. :param svStops: list of voluntarily stopped agents :return: the set of predecessors.

find_stopped_agents() → Set[Tuple[int, int]]

Find stopped agents, using a networkx call to find self-loop nodes. :return: set of stopped agents

find_swaps() → Set[Tuple[int, int]]

Find loops of size 2 in the graph, i.e. swaps leading to head-on collisions. :return: set of all cells in swaps.

get_G_reversed()

mark_preds(svStops: Set[Tuple[int, int]], color: object = 'red') → Set[Tuple[int, int]]

Take a list of stopped agents, and apply a stop color to any chains/trees of agents trying to head toward those cells. :param svStops: list of stopped agents :param color: color to apply to predecessor of stopped agents :return: all predecessors of any stopped agent