Voce viu o Bob?: Localizando Pessoas UsandoAparelhos Celulares

Susanna F. de Rezende

17 de julho de 2012

Sumario

1 Introducao 3

2 Funcionamento 4

3 Visao Panoramica do Sistema 63.1 Aceleracao e Bussola . . . . . . . . . . . . . . . . . . . . . . . 73.2 Correcao do Rastro . . . . . . . . . . . . . . . . . . . . . . . . 73.3 Deteccao de Encontros . . . . . . . . . . . . . . . . . . . . . . 73.4 Grafo de Encontros . . . . . . . . . . . . . . . . . . . . . . . . 8

4 Desafios e Design do Sistema 84.1 Sensores Ruidosos . . . . . . . . . . . . . . . . . . . . . . . . . 8

4.1.1 Acelerometro . . . . . . . . . . . . . . . . . . . . . . . 84.1.2 Bussola . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4.2 Correcao de Posicao . . . . . . . . . . . . . . . . . . . . . . . 124.2.1 Correcao de Posicao via Difusao . . . . . . . . . . . . . 124.2.2 Como Detectar Encontros? . . . . . . . . . . . . . . . . 12

4.3 Correcao do Rastro . . . . . . . . . . . . . . . . . . . . . . . . 144.4 Calculo de Direcoes de Navegacao . . . . . . . . . . . . . . . . 15

4.4.1 Heurısticas de Pruning . . . . . . . . . . . . . . . . . . 164.5 Identificacao Visual . . . . . . . . . . . . . . . . . . . . . . . . 174.6 Escort nas Nuvens . . . . . . . . . . . . . . . . . . . . . . . . 19

1

5 Avaliacao 195.1 Banco de Testes . . . . . . . . . . . . . . . . . . . . . . . . . . 19

5.1.1 Estacionamento . . . . . . . . . . . . . . . . . . . . . . 205.1.2 Um Andar do Departamento . . . . . . . . . . . . . . . 20

5.2 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205.3 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

5.3.1 Experimento no Estacionamento . . . . . . . . . . . . . 235.3.2 Experimento no Andar do Departamento . . . . . . . . 275.3.3 Precisao para Identificar Pessoas . . . . . . . . . . . . 28

6 Limitacoes e Possıveis Trabalhos Futuros 296.1 Energia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296.2 Escolta Atraves de Obstaculos Fısicos . . . . . . . . . . . . . . 296.3 Caminhos Longos . . . . . . . . . . . . . . . . . . . . . . . . . 306.4 Instrucoes sob Baixa Precisao de Localizacao . . . . . . . . . . 306.5 Orientacao do Aparelho Celular . . . . . . . . . . . . . . . . . 306.6 Comportamento com Mais Usuarios . . . . . . . . . . . . . . . 31

7 Conclusao 31

2

1 Introducao

A presente monografia tem por base o artigo entitulado “Did You See Bob?:Human Localization using Mobile Phones” dos autores Ionut Constandache,Xuan Bao, Martin Azizyan e Romit Roy Choudhury. O objetivo e apresentaras principais ideias e contribuicoes desse trabalho, e procurar explicar o fun-cionamento do “Escort”, um sistema de navegacao em ambientes populados,implementado pelos autores citados acima.

Comecaremos descrevendo o problema de localizacao num contexto socialnum cenario hipotetico, conforme apresentado pelos autores. Suponha queAlice chegue a um congresso num grande hotel de Chicago e queira encontrarcom seu amigo, Bob. Uma possıvel solucao seria ela andar pelo hotel ateconseguir visualmente localizar o Bob ou sair perguntando para as pessoas:“Voce viu o Bob?”. Um telefonema pode ser uma terceira opcao, mas pode serinapropriado pois o Bob pode estar numa reuniao ou numa palestra. Mesmose ele atender o telefone, ele pode pedir para a Alice encontra-lo perto dapiscina, deixando para a Alice o problema de localizar a piscina. Navegar emum hotel grande, especialmente sem conhecer precisamente a localizacao doBob, nao e uma tarefa trivial. Alem do mais, o Bob pode estar se deslocando,podendo tornar a tarefa mais frustrante ainda. Uma solucao ideal seria queuma terceira pessoa, que conhecesse a localizacao do Bob, conduzisse a Aliceate ele.

Quando apresentado com um questionario informal, 80% das pessoas con-cordaram que um sistema de escolta ate o destino seria a opcao ideal. Mo-tivado por isso, os autores generalizaram o cenario hipotetico descrito acimapara um problema mais abrangente. A ideia e desenvolver um sistema que,em um abiente publico populado, possa guiar a pessoa A ate uma pessoa es-pecıfica B. Essa forma de localizacao e escolta pode ser aplicada em diversosambientes como shoppings, bibliotecas, museus e universidades. Os autoresimplementaram um tal sistema e deram a ele o nome de Escort.

Nota-se que o Escort e um sistema simples para instalar e nao requer cal-ibracao, war-driving, localizacao via GPS nem nenhum tipo de mapa. Umbeacon (um ponto de referencia estatico) e colocado em um lugar arbitrario eserve como a origem de um sistema de coordenadas virtual. Dessa maneira,o Escort pode ser usado em qualquer local, contanto que uma conexao coma internet permita o acesso ao servidor do Escort. Tendo em vista essa van-tagem, os autores acreditam que o Escort pode ser um sistema de localizacaoutil para ambientes sociais.

3

O restante dessa monografia esta organizado da seguinte forma. A Secao 2descreve o funcionamento do sistem. Apresentamos em seguida, na Secao 3,um visao panoramica do sistema. Na Secao 4 descrevemos os desafios esolucoes na implementacao desse sistema. A avaliacao do sistema e apre-sentada na Secao 5, enquanto as limitacoes e possıveis trabalhos futuros saodiscutidos na Secao 6. Finalmente, uma breve conclusao e apresentada naSecao 7.

2 Funcionamento

A ideia principal do Escort e simples. Aparelhos celulares capturam o “rastrode movimento” usando as medidas do acelerometro e da bussola. Quandooutros aparelhos celulares estao proximos, cada celular tambem registra “en-contros” juntamente com o instante em que o encontro foi detectado. Atupla <rastro de movimento, encontro> e periodicamente enviada para umservidor remoto. Usando essas informacoes, o servidor calcula a visao globaldas posicoes e percursos dos usuarios. A qualquer momento, se A manifestao desejo de navegar ate B, o servidor pode criar uma rota, composta de seg-mentos entre os diversos encontros registrados. Por exemplo, se A encontrouC no passado, e C encontrou B recentemente, entao A pode ser conduzidoate o local em que encontrou com C, depois conduzido pelo caminho queC realizou ate encontrar com B e finalmente conduzido pelo caminho queB realizou desde que encontrou com C ate chegar na sua localizacao atual.Essa situacao e apresentada na Figura 1. Em geral, podem existir diversoscaminhos entre A e B. Nesse caso o servidor do Escort poderia escolher omais eficiente, segundo algum parametro. Esse caminho pode nao ser umalinha reta entre A e B, nem sequer o caminho mais curto, mas provavelmentee um caminho confiavel, pois todos os segmentos sao possıveis de serem per-corridos.

Apesar da ideia ser simples, implementar o Escort abrange diversos de-safios, conforme explicitado abaixo.

1. Medidas de acelerometros e bussolas atraves de aparelhos celulares saoruidosas, o que acarreta em uma divergencia crescente entre os cami-nhos medidos e os caminhos reais;

4

Figura 1: O servidor do Escort assimila a visao global do percurso e encontrosdos usuarios. Os ıcones humanos sao a posicao atual do usuario U , enquantoU(t0) denota a primeira localizacao registrada do usuario U e TUV denota omomento em que os usuarios U e V se encontraram.

2. A ausencia de uma referencia global nao permite um correcao naturalde erros;

3. Mesmo que a localizacao de um usuario possa ser corrigida em al-guns momentos, nao e trivial corrigir todo o seu percurso. Porem, taiscorrecoes sao necessarias para conduzir um usuario a outro.

Para lidar com esses desafios, assumimos que um beacon fixado em umlocal arbitrario transmita tambem informacoes de “encontros” com celularese depois aplicamos alguns metodos para correcao de localizacao e de desviode percurso. A localizacao do beacon nao precisa ser conhecida; ao invesdisso, sua localizacao pode ser vista como a origem de um sistema de co-ordenadas virtual. Qualquer usuario que encontrar com o beacon pode serreposicionado aproximandamente nessa origem, logo seu erro de desvio e res-setado. Alem disso, quando esse usuario reposicionado, digamos X, encontraoutros usuarios, os outros usuarios podem corrigir a sua posicao explorandoo fato de que X tem uma estimativa razoalvemente boa da sua propria local-izacao. Em geral, embora o erro do sistema cresca com o tempo, os encontrosentre usuarios e o beacon ajudam a manter o erro sob controle. A deteccao de

5

Figura 2: (a) A visao panoramica do sistema Escort: usuarios relatam asleituras do acelerometro e da bussola, assim como os encontros; O servidorfaz as trilhas dos usuarios. (b) O grafo da representacao teorica da visaoglobal do servidor das trilhas e interseccoes dos usuarios.

encontros e obtida atraves de sinalizacao via audio; o beacon e todos os apare-lhos celulares periodicamente transmitem tons de audio para dar a conhecersua presenca. Juntos, esses elementos sao consolidados em um prototipo desistema implementado para aparelhos Nokia e Google Android.

As experiencia com usuarios reais apresentaram resultados promissores -em media, um usuario A foi navegado para dentro de 8 metros do usuariodestinoB. Se A ainda nao e capaz de identificarB (talvez porque nao conhecede antemao B), o Escort oferece um servico de identificacao visual. Usandoisso, A pode olhar a sua volta atraves do visor da camara do telefone. QuandoB esta dentro do campo de visao, uma seta e exibida sobre B, possibilitandouma nova forma de localizacao humana.

3 Visao Panoramica do Sistema

A Figura 2 mostra a arquitetura cliente / servidor do Escort. Descreveremosbrevemente os componentes do sistema, seguido por uma discussao sobre osdesafios e solucoes.

6

3.1 Aceleracao e Bussola

O cliente Escort periodicamente mede as leituras do acelerometro e da bussolados telefones moveis dos usuarios. Como os padroes de caminhada geramassinaturas identificaveis no acelerometro, o cliente Escort pode calcular onumero de passos dados pelo usuario. Quando multiplicado pelo tamanhoestimado do passo, obtemos o deslocamento aproximado do usuario. Asleituras da bussola oferecem a direcao do movimento, e quando vistas emsequencia de tempo, as tuplas <deslocamento, direcao, tempo> capturaramo padrao de movimentacao do usuario. Chamamos esse padrao de trilha dousuario.

3.2 Correcao do Rastro

A trilha do usuario e periodicamente informada ao servidor Escort atravesde uma conexao WiFi/3G. Devido a ruıdos dos sensores, a trilha deriva domovimento real do usuario. No entanto, duas oportunidades sao exploradospara compensar a flutuacao:

(i) encontro com o beacon;

(ii) encontro com usuarios que encontraram com o beacon recentemente.

Ambos os eventos, se detectados, fornecem uma melhor estimativa da loca-lizacao do usuario. A diferenca entre a nova estimativa e aquela computadapelos sensores contem informacoes sobre a natureza da deriva com relacaoas medidas da bussola e do acelerometro. O Escort usa essas informacoespara corrigir a trilha do usuario e assim calcular rotas mais precisas entre osusuarios.

3.3 Deteccao de Encontros

Para detectar encontros, o dispositivo do usuario periodicamente sinalizaa sua presenca, ao mesmo tempo ouve para detectar a presenca de outrosdispositivos. A sinalizacao acontece atraves de audio, e consiste em tocarum tom especıfico em frequencias (quase) inaudıveis. Este tom e atribuıdoao aparelho telefone no momento de registro do usuario no servico do Escort.Quando o dispositivo A detecta seu encontro com B, o dispositivo A enviaesta infomacao para o servidor do Escort juntamente com a sua trilha. O

7

servidor corrige desvios de trilha e constroi uma visao global dos movimentosdo usuario e cruzamentos espaciais. Esta visao global se traduz em um grafode caminhos entre os usuarios. Os vertices do grafo sao interseccoes espaciaisde caminhos dos usuarios, enquanto as arestas sao os caminhos percorridosentre esses cruzamentos. A Figura 2(b) mostra esta traducao para o cenarioda Figura 2(a).

3.4 Grafo de Encontros

Desafios praticos surgem ao longo do tempo porque o grafo cresce rapida-mente. Heurısticas de poda (pruning) sao aplicadas de forma que os caminhospossam ser calculados de forma eficiente. Supomos sempre que o caminhopercorrido por um usuario e bidirecional, ou seja, se um usuario andou denorte a sul, entao e possıvel que algum outro usuario ande no sentido in-verso (do sul para o norte) ao longo desse mesmo caminho. Para algumcaso especıfico, isso poderia nao ser verdadeiro, mas para a maior parte dasaplicacoes, isso vale.

Assim, quando Alice solicita encontrar com Bob, a rota computada peloEscort e devolvida como uma sequencia de tuplas de deslocamento e deangulo, ou seja, <passoi; θi >. O cliente do Escort pode entao exibir umangulo, θi, no visor do aparelho e, quando o usuario der o i-esimo passo,o proximo angulo θi+1 pode ser mostrado. Continuando dessa forma ate ovalor maximo de i e esperado que Alice seja guiada ate a vizinhanca de Bob,alcancando o objetivo de uma escolta eletronica.

4 Desafios e Design do Sistema

O projeto do Escort em ambientes reais apresenta alguns desafios praticos.Esta secao caracteriza a natureza destes desafios e apresenta as abordagenspara resolve-los.

4.1 Sensores Ruidosos

4.1.1 Acelerometro

Para determinar a rota de um usuario, o seu deslocamento precisa ser cal-culado a partir de medicoes do acelerometro (Figura 3(a)). Uma possıvelsolucao seria integrar duplamente as leituras da aceleracao. A Figura 3(b)

8

mostra os resultados inaceitaveis obtidos utilizando esse metodo a partir dosdados de dois usuarios que caminharam em linha reta. Os usuarios segu-ravam os telefones nas maos. Evidentemente, a partir dos resultados, o erro(a diferenca entre o deslocamento estimado e o real) aumenta rapidamente,atingindo mais de 100m apos apenas 30m de deslocamento real. Este e umatributo de um acelerometro ruidoso, assim como dos movimentos bruscosdo telefone, enquanto e carregado pelo usuario.

Uma abordagem melhor para calcular o deslocamento a partir dos acelero-metros ja foi descrito em outros artigos. A ideia e identificar uma assinaturade aceleracao no padrao de caminhada como na Figura 3(a). Esta assinaturasurge do deslocamento natural para cima e para baixo do corpo humano aocaminhar, e pode ser usada para contar o numero de passos realizados. Odeslocamento fısico pode entao ser calculado multiplicando a contagem depassos pelo tamanho do passo, uma funcao do peso e da altura do usuario.O Escort usa essa abordagem, mas com um fator de erro extraıdos de umadistribuicao de Gauss centrada em 0 e de desvio padrao 0, 15m. Com isso,acomoda-se melhor as variacoes do tamanho do passo. A Figura 3(c) mostraque o erro acumulado e muito menor com o metodo de contagem de passospara os mesmos 2 usuarios de teste. A precisao desse metodo (como verificadoem dez outros usuarios) e de 96% em media.

4.1.2 Bussola

O ruıdo da bussola e causada por diversos fatores, incluindo o balanco dousuario, irregularidades do movimento, campos magneticos nos arredores epolarizacao interna do sensor. Uma vez que estas fontes estao relacionadascom o usuario, seu ambiente e o proprio sensor, o ruıdo e difıcil de prevere compensar. Por exemplo, experimentalmente foram detectadas mudancastanto no desvio da bussola quanto em outras oscilacoes aleatorias, mesmoquando o usuario andou varias vezes num mesmo caminho.

Para caracterizar o ruıdo da bussola foram rodados 100 experimentos com2 celulares Nokia 6210 Navigator e foi observado um vies medio de 8 grause um desvio padrao de 9 graus. A Figura 4 mostra a distribuicao de ruıdoda bussola. Alem dessa variacao grande do ruıdo, os autores fizeram duasobservacoes consistentes:

9

Figura 3: (a) Leituras do acelerometro a partir de um usuario caminhando.(b) Erro de deslocamento com a integracao dupla para dois usuarios. (c)Erro com o metodo de contagem de passos.

10

Figura 4: Distribuicao de ruıdo da bussola

1. quando o usuario esta andando em uma direcao constante, as leiturasda bussola se estabilizam rapidamente em um valor enviesado e apre-sentam apenas pequenas oscilacoes aleatorias; e

2. depois de cada curva, surge um novo vies.

Com base nestas observacoes, foi possıvel identificar dois estados do usuario:caminhando em uma direcao constante, e fazendo uma curva. As curvas saoidentificadas quando a bussola muda mais significativamente do que as mu-dancas devido as oscilacoes aleatorias. O algoritmo de identificacao de curvautiliza a seguinte relacao:

Avg(ti+1) − Avg(ti) ≤ (StdDev(ti) + StdDev(ti+1))/2 +G,

onde Avg(ti) denota a media das leituras da bussola ao longo de um perıodode tempo ti (por exemplo, 1 segundo), StdDev(ti) e o desvio padrao dasleituras da bussola durante ti, e G, um fator de guarda.

Enquanto na direcao constante, compensa-se a leitura estabilizada dabussola com o vies medio e relata-se o resultado como a direcao do usuario; jadurante as curvas, considera-se a sequencia de leituras relatadas pela bussola.O vies da bussola e a identificacao da curva sao apenas metodos heurısticospara compensar as diversas fontes de ruıdo. Na realidade, a direcao corrigida

11

da bussola ainda pode diferir da verdadeira direcao, devido a uma estimativaincorreta do vies. Erros da distancia computada pelo acelerometro agravamo erro da estimativa. As primeiras tentativas de acompanhar o rastro dousuario provaram-se impraticaveis - apesar do metodo de contagem de pas-sos e de correcao das leitura da bussola, a localizacao e a trilha estimadadivergiram com o tempo da verdadeira localizacao e trilha do usuario. Paracorrigir esses erros, foi necessario explorar os dados proveninetes dos encon-tros, seja com outros usuarios ou com o beacon fixo localizado nessa area.

4.2 Correcao de Posicao

4.2.1 Correcao de Posicao via Difusao

Como mencionado anteriormente, o ruıdo dos sensores do acelerometro e dabussola causa que a posicao estimada do usuario divirja de sua localizacaoreal. Para corrigir isso, explora-se o uso de um beacon fixo, que, se estiverno raio de alcance, pode ser detectado pelos clientes do Escort. Quandoisso acontece, o usuario e reposicionado no beacon. A posicao do beacon econsiderada a origem de um sistema de coordenadas virtual. As localizacoesdos usuarios sao computados com o beacon no ponto (0, 0) e o eixo X e Ycomo a direcao absoluta norte-sul e leste-oeste, respectivamente. Uma trilhado usuario no sistema de coordenadas virtual do Escort esta representado naFigura 5.

Os usuarios do Escort tambem sao reposicionados quando se deparamcom um outro usuario, digamos Eva, que passou perto do beacon recente-mente (por exemplo, a menos de 1 minuto atras). Assim, se Alice encontraEva, e Alice nao encontrou o beacon no ultimo minuto, entao Alice e reposi-cionada atraves da localizacao estimada de Eva. Atraves deste mecanismo, asinformacoes de localizacao podem ser “difundidas” para o sistema. Dito deoutro modo, o beacon corrige a localizacao dos usuarios na sua proximidade,que por sua vez, corrigem a localizacao de outros usuarios que encontram.Isto permite que o erro do sistema nao divirja.

4.2.2 Como Detectar Encontros?

A fim de tirar benefıcios dos encontros, o Escort precisa captura-los com pre-cisao. Um encontro pode ocorrer durante apenas poucos segundos, e portanto

12

Figura 5: O sistema virtual de coordenadas do Escort com o beacon naorigem.

o mecanismo de deteccao tem de ser fiavel. Varios trabalhos existentes us-aram tecnicas baseadas em Bluetooth para a descoberta de vizinhos. Poremas tentativas dos autores com Bluetooth falharam principalmente porque oBluetooth e muito lento para detectar encontros de curta duracao. Os resul-tados mostraram que em media 50% dos encontros nao foram detectados, porconseguinte esta abordagem foi considerada inutilizavel. Se os dispositivosBluetooth futuros forem capazes de detectar o sinal mais rapidamente, entaoesta certamente podera ser um solucao aplicavel.

O problema pratico de deteccao de encontros foi resolvido empregandosinais de audio. Os telefones moveis e o beacon tocam, cada um, um tomunico, enquanto simultaneamente procuram escutar os tons de outros apare-lhos. Os tons sao em uma frequencia de banda estreita especıfica; nesta im-plementacao, as frequencias selecionados estavam quase fora da faixa audıvel,e podem ser feitas inaudıveis para implementacoes reais. A pergunta naturale se a deteccao de tom e confiavel sob diferentes cenarios de ruıdo. Para veri-ficar isso, foram rodados experimentos de deteccao de tom em tres locais: umdormitorio estudantil com bastante ruıdo, uma sala de reunioes com variaspessoas falando, e um shopping com ruıdo branco (mistura de diversos sonsde frequencias diferentes) alto. Os telefones eram colocados a uma pequenadistancia uns dos outros, aproximadamente 1 metro. A Figura 6 mostra queas frequencias de tom dos aparelhos (linhas verticais tracejadas) sao clara-mente distinguıveis dos sons do ambiente.

A deteccao de tons de audio (transmitidos pelo beacon fixo ou por outrosaparelhos) nao e suficiente. O Escort precisa assegurar que o transmissor

13

Figura 6: Deteccao de tom em tres cenarios de teste: (a) dormitorio estudan-til, (b) sala de reuniao, e (c) shopping. A linha vermelha pontilhada marcaa frequencia do tom.

do tom esta proximo. Caso contrario, o reposicionamento de um usuariopode introduzir erros grandes. Para este fim, foi calculado a alteracao deamplitude com a distancia (veja a Figura 7). Evidentemente, a amplitudenao apresenta uma tendencia clara com o aumento da distancia, mas observa-se uma reducao clara na amplitude a partir de 5 metros. Essa reducaofoi observada de forma consistente, e portanto esse valor foi utilizado comolimiar. O encontro sera registrado apenas se o usuario ouvir uma amplitudesuperior a esse limiar (isto e, se o transmissor esta a menos de 5 metrosde distancia). O reposicionamento dos usuarios com base em tais encontrosincorrera, naturalmente, em um erro de ate 5 metros.

4.3 Correcao do Rastro

A correcao da localizacao presente de um usuario (como discutido acima),oferece uma oportunidade para corrigir tambem a trilha passada do usuario.Considere a Figura 8. A linha solida preta representa o verdadeiro caminhodo usuario, e a linha tracejada representa a trilha computada (usando oacelerometro e a bussola). No inıcio desta trilha, no instante tr1, o usuarioencontra o beacon e se reposiciona. Uma vez que a localizacao estimada logo

14

Figura 7: A variacao de amplitude com a distancia - duas classes de distanciassao diferenciaveis.

apos esse encontro provavelmente e bem precisa, o ponto de partida dessatrilha tem uma boa precisao. Em algum instante mais tarde, outra operacaode reposicionamento acontece no instante tr2. Neste momento, calcula-seo valor e o sentido da diferenca entre a posicao estimada do usuario antese depois da correcao. Esse vetor de correcao e uma estimativa do desviocumulativo ao longo do tempo. Com base nesta observacao, pode-se corrigira trilha entre dois perıodos consecutivos de reposicionamentos. Este metodoe chamado de “Cancelamento de Deriva”.

Na Figura 8, o resultado da aplicacao da correccao a trilha e representadapor uma linha tracejada. Espera-se que esta correcao aproxime mais a trilhaestimada da trilha real, que e representada por uma linha preta solida.

4.4 Calculo de Direcoes de Navegacao

O Escort monitora as trilhas dos usuarios continuamente. Em segundo plano,o servidor calcula a posicao atual de cada usuario, juntamente com as inter-seccoes espaciais das trilhas dos usuarios. Baseado nisso, o Escort constroi um“grafo de trilhas”. As arestas do grafo sao segmentos de trilhas de usuarios,enquanto os vertices sao cruzamentos espaciais entre as trilhas ou as localiza-coes atuais dos usuarios. A Figura 2 mostrou essa abstracao, ja a Figura 9(a)mostra um grafo de trilhas real do sistema. Uma vez que o numero de verticese arestas cresce ao longo do tempo, o grafo de trilhas rapidamente se torna

15

Figura 8: Desvio de deriva: a linha solida e a rota real do usuario, a linha apontilhada representa a rota calculada, e a linha tracejada representa a rotacorrigida atraves do cancelamento da deriva.

denso (a Figura 9(a) e um resultado de 10 minutos de operacao). Como eineficiente manter tal grafo (e realizar buscas nele), o Escort emprega umaheurıstica de pruning (poda), conforme descrito a seguir.

4.4.1 Heurısticas de Pruning

Para explicar a heurıstica de pruning, vamos considerar dois usuarios A e B,e suas respectivas rotas estimadas, PA e PB (veja a Figura 10). Digamos quePA e PB se intersectam em varias posicoes (I e J na Figura 10). Observeque as interseccoes sao “espaciais”, o que significa que os usuarios podemter passado por esses locais em diferentes instantes. Consequentemente, asinterseccoes estao a distancias diferentes com respeito a cada usuario - I emais perto do usuario A, enquanto J esta mais perto de B. A heurıstica depruning do Escort seleciona as interseccoes (espaciais) mais proximas paraambos A e B, e as mantem como vertices do grafo de trilhas. As demaisinterseccoes sao eliminadas. Os dois caminhos que unem as duas interseccoestambem sao mantidos nesta fase. Este processo e repetido para cada parde vertices no sistema, resultando em um grafo totalmente conexo, comomostrado na Figura 9(b). Este grafo e entao podado novamente atraves daaplicacao do algoritmo de Floyd-Warshall, mantendo o grafo dos caminhos

16

Figura 9: (a) grafo de trilhas apos rastrear 4 usuarios por 10 minutos. (b) Ografo resultante apos a aplicacao da heurıstica de pruning. (c) O grafo aposa execucao do algoritmo de Floyd-Warshall.

Figura 10: Interseccoes espaciais entre usuarios.

mais curtos entre os usuarios. O novo grafo e mostrada na Figura 9(c). Comoos usuarios se movem, o Escort vai continuar a acrescentar arestas e verticesno grafo de trilhas, no entanto, periodicamente a heurıstica de pruning ereaplicada. Com o mecanismo de poda do grafo de trilhas, os caminhos entreos usuarios podem ser calculados de forma eficiente.

4.5 Identificacao Visual

Suponha que o Escort tenha conduzido a Alice a poucos metros do Bob.Se eles se conhecem, Alice facilmente identificara o Bob. Caso contrario,Alice pode ser incapaz de identifica-lo, especialmente se varias pessoas estaopresentes ao seu redor. Para resolver o problema de localizacao humanaate o fim, o Escort deve ser capaz de identificar Bob, para entao Alice saber

17

Figura 11: Gerando a impressao digital do usuario.

exatamente a quem se dirigir. Propomos uma solucao que os usuarios podemopcionalmente utilizar.

Primeiramente, para que essa solucao seja possıvel, cada usuario deve teruma “impressao digital” que e criada a partir de algumas fotos do usuarioe enviada ao servidor do Escort (veja a Figura 11). Em um cenario ideal,quando Alice quer ideintificar o Bob, o sistema pedira que ela vire a camerapara as pessoas ao seu redor. As imagens gravadas serao analisadas e cadaindivıduo na imagem isolado atraves de metodos de processamento de ima-gem (algoritmos de deteccao e segmentacao de bordas). A impressao digitaldos indivıduos isolados pode ser computada (denotada impressoes digitais deteste) e comparada com a impressao digital do Bob. A impressao digital deteste que melhor corresponder a do Bob pode ser identificada no visor dotelefone. A Figura 12 ilustra esta ideia: Bob e identificado com uma seta.

18

Figura 12: Identificacao do usuario atraves da camera.

4.6 Escort nas Nuvens

O Escort depende de que usuarios periodicamente carreguem suas leiturasda bussola e do acelerometro e suas gravacoes sonoras. Este servico podeser implementado em uma nuvem de computacao (cloud computing). Em talcontexto, o custo computacional nao e uma preocupacao. Do mesmo modo,as FFT’s das gravacoes de som e de processamento de imagem podem sercomputadas rapidamente. Nos testes, o servico do Escort foi instanciadoem um laptop comum e foram monitorados 4 usuarios. Nesse contexto, naohouve nenhum problema de desempenho.

5 Avaliacao

5.1 Banco de Testes

Para poder avaliar o Escort, precisa-se da localizacao exata de cada usuario.Caso contrario, nao e possıvel quantificar nem os erros das posicoes com-putadas e nem o da distancia final entre uma pessoa escoltada e seu destino(por exemplo, entre Alice e Bob). Como o sistema tem como objetivo umaprecisao em metros, a posicao real do usuario deve ser estimada com umerro de no maximo um metro. A primeira solucao considerada foi a derastrear usuarios atraves de GPS. No entanto, os experimentos mostraramerros consistentes de 10 metros, tornando impraticavel o uso do GPS paraas necessidades do experimento. A solucao encontrada foi a de realizar osexperimentos em uma area contendo marcadores com posicoes conhecidas.

19

Neste cenario, os usuarios se movem entre os marcadores e manualmenteregistram cada marcador pelo qual passam, fornecendo sua posicao real.

Implantar uma grade de marcadores e um desafio por dois motivos:

(i) e necessaria uma grade densa de marcadores, com pequenas distanciasentre eles, para que seja possıvel acompanhar o usuario com uma gran-ularidade fina;

(ii) e necessario ter a posicao exata de cada marcador para poder avaliar oerro a cada instante e o erro final apos a escolta de um usuario a umdestino.

5.1.1 Estacionamento

Uma maneira conveniente de atender a esses requisitos foi de realizar o experi-mento em um estacionamento. Foram colocados marcadores nas interseccoese pontos finais das linhas brancas que delimitam os lugares de estaciona-mento. Uma vez que o estacionamento tem varias linhas paralelas, o numerode marcadores obtidos foi grande, com uma distancia media entre os mar-cadores adjacentes de cerca de 5 metros. As posicoes dos marcadores foramobtidas atraves de suas coordenadas GPS a partir do Google Maps SatelliteView. A Figura 13 mostra o estacionamento e alguns dos marcadores emcruzes brancas.

5.1.2 Um Andar do Departamento

Tambem foram realizados experimentos, em um andar de departamento.Foram implantados 7 marcadores neste andar e suas coordenada GPS foramobtidas usando o Google Maps Satellite View. A posicao dos marcadores edo beacon sao mostrados na Figura 14, juntamente com um dos caminhospercorridos.

5.2 Metodologia

A fim de testar o sistema atraves de diversos usuarios, movimentos e padroesde encontro, dividimos os experimentos em duas fases. Chamamos essas fases

20

Figura 13: Grade do Estacionamento. As cruzes brancas indicam a posicao dealguns dos marcadores das experiencias. As linhas solidas brancas e pretasmostram as trilhas predeterminadas percorridas por dois dos usuarios deteste. A linha tracejada representa parte de um caminho aleatorio percorridopor um usuario. O beacon esta localizado na posicao B.

21

Figura 14: Grade do andar do departamento. As cruzes pretas indicama posicoes dos marcadores. As linhas solidas pretas mostram os caminhospercorridos por dois dos usuarios de teste. O beacon esta localizado no centrodo edifıcio.

de: coleta de dados e escolta de usuario. Na fase de coleta de dados, umgrupo de N usuarios se registram no servico do Escort e sao monitorados poralgum tempo T . Os usuarios se movem entre os marcadores por caminho pre-determinados ou aleatoriamente. Quando a fase de coleta de dados terminano tempo T , temos a historia da movimentacao e a posicao de cada pessoa.Desta forma, obtem-se tanto as localizacoes computadas, como as posicoesreais do usuario no sistema de coordenadas do Escort. Em qualquer instante,a diferenca entre estas duas posicoes e o erro instantaneo do Escort, e e umindicador fino do desempenho do Escort.

A eficacia de conduzir usuarios tambem e de interesse. Para isso, o Escortprimeiro calcula o grafo de trilhas entre todos os usuarios no instante t.Entao, ele fornece orientacoes de rota para A navegar ate B. As direcoesdas rotas sao uma sequencia de tuplas de deslocamento e angulo, ou seja,<passoi; θi >. Uma vez que A termina de seguir estas instrucoes, mede-se adistancia final entre as posicoes reais de A e B.

A experiencia no estacionamento foi com 4 usuarios. Os usuarios car-regavam os celulares na mao, com a tela voltada para cima. A fase de coletade dados foi de 13 minutos, e foram realizados no total 40 experimentos deescolta. Para a experiencia no andar do departamento, havia 2 usuarios, a

22

fase de coleta de dados durou 6 minutos, e foram realizados 10 experimentosde escolta.

5.3 Resultados

A avaliacao dos resultados estao concentradas em duas metricas do sistema:

1. a variacao do erro de localizacao a cada instante como uma funcao dotempo, e

2. o erro ao final de uma escolta, isto e, a distancia final entre a pessoaescoltada e o seu destino.

Primeiro sao apresentados os resultados do experimento no estacionamento,em seguida os do experimento realizado no andar do departamento. Poste-riormente, e relatado a precisao na identificacao visual (atraves de visor dotelefone).

5.3.1 Experimento no Estacionamento

A Figura 15 mostra como um erro instantaneo do usuario evolui com o tempopara tres esquemas diferentes:

1. Inercial,

2. de Encontros e

3. de Cancelamento de Deriva.

O esquema Inercial mostra como erro cresce se apenas os sensores da bussolae do acelerometro sao utilizados para localizacao. Evidentemente, a partirdo grafico, o erro cresce rapidamente devido a deriva inercial desses sensores.O esquema de Encontros tem melhor desempenho, pois o erro instantaneocai cada vez que ocorre um encontro com o beacon ou com outro usuario.O Cancelamento de Deriva reduz ainda mais o erro, atraves da correcao dasrotas dos usuarios.

23

Figura 15: Erro instantaneo do usuario 2 atraves do tempo.

A Figura 16 mostra o erro medio em cada instante dos tres esquemaspara cada usuario. Os resultados medios em todos usuarios foram de 36, 2m,8, 5m e 6, 08m para os esquemas Inercial, de Encontros e de Cancelamentode Deriva, respectivamente. Os erros medios sao calculados a partir de dadosobtidos ao longo de todo o experimento. Para compreender a distribuicao doerro instantaneo, marcamos a funcao cumulativa de distribuicao (CDF) doerro na Figura 17. Como mostrado, o erro instantaneo e menor que 10m em68% dos casos. Apos o cancelamento de deriva, 84% dos casos exibem umerro menor que 10m.

Em seguida, avalia-se a precisao da escolta de um usuario A para umusuario B. A metrica de interesse e a distancia final entre A e B quando aescolta e concluıda. O valor medio registado pelos experimentos foi de 8,2metros. A Figura 18 mostra a distribuicao da distancia final.

A Figura 19 mostra tres exemplos de rotas de escolta entre dois usuariosaleatorios, A e B. As formas destas rotas em parte delineiam os padroes demovimento do usuario. Em um ambiente interno, essas formas podem imitara planta do edifıcio.

24

Figura 16: Erro instantaneo medio por usuario.

Figura 17: Funcao cumulativa de distribuicao (CDF) do erro instantaneo noestacionamento.

25

Figura 18: Funcao cumulativa de distribuicao (CDF) do erro final depois daescolta no estacionamento.

Figura 19: Caminhos gerados pelo Escort entre os usuarios.

26

Figura 20: Funcao cumulativa de distribuicao (CDF) do erro instantaneo noambiente interno do predio.

5.3.2 Experimento no Andar do Departamento

O erro em cada instante da localizacao e menor no ambiente interno doque no externo. Isto e causado principalmente pela forma do edifıcio queconfina os movimentos do usuario para corredores e salas (em oposicao auma possilibidade de qualquer caminho aleatorio no estacionamento). Ocancelamento do erro de deriva aumenta os benefıcios, levando a uma precisaode cerca 7 metros em 80% dos casos.

A tabela da Figura 21 apresenta a distancia final entre a pessoa escoltadae seu destino, para os diversos experimentos. A distancia final e em geralpequena, com uma media de 4, 03m. No entanto, em algumas dessas rotas ospontos de virada foram ligeiramente super ou subestimados devido a algumruıdo nas trilhas. No entanto, mesmo com essas pequenas inconsistencias denavegacao, as pessoas foram capazes de adivinhar o que o Escort estava ten-tando transmitir; quando o Escort solicitava que o usuario virasse a algunsmetros de um corredor, a pessoa acabou fazendo a virada correta. Provavel-mente, se fosse oferecida uma representacao visual de todo o caminho (algosemelhante ao sistemas GPS para carros), tornaria o sistema mais tolerantea falhas.

27

Figura 21: Erro em metros da distancia final apos o experimento no interiordo predio. X denota que o usuario nao pode ser conduzido (nao chegou aoseu destino).

Os experimentos 3 e 6 da tabela da Figura 21 mostram exemplos de casosextremos. No experimento 3, temos uma distancia final de 12m, principal-mente porque o erro instantaneo era grande. Assim, mesmo que as instrucoesde direcao estivessem corretas, o usuario chegou ao fim da rota a varios me-tros de seu destino. No experimento 6, o usuario nao pode ser levado aoseu destino. Um vies grande da bussola fez com que o usuario de destinoaparentasse que estava atravessando paredes, e, portanto, o Escort pediu aousuario escoltado a tambem virar e atravessar uma parede. Como nao haviapossıvel virada por perto, o usuario nao pode se guiado ao seu destion. No en-tanto, algum tempo depois, o usuario pode ser conduzido com sucesso ao seudestino. Isso acontece quando o Escort encontra outro caminho, ou quandooutra pessoa andando pelo mesmo caminho, proporciona melhor tracos demovimento.

5.3.3 Precisao para Identificar Pessoas

A precisao para identificar pessoas atraves do visor da camera foi avaliadausando fotos de eventos sociais. Essas fotos foram utilizadas para simulardiferentes configuracoes de teste e impressoes digitais. A Figura 22 mostra aprecisao media de identificacao como uma funcao do numero de impressoesdigitais nos arredores. A dificuldade na tarefa de identificacao aumenta como numero de pessoas. No entanto, mesmo com 8 pessoas nos arredores, aprecisao e de cerca de 80%. Esses resultados, juntamente com a precisaode navegacao para dentro de um raio de 8 metros do destino, oferece umasolucao para o problema de localizacao humana.

28

Figura 22: Precisao na identificacao visual usando a camera do telefone.

6 Limitacoes e Possıveis Trabalhos Futuros

6.1 Energia

O Escort nao foi projetado para ser eficiente do ponto de vista energetico - abussola, o acelerometro e a sinalizacao acustica certamente ira consumir ener-gia. No entanto, existem varias oportunidades para otimizacao do sistema.Quando os usuarios nao estao se movendo, o Escort pode, por exemplo, desli-gar todos os sensores exceto o acelerometro (que tem um consumo de energiarelativamente baixo). Assim que o usuario se mover de novo (acao detectavelpelo acelerometro), todos os outros sensores podem ser ligados novamente. Sehouver muitos usuarios em um lugar, cada usuario pode reduzir considerav-elmente a periodicidade da sinalizacao de audio. Tambem o frequente envio,dos dados do sensor para o servidor do Escort nao e necessario a menos quealguem esta sendo conduzido para este usuario. Uma versao mais eficientedo ponto de vista energetica e deixado para pesquisas futuras.

6.2 Escolta Atraves de Obstaculos Fısicos

O Escort pode dar instrucoes para atravessar obstaculos ou paredes. No en-tanto, se as direcoes do Escort refletirem uma boa aproximacao do percurso,entao e possıvel que a pessoa tome decisoes inteligentes sobre qual caminho

29

seguir. Por exemplo se o Escort pedir para virar um pouco antes de se chegara um corredor, isso nao sera um problema, pois o usuario podera identificar arota correta. Alem disso, as representacoes visuais do caminho podem ajudarna orientacao das decisoes do usuario.

6.3 Caminhos Longos

O Escort pode levar Alice por um caminho longo mesmo que Bob estaja porperto. Isso acontece quando o Escort nao tem conhecimento de um possıvelcaminho ao longo de uma rota mais curta (veja a Figura 19(b)). No entanto,este pode ser um indicativo de um bloqueio nesse caminho. Como umaotimizacao, o Escort poderia fornecer uma rota de linha reta entre os usuarios,uma vez que conhece suas posicoes. Entao, o usuario podera tanto seguir ocaminho direto ou aquele computado pelo Escort. Um possıvel trabalhofuturo seria investigar o problema de encontrar os “melhores” caminhos.

6.4 Instrucoes sob Baixa Precisao de Localizacao

Escoltar um usuario quando sua posicao nao e conhecida com precisao podelevar o Escort a dar instrucoes de navegacao ruins. Como o Escort temconhecimento da ultima vez que o usuario recebeu informacao de localizacaoprecisa, entao se este fato occoreu a muito tempo, o sistema pode instruir ousuario a caminhar em alguma direcao na qual possa obter informacoes maisprecisas sobre sua localizacao (por exemplo, pedir ao usuario que se mova emdirecao a um aglomerado de pessoas). Quando informacoes de localizacaomais precisas estiverem disponıveis, o Escort pode recalcular a rota e dar aousuario um caminho melhor para o seu destino.

6.5 Orientacao do Aparelho Celular

A hipotese de que os usuarios carregam os celulares na mao pode ser muitootimista. Em geral, inferir a orientacao do aparelho nao e trivial. No en-tanto, existem trabalhos que mostram como inferir a posicao relativa dotelefone usando o acelerometro do aparelho. Esses trabalhos, juntamentecom a chegada de giroscopios em telefones celulares, poderao proporcionarnovas oportunidades para descobrir a orientacao do celular.

30

6.6 Comportamento com Mais Usuarios

Tudo leva a crer que a precisao do Escort ira melhorar com um grande numerode usuarios e com o aumento da mobilidade. Dentro desses cenarios, osusuarios terao uma maior chance de cruzarem uns com os outros ou de en-contrarem o beacon. Da mesma forma, se o beacon for colocado em um lugarpopular, ou se forem adicionados outros beacons, entao havera mais oportu-nidades para corrigir e difundir informacoes de localizacao.

7 Conclusao

Pesquisas anteriores consideraram localizacao de usuarios, mas nao abor-daram os desafios de oferecer direcoes para localizar pessoas. Mesmo se alocalizacao exata do usuario esta disponıvel, permanece o desafio de con-duzir um usuario para um destino. O Escort e um prototipo que aborda estaquestao.

Este trabalho identifica o problema da localizacao social, onde o objetivoe ajudar uma pessoa, Alice, a navegar para outra pessoa, Bob. A observacaochave e que o conhecimento das localizacoes absolutas dos usuarios nao saonecessarias. Em vez disso, atraves dos padroes de movimentacao dos usuarios(obtidos pelos sensores, bussolas e acelerometros, do aparelho celular) e en-contros entre usuarios e entre o usuario e o beacon (atraves de sinalizacao deaudio), um grafo pode ser criado em um sistema de coordenadas comum. U-sando tal grafo, uma pessoa pode ser conduzida para qualquer outra pessoa.Os autores usaram essas ideias para desenvolver o Escort, e demonstraram aviabilidade de conduzir um usuario para um raio de 8 metros do seu destino.

31