Uma Heurística para o Problema de Patrulhamento de Ambientes com múltiplos Agentes

Resumo

Neste trabalho é proposto uma heurística para um problema de vigilância com múltiplos agentes em ambientes representados por meio de um grafo. Os n´os do grafo representam os locais a serem visitados em cada ciclo. Um ciclo ´e finalizado quando todas os locais são observados pelo menos uma vez por um agente. Deseja-se determinar as trajetórias dos agentes de modo que a duração de cada ciclo seja mínimo, que os agentes sejam incentivados a se movimentarem o máximo possível. Um modelo de programação inteira mista foi proposto bem como uma heurística baseada na decomposição do modelo. Alguns cenários foram gerados e usados para testar a abordagem heurística e os resultados obtidos mostram seu bom desempenho quando comparado a um solver comercial de otimização utilizado.