1,721,026 research outputs found
Minimising the rank aggregation error
No full textRank aggregation is the problem of generating an overall ranking from a set of individual votes. The aim in doing so is to produce a ranking which is as close as possible to the (unknown) correct ranking for a given distance measure such as the Kendall-tau distance. The challenge is that votes are often both noisy and incomplete. Existing work has largely focused on finding the most likely ranking for a particular noise model (such as Mallows'). Instead, here we focus on minimising the error, i.e., the expected distance between the aggregated ranking and the true underlying one. Specifically, we show that the two objectives result in different rankings, and that these differences become especially significant when many votes are missing. Furthermore, we show how to compute local improvements on existing rankings to reduce the expected error. Finally, we run extensive experiments on both synthetic and real data to compare different aggregation rules. In particular, a surprising result is that for votes generated according to the Mallows' model, Copeland often outperforms Kemeny optimal, despite the latter being the maximum likelihood estimator
Intention-Aware Routing to Minimise Delays at Electric Vehicle Charging Stations
No full textEn-route charging stations allow electric vehicles to greatly extend their range. However, as a full charge takes a considerable amount of time, there may be significant waiting times at peak hours. To address this problem, we propose a novel navigation system, which communicates its intentions (i.e., routing policies) to other drivers. Using these intentions, our system accurately predicts congestion at charging stations and suggests the most efficient route to its user. We achieve this by extending existing time-dependent stochastic routing algorithms to include the battery's state of charge and charging stations. Furthermore, we describe a novel technique for combining historical information with agent intentions to predict the queues at charging stations. Through simulations we show that our system leads to a significant increase in utility compared to existing approaches that do not explicitly model waiting times or use intentions, in some cases reducing waiting times by over 80% and achieving near-optimal overall journey times.Software and Computer TechnologyElectrical Engineering, Mathematics and Computer Scienc
Data for "Intention-Aware Routing of Electric Vehicles" in IEEE Transactions on Intelligent Transportation Systems
No full textFurther data and software used to generate these results can be found at the following URLs (as described in the paper):
Origin-destination data: http://easy.dans.knaw.nl/ui/datasets/id/easy-dataset:50335
Open Source Routing Machine (OSRM): http://project-osrm.org/
OpenStreetMap: http://www.openstreetmap.org/</span
Online mechanism design for scheduling non-preemptive jobs under uncertain supply and demand
No full textWe design new algorithms for the problem of allocating uncertain flexible, and multi-unit demand online given uncertain supply, in order to maximise social welfare. The algorithms can be seen as extensions of the expectation and consensus algorithms from the domain of online scheduling. The problem is especially relevant to the future smart grid, where uncertain output from renewable generators and conventional supply need to be integrated and matched to flexible, non-preemptive demand. To deal with uncertain supply and demand, the algorithms generate multiple scenarios which can then be solved offline. Furthermore, we use a novel method of reweighting the scenarios based on their likelihood whenever new information about supply becomes available. An additional improvement allows the selection of multiple non-preemptive jobs at the same time. Finally, our main contribution is a novel online mechanism based on these extensions, where it is in the agents' best interest to truthfully reveal their preferences. The experimental evaluation of the extended algorithms and different variants of the mechanism show that both achieve more than 85% of the offline optimal economic efficiency. Importantly, the mechanism yields comparable efficiency, while, in contrast to the algorithms, it allows for strategic agents
Compliance in Resource-based Process Models
Full text linkpeer reviewedExecution of business processes often requires resources, the use of which is usually subject to constraints. In this paper, we study the compliance of business processes with resource usage policies. To this end, we relate the execution of a business process to its resource requirements in terms of resources consumed, produced or blocked by tasks of the business process. Policies specifying constraints on resource usage are specified in the form of obligations and the verification of whether a business process complies with a given resource usage policy is formally studied
Route Planning with Breaks and Truck Driving Bans Using Time-Dependent Contraction Hierarchies
No full textMandatory breaks for truck drivers are nowadays scheduled after the route has been decided. However, in some cases it is beneficial to plan these breaks during waiting time caused by truck driving bans. Optimally planning a single break considering driving bans can be done using Dijkstra’s algorithm with multiple labels. This has large effects on predicted travel times: 17% of the analysed routes having a night rest obtain an earlier arrival time by 5 hours on average. However, the computation times of this algorithm are long. A novel heuristic version of time-dependent contraction hierarchies leads to significant reductions in computation times from several seconds to several milliseconds per route. Experiments show that the solutions are still optimal for a representative test set consisting of 10,000 route queries.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.AlgorithmicsTransport and Plannin
Analyzing location-specific error patterns in train data
No full textThrough the years, companies have been exploring the field of data science. The Nederlandse Spoorwegen (NS) is not an exception to this. Modern trains are equipped with sensors that measure a variety of conditions within the train. This data is being stored in their data warehouse. This data has been proven useful for detection and response times to problems, which warrants two high-level goals of the NS: punctuality and reliability. However, even with the available data, visualization and detection of location-specific problems are not yet implemented. Location-specific problems are problems that are not caused by the train, but by the infrastructure or human fault at that specific location. At the moment, most patterns in error codes are only backed up by suspicions, since these error codes are not stored in a way they are easily readable. Therefore, it is hard to find connections between multiple error codes. This document describes the created system that supports the analysis of location-specific error code patterns. With the system, the NS will be able to improve their two high-level goals and ultimately improve customer satisfaction.For the system, a framework was made, which allows the NS to further develop and extend on data analyses. Furthermore, an extensive UI was created, allowing users to investigate found error code patterns and trace back problems to their origin. With the system, the NS is able to verify and create new hypotheses on possible problematic locations. In this document, the problem in elaborated on, multiple solutions are given of which one is chosen and thoroughly motivated, the solutions are elaborated on and, finally, some recommendations for future expansion are given
Bootstrapping LPs in Value Iteration for Multi-Objective and Partially Observable MDPs
No full textIteratively solving a set of linear programs (LPs) is a common strategy for solving various decision-making problems in Artificial Intelligence, such as planning in multi-objective or partially observable Markov Decision Processes (MDPs). A prevalent feature is that the solutions to these LPs become increasingly similar as the solving algorithm converges, because the solution computed by the algorithm approaches the fixed point of a Bellman backup operator. In this paper, we propose to speed up the solving process of these LPs by bootstrapping based on similar LPs solved previously. We use these LPs to initialize a subset of relevant LP constraints, before iteratively generating the remaining constraints. The resulting algorithm is the first to consider such information sharing across iterations. We evaluate our approach on planning in Multi-Objective MDPs (MOMDPs) and Partially Observable MDPs (POMDPs), showing that it solves fewer LPs than the state of the art, which leads to a significant speed-up. Moreover, for MOMDPs we show that our method scales better in both the number of states and the number of objectives, which is vital for multi-objective planning.Algorithmic
A Guide to Solving Pathfinding Problems with Multiple Agents
No full textCurrently, literature regarding Multiagent Path Finding (MAPF) does not give a broad enough overview of all the different approaches. Many papers are hard to read and require proper knowledge of MAPF. The goal of this report is to give a global overview of MAPF. To achieve this goal, we provide a detailed explanation of what MAPF problems look like, as well as giving a clear overview of the strength and weaknesses of different solutions. Besides this theoretical analysis, we also analyse and critique benchmarking performed by other researchers. Following all this, we conclude that the field of MAPF lacks agreement on terminology. Furthermore, performance analysis is limited to researchers choice, skewing research in their own favour
Fuzzy argumentation for trust
No full textIn an open Multi-Agent System, the goals of agents acting on behalf of their owners often conflict with each other. Therefore, a personal agent protecting the interest of a single user cannot always rely on them. Consequently, such a personal agent needs to be able to reason about trusting (information or services provided by) other agents. Existing algorithms that perform such reasoning mainly focus on the immediate utility of a trusting decision, but do not provide an explanation of their actions to the user. This may hinder the acceptance of agent-based technologies in sensitive applications where users need to rely on their personal agents. Against this background, we propose a new approach to trust based on argumentation that aims to expose the rationale behind such trusting decisions. Our solution features a separation of opponent modeling and decision making. It uses possibilistic logic to model behavior of opponents, and we propose an extension of the argumentation framework by Amgoud and Prade to use the fuzzy rules within these models for well-supported decisions
- …
