Animation scientifique

Anonymous Multi-Agent Path Finding (A-MAPF) is the problem of assigning tasks to agents and planning the trajectories of agents in a graph such that they do not collide. We tackle a more realistic and general variant called Anonymous Multi-Agent Path Finding with task Duration (A-MAPF-D), in which each task has a given duration. The duration of a task corresponds to the number of consecutive turns during which an agent must remain on the task in order to perform it. We seek to minimize the makespan, that is, the minimum number of steps needed for all tasks to be performed by agents. We study A-MAPF-D through the light of two agent behaviors on target: whether they have to stay on the task after performing it (also called Complete) or they can move from their task after performing it (also called Reachable). As a first result, we show that A-MAPF-D Reachable is NP-hard. On the positive side, the problem becomes more tractable when those conditions are taken separately: we show that A-MAPF-D Complete is strongly polynomial and that A-MAPF Reachable is polynomial on paths and subdivided stars.