# Planowanie tras wielu robotów bez kolizji (MAPF)

EN: **Multi-agent path finding (MAPF)** · id `mapf` · aliases: multi-agent path finding, MAPF, multi-robot path planning, planowanie tras wielu agentów, planowanie tras wielu robotów

Path: [AI Atlas](https://aiatlasgraph.com/llms.txt) › [Robotyka i embodied AI](https://aiatlasgraph.com/t/robotics.md) › [Floty i zespoły robotów](https://aiatlasgraph.com/t/multirobot.md) › Planowanie tras wielu robotów bez kolizji (MAPF)

## Description

- PL: Wyznaczanie bezkolizyjnych ścieżek dla wielu agentów od startów do celów: metody przeszukiwania (CBS, PBS, LNS), kompilacyjne (SAT, MIP) i uczone.
- EN: Computing collision-free paths for many agents from starts to goals: search-based (CBS, PBS, LNS), compilation-based (SAT, MIP) and learned methods.

## In one sentence

- PL: Algorytm wyznacza trasy dla wielu robotów naraz tak, żeby każdy dojechał do celu, a żadne dwa nie spotkały się w tym samym miejscu.
- EN: An algorithm plans routes for many robots at once so each reaches its goal and no two meet in the same spot.

## Problem it solves

- PL: Gdy każdy robot planuje drogę sam, w wąskich alejkach powstają korki i blokady, z których nikt nie umie wyjechać.
- EN: When each robot plans alone, narrow aisles fill with jams and deadlocks nobody can get out of.

## What it does

- PL: Najpierw daje każdemu najkrótszą trasę, a potem rozwiązuje spory: kto czeka, kto objedzie, jak przy rozkładzie jazdy pociągów.
- EN: It first gives everyone the shortest route, then settles disputes – who waits, who detours – much like a train timetable.

## Everyday example

- PL: W automatycznym magazynie dziesiątki robotów mijają się w alejkach, ustępując sobie na skrzyżowaniach jak dobrze zsynchronizowane światła.
- EN: In an automated warehouse dozens of robots pass in the aisles, yielding at junctions like well-timed traffic lights.

## This concerns you if you…

- PL: projektujesz ruch wielu robotów w ciasnej przestrzeni
- PL: interesują cię algorytmy przeszukiwania w praktyce
- PL: tworzysz grę z wieloma jednostkami na mapie
- EN: design movement of many robots in a tight space
- EN: are interested in search algorithms in practice
- EN: make a game with many units on a map

## Keywords

conflict-based search · priority-based search · MAPF-LNS · ECBS · lifelong MAPF · PRIMAL · SAT-based MAPF · MovingAI benchmarks

## How it works

- PL: Mapa to zwykle graf lub siatka, a czas dzieli się na kroki. Conflict-Based Search planuje każdego agenta osobno algorytmem A*, wykrywa konflikty i rozgałęzia się, dodając ograniczenia dla jednej ze stron. Wersje przybliżone i przeszukiwanie dużych sąsiedztw obsługują tysiące agentów, a podejścia uczone trenują lokalne polityki RL lub imitacją planera.
- EN: The map is usually a graph or grid and time is split into steps. Conflict-Based Search plans each agent separately with A*, detects conflicts and branches by adding constraints for one side. Bounded-suboptimal variants and large neighbourhood search handle thousands of agents, while learned approaches train local policies with RL or by imitating a planner.

## Limits

- PL: Optymalne rozwiązanie jest obliczeniowo trudne, więc duże instancje rozwiązuje się przybliżenie. Model siatki z równymi krokami upraszcza prawdziwą kinematykę i opóźnienia robotów. Metody uczone są zwykle testowane na znacznie mniejszych mapach i flotach niż klasyczne.
- EN: Optimal solutions are computationally hard, so large instances are solved approximately. A grid with uniform steps simplifies real robot kinematics and delays. Learned methods are usually tested on much smaller maps and fleets than classical ones.

## Key terms

- PL: **konflikt**: Dwa roboty w tym samym miejscu lub na tej samej krawędzi w tej samej chwili.
- PL: **CBS**: Conflict-Based Search: rozwiązywanie konfliktów przez dodawanie zakazów.
- PL: **zakleszczenie**: Sytuacja, w której roboty blokują się nawzajem i żaden nie może ruszyć.
- EN: **conflict**: Two robots at the same place or edge at the same time.
- EN: **CBS**: Conflict-Based Search: resolving conflicts by adding constraints.
- EN: **deadlock**: Robots blocking each other so none can move.

## Know first

- [Przeszukiwanie heurystyczne (A*) (Heuristic search (A*))](https://aiatlasgraph.com/t/astar.md)

## Related topics

Untyped, symmetric "see also" links.

- [Siatki nawigacyjne i odnajdywanie drogi (Navigation meshes and pathfinding)](https://aiatlasgraph.com/t/navmesh.md)

## Sources

- [Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding](<https://arxiv.org/abs/2505.19219>) `mapf-survey-2025` · by S. Wang, H. Xu, Y. Zhang, J. Lin, C. Lu, X. Wang, W. Li

---

AI Atlas revision 122 (2026-10-30) · HTML: https://aiatlasgraph.com/t/mapf · index: https://aiatlasgraph.com/llms.txt · everything: https://aiatlasgraph.com/llms-full.txt · updated 2026-10-30