Um estudo sobre algoritmos de coordenação de uma frota flexível de veículos móveis autónomos em ambientes de logística interna

Abstract

Este projeto de dissertação aborda o problema de coordenação de uma frota de veículos autónomos em ambientes de logística interna, sendo que o ambiente é conhecido à priori com obstáculos estáticos e dinâmicos detetados pelas leituras dos sensores dos robôs. Para que haja coordenação é necessário garantir a existência dos seguintes aspetos: comunicação, atribuição de tarefas, prevenção de colisões, planeamento de caminhos, gestão de frotas, protocolos de segurança e flexibilidade. Foi implementada uma abordagem centralizada, isto é, os robôs constituintes da frota comunicam com um componente responsável pela tomada de decisões. Cada robô é responsável por verificar a existência ou ausência de colisões na sua rota. Esta verificação tem em consideração apenas um pequeno traçado da rota, ao invés das poses todas até ao ponto de destino. Quando detetado algum conflito, tal é comunicado ao servidor central, sendo este responsável pela tomada de decisões da frota, mandando o robô avançar ou parar consoante o tipo de conflito detetado e a sua prioridade em relação aos restantes robôs da frota. O sistema foi implementando num ambiente dinâmico. Para o planeamento de caminhos entre dois pontos, e após uma análise a alguns planeadores, optou-se pelo algoritmo de busca Híbrido A*. Utilizando este algoritmo de busca foi possível encontrar, de forma rápida, caminhos em ambientes de elevada dimensão e complexidade. Sendo também possível a sua utilização em ambientes com múltiplos robôs, permitindo que cada robô planeie a sua rota de forma independente, evitando, simultaneamente, colisões com os restantes robôs. Para além disso, este algoritmo também se mostrou capaz de lidar com ambientes em mudança e incorporar novas informações em tempo real.

This dissertation project addresses the problem of coordinating a fleet of autonomous vehicles in intralogistics environments, where the environment is known a priori with static and dynamic obstacles detected by the robot sensor readings. To achieve coordination is required to accomplish the following aspects: communication, task assignment, collision avoidance, path planning, fleet management, safety protocols, and flexibility. A centralized approach was implemented, that is, the robots constituting the fleet communicate with a component responsible for making decisions. Each robot was responsible for checking for the existence or absence of collisions on its route. This check considers only a short stretch of the route, rather than all the poses up to the destination point. When a conflict is detected, it is communicated to the central server, which is responsible for making fleet decisions, ordering the robot to move forward or stop depending on the type of conflict detected and its priority in relation to the other robots in the fleet. The system was implemented in a dynamic environment. Regarding the path planning between two points, and after a brief analysis of some planners, the A* Hybrid search algorithm was chosen. Using this search algorithm, it was possible to quickly find paths in high-dimensional and complex environments. It is also possible to use it in multi-robot environments, allowing each robot to plan its route independently while avoiding collisions with other robots. In addition, this algorithm has also proven capable of handling changing environments and incorporating new information in real time.