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