Arrow Research search

Author name cluster

Peter van Beek

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

16 papers
1 author row

Possible papers

16

AAAI Conference 2019 Conference Paper

Finding All Bayesian Network Structures within a Factor of Optimal

  • Zhenyu A. Liao
  • Charupriya Sharma
  • James Cussens
  • Peter van Beek

A Bayesian network is a widely used probabilistic graphical model with applications in knowledge discovery and prediction. Learning a Bayesian network (BN) from data can be cast as an optimization problem using the well-known score-andsearch approach. However, selecting a single model (i. e. , the best scoring BN) can be misleading or may not achieve the best possible accuracy. An alternative to committing to a single model is to perform some form of Bayesian or frequentist model averaging, where the space of possible BNs is sampled or enumerated in some fashion. Unfortunately, existing approaches for model averaging either severely restrict the structure of the Bayesian network or have only been shown to scale to networks with fewer than 30 random variables. In this paper, we propose a novel approach to model averaging inspired by performance guarantees in approximation algorithms. Our approach has two primary advantages. First, our approach only considers credible models in that they are optimal or near-optimal in score. Second, our approach is more efficient and scales to significantly larger Bayesian networks than existing approaches.

PDF Details

IJCAI Conference 2011 Conference Paper

An Empirical Study of Seeding Manipulations and Their Prevention

  • Tyrel Russell
  • Peter van Beek

It is well known that cheating occurs in sports. In cup competitions, a common type of sports competition, one method of cheating is in manipulating the seeding to unfairly advantage a particular team. Previous empirical and theoretical studies of seeding manipulation have focused on competitions with unrestricted seeding. However, real cup competitions often place restrictions on seedings to ensure fairness, wide geographic interest, and so on. In this paper, we perform an extensive empirical study of seeding manipulation under comprehensive and realistic sets of restrictions. A generalized random model of competition problems is proposed. This model creates a realistic range of problem instances that are used to identify the sets of seeding restrictions that are hard to manipulate in practice. We end with a discussion of the implications of this work and recommendations for organizing competitions so as to prevent or reduce the opportunities for manipulating the seeding.

PDF Details DOI

IJCAI Conference 2003 Conference Paper

A Fast and Simple Algorithm for Bounds Consistency of the All Different Constraint

  • Alejandro Ldpez-Ortiz
  • Claude-Guy Quimper
  • John Tromp
  • Peter van Beek

In constraint programming one models a problem by stating constraints on acceptable solutions. The constraint model is then usually solved by interleaving backtracking search and constraint propagation. Previous studies have demonstrated that designing special purpose constraint propagators for commonly occurring constraints can significantly improve the efficiency of a constraint programming approach. In this paper we present a fast, simple algorithm for bounds consistency propagation of the alldifferent constraint. The algorithm has the same worst case behavior as the previous best algorithm but is much faster in practice. Using a variety of benchmark and random problems, we show that our algorithm outperforms existing bounds consistency algorithms and also outperforms—on problems with an easily identifiable property—state-ofthe-art commercial implementations of propagators for stronger forms of local consistency.

PDF

AAAI Conference 1999 Conference Paper

CPlan: A Constraint Programming Approach to Planning

  • Peter van Beek
  • Xinguang Chen
  • University of Alberta

Constraint programming, a methodology for solving difficult combinatorial problems by representing them as constraint satisfaction problems, has shown that a general purpose search algorithm based on constraint propagation combined with an emphasis on modeling can solve large, practical scheduling problems. Given the success of constraint programming on scheduling problems and the similarity of scheduling to planning, the question arises, would a constraint programming approach work as well in planning? In this paper, we present evidencethat a constraint programming approach to planning does indeed work well and has the advantage in terms of time and space efficiency over the current state-of-the-art planners.

PDF Details

IJCAI Conference 1995 Conference Paper

A Theoretical Evaluation of Selected Backtracking Algorithms

  • Grzegorz Kondrak
  • Peter van Beek

In recent years, many new backtracking algorithms for solving constraint satisfaction problems have been proposed. The algorithms are usually evalu­ ated by empirical testing. This method, however, has its limitations. Our paper adopts a different, purely theoretical approach, which is based on char­ acterizations of the sets of search tree nodes visited by the backtracking algorithms. A notion of in­ consistency between instantiations and variables is introduced, and is shown to be a useful tool for char­ acterizing such well-known concepts as backtrack, backjump, and domain annihilation. The charac­ terizations enable us to: (a) prove the correctness of the algorithms, and (b) partially order the algo­ rithms according to two standard performance mea­ sures: the number of nodes visited, and the number of consistency checks performed. Among other re­ sults, we prove the correctness of Backjumping and Conflict-Directed Backjumping, and show that For­ ward Checking never visits more nodes than Backjumping. Our approach leads us also to propose a modification to two hybrid backtracking algo­ rithms, Backmarking with Backjumping (BMJ) and Backmarking with Conflict-Directed Backjumping (BM-CBJ), so that they always perform fewer con­ sistency checks than the original algorithms.

PDF

AAAI Conference 1994 Conference Paper

On the Inherent Level of LocalConsistency in Constraint Networks

  • Peter van Beek

We present a new property called constraint looseneas and show how it can be used to estimate the level of local consistency of a binary constraint network. Specifically, we present a relationship between the looseness of the constraints, the size of the domains, and the inherent level of local consistency of a constraint network. The results we present are useful in two ways. First, a common method for finding solutions to a constraint network is to first preprocess the network by enforcing local consistency conditions, and then perform a backtracking search. Here, our results can be used in deciding which low-order local consistency techniques will not change a given constraint network and thus are not useful for preprocessing the network. Second, much previous work has identified conditions for when a certain level of local consistency is sufficient to guarantee a network is backtrack-free. Here, our results can be used in deciding which local consistency conditions, if any, still need to be enforced to achieve the specified level of local consistency. As well, we use the looseness property to develop an algorithm that can sometimes find an ordering of the variables such that a network is backtrack-free.

PDF Details

AAAI Conference 1992 Conference Paper

On the Minimality and Decomposability of Constraint Networks

  • Peter van Beek

Constraint networks have been shown to be useful in formulating such diverse problems as scene labeling, natural language parsing, and temporal reasoning. Given a constraint network, we often wish to (i) find a solution that satisfies the constraints and (ii) find the corresponding minimal network where the constraints are as explicit as possible. Both tasks are known t. o be NP-complete in the general case. Task (i) is usually solved using a backtracking algorithm, and task (ii) is often solved only approximately by enforcing various levels of local consistency. In this paper, we identify a property of binary constraints called rozu convesity and show its usefulness in deciding when a form of local consistency called path consistency is sufficient to guarantee a network is both minimal and decomposable. Decomposable networks have the property that a solution can be found without backtracking. We show that the row convexity property can be tested for efficiently and we show, by examining applications of constraint networks discussed in the literature, that our results are useful in practice. Thus, we identify a large class of constraint networks for which we can solve both tasks (i) and (ii) efficiently.

PDF Details

AAAI Conference 1990 Conference Paper

Reasoning about Qualitative Temporal Information

  • Peter van Beek

Interval and point algebras have been proposed for representing qualitative temporal information about the relationships between pairs of intervals and pairs of points, respectively. In this paper, we address two related reasoning tasks that arise in these algebras: Given (possibly indefinite) knowledge of the relationships between some intervals or points, (1) find one or more scenarios that are consistent with the information provided, and (2) find all the feasible relations between every pair of intervals or points. Solutions to these problems have applications in natural language processing, planning, and a knowledge representation language. We define computationally efficient procedures for solving these tasks for the point algebra and for a corresponding subset of the interval algebra. Our algorithms are marked improvements over the previously known algorithms. We also show how the results for the point algebra aid in the design of a backtracking algorithm for the full interval algebra that is useful in practice.

PDF Details