Patrulha temporal: taxonomia, métricas e novas soluções.

Abstract

Nos últimos anos, houve um aumento singificativo do interesse por Problemas de Patrulha Multiagente (MAP). No entanto, existem algumas barreiras que impedem o amadurecimento das pesquisas. A principal barreira é a falta de consenso sobre a definição padrão desse problema, o que torna os resultados de trabalhos diferentes incomparáveis em diversos níveis. Por isso, propomos uma formulação chamada de Patrulha Temporal Multiagente (MATP), que unifica muitas das formulações de MAP que assumem conhecimento do mundo mais restrito. Com base na MATP, fazemos uma análise teórica profunda de medidas de desempenho antigas e novas e de como elas se relacionam com certos requisitos de desempenho. Também propomos uma Taxonomia da MATP que separa casos da MATP que são significativamente diferentes entre si. Essa taxonomia também foi usada para criar um mapeamento dos casos mais e menos estudados, servindo como guia para as próximas pesquisas. Também propomos uma nova família de estratégias para MATP, chamadas de estratégias gravitacionais, inspiradas na lei de gravitação da Física. Por fim, propomos um benchmark baseado na MATP, que foi usado para comparar as novas estratégias com outras estratégias relevantes da literatura.