International Conference on Automated Planning and Scheduling 2006
Research Style of Sven Koenig
Situated agents (such as robots or decision-support systems) must be able to make good decisions in complex situations that involve a substantial degree of uncertainty, yet find solutions in a timely manner despite the large number of potential contingencies. My research provides the foundation for building such agents. Most of my research centers around techniques for decision making (planning and learning) that enable single agents and teams of agents to act intelligently in their environments and exhibit goal-directed behavior in real-time, even if they have only incomplete knowledge of their environment, imperfect abilities to manipulate it, limited or noisy perception or insufficient reasoning speed.
I believe that it is important to create a strong algorithmic foundation for agents. Therefore, I develop new (ideally: fast) decision-making methods, implement them, study their properties theoretically and experimentally, and apply them to domains such as planetary exploration, supply-chain management, medicine, crisis management (such as oil-spill containment), robotics and real-time games (entertainment, serious games, training and simulation). In particular, I both build systems and prove theorems about their behavior. I also study the properties of decision-making methods developed by other researchers to determine how good they are and when they should be used.
I believe that the key to making progress in my research area is to combine ideas from different decision-making disciplines such as artificial intelligence, decision theory (including non-linear utility functions), operations research (including Markov decision processes), and theoretical computer science (including on-line search), which requires serious technical advances to reconcile the different assumptions and approaches in a way that results in synergy between them. I pursued degrees in business administration and artificial intelligence precisely because I was interested in the decision-making techniques that different disciplines have to offer. This also enables me to collaborate effectively with researchers outside of artificial intelligence, including researchers from operations research and theoretical computer science. Consequently, I have published broadly in artificial intelligence and robotics but very occasionally also in theoretical computer science and mathematics. In particular, many researchers publish in one area of artificial intelligence only but I have published in the areas of search, planning, agents, numerical artificial intelligence and control (including reasoning under uncertainty), and machine learning, among others. I restrict my publications to self-selective archival conferences with small acceptance rates whenever possible, such as AAAI, IJCAI, ICAPS (and its predecessors AIPS and ECP), AAMAS (and its predecessor Autonomous Agents), ICML, COLT, NIPS, UAI, KR. and others. For example, only about 16 percent of the papers submitted to IJCAI 2007 were accepted for oral presentation.
From 1995 to 1997, I demonstrated that it is possible to combine ideas from different decision-making disciplines by developing a mobile robot architecture based on partially observable Markov decision process models (POMDPs) from operations research that allows robots to navigate robustly despite a substantial amount of uncertainty. This research resulted in a very reliable robot architecture that overcomes the deficiencies of purely topological or metric robot navigation approaches, which I demonstrated on an indoor mobile robot that received navigation requests from users worldwide via the World Wide Web and has traveled more than 230 kilometers. My current research continues to combine ideas from different decision-making disciplines, resulting in novel insights and algorithms. For example, I am combining ideas from artificial intelligence planning and utility theory to create the foundations for building decision-support systems that fit the risk preferences of human decision makers in high-stake decision situations much better than current systems; I am combining ideas from robotics and theoretical computer science to analyze common robot-navigation methods in unknown terrain for the first time, resulting in a much better understanding of their quality; I am combining ideas from heuristic search and algorithm theory to develop re-planning methods in highly dynamic domains that, different from the ones previously studied in artificial intelligence, are able to provide guarantees on the resulting solution quality; I am combining ideas from robotics and economics to build teams of robots that use auctions to distribute tasks autonomously among themselves; and I am combining ideas from real-time heuristic search and robotics to build terrain-covering ant robots that promise to result in fault-tolerant navigation behavior for teams of minimalistic and thus cheap robots.
My research results are used in classes and seminars. For example, they have been discussed recently at
My research results are cited in textbooks. For example, the standard textbook in artificial intelligence ("Artificial Intelligence: A Modern Approach") states "The connection between MDPs and AI planning problems was made first by Sven Koenig (1991), who showed how probabilistic STRIPS operators provide a compact representation for transition models." and "Although Kalman filtering was well-known as a localization method in control theory for decades, the general probabilistic formulation of the localization problem did not appear in the AI literature until much later, through the work of Tom Dean and colleagues (1990, 1990) and Simmons and Koenig (1995)."
My research results are used by others. For example, our Dynamic A* Lite (= D* Lite) algorithm has been extended at Carnegie Mellon University for use on their robots (without any involvement by us). Maxim Likhachev (now at the University of Pennsylvania) and Dave Ferguson from CMU used a combination of ARA* and D* Lite called Anytime D* to plan long motions involving complex maneuvers (such as traversal of parking lots and complex u-turns) for the winning DARPA Urban Challenge entry from CMU. Dave Ferguson and Tony Stentz from Carnegie Mellon University used elements of D* Lite in a highly optimized version of their Field D* system. Joseph Carsten and Art Rankin from NASA's Jet Propulsion Laboratory installed this version of Field D* on the Mars rovers "Spirit" and "Opportunity" (without any involvement by us) and first let it control a rover on Mars in February 2007 after testing it on a rover on Mars in November 2006.
My research webpages are used as educational tools. For example, they are linked by the "Artificial Intelligence Topics" webpages on "Search" of the Association for the Advancement of Artificial Intelligence, the "Artificial Intelligence Topics" webpages on "Real-Time Reasoning" of the Association for the Advancement of Artificial Intelligence, the "Reinforcement Learning Sample Complexity Analysis" webpages, and the game programming webpages on "Amit's Thoughts on Path-Finding and A*".
International Conference on Automated Planning and Scheduling 2006