Research Publications
All | |
| Narrow your search | 283 result(s) |
By Type
By Year By Research Group | This paper considers a residential market with real-time electricity pricing and flexible electricity consumption profiles for customers. Such a market raises an optimisation problem for home automation systems where they need to schedule consumption ... The Aircraft Recovery Problem appears when external events cause disruptions in a flight schedule. Thus in order to minimize the losses caused by the externalities, aircrafts must be reallocated (rescheduled) in the best possible way. The aim of this ... In 2007, Bessiere et al. have proposed a framework for learning constraint networks via membership queries, that is, by asking the user to classify total assignments of the variables as positive or negative. In this paper we consider the case where the ... We study the computational complexity of the problem of controlling the result of an election by breaking ties. When the chair is only asked to break ties to choose between one of the co-winners, the problem is trivially easy. However, in multi-round ... In this paper we present a two-fold generalization of conditional preference networks (CP-nets) that incorporates uncertainty. CP-nets are a formal tool to model qualitative conditional statements (cp-statements) about preferences over a set of ... We describe an approach to computing upper bounds on the lengths of solutions to reachability problems in transition systems. It is based on a decomposition of state-variable dependency graphs (causal graphs). Our approach is able to find prac- ... A significant portion of the electricity network capacity is built to run only a few days a year when demand peaks. As a result, expensive power generation plants and equipment costing millions of dollars are sitting idle most of the time, which increases... The next generation of power systems face significant challenges, both in coping with increased loading of an aging infrastructure and incorporating renewable energy sources. Meeting these challenges requires a fundamental change in the operation of power... In social choice settings with strict preferences, random dictatorship rules were characterized by Gibbard [1977] as the only randomized social choice functions that satisfy strategyproofness and ex post eciency. In the more general domain with indi... Constraint satisfaction problems may be nearly tractable. For instance, when the set of relations of a problem is a known tractable language with a few extra relations outside of this language. However, such an observation is in general of little use.... The FOCUS constraint expresses the opposite notion than balancing. In practice, this constraint suffers from the rigidity of its semantics. To tackle this issue, we propose three constraints that generalize FOCUS. We provide for each one a complete ... In the paper we investigate computational complexity of two global constraints, the cumulative constraint and the InterDistance constraint, that are key constraints in modeling and solving scheduling problems. Enforcing domain consistency on these ... We consider a simple sequential allocation procedure for sharing indivisible goods between agents in which agents take turns to pick item. Supposing additive utilities and independence between the agents, we show that the expected social welfare can be... AI planners have to compromise between the speed of the planning process and the quality of the generated plan. Planners based on greedy heuristic search are often able to find plans quickly, but the quality of their solutions is often poor. Planners ... Recently, several methods have been proposed for optimal delete-free planning. We present an incremental compilation approach that enables these methods to be applied to problems with conditional effects, which none of them handle natively. With an ... There are many complex combinatorial problems which involve searching for an undirected graph satisfying a certain property. These problems are often highly challenging because of the large number of isomorphic representations of a possible solution. In ... We introduce MiningZinc, a modeling language and framework for constraint-based mining, one of the most popular tasks in data mining. MiningZinc provides high-level and natural modeling of these mining problems; the resulting models closely resemble ... We discuss what behavioral social choice can contribute to computational social choice. An important trademark of behavioral social choice is to switch perspective away from a traditional sampling approach in the social choice literature and to ask ... We investigate the computational complexity of finding optimal bribery schemes in voting domains where the candidate set is the Cartesian product of a set of variables and voters use CP-nets, an expressive and compact way to represent preferences. ... A Markov Decision Process (MDP) policy presents, for each state, an action, which preferably maximizes the expected utility accrual over time. In this paper, we present a novel explanation system for MDP policies. The system interactively generates... Multisets generalize sets by allowing elements to have repetitions. In this paper, we study from a formal perspective representations of multiset variables, and the consistency and propagation of constraints involving multiset variables. These help us ... We study the impact on strategic voting of tie-breaking by means of considering the order of tied candidates within a random vote. We compare this to another non-deterministic tie-breaking rule where we simply choose between candidates uniformly at ... Protein structure prediction is a challenging optimisation problem to the computer scientists. A large number of existing single-point search algorithms attempt to solve the problem by exploring possible structures and finding the one with the minimum ... A short animated movie detailing primary areas of focus for the Algorithmic Decision Theory group at NICTA. We study a simple sequential allocation mechanism for allocating indivisible goods between agents in which agents take turns to pick items. We focus on computational aspects of agents behaving strategically. We view the allocation procedure as a ... Better understanding of structural class of a given protein reveals important information about its overall folding type and its domain. It can also be directly used to provide critical information on general tertiary structure of a protein which has a ... In this paper, we present a hybrid search framework that embeds a tabu-based local search within a population based genetic algorithm. We applied our hybrid algorithm on simplified protein structure prediction problem. We use a low-resolution ab initio ... Determining the structural class of a given protein can provide important information about its functionality and its general tertiary structure. In the last two decades, the protein structural class prediction problem has attracted tremendous attention ... Protein fold recognition (PFR) is considered as an important step towards protein structure prediction problem. It also provides crucial information about the functionality of the proteins. Despite all the efforts that have been made during the past two ... We present a sound, though incomplete, and tractable propagation procedure for PDDL3 trajectory constraints, with the aim of providing an inexpensive unsatisfiability test for sets of such constraints. The propagator is supported by (tractable) methods... The problem of searching for a plan with cost at most equal to a given absolute bound has attracted increasing interest recently, with several search algorithms tailored specifically to this problem proposed. We investigate instead how to adapt ... In large and complex planning domains, there will almost inevitably be aspects that are not relevant to a specific problem instance. Thus, identifying and removing irrelevant parts from an instance is one of the most important techniques for scaling up... Any-angle pathfinding is a common problem from robotics and computer games: it requires finding a Euclidean shortest path between a pair of points in a grid map. Prior research has focused on approximate online solutions. A number of exact methods ... All-pairs shortest paths (APSP) can eliminate the need to search in a graph, providing optimal moves very fast. A major challenge is storing pre-computed APSP data efficiently. Recently, compression has successfully been employed to scale the use of ... Moving target search, where the goal state changes during a search, has recently seen a revived interest. I-ARA* is a very recent, state-of-the-art incremental algorithm for moving target search in a known terrain. In this work, we address the problem ... Following recent studies of visual attractiveness in vehicle routing, we investigate the inclusion of shape and compactness penalties in computing solutions to the Vehicle Routing Problem (VRP) using a Large Neighbourhood Search (LNS). Visually ... Fuel consumption for a ship can be approximated by a cubic function of the ship's speed, and fuel can account for over half of the total cost of maritime transportation. With rising fuel prices in recent years, there has been increased interest in ... This is a review book that will be published as a SpringerBrief. It contains no NICTA IP. I seek pre-approval for publication. A particularly difficult class of scheduling and routing problems involves an objective that is a sum of time-varying action costs, which increases the size and complexity of the problem. Solve-and-improve approaches, which find an initial solution for a ... We propose an adaptive heuristic for model restarts that aligns symmetry breaking with the dynamic branching heuristic. Experiments show that this method performs very well compared to other symmetry breaking methods. Functional relations are ubiquitous in combinatorial problems - the Global Constraint Catalog lists 120 functional constraints. This paper argues that the ability to express functional constraints with functional syntax leads to more elegant and readable ... Cumulative resource constraints can model scarce resources in scheduling problems or a dimension in packing and cutting problems. In order to efficiently solve such problems with a constraint programming solver, it is important to have strong and fast ... In this paper we propose a forward-backward improvement heuristic for the variant of resource-constrained project scheduling problem aiming to maximise the net present value of a project. It relies on the Lagrangian relaxation method to generate an ... Research regarding the stable marriage and roommate problem has a long and distinguished history in mathematics, computer science and economics. Stability in this context is predominantly core stability or one of its variants in which each deviation is ... Two fundamental notions in microeconomic theory are \emph{efficiency}---no agent can be made better off without making another one worse off---and \emph{strategyproofness}---no agent can obtain a more preferred outcome by misrepresenting his preferences. ... We study the computational complexity of manipulating two stage voting rules like Black's procedure. This voting rule selects the Condorcet winner if they exist and otherwise elects the Borda winner. In general, there is no connection between the ... Social networks are increasingly being used to conduct polls. We introduce a simple model of such social polling. We suppose agents vote sequentially, but the order in which agents choose to vote is not necessarily fixed. We also suppose that an agent’s ... |