This tutorial presents techniques for dealing with the fact that the execution of plans and schedules in the real world cannot assume a static environment: the world changes non-deterministically during problem solving and execution. We present techniques from the Artificial Intelligence and Operations Research literature for handling uncertainty in planning and scheduling with emphasis on practical techniques. Such techniques include reactive, on-line scheduling and planning, and proactive, off-line techniques that build solutions that can cope with uncertain events, as well as intermediate approaches between these extremes.

Information about the authors

Cristopher Beck

J. Christopher Beck received a PhD in Artificial Intelligence in 1999 from the University of Toronto under the supervision of Mark S. Fox. From 1994 to 1999 he was the project manager of the Intelligent Scheduling Research Group at the Enterprise Integration Laboratory at University of Toronto. The focus of his research was measurements of problem structure as a basis for scheduling heuristics within a constraint-based scheduling framework. From 1999 until 2002 he was a software developer and Senior Scientist on the Scheduler team at ILOG, SA in Gentilly, France. As of June, 2002, he moved to the position of Staff Scientist at the Cork Constraint Computation Centre, University College Cork. His research interests focus on problem structure, hybrid algorithms, search in constraint-directed scheduling, and in the extension of constraint modeling and solving capabilities to incorporate aspects of real-world scheduling such as uncertainty, dynamic arrival of activities, and robustness.

Cristopher Beck

Thierry Vidal received a PhD in Artificial Intelligence in 1995 from the University of Toulouse under the supervision of Malik Ghallab. He had worked in the Robotics and AI team of the LAAS-CNRS in Toulouse, France, working on temporal constraint processing in temporal planning (the IxTeT system) and in task scheduling, with a special focus on uncertain durations. In 1996-97 he was a guest researcher in Erik Sandewall's team at the Department of Computer Science of the University of Linköping, Sweden, where he conducted basic research work in the area of on-line decision making through contingent plan recognition and reactive controller synthesis. From 1997 he is assistant professor at ENIT in Tarbes, France, working in the Automated Production team of the Production Engineering Laboratory. His current research interests are uncertain constraint reasoning in planning, scheduling and resource allocation, multi-agent approaches to scheduling, reactivity, conditional planning and robust scheduling.

back to tutorials list