FenixEdu™

Dissertação

{en_GB=Task Allocation Algorithms for a Cooperative Drone Parcel Delivery System} {} EVALUATED

Detalhes: {pt=Nas últimas décadas o tema de sistemas multi-agente e mais precisamente sistemas multi-robot tem vindo a ser amplamente estudado com o aumento não só de aplicações práticas na vida diária de tais sistemas como também pelo aumento constante de possibilidades com o avanço da tecnologia. Empresas privadas e entidades públicas têm vindo a encontrar nos veículos aéreos não tripulados, também conhecidos como drones, uma solução para os problemas de logística e sistemas de distribuição em cidades modernas e também para missões de salvamento ou de vigilância. Esta tese enquadra-se num projeto de investigação no âmbito de sistemas de distribuição através de drones, e consiste num estudo de algoritmos de optimização para a alocação de tarefas numa equipa de drones para transporte de encomendas. Com este fim, vários algoritmos são estudados, com enfoque no recente algoritmo Task Sequential Greedy Algorithm. Este algoritmo foi modificado para inclusão de limitação de bateria dos agentes, possibilidade de recarregamento, com objectivos parametrizáveis pelo utilizador, podendo conjugar tempo e energia gasta. O algoritmo foi também modificado para a implementação de manobras de relay, onde, numa manobra em voo, a encomenda pode passar de um drone para outro. Um algoritmo de optimização binária foi implementado para a decisão de onde e quando as manobras de relay são mais benéficas para o sistema. Casos de estudo específicos são apresentados, analisando uma aplicação real do trabalho realizado numa perspectiva do utilizador do algoritmo desenvolvido, bem como uma detalhada explicação da implementação destes algoritmos e das suas modificações. , en=Multi-agent and multi-robot systems have been being widely studied in the last decades, not only due to the practical applications in real quotidian life, but also due to the constant growth of application possibilities arising with technological advances. Both private companies and public entities have found in drones a viable solution for logistic and delivery problems of modern cities and also for search and rescue and surveillance missions. This thesis, developed in the context of a research project regarding drone parcel transportation systems, addresses a study of optimization algorithms for task allocation in a fleet of drones with the goal of parcel delivery. With this goal, many algorithms are discussed, focusing on the study and implementation of Task Sequential Greedy Algorithm. This algorithm was modified to include drone battery limitations and recharge possibilities with a configurable objective function giving the user the possibility of combining and tuning both time and energy consumed. It was also modified to include relays, where parcels can change carrier during an in-flight maneuver. A binary optimization algorithm is implemented to decide where and when the relay maneuvers are beneficial to the system. Specific case studies are presented, analyzing a real application of the generated algorithm from a user point of view as well as a meticulous and detailed explanation of all decisions made and of the implementation of the algorithm and its modifications.}
Keywords: {pt=Optimização, Sistemas de transporte por drones, Alocação de tarefas, Manobras de relay, Sistemas cooperativos, en=Optimization, Drone transportation systems, Task allocation, Relay maneuvers, Cooperative systems}

Discussão: dezembro 15, 2020, 11:0