Multi Agent Path Finding with Crossing Cost

Multi Agent Path Finding (MAPF) is a fundamental problem on AI field. When agents cross each other on planned paths, they have to pay attention for collision. Thus, path planning that minimizes the number of crossing is desirable. In this motivation, we consider IMAPF with crossing cost. Given a directed graph and k pairs of a start and a goal, we want to find k paths minimizing crossing. In this talk, we introduce several results and open problems.