Search

We adopt an emerging and prominent vision of human-centred Artificial Intelligence that requires building trustworthy intelligent systems. Such systems should be capable of dealing with the challenges of an interconnected, globalised world by handling plurality and by abiding by human values. Within this vision, pluralistic value alignment is a core problem for AI– that is, the challenge of creating AI systems that align with a set of diverse individual value systems. So far, most literature on value alignment has considered alignment to a single value system. To address this research gap, we propose a novel method for estimating and aggregating multiple individual value systems. We rely on recent results in the social choice literature and formalise the value system aggregation problem as an optimisation problem. We then cast this problem as an ℓp-regression problem. Doing so provides a principled and general theoretical framework to model and solve the aggregation problem. Our aggregation method allows us to consider a range of ethical principles, from utilitarian (maximum utility) to egalitarian (maximum fairness). We illustrate the aggregation of value systems by considering real-world data from two case studies: the Participatory Value Evaluation process and the European Values Study. Our experimental evaluation shows how different consensus value systems can be obtained depending on the ethical principle of choice, leading to practical insights for a decision-maker on how to perform value system aggregation., Interactive Intelligence

Air pollution in urban areas poses a significant and pressing challenge for modern society. Unfortunately, the existing network of pollution detectors in many cities is limited in scope and fails to adequately cover the entire geographical area. Consequently, the implementation of spatial prediction algorithms becomes essential to generate high-resolution data. In this paper, we introduce two significant contributions: 1) We formalize the air pollution prediction problem as a Maximum A Posteriori (MAP) estimate within the framework of a Markov Random Field and 2) we propose a message-passing algorithm, which stands out as an efficient solution that surpasses the current state of the art. The experimental procedure has been carried out using the case study of the city of Barcelona, based on a dataset extracted from the BCN Open Data portal.

Interactive Intelligence, Information and Communication Technology

As artificial agents become increasingly embedded in our society, we must ensure that their behavior aligns with human values. Value alignment entails value inference, the process of identifying values and reasoning about how humans prioritize values. We introduce a holistic framework that connects the technical (AI) components necessary for value inference. Subsequently, we discuss how hybrid intelligence'the synergy of human and artificial intelligence'is instrumental to the success of value inference. Finally, we illustrate how value inference both poses significant challenges and provides novel opportunities for multiagent systems research., Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public., Interactive Intelligence, Information and Communication Technology

Values, such as freedom and safety, are the core motivations that guide us humans. A prerequisite for creating value-aligned multiagent systems that involve humans and artificial agents is value inference, the process of identifying values and reasoning about human value preferences. We introduce a framework that connects the value inference steps, and motivate why a hybrid intelligence approach is instrumental for its success. We also highlight the multidisciplinary research challenges that hybrid value inference entails., Interactive Intelligence, Information and Communication Technology

[EN]The concept of shared value was introduced by Porter and Kramer as a new conception of capitalism. Shared value describes the strategy of organizations that simultaneously enhance their competitiveness and the social conditions of related stakeholders such as employees, suppliers and the natural environment. The idea has generated strong interest, but also some controversy due to a lack of a precise definition, measurement techniques and difficulties to connect theory to practice. We overcome these drawbacks by proposing an economic framework based on three key aspects: coalition formation, sustainability and consistency, meaning that conclusions can be tested by means of logical deductions and empirical applications. The presence of multiple agents to create shared value and the optimization of both social and economic criteria in decision making represent the core of our quantitative definition of shared value. We also show how economic models can be characterized as shared value models by means of logical deductions. Summarizing, our proposal builds on the foundations of shared value to improve its understanding and to facilitate the suggestion of economic hypotheses, hence accommodating the concept of shared value within modern economic theory.

We show that any characteristic function game (CFG) G can be always turned into an approximately equivalent game represented using the induced subgraph game (ISG) representation. Such a transformation incurs obvious benefits in terms of tractability of computing solution concepts for G . Our transformation approach, namely, AE-ISG, is based on the solution of a norm approximation problem. We then propose a novel coalition structure generation (CSG) approach for ISGs that is based on graph clustering, which outperforms existing CSG approaches for ISGs by using off-the-shelf optimization solvers. Finally, we provide theoretical guarantees on the value of the optimal CSG solution of G with respect to the optimal CSG solution of the approximately equivalent ISG. As a consequence, our approach allows one to compute approximate CSG solutions with quality guarantees for any CFG. Results on a real-world application domain show that our approach outperforms a domain-specific CSG algorithm, both in terms of quality of the solutions and theoretical quality guarantees.

[EN]Energy management is a key topic for today’s society, and a crucial challenge is the shift from a production system based on fossil fuel to sustainable energy. A key ingredient for this important step is the use of a highly automated power delivery network, where intelligent devices can communicate and collaborate to optimize energy management. This paper investigates a specific model for smart power grids initially proposed by Zdeborov et al. (Phys Rev E Stat Nonlinear Soft Matter Phys 80(4): 2009) where backup power lines connect a subset of loads to generators so to meet the demand of the whole network. Specifically, we extend such model to minimize CO2 emissions related to energy production. In more detail, we propose a formalization for this problem based on the Distributed Constraint Optimization Problem (DCOP) framework and a solution approach based on the min-sum algorithm. We empirically evaluate our approach on a set of benchmarking power grid instances comparing our proposed solution to simulated annealing and to the DSA algorithm. Our results show that min-sum favorably compares with simulated annealing and DSA providing a promising solution method for this model.

We investigate a problem that lies at the intersection of three research areas, namely Automated Negotiation, Vehicle Routing, and Multi-Objective Optimization. Specifically, we investigate the scenario that multiple competing logistics companies aim to cooperate by delivering truck loads for one another, in order to improve efficiency and reduce the distance they drive. In order to do so, these companies need to find ways to exchange their truck loads such that each of them individually benefits. We present a new heuristic algorithm that, given one set of orders to deliver for each company, tries to find the set of all order-exchanges that are Pareto-optimal and individually rational. Furthermore, we present experiments based on real-world test data from two major logistics companies, which show that our algorithm is able to find hundreds of solutions in a matter of minutes.

Procedimientos, sistemas y programas informáticos para optimizar una red de compartición de viajes, que comprenden: recibir peticiones de compartición de viaje; aplicar algoritmo probabilístico voraz a las peticiones para determinar vehículos candidatos que maximizan una función de rendimiento individual que depende de una distancia más corta que recorrerá el vehículo candidato, restringida a que una petición candidata puede estar en un solo vehículo candidato; aplicar programa lineal de enteros a vehículos candidatos para determinar vehículos óptimos que maximizan una función de rendimiento global en forma de agregación de la función de rendimiento individual de los vehículos candidatos; determinar vehículos finales aplicando un algoritmo de anticipación que selecciona vehículos óptimos como vehículos finales excepto los que no incluyen al menos una petición que expira en la etapa de tiempo siguiente a la actual; eliminar del conjunto de peticiones las peticiones incluidas en vehículos finales; y enviar correspondientes respuestas de peticiones atendidas

Peer-to-peer ridesharing could be a solution in the near future to avoid traffic in high populated cities and decreasing the level of pollution, while reducing costs to the individuals. Peer-to-peer ridesharing can optimise the rides with private cars by filling the car with more people on similar routes while reducing slightly the optimisation of the individuals path and their travel/waiting time. The problem is inherently an online problem, which means that a predictive behaviour is fundamental to improve the solution of the ridesharing online problem, as the algorithm can take heed of the predictions to decide to form a car or wait to the future using the predictions as part of the given data. An online approximate algorithm has been proposed to solve the large-scale problem, the algorithm has different predictors and several experiments had been conducted [1, 2] to test which predictor has the greatest performance after using the forecast to optimise. This approach of using a forecast in the optimisation is called predictive approach. The goal of this thesis is to further study an other classical predictive approach and add it to the original work [1], which already had a reactive approach without any predictor, namely look ahead reasoning acting after the optimisation, and a predictive approach acting before the optimisation. The thesis not only focuses on the performance of the predictions but also is concern about the computer resources used by the different predictors and their implementation in the actual algorithm. Actually, the key evaluation characteristic are the optimisation reward, based on the efficiency of the whole algorithm, instead of the usual performance of predictors measured by the efficency of the prediction as it is usual in the studies of this kind.

We show that any characteristic function game (CFG) G can be always turned into an approximately equivalent game represented using the induced subgraph game (ISG) representation. Such a transformation incurs obvious benefits in terms of tractability of computing solution concepts for G. Our transformation approach, namely AE-ISG, is based on the solution of a norm approximation problem. We then propose a novel coalition structure generation (CSG) approach for ISGs that is based on graph clustering, which outperforms existing CSG approaches for ISGs by using off-the-shelf optimisation solvers. Finally, we provide theoretical guarantees on the value of the optimal CSG solution of G wrt the optimal CSG solution of the approximately equivalent ISG. As a consequence, our approach allows one to compute approximate CSG solutions with quality guarantees for any CFG. Results on a real-world application domain show that our approach outperforms a domain-specific CSG algorithm, both in terms of quality of the solutions and theoretical quality guarantees.

Peer-to-peer ridesharing enables people to arrange one-time rides with their own private cars, without the involvement of professional drivers. It is a prominent collective intelligence application producing significant benefits both for individuals (reduced costs) and for the entire community (reduced pollution and traffic). Despite these very promising potential advantages, the percentage of users who currently adopt ridesharing solutions is very low, well below the adoption rate required to achieve said benefits. One of the reasons of this insufficient engagement by the public is the lack of effective incentive policies by regulatory authorities, who are not able to estimate the costs and the benefits of a given ridesharing adoption policy. Here we address these issues by (i) developing a novel algorithm that makes large-scale, real-time peer-topeer ridesharing technologically feasible; and (ii) exhaustively quantifying the impact of different ridesharing scenarios in terms of environmental benefits (i.e., reduction of CO2 emissions, noise pollution, and traffic congestion) and quality of service for the users. Our analysis on a real-world dataset shows that major societal benefits are expected from deploying peer-to-peer ridesharing depending on the trade-off between environmental benefits and quality of service. Results on a real-world dataset show that our approach can produce reductions up to a 70.78% in CO2 emissions and up to 80.08% in traffic congestion.

Co-operative learning in heterogeneous teams refers to learning methods in which teams are organised both to accomplish academic tasks and for individuals to gain knowledge. Competencies, personality and the gender of team members are key factors that influence team performance. Here, we introduce a team composition problem, the so-called synergistic team composition problem (STCP), which incorporates such key factors when arranging teams. Thus, the goal of the STCP is to partition a set of individuals into a set of synergistic teams: teams that are diverse in personality and gender and whose members cover all required competencies to complete a task. Furthermore, the STCP requires that all teams are balanced in that they are expected to exhibit similar performances when completing the task. We propose two efficient algorithms to solve the STCP. Our first algorithm is based on a linear programming formulation and is appropriate to solve small instances of the problem. Our second algorithm is an anytime heuristic that is effective for large instances of the STCP. Finally, we thoroughly study the computational properties of both algorithms in an educational context when grouping students in a classroom into teams using actual-world data.

We focus on Graph-Constrained Coalition Formation (GCCF), a widely studied subproblem of coalition formation where the set of valid coalitions is constrained by a graph. We propose COP-GCCF, a novel approach that models GCCF as a COP. We then solve such COP with a highly-parallel GPU implementation of Bucket Elimination, which is able to exploit the high constraint tightness of COP-GCCF. Results on realistic graphs, i.e., a crawl of the Twitter social graph, show that our approach outperforms state of the art algorithms (i.e., DyCE and IDP G ) by at least one order of magnitude, both in terms of runtime and memory.

We consider Graph-Constrained Coalition Formation (GCCF), a widely studied subproblem of coalition formation in which the set of valid coalitions is restricted by a graph. We propose COP-GCCF, a novel approach that models GCCF as a COP, and we solve such COP with a highly-parallel approach based on Bucket Elimination executed on the GPU, which is able to exploit the high constraint tightness of COP-GCCF. Results show that our approach outperforms state of the art algorithms (i.e., DyCE and IDP^G) by at least one order of magnitude on realistic graphs, i.e., a crawl of the Twitter social graph, both in terms of runtime and memory.

Co-operative learning is used to refer to learning procedures for heterogeneous teams in which individual and teamwork are organised to complete academic tasks. Key factors for team performance are competences, personality and team members' genders. Here, we present a computational model to form heterogeneous teams that incorporates those key factors. In addition, we propose efficient algorithms to partition a classroom into teams of even size and homogeneous performance. The first algorithm is based on an ILP formulation. For small problem instances this approach is appropriate. However, this is not the case for large problems, for which we propose a heuristic algorithm. We study the computational properties of both algorithms in the context of student teams.

Ridesharing is a prominent collective intelligence application producing significant benefits both for individuals (reduced costs) and for the entire community (reduced pollution and traffic). We tackle the online ridesharing (ORS) problem with the objective of forming cost-effective shared rides among commuters that submit requests to be served in a short time period (i.e., in a few minutes). We demonstrate a web-based simulation tool that computes and shows cost-effective shared cars along with the optimal path for each car. Our tool internally employs an online optimisation approach that can tackle large-scale ORS problems originating from real-world data (i.e., with ~400 requests per minute). Specifically, our simulation tool uses data from a real-world dataset, i.e., the New York City taxi dataset.

[EN]In this paper we present, by way of case studies, a proof of concept, based on a prototype working on a automotive data set, aimed at showing the potential usefulness of using formulas of Łukasiewicz propositional logic to query databases in a fuzzy way. Our approach distinguishes itself for its stress on the purely linguistic, contraposed with numeric, formulations of queries. Our queries are expressed in the pure language of logic, and when we use (integer) numbers, these stand for shortenings of formulas on the syntactic level, and serve as linguistic hedges on the semantic one. Our case-study queries aim first at showing that each numeric-threshold fuzzy query is simulated by a Łukasiewicz formula. Then they focus on the expressing power of Łukasiewicz logic which easily allows for updating queries by clauses and for modifying them through a potentially infinite variety of linguistic hedges implemented with a uniform syntactic mechanism. Finally we shall hint how, already at propositional level, Łukasiewicz natural semantics enjoys a degree of reflection, allowing to write syntactically simple queries that semantically work as meta-queries weighing the contribution of simpler ones.

In this work, we adopt a cooperative game theoretic approach in order to tackle the social ridesharing (SR) problem, where a set of commuters, connected through a social network, form coalitions and arrange one-time rides at short notice. In particular, we address two fundamental aspects of this problem. First, we focus on the optimisation problem of forming the travellers' coalitions that minimise the travel cost of the overall system. To this end, we model the formation problem as a Graph-Constrained Coalition Formation (GCCF) one, where the set of feasible coalitions is restricted by a graph (i.e., the social network). Our approach allows users to specify both spatial and temporal preferences for the trips. Second, we tackle the payment allocation aspect of SR, by proposing the first approach that computes kernel-stable payments for systems with thousands of agents. We conduct a systematic empirical evaluation that uses real-world datasets (i.e., GeoLife and Twitter). We are able to compute optimal solutions for medium-sized systems (i.e., with 100 agents), and high quality solutions for very large systems (i.e., up to 2000 agents). Our results show that our approach improves the social welfare (i.e., reduces travel costs) by up to 36.22% with respect to the scenario with no ridesharing. Finally, our payment allocation method computes kernel-stable payments for 2000 agents in less than an hour—while the state of the art is able to compute payments only for up to 100 agents, and does so 84 times slower than our approach.

Bucket elimination (BE) is a framework that encompasses several algorithms, including belief propagation (BP) and variable elimination for constraint optimization problems (COPs). BE has significant computational requirements that can be addressed by using graphics processing units (GPUs) to parallelize its fundamental operations, i.e., composition and marginalization, which operate on functions represented by large tables. We propose a novel approach to parallelize these operations with GPUs, which optimizes the table layout so to achieve better performance in terms of increased speedup and scalability. Our approach allows us to process incomplete tables (i.e., tables with some missing variables assignments), which often occur in several practical applications (such as the ones we consider in our dataset). Finally, we can process tables that are larger than the GPU memory. Our approach outperforms the state-of-the-art technique to parallelize BP on GPUs, achieving better speedups (up to +466% with respect to such parallel technique). We test our method on a publicly available COP dataset, measuring a speedup up to 696.02× with respect to the sequential version. The ability of our technique to process large tables is crucial in this scenario, in which most of the instances generate tables larger than the GPU memory, and hence they cannot be solved with previous GPU techniques related to BE.