Context-aware Non-electronic Service Discovery and Composition

Yifei ZhangSpectrum Research Repository (Concordia University) 2015

Abstract

In the modern web ecosystem, service discovery and composition are essential for fulfilling complex user requests. While traditional research focuses on electronic services, this work extends these concepts to "non-electronic" services—physical entities such as restaurants, movie theaters, and shopping malls. We propose a context-aware framework that utilizes a hybrid context model to handle both low-level sensor data and high-level predicate logic. By employing a backtracking algorithm with soft constraints, the system avoids "null" solutions, instead providing users with multiple "good enough" options ranked by satisfaction scores. A replanning module and a diversity filter further refine the user experience.

1. Introduction

Automated Service Composition (ASC) has long been a cornerstone of web service research, typically involving the chaining of APIs to automate digital workflows. However, human daily life is primarily composed of physical interactions. Planning a night out—finding a restaurant that fits a budget, is near a specific theater, and aligns with a movie's end time—is a complex composition problem involving non-electronic services. These services are often treated as "black boxes" because they lack the standardized input/output parameters of digital APIs.

This paper presents a framework for context-aware discovery and composition of these physical services. By integrating real-world context (location, time, budget) and allowing for flexible constraint satisfaction, the system mimics human decision-making to provide realistic, actionable itineraries.

2. The Challenge of Non-Electronic Services

Traditional ASC planners are often rigid. They rely on hard constraints; if a single condition (e.g., a $100 budget) is violated by even a small margin, the planner returns a "null" result. This is impractical for real-world scenarios where a user might accept a slightly more expensive meal if it saves significant travel time. Furthermore, physical services require a sophisticated context model to bridge the gap between raw sensor data (GPS) and high-level concepts (user preferences or activity states).

3. The Proposed Framework

The framework consists of three core innovations designed to handle the ambiguity of the physical world.

3.1 Hybrid Context Modeling

To represent the environment accurately, the system employs a multi-layered context model:

  • Key-Value Pairs: Used for low-level data such as coordinates and timestamps.
  • Predicate Logic: Used for high-level states, such as determining if a user has already visited a specific location.
  • Domain-Independent Ontology: Ensures the system understands the semantic relationships between different service categories (e.g., a "Bistro" is a type of "Restaurant").

3.2 Soft Constraints and Satisfaction Scores

The "secret sauce" of this approach is the transition from binary logic to soft constraints. Each constraint is assigned a satisfaction degree between 0 and 1. The overall quality of a plan is represented by a satisfaction score ($\omega$). If a plan exceeds a budget slightly, it is not discarded; instead, its $\omega$ value is penalized. This allows the system to rank and present "good enough" solutions rather than failing entirely.

3.3 Composition and Diversity Filtering

The system uses a Customized Backtracking Search Algorithm (BSA) to navigate the state-space tree of possible service sequences. To ensure the user is presented with a diverse range of options, the framework incorporates a diversity filter based on Levenshtein distance. By comparing the sequences of service IDs, the system filters out plans that are too similar (e.g., the same itinerary but with a different coffee shop next door), ensuring the $k$ results returned are meaningfully different.

4. Implementation and Evaluation

The framework was implemented as a "Personal Entertainment Planner" using a Mashup Engine that aggregates live data from Google Places, Yelp, Foursquare, and Google Maps.

4.1 Performance

The system demonstrated high efficiency in real-world testing:

  • Discovery Phase: Multi-threaded service discovery consistently took between 2 and 3 seconds.
  • Composition Phase: The BSA showed linear scalability. Planning a complex itinerary with five distinct service types took approximately 2.02 seconds.

4.2 User Study

A study involving eight participants evaluated the prototype. The system received high marks across several metrics:

  • Success Rate of Plan Generation: 4.7/5
  • Response Time Satisfaction: 4.5/5
  • Overall Plan Quality: 4.1/5

5. Conclusion and Future Work

The proposed framework successfully brings the benefits of automated service composition to the physical world. By prioritizing "good enough" solutions through soft constraints and ensuring result diversity, the system provides a more human-centric approach to planning.

Future work will address attribute sparsity in third-party APIs and explore parallelizing the backtracking search to handle even more complex service meshes. Additionally, moving from static satisfaction weights to learned user preferences could further personalize the planning experience.

Summary updated

Abstract

In today’s web, many web services are created and updated on the Internet. In many cases, a single service is not sufficient to respond to the user’s request and often services should be combined through service composition to fulfill business goals. Service discovery and service composition can be highly compatible with context, i.e., according to context information, e.g., location, budget and time, services are chosen and composed. Moreover, we include non-electronic services, e.g., restaurants, movie theaters shopping malls and so on, into service composition. Non-electronic services are rarely considered in existing service composition research, however are frequently used in people’s daily life. In this thesis, we provide an approach for using contexts to discover and compose non-electronic services. We present a new context model which is to make it more suitable for service composition. This model is also able to handle both low level sensor data and high level data in predicated logic. Our service composition algorithm uses soft constraints, dissatisfaction of which causes a penalty instead of the fail of planning. With this feature, the service composition algorithm can give the user several “good enough” solutions, instead of null solution. Additionally, a replanning module is developed to refine the solution according to user’s further adjustments of his or her requirements. As a motivating example, a web based Personal Entertainment Planner system is built.
BibTeX
@inproceedings{zhang2015context,
  author = {Yifei Zhang},
  title = {{Context-aware Non-electronic Service Discovery and Composition}},
  booktitle = {Spectrum Research Repository (Concordia University)},
  year = {2015},
}
Figure