some changes in code

[sirius-zyj]

If at time T, an agent occupies a grid, then at time T+1, no other agent except the occupant itself can move to this grid. In this case, how can I edit the code?

[Kei18]

Hi, I think it is doable. Below is a short guideline.

• LaCAM(*) uses PIBT as a configuration generator
• Except for the swap operation, PIBT can prohibit such conflicts by adding a few lines, c.f.,
  • vertex conflict
  • swap conflict
• And, do not forget to add constraints to LaCAM itself
• I do not have a short answer for the swap operation. At first, it is better to drop it. Seems complicated.

[sirius-zyj]

Thank you very much for your advice. Based on my understanding of the algorithm, I added the PIBT conflict constraint and LACAM constraint as follows. However, the results of the code execution are rather strange. I hope you can help correct it when you have time.

[Kei18]

The following is a minimum working example.

constraints for LaCAM https://github.com/Kei18/lacam2/blob/dev/lacam2/src/planner.cpp#L290

  // add constraints
  for (uint k = 0; k < L->depth; ++k) {
    const auto i = L->who[k];        // agent
    const auto l = L->where[k]->id;  // loc

    // check vertex collision
    if (occupied_next[l] != nullptr) return false;

    // check following collision
    if (occupied_now[l] != nullptr && i != occupied_now[l]->id) return false;

    // set occupied_next
    A[i]->v_next = L->where[k];
    occupied_next[l] = A[i];
  }

PIBT https://github.com/Kei18/lacam2/blob/dev/lacam2/src/planner.cpp#L342

  // PIBT operation
  for (auto k = 0; k < K + 1; ++k) {
    auto u = C_next[i][k];

    // avoid vertex conflicts
    if (occupied_next[u->id] != nullptr) continue;

    auto& ak = occupied_now[u->id];

    // avoid following conflicts
    if (ak != ai && ak != nullptr) continue;

    // reserve next location
    occupied_next[u->id] = ai;
    ai->v_next = u;

    // success to plan next one step
    return true;
  }

Please note that this is a toy example. To elicit the performance of LaCAM, you need to improve the performance of the PIBT part; Indeed, the above is just doing prioritized planning with a single-step window (and empirically shown bad in the AAAI-23 paper)