Roteamento Eficiente para Abordagem de Indivíduos em Ambientes com Obstáculos Baseado em Normas Sociais
Resumo
Esta tese propõe métodos de roteamento eficientes baseados em normas sociais para a abordagem sequencial de indivíduos e grupos em ambientes com obstáculos. Três soluções são apresentadas. Nossa primeira solução propõe uma modelagem inédita para o problema de indivíduos isolados em ambientes estáticos como um Problema Generalizado do Caixeiro Viajante (GTSP). A segunda expande a abordagem para grupos, modelando-a como um Problema de Orientação de Conjuntos (SOP) para maximizar recompensas sob restrições de recursos. A solução mais sofisticada aborda ambientes dinâmicos, integrando segmentação do espaço social, sistema de recompensas e o método da faixa elástica para navegação adaptativa, modelado como um Problema de Orientação Agrupado com Subgrupos (COPS). Os experimentos demonstram a eficácia de cada abordagem, com destaque para o equilíbrio da solução COPS entre eficiência computacional e adesão às normas sociais em cenários dinâmicos.
Palavras-chave:
roteamento, aproximação robô-humano, navegação social, ambientes dinâmicos, otimização de trajetória
Referências
Al-Wazzan, A., Al-Farhan, R., Al-Ali, F., and El-Abd, M. (2016). Tour-guide robot. In 2016 International Conference on Industrial Informatics and Computer Systems (CIICS), pages 1–5. IEEE.
Almeida, L. E. and Macharet, D. G. (2023). Clustered orienteering problem with subgroups.
Althaus, P., Ishiguro, H., Kanda, T., Miyashita, T., and Christensen, H. I. (2004). Navigation for human-robot interaction tasks. In IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA’04. 2004, volume 2, pages 1894–1900. IEEE.
Archetti, C., Carrabs, F., and Cerulli, R. (2018). The Set Orienteering Problem. European Journal of Operational Research, 267(1):264–272.
Ciolek, T. M. and Kendon, A. (1980). Environment and the spatial arrangement of conversational encounters. Sociological Inquiry, 50(3-4):237–271.
Dautenhahn, K., Walters, M., Woods, S., Koay, K. L., Nehaniv, C. L., Sisbot, A., Alami, R., and Siméon, T. (2006). How may i serve you? a robot companion approaching a seated person in a helping context. In Proceedings of the 1st ACM SIGCHI/SIGART conference on Human-robot interaction, pages 172–179.
Glover, F. (1986). Tabu search: A tutorial. Interfaces, 20(4):74–94.
Golden, B. L., Levy, L., and Vohra, R. (1987). The orienteering problem. Naval Research Logistics (NRL), 34(3):307–318.
Gross, H.-M., Boehme, H., Schroeter, C., Müller, S., König, A., Einhorn, E., Martin, C., Merten, M., and Bley, A. (2009). Toomas: interactive shopping guide robots in everyday use-final implementation and experiences from long-term field trials. In 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 2005–2012. IEEE.
Hall, E. T. (1966). The Hidden Dimension: Man’s Use of Space in Public and Private. The Bodley Head Ltd.
Helsgaun, K. (2015). Solving the equality generalized traveling salesman problem using the lin–kernighan–helsgaun algorithm. Mathematical Programming Computation, 7(3):269–287.
Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press, Cambridge, MA.
Kavraki, L. E., Svestka, P., Latombe, J.-C., and Overmars, M. H. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4):566–580.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598):671–680.
Koay, K. L., Syrdal, D. S., Ashgari-Oskoei, M., Walters, M. L., and Dautenhahn, K. (2014). Social roles and baseline proxemic preferences for a domestic service robot. International Journal of Social Robotics, 6(4):469–488.
Langedijk, R. M., Odabasi, C., Fischer, K., and Graf, B. (2020). Studying drink-serving service robots in the real world. In 2020 29th IEEE International Conference on Robot and Human Interactive Communication (RO-MAN), pages 788–793. IEEE.
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A., and Shmoys, D. B. (1985). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley.
Lawler, E. L. and Wood, D. E. (1966). The branch and bound method for discrete programming: An informal survey. Operations Research, 14(4):699–719.
Melo, F. and Moreno, P. (2022). Socially reactive navigation models for mobile robots. In 2022 IEEE International Conference on Autonomous Robot Systems and Competitions (ICARSC). IEEE.
Pěnička, R., Faigl, J., and Saska, M. (2019). Variable Neighborhood Search for the Set Orienteering Problem and its application to other Orienteering Problem variants. European Journal of Operational Research, 276(3):816–825.
Quinlan, S. and Khatib, O. (1993). Elastic bands: Connecting path planning and control. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pages 802–807. IEEE.
Rios-Martinez, J. (2013). Socially-aware robot navigation : combining risk assessment and social conventions.
Rosenberg-Kima, R., Koren, Y., Yachini, M., and Gordon, G. (2019). Human-robot-collaboration (hrc): social robots as teaching assistants for training activities in small groups. In 2019 14th ACM/IEEE International Conference on Human-Robot Interaction (HRI), pages 522–523. IEEE.
Sarathy, V., Arnold, T., and Scheutz, M. (2019). When exceptions are the norm. 8(3):1–21.
Shiomi, M., Kanda, T., Imai, M., Ishiguro, H., and Hagita, N. (2014). Towards a socially acceptable collision avoidance for a mobile robot navigating among pedestrians using a pedestrian model. International Journal of Social Robotics, 6(3):443–455.
Silva, A. D. G. and Macharet, D. G. (2019). Are You With Me? Determining the Association of Individuals and the Collective Social Space. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 313–318.
Su, Y. (2023). Artificial intelligence: The significance of tesla bot. Highlights in Science, Engineering and Technology, 39:1351–1355.
Takayama, L. and Pantofaru, C. (2009). Influences on proxemic behaviors in human-robot interaction. In 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5495–5502. IEEE.
Almeida, L. E. and Macharet, D. G. (2023). Clustered orienteering problem with subgroups.
Althaus, P., Ishiguro, H., Kanda, T., Miyashita, T., and Christensen, H. I. (2004). Navigation for human-robot interaction tasks. In IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA’04. 2004, volume 2, pages 1894–1900. IEEE.
Archetti, C., Carrabs, F., and Cerulli, R. (2018). The Set Orienteering Problem. European Journal of Operational Research, 267(1):264–272.
Ciolek, T. M. and Kendon, A. (1980). Environment and the spatial arrangement of conversational encounters. Sociological Inquiry, 50(3-4):237–271.
Dautenhahn, K., Walters, M., Woods, S., Koay, K. L., Nehaniv, C. L., Sisbot, A., Alami, R., and Siméon, T. (2006). How may i serve you? a robot companion approaching a seated person in a helping context. In Proceedings of the 1st ACM SIGCHI/SIGART conference on Human-robot interaction, pages 172–179.
Glover, F. (1986). Tabu search: A tutorial. Interfaces, 20(4):74–94.
Golden, B. L., Levy, L., and Vohra, R. (1987). The orienteering problem. Naval Research Logistics (NRL), 34(3):307–318.
Gross, H.-M., Boehme, H., Schroeter, C., Müller, S., König, A., Einhorn, E., Martin, C., Merten, M., and Bley, A. (2009). Toomas: interactive shopping guide robots in everyday use-final implementation and experiences from long-term field trials. In 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 2005–2012. IEEE.
Hall, E. T. (1966). The Hidden Dimension: Man’s Use of Space in Public and Private. The Bodley Head Ltd.
Helsgaun, K. (2015). Solving the equality generalized traveling salesman problem using the lin–kernighan–helsgaun algorithm. Mathematical Programming Computation, 7(3):269–287.
Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press, Cambridge, MA.
Kavraki, L. E., Svestka, P., Latombe, J.-C., and Overmars, M. H. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4):566–580.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598):671–680.
Koay, K. L., Syrdal, D. S., Ashgari-Oskoei, M., Walters, M. L., and Dautenhahn, K. (2014). Social roles and baseline proxemic preferences for a domestic service robot. International Journal of Social Robotics, 6(4):469–488.
Langedijk, R. M., Odabasi, C., Fischer, K., and Graf, B. (2020). Studying drink-serving service robots in the real world. In 2020 29th IEEE International Conference on Robot and Human Interactive Communication (RO-MAN), pages 788–793. IEEE.
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A., and Shmoys, D. B. (1985). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley.
Lawler, E. L. and Wood, D. E. (1966). The branch and bound method for discrete programming: An informal survey. Operations Research, 14(4):699–719.
Melo, F. and Moreno, P. (2022). Socially reactive navigation models for mobile robots. In 2022 IEEE International Conference on Autonomous Robot Systems and Competitions (ICARSC). IEEE.
Pěnička, R., Faigl, J., and Saska, M. (2019). Variable Neighborhood Search for the Set Orienteering Problem and its application to other Orienteering Problem variants. European Journal of Operational Research, 276(3):816–825.
Quinlan, S. and Khatib, O. (1993). Elastic bands: Connecting path planning and control. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pages 802–807. IEEE.
Rios-Martinez, J. (2013). Socially-aware robot navigation : combining risk assessment and social conventions.
Rosenberg-Kima, R., Koren, Y., Yachini, M., and Gordon, G. (2019). Human-robot-collaboration (hrc): social robots as teaching assistants for training activities in small groups. In 2019 14th ACM/IEEE International Conference on Human-Robot Interaction (HRI), pages 522–523. IEEE.
Sarathy, V., Arnold, T., and Scheutz, M. (2019). When exceptions are the norm. 8(3):1–21.
Shiomi, M., Kanda, T., Imai, M., Ishiguro, H., and Hagita, N. (2014). Towards a socially acceptable collision avoidance for a mobile robot navigating among pedestrians using a pedestrian model. International Journal of Social Robotics, 6(3):443–455.
Silva, A. D. G. and Macharet, D. G. (2019). Are You With Me? Determining the Association of Individuals and the Collective Social Space. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 313–318.
Su, Y. (2023). Artificial intelligence: The significance of tesla bot. Highlights in Science, Engineering and Technology, 39:1351–1355.
Takayama, L. and Pantofaru, C. (2009). Influences on proxemic behaviors in human-robot interaction. In 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5495–5502. IEEE.
Publicado
13/10/2025
Como Citar
SILVA, Aline F. F.; MACHARET, Douglas G..
Roteamento Eficiente para Abordagem de Indivíduos em Ambientes com Obstáculos Baseado em Normas Sociais. In: CONCURSO DE TESES E DISSERTAÇÕES EM ROBÓTICA - CTDR (DOUTORADO) - SIMPÓSIO BRASILEIRO DE ROBÓTICA E SIMPÓSIO LATINO-AMERICANO DE ROBÓTICA (SBR/LARS), 16. , 2025, Vitória/ES.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 61-72.
DOI: https://doi.org/10.5753/sbrlars_estendido.2025.248236.
