Uma aplicação do algoritmo QT clustering para marcação colaborativa de pontos perigosos em vias públicas - PDF
Download "Uma aplicação do algoritmo QT clustering para marcação colaborativa de pontos perigosos em vias públicas"
Gabriel Henrique Pedroso Soares
1 UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE CENTRO DE TECNOLOGIA PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E DE COMPUTAÇÃO Uma aplicação do algoritmo QT clustering para marcação colaborativa de pontos perigosos em vias públicas Adelson Luiz de Lima Orientador: Prof. Dr. Agostinho de Medeiros Brito Júnior Dissertação de Mestrado apresentada ao Programa de Pós-Graduação em Engenharia Elétrica e de Computação da UFRN como parte dos requisitos para obtenção do título de Mestre em Ciências. Número de ordem PPgEE: M372 Natal, RN, dezembro de 2012
2 UFRN / Biblioteca Central Zila Mamede Catalogação da Publicação na Fonte Lima, Adelson Luiz de. Uma aplicação do algoritmo QT clustering para marcação colaborativa de pontos perigosos em vias públicas / Adelson Luiz de Lima. - Natal, RN, f. : il. Orientador: Prof. Dr. Agostinho de Medeiros Brito Júnior. Dissertação (Mestrado) - Universidade Federal do Rio Grande do Norte. Centro de Tecnologia. Programa de Pós-Graduação Engenharia Elétrica e da Computação. 1. Algoritmo QT - Dissertação. 2. Acidentes de trâncito - Prevenção - Dissertação. 3. Sistema de alerta - Dissertação. 4. Sistemas colaborativos - Dissertação. 4. Aglomeração de dados - Dissertação. 5. Sistema de Informação Geográfica - Dissertação. I. Brito Júnior, Agostinho de Medeitos. II. Universidade Federal do Rio Grande do Norte. III. Uma aplicação do algoritmo QT clustering para marcação colaborativa de pontos perigosos em vias públicas. RN/UF/BCZM CDU
3 Uma aplicação do algoritmo QT clustering para marcação colaborativa de pontos perigosos em vias públicas Adelson Luiz de Lima Dissertação de Mestrado aprovada em 7 de dezembro de 2012 pela banca examinadora composta pelos seguintes membros: Prof. Dr. Agostinho de Medeiros Brito Júnior (orientador) DCA/UFRN Prof. Dr. Allan de Medeiros Martins DEE/UFRN Prof. Dr. Paulo Sérgio da Motta Pires DCA/UFRN Prof. Dr. George Azevedo da Silva IFRN
4 Dedico este trabalho à minha família e amigos.
5 Agradecimentos Ao meu orientador, professor Agostinho, sou grato pela orientação. Ao professor Paulo Motta, pelos valiosos comentários que enriqueceram meu trabalho. Aos meus colegas de pós-graduação, pelas críticas, sugestões e apoio. À minha família e amigos pelo apoio durante esta jornada. À CAPES, pelo apoio financeiro.
6 Resumo O trabalho propõe um sistema colaborativo para marcação de pontos perigosos em vias de transporte e geração de alertas para motoristas. Ele consistire de um sistema de alerta de proximidade de um ponto de perigo, que será alimentado pelos próprios motoristas através de um aparelho móvel equipado com GPS. O sistema deverá consolidar dados fornecidos por vários motoristas diferentes e gerar um conjunto de pontos comuns que serão usados no sistema de alerta. Embora a aplicação seja destinada à proteção de motoristas, os dados gerados por ela poderão servir de insumos para os órgãos responsáveis melhorarem a sinalização e recuperação de vias públicas. Palavras-chave: Prevenção de acidentes de trânsito, sistema de alerta, sistemas colaborativo, aglomeração de dados, sistemas de informação geográfica.
7 Abstract This work proposes a collaborative system for marking dangerous points in the transport routes and generation of alerts to drivers. It consisted of a proximity warning system for a danger point that is fed by the driver via a mobile device equipped with GPS. The system will consolidate data provided by several different drivers and generate a set of points common to be used in the warning system. Although the application is designed to protect drivers, the data generated by it can serve as inputs for the responsible to improve signage and recovery of public roads. Keywords: Prevention of traffic accidents, warning systems, collaborative systems, data clustering, geographic information systems.
8 Sumário Sumário Lista de Figuras i iii 1 Introdução Objetivos Objetivos Específicos Organização do texto Sistemas de Informação Geográfica Foursquare WAZE WikiMapa Wikimapia Comob Avaliação das ferramentas pesquisadas no escopo do trabalho proposto Aglomeração de dados QT clustering Trabalho proposto Funcionamento do sistema Marcação de pontos Processamentos dos dados Remoção de pontos Alertas de perigo Interface desktop Sincronização e expurgo de dados Modelo do sistema Resultados 29 i
9 6 Considerações finais 34 7 Agradecimentos 36 Referências bibliográficas 36
10 Lista de Figuras 4.1 Arquitetura do sistema proposto para marcação e aglomeração de pontos Interface de usuário para dispositivo móvel Exemplo de nuvens formada pela marcação de vários motoristas com seu ponto representativo e os diferentes tipos de nuvens com pontos de perigo que podem ser marcados nos cursos das vias Protótipo da interface desktop para visualização de centros usando os recursos do Google Maps Módulos do sistema Módulos/Plataformas do sistema Diagrama de classes do módulo móvel Experimento em zona urbana Experimento em zona rural Experimento em zona urbana - marcação de falhas nas Avenidas Salgado Filho e Hermes da Fonseca, Natal-RN iii
11 Capítulo 1 Introdução A imperícia e a imprudência no trânsito são, sem dúvida, os principais responsáveis pela maioria dos acidentes nas estradas brasileiras. De fato, a má formação de condutores para o trânsito brasileiro, junto com a dificuldade de fiscalização e aplicação de penas mais severas aos infratores, contribui para o estado em que se encontra o trânsito no nosso país. É inegável a contribuição da formação humana para a quantidade, a gravidade e o tipo dos acidentes presentes nas estatísticas oficiais do DNIT - Departamento Nacional de Infraestrutura de Transporte [DNIT 2011]. Entretanto, boa parcela dos acidentes de trânsito no Brasil são provocados por falhas nas vias de transporte estaduais e federais, sejam essas falhas buracos, ondulações, pavimentos irregulares, valetas, inclinações, depressões, lombadas e curvaturas mal planejadas. As próprias estatísticas do DNIT relatam que, em 2010, havia aproximadamente km de vias no país que concentravam acidentes. Informações fornecidas pela Polícia Rodoviária Federal demonstram que, embora reduzidos, acidentes por defeito nas vias ainda são comuns. Os dados fornecidos são apresentados na Tabela Ano do Acidente Quantidade. de Acidentes % do total de acidentes ,83% ,55% ,65% ,32% Total geral ,56% Tabela 1.1: Estatísticas de acidentes causados por falhas em vias públicas. Danos físicos e até mortes são consequências comuns em acidentes causados por falhas nas vias, principalmente relacionado a veículos com duas rodas. Ainda, os danos 1 informações gentilmente cedidas pela Polícia Rodoviária Federal
12 CAPÍTULO 1. INTRODUÇÃO 2 não se resumem apenas em prejuízo à integridade física dos motoristas e passageiros. Grande prejuízos financeiro são agregados frequentemente a essas falhas, sejam eles representados por gastos com manutenções ou reparos causados por tais problemas. Dada a quantidade de impostos pagos pelos contribuintes para criação e manutenção de vias, geralmente entende-se de responsabilidade do estado os prejuízos causados aos veículos e passageiros pela má conservação, má sinalização ou má manutenção das vias públicas. Um caso exemplar de grande prejuízo pode-se imaginar no meio das empresas transportadoras de cargas. A perda da carga no caso de um tombamento ocasionado por uma falha nas rodovias não só representa o prejuízo, mas também danos ao veículo e atraso ocasionado pelo reenvio da carga. Em outras palavras, o prejuízo direto será não somente para a empresa transportadora mas também para a sua contratante. Embora investimentos públicos sejam feitos constantemente para melhorar a qualidade das estradas brasileiras, a presença de pontos perigosos são inevitáveis. As origens geralmente são advindas do desgaste natural pelo uso constante, relevo e topologia, e a própria intempéries da natureza. Diversas soluções comerciais que já são capazes de orientar motoristas no trânsito, que são os tradicionais sistemas guiados por GPS (Global Positioning System). Alguns deles, por exemplo, oferecem alertas de proximidade para radares de velocidade, permitindo que o motorista fique atento aos limites de velocidade e, é claro, às multas impostas pela transgressão destes limites. A eficiência destas soluções dependem do esforço das empresas em manter sempre atualizados seus bancos de dados e nos mecanismos de repasse destes dados aos proprietários dos sistemas de navegação. Apesar do sucesso destas ferramentas, nota-se a carência de uma funcionalidade simples que permita aos próprios motoristas ajudarem uns aos outros a se proteger de falhas e pontos perigosos nas vias públicas, principalmente durante períodos noturnos, quando a visibilidade da via diminui. É nesse contexto que o presente trabalho é inserido, oferecendo uma forma de atenuar os problemas decorrentes dos danos causados pelas falhas e pontos perigosos presentes nas vias de transporte. O trabalho propõe um sistema que alerta aos motoristas da proximidade de algum ponto de perigo, permitindo a tomada de decisões capazes de evitar danos à saúde ou ao patrimônio. O sistema proposto consistirá de um programa para dispositivos móveis que poderá ser instalado em celulares do tipo smartphones equipados com GPS. O sistema será dotado de uma interface bastante simples, com botões para propor a inserção e remoção de pontos perigosos, além de exibir alertas visuais e sonoros aos seus usuários. A proposta da implementação em smartphones alia conveniência e custo, haja vista o barateamento de
13 CAPÍTULO 1. INTRODUÇÃO 3 tais dispositivos no mercado, o uso cada vez mais presente destes dispositivos como meio de comunicação e a presença de módulos GPS em grande parte deles. Neste contexto, a ferramenta proposta seria apenas mais um aplicativo a ser inserido no smartphone, tornando os custos da solução bastante reduzidos. Para que o sistema alerte ao usuário da proximidade de um ponto de perigo é preciso saber a localização deste ponto. Para isto, os usuários do sistema ao trafegarem pelas vias e identificarem esses pontos contribuirão com o sistema marcando-os na ferramenta interativa, para que a coordenada geográfica desse ponto seja transmitida ao servidor para um futuro processamento. A fusão das informações fornecidas pelos usuários deverá ser feita através de um servidor central que coletará, através da Internet, os pontos marcados pelos usuários da ferramenta e realizará a consolidação destes dados através da catalogação de aglomerados de pontos sugeridos para trechos comuns. O servidor processará os pontos oferecidos pelos motoristas utilizando algoritmos inteligentes, repassando as informações consolidadas aos módulos dos smartphones, por requisição dos próprios usuários. Os dados gerados pelo sistema serão integrados com o sistema de informações geográficas Google Maps (http://maps.google.com), acessível através da Internet, que mostrará a localização dos pontos de perigo e poderá disponibilizar estatísticas para que usuários e governantes possam utilizá-lo de forma a visualizar e colaborar na prevenção de acidentes. Ainda, a base de dados do sistema poderá servir de insumo para integração em sistemas de navegação que permitam traçados de rotas mais seguras, evitando assim possíveis danos ao motorista e ao seu veículo. 1.1 Objetivos O objetivo geral do trabalho é desenvolver um sistema de alerta que ajude aos motoristas de transportes automotivos a ficarem atentos a falhas nas vias de transporte ou trechos perigosos, ajudando a evitar acidentes e prejuízos materiais. Sua principal contribuição é oferecer uma ferramenta voltada especificamente para a realidade brasileira, preenchendo uma lacuna deixada pela maioria das ferramentas comerciais encontradas Objetivos Específicos Os objetivos específicos do presente trabalho de pesquisa consistem em: Fazer uma revisão dos trabalhos existentes que utilizam SIG;
14 CAPÍTULO 1. INTRODUÇÃO 4 Realizar estudos sobre algoritmos de aglomeração de dados (clustering); Elicitar os requisitos do sistema a ser desenvolvido; Modelar a arquitetura do sistema; Implementar protótipo de ferramenta para funcionamento em algum modelo de smartphone; Propor uma mecanismo de coleta, distribuição e processamento de dados de usuários; Validar o sistema proposto. 1.2 Organização do texto Este trabalho encontra-se dividido da seguinte forma. O Capítulo 2 descreve a ideia geral do trabalho que se propõe desenvolver no contexto de aplicações correlatas existentes. O Capítulo 3 oferece uma visão geral de algoritmos de aglomeração de dados, fundamentando a escolha do algoritmo de aglomeração proposto para uso no processamento dos dados fornecidos pelos usuários. O Capítulo 4 descreve o sistema proposto, seu funcionamento e sua arquitetura. O Capítulo 5 mostra alguns resultados obtidos com pontos coletados em zonas urbanas e rurais no estado do Rio Grande do Norte. O Capítulo 6 finaliza o trabalho apresentando algumas considerações acerca do desenvolvimento e traça proposta de tarefas futuras agregadas à temática apresentada.
15 Capítulo 2 Sistemas de Informação Geográfica Sistemas de Informação Geográfica (SIG) são ferramentas que permitem sobrepor informações espaciais (geográficas) com vários outros tipos de informações [Clarke 1986]. A sobreposição permite cruzar informações respeitando uma determinada localização geográfica. Deste modo, é possível construir mapas onde aparecem informações úteis para analisar diversos fenômenos. Esse cruzamento de informações possibilita vários estudos de análise espacial com base nos parâmetros presentes no SIG. Devido às suas potencialidades, os SIGs são atualmente utilizados em diversas atividades profissionais, seja em planejamento, em investigação científica, em estudos de impacto ambiental ou compartilhamento de informações genéricas. Os SIGs permitem ainda realizar diferentes operações de análise, como calcular distâncias, identificar os elementos que se encontram em determinados locais, ou que tenham determinadas características. Praticamente não há limitação acerca dos tipos de dados que podem ser utilizados em um SIG. Embora originalmente tenham sido desenvolvidos para fins de exibição de informações naturais como relevo, clima e vegetação, a tecnologia atual permite inserir os mais variados tipos de dados em um SIG. Exemplos de informações presentes em SIGs atuais incluem imagens, vídeos e pontos de referência. No presente trabalho, o SIG funcionaria utilizando uma base de dados com as informações geográficas de pontos de perigo que podem ser mostrados em um mapa digital como a plataforma Google Maps. Os modelos mais comuns em SIG são o raster (ou matricial) e o vetorial. O modelo de SIG matricial utiliza um mapa de células de tamanho regular, geralmente quadradas, que armazenam valores de informação para uma dada região do espaço real. Quanto maior a dimensão da célula, menor é a quantidade de detalhes que se consegue representar no espaço geográfico. Quanto menor o tamanho da célula, maior a quantidade de detalhes. No caso do modelo de SIG vetorial, a representação é focada na precisão da localização dos elementos no espaço. A ferramenta Google Maps, por exemplo, apresenta uma
16 CAPÍTULO 2. SISTEMAS DE INFORMAÇÃO GEOGRÁFICA 6 mistura destes dois modelos. Em um mesmo mapa, é possível visualizar de forma superposta informações de terreno (modelo matricial com fotos de satélite) e desenhos com ruas, avenidas e pontos de referência (modelo vetorial). Os campos de aplicação dos Sistemas de Informação Geográfica, por serem muito versáteis, são muito vastos, podendo-se utilizar na maioria das atividades com um componente espacial, da cartografia a estudos de impacto ambiental ou vigilância epidemiológica de doenças, de prospecção de recursos ao marketing, constituindo o que poderá designar de Sistemas Espaciais de Apoio à Decisão. Dada a versatilidade do georeferenciamento de informações, é possível encontrar aplicações dos mais variados tipos à disposição dos usuários. O foco inicial dos SIGs nas áreas de cartografia e vigilância ambiental está migrando, atualmente, para as áreas de interação social, disseminação dos mais variados tipos de informação e, notadamente, comércio, propaganda e logística. Além da disseminação dos SIGs no comércio, eles estão migrando cada vez mais do uso em computadores pessoais (desktop) para o uso em dispositivos móveis. Neste sentido, o mercado vem investindo de forma significativa, dado o potencial associado à capacidade de geolocalização. Algumas aplicações SIG, como as que serão apresentadas nas seções seguintes, embora conceitualmente simples, são notáveis em utilidade e funcionalidade, cada qual em sua área de interesse. 2.1 Foursquare Foursquare é uma plataforma de localização móvel, uma rede social, e um micro blog, baseada em geolocalização, que permite ao utilizador indicar onde se encontra e procurar por contatos que estejam próximo desse local. [Foursquare 2011]. A aplicação móvel está disponível para celulares, através de SMS, ou smartphones, com suporte à ios, Android, Windows Mobile, Blackberry e Symbian. O serviço Foursquare recolhe dados pessoais dos utilizadores e partilha-os com outros, por iniciativa e consentimento do utilizador do serviço. O serviço é baseado na partilha e comunicação da localização, por vontade própria, dos seus utilizadores. Segundo informações da própria Foursquare, havia passado de 100 milhões a quantidade de atualizações de dados em diferentes locais no mês de julho de A taxa de crescimento de entrada de usuários vêm de 1 milhão de atualizações, no ano de 2010, para mais de 40 milhões nos últimos dois meses de A utilização do serviço se dá através de um dispositivo móvel, como celular ou smartphone. O usuário do serviço acessa o site, ativa seu perfil, identifica o local onde
17 CAPÍTULO 2. SISTEMAS DE INFORMAÇÃO GEOGRÁFICA 7 está via GPS, e informa a informação desejada já georeferenciada. O usuário pode ainda compartilhar sua localização com outras pessoas, via Facebook ou Twitter. 2.2 WAZE Geralmente chamado de GPS social, o Waze é um aplicativo que funciona em smartphones dotados dos sistemas operacionais Android, ios, Symbian e Windows Mobile. A proposta do sistema é permitir que usuários compartilhem em tempo real informações de trânsito e tráfego, podendo evitar problemas comuns como acidentes, engarrafamentos e blitz. [Waze 2010] O funcionamento do sistema é bem simples. Quando o motorista entra no carro, deverá ativar o aplicativo do Waze em seu smartphone e deixá-lo em funcionamento. Enquanto dirige, o aplicativo envia pela Internet informações sobre a velocidade de seu veículo e, também, coleta informações da Internet acerca da velocidade da via e de outras subjacentes. Se a velocidade da via estiver baixa, o aplicativo marca a via em cores vibrantes, sugerindo que outros usuários evitem a região. Outra funcionalidade oferecida pela ferramenta é a comunicação de acidentes. Se o motorista usuário do Waze estiver preso em um engarrafamento motivado por acidente, ele pode, tirar uma foto do local e enviá-la através do programa. Os outros usuários da rede, denominado wazers, receberão essa informação na hora e visualizarão a foto. No Brasil, o serviço ainda é bem limitado, dada a pequena quantidade de usuários. Como a base de dados é mantida por voluntários, ainda faltam mapas das ruas nas principais cidades. O serviço provido pela Waze, entretanto, é capaz de deduzir possíveis ruas, melhorar a geometria de ruas existentes e corrigir sentido de ruas. 2.3 WikiMapa O WikiMapa é um mapa virtual alimentado de forma colaborativa por diversos participantes, por meio do telefone celular ou Internet. [WikiMapa 2011]. O projeto foi lançado em 2009 pelo Programa Rede Jovem, da ONG Comunitas, que atua em comunidades de baixa renda oferecendo à juventude oportunidades de interação com as novas tecnologias. Com o WikiMapa é possível inserir informações sobre diferentes lugares de interesse público (hospitais, escolas, comércios, praças, quadras esportivas, restaurantes, bares, entre outros) em quaisquer lugar do Brasil e do mundo, como também consultar e editar
18 CAPÍTULO 2. SISTEMAS DE INFORMAÇÃO GEOGRÁFICA 8 comentários e referências sobre os locais já mapeados. Esse mapeamento pode ser feito por qualquer pessoa que tenha cadastro no site do WikiMapa e/ou o programa instalado em um celular com GPS, permitindo a inserção das informações, coleta da localização e também compartilhamento das experiências em blogs dentro do site do projeto. O diferencial do projeto é o mapeamento de ruas e vielas de comunidades de baixa renda, que até então não tem sido realizados pelos serviços de pesquisa e visualização de mapas na Internet, além do mapeamento dessas comunidades, realizado pelos próprios moradores. Em sua fase piloto, cinco comunidades cariocas foram mapeadas: Complexo do Alemão, Complexo da Maré, Cidade de Deus, Santa Marta e Pavão-Pavãozinho. Em cada uma tem um jovem morador, responsável por identificar caminhos e locais de interesse, iniciando a construção do mapa georeferenciado de sua comunidade, tornando sua cultura e geografia conhecidas por qualquer usuário do WikiMapa. O Programa Rede Jovem recebeu em 2010 quatro grandes prêmios devido à experiência adquirida com o projeto Wikimapa e foi, ainda, a única iniciativa da América Latina indicada como finalista ao prêmio Mobile Monday Peer Awards, na categoria Bottom of the Pyramids. 2.4 Wikimapia Wikimapia é um sistema de busca e mapeamento na Internet que utiliza imagens de satélite do planeta Terra para identificar os locais mostrados, desde pequenos comércios até cidades inteiras. O serviço se baseia nas imagens de satélite como as providas pelo Google Maps. O sistema wiki é aplicado na forma de localização de lugares, pois qualquer pessoa tem a permissão (sendo registrado) de inserir um local no mapa até mesmo editar os locais já criados. [Wikimapia 2011] O WikiMapia foi apresentado em 2006 pelos russos Alexandre Koriakine e Evgeniy Saveliev. A aplicação dispõe de várias funcionalidades de edição de mapas, principalmente através do uso de polígonos que permitem definir precisamente a área do local marcado - e ferramentas lineares, como estradas, ferrovias e rios. No princípio, todos os usuários editavam anonimamente e não havia mecanismos de monitoramento de usuários problemáticos ou vândalos. Em outubro de 2006, criou-se o sistema de registro de usuários. Apesar disso, o registro não se tornou obrigatório e ainda hoje é permitida a colaboração como usuário não registrado. Posteriormente, adotaram-se diferentes níveis de usuários, permitindo que usuários mais experientes que
19 CAPÍTULO 2. SISTEMAS DE INFORMAÇÃO GEOGRÁFICA 9 sejam considerados confiáveis (chamados de usuários nível 2, ou usuários avançados) ganhassem maiores capacidades, como proteger regiões ou banir vândalos. A marcação dos locais envolve basicamente a definição da área ocupada, título, descrição, endereço, categorias. Um link para artigos da Wikipédia descrevendo o local, é também incentivado, havendo campos específicos para este fim. Os usuários podem ainda adicionar fotos dos locais. Na descrição é permitida a inserção de links para páginas da web e vídeos do Youtube, por exemplo. As categorias são usadas para que se possa filtrar a visualização, permitindo se ver apenas os locais marcados com certa categoria. Os locais marcados podem ser descritos em 101 idiomas diferentes, enquanto a interface do usuário já foi traduzida para 56 idiomas. 2.5 Comob Comob é um projeto de arte digital que explora o potencial do mapeamento colaborativo com a tecnologia GPS. Comob foi desenvolvido como uma ferramenta de pesquisa para explorar as relações sociais e espaciais entre as pessoas em movimento [Comob 2011]. Ele atualmente é suportado nas plataformas suporta aplicações para iphone e Nokia que explora mapeamento colaborativo com a tecnologia GPS. O sistema permite que os membros de um grupo compartilhado vejam a posição e a movimentação do outro em tempo real em seus telefones móveis. O grupo é interligado por uma linha que mostra a sua distribuição espacial relativa. 2.6 Avaliação das ferramentas pesquisadas no escopo do trabalho proposto Aplicações como estas que foram descritas nas seções anteriores revelam um aspecto interessante sobre interações sociais no mundo digital: muitos estão dispostos a colaborar em prol do bem comum. De fato, quanto mais bem alimentados forem os bancos de dados de cada ferramenta, mais bem informados estarão seus usuários. Entretanto, dois aspectos importantes podem ser observado nestas e em outras propostas de sistemas de georeferenciamento colaborativo existentes. Um deles é o fato de as aplicações estarem cada vez mais voltadas para o mercado de dispositivos móveis. O outro é que a grande maioria das aplicações são desenvolvida em países de primeiro mundo, onde as malhas viárias geralmente são bem cuidadas e a educação no trânsito é realmente levada à sério.
20 CAPÍTULO 2. SISTEMAS DE INFORMAÇÃO GEOGRÁFICA 10 No Brasil, não são raras as falhas em vias públicas e regiões de perigo. Entenda-se por regiões de perigo os trechos de rodovia que, embora possam estar livres de falhas na via, são palco de constantes acidentes de trânsito (ex: trechos com baixa visibilidade, curvas acentuadas e locais de constantes transgressões de motoristas). O uso de navegação automotiva assitida por GPS não se faz necessário para os usuários quando as rotas de chegada ao destino são conhecidas. Exemplos típicos destes usuários são motoristas de ônibus de linhas interestaduais e caminhoneiros. Para estes usuários, a existência de uma ferramenta que os lembre de pontos de perigo oferecem grande utilidade em suas viagens de transporte de passageiros e cargas. As ferramentas comerciais disponíveis, embora sejam capazes de orientar motoristas sobre rotas de viagem, são inúteis para realizar alertas de falhas e pontos de perigo. Neste sentido, a proposta do trabalho vem preencher esta lacuna, oferecendo um sistema que pode ser usado pelas mais variadas categorias de motoristas para melhorar sua proteção durante seus deslocamentos entre localidades. Ademais, a ferramenta não deverá demandar a presença constante de um canal de comunicação para que mapas e pontos de interesse sejam carregados para o dispositivo móvel. A atualização dos dados poderá ser feita pelo usuário apenas nos locais onde canais de comunicação estiverem disponíveis. Tal funcionalidade é útil, tanto no sentido de que nem sempre sinais de rádio estão presentes nas vias de transporte estadual ou interestadual, quanto no sentido da redução de custos de comunicação, geralmente associados à transmissão de dados por operadoras de telefonia móvel. Para desenvolver a proposta do trabalho, que é a marcação de pontos de perigo de forma colaborativa, é necessário considerar a marcação redundante de pontos pelos usuários e, inclusive, a remoção de pontos de perigo, por exemplo, em falhas já consertadas em vias danificadas. Para isso, o uso de algoritmos de aglomeração de dados que reduzam esta redundância são necessários e valiosos para oferecer ao usuário mapas condensados. Estes mapas deverão representar as informações de alerta de forma a exigir o mínimo de recursos de memória para o dispositivo móvel e evitar aborrecer o usuário com repetições (o que poderia desestimular o uso da ferramenta). A seleção do algoritmo de aglomeração apropriado será discutida no capítulo seguinte.
21 Capítulo 3 Aglomeração de dados Os algoritmos de aglomeração englobam uma categoria de algoritmos que buscam reunir objetos em grupos homogêneos [Frei 2006]. Eles representam uma das principais etapas de processos de análise de dados, denominada análise de clusters [Jain et al. 1999]. Aglomeração de dados é um processo de particionamento de uma quantidade de dados em grupos, ou clusters e, por natureza, operam de forma não supervisionada. Em outras palavras, algoritmos de aglomeração não requerem conhecimento prévio dos grupos de dados para poderem agir sobre um conjunto de dados. O critério usado para aglomerar os grupos é geralmente alguma medida de similaridade ou distância. Como resultado do processo, elementos originalmente separados são organizados em conjuntos denominados de clusters. Um exemplo de medida de similaridade é a distância euclidiana. Os algoritmos de aglomeração colocam no mesmo cluster elementos que têm mais semelhança entre eles, maximizando então as semelhanças entre elementos dentro do cluster. De forma concomitante, elementos de diferentes clusters apresentam menor similaridade entre si, minimizando, então, as similaridades entre grupos. Assegurar estas características é uma importante etapa do processo de análise de dados, tradicionamente conhecida de análise de clusters [Jain et al. 1999]. Algoritmos de aglomeração podem ser divididos em dois grupos principais: algoritmos hierárquicos e não hierárquicos [Jain et al. 1999, Larose 2005]. Os algoritmos hierárquicos criam uma hierarquia de clusters, que podem ser representados em uma estrutura de árvore chamada dendrograma. Eles podem ser divididos em mais duas categorias: algoritmos aglomerativos e divisivos. O algoritmo hierárquico aglomerativo têm uma abordagem bottom-up, ou seja, o processo inicialmente assume cada elemento de dado como um cluster diferente. Então, o algoritmo vai juntando de forma iterativa dois clusters, que têm maior semelhança e prosseguindo neste processo até que no final exista apenas um cluster ou até que outro critério de parada seja alcançado, como o limite no número de clusters, por exemplo.
22 CAPÍTULO 3. AGLOMERAÇÃO DE DADOS 12 Diferente do aglomerativo, o algoritmo divisivo apresenta abordagem top-down. Começa o processo com apenas um cluster contendo todo o conjunto de dados. A cada passo do algoritmo, esse cluster é dividido recursivamente seguindo métricas de comparação, até que cada elemento represente o seu próprio cluster. Ao fim do processo, ou o número de clusters é igual à quantidade de dados ou até algum outro critério de parada ser alcançado, tal como o número máximo de clusters alcançado. Os algoritmos não-hierárquicos (ou particionados) normalmente particionam os dados uma única vez em um determinado número de clusters especifico, ao invés de uma estrutura interligada, como o dendrograma produzido pela técnica hierárquica. Métodos particionados têm vantagens em aplicações que envolvam grandes conjuntos de dados para os quais a construção de um dendrograma é computacionalmente custosa. Esta característica coloca a escolha de algoritmos particionados como candidatos naturais para aplicação no problema proposto neste trabalho. Uma das limitações que geralmente acompanha o uso de um algoritmo divisivo é a escolha do número de clusters desejado.[jain et al. 1999]. Entretanto, existem soluções elegantes que conseguem contornar esta limitação. Dos algoritmos particionados, talvez o mais conhecido seja o algoritmo k-means [MacQueen 1967]. O algoritmo surgiu em 1967 e sua proposta é processar um conjunto de dados n-dimensionais agrupando os elementos em uma quantidade pré-determinada de grupos. Dado um conjunto n-dimensional, o algoritmo k-means visa particionar o conjunto de dados em k clusters. Ao final do processamento, o algoritmo encontrará k centros, um para cada cluster. Cada centro é representado por um elemento n-dimensional c i,i = 1...k, que é o ponto médio (ou centro) de cada cluster. Os centros obtidos pelo algoritmo k- means podem ser usados para fazer a classificação de um elemento de prova em busca do melhor grupo em que esse possa ser inserido. O algoritmo k-means funciona conforme os seguintes passos: 1 - Dado o valor de k, número de clusters a serem gerados, são escolhidos aleatoriamente k elementos para serem os centros dos clusters, geralmente do próprio conjunto de entrada. 2 - Para cada elemento do conjunto de dados: Encontrar o cluster que tem a maior similaridade com o elemento, com base na medida de distância Definir este elemento como pertencente ao respectivo cluster. 3 - Para cada cluster:
23 CAPÍTULO 3. AGLOMERAÇÃO DE DADOS Atualizar os valores dos centros como sendo a média dos elementos pertencentes ao cluster. 4 - Repetir os passos 2 e 3 até que se atinja a convergência, por exemplo, quando a distância entre o centro em um passo anterior e o passo atual for menor que um limiar pré-estabelecido. Como exemplo de aplicação do algoritmo, considere um sistema de classificação de tumores de pele. O sistema recebe informações do tipo curvatura, tamanho, textura e cor e deve ser capaz de orientar seu usuário acerca da melhor classificação do tumor sub judice. Entretanto, o sistema precisa ser treinado com exemplos previamente rotulados por especialistas, descrevendo a benignidade ou malignidade dos exemplos. O algoritmo k-means pode ser usado neste problema para processar os exemplos e agrupá-los em dois conjuntos (benignos e malignos), gerando centros correspondentes para cada um. Rotulados os centros com base nas informações fornecidas pelos especialistas, estes podem ser usados para classificar uma nova amostra, usando a mesma medida de distância escolhida para o treinamento. Embora seja aplicável a diversos tipos de problemas de aglomeração, o algoritmo k-means possui uma limitação que o impede de ser usado no problema proposto. O número de centros deve ser previamente definido. Sendo assim, alternativas que permitam a aglomeração de pontos sem a prévia fixação da quantidade de centros precisam ser consideradas. Dos algoritmos pesquisados, um deles chama a atenção pela forma como realiza o processo de aglomeração. A criação do centro se dá pela fixação do seu limite de diâmetro, que é justamente o que se busca para o caso do sistema de alerta proposto. O algoritmo é denominado QT clustering e será descrito na seção a seguir, bem como as justificativas que embasam sua escolha. 3.1 QT clustering O algoritmo de aglomeração Quality Threshold clustering (ou QT clustering) foi desenvolvido por Heyer, Kruglyak e Yooseph para aglomeração genes de DNA [Heyer et al. 1999]. O algoritmo requer um maior custo computacional que o algoritmo k-means, possui custo exponencial, porém não exige a definição do número de clusters a priori, como no k-means. Execuções distintas do QT clustering fornecem sempre o mesmo resultado.
24 CAPÍTULO 3. AGLOMERAÇÃO DE DADOS 14 Ao invés do número de clusters, esse algoritmo recebe como entrada um valor limite para o diâmetro do cluster. Sendo assim, o foco desse algoritmo é encontrar clusters cujos diâmetros não ultrapassem o limiar fornecido. O algoritmo segue os seguintes procedimentos: 1. O primeiro aglomerado candidato é formado começando pelo primeiro elemento amostrado do conjunto de entradas; 2. Os demais elementos do conjunto são adicionados iterativamente, dado que cada elemento escolhido minimiza o aumento do diâmetro do aglomerado candidato. O processo continua até que o diâmetro do aglomerado candidato não ultrapasse o limiar; 3. Um segundo aglomerado candidato é formado pelo segundo elemento do conjunto e o mesmo processo de formação descrito na etapa anterior é repetido para todos os dados do conjunto de entrada; 4. O processo é repetido para todos os elementos do conjunto, de sorte que o número de aglomerados candidatos seja igual ao número de elementos no conjunto de entrada; 5. O aglomerado candidato com maior número de dados é selecionado como um aglomerado titular e os dados contidos nele são removidos dos outros aglomerados candidatos; 6. O processo de seleção de titulares é repetido para todos os aglomerados candidatos até o último aglomerado; 7. O centro de cada aglomerado é assumido como sendo posição do elemento que o originou. Um possível critério de parada é quando o cluster restante contiver menos que um número de elementos especificado. O Algoritmo 1 mostra o funcionamento do QT clustering. A idéia do algoritmo, embora simples, possui aplicação direta no problema proposto. Considere a situação onde o sistema de alerta precise avisar um motorista de um ponto de perigo que se encontra adiante no curso da via. Emitido o alerta, o motorista deveria ser capaz de reagir ao alerta, iniciar o processo de frenagem e parar, antes de atingir o ponto de perigo, para se por em segurança. A distância percorrida entre o início da reação e a parada do veículo é denominada distância de parada e, usando cálculos simples, pode ser estimada conforme a velocidade do veículo e tipo de pista. Para um veículo se deslocando a 110 km/h em pista seca, a distância de parada pode ser estimada em aproximadamente 150m [Seguras 2011].
25 CAPÍTULO 3. AGLOMERAÇÃO DE DADOS 15 Algoritmo 1 QT clustering(g,d). Recebe como dados de entrada o conjunto G e um diâmetro d, e retorna um conjunto de clusters limitados em tamanho pelo diâmetro fornecido. Fonte: [Heyer et al. 1999] 1: if G 0 then 2: return G 3: else 4: for all i G do 5: f lag T RUE 6: A i {i} 7: while ( f lag = T RUE)&(A i G) do 8: Encontre j (G A i ) em que o diâmetro de (A i { j}) é mínimo 9: if diâmetro de (A i { j}) > d then 10: f lag FALSE 11: else 12: A i A i { j} 13: end if 14: end while 15: end for 16: end if 17: Identifique o conjunto C {A 1,A 2,...,A G } com a máxima cardinalidade 18: return C 19: QTclustering(G C, d) Criando clusters, por exemplo, com limite de diâmetro de 300m, seria possível marcar pontos de perigo representativos de aglomerados que estejam a aproximadamente 150m de distância de um motorista posicionado no limite do aglomerado. Assim, motoristas se deslocando a 110 km/h se avisados quando estiverem a 150m de distância do ponto representativo, poderiam reduzir a velocidade com segurança até atingir o obstáculo. Embora possa ser estimado um valor mínimo para essa distância de alerta, esta grandeza poderá também ser definida pelo próprio usuário da ferramenta, através do estabelecimento de parâmetros em uma interface de usuário. Estudos heurísticos podem ser realizados usando, por exemplo, opiniões e dados coletados dos próprios usuários da ferramenta para determinar um diâmetro adequado para os centros dos aglomerados e distância padrão para alertas, nem tão pequena que irrite os motoristas com alertas excessivos, nem tão grande que instrua o sistema a realizar alertas demasiadamente antecipados.
26 Capítulo 4 Trabalho proposto O presente trabalho propõe o desenvolvimento de um Sistema Informação Geográfica (SIG) colaborativo capaz de agregar tecnologias muito difundidas e de fácil acesso, como as ferramentas localização geográfica, cartografia digital e interatividade com a Internet, usando smartphones. São agregados um sistema de geração de alertas, através de um dispositivo móvel, que avisa da proximidade de pontos de perigo nas vias de transporte, e um sistema de aglomeração de dados para coletar e processar informações dos seus diversos usuários. Para funcionar, o sistema precisa ter a priori as coordenadas geográficas desses pontos cadastradas em uma base de informações. Estas coordenadas deverão ser fornecidas pelos usuários enquanto estiverem trafegando nas vias. Os pontos deverão ser enviados a um servidor que irá processá-los e gerar uma lista representativa de pontos de perigo. Uma vez recuperada esta lista, o usuário poderá utilizá-la durante a navegação em conjunto com a lista dos pontos por ele marcados. 4.1 Funcionamento do sistema Uma visão geral do sistema proposto é apresentada na Figura 4.1. Nesta figura, cada número identifica uma fase do processo de armazenamento, tratamento e recuperação de informações do servidor SIG. O processo de construção da base de informações tem início pela iniciativa dos seus usuários, que alimentam o sistema marcando nos dispositivos móveis os pontos de perigo e os enviam ao servidor SIG (1). O servidor armazena os pontos fornecidos em um banco de dados (2), relacionando as marcações realizadas pelos usuários. Os pontos presentes na base de dados de usuários são enviados para processamento e geração periódica dos aglomerados através do algoritmo QT clustering (3). O resultado do processamento é armazenado no banco de dados (4) para consultas (5) e atualização de pontos de perigo (centros dos aglomerados) nos clientes móveis (6). Os dados presentes
27 Esc ~ `! # $ % ^ & * ( ) _ - + = { < Num Lock 7 / \ Scrn Print SysRq Scroll Lock : ', } ] > ". Pause? Insert / Break Alt Gr Home Delete Page Up End Page Down Ctrl * End 2 + PHONE MIC LINE-IN USB SATA AUDIO CARD READER 0 3 Ins PgDn. EJECT Del POWER Enter CAPÍTULO 4. TRABALHO PROPOSTO 17 no servidor de banco de dados também podem ser acessíveis de forma integrada com clientes desktop (6), no caso da necessidade de visualização ou manipulação dos pontos superpostos com mapas digitais em um computador. LCD-Pro DVD-RW MENU SELECT - + Cliente móvel 1 6 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F 1 F Q W E R T Y U I O P [ A S D F G H J K L Z X C V B N M Caps Lock ; Shift Shift Ctrl Alt Num Lock CapsLock Scroll Lock Cliente desktop Home PgUp Internet 5 4 Banco de dados 2 4 Servidor SIG 3 QT clustering/ Processamento auxiliar Figura 4.1: Arquitetura do sistema proposto para marcação e aglomeração de pontos. 4.2 Marcação de pontos Em se tratando de um sistema de alerta colaborativo, o usuário deve ser capaz de marcar de forma simples e rápida a presença de algum ponto de perigo na via em que estiver trafegando. A marcação deverá ser feita no dispositivo móvel através de
28 CAPÍTULO 4. TRABALHO PROPOSTO 18 botões presentes na interface do aplicativo. Da mesma forma que a marcação de pontos candidatos a inclusão na base de informações é permitida, também será permitida a marcação de pontos candidatos a remoção da base de dados. Esta situação poderá ocorrer, por exemplo, para falhas na via marcadas pelos usuários e já foram reparadas. A interface de usuário proposta para o sistema é mostrada na Figura 4.2. (10:30h) GPS ok! Iniciando navegação (10:40h) Inserida falha na via (10:42h) Trecho perigoso a 200m (10:53h) Zona livre marcada (10:55h) Inserida falha na via (14:00h) Base de dados sincronizada TRECHO PERIGOSO FALHA NA VIA ZONA LIVRE Figura 4.2: Interface de usuário para dispositivo móvel. Na tela da interface do usuário são propostas quatro regiões principais: uma região superior para apresentação de informações (distância para pontos de perigo, iterações com o aplicativo, etc) e três regiões sensíveis ao toque, sendo dois botões centrais para marcação de pontos de perigo e um botão inferior para a marcação de zonas livres. Os pontos de perigo serão classificados em duas categorias: falhas na via (caracterizadas pela associação a buracos e ondulações, por exemplo) e zonas de perigo (associadas a curvas fechadas e pontos de ultrapassagem perigosos, por exemplo). Cada categoria poderá gerar um alerta diferenciado para o usuário, bem como prover às entidades govenamentais dados para melhorarem a sinalização e manuntenção das vias, dadas as opiniões dos próprios motoristas acerca do que consideram trechos perigosos. A marcação de zonas livre, associada à remoção de pontos, é feita pelo acionamento do botão zona livre.
29 CAPÍTULO 4. TRABALHO PROPOSTO 19 A interface oferece alertas sonoros para não desviar a atenção visual do motorista enquanto percorre o curso da rodovia. Com isso, a ferramenta desenvolvida não oferece insumos que motivem os motoristas a desobedecer a legislação de trânsito, desviando o foco da atenção. Dessa forma, a interação entre usuário e ferramenta funciona de forma semelhante à do navegador GPS convencional, onde este vai ditando as informações ao motorista. A alimentação da plataforma móvel com as marcações se dá quando o usuário acionar as regiões correspondentes no seu smartphone. Entenda-se como usuário, durante procedimento de marcação, aquele que vai manipular a plataforma móvel (que pode ser um dos passageiros que acompanham o motorista durante a viagem). Para cada ponto marcado são armazenadas as suas coordenadas geográficas, latitude e longitude, data e hora da marcação, bem como o tipo de ponto selecionado (falhas na via ou zonas de perigo). O envio dos pontos da plataforma móvel para o servidor SIG não é imediata. Parte-se do princípio que, em zonas rurais, normalmente sinais de rádio que permitiriam conexões de dados estão indisponíveis. Portanto, os pontos podem ser enviados para o servidor SIG para futuro processamento através de um processo de sincronização, quando uma conexão com a Internet estiver disponível. O envio das informações para o servidor SIG é feito em lote, quando então as informações dos novos pontos presentes no smartphone são transferidos. Quando os dados chegam ao servidor, estes são submetidos a técnicas de processamento inteligente para escolher os pontos de alerta. Pressupõe-se que a marcação do ponto de perigo na via não deva ser exatamente a mesma para todos os motoristas. Quando um usuário passa por um ponto de perigo e realiza a marcação no seu aparelho móvel, esta poderá ocorrer em pontos aproximados ao ponto de perigo real, devido ao retardo ou antecipação associados à ação do usuário, ou precisão do receptor GPS do dispositivo móvel. A falha pode ser marcada, portanto, antes ou depois de o veículo passar pelo ponto. Além disso, vários usuários podem marcar a mesma falha mais de uma vez, resultando em redundância de informações em torno dos pontos de perigo. Sendo assim, ocorre a necessidade de consolidar estes vários pontos marcados e selecionar um único ponto de perigo associado às marcações sugeridas. Exemplos de nuvens de pontos que podem ser marcadas no processo colaborativo são mostradas na Figura 4.3. Nesta figura, os pontos marcados pelos usuários são representados com uma cruz e o ponto representativo de uma aglomerado gerado após tratamento por técnicas inteligentes é destacado com um círculo.
30 CAPÍTULO 4. TRABALHO PROPOSTO 20 Ponto representativo Pontos de perigo Curso da via Cursos das vias Falhas nas vias Trechos perigosos Figura 4.3: Exemplo de nuvens formada pela marcação de vários motoristas com seu ponto representativo e os diferentes tipos de nuvens com pontos de perigo que podem ser marcados nos cursos das vias. 4.3 Processamentos dos dados É no contexto da Figura 4.3 que o processamento dos pontos colhidos pelos usuários do aplicativo torna-se necessário para produzir apenas pontos de perigo significativos. Para problemas dessa natureza, algoritmos de aglomeração são candidatos naturais para uso no sistema de marcações. A geração dos pontos representativos dos aglomerados de marcações fornecidas pelos usuários deve ser feita de modo a remover as possíveis redundâncias que porventura sejam fornecidas por diferentes usuários. No caso desse trabalho, demanda-se um algoritmo de aglomeração que não exija a determinação a priori da quantidade de aglomerados a serem formados, visto que não existe a possibilidade de saber de antemão quantos pontos de perigo poderão existir em uma via.
31 CAPÍTULO 4. TRABALHO PROPOSTO 21 Os aglomerados de pontos deverão ser formados nas proximidades dos pontos de perigo, conforme as marcações dos usuários, devendo esta condição se repetir para cada ponto de perigo real (ver Figura 4.3). Acredita-se que o diâmetro dessas nuvens tenda a ser regular, devendo assumir forma geralmente elíptica. Tais conjecturas são baseadas no tempo de observação e reação média dos usuários, promovendo a forma do eixo maior da elipse, e na precisão do GPS, promovendo a expansão do eixo menor. Diante das peculiaridades do sistema proposto, o algoritmo QT clustering apresentado na seção 3.1 foi escolhido como candidato à criação dos centros que marcam os pontos de perigo. O servidor SIG, em atividades escalonadas periodicamente, determina os centros dos aglomerados via QT clustering, e torna estes centros disponíveis aos usuários para atualização das bases de informação móveis. O uso do algoritmo de aglomeração QT clustering possibilita amenizar a redundância de marcações, oferecendo para um usuário apenas os pontos mais significativos de perigo, de modo a orientá-lo sem excesso de informações. Neste trabalho, foi escolhida uma distância de 300 metros como diâmetro máximo dos aglomerados, assumindo que, para este diâmetro, é oferecido um limite mínimo para alertar o motorista com segurança. 4.4 Remoção de pontos Para os aglomerados formados em torno dos ponto de perigo, centros correspondentes serão determinados pelo próprio algoritmo de aglomeração. O processo de criação ou atualização destes pontos de perigo deve prever, também, a situação onde a existência de determinados pontos de perigo não seja mais necessária. Um exemplo típico dessa situação é propiciada pelo reparo de um buraco na rodovia que fôra marcado como ponto de perigo. Em casos como esses, os usuários da ferramenta poderão realizar uma marcação do tipo zona livre (ver Figura 4.2), indicando a inexistência de fatores capazes de gerar perigos na região marcada. Os pontos marcados como zona livre também participam do processo de aglomeração, influindo negativamente na inclusão ou manutenção de centros novos ou existentes, respectivamente. O processamento desses pontos pelo algoritmo de aglomeração leva em conta informações tais como o momento em que os pontos foram inseridos na base de dados de pontos de perigo e a quantidade de marcações do tipo zona livre. Os pontos marcados como zona livre não provocam a criação de novos aglomerados. Eles servem apenas para decidir se os aglomerados dos quais participam são ou não candidatos à remoção. Para decidir a remoção de um aglomerado da base de dados foi utilizada uma
32 CAPÍTULO 4. TRABALHO PROPOSTO 22 heurística simples com base em um limiar K preestabelecido. Calcula-se a idade média dos pontos de perigo mais recentes no aglomerado e dos pontos de zona livre mais recentes no mesmo aglomerado e compara-se as duas médias. Caso a média de idade dos pontos de zona livre supere a média de idades dos pontos de perigo e o número de pontos de zona livre atinja o limiar K, todo o aglomerado é removido da base de dados. No protótipo desenvolvido, escolheu-se um limiar K = 3 como parâmetro para controlar a remoção de aglomerados. A heurística proposta foi escolhida com base em algumas suposições acerca do uso da plataforma móvel. Caso um usuário receba um alerta de ponto de perigo e o ponto realmente exista, dificilmente ele marcará novamente este ponto na ferramenta como sendo ponto de perigo, uma vez que foi avisado corretamente da presença do ponto. Neste caso, as idades das marcações dos pontos de perigo tendem a ser mais antigas que as idades das marcações de zona livre. Caso um usuário receba um alerta de ponto de perigo e o ponto não exista, a realimentação natural será marcar aquele ponto como zona livre, para evitar futuros alertas. O limiar para remoção de aglomerados mencionado no parágrafo anterior visa impedir a remoção prematura de pontos de perigo, requerendo que alguns usuários colaborem na confirmação da zona livre marcada. É importante observar que o mesmo limiar inexiste para a marcação de um ponto de perigo, justamente para que prevaleça o zelo na marcação de possíveis perigos presentes nas vias. 4.5 Alertas de perigo O sistema de alerta para o dispositivo móvel oferece alerta sonoros, informando ao motorista da proximidade de algum ponto de perigo na via em que ele estiver trafegando. Para chamar atenção do motorista, o alerta sonoro pode sintetizar fala para informar ao motorista a distância para o ponto de perigo e o tipo de perigo que está eminente. A plataforma de testes na qual o protótipo da ferramenta foi criado, a plataforma Android(http://www.android.com), já dispõe deste recurso para o desenvolvedor. Para gerar os alertas, o programa em execução na plataforma móvel deverá constantemente recuperar as coordenadas geográficas locais via GPS, calcular a distância do usuário para o ponto de perigo mais próximo, e avisar o usuário conforme os alertas programados na interface de usuário. Embora os aglomerados sejam gerados com diâmetro fixo, a distância mínima de alerta poderá ser definida pelo próprio usuário.
33 CAPÍTULO 4. TRABALHO PROPOSTO Interface desktop A visualização das posições dos pontos pode ser feita na própria plataforma móvel utilizando os recursos de apresentação de mapas disponibilizados pela Google. Apesar desta comodidade, uma interface desktop é também disponibilizada para possibilitar a exibição dos pontos de perigos juntamente com a ferramenta Google Maps. A interface desktop é capaz de oferecer uma interação visual mais rica e poderá servir como fonte de insumos para os órgãos responsáveis pela conservação e manutenção das vias de transporte realizarem procedimentos de recuperação ou melhor sinalização das vias. Cruzando informações fornecidas pelas marcações geradas pela ferramenta proposta com informações do próprio DNIT, medidas colaborativas entre cidadãos e o Estado podem ser tomadas para melhorar a qualidade das vias públicas e diminuir a quantidade de acidentes. A exibição dos centros gerados pelo algoritmo pode ser feita diretamente através de uma página web pela integração com a ferramenta Google Maps. Os recursos de desenvolvimento disponibilizados pela Google permite que os pontos seja exibidos na forma de uma camada (layer) integrada ao próprio navegador. Com isso, o usuário poderá visualizar a representação dos pontos de perigo juntamente com fotos de satélite contemplando a região onde são situados. O protótipo desenvolvido para este trabalho é ilustrado na Figura 4.4. Figura 4.4: Protótipo da interface desktop para visualização de centros usando os recursos do Google Maps.
34 CAPÍTULO 4. TRABALHO PROPOSTO Sincronização e expurgo de dados A sincronização entre as marcações presentes na plataforma e as marcações fornecidas a esta pelo servidor SIG é outro aspecto importante que precisou ser considerado. Ao enviar ou receber informações, a ferramenta presente no dispositivo móvel precisa estar alerta para não enviar dados repetidos ou desnecessários ao servidor SIG. Da mesma forma, precisa ser capaz de evitar possíveis redundâncias oriundas dos dados recebidos deste servidor. Visando contornar tais problemas, estratégias de rotulação e processamento adicionais foram também incorporadas à ferramenta móvel. Para fins de sincronização, os pontos de perigo receberam os seguintes rótulos adicionais (além dos rótulos de trecho perigoso e falha na via): Novo: Ponto marcado pelo usuário, mas que ainda não foi comunicado ao servidor SIG. Sincronizado: Ponto marcado pelo usuário e que já foi comunicado ao servidor SIG. Centro: Ponto recebido pelo servidor SIG, resultado do processamento dos aglomerados via algoritmo QT clustering. Na interface da ferramenta móvel, são providas funcionalidades para permitir que o usuário envie os pontos para o servidor remoto. Nesta etapa, os pontos dotados do rótulo Novo têm seus rótulos substituídos por Sincronizado e são então enviados ao servidor SIG, evitando assim o envio redundante de marcações ao servidor. A recuperação dos centros gerados também é feita por intervenção do usuário na interface da ferramenta móvel. Durante o processo, os pontos locais marcados como centro são substituídos pelos novos centros recuperados. O processo de marcação de zonas livres também sofre processamento adicional na ferramenta móvel e possui processo de sincronização ligeiramente diferente dos pontos de perigo. Cada marcação de zona livre realizada pelo usuário inicia duas ações a serem tomadas. A primeira ação, realizada imediatamente, consiste em marcar para remoção na base de dados local todos os pontos de perigo marcados dentro de um raio igual à metade do diâmetro estipulado para o tamanho máximo dos aglomerados. A segunda ação consiste em comunicar ao servidor SIG, durante a etapa de recuperação de centros, os pontos marcados como zona livre. Uma vez enviados, eles são então removidos da base de dados local, posto que sua presença torna-se inútil na ferramenta.
35 CAPÍTULO 4. TRABALHO PROPOSTO Modelo do sistema O sistema desenvolvido é composto principalmente por três módulos, são eles o MÓVEL, o WEB e o CORE, como ilustrado na Figura 4.5. Figura 4.5: Módulos do sistema Cada módulo do sistema utiliza tecnologias adequadas as suas especificidades. A Figura 4.6 mostra mais detalhes sobre cada um dos módulos, especificando as plataformas utilizadas para desenvolvimento de cada um deles. O módulo móvel foi desenvolvido utilizando a linguagem de programação Java, dadas as exigências da plataforma/sistema operacional Android. Para o armazenamento dos dados no módulo foi utilizado uma base de dados SQLite, provida pela plataforma Android. Na Figura 4.7 é ilustrado o diagrama de classes utilizado no módulo móvel. Ele se difere do diagrama de classes dos outro módulos pela necessidade de armazenamento dos senos e cossenos da latitude e longitude da coordenada geográfica para agilizar o processamento, visto que o SQLite não provê funções nativas para executar sobre
36 CAPÍTULO 4. TRABALHO PROPOSTO 26 Figura 4.6: Módulos/Plataformas do sistema comandos SQL, como também da classe Mapa que é utilizada para agrupar os conjuntos de pontos marcados pelo usuário, permitindo assim ele escolher diferentes conjuntos, mapas, e gerenciá-los. O módulo WEB foi implementado principalmente em PHP. A integração com o módulo móvel foi feita através de um web service utilizando o protocolo JSON-RPC. O JSON-RPC é um protocolo que foi projetado para ser bastante simple e que utiliza menos tráfego de dados do que os web services que utilizam XML. Um web service assim se mostra adequado para a tranferêcia dos dados entre os módulos móvel e web, pois dessa utiliza menos o plano de dados do smartphone. O módelo de comunicação dos dados entre os módulos móvel e web via web service é: 1 > { " method " : "NOME DA FUNÇÃO", " params " : [ TIPO DE PONTO, STATUS DO PONTO, LATITUDE, LONGITUDE], " i d " : n u l l } 2 < { " r e s u l t " : "OK/ FAIL ", " e r r o r " : n u l l, " i d " : n u l l }
37 CAPÍTULO 4. TRABALHO PROPOSTO 27 Figura 4.7: Diagrama de classes do módulo móvel Um exemplo de comunicação entre o módulo móvel e web: 1 > { " method " : " add_ponto ", " params " : [ 1, 1, , ], " i d " : n u l l } 2 < { " r e s u l t " : "OK", " e r r o r " : n u l l, " i d " : n u l l } Para a interação com usuário no módulo WEB além de PHP, foi utilizado também uma biblioteca JavaScript disponibilizada pela plataforma Google Maps para visualização dos mapas. No módulo CORE se concentram a parte de acesso aos dados e também os procedimentos para o processamento numérico do algoritmo QT clustering que foi desenvolvido utilizando a linguagem C++, que é justificado pelo alto custo computacional exigido pelo algoritmo de aglomeração. Além disso, esta linguagem permite que versões futuras do algoritmo que executem em arquiteturas paralelas sejam mais facilmente acopladas ao módulo servidor. Por último, temos a base principal de dados, que foi projetada em cima do SGBD
38 CAPÍTULO 4. TRABALHO PROPOSTO 28 MySQL.
39 Capítulo 5 Resultados Para testar a ferramenta proposta foram feitos experimentos utilizando um smartphone Samsung Galaxy S II executando sistema operacional Android (ice cream sandwich). Nos experimentos realizados os usuários foram instruídos a marcarem os pontos de perigo que lhes conviesse, sendo apenas informados o que poderia ser caracterizado como trechos perigosos e falhas na via. O primeiro experimento visava contemplar uma zona urbana. Vários deslocamentos foram realizados na Avenida Senador Salgado Filho, na cidade de Natal, no Estado do Grande do Norte, e foi pedido a diferentes usuários que marcassem todos as posições dos 9 semáforos presentes em um trecho de 3km escolhido nesta avenida como sendo do tipo trecho perigoso. Nesse experimento, 6 usuários marcaram um total de 61 pontos. Os pontos marcados pelos usuários são ilustrados na Figura 5.1a. Com a base de dados abastecida com os pontos recolhidos da marcação, o algoritmo QT clustering foi executado utilizando limite de diâmetro de 300 metros. Os centros gerados são apresentados na Figura 5.1b. Para este experimento, constatou-se a formação de 10 centros, 9 dos quais marcando corretamente a posição real dos semáforos para fins de navegação automotiva. O segundo experimento visava contemplar uma zona rural. Para isso, 2 usuários diferentes foram instruídos a marcar na ferramenta todos os ponto de perigo numa rodovia de 15 km situada entre o centro da cidade de Nísia Floresta até a praia de Barra de Tabatinga, no Estado do Rio Grande do Norte. Um dos usuários dirigiu-se da cidade à praia e o outro da praia à cidade. Realizadas as marcações em ambos os sentidos, os dados gerados pelos usuários foram processados, gerando os centros para as zonas de perigo marcadas. De posse destes centros, foi pedido a cada usuário que percorresse o mesmo trecho no sentido contrário ao que haviam percorrido e que verificasse se a ferramenta gerava corretamente os alertas. O resultado constatado pelos usuários foi o de que todos os alertas foram
40 CAPÍTULO 5. RESULTADOS 30 gerados corretamente, e contemplaram praticamente a totalidade de falhas na via que haviam encontrado. Um dos experimentos no trecho que liga o centro de Nísia Floresta à praia de Barra de Tabatinga foi realizado à noite, para testar uma situação onde o usuário desconhece a via onde trafega e a visibilidade é curta. A experiência relatada pelo usuário foi de que a ferramenta tornou-se bastante útil no sentido de que pôde ficar mais alerta na proximidade de pontos de perigo desconhecidos. Os alertas o ajudaram na navegação, permitindo que tomasse decisões seguras com antecedência, sem ser supreendido por um obstáculo no curso da rodovia. Uma das atitudes mais presenciadas durante o experimento foi a redução de velocidade do motorista ao ser alertado. Os 68 pontos marcados pelos dois usuários na zona rural e os 31 centros gerados pelo QT clustering são ilustrados nos mapas das Figuras 5.2a e 5.2b, respectivamente. Observando-se os mapas, pode-se questionar o fato de os pontos encontrarem-se ligeiramente desalinhados das marcações das rodovias fornecidas pelo Google Maps. Entretanto, a inconsistência encontra-se no mapa gerado pela Google e não na posição dos pontos marcados pelo usuários. Embora estas inconsistências possam ser inconvenientes, a Google vem se esforçando para melhorar seus serviços de mapas e, para o motorista usuário da ferramenta, o mais importante é ser alertado da presença de pontos de perigo. Outro experimento foi realizado para marcar pontos de falha na via nas Avendidas Salgado Filho e Hermes da Fonseca, em Natal, RN. A marcação foi realizada no dia 27 de setembro de 2012 com o objetivo de marcar as principais falhas da via em um precurso de metros que abrangem estas duas avenidas ao todo. Na época da escrita desse documento, a sociedade natalense presenciou sérios problemas de desgaste nestas duas vias (entre outras várias) e, neste experimento, procurou-se demonstrar a viabilidade da ferramenta para mostrar (em números) problemas encontrados, servindo assim como instrumento de cobrança de ações públicas. Foram marcados, nessa época, 38 pontos de falha, que são ilustrados no mapa da Figura 5.3. Para esta situação, os centros gerados poderiam ser usados como insumo logístico para os órgãos responsáveis determinarem regiões de atuação.
41 CAPÍTULO 5. RESULTADOS 31 (a) Pontos marcados (b) Centros gerados Figura 5.1: Experimento em zona urbana.
42 CAPÍTULO 5. RESULTADOS 32 (a) Pontos marcados (b) Centros gerados Figura 5.2: Experimento em zona rural.
43 CAPÍTULO 5. RESULTADOS 33 (a) Pontos marcados (b) Centros gerados Figura 5.3: Experimento em zona urbana - marcação de falhas nas Avenidas Salgado Filho e Hermes da Fonseca, Natal-RN
UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE CENTRO DE TECNOLOGIA PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E DA COMPUTAÇÃO Uma aplicação do algoritmo