Professor and Associate Director

Peter van BeekResearch interests

Professor van Beek's research interests span the field of artificial intelligence with a focus on representation and reasoning, constraint programming, constraint satisfaction, backtracking algorithms, planning, scheduling, optimization, applied machine learning, probabilistic reasoning, and applications of artificial intelligence. A recent additional interest is algorithms and techniques in computational photography.

A theme in much of his work is constraint programming, a methodology for solving difficult combinatorial optimization problems. In a constraint programming approach, one specifies constraints on acceptable solutions and search is used to find a solution that satisfies the constraints. Constraint programming is applicable to a wide variety of interesting problems, from vision to probabilistic reasoning to compiler optimization.

Degrees and awards

BSc (British Columbia), MMath, PhD (Waterloo)

Best Paper Award, Canadian Conference on AI (2011); Fellow of the AAAI (2008); Best Paper Award, Canadian Conference on AI (2008); Faculty of Mathematics Fellow, University of Waterloo (2004-2007); IBM CAS Fellow (2003-2008); Best Paper Award (Innovative Applications Track), International Conference on Principles and Practice of Constraint Programming (2001); Best Paper Award, Canadian Conference on AI (2001); Outstanding Paper Award, International Joint Conference on Artificial Intelligence (1995)

Industrial and sabbatical experience

Since graduating in 1990, Professor van Beek has had several applied research projects.

In a past project, Professor van Beek and his students investigated constraint programming techniques for the sequencing and scheduling of manufacturing assembly lines, using car assembly lines as the test-bed application. The car assembly line sequencing problem arose from a collaboration with Shiva Soft Inc. (now Matrikon) of Edmonton, Alberta. A system developed by Shiva Soft using expert-system technology currently schedules the production of cars on assembly lines in two North American assembly plants of a major car company. Using a constraint programming approach, Professor van Beek and his students were able to significantly improve the production schedules as measured on real data.

More recently, Professor van Beek and his students have pursued a project with IBM Canada which investigated constraint programming techniques for instruction scheduling. Modern architectures allow instruction level parallelism and it is the job of the compiler to generate code that takes advantage of this parallelism. This task can be viewed as a scheduling task, where instructions are appropriately scheduled to start at a time step on a particular functional unit. Current compilers use non-optimal methods to solve the scheduling task. Professor van Beek and his students developed optimal approaches to the problem for realistic architectures, improving on previous approaches as measured on widely used industrial benchmarks.

Representative publications

M. Beg and P. van Beek. A Constraint Programming Approach for Integrated Spatial and Temporal Scheduling for Clustered Architectures. ACM Transactions on Embedded Computing Systems, 13(1):14:1-14:23, 2013.

M. Chase, A.M. Malik, T. Russell, R.W. Oldford, and P. van Beek. A Computational Study of Heuristic and Exact Techniques for Superblock Instruction Scheduling. Journal of Scheduling, 15(6):743-756, 2012.

T. Russell and P. van Beek. A Hybrid Constraint Programming and Enumeration Approach for Solving NHL Playoff Qualification and Elimination Problems. European Journal of Operational Research, 218(3):819-828, 2011.

W. Li, P. Poupart, and P. van Beek. Exploiting Structure in Weighted Model Counting Approaches to Probabilistic Inference. Journal of Artificial Intelligence Research, 40:729-765, 2011.

T. Russell, A. M. Malik, M. Chase, and P. van Beek. Learning Heuristics for the Superblock Instruction Scheduling Problem. IEEE Transactions on Knowledge and Data Engineering, 21(10):1489-1502, 2009.

University of Waterloo
Contact information: 

Profiles by type