Discerning Context Through Reinforcement Learning

Santiago, Roberto A., George G. Lendaris (2005), “Discerning Context Through Reinforcement Learning,” Proceedings of the American Association of Artificial Intelligence Conference 2005 (AAAI’05), Pittsburgh, Pennsylvania, July. Submitted

This paper presents a method for using reinforcement learning (RL) to construct an artificial agent capable of applying learning knowledge in a contextually appropriate way (Contextual Reinforcement Learning). In the proposed method, the stream of inputs and feedback used by the machine learning algorithm is treated as a context to the optimal parameters as determined by the algorithm. Thus, each set of parameters has a context in which they are most appropriate. The reinforcement learning aspect of the method seeks to build an algorithm which works across contexts and extracts those features which are most informative about the optimal parameter settings. Thus for novel context, the proposed methods works to extract context features and translate them into an “educated guess” of the appropriate parameter settings.

Relation to my thesis: This paper was one inspiration for my doctoral school paper on Improving Location-Aware Applications Through Reinforcement Learning. I find machine learning interesting because it could give a sense of evolution of the system according to its usage and environment. Interaction is not only done via an interface, the core of a context-aware application could co-evolve with the user.

Towards Realizing Global Scalability in Context-Aware Systems

Buchholz, T., Linnhoff–Popien, C., Towards Realizing Global Scalability in Context–Aware Systems In Location- and Context-Awareness. Proceedings of the First International Workshop, LoCA 2005, Lecture Notes in Computer Science (3479), pages 26-39, Springer, Oberpfaffenhofen, Germany, Mai, 2005.

Most of research in ubiquitous computing focus on application where all entities involved in a user session are located in each other’s spatial proximity. This has been coined as “localized scalability”. However there are application where the users are not collocated. Thus, interactions between distant entities are needed. In these situation arise the question of how global scalability in context-aware systems can be reached. This paper classifies Context-Aware Services (CASs) according to their scalability needs and reviews context provision and service provision infrastructure with regard to their scalability.

Scale consists of a numerical (number of users, context sources), a geographical (distance between the farthest nodes), and an administrative dimension (number of organizations). A system is scalable if users, objects and services can be added, if it can be scattered over a larger area, it if the chain of value creation can be divided among more organizations without the system suffering loss of performance or increased administrative complexity. Scalability problems arise especially if dynamic properties of target object (target context) and of objects between the user’s current position and the targets’ position (transition context) are included into the recommendation given to the user.

Good candidates as a suitable CAS provision infrastructure are grids, P2P networks, and CDNs. These systems need to be coupled with a large-scale context provision infrastructure (providing homogeneous access interface of context information).

Relation to my thesis: As I am at applying ubiquity in the real-world, I am interested in the scalability of ubiquitous technologies. This papers the properties to scale from local towards global.

Everyday Encounters with Context-Aware Computing in a Campus Environment

Barkhuus, Louise and Paul Dourish, “Everyday Encounters with Context-Aware Computing in a Campus Environment“. In Proceedings of UbiComp 2004, Nottingham, UK, 2004.

This paper report on a field work which highlights that in heterogeneous groups, concerns such as location infrastructure, access and mobility can take on quite different forms, with very different implications for technology design and use. Context-aware computing attemps to make the context in which technologies are deployed and used into a configuration parameter for those technologies. In this paper, the authors consider context of a rather different sort – the social, organizational, and institutional contexts into which context-aware and ubiquitous technologies are deployed. They take the “embodied interaction” approach of ubicomp, that is moving the focus from the technology itself to the settings within which that technology will be employed. In their empirical investigation of the use of ubiquitous computing blending mobile and location-based technologies to create augmented experiences for university students (UCSD Active Campus project), they focuses on how the technology fits into broader social context of student life. They examined the factors that influence adoption and use of ubiquitous computing technologies and studies the emergent practices of ubiquitous computing (i.e. collective practices that emerge when a technology is put into the hands of an active user community)

The study revealed five concerns for the design of effective ubiquitous computing experiences at a large-scale:

• Technology design must be sensitive to the variability of institutional arrangements. That is that technology use is systematically related to people’s roles and relationships.
• Different temporal dynamics apply to laboratory settings and real-world settings. In real-world setting, new technologies must live along side old ones
• We must be attentive to infrastructure of all sorts (both technological and procedural infrastructures).
• Look at the relationship between technology and local cultural practices.
• Technologies are a means by which relationships between social groups are enacted.

Relation to my thesis: the move of ubiquitous computing from laboratory settings into the everyday world (in the trend of Abowd’s everyday computing). Barkhuus and Dourish show an example how observational and qualitative methods can offer a set of concepts to help for the design of ubiquitous environments. The five concerns mention are an inspiration for a paper on the design and deployment of CatchBob!

Valuable references include:

W. K. Edwards, V. Bellotti, A. K. Dey, and M. W. Newman. The challenges of user-centered design and evaluation for infrastructure. In Proceedings of CHI 2003, pages 297–304. ACM Press, 2003.

J. Scott and M. Hazas. User-friendly surveying techniques for location-aware systems. In Proceedings of UbiComp 2003, pages 44–53. Springer, 2003.

Architecture of a Large-scale Location Service

Leonhardi, A. and Rothermel, K. 2002. Architecture of a Large-Scale Location Service. In Proceedings of the 22 Nd international Conference on Distributed Computing Systems (Icdcs’02) (July 02 – 05, 2002). ICDCS. IEEE Computer Society, Washington, DC, 465.

This paper proposes a a generic location service (LS) to manage highly dynamic location information for a large number of mobile objects. It suggests the support of multiple types of queries such as position query, range query and nearest neighborhood query, and take into consideration the accuracy of the location information. It should also hide the heterogeneity of data generated by sensor systems. In its architecture and to ensure scalability, the LS are organized in a hierarchical manner (similar to the GSM-1900). The LS is configured to cover a certain geographic area called the service area.

Relation to my thesis: A quick and easy paper that covers an IEEE approach to scalable location-aware systems. Generic location service are about heterogeneity in the sensed data, types of query, scalability (service areas), accuracy, and frequency of update message. On a similar subject (update protocols) there is A Comparison of Protocols for Updating Location Information.

From Interaction to Participation: Configuring Space through Embodied Interaction

Williams, A., Kabisch, E., and Dourish, P. (2005.) From Interaction to Participation: Configuring Space through Embodied Interaction. Proc. Intl. Conf. Ubiquitous Computing Ubicomp 2005 (Tokyo, Japan).

This paper explores the question of how will people encounter and understand ubiquitous environments (new space), and how will they interact with each each other through the augmented capabilities of ubicomp technologies of such environments (i.e. the reconfiguration of the relationship between people, objects and space). The fundamental concern is with the ways in which we encounter space not simply as a container for our actions, but as a setting within which we act (embodied nature of activity). The spatial organization of activities goes beyond simply space and action. Rather, it speaks to first the mutual configuration of arrangements of bodies, artifacts and activities, and second, the social and cultural practices by which actions are both produced and interpreted.

Traditional focus of HCI is on how people might interact with technologies. The author take an other approach on looking at how people engage with space and with each other through the technologies that are provided to them. Rather than focusing on the interaction, they focus on the participation. In the same time, we think and talk about ubiquitous computing systems with a primer focus on technologies and less on the space that those technology occupy. From their experience, the authors notes some broad observations:

• People sought to understand the system not as a whole but in terms of the individual actions of different components
• We currently lack of good design approaches for understanding the temporal aspects of technologies.
• Ubiquitous computing technologies are ones through which people encounter and come to understand infrastructures. The presence or absence of infrastructure, or difference in its availability, become one of the way in which spaces are understood and navigated (e.g. the strength of a cellular telephone signal becomes an important aspect of how space is assessed and used).

Relation to my thesis: My thesis may contain a phenomenological perspective of how will people be able to make sense of computationally enhances spaces, and how will people be able to make sense of each other in the spaces. So far, I have noticed in Catchbob! the impact of a fluctuant link between the infrastructure based on ubicomp technologies and the activities due to the fluctuant network coverage and consistency (hurting (changing?) the communication) and spatial uncertainty. The infrastructure has an impact on the way we encounter space. This is Dourish’s “embodies interaction” paradigm. That is how technologies and artifacts take on meaning for their users through their embedding into systems of practice. Well, I shall read Where The Action Is: The Foundations of Embodied Interaction to really grasp what embodied interaction really is.

Lost in Virtual Space: Studies in Human and Ideal Spatial Navigation

Stankiewicz, B.J., Legge, G. E., Mansfield, J. S., & Schlicht, E. J. (2006). Lost in Virtual Space: Studies in Human and Ideal Spatial Navigation. In Press. Journal of Experimenal Psychology: Human Perception & Performance. 32(3), 688-704.

An internal representation of the space is usually referred to as a cognitive map. To develop an understanding of human spatial navigation, it is important to understand how the cognitive map is developed and the nature of its representation. This paper describes three human spatial navigation experiments that investigate how limitations of perception, memory, uncertainty and decision strategy affect human spatial navigation. The authors present a model designed to navigate through visual sparse indoor environments that contain perceptual ambiguity. First experiment found that participants’ way finding efficiency decreased as layout size increased. Experiment 2 investigated whether this reduction in navigation efficiency was due to visual perception. Experiment 3 investigated if it was due to memory, spatial updating strategy, or decision strategy. Results suggest that the inefficiency in Experiment 1 is due to inefficiency in the participant’s spatial updating strategy.

The key properties of the model’s spatial navigation task are:

• Perception: perceptual input like two-dimensional and stereo depth visual images, auditory cues, kinesthetic feedback from joints and muscles
• Spatial updating: ability to determine our location and heading in a large-scale space given our knowledge about the environment (cognitive map) and the sequence of specific observations and actions while navigating.
• Decision strategy: set of actions to move from one state in the environment to another.
• Navigation goal: to formalize a spatial navigation task one needs to specify the goal. The most common spatial navigation goal is to travel from one known location to another known location.

These properties are used to investigate where the cognitive limitations might exist in spatial navigation. Experiment 3 might be the most related to my research because it deals with give supplementary information made available to the participant. It had three conditions, No-Map, Map and Map + Belief Vector.

Findings of experiment 3 suggest that participants did not have difficulty in accessing their cognitive map, or that the global information afforded by the supplementary map was not useful to them. Future research will investigate the contribution on navigating behavior when navigating with uncertainty of:

• accurately updating a belief vector given an action
• generating the candidate states given an observation
• accurately updating a belief vector given an action
• accurately eliminating candidate states given the current observation

In the discussion, the author mention navigating with uncertainty:

The present studies suggest that participants have difficulty navigating when there is state uncertainty. The three experiments show that the major factor in participants’ inefficient navigation behavior lies in the methods they use to update their belief vector. Within this updating procedure, there are four specific procedures; any one of them, or a combination of inefficient processing, can lead to the inefficient behaviors found in the present experiments. These subprocesses include the following: (a) generate all of the states that are consistent with the current observation, (b) remember the candidate states, (c) update this collection of states on the basis of the most recent action; and (d) eliminate the candidate states that are inconsistent with the current view. Any or all of these processes may have produced the inefficient behavior found in these studies.

Relation to my thesis: Maps and location-aware systems are mediums to help create and update cognitive maps of physical/virtual spaces. Here I am digging into spatial navigation and spatial cognition. Spatial navigation is composed of multiple processes that include perception, memory, spatial updating and decision making. This study investigate our navigating skills when there is uncertainty about our current state in the environment and their is very visual information to reduce the ambiguity. The paper describes well how the psycho experiment was run. That is observing and then testing hypothesis with different conditions. The authors use desktop virtual to investigate way-finding behavior. The question is if the results will actually generalize to navigation under more realistic conditions. It would be good to find references on such spatial navigation/cognition experiments in real-world settings. The paper bring several useful concepts such as:

• Perceptual ambiguity
• Cognitive map (Hirtle and Heidorn 1993; Kuipers, 2001; O’Keefe & Nadel, 1978; Tolman, 1948). The concept of a cognitive map has influenced how researchers describe the ultimate representation that we obtain after extensive exploration of a large-scale space.
• Belief vector, the list of states that the participan could be in given their previous observations and actions.

Putting Systems into Place: A Study of Design Requirements for Location-Aware Community Systems

Samer Karam, Sukeshini A. Grandhi, Quentin Jones, Loren Terveen and Steve Whittaker. Putting Systems into Place: A Study of Design Requirements for Location-Aware Community Systems. Poster at UbiComp04

A poster to present a conceptual framework on how socially-defined places influence people’s information sharing and communication needs. The authors argue that system design must factor in userrs’ activities and social networks, alongside place. They present the P3-Systems conceptual framework organizes the design space and location-aware systems into mainly People-Centered and Place-Centered systems. People-Centered systems employ user location to support awareness, while Place-Centered systems link virtual spaces to physical locations.

From the findings of the study some implication for design can be extracted:

• Place alone does not determine information needs; user routines and social relationships must be integrated
• While people are willing, to share their location information with others, for a seamless user experience the relationships between users, places, and their social networks will have to be simultaneously taken into account.

A full paper was later published:
Jones, Q., Grandhi, S. A., Whittaker, S., Chivakula, K., and Terveen, L. 2004. Putting systems into place: a qualitative study of design requirements for location-aware community systems. In Proceedings of the 2004 ACM Conference on Computer Supported Cooperative Work (Chicago, Illinois, USA, November 06 – 10, 2004). CSCW ’04. ACM Press, New York, NY, 202-211.

Relation to my thesis: Study on the type users’ social networks and activity beyond place as determinant location information. I inspired myself from the people/place-centered distinction of location-aware systems for UbiComp06. The authors also categories location-aware systems accoding to absolute/relative positioning, user activity/virtual space, and synchronous and asynchronous

The here a reference to Context-Aware Experience Life Sampling Methods (CAES) that I should dig into to run my second experiment:
Intille, S. S., Tapia, E. M., Rondoni, J., Beaufin, J., Kukla, C., Agarwal, S., Bao, L., and Larson, K., (2003). Tools for Studying Behavior and Technology in Natural Settings. UbiComp 2003.

as well as:
Jones, Q., Grandhi, S. A., Whittaker, S., Chivakula, K., and Terveen, L. 2004. Putting systems into place: a qualitative study of design requirements for location-aware community systems. In Proceedings of the 2004 ACM Conference on Computer Supported Cooperative Work (Chicago, Illinois, USA, November 06 – 10, 2004). CSCW ’04. ACM Press, New York, NY, 202-211.

De Vuelta en Barcelona

Privacy Observant Location System (POLS)

Very similar to Place Lab, Intel Reseach’s POLS is a Privacy Observant Location System that provides an easy to use, on-device localization solution for mobile application developers. During the development of POLS, a large set of cell data for the Seattle Metro area was collected. The map below shows the coverage area. The combination of this data and the POLS software give a complete working location system within the coverage area.

POLS currently supports phones based on the HTC Typhoon series phone (Audiovox SMT 5600, Orange SPV C500, UTStarcom SMT 5600, I-Mate SP3/SP3i, QTEK 8010/8020, Dopod 565, MoviStar TSM 520, O2 Xphone II
T-Mobile SDA.

Relation to my thesis: Planning second experiment

UbiComp06 Full Papers

At the Ubicomp06 conference, I’ll be greatly interested in Wednesday’s sessions including: Where Are We Going?, Games as Platforms, and Using Ubicomp For Real. Key full papers related to my work are:

Mobility Detection Using Everyday GSM Traces
Timothy Sohn (University of California, San Diego, US); Alex Varshavsky (University of Toronto, CA); Anthony LaMarca (Intel Research Seattle, US); Mike Chen (Intel Research Seattle, US); Tanzeem Choudhury (Intel Research Seattle, US); Ian Smith (Intel Research Seattle, US); Sunny Consolvo (Intel Research Seattle, US); William Griswold (UC San Diego, US)

Practical Metropolitan-scale Positioning for GSM Phones
Mike Chen (Intel Research Seattle, US); Timothy Sohn (University of California, San Diego, US); Dmitri Chmelev (University of Washington, US); Dirk Haehnel (Intel Research Seattle, US); Jeffrey Hightower (Intel Research Seattle, US); Jeff Hughes (University of Washington, US); Anthony LaMarca (Intel Research Seattle, US); Fred Potter (University of Washington, US); Ian Smith (Intel Research Seattle, US)

Hitchers: Designing for Cellular Positioning
Adam Drozd (University of Nottingham, UK); Steve Benford (University of Nottingham, UK); Alan Chamberlain (University of Nottingham, UK); Michael Wright (University of Nottingham, UK); Nick Tandavanitj (Blast Theory, UK)