1
$\begingroup$

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.

Paths of individual agents

[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.

$\endgroup$
4
  • $\begingroup$ This is way too abstract. Can you elaborate, give a small example? $\endgroup$ Jun 12, 2022 at 20:59
  • $\begingroup$ @LaurentPerron Sorry about that, I have explained in greater details as requested. Thanks. $\endgroup$ Jun 12, 2022 at 21:19
  • 1
    $\begingroup$ @RaghavThakar, why not solving the problem for each agent separately and collecting them together in the next step instead of solving the whole model? What does exactly intersecting cell mean? $\endgroup$
    – A.Omidi
    Jun 13, 2022 at 4:40
  • $\begingroup$ @A.Omidi I would like that no two agents occupy the same cell at the same time. I can solve each agent separately, but then that would not take into account the possibility of another agent planning a path that causes two agents to collide (by being on the same cell at the same time) $\endgroup$ Jun 13, 2022 at 18:03

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Perfect! The aspect of a start and end variable for each arc would mean that I can control individual transitions. Thank you. I think a callback function after each primitve solution to check for conflics will do the trick. $\endgroup$ Jun 13, 2022 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.