SISTEMAS MULTI-AGENTES COOPERATIVOS INSPIRADOS EM ROBÓTICA DE ENXAME MÁRCIO MENDONÇA 1, LÚCIA VALÉRIA RAMOS DE ARRUDA 1, IVAN ROSSATO CHRUN 1, JOAO PAULO LIMA SILVA 1,2 DE ALMEIDA 1. Programa de PG em Engenharia Elétrica e Informática Industrial (CPGEI) Universidade Tecnológica Federal do Paraná, campus Curitiba. Av. Sete de Setembro, 3165, CEP 80230-901, Curitiba, Paraná, Brasil. E-mails: [email protected], [email protected]; [email protected]. 2. Instituto Federal de Educação, Ciência e Tecnologia do Paraná (IFPR), campus Jacarezinho. Avenida Doutor Tito, s/n, Jardim Panorama, CEP 86400-000, Jacarezinho, Paraná, Brasil. E-mail: [email protected] Abstract This work presents a cooperative architecture for autonomous agents based on dynamic fuzzy cognitive maps, an evolution of fuzzy cognitive maps. This architecture is used to develop an autonomous navigation system for mobile robots, which has capacity for learning, self-adaptation and behavior management. The developed navigation system adopts a multiagent approach, based on Brooks’subsumption architecture, which allows hierarchical management of actions and parallel processing. Reinforcement learning is used to self-tune the system allowing self-adaptability. Bio-inspired strategies based on ant’s behaviour and memory navigation are also used for communication between agents. The strategies are simulated and confronted in a virtual environment. Keywords Dynamic Cognitive Maps; Cooperative Autonomous Agents; Swarm Robotics; Multi-agent Systems. 1 Introdução Em aplicações da robótica, muitas são as situações em que agentes são submetidos às condições em que não há a viabilidade de interferência humana, devido a fatores de risco. Dentre tais condições, destaca-se, por exemplo, a necessidade de locomoção de agentes em ambientes nocivos ou em locais de grande extensão contendo infraestruturas e/ou recursos críticos que devem ser protegidos (MENDONÇA, ARRUDA e NEVES-Jr., 2014) . Desse modo, torna-se necessário desenvolver sistemas robóticos computacionalmente distribuídos e com capacidade de colaboração inteligente, como proposto na teoria de sistemas multi-agentes. Por outro lado, sabe-se que as técnicas embasadas em Inteligência Artificial, em especial sistemas fuzzy possuem diferentes áreas de aplicações (ALCALA-FDEZ; ALONSO, 2015), e, de uma forma específica, as aplicações de sistemas inteligentes fuzzy nas áreas de navegação robótica autônoma estão em uma fase ascendente (PAULOS et al, 2015). Russel e Norvig (1995) definem um sistema autônomo como um sistema capaz de desenvolver tarefas complexas com um grau de sucesso elevado. Por exemplo, a geração de trajetórias de um único robô requer que o sistema autônomo seja capaz de aprender on-line uma estratégia de navegação por meio de interações com o ambiente proposto (MENDONÇA, ARRUDA e NEVES-Jr., 2012). A geração de trajetórias para múltiplos robôs interagindo em um único ambiente e com tarefas semelhantes ou distintas torna-se então uma tarefa mais complexa e de difícil implementação. Neste contexto, uma área de pesquisa emergente em navegação autônoma móvel se estende aos conceitos que envolvem o tema de enxame de robôs, do inglês Swarm Robotics. Na área de enxame de robôs, o termo ''inteligência coletiva'' refere-se a um comportamento coletivo que pode ser considerado a partir da combinação entre agentes que possuem uma dinâmica relativamente simples, cada um agindo de forma autônoma (BRAMBILLA et al, 2013), (ESPELOSIN et al, 2012) e (TAN; ZHENG, 2013). De uma forma geral, os sistemas autônomos dotados de inteligência coletiva são totalmente distribuídos, auto-organizável e inspirados em comportamento social de colônias de insetos e/ou de outros animais (PESSIN et al, 2010). Os mapas cognitivos fuzzy (Fuzzy Cognitive Maps - FCM), são uma forma alternativa de representar o conhecimento heurístico de vários especialistas sobre um sistema, que usam o formalismo matemático de grafos (KOSKO, 1986), em que as variáveis envolvidas são variáveis fuzzy. De uma forma geral, FCM pode ser considerado como um tipo de rede ou grafo fuzzy cognitivo, o qual inicialmente é desenvolvido pela aquisição de conhecimento de diversos especialistas, mas também pode ser treinado por diversas técnicas supervisionadas e/ou não-supervisionadas (PAPAGEORGIOU et al, 2006). Além da abordagem clássica dos FCMs, existem algumas variações desta técnica que possuem características específicas de acordo com as aplicações (PAPAGEORGIOU; SALMERON, 2013). Neste trabalho, utiliza-se um mapa cognitvo fuzzy dinâmico (DFCM), do inglês Dynamic Fuzzy Cognitive Maps, proposto em (MENDONÇA, ARRUDA e NEVES-Jr., 2014) no desenvolvimento de um sistema autônomo de navegação de um enxame de robôs em busca de alvos. Os agentes considerados possuem a capacidade de aprendizado, sintonia on-line e habilidades de auto-adaptação. Para isso, uma abordagem descentralizada é implementada, em que cada robô possui um controlador DFCM independente capaz de realizar a inferência em função da informação compartilhada (memória de tráfego). O compartilhamento da informação é efetuado em função da implementação do ferormônio artificial. Este trabalho está estruturado da seguinte forma: na seção 2 são apresentados os principais conceitos acerca do tema de FCM. Em seguida, na seção 3 o DFCM é desenvolvido em duas versões distintas para a aplicação proposta. Por fim, nas seções 4 e 5 são apresentadas as análises dos resultados obtidos e as conclusões do trabalho, respectivamente. representa uma variável fuzzy relacionada com a causalidade entre os conceitos; cada conceito representa uma característica do sistema a ser modelado. Um exemplo de um FCM é dado na Figura 1. A inferência ou evolução dos conceitos de um FCM é efetuada após várias iterações, através da equação (2) (STYLIOS; GROUMPOS, 2004). A variável j representa o contador das iterações, n é o número de nós do grafo, w(i,j) é o peso do arco que conecta o conceito Cj ao conceito Ci, Ai (Ai-anterior) é o valor do conceito Ci na iteração atual (anterior) e, a função f pode ser representada por um comportamento do tipo sigmoide, conforme é exemplificado na equação (3). Resumidamente essas duas equações representam a inferência dos FCMs. 2 Mapas Cognitivos Fuzzy Mapas cognitivos foram inicialmente apresentados por Axelrod (1976) com o intuito de expressar as relações de causa-efeito entre conceitos descrevendo um assunto, através de um modelo matemático baseado em grafos e operações matriciais. Tal modelo matemático foi adaptado para a inclusão de incertezas, por meio da lógica fuzzy, por Kosko (1986). A partir desse fato, os FCMs têm ocupado uma visível posição em modelagem fuzzy como um modelo de grafo orientado que descreve as relações entre conceitos (PEDRYCZ; HOMENDA, 2013) de um sistema qualquer e, vem sendo considerado em muitas áreas de aplicações com algumas variações específicas na estrutura inicialmente proposta por Kosko (1986). De acordo com a sua implementação, um FCM pode ser visto como um grafo fuzzy, ou como uma Rede Neural Artificial, ou ainda como um tipo de Rede Semântica, entre outras interpretações (PAPAGEORGIOU, 2014). A representação de conhecimentos por meio de um FCM é realizada de forma simbólica, na qual são utilizados conceitos para ilustrar diferentes comportamentos dinâmicos, de forma a integrar a experiência de vários especialistas na construção de um mesmo modelo. Alguns exemplos de áreas de aplicações de FCMs são: controle de processos (STYLIOS; GROUMPOS, 2004); robótica (MOTLAGH, 2012); serie temporal (HOMENDA; JASTRZEBSKA; PEDRYCZ, 2014), navegação autônoma (VASCAK; MADARÁSZ, 2010); entre outras áreas. Um FCM pode ser considerado um grafo direcionado acíclico, em que: os nós são conceitos linguísticos (conjuntos fuzzy); cada nó é associado com outros por meio de arcos com um peso que Figura 1. FCM inicial do controlador Ai f f n j 1 A x j w ji Aianterior 1 1 e x (1) (2) De acordo com as equações acima, alguns autores argumentam que os FCMs não estão aptos a representar sistemas dinâmicos reais uma vez que apenas expressam relações causais simétricas e monotônicas. Além disto, a precisão e robustez do modelo estão associadas ao cálculo correto da matriz de pesos, que pode variar de acordo com características especificas da aplicação ou pela ocorrência de eventos. Como solução, várias abordagens têm sido propostas para conferir aos FCMs habilidades de modelar aspectos temporais presentes nos sistemas reais (Mendoça et al, 2013). A abordagem adotada neste artigo é a mesma proposta por Acampora e Loia (2011) e aplicada em (MENDONÇA et al, 2013) em que um mapa cognitivo fuzzy dinâmico (DFCM) é um FCM no qual os conceitos, as relações causais entre eles e os efeitos associados a elas são variantes no tempo. Em especial, adotam-se os mesmos tipos de conceitos e relações apresentados em (MENDONÇA, et al., 2013). 3 Mapas Cognitivos Fuzzy Dinâmicos O desenvolvimento de um modelo DFCM tem por base o exposto em Mendonça et. al (2013), e para aplicação em estudo resultou no DFCM proposto na figura 1. Inicialmente, identificou-se 3 três entradas (SeE, SeD e SeF) relacionadas com a descrição do ambiente (presença de obstáculos à esquerda, à direita ou a frente do agente) e 3 saídas (Saída Esq, Saída Frente e Saída Dir.) que descrevem os movimentos do agente: vire à esquerda, vire à direita ou acelera ou desacelera para a frente. As três entradas assumem valores a partir de três sensores, localizados à esquerda, à direita e na frente do agente. As três decisões foram originalmente modeladas partir do entendimento da reação do agente em presença de obstáculo, ou seja, se o sensor de esquerda detecta um obstáculo, o veículo deve girar para a direita, se o obstáculo está à direita deve girar a esquerda e, quando se detecta um caminho livre de obstáculos, o agente deve seguir em linha reta com uma aceleração suave. Entretanto, em casos inesperados (um obstáculo em movimento cruza repentinamente a trajetória do agente) levando a iminência de colisão, um novo conceito (Colisão, figura 2) foi adicionado para incrementar a função “reverso” e favorecer o retrocesso do agente. Os conceitos de arquiteturas híbridas em robótica foram incluídos no modelo DFCM desenvolvido, a fim de combinar o uso de funções reativas e funções deliberativas para a resolução de problemas complexos (POLICASTRO; ROMERO; ZULIANI, 2007). Isso se deve porque o FCM mostrado na figura 1, apesar de ter algumas relações variantes no tempo (pesos pontilhados na figura 1) é totalmente reativo, ou seja, suas saídas são diretamente dependentes das suas entradas. Desse modo, a fim de compatibilizar as diversas tarefas do robô, a saber desviar de obstáculos e alcançar alvos, além de compartilhar memória de navegação e coleta de feromônios, dependo da estratégia empregada, foi implementada um hierarquia de comportamentos baseada na arquitetura de subsumpção de Brooks (1986). O DFCM da figura 2 tem funcionalidades de evitar colisões e de compartilhar memória de navegação, incorporando as funcionalidades de cooperação de informação e passo a passo ou robô a robô, de criação de landmarks (nesse caso, artificiais). De modo específico, as ações de controle realizadas por um robô em uma região antes da iminência de colisão é compartilhada com próximo agente (robô) e assim por diante. Esse compartilhamento de uma memória de navegação é realizado através da técnica de liberação de feromônio no caminho, utilizada em algoritmos de colônia de formigas (PAYTON, ESTKOWSKI e HOWARD, 2015). A deposição de feromônio e por conseguinte o compartilhamento de memória passa a ser otimizada com a evolução do enxame de robôs, amplificando assim a capacidade de inteligência coletiva do sistema proposto. Figura 2. DFCM: subsunção cooperativa (estratégia modificada). Na figura 2, os conceitos DXL e DXR que foram acrescentados ao DFCM da figura 1 processam a distância dos alvos, e, junto com as relações de seleção (WS4 e WS5) disparam o evento de busca de alvos. Já as relações WS1, WS2 e WS3 disparam a redução do efeito de “zig-zag” juntamente com os conceitos de fator de saída. Em ambas estratégias uma versão modificada no algoritmo de aprendizado por reforço Q-learning, (SUTTON; BARTO, 1998), com uma política de bonificação e punição por meio de regras heurísticas foi utilizado para uma sintonia dinâmica das relações causais (W1-W9) na figura 2. Maiores detalhes desse modelo adaptado podem ser conferidos no trabalho (MENDONÇA, 2011) e (MENDONÇA, et al.,2013). Já os conceitos de “Colisão” e de “Memória” são ativados por relações de seleção, que são regras simples na forma de “antecedente-consequente” (SEENTÃO) e que implicam em uma ou mais condições para a inclusão desses conceitos no modelo. Desse modo, o DFCM da figura 2 pode ser considerado um modelo cognitivo de estrutura mutável. As condições para o disparo dessas regras são em função da iminência de colisão (agente deve estar muito próximo a um obstáculo) representada no conceito de “Colisão”. Para o conceito memória de Navegação, em uma região de aproximadamente 40 passos (ponto crítico) antes de um obstáculo, o robô antecedente compartilha sua memória de navegação com o próximo robô que utiliza seus próprios sensores somados a 1% da memória compartilhada. Tais procedimentos objetivam otimizar a trajetória dos robôs por meio da técnica de liberação de feromônios utilizada em algoritmos de colônia de formigas. Nesse caso, há o intuito de desenvolver de forma dinâmica uma nova trajetória, sem a necessidade de o agente retroceder por conta de um obstáculo, cumprindo os objetivos de coleta de alvos e de desvio de obstáculos. Uma segunda estratégia de compartilhamento de memória foi realizada também através de DFCM. Do mesmo modo da primeira estratégia, o agente navega através do ambiente e deixa demarcações (feromônios artificiais) sobre o seu caminho tomado no ambiente, enquanto outro agente interpreta o feromônio para auxiliar em sua tomada de decisão. No entanto, a utilização ou não do feromônio é determinada pelo DFCM da figura 3 que substitui o conceito memória de navegação (em verde na figura 2). Este DFCM contém 3 novos conceitos: Feromônio Release (C10), ponderações (C12) e Detecção de feromônio (C11). Também duas novas relações de seleção são adicionadas, WS5 e WS6 (MENDONÇA et al., 2013). Além disto, os conceitos de entrada Se.E., Se.F. e Se.D. estão relacionados com o sensor esquerdo, com o sensor frontal e com o sensor direito, respectivamente, como no DFCM da figura 1. As linhas tracejadas pretas representam relações que somente são disparadas para selecionar o estado da DFCM. O conceito C10 gerencia os feromônios para serem liberados pelo agente, uma vez atendidos os critérios de seleção (WS5). O conceito C11 é uma variável de entrada auxiliar que detecta os feromônios deixados por outros agentes. 4 Resultados Um simulador em 2-D genérico desenvolvido no ambiente gráfico do MATLAB® foi desenvolvido para se demonstrar os resultados, e validar a proposta desenvolvida. As simulações foram realizadas em função de obstáculos em localizações semelhantes, de forma a induzir uma igualdade de condições. Adotou-se simbologias distintas para agentes e para obstáculos. Um exemplo de cenário é exposto por meio da Figura 4. Os resultados da primeira estratégia (algoritmo de deposição de feromônio convencional) convergiram em duas etapas, considerou-se que a primeira foi a passagem do primeiro agente, o qual compartilhou sua memória de navegação com o segundo agente. Os desempenhos do primeiro e segundo agente são mostrados nas Figuras 4 e 5, respectivamente. Observa-se na Figura 4 que houve a necessidade de frenagem e reversão, destacada por uma seta, enquanto que na passagem do segundo agente pelo mesmo ponto (figura 5) não houve esta necessidade. Figura 4. Cenário de simulação genérico. Figura 3. DFCM: subsunção cooperativa (estratégia inspirada em ACO). No entanto, o feromônio artificial auxilia no processo de tomada de decisões, antecipando manobras de desvio de obstáculos ou em alvos de captura. Um sistema de seleção entre os conceitos de C11 e C12 altera a relação causal de W12, referindo-se a sua intensidade, dada pela regra de seleção WS6. O conceito C12 é similar ao conceito de ponderação a partir da estratégia de partilha de trajetória. Este conceito interfere na informação adquirida por C5 e por C6 (ações de controle) e saídas da informação a partir da leitura de feromônio. Figura 5. Passagem do primeiro agente na estratégia 1. As simulações comprovam que o DFCM da figura 2 configura-se em um sistema multiagente suportando agentes capazes de realizar tarefas distintas e conflitantes (coletar alvos e desviar de obstáculos) e capazes de cooperar entre si. Os resultados de simulação comprovam ainda que ambas as estratégias de compartilhamento de memória atingiram o mesmo objetivo na segunda passagem do agente. Observou-se que mesmo com diferentes métodos, porém inspirados na mesma técnica de robótica coletiva, foi possível desenvolver a cooperação agentes através de FCMs. 5 Conclusões Figura 6. Passagem do segundo agente na estratégia 1. Figura 7. Passagem do primeiro agente na estratégia 2. Na Figura 7 é exposta a passagem do primeiro agente para a segunda estratégia (compartilhamento de memória através da DFCM da figura 3). Observase que existem uma forte semelhança com a passagem do primeiro agente na primeira estratégia. Na Figura 8 é exposto o desempenho do segundo agente em função do rastro de feromônio artificial deixado pelo agente anterior, para a segunda estratégia. Como antes, o segundo agente também superou o ponto crítico sem ocorrência de manobras de reversão. Figura 9. Passagem do segundo agente na estratégia 2. Este artigo apresentou uma proposta inicial de arquitetura híbrida para sistemas multiagetnes em robótica. Apesar de serem resultados iniciais, simulados em condições não reais, ou seja, sem a presença de ruídos ou de sinais fantasmas nos sensores de ultrassom, ou ainda de derrapagem do robô, é possível observar de forma satisfatória a cooperação entre os agentes, a autonomia e a capacidade de adquirir conhecimento para compensar dados incertos ou parciais. A utilização de um algoritmo de aprendizado por reforço, embora não explorado neste trabalho, permitiu uma melhor interação com ambiente, atenuando as incertezas das ações de baixo nível. Futuros trabalhos visam a utilização de cenários mais complexos, além da inserção de ruídos.. Desse modo, espera-se ter contribuído para a construção de sistemas cooperativos multi-agentes. Referências Bibliográficas Acampora, G., Loia, V., 2011. On the temporal granularity in fuzzy cognitive maps.IEEE Trans. Fuzzy Syst. 19, 1040–1057. Alcala-Fdez, J.; Alonso, J.M., (2015) A Survey of Fuzzy Systems Software: Taxonomy, Current Research Trends and Prospects, Fuzzy Systems, IEEE Transactions on , vol.PP, no.99, pp.1,1 Axelrod, R. (1976). Structure of Decision: The Cognitive Maps of Political. Elites. Princeton, NJ: Princeton Univ. Press. Brambilla, M; Ferrante, E.; Birattari, M. e Dorigo, M. (2013). Swarm robotics: a review from the swarm engineering perspective, Swarm Intelligence 7(1): 1-41. Brooks RA (1986) A robust layered control system for a mobile robot. IEEE J Robot Autom 2(1):14–23. Espelosin, J.; Acosta, L.; Hamilton, A., (2012). "Robot navigation in simulated pedestrian areas based on swarm intelligence," Control & Automation (MED), 2012 20th Mediterranean Conference on, vol., no., pp.140, 144, 3-6 July. Homenda, W.; Jastrzebska, A.; Pedrycz, W., (2014) Modeling time series with fuzzy cognitive maps, Fuzzy Systems (FUZZ-IEEE), 2014 IEEE International Conference on , vol., no., pp.2055,2062, 6-11 July 2014 Kosko, B. (1986). Fuzzy cognitive maps,” International Journal of Man-Machine Studies, vol. 24, pp. 65–75. Mendonça, M. (2011). Uma Contribuição ao Desenvolvimento de Sistemas Inteligentes Utilizando Redes Cognitivas Dinâmicas. Tese (Doutorado) – Programa de Pós-Graduação em Engenharia Elétrica e Informática Industrial, Universidade Tecnológica Federal do Paraná, Curitiba, PR. Mendonça, M., Arruda, LVR., Neves-Jr., F., (2012). Autonomous navigation system using event driven-fuzzy cognitive maps. Appl. Intell. 37, 175– 188. Mendonca, M., Angélico, B., Arruda, LVR., NevesJr.,F., (2013). A Subsumption Architecture to Develop Dynamic Cognitive Network-Based Models With Autonomous Navigation Application. Journal of Control, Automation and Electrical Systems, v. 24, p. 117-128. Mendonça, M., Arruda, LVR., Neves-Jr., F., (2014). Cooperative Autonomous Agents Based on Dynamical Fuzzy Cognitive Maps. In: Elpiniki L. Papageorgiou. (Org.). Intelligent Systems Reference Library. 1ed.Berlin: Springer Berlin Heidelberg, 2014, v. 54, p. 159-175. Motlagh, O.; Tang, S. H.; Ismail, N. and Ramli, A. R. (2012). An Expert Fuzzy Cognitive Map for Reactive Navigation of Mobile Robots. Fuzzy Sets and Systems, vol. 201, pp. 105–121 Papageorgiou, E. I.; Stylios, C. and Groumpos, P. (2006). Unsupervised Learning Techniques for Fine-Tuning Fuzzy Cognitive Map Causal Links. International Journal of Human-Computer Studies, vol. 64, pp. 727–743. Papageorgiou, E. I. and Salmeron, J. L. (2013). A Review of Fuzzy Cognitive Map research during the last decade. Accepted for publication in IEEE Transactions on Fuzzy Systems, vol. 21 no. 1, pp. 66-79. Papageorgiou, E. I. (2014) Fuzzy Cognitive Maps for Applied Sciences and Engineering from Fundamentals to Extensions and Learning Algorithms. Springer. Payton, D.; Estkowski, R. and Howard, M. (2015), Compound Behaviors in Pheromone Robotics, Robotics and Autonomous Systems, vol. 44, pp. 229–240. 2003. Paulos, J.; Eckenstein, N.; Tosun, T.; Jungwon Seo; Davey, J.; Greco, J.; Kumar, V.; Yim, M., (2015). Automated Self-Assembly of Large Maritime Structures by a Team of Robotic Boats,Automation Science and Engineering, IEEE Transactions on, vol.12, no.3, pp.958, 968, July 2015 Pedrycz, W. Homenda, W. (2013). From Fuzzy Cognitive Maps to Granular Cognitive Maps. Fuzzy Systems, IEEE Transactions on, vol.PP, no.99, pp.1, 1, 0 Pessin, G.; Osorio, F.; Hata, A.; Wolf, D. (2010). Intelligent control and evolutionary strategies applied to multirobotic systems, Industrial Technology (ICIT), 2010 IEEE International Conference on, Vina del Mar, Chile, pp. 1427-1432. Policastro, C.A.; Romero, R.A.F.; Zuliani, G., (2007). Robotic Architecture Inspired on Behavior Analysis, Neural Networks. IJCNN. International Joint Conference on, vol., no., pp.1482, 1487, 12-17 Aug. Russell, S. J. and Norvig, P. (1995). Artificial Intelligence: A Modern Approach. Englewood Cliffs: Prentice Hall. Romero, R. A. (2014) F. ET (ORGS.). ROBÓTICA MÓVEL. LTC, 07/2014. VITAL BOOK, Stylios, C. D. and Groumpos, P. P. (2004). Modeling Complex Systems Using Fuzzy Cognitive Maps. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, vol. 34 no. 1, pp. 155-162. Sutton, R.; Barto, (1998). A. Reinforcement learning: an introduction. Cambridge: MIT Press, 1998. Tan, Y. e Zheng, Z. (2013). Research advance in swarm robotics, Defence Technology 9(1): 1839. Vascak, J. and Madarász, L. (2010) Adaptation of Fuzzy Cognitive Maps – a Comparison Study. In: Acta Polytechnica Hungarica. v. 7, n 3, p. 109-122. Yeap, W. K.; Wong, C. K. and Schmidt, J. (2006). Initial Experiments with a Mobile Robot on Cognitive Mapping. In Proceedings of the 2006 International Symposium on Practical Cognitive Agents and Robots, Perth, Australia, November 27 – 28.