Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/5277| Título: | Mecanismo de leilão descentralizado para atribuição de tarefas colaborativas em um sistemas multirrobô |
| Título(s) alternativo(s): | Decentralized auction mechanism for collaborative task assignment in a multirobot system |
| Autor(es): | Nakashima, Renan Taizo |
| Orientador(es): | Arruda, Lucia Valeria Ramos de |
| Palavras-chave: | Robôs - Sistemas de controle Robôs - Sistemas de controle Robôs móveis - Controle automático Robôs móveis - Controle automático Sistemas multiagentes Sistemas multiagentes Leilões - Modelos matemáticos Leilões - Modelos matemáticos Algoritmos Algoritmos Processamento eletrônico de dados - Processamento distribuído Processamento eletrônico de dados - Processamento distribuído Sistemas de controle inteligente Sistemas de controle inteligente Robots - Control systems Robots - Control systems Mobile robots - Automatic control Mobile robots - Automatic control Multi-agent systems Multi-agent systems Auctions - Mathematical models Auctions - Mathematical models Algorithms Algorithms Electronic data processing - Distributed processing Electronic data processing - Distributed processing Intelligent control systems Intelligent control systems |
| Data do documento: | 22-Set-2020 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Curitiba |
| Citação: | NAKASHIMA, Renan Taizo. Mecanismo de leilão descentralizado para atribuição de tarefas colaborativas em um sistemas multirrobô. 2020. Dissertação (Mestrado em Engenharia Elétrica e Informática Industrial) - Universidade Tecnológica Federal do Paraná, Curitiba, 2020. NAKASHIMA, Renan Taizo. Mecanismo de leilão descentralizado para atribuição de tarefas colaborativas em um sistemas multirrobô. 2020. Dissertação (Mestrado em Engenharia Elétrica e Informática Industrial) - Universidade Tecnológica Federal do Paraná, Curitiba, 2020. |
| Resumo: | Os sistemas multirrobôs têm recebido atenção considerável nos últimos anos, devido à sua eficiência para resolver problemas complexos através da divisão de tarefas com atuação colaborativa. Esta classe de sistema robótico encontra aplicações que vão desde atividades cotidianas a atividades críticas e de alto risco, como busca por sobreviventes de desastres naturais ou vigilância e monitoramento de ambientes. A eficiência de tais sistemas depende diretamente da qualidade do compartilhamento e alocação de tarefas entre os agentes que o compõem. Este trabalho apresenta o desenvolvimento de uma solução inspirada em paradigmas de mercado, a partir de um mecanismo de leilão, para o problema da alocação de tarefas em um sistema multirrobô. O sistema proposto considera que as tarefas possuem pré-requisitos, podendo exigir dos robôs uma ou mais habilidades, e só podem ser concluídas se todos os pré-requisitos forem atendidos. Cada robô pode possuir somente uma única habilidade, de forma que os robôs devem formar coalizões para concluir tarefas que exigem mais de uma habilidade. O sistema possui a premissa de ser totalmente distribuído e descentralizado. O processamento computacional exigido para coordenar um leilão é distribuído entre os robôs em rodadas, onde cada robô deverá atuar como leiloeiro em seu turno. O cálculo do valor dos lances é realizado em função de um conjunto de fatores, os quais ponderam a importância de parâmetros do sistema, como distribuição de tarefas e distância do recurso leiloado. O sistema foi validado através de simulações computacionais em um cenário de busca e resgate, com ambiente parcialmente desconhecido, onde os robôs foram equipados com mecanismos de sensoreamento, mapeamento, exploração baseada em fronteiras, planejamento de trajetória, controle de navegação e desvio de obstáculos. O primeiro grupo de resultados valida o funcionamento do mecanismo de leilão de forma isolada em dois cenários distintos, variando o número de tarefas individuais, colaborativas e de robôs presentes no ambiente. O segundo grupo de resultados valida o funcionamento do sistema como um todo, de forma integrada. Os resultados demonstram um desempenho satisfatório do mecanismo proposto, permitindo que os robôs atuem colaborativamente na resolução do problema. Ainda, confirmou-se que a performance do sistema é parametrizável em função de constantes pré-definidas. Por fim, as simulações sugerem que o mecanismo de leilão é escalável. No entanto, mais testes são necessários para confirmar, efetivamente, a escalabilidade do sistema. Os sistemas multirrobôs têm recebido atenção considerável nos últimos anos, devido à sua eficiência para resolver problemas complexos através da divisão de tarefas com atuação colaborativa. Esta classe de sistema robótico encontra aplicações que vão desde atividades cotidianas a atividades críticas e de alto risco, como busca por sobreviventes de desastres naturais ou vigilância e monitoramento de ambientes. A eficiência de tais sistemas depende diretamente da qualidade do compartilhamento e alocação de tarefas entre os agentes que o compõem. Este trabalho apresenta o desenvolvimento de uma solução inspirada em paradigmas de mercado, a partir de um mecanismo de leilão, para o problema da alocação de tarefas em um sistema multirrobô. O sistema proposto considera que as tarefas possuem pré-requisitos, podendo exigir dos robôs uma ou mais habilidades, e só podem ser concluídas se todos os pré-requisitos forem atendidos. Cada robô pode possuir somente uma única habilidade, de forma que os robôs devem formar coalizões para concluir tarefas que exigem mais de uma habilidade. O sistema possui a premissa de ser totalmente distribuído e descentralizado. O processamento computacional exigido para coordenar um leilão é distribuído entre os robôs em rodadas, onde cada robô deverá atuar como leiloeiro em seu turno. O cálculo do valor dos lances é realizado em função de um conjunto de fatores, os quais ponderam a importância de parâmetros do sistema, como distribuição de tarefas e distância do recurso leiloado. O sistema foi validado através de simulações computacionais em um cenário de busca e resgate, com ambiente parcialmente desconhecido, onde os robôs foram equipados com mecanismos de sensoreamento, mapeamento, exploração baseada em fronteiras, planejamento de trajetória, controle de navegação e desvio de obstáculos. O primeiro grupo de resultados valida o funcionamento do mecanismo de leilão de forma isolada em dois cenários distintos, variando o número de tarefas individuais, colaborativas e de robôs presentes no ambiente. O segundo grupo de resultados valida o funcionamento do sistema como um todo, de forma integrada. Os resultados demonstram um desempenho satisfatório do mecanismo proposto, permitindo que os robôs atuem colaborativamente na resolução do problema. Ainda, confirmou-se que a performance do sistema é parametrizável em função de constantes pré-definidas. Por fim, as simulações sugerem que o mecanismo de leilão é escalável. No entanto, mais testes são necessários para confirmar, efetivamente, a escalabilidade do sistema. |
| Abstract: | Multi-Robot Systems are receiving considerable attention during the last years due their efficiency in solving complex problems through task sharing and collaborative assignments. This class of systems have several different applications, ranging from daily to critical and highrisk activities, for example search and rescue of survivors in natural disaster scenarios and site vigilance. The efficiency of such systems relies on the quality of the task allocation among the agents. This works presents the development of a market-inspired solution by applying an auction mechanism to solve the multi-robot task allocation problem. The proposed system considers that each task requires one or more robot’s skills in order to be complete. Since each robot can only have one single skill, the robots must form coalitions to complete tasks that require multiple skills. The system is fully distributed and decentralized. The computation processing required to coordinate an auction is distributed among the robots in turns, in which each robot should perform an auction in its turn. The calculation for the bidding values is performed upon a set of factors that weight the importance of some characteristics of the system, such as task allocation and distance to the auctioned resource. The proposed system is verified through simulations in partially unknown search and rescue scenarios, where each robot is also equipped with sensing, mapping, frontier-based exploration, mission planning, navigation control and deviation mechanisms. The results are split in two parts. The first part isolates the auction mechanism to evaluate its performance by changing the number of robots, collaborative and individual tasks in two distinct scenarios. The second part validates the system as a whole, by integrating the auction mechanism with the remaining mechanisms. The results show that the performance is satisfactory, allowing the robots to cooperate in solving the task allocation problem. It is also indicated that the system performance can be configurable regarding some predefined constants that can be chosen. Lastly, the results also suggest that the proposed auction mechanism is scalable. However, further testing is required to confirm the scalability of the system. Multi-Robot Systems are receiving considerable attention during the last years due their efficiency in solving complex problems through task sharing and collaborative assignments. This class of systems have several different applications, ranging from daily to critical and highrisk activities, for example search and rescue of survivors in natural disaster scenarios and site vigilance. The efficiency of such systems relies on the quality of the task allocation among the agents. This works presents the development of a market-inspired solution by applying an auction mechanism to solve the multi-robot task allocation problem. The proposed system considers that each task requires one or more robot’s skills in order to be complete. Since each robot can only have one single skill, the robots must form coalitions to complete tasks that require multiple skills. The system is fully distributed and decentralized. The computation processing required to coordinate an auction is distributed among the robots in turns, in which each robot should perform an auction in its turn. The calculation for the bidding values is performed upon a set of factors that weight the importance of some characteristics of the system, such as task allocation and distance to the auctioned resource. The proposed system is verified through simulations in partially unknown search and rescue scenarios, where each robot is also equipped with sensing, mapping, frontier-based exploration, mission planning, navigation control and deviation mechanisms. The results are split in two parts. The first part isolates the auction mechanism to evaluate its performance by changing the number of robots, collaborative and individual tasks in two distinct scenarios. The second part validates the system as a whole, by integrating the auction mechanism with the remaining mechanisms. The results show that the performance is satisfactory, allowing the robots to cooperate in solving the task allocation problem. It is also indicated that the system performance can be configurable regarding some predefined constants that can be chosen. Lastly, the results also suggest that the proposed auction mechanism is scalable. However, further testing is required to confirm the scalability of the system. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/5277 |
| Aparece nas coleções: | CT - Programa de Pós-Graduação em Engenharia Elétrica e Informática Industrial |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| leilaodescentralizadosistemamultirrobo.pdf | 13,98 MB | Adobe PDF |  Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.