Designing Ubiquitous Computing Games – A Report from a Workshop Exploring Ubiquitous Computing Entertainment

We report from a Research Atelier that explored how ubiquitous computing could be applied to fun and entertainment. The Atelier lasted for five days, starting with two days of scenario development and brainstorming activities. This led to three fairly concrete – though very different – game ideas. The background and motivation for the Atelier is described, as well as the method used and the games developed. Correspondence to: Mr S. Bjork, PLAY Studio, Interactive Institute, Box 620, SE 40530 Goteborg, Sweden.     

Movement Awareness for Ubiquitous Game Control

This paper describes a sensing system for recognising and characterising human movements and its application to ubiquitous gaming. In particular this paper considers the control of computer games through players interacting with the physical environment around them in a natural and appropriate manner. This pushes the interface into the environment, and pulls ubiquitous computing into the game. This is achieved using a sentient computing system. Such a system senses the location, motions, actions and even physiological responses of users. This sensory data can be used to interface and control a game. A good example is 3D first-person games and we demonstrate a system in which actions in the game are mapped to similar actions in the real world. Correspondence to: R. Headon, Laboratory for Communications Engineering, Department of Engineering, University of Cambridge, Trumpington Street, Cambridge CB2 1PZ, UK. Email: rph25@cam.ac.uk     

Touch-Space: Mixed Reality Game Space Based on Ubiquitous, Tangible, and Social Computing

This paper presents a novel computer entertainment system which recaptures human touch and physical interaction with the real-world environment as essential elements of the game play, whilst also maintaining the exciting fantasy features of traditional computer entertainment. Our system called ‘Touch-Space’ is an embodied (ubiquitous, tangible, and social) computing based Mixed Reality (MR) game space which regains the physical and social aspects of traditional game play. In this novel game space, the real-world environment is an essential and intrinsic game element, and the human’s physical context influences the game play. It also provides the full spectrum of game interaction experience ranging from the real physical environment (human to human and human to physical world interaction), to augmented reality, to the virtual environment. It allows tangible interactions between players and virtual objects, and collaborations between players in different levels of reality. Thus, the system re-invigorates computer entertainment systems with social human-to-human and human-to-physical touch interactions. Correspondence to: Professor A. Cheok, National University of Singapore, 10 Kent Ridge Crescent, Singapore 119260. Email: adriancheok@nus.edu.sg     

Beyond Position Awareness

Location models are merely based on positional information. Using wireless sensor networks, however, allows us to extract information which can be related to different levels of semantic proximity of different devices. Based on this observation, the paper proposes a semantic proximity hierarchy based on a wireless sensor network. In this paper, we argue that the proposed proximity hierarchy adds a new and complementary dimension to pure positional location information. The paper discusses the proposed hierarchy, gives application examples and some preliminary experimental results. Correspondence to: Mr S Antifakos, Perceptual Computing and Computer Vision Group, ETH Zentrum, CH08092 Zurich, Switzerland. Email: antifakos@inf.ethz.ch     

Active Environments: Sensing and Responding to Groups of People

Most environments are passive– deaf, dumb and blind, unaware of their inhabitants and unable to assist them in a meaningful way. However, with the advent of ubiquitous computing – ever smaller, cheaper and faster computational devices embedded in a growing variety of “smart” objects – it is becoming increasingly possible to create active environments: physical spaces that can sense and respond appropriately to the people and activities taking place within them. Most of the early ubiquitous computing applications focus on how individuals interact with their environments as they work on foreground tasks. In contrast, this paper focuses on how groups of people affect and are affected by background aspects of their environments.     

A Location Model for Communicating and Processing of Context

Location is one of the most important elements of context in ubiquitous computing. In this paper we describe a location model, a spatial-aware communication model and an implementation of the models that exploit location for processing and communicating context. The location model presented describes a location tree, which contains human-readable semantic and geometric information about an organisation and a structure to describe the current location of an object or a context. The proposed system is dedicated to work not only on more powerful devices like handhelds, but also on small computer systems that are embedded into everyday artefact (making them a digital artefact). Model and design decisions were made on the basis of experiences from three prototype setups with several applications, which we built from 1998 to 2002. While running these prototypes we collected experiences from designers, implementers and users and formulated them as guidelines in this paper. All the prototype applications heavily use location information for providing their functionality. We found that location is not only of use as information for the application but also important for communicating context. In this paper we introduce the concept of spatial-aware communication where data is communicated based on the relative location of digital artefacts rather than on their identity. Correspondence to: Michael Biegl, Telecooperation Office (TecO), University of Karlsruhe, Vincenz-Prieβritz-Str. 1 D-76131 Karlsruhe, Germany. Email: michael@teco.edu     

Contextual Virtual Interaction as Part of Ubiquitous Game Design and Development

This paper relates to the problems of designing rich interaction, in the context of multi-player games, that would adequately support communication, control and co-ordination. The aspects of fun and rich experiences, usually required within the entertainment context, are easily overlooked in technologically driven system design. The concepts of a future ubiquitous game can be difficult to comprehend and evaluate in cases where a fully functioning physical prototype is not an option. One solution for the problem is Contextual Virtual Reality Prototyping that adds the missing context to the design simulations. The product can be designed and demonstrated in the corresponding environment, thus making it easier to understand the use-cases of, for example, a mobile device that has various location-dependent features. The main contribution of this research is the design and development approach that supports the creation of rich interaction. The primary emphasis of the approach is to avoid purely technologically driven design and development, but rather to provide a supporting, or even a guiding, approach that focuses on the creative process and conceptual understanding of rich interaction. This conceptually grounded content production-oriented approach to interactive system design is described and evaluated. Correspondence to: T. Manninen, Department of Information Processing Science, University of Oulu, PO Box 3000, 90014 Oulun Yliopisto, Finland. Email: tony.manninen@oulu.fi     

Location Models from the Perspective of Context-Aware Applications and Mobile Ad Hoc Networks

Location models are crucial for providing location-dependent data to context-aware applications. In this paper, we present two approaches for modeling location information taken from an infrastructure-based and an ad hoc network-based application scenario. From these approaches we derive requirements for a general location modeling language for ubiquitous computing. Correspondence to: M. Bauer, Fakult?t Informatik, Universit?t Stuttgart, Breitwiesenstr. 20-22, D-70565 Stuttgart, Germany. Email: mabauer@informatik.uni-stuttgart.de     

SenToy in FantasyA: Designing an Affective Sympathetic Interface to a Computer Game

We describe the design process of an affective control toy, named SenToy, used to control a synthetic character in a computer game. SenToy allows players to influence the emotions of a synthetic character placed in FantasyA, a 3D virtual game. By expressing gestures associated with anger, fear, surprise, sadness and joy through SenToy, players influence the emotions of the character they control in the game. When designing SenToy we hypothesized that players would manipulate the toy to express emotions using a particular set of gestures. Those gestures were drawn from literature on how we express emotions through bodily movements and from emotion theories. To evaluate our idea we performed a Wizard Of Oz study [1]. The results of the study show that there are behaviours that players easily pick up for expressing emotions through the gestures with the toy, though not necessarily the ones extracted from literature. The study also provided some indication on what type of toy we should build, in particular, its ‘look and feel’. Correspondence to: Ms A. Paiva, IST & Instituto de Engenharia de Sistemas e Computadores, Rua Alves Redol 9, 1000 Lisboa, Portugal. Email: Ana.Paiva@inesc.pt     

Integrating E-Commerce and Games

This paper investigates how many users of commercial interactive systems are not properly agents within the interactive narrative, largely due to the dynamics of branding in cyberspace. Parallels are drawn between the dynamic personalization of e-CRM engines and context aware computing systems. Several seminal games are discussed as examples of systems in which very different relationships exist between users and the system. Arguments are made for designing e-commerce interactive systems that install into games, inside the game narrative. Correspondence to: Ms N. Cummins, Preject Brand Communications Consultancy, Unit P, Carlton Works Studios, Asylum Road, London SE15 2SB, UK. Email: nizami@preject.com     

The BG distributed simulation algorithm

We present a shared memory algorithm that allows a set of f+1 processes to wait-free “simulate” a larger system of n processes, that may also exhibit up to f stopping failures. Applying this simulation algorithm to the k-set-agreement problem enables conversion of an arbitrary k-fault-tolerant{\it n}-process solution for the k-set-agreement problem into a wait-free k+1-process solution for the same problem. Since the k+1-processk-set-agreement problem has been shown to have no wait-free solution [5,18,26], this transformation implies that there is no k-fault-tolerant solution to the n-process k-set-agreement problem, for any n. More generally, the algorithm satisfies the requirements of a fault-tolerant distributed simulation.\/ The distributed simulation implements a notion of fault-tolerant reducibility\/ between decision problems. This paper defines these notions and gives examples of their application to fundamental distributed computing problems. The algorithm is presented and verified in terms of I/O automata. The presentation has a great deal of interesting modularity, expressed by I/O automaton composition and both forward and backward simulation relations. Composition is used to include a safe agreement\/ module as a subroutine. Forward and backward simulation relations are used to view the algorithm as implementing a multi-try snapshot\/ strategy. The main algorithm works in snapshot shared memory systems; a simple modification of the algorithm that works in read/write shared memory systems is also presented. Received: February 2001 / Accepted: February 2001     

Better Living Through Geometry

Mark Weiser described ubiquitous computing as “invisible, everywhere computing that does not live on a personal device of any sort, but is in the woodwork everywhere”[1]. The EasyLiving project is concerned with development of an architecture and technologies for ubiquitous computing environments that allow the dynamic aggregation of diverse I/O devices into a single coherent user experience. Though the need for research in distributed computing, perception and interfaces is widely recognised, the importance of an explicit geometric world model for enhancing the user’s experience of a ubiquitous computing system has not been well-articulated. This paper describes three scenarios that benefit from geometric context and introduces the EasyLiving Geometric Model.     

Expressing Location Information for Applications in the Internet

As part of the Spatial Location Protocol activity in the Internet Engineering Task Force (IETF), we have been working on how to express location information in an interoperable way in the Internet. The objective of this paper is to share our ideas on concepts for enabling interoperability and reuse of location information. These concepts can also be used in the area of ubiquitous computing. Correspondence to: Ms M. Korkea-aho, Department of Computer Science & Engineering, Helsinki University of Technology, Apollokatu 10 A 49, FIN-00100 Helsinki, Finland. Email: mari.korkea-aho@iki.fi     

Automatic video data structuring through shot partitioning and key-frame computing

In video processing, a common first step is to segment the videos into physical units, generally called shots. A shot is a video segment that consists of one continuous action. In general, these physical units need to be clustered to form more semantically significant units, such as scenes, sequences, programs, etc. This is the so-called story-based video structuring. Automatic video structuring is of great importance for video browsing and retrieval. The shots or scenes are usually described by one or several representative frames, called key-frames. Viewed from a higher level, key frames of some shots might be redundant in terms of semantics. In this paper, we propose automatic solutions to the problems of: (i) video partitioning, (ii) key frame computing, (iii) key frame pruning. For the first problem, an algorithm called “net comparison” is devised. It is accurate and fast because it uses both statistical and spatial information in an image and does not have to process the entire image. For the last two problems, we develop an original image similarity criterion, which considers both spatial layout and detail content in an image. For this purpose, coefficients of wavelet decomposition are used to derive parameter vectors accounting for the above two aspects. The parameters exhibit (quasi-) invariant properties, thus making the algorithm robust for many types of object/camera motions and scaling variances. The novel “seek and spread” strategy used in key frame computing allows us to obtain a large representative range for the key frames. Inter-shot redundancy of the key-frames is suppressed using the same image similarity measure. Experimental results demonstrate the effectiveness and efficiency of our techniques.     

Practical CTL* model checking: Should SPIN be extended?

We describe an efficient CTL^* model checking algorithm based on alternating automata and games. A CTL^* formula, expressing a correctness property, is first translated to a hesitant alternating automaton and then composed with a Kripke structure representing the model to be checked, after which this resulting automaton is then checked for nonemptiness. We introduce the nonemptiness game that checks the nonemptiness of a hesitant alternating automaton (HAA). In the same way that alternating automata generalise nondeterministic automata, we show that this game for checking the nonemptiness of HAA, generalises the nested depth-first algorithm used to check the nonemptiness of nondeterministic Büchi automata (used in Spin).     

Linguistic Problems with Requirements and Knowledge Elicitation

Human and conversational aspects of requirements and knowledge identification are employed to show that requirements ‘engineering’ is not the same as civil engineering or scientific problem solving. Not only can requirements not be made fully explicit at the start of a project, they cannot be made fully explicit at all. A need is identified to enhance computer-based information systems (CBIS) development methods to accommodate: plurality of incommensurable perspectives, languages and agendas; dynamic representations of system features that can be experienced rather than abstracted and forced into an abstract paper-based representation; recognition that CBIS development is in general a continuous process where users changing their minds is a natural and necessary indication or organisational vitality.  It is suggested that prototyping and rapid application development go some way to addressing these requirements but that they require further development in the light of the theoretical light thrown on the nature of the problem.     

Seeking the truth about ad hoc join costs

In this paper, we re-examine the results of prior work on methods for computing ad hoc joins. We develop a detailed cost model for predicting join algorithm performance, and we use the model to develop cost formulas for the major ad hoc join methods found in the relational database literature. We show that various pieces of “common wisdom” about join algorithm performance fail to hold up when analyzed carefully, and we use our detailed cost model to derive op timal buffer allocation schemes for each of the join methods examined here. We show that optimizing their buffer allocations can lead to large performance improvements, e.g., as much as a 400% improvement in some cases. We also validate our cost model's predictions by measuring an actual implementation of each join algorithm considered. The results of this work should be directly useful to implementors of relational query optimizers and query processing systems. Edited by M. Adiba. Received May 1993 / Accepted April 1996     

Failure detection and consensus in the crash-recovery model

Summary. We study the problems of failure detection and consensus in asynchronous systems in which processes may crash and recover, and links may lose messages. We first propose new failure detectors that are particularly suitable to the crash-recovery model. We next determine under what conditions stable storage is necessary to solve consensus in this model. Using the new failure detectors, we give two consensus algorithms that match these conditions: one requires stable storage and the other does not. Both algorithms tolerate link failures and are particularly efficient in the runs that are most likely in practice – those with no failures or failure detector mistakes. In such runs, consensus is achieved within time and with 4 n messages, where is the maximum message delay and n is the number of processes in the system. Received: May 1998 / Accepted: November 1999     

Model checking for a probabilistic branching time logic with fairness

We consider concurrent probabilistic systems, based on probabilistic automata of Segala & Lynch [55], which allow non-deterministic choice between probability distributions. These systems can be decomposed into a collection of “computation trees” which arise by resolving the non-deterministic, but not probabilistic, choices. The presence of non-determinism means that certain liveness properties cannot be established unless fairness is assumed. We introduce a probabilistic branching time logic PBTL, based on the logic TPCTL of Hansson [30] and the logic PCTL of [55], resp. pCTL [14]. The formulas of the logic express properties such as “every request is eventually granted with probability at least p”. We give three interpretations for PBTL on concurrent probabilistic processes: the first is standard, while in the remaining two interpretations the branching time quantifiers are taken to range over a certain kind of fair computation trees. We then present a model checking algorithm for verifying whether a concurrent probabilistic process satisfies a PBTL formula assuming fairness constraints. We also propose adaptations of existing model checking algorithms for pCTL [4, 14] to obtain procedures for PBTL under fairness constraints. The techniques developed in this paper have applications in automatic verification of randomized distributed systems. Received: June 1997 / Accepted: May 1998     

Specifications in Context: Stakeholders, Systems and Modelling of Conflict

This paper looks from an ethnographic viewpoint at the case of two information systems in a multinational engineering consultancy. It proposes using the rich findings from ethnographic analysis during requirements discovery. The paper shows how context – organisational and social – can be taken into account during an information system development process. Socio-technical approaches are holistic in nature and provide opportunities to produce information systems utilising social science insights, computer science technical competence and psychological approaches. These approaches provide fact-finding methods that are appropriate to system participants’ and organisational stakeholders’ needs.  The paper recommends a method of modelling that results in a computerised information system data model that reflects the conflicting and competing data and multiple perspectives of participants and stakeholders, and that improves interactivity and conflict management.