Encontrar o caminho multi-agente em ambientes contínuos

Por Kristýna Janovská e Pavel Surynek

Think about se todos os nossos carros pudessem dirigir – dirigir autônomo está se tornando possível, mas até que ponto? Para conseguir um veículo em algum lugar por si só, pode não parecer tão complicado se a rota estiver clara e bem definida, mas e se houver mais carros, cada um tentando chegar a um lugar diferente? E se adicionarmos pedestres, animais e outros não contabilizados para elementos? Esse problema foi recentemente estudado cada vez mais e já usado em cenários como a Logística do Warehouse, onde um grupo de robôs transfer caixas em um armazém, cada um com seu próprio objetivo, mas todos se movendo ao se certificar de não colidir e fazer suas rotas – caminhos – o mais curto possível. Mas como formalizar esse problema? A resposta é MAPF – descoberta de caminho multi-agente (Silver, 2005).

A descoberta de caminho multi-agente descreve um problema em que temos um grupo de agentes-robôs, veículos ou até pessoas-que estão tentando obter de suas posições iniciais para as posições de sua meta de uma só vez, sem nunca colidir (estar na mesma posição ao mesmo tempo).

Normalmente, esse problema foi resolvido em gráficos. Os gráficos são estruturas capazes de simplificar um ambiente usando seus pontos focais e interconexões entre eles. Esses pontos são chamados de vértices e podem representar, por exemplo, coordenadas. Eles são conectados pelas bordas, que conectam vértices vizinhos e representam distâncias entre eles.

Se, no entanto, estamos tentando resolver um cenário da vida actual, nos esforçamos para chegar o mais próximo possível da realidade. Portanto, a representação discreta (usando um número finito de vértices) pode não ser suficiente. Mas como pesquisar em um ambiente contínuo, ou seja, onde há basicamente uma quantidade infinita de vértices conectados por bordas de tamanhos infinitamente pequenos?

É aqui que algo chamado algoritmos baseados em amostragem entra em jogo. Algoritmos como RRT* (Karaman e Frazzoli, 2011), que usamos em nosso trabalho, selecionam aleatoriamente as coordenadas (amostras) em nosso espaço de coordenadas e os usam como vértices. Quanto mais pontos são amostrados, mais precisa é a representação do ambiente. Esses vértices estão conectados aos de seus vizinhos mais próximos, o que minimiza o comprimento do caminho do ponto de partida até o ponto recém -amostrado. O caminho é uma sequência de vértices, medida como uma soma dos comprimentos das bordas entre eles.

Figura 1: Dois exemplos de caminhos que conectam posições iniciais (azul) e posições de metas (verde) de três agentes. Uma vez que um obstáculo está presente, os agentes planejam caminhos curvos suaves ao seu redor, evitando com sucesso o obstáculo e o outro.

Podemos ficar perto do caminho very best dessa maneira, embora ainda exista um problema. Os caminhos criados dessa maneira ainda são um tanto acidentados, pois a transição entre diferentes segmentos de um caminho é nítida. Se um veículo seguisse esse caminho, provavelmente teria que se virar de uma só vez, quando chegar ao remaining de um segmento, como fazem alguns aspiradores robóticos ao se movimentar. Isso diminui significativamente o veículo ou um robô. Uma maneira de resolver isso é seguir esses caminhos e suavizá -los, para que as transições não sejam mais nítidas, mas curvas suaves. Dessa forma, robôs ou veículos que se movem para eles podem viajar suavemente sem parar ou desacelerar significativamente quando precisam de um turno.

Nosso papel (Janovská e Surynek, 2024) propuseram um método para a descoberta de caminho multi-agente em ambientes contínuos, onde os agentes se movem em conjuntos de caminhos suaves sem colidir. Nosso algoritmo é inspirado na pesquisa baseada em conflito (CBS) (Sharon et al.2014). Nossa extensão em um espaço contínuo chamado Pesquisa Baseada em Conflitos (CE-CBS) contínua de ambiente contínuo (CE-CBS) em dois níveis:

Figura 2: Comparação de caminhos encontrados com o algoritmo CBS discreto em uma grade 2D (esquerda) e caminhos CE-CBS em uma versão contínua do mesmo ambiente. Três agentes passam de pontos de partida azuis para pontos de gol verde. Essas experiências são realizadas no Laboratório de Agentes Robóticos da Faculdade de Tecnologia da Informação da Universidade Técnica da Tcheca em Praga.

Em primeiro lugar, cada agente procura um caminho individualmente. Isso é feito com o algoritmo RRT*, como mencionado acima. O caminho resultante é então suavizado usando curvas de spline b, curvas polinomiais por partes aplicadas aos vértices do caminho. Isso take away as curvas nítidas e facilita o caminho do caminho para um agente físico.

Os caminhos individuais são então enviados para o nível mais alto do algoritmo, no qual os caminhos são comparados e os conflitos são encontrados. O conflito surge se dois agentes (que são representados como corpos circulares rígidos) se sobreporem a qualquer momento. Nesse caso, são criadas restrições para proibir um dos agentes de passar pelo espaço conflitante em um intervalo de tempo durante o qual estava presente anteriormente nesse espaço. Ambas as opções que restringem um dos agentes são tentadas – uma árvore de configurações de restrição possíveis e suas soluções é construída e expandida com cada conflito encontrado. Quando uma nova restrição é adicionada, essas informações passam a todos os agentes que ela se preocupa e seus caminhos são re-planejados para que eles evitem o tempo e o espaço restritos. Em seguida, os caminhos são verificados novamente quanto à validade, e isso se repete até que seja encontrada uma solução livre de conflitos, que visa ser o mais curto possível.

Dessa forma, os agentes podem se mover efetivamente sem perder a velocidade enquanto giram e sem colidir um com o outro. Embora existam ambientes como corredores estreitos onde a desaceleração ou até mesmo a parada pode ser necessária para os agentes passarem com segurança, o CE-CBS encontra soluções na maioria dos ambientes.

Esta pesquisa é apoiada pela Tchech Science Basis, 22-31346s.

Você pode ler nosso artigo aqui.

Referências

• Janovská, Okay. e Surynek, P. (2024). Descoberta de caminho multi-agente em ambiente contínuoCorr.
• Sharon, G., Stern, R., Felner, A. e Sturtevant, NR (2014). Pesquisa baseada em conflito por uma very best de busca multi-agenteInteligência synthetic.
• Karaman, S. e Frazzoli, E. (2011). Algoritmos baseados em amostragem para planejamento very best de movimentoCorr.
• Piegl, L. e Tiller, W. (1996). O livro NurbsSpringer-Verlag, Nova York, EUA, segunda edição.
• Silver, D. (2005). Pathfinfing Cooperative.