ITA-ECBS: A Bounded-Suboptimal Algorithm for the Combined Target-Assignment and Path-Finding Problem
<|reference_start|>ITA-ECBS: A Bounded-Suboptimal Algorithm for the Combined Target-Assignment and Path-Finding Problem: Multi-Agent Path Finding (MAPF), i.e., finding collision-free paths for multiple robots, plays a critical role in many applications. Sometimes, assigning a target to each agent also presents a challenge. The Combined Target-Assignment and Path-Finding (TAPF) problem, a variant of MAPF, requires one to simultaneously assign targets to agents and plan collision-free paths for agents. Several algorithms, including CBM, CBS-TA, and ITA-CBS, optimally solve the TAPF problem, with ITA-CBS being the leading algorithm for minimizing flowtime. However, the only existing bounded-suboptimal algorithm ECBS-TA is derived from CBS-TA rather than ITA-CBS. So, it faces the same issues as CBS-TA, such as searching through multiple constraint trees and spending too much time on finding the next-best target assignment. We introduce ITA-ECBS, the first bounded-suboptimal variant of ITA-CBS. Transforming ITA-CBS to its bounded-suboptimal variant is challenging because different constraint tree nodes can have different assignments of targets to agents. ITA-ECBS uses focal search to achieve efficiency and determines target assignments based on a new lower bound matrix. We show that it runs faster than ECBS-TA in 87.42% of 54,033 test cases.<|reference_end|>
@article{tang2024ita-ecbs:,
    title={ITA-ECBS: A Bounded-Suboptimal Algorithm for the Combined
  Target-Assignment and Path-Finding Problem},
    author={Yimin Tang, Sven Koenig, Jiaoyang Li},
    journal={arXiv preprint arXiv:2404.05223},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.05223},
    primaryClass={cs.AI cs.RO}
}