Made available in DSpace on 2014-06-12T15:56:22Z (GMT). No. of bitstreams: 2
arquivo2919_1.pdf: 1890307 bytes, checksum: a778a46df2372bc90f89174a0b49fdda (MD5)
license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5)
Previous issue date: 2008 / Patrulhar é o ato de andar ou viajar por uma área, em intervalos regulares, para
protegê-la ou supervisioná-la. Informalmente, uma boa estratégia de patrulhamento é
aquela que minimiza o tempo gasto entre duas visitas à mesma localização. Além de sua
aplicação prática, o Problema da Patrulha Multiagentes (PMA) é um problema didático,
pois compreende desde problemas computacionais simples, como a determinação do
menor caminho entre dois pontos em um território até problemas mais complexos
inerentes ao estudo de Sistemas Multiagentes (SMA). Para o estudo de SMAs, o PMA
mostra-se rico, pois envolve várias características relevantes de um SMA como
coordenação, comunicação, organização, negociação, conceitos de sociedades de
agentes, entre outros.
Em 2002, um trabalho pioneiro, realizado pelo grupo de Inteligência Artificial
do Centro de Informática da Universidade Federal de Pernambuco, propôs as primeiras
arquiteturas para o PMA e as avaliou empiricamente. Trabalhos posteriores propuseram
soluções mais sofisticadas, como a utilização de negociação e aprendizagem,
elaborando e avaliando uma maior quantidade de arquiteturas. Apesar dos trabalhos
empíricos realizados, uma abordagem teórica do PMA se fazia necessária para a
evolução na pesquisa do problema. Em cooperação com a Universidade Paris 6 na
França, um primeiro estudo teórico do PMA foi proposto por Yann Chavaleyre e este
motivou os resultados apresentados no nosso trabalho.
Nosso objetivo na presente dissertação é desenvolver estratégias de
patrulhamento e formalizar o PMA como problema de otimização. Mencionamos os
trabalhos relacionados ao PMA existentes na literatura, adicionando inclusive os
estudos mais recentes envolvendo estratégias de partições em grafos. Formalizamos o
PMA como um problema de otimização NP (NP-Optimization Problem - NPO) bem
como também exibimos uma prova de sua intratabilidade. Elaboramos e
implementamos estratégias de patrulhamento a partir de algoritmos de aproximação e
outras heurísticas para geração de partições conexas em grafo. Para o particionamento
dos territórios, utilizamos soluções para o Problema do k-Centros Capacitado e o
Problema das Partições Conexas Balanceadas. Implementamos também o algoritmo de
aproximação desenvolvido por Chavaleyre com base na geração de partições a partir da árvore geradora de peso mínimo dos grafos a serem patrulhados. Realizamos vários
experimentos no Simpatrol, simulador para sistemas multiagentes em tempo real,
desenvolvido neste projeto de mestrado em um trabalho conjunto com o aluno Daniel
Moreira. Também efetuamos análises comparativas dos resultados obtidos
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufpe.br:123456789/2297 |
| Date | 31 January 2008 |
| Creators | Josué da Silva Filho, Luiz |
| Contributors | Rose Benning Salgado, Liliane |
| Publisher | Universidade Federal de Pernambuco |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFPE, instname:Universidade Federal de Pernambuco, instacron:UFPE |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0627 seconds