Edge collision check in PIBT inside LaCAM(*) implementation

[Arseni1919]

The journal version of PIBT pseudocode is:

I want to check a little issue with the code regarding edge collision (ec) checks. While in pure PIBT algorithm, the pseudocode totally works, in LaCAM implementation PIBT function receives some predecided locations for several agents due to LowLevelNode's constraints. In the latter case, unfortunately, the previous ec check will not catch all the cases, where the ec may occur not only with the agent j.

if agent_j is not None and config_from[agent_j.name] == nei_node:
    continue

May I suggest the following code for completeness:

def there_is_ec(
        agent_i: AgentAlg,
        nei_node: Node,
        config_from: Dict[str, Node],
        config_to: Dict[str, Node],
) -> bool:
    node_from = config_from[agent_i.name]
    for other_name, other_f_node in config_from.items():
        if other_name == agent_i.name:
            continue
        if other_name not in config_to:
            continue
        other_t_node = config_to[other_name]
        if other_f_node == nei_node and other_t_node == node_from:
            return True
    return False

Am I missing any details about the ec check?...

Thank you!

[Kei18]

I do not see issues with the implementation of the edge collision check. This part should (efficiently) catch all cases, regardless of the work of the low-level node. https://github.com/Kei18/py-lacam/blob/pibt/pycam/pibt.py#L42-L46

Let me know if you have counterexamples.

[Arseni1919]

Great! That code solves the problem completely indeed:

j = self.occupied_now[v]

# avoid edge collision
if j != self.NIL and Q_to[j] == Q_from[i]:
    continue

( https://github.com/Kei18/py-lacam/blob/pibt/pycam/pibt.py#L42-L46 )

The difference is what does the agent j mean in each case:

• in pseudocode (presented above), the j agent is one that comes with the input of the function
• in the snippet the j agent is one that occupies the vertex (occupied_now[v])

IMO, that might confuse a bit, that's all. Hope I was clear with the description.

[Kei18]

Right, in recent implementations of PIBT I do not use arguments for agent-j. I realised it was redundant from an implementation perspective.