Software Agents and Web Services

In many software systems, it is advantageous to decompose the processing into relatively independent software agents. In some cases, the decomposition is imposed because different users participate in a decision process. In others, it is required in order to balance the computational load to several processors. At the LIA, research into software agents focuses above all on the decomposition aspect: how can a problem solving process be decomposed so that the agents become as independent as possible?

Current projects:

Past projects:

Technologies for search, recommendation and reputation

One of the most important tasks on the WWW is to find items that best satisfy a set of preferences, a problem we call preference-based search. Most sites require the user to specify a fixed set of criteria and then retrieve the most preferred items from a database. However, due to various shortcomings of human decision-making, people are in general not able to state their preferences. Studies show that only a small portion of users actually manage to find their most preferred options, and often end up with suboptimal results. We have developed new mixed-initiative tools using example-critiquing and suggestions, and shown through user studies that they dramatically increase decision accuracy. For more information, see page on preference-based search with suggestions by Paolo Viappiani .

Often, products or other choices cannot be characterized in a vocabulary that would allow people to express their preferences, or people might not even be aware of their preferences. In such cases, they would like to use a recommender system that gives them ideas of items they might like, based on the user’s rating of other items. A major problem in existing recommendation systems is the cold-start problem: a relatively large number of ratings is required to provide accurate recommendations. We have developed (and patented) at new technique called ontology filtering that reduces the required information to a practically manageable amount. We are in the process of commercializing this through a startup company, Prediggo.

Another use of product ratings and services is to indicate the reputation for quality. Systems for reputation feedback become increasingly important to help people deal with the anonymity of interactions through the internet. Reputation mechanisms can have two roles: signaling the true quality of products or services, or sanctioning bad quality or dishonest behavior.

We are addressing the design of trustworthyreputation mechanisms that are:

  • incentive-compatible: explicit rewards make it in the best interest of rational agents to report the truth. Honest reporting thus becomes a Nash equilibrium of the system;
  • collusion-resistant: small coalitions of rational agents do not have an interest to coordinate on lying strategies;
  • robust: small noise and errors do not perturb the properties of the mechanism;
  • practical;

Here is an overview of some of our results!Current projects:

Past projects:

Distributed Constraint Satisfaction and Optimization

Constraint satisfaction and optimization is a general framework for expressing many combinatorial problems, and is widely used, particularly for resource allocation, scheduling and planning applications. Often, such problems are distributed over multiple agents that control parts of the variables and constraints, and might want to apply different methods to solve them. Over the past decade, we have developed a series of methods for distributed constraint satisfaction and optimization.

  • Asynchronous Aggregation Search (AAS)was our first distributed CSP algorithm. It forms aggregates of values and thus dramatically reduces the complexity of earlier methods such as asynchronous backtracking (ABT). By the same token, it also allows constraints to be controlled by single agents.
  • In the context of AAS, we also developed new techniques for variable reordering and maintaining arc concistency. A cleaned-up overview appears here.
  • We considered coordination problems in large projects with multiple agents, such as the LHC constructed at CERN. We developed new techniques based on local searchand validated them on real planning data from CERN. Carlos Eisenberg has started a company, Synctec, mostly based on this work.
  • We have considered the question of how to minimize the amount of information that must be collected from agents to compute a consistent or optimal solution to a constraint satisfaction problem. We have defined the framework of open constraint programming to characterize this situation. In open constraint programming, variable domains are not known a priori and are only discovered through queries to agents. In most cases, even optimal solutions require only partial knowledge of domains. For optimization, we have an algorithm that is provably optimal, and we also have a distributed version of this algorithm.
  • We have developed a series of algorithms based on dynamic programming. They exploit the fact that distributed problems often have a relatively low treewidth and are thus very suitable for solution by dynamic programming methods. Starting with the basic algorithm, DPOP, we have developed a series of algorithms that build on it and address various shortcomings of dynamic programming. This framework has turned out to be many orders of magnitude more efficient than search-based approaches and has allowed us to solve much larger problems than any earlier algorithm. An overview of the large amount of work on this topic can be gained from the publications of Adrian Petcu.
  • To address the issue of privacy, we have proposed a family of variants of DPOP that make use of code names, obfuscation and homomorphic encryption to provide strong guarantees that any agent’s private knowledge of the problem will not be revealed to the other agents. We have applied these algorithms to various problem classes including vehicle routing problems, and we have shown that our algorithms could largely outperform the previous state of the art in privacy-preserving algorithms.
  • We have also investigated the issue of uncertainty in the problem data, by extending the traditional DCOP framework to that of DCOP under Stochastic Uncertainty (StochDCOP), in which sources of uncertainty are modeled by random variables with known probability distributions. Our novel StochDCOP algorithms are able to discover and exploit the locality of each source of uncertainty to improve efficiency.

Additionally, we have developed and publicly released a “FRamework for Open/Distibuted Optimization” FRODO, which is a Java platform that provides implementations for a large number of algorithms, including SynchBB, MGM and MGM-2, ADOPT, DSA, DPOP, S-DPOP, MPC-Dis(W)CSP4, O-DPOP, AFB, MB-DPOP, Max-Sum, ASO-DPOP, P-DPOP, P2-DPOP, E[DPOP], Param-DPOP, and P3/2-DPOP. The platform makes it possible to simulate multiple agents on a single machine, and also to solve problems in a fully distributed fashion, involving multiple machines communicating over TCP/IP. Random problem generators are provided to carry out performance experiments on a number of problem classes, including graph coloring, meeting scheduling, random Max-DisCSPs, combinatorial auctions, kidney exchange, graphical games, and vehicle routing. The platform is available under an free software license from the dedicated FRODO website.

Current projects:

Past projects: