The Experts below are selected from a list of 7110 Experts worldwide ranked by ideXlab platform
Francesca Rossi - One of the best experts on this subject based on the ideXlab platform.
-
General Properties and Termination Conditions for Soft Constraint Propagation
Constraints - An International Journal, 2020Co-Authors: Stefano Bistarelli, Rosella Gennari, Francesca RossiAbstract:Soft Constraints based on semirings are a generalization of classical Constraints, where tuples of variables' values in each Soft Constraint are associated to elements from an algebraic structure called semiring. This framework is able to express, for example, fuzzy, classical, weighted, valued and over-constrained Constraint problems. Classical Constraint propagation has been extended and adapted to Soft Constraints by defining a schema for Soft Constraint propagation l8r. On the other hand, in l1–3r it has been proven that most of the well known Constraint propagation algorithms for classical Constraints can be cast within a single schema. In this paper we combine these two schemas and we provide a more general framework where the schema of l3r can be used for Soft Constraints. In doing so, we generalize the concept of Soft Constraint propagation, and we provide new sufficient and independent conditions for its termination.
-
Abstracting Soft Constraints
Lecture Notes in Computer Science, 2020Co-Authors: Stefano Bistarelli, Philippe Codognet, Yan Georget, Francesca RossiAbstract:We propose an abstraction scheme for Soft Constraint problems and we study its main properties. Processing the abstracted version of a Soft Constraint problem can help us in many ways: for example, to find good approximations of the optimal solutions, or also to provide us with information that can make the subsequent search for the best solution easier. The results of this paper show that the proposed scheme is promising; thus they can be used as a stable formal base for any experimental work specific to a particular class of Soft Constraint problems.
-
New Trends in Constraints - Abstracting Soft Constraints
New Trends in Constraints, 2020Co-Authors: Stefano Bistarelli, Philippe Codognet, Yan Georget, Francesca RossiAbstract:We propose an abstraction scheme for Soft Constraint problems and we study its main properties. Processing the abstracted version of a Soft Constraint problem can help us in many ways: for example, to find good approximations of the optimal solutions, or also to provide us with information that can make the subsequent search for the best solution easier. The results of this paper show that the proposed scheme is promising; thus they can be used as a stable formal base for any experimental work specific to a particular class of Soft Constraint problems.
-
ICAART (1) - MULTI-AGENT Soft Constraint AGGREGATION - A Sequential Approach
2020Co-Authors: Giorgio Dalla Pozza, Francesca Rossi, K. Brent VenableAbstract:We consider a scenario where several agents express their preferences over a common set of variable assignments, by means of a Soft Constraint problem for each agent, and we propose a procedure to compute a variable assignment which satisfies the agents’ preferences at best. Such a procedure considers one variable at a time and, at each step, asks all agents to express its preferences over the domain of that variable. Based on such preferences, a voting rule is used to decide on which value is the best for that variable. At the end, the values chosen constitute the returned variable assignment. We study several properties of this procedure and we show that the use of Soft Constraints allows for a great flexibility on the preferences of the agents, compared to similar work in setting where agents model their preferences via CP-nets, where several restrictions on the agents’ preferences need to be imposed to obtain
-
multi agent Soft Constraint aggregation via sequential voting theoretical and experimental results
Autonomous Agents and Multi-Agent Systems, 2019Co-Authors: Cristina Cornelio, Francesca Rossi, Maria Silvia Pini, Kristen Brent VenableAbstract:We consider scenarios where several agents must aggregate their preferences over a large set of candidates with a combinatorial structure. That is, each candidate is an element of the Cartesian product of the domains of some variables (i.e., features). These scenarios are very common when candidates are described by feature vectors, such as cars, or houses, or any complex product. We assume agents to compactly express their preferences over the candidates via Soft Constraints. This is a compact way to model preferences which naturally models variables domains, and relationship among variables. To aggregate the preferences of the agents, we consider a sequential procedure that asks the agents to vote on one variable at a time. At each step, all agents express their preferences over the domain of a variable; based on such preferences, a voting rule is used to select one value for that variable. When all variables have been considered, the selected values constitute the returned variable assignment, that is, the elected candidate. We study several properties of this procedure (such as Condorcet consistency, anonymity, neutrality, monotonicity, consistency, efficiency, participation, independence of irrelevant alternatives, non dictatorship, and strategy-proofness), by relating them to corresponding properties of the adopted voting rules used for each variable. Moreover, we perform an experimental study on a special kind of Soft Constraints, namely fuzzy Constraints. The experimental study shows that the proposed sequential procedure yields a considerable saving in time with respect to a non-sequential approach, while the winners satisfy the agents just as well, independently of the variable ordering, and of the presence of coalitions of agents.
Stefano Bistarelli - One of the best experts on this subject based on the ideXlab platform.
-
Abstracting Soft Constraints
Lecture Notes in Computer Science, 2020Co-Authors: Stefano Bistarelli, Philippe Codognet, Yan Georget, Francesca RossiAbstract:We propose an abstraction scheme for Soft Constraint problems and we study its main properties. Processing the abstracted version of a Soft Constraint problem can help us in many ways: for example, to find good approximations of the optimal solutions, or also to provide us with information that can make the subsequent search for the best solution easier. The results of this paper show that the proposed scheme is promising; thus they can be used as a stable formal base for any experimental work specific to a particular class of Soft Constraint problems.
-
General Properties and Termination Conditions for Soft Constraint Propagation
Constraints - An International Journal, 2020Co-Authors: Stefano Bistarelli, Rosella Gennari, Francesca RossiAbstract:Soft Constraints based on semirings are a generalization of classical Constraints, where tuples of variables' values in each Soft Constraint are associated to elements from an algebraic structure called semiring. This framework is able to express, for example, fuzzy, classical, weighted, valued and over-constrained Constraint problems. Classical Constraint propagation has been extended and adapted to Soft Constraints by defining a schema for Soft Constraint propagation l8r. On the other hand, in l1–3r it has been proven that most of the well known Constraint propagation algorithms for classical Constraints can be cast within a single schema. In this paper we combine these two schemas and we provide a more general framework where the schema of l3r can be used for Soft Constraints. In doing so, we generalize the concept of Soft Constraint propagation, and we provide new sufficient and independent conditions for its termination.
-
New Trends in Constraints - Abstracting Soft Constraints
New Trends in Constraints, 2020Co-Authors: Stefano Bistarelli, Philippe Codognet, Yan Georget, Francesca RossiAbstract:We propose an abstraction scheme for Soft Constraint problems and we study its main properties. Processing the abstracted version of a Soft Constraint problem can help us in many ways: for example, to find good approximations of the optimal solutions, or also to provide us with information that can make the subsequent search for the best solution easier. The results of this paper show that the proposed scheme is promising; thus they can be used as a stable formal base for any experimental work specific to a particular class of Soft Constraint problems.
-
ATC - A formal framework for trust policy negotiation in autonomic systems: abduction with Soft Constraints
Lecture Notes in Computer Science, 2010Co-Authors: Stefano Bistarelli, Fabio Martinelli, Francesco SantiniAbstract:We show that Soft Constraints can be used to model logical reasoning, that is deduction and abduction (and induction). In particular, we focus on the abduction process and we show how it can be implemented with a (Soft) Constraint removal operator. As a running application example throughout the paper, we reason with access control policies and credentials. In this way, we can associate the level of preference defined by the "Softness" of the Constraint with a "level" of trust. The main benefit comes during the process of automated access authorization based on trust: Soft Constraint operations can be easily adopted to measure the level of trust required for each operation. Moreover, when the level is not sufficient, abduction can be used to compute the missing credentials and the levels that grant the access, making the request a (weighted) logical consequence. The proposed framework can be used to automate the deduction-abduction negotiation processes.
-
modelling multicast qos routing by using best tree search in and or graphs and Soft Constraint logic programming
Electronic Notes in Theoretical Computer Science, 2007Co-Authors: Stefano Bistarelli, Ugo Montanari, Francesca Rossi, Francesco SantiniAbstract:We suggest a formal model to represen t and solve the multicast routing problem in multicast networks. To attain this, we model the netw ork adapting it to a weighted and-or graph, where the weight on a connector corresponds to the cost of sending a pac ket on the network link mo delled by that connector. Then, we use the Soft Constraint Logic Programming (SCLP) framew ork as a convenient declarative programming environment in which to specify related problems. In particular, we show ho w the semantics of an SCLP program computes the best tree in the corresp onding and-or graph: this result can be adopted to find, from a given source node, the multicast distribution tree having minimum cost and reac hing all the destination nodes of the multicast communication. The costs on the connectors can be described also as vectors (multidimensional costs), each component representing a dierent Quality of Service metric v alue. Therefore, the construction of the best tree may in volve a set of criteria, all of which are to be optimized (multi-criteria problem), e.g. maximum global bandwidth and minimum delay that can be experienced on a single link.
Ugo Montanari - One of the best experts on this subject based on the ideXlab platform.
-
Graph Transformation, Specifications, and Nets - Decomposition Structures for Soft Constraint Evaluation Problems: An Algebraic Approach
Graph Transformation Specifications and Nets, 2018Co-Authors: Ugo Montanari, Matteo Sammartino, Alain TcheukamAbstract:(Soft) Constraint Satisfaction Problems (SCSPs) are expressive and well-studied formalisms to represent and solve Constraint-satisfaction and optimization problems. A variety of algorithms to tackle them have been studied in the last 45 years, many of them based on dynamic programming. A limit of SCSPs is its lack of compositionality and, consequently, it is not possible to represent problem decompositions in the formalism itself. In this paper we introduce Soft Constraint Evaluation Problems (SCEPs), an algebraic framework, generalizing SCSPs, which allows for the compositional specification and resolution of (Soft) Constraint-based problems. This enables the systematic derivation of efficient dynamic programming algorithms for any such problem.
-
decomposition structures for Soft Constraint evaluation problems an algebraic approach
Graph Transformation Specifications and Nets, 2018Co-Authors: Ugo Montanari, Matteo Sammartino, Alain TcheukamAbstract:(Soft) Constraint Satisfaction Problems (SCSPs) are expressive and well-studied formalisms to represent and solve Constraint-satisfaction and optimization problems. A variety of algorithms to tackle them have been studied in the last 45 years, many of them based on dynamic programming. A limit of SCSPs is its lack of compositionality and, consequently, it is not possible to represent problem decompositions in the formalism itself. In this paper we introduce Soft Constraint Evaluation Problems (SCEPs), an algebraic framework, generalizing SCSPs, which allows for the compositional specification and resolution of (Soft) Constraint-based problems. This enables the systematic derivation of efficient dynamic programming algorithms for any such problem.
-
modelling multicast qos routing by using best tree search in and or graphs and Soft Constraint logic programming
Electronic Notes in Theoretical Computer Science, 2007Co-Authors: Stefano Bistarelli, Ugo Montanari, Francesca Rossi, Francesco SantiniAbstract:We suggest a formal model to represen t and solve the multicast routing problem in multicast networks. To attain this, we model the netw ork adapting it to a weighted and-or graph, where the weight on a connector corresponds to the cost of sending a pac ket on the network link mo delled by that connector. Then, we use the Soft Constraint Logic Programming (SCLP) framew ork as a convenient declarative programming environment in which to specify related problems. In particular, we show ho w the semantics of an SCLP program computes the best tree in the corresp onding and-or graph: this result can be adopted to find, from a given source node, the multicast distribution tree having minimum cost and reac hing all the destination nodes of the multicast communication. The costs on the connectors can be described also as vectors (multidimensional costs), each component representing a dierent Quality of Service metric v alue. Therefore, the construction of the best tree may in volve a set of criteria, all of which are to be optimized (multi-criteria problem), e.g. maximum global bandwidth and minimum delay that can be experienced on a single link.
-
unicast and multicast qos routing with Soft Constraint logic programming
arXiv: Logic in Computer Science, 2007Co-Authors: Stefano Bistarelli, Ugo Montanari, Francesca Rossi, Francesco SantiniAbstract:We present a formal model to represent and solve the unicast/multicast routing problem in networks with Quality of Service (QoS) requirements. To attain this, first we translate the network adapting it to a weighted graph (unicast) or and-or graph (multicast), where the weight on a connector corresponds to the multidimensional cost of sending a packet on the related network link: each component of the weights vector represents a different QoS metric value (e.g. bandwidth, cost, delay, packet loss). The second step consists in writing this graph as a program in Soft Constraint Logic Programming (SCLP): the engine of this framework is then able to find the best paths/trees by optimizing their costs and solving the Constraints imposed on them (e.g. delay < 40msec), thus finding a solution to QoS routing problems. Moreover, c-semiring structures are a convenient tool to model QoS metrics. At last, we provide an implementation of the framework over scale-free networks and we suggest how the performance can be improved.
-
Soft concurrent Constraint programming
ACM Transactions on Computational Logic, 2006Co-Authors: Stefano Bistarelli, Ugo Montanari, Francesca RossiAbstract:Soft Constraints extend classical Constraints to represent multiple consistency levels, and thus provide a way to express preferences, fuzziness, and uncertainty. While there are many Soft Constraint solving formalisms, even distributed ones, as yet there seems to be no concurrent programming framework where Soft Constraints can be handled. In this article we show how the classical concurrent Constraint (cc) programming framework can work with Soft Constraints, and we also propose an extension of cc languages which can use Soft Constraints to prune and direct the search for a solution. We believe that this new programming paradigm, called Soft cc (scc), can be also very useful in many Web-related scenarios. In fact, the language level allows Web agents to express their interaction and negotiation protocols, and also to post their requests in terms of preferences, and the underlying Soft Constraint solver can find an agreement among the agents even if their requests are incompatible.
Brent K Venable - One of the best experts on this subject based on the ideXlab platform.
-
multi agent Soft Constraint aggregation via sequential voting
International Joint Conference on Artificial Intelligence, 2011Co-Authors: Giorgio Dalla Pozza, Francesca Rossi, Maria Silvia Pini, Brent K VenableAbstract:We consider scenarios where several agents must aggregate their preferences over a large set of candidates with a combinatorial structure. That is, each candidate is an element of the Cartesian product of the domains of some variables. We assume agents compactly express their preferences over the candidates via Soft Constraints. We consider a sequential procedure that chooses one candidate by asking the agents to vote on one variable at a time. While some properties of this procedure have been already studied, here we focus on independence of irrelevant alternatives, non-dictatorship, and strategy-proofness. Also, we perform an experimental study that shows that the proposed sequential procedure yields a considerable saving in time with respect to a non-sequential approach, while the winners satisfy the agents just as well, independently of the variable ordering and of the presence of coalitions of agents.
-
multi agent Soft Constraint aggregation a sequential approach
International Conference on Agents and Artificial Intelligence, 2011Co-Authors: Giorgio Dalla Pozza, Francesca Rossi, Brent K VenableAbstract:We consider a scenario where several agents express their preferences over a common set of variable assignments, by means of a Soft Constraint problem for each agent, and we propose a procedure to compute a variable assignment which satisfies the agents’ preferences at best. Such a procedure considers one variable at a time and, at each step, asks all agents to express its preferences over the domain of that variable. Based on such preferences, a voting rule is used to decide on which value is the best for that variable. At the end, the values chosen constitute the returned variable assignment. We study several properties of this procedure and we show that the use of Soft Constraints allows for a great flexibility on the preferences of the agents, compared to similar work in setting where agents model their preferences via CP-nets, where several restrictions on the agents’ preferences need to be imposed to obtain
-
elicitation strategies for Soft Constraint problems with missing preferences properties algorithms and experimental studies
Artificial Intelligence, 2010Co-Authors: Mirco Gelain, Francesca Rossi, Maria Silvia Pini, Brent K Venable, Toby WalshAbstract:We consider Soft Constraint problems where some of the preferences may be unspecified. This models, for example, settings where agents are distributed and have privacy issues, or where there is an ongoing preference elicitation process. In this context, we study how to find an optimal solution without having to wait for all the preferences. In particular, we define algorithms, that interleave search and preference elicitation, to find a solution which is necessarily optimal, that is, optimal no matter what the missing data will be, with the aim to ask the user to reveal as few preferences as possible. We define a combined solving and preference elicitation scheme with a large number of different instantiations, each corresponding to a concrete algorithm, which we compare experimentally. We compute both the number of elicited preferences and the user effort, which may be larger, as it contains all the preference values the user has to compute to be able to respond to the elicitation requests. While the number of elicited preferences is important when the concern is to communicate as little information as possible, the user effort measures also the hidden work the user has to do to be able to communicate the elicited preferences. Our experimental results on classical, fuzzy, weighted and temporal incomplete CSPs show that some of our algorithms are very good at finding a necessarily optimal solution while asking the user for only a very small fraction of the missing preferences. The user effort is also very small for the best algorithms.
-
dealing with incomplete preferences in Soft Constraint problems
Principles and Practice of Constraint Programming, 2007Co-Authors: Mirco Gelain, Francesca Rossi, Maria Silvia Pini, Brent K VenableAbstract:We consider Soft Constraint problems where some of the preferences may be unspecified. This models, for example, situations with several agents providing the data, or with possible privacy issues. In this context, we study how to find an optimal solution without having to wait for all the preferences. In particular, we define an algorithm to find a solution which is necessarily optimal, that is, optimal no matter what the missing data will be, with the aim to ask the user to reveal as few preferences as possible. Experimental results show that in many cases a necessarily optimal solution can be found without eliciting too many preferences.
O. Tanrikulu - One of the best experts on this subject based on the ideXlab platform.
-
Soft Constraint satisfaction scs blind channel equalization algorithms
International Journal of Adaptive Control and Signal Processing, 1998Co-Authors: O. Tanrikulu, B. Baykal, A.g. Constantinides, J.a. ChambersAbstract:The constant modulus adaptive blind equalization algorithms presented in this paper are shown to correspond to an error performance surface which is much improved upon that of existing algorithms such as the well-known constant modulus or Godard algorithm. Many undesirable local solutions ULSs are avoided by careful derivation. We use a deterministic optimization criterion with a Soft Constraint to obtain an update equation which contains a normalized gradient vector and a particular continuous non-linearity. This approach is extended to multiple Constraints to yield faster converging algorithms. An autoregressive AR channel model is studied to demonstrate analytically the absence of a class of ULSs. Finally, the findings are verified experimentally for various AR and moving-average MA channels. © 1998 John Wiley & Sons, Ltd.
-
Constant modulus blind equalisation algorithms under Soft Constraint satisfaction
1997 IEEE International Conference on Acoustics Speech and Signal Processing, 1997Co-Authors: O. Tanrikulu, B. Baykal, A.g. Constantinides, J.a. ChambersAbstract:New constant modulus (CM) algorithms are presented that are based on Soft Constraint satisfaction. The stationary points of an algorithm in this family are studied for an AR(p) channel and it is shown that Ding-type undesirable local solutions (ULS) do not exist. This is due to the normalisation of the gradient vector and the Soft nonlinearity used in these algorithms. Error performance surfaces (EPS) and convergence trajectories from arbitrary initialisations are presented for various channels that support the analytical findings.
-
Adaptive Soft-Constraint satisfaction (SCS) algorithms for fractionally-spaced blind equalizers
1997 IEEE International Conference on Acoustics Speech and Signal Processing, 1997Co-Authors: B. Baykal, O. Tanrikulu, J.a. ChambersAbstract:Constant modulus algorithms based on a deterministic error criterion are presented. Soft-Constraint satisfaction methods yield a general family of blind equalization algorithms employing nonlinear functions of the equalizer output which must satisfy certain conditions. The algorithms are also extended to cover fractionally-spaced blind equalization. A normalization factor which appears as a result of the deterministic formulation of the problem helps the blind equalizer improve its performance. Also, the family supports a wide range of nonlinear functions. Extensive simulations are presented to reveal convergence characteristics which also include signals from the signal processing information base (SPIB).
