Comparação de algoritmos para otimização de restrições distribuídas em um cenário de controle semafórico

Detalhes bibliográficos
Ano de defesa: 2007
Autor(a) principal: Junges, Robert
Orientador(a): Bazzan, Ana Lucia Cetertich
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Palavras-chave em Inglês:
Link de acesso: http://hdl.handle.net/10183/16123
Resumo: Problemas de otimização de restrições distribuídas (DCOP - Distributed Constraint Optimization Problem) formam uma classe de problemas de grande interesse de estudo na ciência da computação em função da complexidadecomputacionaL O presente trabalho tem o objetivo de comparar os três algoritmos mais populares em DCOP (ADOPT, OptAPO e DPOP) em termos de eficiência computacional e de solução proposta. Para tal estudo, é utilizado como domínio um problema de controle semafórico. Esse tipo de problema de controle é de fundamental importânciapara que se tenha uma administração eficiente do fluxo de veículos em uma malha viária. Além disso, envolve muitas interdependências entre variáveis da rede, como ocupação das vias e tempos de sinal verde dos semáforos, para que sejam determinadas as melhores configurações de controle. Nesse sentido, as estratégias devem fornecer bons resultados em nível de aplicação, e também em nível de computação, no que diz respeito ao uso da infra-estrutura computacional disponível, o que casa perfeitamente com os objetivos das implementações de DCOP. Ao longo deste trabalho, os temas relacionados à coordenação em sistemas multiagentes, otimização de restrições e controle de semáforos são estudados. Os modelos DCOP são utilizados com a finalidade de comparar os algoritmos.No que diz respeito aos resultados, percebe-se uma melhora no controle, obtida com o uso dos algoritmos DCOP em relação ao uso de controle fixo sincronizado e não sincronizado. Isso é verificado em nível de utilização das vias da rede. Além disso, outro tipo de resultado é verificado na execução dos algoritmos, tratando de questões como o tempo de execução. Foi possível estabelecer um comparativo entre os algoritmos e frente ao aumento do problema em quantidade de semáforos.