Multi-Agent Path Finding

Também chamado: MAPF, multi-agent pathfinding, multi-robot path planning
Categoria: Learning & autonomy › Multi-robot
Tags: multi-robot, path-planning, warehouse-automation, coordination, graph-search

O problema de calcular caminhos livres de colisão para muitos agentes que se movem ao mesmo tempo em um grafo compartilhado, como robôs de armazém em uma grade, de modo que cada agente chegue a seu objetivo sem conflitos.

Definição

Busca de caminhos multiagente (Multi-Agent Path Finding, MAPF) é o problema de planejar caminhos para um grupo de agentes que compartilham um ambiente, de modo que cada agente vá de seu início até seu objetivo sem que dois agentes ocupem o mesmo lugar ao mesmo tempo ou troquem de lugar ao longo da mesma aresta. O ambiente geralmente é modelado como um grafo, muitas vezes uma grade, e o tempo é dividido em passos discretos em que cada agente se move para um vértice vizinho ou espera.

As soluções de MAPF costumam ser avaliadas pela soma dos custos, o tempo total que todos os agentes levam para chegar a seus objetivos, ou pelo makespan, o tempo até a chegada do último agente. Encontrar uma solução ótima sob esses objetivos é NP-difícil em geral, por isso a área desenvolveu algoritmos que trocam otimalidade por velocidade. Entre os métodos ótimos está o Conflict-Based Search (CBS), que planeja cada agente de forma independente e depois resolve as colisões adicionando restrições em uma árvore de busca. Métodos subótimos, como o planejamento priorizado, em que os agentes planejam um de cada vez e tratam os agentes anteriores como obstáculos em movimento, escalam para equipes muito maiores.

O MAPF contínuo (lifelong MAPF) é uma variante em que os agentes recebem novos objetivos assim que alcançam os anteriores, o que corresponde a como robôs de armazém e de triagem realmente trabalham. O planejamento então roda continuamente, muitas vezes sobre uma janela de tempo limitada, e a vazão passa a ser a principal medida.

Robôs reais também quebram as suposições dos livros: eles têm tamanho, limites de aceleração e atrasos de execução, por isso os planos de MAPF geralmente são executados com uma camada extra de coordenação que mantém os robôs seguros quando alguns ficam atrasados em relação ao cronograma. Métodos baseados em aprendizado, incluindo aprendizado por imitação a partir de planejadores baseados em busca, são uma linha de pesquisa ativa para escalar para frotas muito grandes.

Por que importa

Armazéns, fábricas e centros de triagem operam frotas crescentes de robôs móveis em pisos compartilhados, e sua vazão depende de quão bem esses robôs são coordenados. O MAPF fornece os algoritmos que mantêm os robôs em movimento sem colisões nem impasses à medida que as frotas crescem.

Principais aplicações

Frotas de robôs em armazéns e centros de fulfillment
Sistemas de triagem de encomendas com muitos robôs móveis
Coordenação de veículos guiados automaticamente em fábricas
Coordenação de múltiplos drones e do tráfego em solo de aeroportos
Movimentação de personagens em videogames e simulação de multidões

Na prática

Uma equipe que opera uma frota de armazém normalmente modela o piso como uma grade ou um grafo de rotas, com cada célula dimensionada para caber um robô. Um planejador central recebe objetivos do sistema de pedidos e calcula caminhos coordenados, muitas vezes com uma busca priorizada ou por janelas que replaneja a cada poucos segundos em vez de resolver o problema inteiro de forma ótima. Os caminhos são convertidos em pontos de passagem temporizados e enviados aos robôs, e uma camada de execução, como um grafo de dependências de ações, garante que um robô não entre em uma célula até que o robô à frente a tenha liberado. Os engenheiros medem a vazão, o tempo de espera e a frequência de impasses em simulação com a frota completa antes de mudar o layout do piso ou o algoritmo no sistema real.

Equívocos comuns

Cada robô pode planejar seu próprio caminho mais curto de forma independente — caminhos independentes colidem, então os robôs precisam ser coordenados no tempo e no espaço
O MAPF ótimo escala para qualquer tamanho de frota — a solução ótima é NP-difícil, por isso frotas grandes dependem de métodos subótimos ou por janelas
Um plano de MAPF pode ser executado exatamente como calculado — robôs reais adiantam ou atrasam, então a execução precisa de sua própria camada de segurança e coordenação

Quem deve saber

Engenheiros de automação de armazéns e de gestão de frotas
Pesquisadores de planejamento multirrobô
Integradores de sistemas AMR e AGV
Pesquisadores operacionais que trabalham com logística

Tecnologias relacionadas

Conflict-Based Search
Planejamento priorizado (Prioritized Planning)
Busca A (A Search)
Sistemas de gestão de frotas (Fleet Management Systems)
Aprendizado por imitação (Imitation Learning)

Termos relacionados

Projetos relacionados

Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
Open X-Embodiment (OXE): Largest open robotics dataset: 1M+ episodes from 22 embodiments
IR-SIM: Lightweight pure-Python 2D robot simulator for navigation, control and RL research
Mesh Navigation: Robot navigation on 3D triangle meshes for rough outdoor terrain, from Nature Robots