Informal Meeting with Alexandre Albore on Robotic Localization Issues

In an informal meeting, Alexandre Albore, PhD student in the Artificial Intelligence Group at the UPF, introduced me to the field of robotic localization. Alex is focused on the theoretical aspects of planning in AI, that is creating sequences of actions, possibility conditioned by observations, that bring a system from an initial state to a goal. We have in common our experience that imperfect observations within uncertain domains and dynamic world often challenges planning (for robots and humans). The difference between CatchBob! and his robots is that I do not give players information about the location data imprecision, while such data are required by robots.

He explained me his use of Monte Carlo localization (i.e. Markov localization, particle distribution) and Kalman filter in robotics.

We share on the multiple issues inherent to robotic localization. Robots most often use lasers (50m coverage, problems with windows) and sonars (10m coverage, echo and filter problems). New localization system now use limunosity (I am reading something on this for context-aware wearable computing). Often an integration of different localization techniques is uses (fusion). In the context of Monte Carlo localization, observations are used to disambiguate previous inferences. Issues are that there might be too much or not enough information.

He advised me to have a look at the work of: Sebastien Thurn Sven Koenig, Vadim Bulitko, Illah Nourbakhsh, Human-robot interaction, some work on localization and Eric Beaudry.

Relation to my thesis: Real-life AI applications are often characterized by uncertainty, dynamic changes of the world, and limited knowledge available a priori. As a result, researchers from several AI areas have recently invested much effort into methods suitable for domains with such kinds of incomplete information.

Euro Coins Diffusion

French INED and CNRS created the Euro Spatial Diffusion Observatory to realize a set of studies on the spatial and social diffusion of the Euro in the “Euro Zone” countries. The diffusion of the Euro is the occasion to observe the movements and links among the different european regions.

Surveys of the wallet of 2000 french people are performed every three months. The origin of the coins are collected with the people residential location and the social features. The combined analysis of the social and spatial diffusion of the coins bring helpful empirical data for social networking, integration, exclusion, and internationalization phenomenon. The same data also allow to validate theoretical models of socio spatial diffusion.

Due to the strong discontinuity of Euro propagation (due to the elapsed time between surveys and the amount of surveys performed – influencing the data timeliness and data quality), the maps produced contain a certain amount of uncertainty. Without some gaussian smoothing (value at one point, corresponds to the average of the neighbors) that blurs a bit the reality, the maps would give the impression of brutal changes between regions. Moreover, a dynamic map showing the diffusion of the coins over time, allows to reduce the errors and provide a better big picture of the main movements and propagation (at the borders and during the holidays).

Relation to my thesis: Tracking things can generate valuable socio-spatial information (spatial analysis and modeling of phenomenon of spatial interaction, impact of physical or political borders). Timeliness and quality of the gathered spatial information are taken into account to present the spatial data (use of gaussian smoothing and map animation)

Location-Aware Information Delivery with ComMotion

Marmasse, N. and Schmandt, C. 2000. Location-Aware Information Delivery with ComMotion. In Proceedings of the 2nd international Symposium on Handheld and Ubiquitous Computing (Bristol, UK, September 25 – 27, 2000). P. J. Thomas and H. Gellersen, Eds. Lecture Notes In Computer Science, vol. 1927. Springer-Verlag, London, 157-171.

ComMotion is a location-aware computing environment which links personal information to locations. Its uses GPS position sensing to gradually learn about the locations of the users’ daily life based on travel patterns. The authors use a simple learning algorithm to exploit the GPS signals loss to detect building. When the GPS signal was lost and then later re–acquired within a certain radius, comMotion considered this to be indicative of a building. This approach avoided false detection of buildings when passing through urban canyons or suffering from hardware issues such as battery loss.

Unfortuantally, the evalutation of the system was only done with 4 people. Therefore the feedback on location precision is rather weak:

Precision and Alert Timing. GPS data is intentionally imprecise –when the user evaluation was done, accuracy was within 100 metres. For this application, exact position information is not required. When two different virtual locations are physically within meters of each other, however, due to the inaccuracy of the position data, one location is identified and not the other –that is, location shadowing. This can be solved by clustering the virtual locations and providing alerts for all the locations within the cluster. The lack of precision of position data also strongly affects the alert timing and auditory cues were sometimes given too late. Loss of GPS signal due to shadowing by tall buildings was also experienced.

Relation to my thesis: The authors acknowledge that location accuracy and reliability must be taken into account for the design of location-aware application. They integrate the signal loses to make sense of the space. They also mention the importance of the granularity of the location information. However, the feedback of only 4 people is really limiting to evaluate if the learning algorithm and the design. This work is very much related to Learning Significant Locations and Predicting User Movement with GPS.

Accuracy Attribute in Latest Google Maps API

The Google Maps API v2.60 adds, among other features, an accuracy attribute for the geocoder, that is how accurately the address could be geocoded. For example, the geocoder returns 7 (intersection level accuracy) for the address “Haight and Ashbury St, San Francisco” and 4 (town level accuracy) for “New York City”.

Relation to my thesis: Accuracy is an attribute of location quality. This value could helps defining the granularity of the location information to be displayed matching the data given to the geocoder.

GIS/GPS in Transportation, Real World Experiences

Guo, Bo, Allen D. Poling, and Mark J. Poppe, 1995. GIS/GPS in Transportation, Real World Experiences. Proceedings of the 15th Annual ESRI User Conference

A paper that summarizes the three types of real world applications of the GIS/GPS technologies

1. GPS as a Roadway Data Collector
2. GIS as a Transportation Database Manager
3. GPS as a Traffic Design Aid

The authors discuss the problems of accuracy and GPS signal reception and the problems in data acquisition and validation.

Location data collected through GPS units have intrinsic random errors that cannot be totally eliminated. To obtain the higher level of accuracy for any receiver requires differential correction, a process of placing a receiver on a known location, called a base station, and using the collected satellite data to adjust GPS positions compute by other receivers at unknown locations during the same time period.
[...]
Bad GPS signal reception results in missing data. This has been another major issue.
[...]
Due to GPS reception problems mentioned above, it was necessary to collect some attribute information using manual methods in the White House/Washington Mal project.
[...]
Some of Lee’s experiences indicate that the most difficult aspects of GIS are not necessary at the technical level, but at the data acquisition and validation level.

Relation to my thesis: Real-world example of the use of geospatial information with the issues of measuring/mapping the physical space. In addition to my other reading in the transportation research.

HawkTour: A Mobile, Context-Aware Tour Guide System

Related to the book Local Positioning Systems, Tyler Butler, Santhosh Meleppuram, Xian-He Sun from the Illinois Institute of Technology describe the architecture of HawkTour, a TabletPC-based system, allowing visitors to tour the IIT main campus. Positioning is done by the fusion of GPS for outdoor navigation and Wi-Fi based transliteration for indoors. The project is now called MyWay that uses Segways to tour the Chicago city center.

Relation to my thesis: The architecture of HawkTour has many similarities with CatchBob! (TablePCs, Wi-Fi positioning, SOAP as high-level protocol, …). The description of their system is an inspiration for the formalization of the technical part of my CatchBob! postmortem into a paper.

Precision Indoor/Outdoor Personnel Location Project

Each of indoor location technologies has drawbacks. For example, enhanced GPS is currently unable to achieve the precision required for first responder location. Inertial navigation relies on gyroscopes, which must be frequently realigned. RFID systems only work in buildings where monitoring stations have been preinstalled.

In their Precision Personnel Location Project, a Worcester Polytechnic Institute (WPI) research group has been following a different route, developing a system that employs principles from orthogonal frequency division multiplexing (OFDM), which transmits high-speed data via wired and wireless channels and integrates well in the radio spectrum, along with super-resolution techniques as used in synthetic aperture radar (SAR), which can extract great detail from radar signals.

WPI’s first responder locator system will employ transmitters, to be worn by the first responders, that continuously emit customized OFDM signals. Receivers located on emergency vehicles arrayed around a building will detect and decipher the signals. The receivers will use sophisticated, custom-designed algorithms to determine their distance from the transmitters and, by sorting out a multitude of straight-line and reflected signals, determine the exact location of the transmitters in three-dimensional space.

Relation to my thesis: An indoor positioning approach with radar signals I have not aware off.

Meeting with Paul Verschure

Today, I had a meeting with Paul Verschure. Paul is an ICREA Professor at the UPF with a background in cognitive neuroscience and neuroinformatics.

For my interest on the impact of special uncertainty, he advised me to have a closer look at the literature in spatial cognition and more precisely in spatial navigation. Somehow, his suggested to step backward to the first results and literature review I did so far. First I should gain basic understanding of spatial cognition under uncertainty and then suggest implications for design. We talked about the ways the studies are ran in experimental psychology and specifically how to carefully control conditions (manipulating uncertainty) in uncontrolled environments. it is very much possible when the control group and the experimental group are very carefully selected and managed. One challenge is not to fall into the problem of confirmation bias (interpret information according to preconceptions). In my context, I could work on three parameters (e.g. map resolution, abstraction of the data on the map, …) and then measure the performance and/or the learning.

I plan to setup a second experiment in a larger scale uncontrolled environment (because “scale” is one of the 2 most important challenge of ubicomp, next to “context”). Paul was pretty enthusiast about it and saw a lot of potential. It could actually become a real-world framework for multiple experiments (potential at the 22@ area). A scholarship is potentially available for a psychologist to work with me. Moreover, structures such as the Urban Ecology Agency of Barcelona are in deep need of data about people’s mobility and might be interested in getting involved. Such connection would match with my early digging into ABM and transportation research. I also came up some fun basic study that could involve Barcelona taxi drivers using GPS systems . To that, Paul mentioned a study in London that showed that Taxi drivers’ brains ‘grow’ on the job due to the navigating they do (“The posterior hippocampus was also more developed in taxi drivers who had been in the career for 40 years than in those who had been driving for a shorter period.”).

On the side, Paul introduced me to Bayesian Inference and how users have multiple sources of information (in the context of spatial uncertainty).

Relation to my thesis: facing experimental psychology and first thoughts on the resources available for a second experiment. I will dig in the spatial cognition literature.

Posters for UbiComp 2006 Accepted

My poster “Towards Design Strategies to Deal with Spatial Uncertainty in Location-Aware Systems” (Girardin, F., Nova, N., Blat, J.) has been accepted for UbiComp 2006 in Orange County, CA. Not surprisingly, the reviewer expect more preliminary insight or analysis. One feedback mentioned that I should relate my categories of reactions to spatial uncertainty according to the context and not the system.

In addition, Nicolas’ poster “Investigating How Automatic Disclosure of Partners’ Location Influences Mobile Coordination” (Nova, N., Girardin, F., Dillenbourg, P.) has also been accepted.

Relation to my thesis: An important milestone validating my first 10 months. One reviewer commented that he/she would like to see a submission of a full paper on the lessons learned and insight gained from the field study. I have the feeling this has mainly already been done by Benford et al. in Bridging the Physical and Digital in Pervasive Gaming and Can you See Me Now?. I might be writing such a paper with Mike Blackstock and Nicolas Nova on the lessons learned from the design and deployment of a pervasive game. The idea would be to coin the issues/challenges (constraints of location technologies, location awareness, spatial uncertainty) in performing a field study in form of a pervasive game as well as describing the impacts on the users and administrators.

Time now to learn how to analyze the CatchBob! data and think of a second experiment.

Prototypes in the Wild: Lessons from Three Ubicomp Systems

Carter, S. and Mankoff, J. 2005. Prototypes in the Wild: Lessons from Three Ubicomp Systems. IEEE Pervasive Computing 4, 4 (Oct. 2005), 51-57

Ubicomp research tends now to explore evaluation techniques including field studies that drive invention, early stage requirements gathering, and prototyping iteration. The authors evaluated three ubicomp systems at multiple design stages to provide a better understanding of how ubicomp evaluation technique should evolve. The designer must understand how to meet the user needs (what is evaluated) with the limits of feasibility depending on the availability of network connectivity and data, of sensors and algorithm for interpreting the data they produce, and of tolls with with to ease the building of applications.

The author’s suggested implication for evaluating interactive prototypes is:

Based on our experiences, we feel that field-based interactive prototypes provide invaluable feedback on a system’s use and co-evolution. However, they’re difficult and time consuming to deploy, and maintaining them unobtrusively is challenging. Designing for remote updates and using local champions and participatory design might mitigate these issues.

Relation to my thesis: I am considering evaluating my design (e.g. intelligible system to cope with spatial uncertainty) and in a field study to determine how well it performs. Based on my experience with CatchBob! I am concidering writing an article on the “Lessons learned from the design and deployment of a pervasive game”.