Modeling Multi-Agent Collision in Google CP-SAT Solver

Question

I would like to implement a solution for Multi-Agent Pathfinding Problem using Google's CP-SAT Solver.

How do I implement the constraint that prohibits 2 or more agents from occupying the same cell at the same time instance? I would like that when considering every individual step by an agent to be taking 1 time unit, at any time instance ti, no 2 agents occupy the same node in the graph.

[Example:] As visible in the image, for the three agents following the trajectory as marked, at time t=6 units, the green and blue agents occupy the same cell. Similarly, at t=12 units, the blue and pink agents occupy the same cell. The trajectories of the pink and green agents intersecting is not an issue, as each agent occupies the cell at different time steps, therefore not causing a collision.

Till now, I have implemented the problem without collision avoidance. Each agent has its corresponding matrix of decision variables, where each decision variable Pij represents if there is a transition or not from cell i to j in the solution. I have also added flow constraints, which means each agent may traverse a cell once each. Transitions are only possible in single steps between adjacent cells.

You may find my code till now here.

Answer 1

Here is my proposal:

for each arc: (one vertical or horizontal segment of an path)

• create a start variable
• compute a min duration
• create a end variable
• create an variable interval with those 3 variables
• add (start(current_arc) == end(previous_arc) # no wait constraint

For each conflicting cell:

• create a no_overlap_constraint(arcs using that cell)

Solve as a regular (scheduling) problem.