Automating Service Composition with Behavioral Synthesis

In this paper, we present a formal framework for composing services in task-oriented systems. We propose a two-stage technique that first identifies the set of policies that maximize the probability of reaching target states, and then constructs a "pruned MDP" to find optimal policies that minimize costs while ensuring maximum probability of task satisfaction. Our approach is based on bi-objective lexicographic optimization over a special Markov Decision Process, allowing us to balance service utilization costs and task satisfaction probabilities.
Imagine you’re building a smart manufacturing system where different services work together to complete tasks. Just like how you might combine different ingredients to make a delicious meal, we want to show how these services can be composed in a way that maximizes their chances of success. Our framework provides a formal way to do this by identifying the best policies for each service to follow, based on probabilities and costs.
To start, we break down the problem into two stages. In the first stage, we find the set of policies that are most likely to reach the target states. These are like the "winning strategies" in a game, where you want to maximize your chances of winning. Once we have these policies, we create a new MDP (a kind of decision-making system) that only allows for optimal actions to be taken, and keeps track of the target states.
In the second stage, we solve a bi-objective optimization problem over this special MDP to find the best policies that balance service utilization costs and task satisfaction probabilities. Think of this as a game where you want to minimize the cost of ingredients while still making sure your meal tastes good. We use a combination of planning and optimization techniques to arrive at an optimal solution.
Our approach is based on formal definitions and provably correct techniques, ensuring that our solutions are reliable and efficient. We also discuss how our framework can be used in smart manufacturing systems, where task-oriented compositions are becoming increasingly important.
In summary, this paper presents a formal framework for composing services in task-oriented systems, allowing us to balance service utilization costs and task satisfaction probabilities while ensuring maximum probability of success. By breaking down the problem into two stages and using bi-objective optimization over a special MDP, we arrive at an optimal solution that can be used in real-world applications like smart manufacturing.