Soluções Exatas para o Problema Cromático da Galeria de Arte

• Processo: 12/24993-6
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de maio de 2013
• Data de Término da vigência: 31 de outubro de 2014
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Pedro Jussieu de Rezende
• Beneficiário: Mauricio Jose de Oliveira Zambon
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Bolsa(s) vinculada(s): 13/25104-3 - O problema cromático da galeria de arte, BE.EP.MS
• Assunto(s): Geometria computacional
• Palavra(s)-Chave do Pesquisador: art gallery | graph coloring | Integer Programming | Geometria Computacional

Resumo

Considere uma aplicação na qual um robô móvel (por exemplo, um manipulador industrial, ou um vigia móvel numa área de segurança) encontra-se em um ambiente cuja planta baixa tem sua fronteira descrita por um polígono simples (possivelmente com buracos). Com o intuito de se guiar o robô, podem ser colocadas marcações neste ambiente (ou emissores de sinal visual) de forma que o robô consiga discerni-las e possa realizar ações de locomoção baseado em suas localizações. Movimentos possíveis incluem seguir em direção a uma marca, em direção oposta a ela ou circularmente à sua volta. Para fins de formulação do problema, considere que as marcas, distinguíveis apenas por suas cores, assim como o robô, são idealizados como pontos (zero dimensionais). Uma instrução de movimento ao robô é impraticável se ele não tem nenhuma marcação à vista e ambígua se ele vê simultaneamente duas marcações de mesma cor. Dizemos que uma marcação cobre um ponto do ambiente se um robô é capaz de ver essa marcação a partir daquele ponto. Deste modo, dada uma descrição do ambiente, faz-se necessário determinar o posicionamento de marcações que garantam a cobertura de todos os pontos do ambiente de forma que se possa atribuir uma coloração a essas marcas de maneira que nenhum ponto seja coberto por duas marcas de mesma cor. Além disso, é desejável que o número de cores resultante seja o menor possível.Uma maneira alternativa de se descrever esse problema é no contexto dos problemas de Galeria de Arte amplamente estudados na literatura de geometria computacional. Considere P um polígono simples (possivelmente com buracos) e um conjunto finito de pontos (guardas) R, subconjunto de P, que cobre P. Obviamente, |R| cores são suficientes para se colorir os pontos de R de modo que nenhum ponto de P seja coberto por dois guardas de cores iguais. A uma coloração de R com essa propriedade denominamos coloração válida. A busca por uma coloração válida minimal se justifica, no contexto da aplicação mencionada, já que, quanto menos cores o robô tiver que identificar, mais precisa será a classificação das marcações, pois, dependendo das condições de iluminação e da qualidade dos sensores do robô, quanto mais tons similares houver, maior a chance de erros de classificação.Assim, várias questões podem ser levantadas. A mais simples é dados P e R determinar uma coloração com o menor número de cores suficientes para se colorir R de forma válida. Mais interessante é o problema de, dados P e um conjunto finito de pontos G, determinar uma cobertura R, subconjunto de G, de P que admite uma coloração válida de menor cardinalidade dentre todas as coberturas contidas em G. A este último denomina-se Problema da Galeria de Arte Cromática} (Chromatic Art Gallery Problem - CAGP).O objetivo principal deste projeto é resolver de forma exata o CAGP, assim como algumas de suas variações. Como esse problema só foi introduzido na literatura muito recentemente (em 2011), sua complexidade ainda está em aberto. São conhecidos apenas alguns limites superiores e inferiores para classes muito restritas de polígonos e nenhum algoritmo exato nem aproximado. Pretendemos atingir esse objetivo através de modelos de Programação Linear Inteira. Além disso, pretende-se desenvolver heurísticas para escolhas de candidatos a guardas, para um estudo comparativo.

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

ZAMBON, Mauricio Jose de Oliveira. Soluções exatas para o Problema Cromático da Galeria de Arte. 2014. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.