Genetic Algorithms Applied to Robotic Group Formation and Coordination

• Gustavo Pessin USP
• Fernando Osório USP

Abstract

O objetivo deste artigo é detalhar o modelo, a implementação e a avaliação da eficiência de Algoritmos Genéticos aplicados à formação e atuação de grupos robóticos. A atuação do grupo robótico é realizada sobre um desastre ambiental do tipo incêndio florestal, cujo desenvolvimento do simulador é descrito em [Pessin et al. 2007a]. Realizamos experiências com diferentes estruturas de cromossomos e diversas variações de parâmetros. Descrevemos neste artigo as experiências realizadas, detalhando tanto os conjuntos de parâmetros que nos permitiram obter resultados positivos como os negativos. Os resultados das simulações demonstram que com um conjunto adequado de parâmetros é possível obter posições satisfatórias para atuação de um grupo robótico; sendo esta solução possível de aplicação em atividades similares.

References

Balch, T. and Arkin, R. C. (1998). “Behavior-based formation control for multirobot teams”. IEEE Transactions on Robotics and Automation, 14(6):926–939.

Bekey, G. A. (2005). Autonomous Robots: From Biological Inspiration to Implementation and Control. The MIT Press, Cambridge, Massachusetts, USA.

Boeing (2007). “Boing company website”, [link], Maio.

Burchardt, H. and Salomon, R. (2006). “Implementation of path planning using GA on mobile robots”. In IEEE Congress on Evolutionary Computation, pages 1831–1836.

Carvalho, A. C. F., Braga, A. P., and Ludermir, T. B. (2003). Sistemas Inteligentes: Fundamentos e Aplicações, chapter Computação Evolutiva, pages 225–248. Manole.

Costa, E. R., Gomes, M. L., and Bianchi, R. A. C. (2003). “Um mini robô móvel seguidor de pistas guiado por visão local”. In Anais do VI SBAI, pages 710–715.

Darpa (2007). “Grand challenge website”, [link], Maio.

Dassault (2007). “Dassault company website”, [link], Maio.

Dejong, K. (1975). The analysis and behaviour of a class of genetic adaptive systems. PhD thesis, University of Michigan, USA.

Demeter (2007). “Demeter terrain engine”, [link], Março.

Dias, M. B., Zlot, R., Kalra, N., and Stentz, A. (2006). “Market-based multirobot coordination: a survey and analysis”. Proceedings of the IEEE, 94:1257–1270.

Dorigo, M., Trianni, V., Sahin, E., Gro, R., Labella, T., Baldassarre, G., Nolfi, S., Deneubourg, J., Mondada, F., Floreano, D., and Gambardella, L. (2004). “Evolving self-organizing behaviors for a swarm-bot”. Autonomous Robots, 17:223–245.

Dudek, G. and Jenkin, M. (2000). Computational Principles of Mobile Robotics. The MIT Press, Cambridge, London, UK.

Go, J., Browning, B., and Veloso, M. (2004). “Accurate and flexible simulation for dynamic, vision-centric robots”. In Proceedings of 3th AAMAS, New York.

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Professional, Boston, MA, USA.

Gonzalez, J. A. and Marengoni, M. (2005). “Controle baseado em algoritmo genético para um braço robótico móvel”. In Anais do VII SBAI, São Luis, MA, Brasil.

Heinen, M. R. (2007). Controle Inteligente do Caminhar de Robôs Móveis Simulados. Master’s thesis, Universidade do Vale do Rio dos Sinos (Unisinos).

Holland, J. (1975). Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, Michigan, USA.

IdMind (2007). “Projecto RAPOSA”, [link], Setembro.

Macedo, A. R. M., Macedo, A. R. L., and Duarte, J. B. F. (2007). “Robótica aplicada ao combate a incidentes”. Revista TN Petróleo, (53):108–113.

Michalewicz, Z. (1996). Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, New York, USA.

Mitchell, M. (1996). An Introduction to Genetic Algorithms. The MIT Press.

Mondada, F., Gambardella, L. M., Floreano, D., and Dorigo, M. (2005). “The cooperation of swarm-bots: physical interactions in collective robotics”. IEEE Robotics and Automation Magazine, 12:21–28.

Osagie, P. (2006). Distributed Control for Networked Autonomous Vehicles. Master’s thesis, KTH CSC, Royal Institute of Technology, Sweden.

OSG (2007). “Open Scene Graph Community”, [link], Março.

PennState (2007). “Mobile Robotics Program”, [link], Junho.

Pessin, G. (2008). Evolução de Estratégias e Controle Inteligente em Sistemas Multi-Robóticos Robustos. Master’s thesis, Universidade do Vale do Rio dos Sinos, Disponível em [link].

Pessin, G., Osório, F. S., and Musse, S. R. (2008). “Simulação virtual da evolução de estratégias e do controle inteligente em sistemas multi-robóticos”. In Anais do X SVR.

Pessin, G., Osório, F. S., Musse, S. R., Nonnenmacher, V., and Ferreira, S. S. (2007a). “Ambiente virtual para simulação de robôs móveis inteligentes aplicados no combate de incêndios florestais”. Revista Disciplinarum Scientia.

Pessin, G., Osório, F. S., Musse, S. R., Nonnenmacher, V., and Ferreira, S. S. (2007b). “Simulação virtual de agentes autônomos para a identificação e controle de incêndios em reservas naturais”. In Anais do IX SVR, pages 236–245, Petrópolis, RJ, Brasil.

Sdl (2007). “Simple DirectMedia Layer”, [link], Janeiro.

Smith, R. (2007). “Open Dynamics Engine”, [link], Janeiro.

Trinity (2007). “Firefighting robot contest”, [link], Setembro.

Wall, M. (2007). “Genetic Algorithms Library”, [link], Maio.

Yamaguchi, H. “Adaptive formation control for distributed autonomous mobile robot-groups”. In IEEE Conference on Robotics and Automation, pages 2300–2305.

Zhao, Y. and Collins, E. G. (2005). “Robust automatic parallel parking in tight spaces via fuzzy logic”. Robotics and Autonomous Systems, 51:111–127.

Zhou, Y. (2005). An Area Exploration Strategy Evolved by Genetic Algorithm. Master’s thesis, University of Georgia.