OSDAG: Online Scheduling for Efficient Multi-Robot Collaboration

Resumo Técnico de OSDAG: Agendamento Online para Colaboração Eficiente de Multi-Robôs

1. Declaração do Problema

O artigo aborda o desafio de coordenar Sistemas de Multi-Robôs (MRS) Heterogêneos para tarefas complexas de longo horizonte. Embora os Grandes Modelos de Linguagem (LLMs) tenham permitido que robôs interpretem linguagem natural e se adaptem a novas tarefas sem reprogramação, as estruturas existentes baseadas em LLM sofrem de dois gargalos críticos:

1. Latência de Inferência Repetida: Abordagens descentralizadas e baseadas em diálogo (ex: RoCo) exigem consultas contínuas ao LLM à medida que o número de agentes aumenta, fazendo com que o histórico de conversa cresça linearmente e infle a latência de execução.
2. Ineficiência do Agendamento Offline: A maioria das estruturas atuais, incluindo aquelas que combinam LLMs com otimização ou planejamento, depende de agendamento offline, onde todo o plano é computado antes do início da execução. Isso força os robôs a permanecerem ociosos enquanto esperam por predecessores ordenados sequencialmente, mesmo quando subtarefas independentes estão prontas para serem executadas em paralelo.

O problema central é desenvolver um sistema que mantenha as capacidades de raciocínio de alto nível dos LLMs, permitindo simultaneamente a execução paralela em tempo real que minimize o tempo de ociosidade e evite o overhead de inferência repetida.

2. Metodologia

A estrutura proposta, OSDAG (Online Scheduling for Efficient Multi-Robot Collaboration), integra o raciocínio baseado em LLM com representação de Grafo Acíclico Dirigido (DAG) e agendamento online consciente de restrições. O pipeline consiste em três estágios:

A. Decomposição de Tarefas Impulsionada por LLM (Inferência Única)
Diferente dos métodos baseados em diálogo, o OSDAG invoca o LLM exatamente uma vez. O LLM atua como um raciocinador de alto nível, não como um controlador de baixo nível. Dada uma instrução em linguagem natural, o contexto atual do espaço de trabalho (estados de objetos, capacidades dos agentes e alcançabilidade), o LLM gera uma lista estruturada de subtarefas.

• Entrada: O prompt inclui a instrução, agentes disponíveis, objetos alcançáveis, ações executáveis e um esquema de saída estrito.
• Saída: Uma lista de tarefas candidatas onde cada tarefa é anotada com um agente atribuído, ação, objeto alvo, destino e um conjunto de tarefas pré-requisitas (dependências).
• Validação: As tarefas geradas são validades contra restrições de viabilidade (ex: garantir que o agente atribuído possa alcançar o objeto e realizar a ação). Planos inválidos são rejeitados e regenerados.

B. Formalização do Grafo de Tarefas (Construção de DAG)
A lista de tarefas validada é convertida em um Grafo Acíclico Dirigido (DAG), $G = (V, E)$.

• Vértices: Representam subtarefas individuais.
• Arestas: Representam restrições de precedência (ex: uma tarefa de "colocar" não pode começar até que a tarefa correspondente de "pegar" esteja concluída).
• Significância: Esta estrutura codifica explicitamente tanto dependências sequenciais (ex: pegar $\to$ colocar) quanto dependências entre agentes (ex: transferências de objetos). Crucialmente, ela expõe ramos de tarefas independentes que podem ser executados em paralelo, ao contrário de sequências de ações lineares.

C. Agendamento Online Consciente de Restrições
Um agendador online leve executa o DAG em tempo real.

• Mecanismo: O agendador monitora continuamente os estados dos agentes (Livre ou Ocupado) e o status de conclusão das tarefas.
• Alocação Dinâmica: Quando um agente fica livre, o agenciador identifica imediatamente o conjunto de tarefas "prontas" (aquelas cujos predecessores foram concluídos e para as quais o agente é capaz). Ele atribui a tarefa pronta de índice mais precoce ao agente.
• Paralelismo: Esta abordagem orientada a eventos permite que ramos independentes do DAG procedam concorrentemente, eliminando o tempo de ociosidade inerente aos cronogramas offline pré-comprometidos.

3. Principais Contribuições

O artigo descreve três contribuições primárias:

1. Integração LLM-DAG: Um mecanismo que combina o raciocínio de LLM com a modelagem de dependência baseada em DAG, onde o LLM gera um grafo anotado com dependências baseado nas capacidades dos agentes e restrições ambientais em uma única passagem de inferência.
2. Algoritmo de Agendamento Online: Um algoritmo de alocação de tarefas em tempo real que garante a concorrência, minimiza o tempo de ociosidade e adere estritamente às restrições de dependência e recursos.
3. Validação Empírica: Experimentos abrangentes em cenários de simulação e do mundo real demonstrando desempenho superior em taxa de sucesso, latência e escalabilidade em comparação com modelos de referência.

4. Resultados Experimentais

O sistema foi avaliado em cinco cenários de benchmark envolvendo manipulação de mesa com 2–3 agentes, cobrindo tarefas como ordenação de objetos, limpeza e transferências (handoffs).

• Tempo de Raciocínio: O OSDAG alcançou um aceleração de 5 a 15 vezes no tempo de raciocínio em comparação com métodos baseados em diálogo (ex: RoCo). Para uma tarefa de 3 agentes, o RoCo exigiu 206,3 segundos, enquanto o OSDAG exigiu apenas 14,0 segundos. O OSDAG igualou a baixa latência de geradores de sequência plana (ChatGPT-Prompts) enquanto mantinha a consciência de dependência.
• Redução do Makespan: Ao utilizar o agendamento online para executar tarefas independentes em paralelo, o OSDAG reduziu o tempo total de conclusão (makespan) em 33% a 38% em comparação com as bases de agendamento offline. Por exemplo, em uma tarefa de transferência de 5 agentes, o makespan caiu de 41,6s (base) para 26,0s.
• Taxa de Sucesso: O OSDAG manteve taxas de sucesso competitivas (80–100%). Notavelmente, alcançou uma taxa de sucesso de 80% em uma tarefa complexa que exigia raciocínio de dependência implícita (ex: abrir uma gaveta antes de colocar itens), enquanto modelos de referência como RoCo e TwoStep falharam (0%) devido à falta de contexto de estado do objeto.
• Estudos de Ablação:
  • Remover o grafo de dependência causou falha completa (0% de taxa de sucesso) devido a conflitos de recursos.
  • Remover o agendamento online aumentou o makespan em 49–60%, apesar de planos corretos, confirmando a necessidade de alocação dinâmica.
  • Remover os embeddings de objeto/ação aumentou o tempo de raciocínio e reduziu as taxas de sucesso devido a alucinações.

Validação no Mundo Real: A estrutura foi implantada em um manipulador UF850 colaborando com um humano. O sistema coordenou com sucesso agentes heterogêneos (robô e humano) com diferentes interfaces, validando sua aplicabilidade prática.

5. Significância e Limitações

O artigo afirma que o OSDAG representa um passo significativo em direção à coordenação eficiente de multi-robôs, preenchendo a lacuna entre o raciocínio de alto nível de LLM e a eficiência de execução de baixo nível. Sua principal significância reside em demonstrar que a inferência de LLM de passagem única combinada com o agendamento de DAG online pode superar tanto sistemas descentralizados pesados em diálogo quanto planejadores offline rígidos.

No entanto, os autores reconhecem modestamente as limitações:

• A estrutura depende do LLM para gerar as arestas de dependência; erros de raciocínio podem aumentar com a complexidade ambiental e o número de agentes.
• A política atual de seleção de tarefas (tarefa pronta de índice mais precoce) pode não gerar cronogramas globalmente ótimos.
• O sistema atualmente carece de mecanismos de replanejamento; falhas de execução podem causar efeitos em cascata sem recuperação dinâmica.