Research Publications
All Conference Paper | |
| Narrow your search | 173 result(s) |
By Type By Year By Research Group | We propose an online form of the cake cutting problem. This models situations where agents arrive and depart during the process of dividing a resource. We show that well known fair division procedures like cut-and-choose and the Dubins-Spanier moving ... Reducing traveling delay by optimizing traffic signal schedules at intersection has long been under research. Similarly, many vehicle technologies have been applied to reduce fuel consumption and emission. One major source of fuel consumption and ... Proteins are one of the most vital macromolecules on the cellular level. In order to understand the function of a protein, its structure needs to be determined. For this purpose, different computational approaches have been introduced. Genetic algorithms ... Pathfinding is important in many applications, including games, robotics and GPS itinerary planning. In games, most pathfinding methods rely on runtime search. Despite numerous enhancements introduced in recent years, runtime search has the disadvantage ... Diagnosis is traditionally defined on a space of hypotheses (typically, all the combinations of zero or more possible faults). In the present paper, we argue that a suitable reformulation of this hypothesis space can lead to more efficient diagnostic ... We present a theory of abstraction for diagnosis of discrete-event systems. We show what properties an abstraction should satisfy for the diagnosis to be computable and correct. We also show how to determine diagnosability with an abstract model.... Reliable and informative alarm processing is important for improving the situational awareness of operators of electricity networks and other complex systems. Earlier approaches to alarm processing have been predominantly syntactic, based on text-level ... Reliable and informative alarm processing is important for improving the situational awareness of operators of electricity networks and other complex systems. Earlier approaches to alarm processing have been predominantly syntactic, based on text-level ... We formulate DES diagnosis as the problem of finding preferred candidates in a space of hypotheses. This formulation allows us to compute an exhaustive diagnosis by solving a series of simple problems, called “diagnosis tests”, which consist in ... The increased use of health information technology in hospitals brings with it a growing need to appreciate the contexts in which health information technology may be used. Information flow and workflow are directly affected by the implementation of such ... Usually propagation-basedconstraintsolversconstructacon- straint network as a conjunction of constraints. They provide propagators for each form of constraint c. In order to increase expressiveness, systems also usually provide propagators for reified ... In this paper, we introduce Kangaroo, a constraint-based local search system. While existing systems such as Comet maintain invariants after every move, Kangaroo adopts a lazy strategy, updating invariants only when they are needed. Our empirical ... In this paper we present a model for the carpet cutting prob- lem in which carpet shapes are cut from a rectangular carpet roll with a fixed width and sufficiently long length. Our exact solution approaches decompose the problem into smaller parts and ... The ability to model search in a constraint solver can be an essential asset for solving combinatorial problems. However, existing infrastructure for defining search heuristics is often inadequate. Either modeling capabilities are extremely limited or ... The ability to model search in a constraint solver can be an essential asset for solving combinatorial problems. However, existing infrastructure for defining search heuristics is often inadequate. Either modeling capabilities are extremely limited or ... We present an approach to propagation based solving, Boolean equi-propagation, where constraints are modelled as propagators of information about equalities between Boolean literals. Propagation based solving applies this information as a form of partial ... We consider manipulation problems when the manipulator only has partial information about the votes of the nonmanipulators. Such partial information is described by an information set, which is the set of profiles of the nonmanipulators that are ... We prove that it is NP-hard for a coalition of two manipulators to compute how to manipulate the Borda voting rule. This resolves one of the last open problems in the computational complexity of manipulating common voting rules. Because of this ... Nanson’s and Baldwin’s voting rules select a winner by successively eliminating candidates with low Borda scores. We show that these rules have a number of desirable computational properties. In particular, with unweighted votes, it is NP-hard to ... We study the computational complexity of finding the next most preferred solution in some common formalisms for representing constraints and preferences. The problem is computationally intractable for CSPs, but is polynomial for tree-shaped CSPs and ... Pathfinding in uniform-cost grid environments is a problem commonly found in application areas such as robotics and video games. The state-of-the-art is dominated by hierarchical pathfinding algorithms which are fast and have small memory overheads but ... From an automated planning perspective the problem of prac- tical mobile robot control in realistic environments poses many important and contrary challenges. On the one hand, the planning process must be lightweight, robust, and timely. Over the ... Set and multiset variables in constraint programming have typically been represented using subset bounds. However, this is a weak representation that neglects potentially useful information about a set such as its cardinality. For set variables, the ... We present a new approach to enhancing answer set programming (ASP) with constraint programming (CP) techniques based on conflict-driven learning and lazy nogood generation. Modular extensibility is a highly desirable property of a domain-specific language (DSL): the ability to add new features without affecting the implementation of existing features. Functional mixins (also known as open recursion) are very suitable for ... My research proposes a new technique for speeding up grid-based pathfinding in performance-sensitive or resource-limited application areas such as robotics and video games. I work specifically on the problem of identifying and eliminating symmetric ... We explore a symmetry-based reformulation technique which can speed up optimal pathfinding on undirected uniform-cost grid maps by over 30 times. Our offline approach decomposes grid maps into a set of empty rectangles, removing from each all interior... Lazy clause generation is a powerful approach to reducing search in constraint programming. This is achieved by recording sets of domain restrictions that previously lead to failure as new clausal propagators. Symmetry breaking approaches are also ... Representing and solving constraint satisfaction problems is one of the challenges of artificial intelligence. In this paper, we present answer set programming (ASP) models for an important and very general class of constraints, including all constraints ... Vehicle Routing Problems in the Operations Research and Artificial Intelligence literature often allow only standard constraints plus (optionally) one ``side'' constraint. However, in practice, every problem has a number of side constraints, some of ... We solve constraint satisfaction problems through translation to answer set programming (ASP). Our reformulations have the property that unit-propagation in the ASP solver achieves well defined local consistency properties like arc, bound and range ... In this study, we consider a task allocation model with interdependent tasks, where tasks are assigned based on what agents report about their privately known capabilities and costs. Since selfish agents may strategically misreport their private ... Navigating thousands of mobile units to their targets, on navigation graphs such as grid maps, is well beyond the capability of optimal multi-agent pathfinding algorithms. Suboptimal algorithms can handle large numbers of units, yet the quality of their ... Zinc is a high-level logical modelling language. Zinc supports constraints in non-Boolean contexts, in the form of partial functions and in the form of constraints on local variables in non-Boolean expressions. Zinc models are executed on constraint ... The stable marriage problem is a well-known problem of matching men to women so that no man and woman, who are not married to each other, both prefer each other. Such a problem has a wide variety of practical applications, rang- ing from matching ... SAT and its extensions like SAT Modulo Theories or Lazy Clause Generation can handle many problems efficiently and fully auto- matically. However, their activity-based variable selection heuristics make search chaotic, i.e., extremely sensitive to the... We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like scheduling, frequency allocations and graph coloring ... Partial-order schedules are valued because they are flexible, and therefore more robust to unexpected delays. Previous work has indicated that constructing partial-order schedules by a two-stage method, in which a fixed-time schedule is first found ... Diagnosis of discrete event systems amounts to finding good explanations, in the form of system trajectories consistent with a given set of partially ordered observations. This problem is closely related to planning, and in fact can be recast as a ... We define an incremental lower bound function for additive cost planning, based on repeatedly solving and strengthening the delete-relaxation of the problem. We show that it is monotonically increasing, and thus in the limit will produce an optimal plan. ... Heterogeneous nonmonotonic multi-context systems (MCS) permit different logics to be used in different contexts, and link them via bridge rules. We investigate the role of symmetry detection and symmetry breaking in such systems to eliminate symmetric ... We propose AllDiffPrecedence, a new global constraint that combines together an AllDifferent constraint with precedence constraints that strictly order given pairs of variables. We identify a number of applications for this global constraint including ... The stable marriage problem is a well-known problem of matching men to women so that no man and woman, who are not married to each other, both prefer each other. It has a wide variety of practical applications, ranging from match- ing resident doctors... Given the preferences of several agents over a common set of candidates, voting trees can be used to select a candidate (the winner) by a sequence of pairwise competitions modelled by a binary tree (the agenda). The majority graph compactly represents the... The stable marriage problem is a well-known problem of matching men to women so that no man and woman, who are not married to each other, both prefer each other. Such a problem has a wide variety of practical applications, ranging from matching resident... We consider fuzzy 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... Factored planning methods aim to exploit locality to efficiently solve large but “loosely coupled” planning problems by computing solutions locally and propagating limited information between components. However, all factored planning methods ... We consider the problem of computing optimal plans for propositional planning problems with action costs. In the spirit of leveraging advances in general-purpose automated reasoning for that setting, we develop an approach that operates by solving a ... We consider the problem of Consensus Clustering. Given a finite set of input clusterings over some data items, a consensus clustering is a partition of the items which matches as closely as possible the given input clusterings. The best exact approach to ... Planning based on propositional SAT(isfiability) is a powerful approach to computing step-optimal plans given a parallel execution semantics. In this setting: (i) a solution plan must be minimal in the number of plan steps required, and (ii) ... Although clause weighting local search algorithms have produced some of the best results on a range of challenging satisfiability (SAT) benchmarks, this performance is dependent on the careful hand-tuning of sensitive parameters. When such hand-tuning is ... In the planning-as-SAT paradigm there have been numerous recent developments towards improving the speed and scalability of planning at the cost of finding a step-optimal parallel plan. These developments have been towards: (1) Query strategies that ... We describe a restricted class of planning problems and polynomial time membership and plan existence decision algorithms for this class. The definition of the problem class is based on a graph representation of planning problems, similar to Petri nets... Recent times have seen the development of planners that exploit advances in SAT(isfiability) solving technology to achieve good performance. In that spirit we develop the approximate contingent planner PSLSPLAN. Our approach is based on local search for ... Despite significant improvements over the last two decades, local search techniques still struggle to compete with the best systematic methods when solving highly structured real-world satisfiability (SAT) problems. Recent work has successfully employed a... In this paper we describe a stochastic local search (SLS) procedure for finding satisfying models of satisfiable propositional formulae. This new algorithm, gNovelty$^+$, draws on the features of two other WalkSAT family algorithms: R+AdaptNovelty$^+$ and... We describe an approach to deriving consistent heuristics for automated planning, based on explicit search in abstract state spaces. The key to managing complexity is interleaving composition of abstractions over different sets of state variables with ... Heuristic search is a leading approach to domain-independent planning. For cost-optimal planning, however, existing admissible heuristics are generally too weak to effectively guide the search. Pattern database heuristics (PDBs), which are based on ... The key to efficient on-the-fly reachability analysis based on unfolding is to focus the expansion of the finite prefix towards the desired marking. However, current unfolding strategies typically equate to blind (breadth-first) search. They do not ... 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 ... When healthcare organisations plan the introduction of advanced health information systems, they need to envision future use. In this paper we describe four different ways of modeling the flow of information in a healthcare context: normative, indicating ... 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 ... |