Normalized Interactions between autonomous agents

The CEC Project GOAL (Esprit 6283) aims to develop generic software tools to support a new project management paradigm, in which projects are collaborative, decentralised and inter-organizational. To support inter-organizational interaction, communication and cooperation, we are developing a design framework for formalizing the flow of information between organizations, specifying access to and provision of project services, and defining project-wide standards and procedures. This framework is based on normalizing interactions between autonomous software agents by specifying messages and protocols for inter-agent communication and cooperation. This paper reviews the framework, and then focusses on the specification and implementation of a case study, the automation of a distributed document review procedure. This is both a successful proof of concept and a demonstration of how Artificial Intelligence technologies can support inter-organizational project management. It also points the way to agent brokering, an enhancement of object brokering in distributed open systems, where the satisfaction of service requests can be subject to negotiation.Supported by CEC Esprit Project GOAL (Esprit 6283) and CEC Esprit BRA Medlar II (Esprit 6471).Supported by CEC Esprit Project GOAL (Esprit 6283).     

A magnetic bead-based DNA extraction and purification microfluidic device

This article introduces a novel magnetic bead-based DNA extraction and purification device using active magnetic mixing approach. Mixing and separation steps are performed using functionalised superparamagnetic beads suspended in cell lysis buffer in a circular chamber that is sandwiched between two external magnetic coils. Non-uniform nature of magnetic field causes temporal and spatial distribution of beads within the chamber. This process efficiently mixes the lysis buffer and whole blood in order to extract DNA from target cells. Functionalized surface of the magnetic beads then attract the exposed DNA molecules. Finally, DNA-attached magnetic beads are attracted to the bottom of the chamber by activating the bottom magnetic coil. DNA molecules are extracted from magnetic beads by washing and re-suspension processes. In this study, a circular PMMA microchamber, 25 μL in volume, 500 μm in depth and 8 mm in diameter was fabricated to purify DNA from spiked bacterial cell cultures into the whole blood sample using Promega Magazorb DNA extraction kit. The lysis efficiency was evaluated using a panel of Gram-positive (Bacillus subtilis) and Gram-negative (Escherichia coli) bacterial cells cultures into the blood sample to achieve approximately 100,000 copy levels inside the chip. Manufacturer’s standard extraction protocol was modified to a more simplified process suitable for chip-based extraction. The lysis step was performed using 5 min incubation at 56 °C followed by 5 min incubation at room temperature for binding process. Temperature rise was generated and maintained by the same external magnetic coils used for active mixing. The yield/purity and recovery levels of the extracted DNA were evaluated using quantitative UV spectrophotometer and real-time PCR assay, respectively. Real-time PCR results indicated efficient chip-based bacterial DNA extraction using modified extraction protocol comparable to the standard bench-top extraction process.     

Visualization and Analysis‐Oriented Reconstruction of Material Interfaces

Reconstructing boundaries along material interfaces from volume fractions is a difficult problem, especially because the under‐resolved nature of the input data allows for many correct interpretations. Worse, algorithms widely accepted as appropriate for simulation are inappropriate for visualization. In this paper, we describe a new algorithm that is specifically intended for reconstructing material interfaces for visualization and analysis requirements. The algorithm performs well with respect to memory footprint and execution time, has desirable properties in various accuracy metrics, and also produces smooth surfaces with few artifacts, even when faced with more than two materials per cell.     

Adopt,adapt, abandon: Understanding why some young adults start,and then stop,using instant messaging

Instant messaging (IM) has become a popular and important mode of staying in touch for teens and young adults. It allows for easy, frequent and lightweight interaction that contributes to building and sustaining friendships, as well as coordinating social activities. Despite the initial appeal of IM, however, some have found it too distracting and have changed their usage or abandoned it. I interviewed 21 former users of IM about their adoption, usage and eventual abandonment of the technology. Results show that participants were initially attracted to features of IM that enabled them to maximize their use of leisure time via easy and frequent interaction with their friends, but that, in a different usage context, these same features became distracting and annoying. Participants adapted their behavior to avoid these drawbacks, but IM did not support these adaptations effectively. In particular, IM did not allow for control over interruptions, which became more important as their contact lists grew and social time became scarce; and they ultimately abandoned the technology. These results point to a need for understanding use beyond adoption, and a theoretical and practical focus on understanding the adaptation and changing utility that accompany long-term usage of technologies.     

Indoor robot gardening: design and implementation

This paper describes the architecture and implementation of a distributed autonomous gardening system with applications in urban/indoor precision agriculture. The garden is a mesh network of robots and plants. The gardening robots are mobile manipulators with an eye-in-hand camera. They are capable of locating plants in the garden, watering them, and locating and grasping fruit. The plants are potted cherry tomatoes enhanced with sensors and computation to monitor their well-being (e.g. soil humidity, state of fruits) and with networking to communicate servicing requests to the robots. By embedding sensing, computation, and communication into the pots, task allocation in the system is de-centrally coordinated, which makes the system scalable and robust against the failure of a centralized agent. We describe the architecture of this system and present experimental results for navigation, object recognition, and manipulation as well as challenges that lie ahead toward autonomous precision agriculture with multi-robot teams.     

Towards capacity and profit optimization of video-on-demand services in a peer-assisted IPTV platform

This paper studies the conditions under which peer-to-peer (P2P) technology may be beneficial in providing IPTV services over typical network architectures. It has three major contributions. First, we contrast two network models used to study the performance of such a system: a commonly used logical “Internet as a cloud” model and a “physical” model that reflects the characteristics of the underlying network. Specifically, we show that the cloud model overlooks important architectural aspects of the network and may drastically overstate the benefits of P2P technology. Second, we propose an algorithm called Zebra that pre-stripes content across multiple peers during idle hours to speed up P2P content delivery in an IPTV environment with limited upload bandwidth. We also perform simulations to measure Zebra’s effectiveness at reducing load on the content server during peak hours. Third, we provide a cost-benefit analysis of P2P video content delivery, focusing on the profit trade-offs for different pricing/incentive models rather than purely on capacity maximization. In particular, we find that under high volume of video demand, a P2P built-in incentive model performs better than any other model, while the conventional no-P2P model generates more profits when the request rate is low. The flat-reward model generally falls in between the usage-based model and the built-in model in terms of profitability except for low request rates. We also find that built-in and flat-reward models are more profitable than the usage-based model for a wide range of subscriber community sizes. Funding for J. Rahe’s research has been provided by AT&T Labs, the State of California under the MICR Oprogram, and by the Toshiba Corporation. Zhen Xiao is partially supported by China MOST project (2006BAH02A10).     

Formalisations and applications of BPMN

We present two formalisations of the Business Process Modelling Notation (BPMN). In particular, we introduce a semantic model for BPMN in the process algebra CSP; we then study an augmentation of this model in which we introduce relative timing information, allowing one to specify timing constraints on concurrent activities. By exploiting CSP refinement, we are able to show some relationships between the timed and the untimed models. We then describe a novel empirical studies’ model, and the transformation to BPMN, allowing one to apply our formal semantics for analysing different kinds of workflows. To provide a better facility for describing behaviour specification about a BPMN diagram, we also present a pattern-based approach using which a workflow designer could specify properties which could otherwise be difficult to express. Our approach is specifically designed to allow behavioural properties of BPMN diagrams to be mechanically verified via automatic model checking as provided by the FDR tool. We use two examples to illustrate our approach.     

Property specifications for workflow modelling

Previously we provided two formal behavioural semantics for the Business Process Modelling Notation (BPMN) in the process algebra CSP. By exploiting CSP’s refinement orderings, developers may formally compare their BPMN models. However, BPMN is not a specification language, and it is difficult and sometimes impossible to use it to construct behavioural properties against which other BPMN models may be verified. This paper considers a pattern-based approach to expressing behavioural properties. We describe a property specification language PL for capturing a generalisation of Dwyer et al.’s Property Specification Patterns, and present a translation from PL into a bounded, positive fragment of linear temporal logic, which can then be automatically translated into CSP for simple refinement checking. We present a detailed example studying the behavioural properties of an airline ticket reservation business process. Using the same example we also describe some recent results on expressing behavioural compatibility within our semantic models. These results lead to a compositional approach for ensuring deadlock freedom of interacting business processes.     

Linear-Time Recognition of Helly Circular-Arc Models and Graphs

A circular-arc model ℳ is a circle C together with a collection A\mathcal{A} of arcs of C. If A\mathcal{A} satisfies the Helly Property then ℳ is a Helly circular-arc model. A (Helly) circular-arc graph is the intersection graph of a (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear-time recognition algorithms have been described both for the general class and for some of its subclasses. However, for Helly circular-arc graphs, the best recognition algorithm is that by Gavril, whose complexity is O(n ³). In this article, we describe different characterizations for Helly circular-arc graphs, including a characterization by forbidden induced subgraphs for the class. The characterizations lead to a linear-time recognition algorithm for recognizing graphs of this class. The algorithm also produces certificates for a negative answer, by exhibiting a forbidden subgraph of it, within this same bound.