Baixe o app para aproveitar ainda mais
Prévia do material em texto
Anhanguera Educacional S.A. Correspondência/Contato Alameda Maria Tereza, 2000 Valinhos, SP - CEP 13278-181 rc.ipade@unianhanguera.edu.br pic.ipade@unianhanguera.edu.br Coordenação Instituto de Pesquisas Aplicadas e Desenvolvimento Educacional - IPADE Trabalho realizado com o incentivo e fomento da Anhanguera Educacional S.A. Kariny Escócio dos Santos Professora Orientadora: Ms. Janaine Cristiane de Souza Arantes Professor Colaborador: Esp. Maurício Rodrigues de Morais Curso: Ciência da Computação FACULDADE ANHANGUERA DE VALINHOS Trabalho apresentado no 9° Congresso Nacional de Iniciação Científica - CONIC. Trabalho apresentado no Evento Interno de Iniciação Científica - 2009. LÓGICA MATEMÁTICA APLICADA À DEFINIÇÃO DE ROTAS USANDO DISPOSITIVOS GPS ANUÁRIO DA PRODUÇÃO DE INICIAÇÃO CIENTÍFICA DISCENTE Vol. XII, Nº. 14, Ano 2009 RESUMO O problema de roteamento é um dos mais clássicos na área de computação, que abrange situações reais tão distintas como decisões de logística e definição de rotas em uma rede. Uma vez que um dos objetivos da área de Tecnologia da Informação (TI) é apresentar soluções computacionais para problemas do cotidiano, é possível entender quantas diferentes abordagens já foram estudadas para a solução desse problema. Este projeto pretende explorar a aplicação da Lógica Matemática ao problema de definição de rotas de veículos com a utilização de dispositivos ligados ao Sistema de Posicionamento Global (GPS). Para isso deve-se desenvolver e implementar um algoritmo em linguagem de programação lógica, a fim de contribuir cientificamente com a área de Inteligência Artificial (IA) e servir de fonte para outros pesquisadores. Inicialmente, o projeto explorou os fundamentos de logística referentes a problemas de roteamento, conceitos e paradigmas de programação lógica e sua linguagem mais conhecida, o PROLOG. Também se estudou a definição e utilização da tecnologia GPS e deu-se início à formulação da base de dados proposta para unir os assuntos abordados. A base de dados desenvolvida mostra que é possível determinar rotas a serem seguidas a partir de parâmetros pré-estabelecidos. Palavras-Chave: lógica matemática; programação lógica; métodos de roteamento; PROLOG; GPS. 401 Publicação: 10 de maio de 2010 ANUIC_N14_miolo.pdf 401 7/6/2010 18:17:06 402 Lógica matemática aplicada à definição de rotas usando dispositivos GPS 1. INTRODUÇÃO Desde os primórdios, a humanidade traz consigo a necessidade de explorar novas fronteiras (HASEGAWA et al., 2000). Para isso foi preciso desenvolver a arte da navegação, ou seja, obter conhecimento espacial dos locais que se pretende explorar. No entanto, explorar não se restringe somente ao posicionamento, mas abrange conhecimentos espaciais do ambiente, conhecimentos em definição de rotas e métodos de navegação. Um importante exemplo da utilização desses conhecimentos é apresentado por Russell (2004) e encerra em si um fato histórico. Durante a crise do Golfo Pérsico em 1991, o exército americano utilizou uma ferramenta chamada Dynamic Analysis and Replanning Tool (DART), que realizava o planejamento logístico de aproximadamente 50.000 veículos, levando em conta os pontos de partida, rotas e destinos, dentre outros fatores. O DART utilizava conceitos e técnicas de IA para a resolução de problemas reais. Dentre as áreas da computação, IA tem importância significativa na resolução desse tipo de problema. Nota-se sua contribuição para o avanço dos métodos de navegação, antes rudimentares como a utilização de bússola ou astrolábio, hoje melhor desenvolvidos como o GPS. Além dos avanços promovidos em relação à navegação, ressaltam-se os avanços em softwares que facilitam o processo de exploração e logística (FERREIRA FILHO, 2006). Uma das linguagens bastante utilizadas em IA (DIAS, 2002) é o PROLOG, que permite a criação de programas com a utilização dos conceitos de lógica de primeira ordem (SOUZA, 2002). Com isso é possível determinar a partir de parâmetros pré- estabelecidos quais as rotas a serem seguidas. Os princípios de lógica de primeira ordem fazem parte de Lógica Matemática, que é de extrema importância aos alunos do curso de Ciência da Computação, pois além de desenvolver o raciocínio lógico para solução de problemas cotidianos, promove a capacidade de romper as barreiras da imaginação, provar hipóteses e paradigmas, deduzir e criar novos conhecimentos (GERSTING, 2004). Este projeto propõe uma solução para os problemas de roteamento com o uso de dispositivos GPS, aplicação de conhecimentos primários em programação lógica e métodos de roteamento, bem como a modelagem de um protótipo na linguagem de programação PROLOG. Isso comprova que é possível utilizar os conceitos estudados em problemas reais, como a definição de rotas a partir de parâmetros pré-estabelecidos. Anuário da Produção de Iniciação Científica Discente • Vol. XII, Nº. 14, Ano 2009 • p. 401-412 ANUIC_N14_miolo.pdf 402 7/6/2010 18:17:06 Kariny Escócio dos Santos 403 Este artigo está organizado em seções. A primeira seção é essa introdução, a seção 2 apresenta os objetivos da pesquisa. A metodologia utilizada na realização da pesquisa é apresentada na seção 3. As informações relacionadas ao desenvolvimento da pesquisa como a revisão de literatura, o problema abordado, a solução proposta e implementada são mostradas na seção 4. A forma de abordar os experimentos, os resultados e as discussões são descritos na seção 5. Por fim, as considerações finais são apresentadas na seção 6. 2. OBJETIVO O objetivo principal deste projeto é mostrar que, a partir dos princípios dedutivos de Lógica Matemática, com a aplicação dos conceitos da linguagem de programação PROLOG, é possível determinar a melhor rota entre dois pontos marcados com o sistema de posicionamento global. Para isso foi desenvolvida uma modelagem de protótipo com a linguagem lógica de programação. O GPS foi utilizado como ferramenta para que o software identifique os pontos e trace rotas entre os mesmos. Além disso, como objetivo secundário pretende-se constatar que os conhecimentos adquiridos no início de um curso de Ciência da Computação são efetivos para a construção de uma base de dados que solucione problemas reais. 3. METODOLOGIA A pesquisa foi iniciada com o estudo da bibliografia referente aos assuntos relacionados ao projeto, que são: problemas de roteamento, tecnologia GPS e programação lógica. Com os conhecimentos obtidos, iniciou-se a modelagem do protótipo e a definição da base de dados para traçar a rota a ser seguida a partir do sistema GPS. Passou-se ao planejamento dos detalhes do experimento realizado e seu aprimoramento. Uma vez concluídos esses passos, o algoritmo em linguagem PROLOG foi executado e os resultados foram coletados. Por fim foi realizada a análise dos resultados obtidos e a escrita do artigo científico. 4. DESENVOLVIMENTO Para desenvolver o algoritmo proposto, inicialmente, foi necessário obter conhecimento sobre roteamento, GPS e programação lógica, bem como o estudo de alguns trabalhos correlatos. Anuário da Produção de Iniciação Científica Discente • Vol. XII, Nº. 14, Ano 2009 • p. 401-412 ANUIC_N14_miolo.pdf 403 7/6/2010 18:17:06 404 Lógica matemática aplicada à definição de rotas usando dispositivos GPS 4.1. Definição de Rotas O roteamento, seja ele de frotas de veículos, rede de computadores ou transporte de materiais, para melhor ser entendido necessita da definição de alguns conceitos de logística. Carvalho (2002) divide a logística em dois grupos de atividades, as principais (transporte, manutenção de estoquee processamento de pedidos) e as secundárias (armazenagem, manuseio de materiais, embalagem, suprimentos, planejamento e sistema de informação). Segundo Ferreira (1986), logística, do francês Logistique, por definição trata do planejamento e realização do projeto, armazenamento, transporte, distribuição, reparação, manutenção e evacuação de material para fins operativos ou administrativos. Ferreira Filho (2006) descreve seu objetivo e missão, que são a redução de custos operacionais e agregar qualidade, praticidade e satisfação do cliente/usuário, a fim de criar rotinas para minimizar erros e aumentar o nível da prestação do serviço. No âmbito de uma das atividades principais da logística, o transporte, mais especificamente a definição de rotas e trajetos, a partir de parâmetros pré-estabelecidos, nota-se a preocupação com a prévia visualização de alguns dados. Esses dados são fatores de determinação da rota, como quantidade de veículos, sequência realizada por cada veículo, produtos a serem embarcados, capacidade de carga ou restrições de velocidade. Ainda com o objetivo de melhorar esse planejamento logístico é necessário, além dos dados informativos, citados anteriormente, obter conhecimentos espaciais, posicionamento, restrições viárias e métodos de navegação (HASEGAWA et al., 2000). A combinação da logística e TI forma uma arma estratégica para a melhor solução dos problemas de definição de rotas (FIGUEIREDO, 2000). Assim desenvolvem-se táticas, a fim de aperfeiçoar os processos a serem realizados e obter um resultado positivo para a solução dos problemas cotidianos. 4.2. GPS Durante anos uma das tecnologias de mapeamento que mais expande é o GPS. O sistema foi criado pelo Departamento de Defesa dos Estados Unidos da América, o DoD (DEFENSE LINK, 2009), no término da década de 1970, porém, foi considerado totalmente operacional somente em 1995. Seu desenvolvimento custou por volta de 10 bilhões de Anuário da Produção de Iniciação Científica Discente • Vol. XII, Nº. 14, Ano 2009 • p. 401-412 ANUIC_N14_miolo.pdf 404 7/6/2010 18:17:06 Kariny Escócio dos Santos 405 dólares e, embora inicialmente fosse de uso exclusivo militar, hoje é aberto gratuitamente para a população civil. O sistema é formado por 28 satélites orbitais que foram construídos pela empresa Rockwell. Cada satélite chega a uma velocidade de 11265 quilômetros por hora, completa duas voltas por dia na órbita terrestre a uma altura de cerca de 20200 quilômetros e transmite sinais para os receptores, que, por sua vez, captam os sinais de quatro satélites, os decodificam e informam as respectivas posições. Além de mostrar a latitude e longitude, o receptor pode informar outros diversos dados, que podem ser geográficos, topográficos e, de acordo com a configuração, nomes de ruas, avenidas e construções. Existem receptores de diversas marcas e são geralmente classificados em Geodésicos, Topográficos ou de Navegação. Os Geodésicos e Topográficos têm um funcionamento similar e de grande precisão, porém, não informam a posição instantânea. Os Receptores de Navegação são mais utilizados, apesar de possuírem menor precisão, pelo menor custo de aquisição e maior variedade de modelos; e podem ser celulares, relógios, computadores de mão, notebooks, rastreadores de veículos, dentre outros (THEODORE, 2009). A tecnologia GPS tem sua aplicação na área de aviação, navegação marítima, exploração florestal, geológica ou arqueológica (MELO, 2009) e é uma ferramenta valiosa para a melhor definição de rotas. Neste projeto a importância dessa ferramenta dá-se pelo fato de obter dados precisos e alimentar a base de dados do protótipo proposto para que as rotas sejam traçadas. 4.3. Programação Lógica A lógica, do grego Logos, significa pensamento, razão ou idéia e está intimamente ligada à matemática e à filosofia (BLANCHE; DUBUCS, 2001). Um sistema lógico é um “conjunto de axiomas e regras de inferência que visa representar formalmente o raciocínio válido”. Com o estudo da Lógica Matemática aprimorou-se a capacidade de desenvolver teorias matemáticas ou filosóficas, que determinam a validade de argumentos e encontram valores lógicos em alguma interpretação da expressão lógica. A linguagem de programação lógica tem sua base em Lógica Matemática e começou a ser desenvolvida na década de 1950 por John McCarthy no contexto de IA (DIAS, 2002), que une a eficácia da lógica de predicados com a linguagem computacional. Anuário da Produção de Iniciação Científica Discente • Vol. XII, Nº. 14, Ano 2009 • p. 401-412 ANUIC_N14_miolo.pdf 405 7/6/2010 18:17:07 406 Lógica matemática aplicada à definição de rotas usando dispositivos GPS Dentre as linguagens de programação procedurais mais conhecidas estão o C e o Pascal. Nesse tipo de linguagem a maior parte do código escrito consiste em executar passo a passo o algoritmo que o programador desenvolveu com o intuito de solucionar o problema considerado. Nesse caso, o programador necessita instruir o que e como o programa irá fazer (GERSTING, 2004). Diferentemente das linguagens procedurais existem as linguagens declarativas ou descritivas. Nesse paradigma encontra-se o PROLOG (abreviação de Programming in Logic), que se baseia na lógica de predicados. Segundo Gersting (2004), o conjunto de declarações, também conhecido como banco de dados PROLOG, é dividido entre fatos e regras. Os fatos formam base de dados relacionais entre os predicados e as regras referem-se às relações lógicas. Por exemplo, para formar uma relação progenitora entre os argumentos pode-se utilizar a declaração (1) que indica por definição que Maria é progenitora de Jesus (MONARD; NICOLETTI, 1993). (1) Ao compilar o programa, pode-se perguntar sobre a relação progenitor como mostra o exemplo (2). (2) A resposta que o programa oferece é positiva, pois esse é um fato inserido em sua base. Entendido esse conceito, pode-se variar as questões conforme a estrutura (3). (3) Nota-se a capacidade de validar se uma relação é verdadeira ou falsa. No caso (4) o programa fornece o valor de X e não se a relação é verdadeira ou falsa. (4) As regras, classificadas ou não como recursivas, também chamadas de cláusulas, podem utilizar variáveis e dão um valor de verdadeiro ou falso a um objeto conforme o exemplo (5). (5) progenitor(maria,jesus). ?- progenitor(maria,jesus). yes ?- progenitor(silvio,jesus). no ?- progenitor(X,jesus). X=maria luz(acesa):-interruptor(ligado). Anuário da Produção de Iniciação Científica Discente • Vol. XII, Nº. 14, Ano 2009 • p. 401-412 ANUIC_N14_miolo.pdf 406 7/6/2010 18:17:07 Kariny Escócio dos Santos 407 O sinal “:-“ indica a relação “se” a luz está acesa, o interruptor está ligado, tornando-a verdadeiro. Os dados em PROLOG também são diferentes das linguagens procedurais por serem somente do tipo Termo. Eles são diferenciados a partir dos elementos léxicos utilizados na declaração que os darão características de número, texto, variável, átomo ou termo composto. Esses são conceitos primários de programação lógica, mas suficientes para entender o seu funcionamento e aplicação em problemas cotidianos. 4.4. Trabalhos Correlatos Constatou-se com a revisão de literatura que os assuntos abordados na pesquisa foram muito explorados, porém, de forma isolada. Podem-se citar como trabalhos correlatos o Problema do Rato no Tabuleiro (MONARD, 1993) e o Problema do Cavalo (MONARD, 1993). O Problema do Rato no Tabuleiro, apresentado na Figura 1, é uma eficaz solução de roteamento de um rato em uma determinada posição no tabuleiro de xadrez até um pedaçode queijo em outra posição no mesmo tabuleiro. O rato memoriza o caminho para não passar mais que uma vez pela mesma posição, até chegar ao objetivo. O Problema do Cavalo consiste em definir uma rota para que o cavalo saia de um ponto inicial no tabuleiro e chegue ao ponto final, que são definidos pelo usuário. Como no jogo de xadrez, o cavalo só pode andar na posição determinada (duas casas na horizontal e uma na vertical, ou vice-versa, em qualquer direção). Para isso foram marcados os pontos no tabuleiro, os parâmetros que o cavalo pode andar e as regras de verificação dos caminhos percorridos. Anuário da Produção de Iniciação Científica Discente • Vol. XII, Nº. 14, Ano 2009 • p. 401-412 ANUIC_N14_miolo.pdf 407 7/6/2010 18:17:07 408 Lógica matemática aplicada à definição de rotas usando dispositivos GPS Figura 1 – Execução do Programa do Rato no Tabuleiro. Os dois trabalhos definem rotas a partir de parâmetros pré-estabelecidos e utilizam conceitos de lógica matemática e programação lógica. Este projeto visa propor uma solução similar, porém tratar-se-á de um problema cotidiano real. 4.5. Algoritmo A modelagem do algoritmo propõe, a partir dos princípios de programação lógica, a definição de uma rota a ser seguida com base em parâmetros pré-estabelecidos e do marco de dois pontos no sistema GPS. A base de conhecimento do algoritmo proposta é alimentada com as coordenadas geográficas obtidas pelo sistema GPS. O usuário define o ponto de partida e de chegada e o algoritmo indica as possíveis rotas entre eles. Anuário da Produção de Iniciação Científica Discente • Vol. XII, Nº. 14, Ano 2009 • p. 401-412 ANUIC_N14_miolo.pdf 408 7/6/2010 18:17:07 Kariny Escócio dos Santos 409 Como exemplo da utilização do GPS, foi escolhido um bairro na cidade de Itatiba-SP, mostrado na Figura 2. Figura 2 – Pontos no Sistema GPS. A partir do mapa apresentado na Figura 2, o relacionamento entre os pontos foram definidos como fatos na Figura 3. Figura 3 – Amostra dos Fatos em PROLOG. Para que o algoritmo trace a rota entre um ponto e outro, é necessário definir pelo menos uma regra (que pode ser recursiva) com base nos fatos como exemplificado na Figura 4. A partir dessa regra inicial, pode-se observar a locomoção entre diversos pontos, desde que haja ligação entre eles. Anuário da Produção de Iniciação Científica Discente • Vol. XII, Nº. 14, Ano 2009 • p. 401-412 ANUIC_N14_miolo.pdf 409 7/6/2010 18:17:07 410 Lógica matemática aplicada à definição de rotas usando dispositivos GPS Figura 4 – Amostra das Regras em PROLOG. Ao executar o algoritmo no programa SWI-PROLOG, constata-se a possibilidade de navegação entre os pontos. Uma amostra da resposta do programa pode ser visualizada na Figura 5. Figura 5 – Execução do Algoritmo no Programa SWI-PROLOG. 5. RESULTADOS Após o estudo bibliográfico dos conceitos de logística, tecnologia GPS e programação lógica foi possível obter conhecimento necessário para entender o modelo do problema sobre uma ótica de programação lógica, alimentar a base de conhecimento do protótipo com as coordenadas geográficas obtidas através do sistema GPS e desenvolver a modelagem do algoritmo de roteamento. Para verificar se a modelagem do algoritmo contém todos os fatos necessários e as regras de relacionamento entre eles, testes foram aplicados e os resultados foram coletados. Isso possibilitou alguns ajustes necessários para a melhor definição do algoritmo. Anuário da Produção de Iniciação Científica Discente • Vol. XII, Nº. 14, Ano 2009 • p. 401-412 ANUIC_N14_miolo.pdf 410 7/6/2010 18:17:07 Kariny Escócio dos Santos 411 Também como resultado, pode-se observar as possibilidades de melhorias na modelagem e a implementação de interface gráfica para comunicação com o usuário. 6. CONSIDERAÇÕES FINAIS Com base nos assuntos estudados nota-se que a definição de rotas é um assunto de extrema relevância, pois abrange vários problemas cotidianos que podem ser melhor resolvidos com a junção de conceitos de logística e TI. Apesar da dificuldade em encontrar trabalhos que unam os conceitos abordados, existem muitos isolados que tratam dos mesmos assuntos, o que serviu de embasamento para o desenvolvimento do projeto. A relevância da pesquisa se dá por fazer o elo entre esses conceitos. A partir do desenvolvimento da modelagem do algoritmo em linguagem de programação PROLOG e testes aplicados, pode-se citar que o algoritmo é capaz de definir o caminho a ser seguido com a utilização da tecnologia GPS e princípios de lógica matemática. Como proposta de continuação desse projeto estão a melhoria da base de conhecimento, a criação de interface gráfica para comunicação com o usuário e o desenvolvimento do algoritmo em linguagem Java com o uso de frameworks que possibilitem a programação lógica. Com isso é possível obter melhores rotas com facilidade de comunicação e armazenamento dos resultados obtidos pelo protótipo. REFERÊNCIAS BLANCHE, Robert; DUBUCS, Jacques-Paul. História da Lógica. Edições 70, 2001. CARVALHO, José Meixa Crespo de. Logística. 3.ed. Lisboa: Edições Silabo, 2002. DEFENSE LINK. Satellite Provides Vital Information to Military. Disponível em: <http://www.defenselink.mil/transformation/articles/2006-05/ta050106a.html>. Acesso em: 19 maio 2009. DIAS, Francielton da Silva. Inteligência Computacional. Universidade Estadual Vale do Aracajú, 2002. FERREIRA, Aurélio Buarque de Holanda. Novo Dicionário Aurélio da Língua Portuguesa. 2.ed. Rio de Janeiro: Nova Fronteira, 1986. FERREIRA FILHO, A.S. Modelagem de Sistemas de Informação para os transportes em ambientes logísticos geo-referenciados com o emprego da Lógica de Fuzzy. Universidade Federal do Rio de Janeiro, 2006. FIGUEIREDO, Kleber Fossati. Logística Empresarial: A Perspectiva Brasileira. São Paulo: Atlas, 2000. Anuário da Produção de Iniciação Científica Discente • Vol. XII, Nº. 14, Ano 2009 • p. 401-412 ANUIC_N14_miolo.pdf 411 7/6/2010 18:17:07 412 Lógica matemática aplicada à definição de rotas usando dispositivos GPS Anuário da Produção de Iniciação Científica Discente • Vol. XII, Nº. 14, Ano 2009 • p. 401-412 GERSTING, Judith L.; IORIO, Valéria de Magalhães. Fundamentos Matemáticos para a Ciência da Computação. 5.ed. Rio de Janeiro: LTC, 2004. HASEGAWA, J.K. et al. Planejamento logístico de rotas para sistema de navegação apoiado por GPS. In: COBRAC – Congresso Brasileiro de Cadastro Técnico Multifinalitário. Florianópolis – SC, 2000. CD-ROM. MELO, Marcelo. Global Positioning Systems - Navegação e Análise para vôo-livre. Disponível em: <http://www.scribd.com/doc/13497045/Curso-de-Gps>. Acesso em: 02 maio 2009. MONARD, M.C. Busca informada e Não informada: Aplicações. Universidade de São Paulo / ICMC, 1993. MONARD, M.C.; NICOLETTI, M.C. Programas PROLOG para Processamento de Listas e Aplicações. Universidade Federal de São Carlos / ILTC, Versão 2.0, 1993. RUSSELL, Stuart; NORVIG, Peter. Inteligência Artificial. 2.ed. Rio de Janeiro: Elsevier, 2004. SOUZA, João Nunes de. Lógica para Ciência da Computação: fundamentos de linguagem, semântica e sistemas de dedução. 1.ed. Rio de Janeiro: Elsevier, 2002. THEODORE. Egypt Lifts GPS Ban. Disponível em: <http://www.thedailynewsegypt.com/article.aspx?ArticleID=20865>. Acesso em: 16 maio 2009. ANUIC_N14_miolo.pdf 412 7/6/2010 18:17:07 1672_PIC09192_ed
Compartilhar