Busca avançada
Ano de início
Entree

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

Processo: 12/24993-6
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de maio de 2013
Vigência (Término): 31 de outubro de 2014
Área do 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

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.