A central problem in artificial intelligence is how to develop computational models that allow decision-support systems or autonomous agents to react to a situation after performing the right amount of deliberation. Frequently, the complexity of problem solving makes it beneficial to use approximate solutions rather than try to compute the optimal answer. This issue arises in a wide range of application domains including medical trauma management, Bayesian inference, sequence alignment, graphics rendering, web page prefetching, autonomous space exploration, real-time avionics, and robot navigation. This tutorial explores the theory and practice of building intelligent systems that reason explicitly about employing limited computational resources to generate timely solutions to difficult combinatorial optimization, planning and scheduling problems. Solution techniques go beyond simple greedy or reactive algorithms to achieve high-quality solutions while meeting both hard and soft real-time deadlines. We will explore over fifteen years of progress in this area, covering historical perspectives, state-of-the-art solution techniques, and current and future challenges.

Participants should be familiar with introductory artificial intelligence, algorithm design and analysis, and introductory probability and statistics.

Information about the authors

Lloyd Greenwald Lloyd Greenwald is an Assistant Professor of Computer Science and Director of the Intelligent Time-Critical Systems Lab at Drexel University. He received his Ph.D. in Computer Science from Brown University. His research interests include time-critical planning and scheduling, mobile robotics, machine learning, ad hoc and sensor networks, and medical decision making.

Shlomo Zilberstein

Shlomo Zilberstein is an Associate Professor of Computer Science and Director of the Resource-Bounded Reasoning Lab at the University of Massachusetts, Amherst. He received his Ph.D. in Computer Science from the University of California, Berkeley. His research interests include approximate reasoning, decision theory, heuristic search, planning and scheduling, and resource-bounded reasoning.

back to tutorials list