A Wearable Interface for Topological Mapping and Localization in Indoor Environments

G. Schindler, T. Starner, and C. Metzger. A Wearable Interface for Topological Mapping and Localization in Indoor Environments. 2nd International Workshop on Location and Context-Awareness (LoCA), 2006.

The authors present a method for mapping and localization in indoor environments using FreeDigiter, an ear-mounted gesture interface equipped with an infrared proximity sensor (to detect footsteps, doorways and finger gesture) and a dual axis accelerometer. The mobile robotics community has studied the automatic mapping of unknown indoor environments. Normally, in location-recognition works with wearable accelerometers a dead reckoning approach is used. The accelerometers data are integrated over time to build a metric map of a user’s path through an environment. FreeDigiter also takes the user’s steps, but also captures the connectivity of an indoor environment composed of multiple rooms. It builds and tracks a topological map. In robotics literature focuses on Simultaneous Location And Mapping (SLAM). In their projects, the authors propose a cheap, lightweight device requiring minimal user intervention.

Mapping and localization is done by first building an augmented topological map:

A map is represented as a set of edges E and vertices V defining a graph G = {E, V }. Each edge is augmented with a length l (in footsteps) and an edge-specific probability distribution over proximity sensor readings (the mean μ and variance σ of a Gaussian). By this definition, each edge corresponds to a constant part of the environment – i.e. the world looks the same to the sensors at every point on an edge.

In the building, the proximity sensor is used to detect and measure doorways and use an accelerometer to determine the distance between doorways. Once the map is constructed, the autors used a particle filter to track the user’s movements accross the edges of the graphs. With an experience FreeDigit user tracking accuracy reach 100%. This means a user has to be able to maintain a constant speed and be a consistent walker.

Relation to my thesis: A lab experiment using mapping and localization for person tracking in unknown indoor settings. The authors the knowledge in robotics to person tracking. It is not a surprise to see that somehow the users must behave like robots (keep pace and consistent) for the system to be performant (adding more sensors can alleviate the problem). However, I find interesting that the user takes part of the mapping and trains the location application. The user helps disambiguates. I was not aware of SLAM and might find there some relations between robot and person localization and it provides good reference in robotics localization:

On partical filtering:
S. Thrun, D. Fox, F. Dellaert, and W. Burgard. Particle filters for mobile robot localization. In Arnaud Doucet, Nando de Freitas, and Neil Gordon, editors, Sequential Monte Carlo Methods in Practice. Springer-Verlag, New York, January 2001.

On Voronoi tracking
L.Liao, D.Fox, J.Hightower, H.Kautz, and D.Schulz. Voronoi tracking: Location estimation using sparse and noisy sensor data. In IROS, 2003.

Coping with Uncertainty: Insights from the New Sciences of Chaos, Self-Organization, and Complexity

Coping with Uncertainty: Insights from the New Sciences of Chaos, Self-Organization, and Complexity, by Uri Merry.

The ground hypothesis of this book is that the world becomes more complex and therefore more uncertain. Uri Merry takes the perspective of the new sciences of chaos, self-organization, complexity to understand the impact on individuals and social organizations (families, societies, cities, nations, institutions).

Chaos is the time of transition between orders (transition period). It is the irregular, uncertain, discontinuous aspect of change within the confines of a patterned whole. Chaos creates stress in human life; when too many uncertainties engult a person, he or she may become stressed. The uncertain and unpredictable forms of change are in contrast to the regular and predictable ways people expect and believe that most things around them do change. People build organizations as a line of defense against the uncertainty and the chaotic elements of the world. It allows them to define regularity, predictability, routines, norms, rules and roles to reach stability and defense against uncertainty. Nevertheless, a mixture of order and chaos is the natural form of all living things. Indeed, uncertainty, unpredictability, complexity and chaos are a natural legitimate necessary, inescapable aspect of reality and will never go away.

Complex behaviors may emerge from a number of basic rules controlling part of the system. That behaviors is not predictable from knowledge of the individual elements. But it can be discovered by studying how the elements interact and how the system is and changes throughout time. The features distinguishing complext systems (p. 59) are: non-reducibility, emergent behavior, unpredictability and regularity.

The more complex a system becomes, the greater it needs to become aware of and devote communication information resources, and interaction skills to maintain its internal processes. Prigogine and Stengers describe this as a competition between communication and fluctuations. “There is competition between stabilization though communication and instability through fluctuations. The outcome of that competition determines the threshold of stability“. (p. 65) Moreover, increase connectedness leads to complexity. That is increased interdependence intensifies uncertainty if the quality of the relationships does not match the degree of interdependence. Eventually, the more complex, the more likely to break.

P. 81-82 contain a few line on technology as an intensifier of uncertainty in the world. Ironically, we develop technologies to regain control (stability), while technology accelerates changes and therefore feeds the complexity spiral.

Individuals, organizations, and societies react to uncertainty engendered by basic change in a number of ways (p. 123):

• Repeating former behavior over and over again
• Varying behavior slightly and predictably
• Adapting new behaviors
• Transiting through a choatic crisis
• Transforming to a new more complex mode of functioning

Most people will not make a deeper kind of change if they can get by with a lighter change. They will first tend to try out behavior they are user to and create variations if circumstances demand it.

Accepting Uncertainty (p. 143)
The ability to accept uncertainty and tolerate ambiguity might become an essential aspect of a personality that has to deal with an unpredictable environment. Accepting uncertainty includes the ability to be in confusion and to accept that confusion as a necessary element in the process of interacting with a nonlinear world, a world suffused with ambiguity. Ambiguity being uncertainty of meaning.

Boundaries are not clear and objects can be viewd and understood from multiple viewpoints wihtout one canceling the other out. Accepting uncertainty necessitates an ability to live with ambivalence such as having both negative and positive sentiments with regard to the same object. Ambivalence is uncertainty of value.

An uncertain, unpredictable environment is one to which a person must constantly find a fit.

Awareness (p. 151)
An environment of turbulence and discontinuous change may necessitate functioning at a higher level of awareness. Humans may need to accustom themselves to everyday functioning at a level of consciousness that is suited to an uncertain environment. This would necessitate their being able to maintain a state of consciousness of being fully aware of what they are engaged in within the environment together with a hold on their self as the focal point from which to decide in what to engage. Being fully aware entails maintaining consciousness focus awaringly in two directions simultaneously: on what one is engaged in with the environment and on the self that is observing the activity.

P. 173 has a few words on coevolution as well as competition and cooperation.

Designing and Developing Systems (p. 192)
Evolutionary system design attempts to translate the vision into policies and activities that advance human systems closer to their vision. In system design, pieces cannot be broken off to be dealt with separately. The quality of the part is dependent on its relationship to the whole. The design needs to focus on interactions and interrelations of all the components of the system. The system must be designed as a whole. While there will be differences, there may be a number of guidelines that can assist those attempting to create a design and develop it:

• Balancing at the edge of chaos
• Creating and identity of a learning system
• Taking a coherent part in the network of ecological processes. Encouraging variety and diversity
• Learning to manage chaos
• Coevolvement of the outer and the inner world.

Relation to my thesis: ubiquitous computing is about complexity, unpredictability, stability, consistency, robustness, fluctuancy, vulnerability, resilience, irregularity, ambiguity, uncertaitny, ambivalence, and confusion. All these words have been used in this books and are related to the problem I would like to solve. I should probably find a clear definition of each of these terms and link them to my current topology of spatial uncertainty. Ubiquitous computing is also challenged by the nonlinear and interdependent human and social systems. The world has inherent irregularity (nonlinear world). System designer must accept uncertainty in an unpredictable environment. The author mention the necessity of awareness of complexity and explained it as “stability through communication”. It stays very abstract, but I surely could inspire from it. Also inspiring are the categories of reaction to uncertainty engerered by basic change.

On a more philosophical level, I could use the “technology as an intensifier of uncertainty” as introduction to my work. Somehow play with the irony to we develop technology for the opposite purpose. It has some similarities with what Satyanarayanan (2003) was writting in his “Coping with Uncertainty“. That is that digital computing allowed us to eliminate uncertainty with finite state representation and transformation. And now ironic that today’s all-digital world, uncertainty reappears as a major concern at a higher level of representation.

Point and Retrieve

Two services of “point and retrieve” have been announced almost simultaneously. iPointer and GeoVector (NYT article) are based on a GPS-enabled mobile phone with an embedded digital magnetic compass and a wireless data connection. They allow to retrieve information about a landmark by pointing at it:

When users wish to identify a landmark, they point the hand-held device and press a button. The iPointer™ device receives coordinate signals from GPS satellites and orientation information from the digital magnetic compass to identify the user’s location and device’s pointing angle. These coordinates are then sent over the wireless network to the database. iST’s geospatial database’s selection algorithms identify the selected landmark and sends information back over the wireless network to be displayed in text, visuals and audio on the user’s device.

Relation to my thesis: A technology that enables near field interaction with the physical space and local search. I am absolutly curious to know how users of such services manage the shortcoming of the technology. Does a magnetic compas increases or decreases confusion in navigating in urban environments?

Comment Faire de la Recherche en Intelligence Artificielle

Jacques Pitrat, Comment faire de la recherche en intelligence artificielle, LAFORIA 97/06. Mars 1997

Ce papier donne quelques conseils au chercheur qui commence une thèse en intelligence artificielle basées sur le développement d’un système utilisant l’informatique. Il dégage certains points communs avec ma recherche appliquée en HCI/UbiComp.

Tout d’abord une étude d’IA devrait comporter la réalisation de deux systèmes. Le premier pour se familiariser avec le domaine et ses difficultés, sans attendre des résultats extraordinaires. Après une péridoe de plusieurs mois de décantation (écriture de papier décrivant ce qui a été fait), vient la mise en place du deuxième système, tenant compte des enseignements de la première expérimentation, qui apportera des idées vraiment nouvelles. C’est ce que je tente d’effectuer avec d’abord CatchBob! puis système possiblement un système dans le zone 22@ à Barcelone.

Deux chercheurs peuvent faire davantage de travail qu’un seul, et cela permet de s’attaquer à des problèmes qui demandent la résolution de plusieurs difficultés, chaque chercheur prenant en charge l’une d’entre elle. Je le fais déjà avec Nicolas. Thème abordé à mon dernier meeting.

Il faut savoir aller à l’opposé avec ce qu’enseignent les informaticiens. C’est-à-dire commencer à réaliser un système alors que l’on ne sait pas bien ce que l’on va y mettre (dans mon cas, faire du participatory design). Il se trouve qu’en IA la situation est en général tellement complexe qu’il est impossible de faire une analyse préalable.

Mettre son inconscient dans de bonnes conditions pour travailler. C’est-à-dire lire ce qui a été fait dans le domaine et dans d’autres domaines (trouver des analogies). Ce que je fais en aller gratter dans la géographie, psychology (spatil cognition and navigation), information retrieval, systémique et robotics. Il n’est pas bon de travailler de façon continue. Les repos permettent de digérer et d’assimiler ce qui vient d’être fait. Mélanger des travaux moins prenants aux périodes de réfléxion (littérature, rédaction).

La chronologie de la thèse peut être définie comme suit: Toute une année peut être nécessaire pour définir un sujet satisfaisant et voir comment bâtir un système capable de résoudre les problèmes qu’ils veulent lui poser. Puis la phase de réalisation et expérimentation du système est d’au moins deux ans. Il faut compter trois ans pour la réalisation d’une thèse dès lors qu’elle comporte l’expérimentation d’un système, en supposant que les trois quart du temps y sont consacré. Un pré-soutenance au bout des premières années de thèse est une bonne idée (c’est qui sera le cas pour moi avec l’obtention d’un DEA après 2 ans de PhD). C’est l’occasion de rédiger une description de l’ensemble de ce qui a été fait et de faire apparaître des insuffisancces.

Relation to my thesis: learning while doing

Real-World Deployments Theme in IEEE Pervasive Computing Journal

Current IEEE Pervasive Computing Journal issue (July-September 2006 (Vol. 5, No. 3)) features papers on real-world deployment of pervasive systems. Contributions close to my focus are:

Albrecht Schmidt, Sarah Spiekermann, Anatole Gershman, Florian Michahelles, “Real-World Challenges of Pervasive Computing,” IEEE Pervasive Computing, vol. 5, no. 3, pp. 91-93, c3, Jul-Sept, 2006.

Jeffrey Hightower, Anthony LaMarca, Ian E. Smith, “Practical Lessons from Place Lab,” IEEE Pervasive Computing, vol. 5, no. 3, pp. 32-39, Jul-Sept, 2006.

Thomas Riisgaard Hansen, Jakob E. Bardram, Mads Soegaard, “Moving Out of the Lab: Deploying Pervasive Technologies in a Hospital,” IEEE Pervasive Computing,

Zhiwen Yu, Xingshe Zhou, Daqing Zhang, Chung-Yau Chin, Xiaohang Wang, Ji Men, “Supporting Context-Aware Media Recommendations for Smart Phones,” IEEE Pervasive Computing, vol. 5, no. 3, pp. 68-75, Jul-Sept, 2006.

Oliver Storz, Adrian Friday, Nigel Davies, Joe Finney, Corina Sas, Jennifer Sheridan, “Public Ubiquitous Computing Systems: Lessons from the e-Campus Display Deployments,” IEEE Pervasive Computing, vol. 5, no. 3, pp. 40-47, Jul-Sept, 2006.

Relation to my thesis: I still plan to write a paper on the experience of designing and deploying CatchBob! Real-world experiments is the only way to experiment with problems of scale in uncertain and dynamic environments. As this issue’s editor, Roy Want of Intel, puts it in Build What You Use:

To prove success in ubiquitous computing research, you must implement your ideas and deploy them in support of a work practice or community activity. Anything less, and the design’s utility will always be doubted, even if the core engineering is outstanding.

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)