Задача много-агентного планирования путей (задача MAPF, от англ. Multi-Agent Pathfinding) состоит в том, чтобы найти совокупность неконфликтных путей на графе. С одной стороны известно, что даже при наличии многих упрощающих допущений получение оптимальных решений этой задачи относится к классу NP-Hard. С другой – эффективные алгоритмы решения MAPF задач очень востребованы на практике, например, при создании автоматизированных складов. Именно поэтому область MAPF активно развивается, а соответсвующие подходы постоянно совершенствуются, как за счет алгоритмических решений, так и за счет применения современных методов и моделей машинного обучения. Несмотря на достигнутый прогресс, в области остается ещё много интересных, нерешенных задач, над которыми в том числе работают сотрудники Лаборатории Маркова.