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 a large number of potential contingencies. Our research is intended to help provide a strong foundation for building such agents. Most of our research centers around methods for decision making 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. We (namely, my research group and our collaborators) develop new decision-making methods, implement them and study their properties theoretically and experimentally, often using problems from robotics as motivation. We also study decision-making methods developed by other researchers to determine how good they are and when they should be used.

We believe that the key to making progress in our research area is to combine ideas from different decision-making disciplines, such as artificial intelligence, decision theory, operations research and theoretical computer science, 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 methods that different disciplines have to offer. This background also enables me to build up the necessary collaborations with researchers outside of artificial intelligence. It is therefore no surprise that, during my two years as program director at the National Science Foundation, I worked on furthering interdisciplinary and international research collaborations (among other things). With respect to interdisciplinary research collaborations, I was a member of the ICES (Interface between Computer Science and Economics and Social Sciences) and NRI (National Robotics Initiative) teams and received a Director's Award for Collaborative Integration twice, which is conferred by the National Science Foundation upon employees who demonstrate outstanding accomplishments in collaborative efforts that involve more than one discipline or directorate (or for an interagency effort that crosses the spectrum of fundamental science, mathematics and engineering). I also helped to initiate efforts to further the interface between artificial intelligence and operations research. With respect to international research collaborations, I helped to initiate the NSF-Deutsche Forschungsgemeinschaft (DFG) Collaborative Research effort (with a focus on autonomous learning), organized an IJCAI Session on Funding Opportunities for International Research Collaborations. and helped to initiate the NSF European Extended Lab Visit Program for Graduate Students in Artificial Intelligence and Robotics.

We have published broadly in artificial intelligence (and more narrowly in robotics) and try to restrict our publications to self-selective archival conferences with small acceptance rates, such as IJCAI, AAAI, ICAPS (and its predecessors AIPS and ECP), AAMAS (and its predecessor Autonomous Agents), ICML, COLT, NIPS, UAI, KR, CP and SODA.

As part of my dissertation, I have demonstrated that it is possible to combine ideas about search 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 reliable robot architecture that overcomes the deficiencies of purely topological or metric robot navigation approaches, which was used on an indoor mobile robot that received navigation requests from users worldwide via the World Wide Web and traveled more than 230 kilometers. Since then, we have continued to combine ideas from different decision-making disciplines, resulting in novel insights and methods. For example, we have combined 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 better than current systems; we have combined ideas from robotics and theoretical computer science to analyze common robot-navigation methods in unknown terrain, resulting in a better understanding of their quality; we have combined ideas from heuristic search and algorithm theory to develop re-planning methods in highly dynamic domains that, different from the ones typically studied in artificial intelligence, are able to provide guarantees on the resulting solution quality; we have combined ideas from robotics and economics to build teams of robots that use auctions to distribute tasks autonomously among themselves; and we have combined 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.

While this list might appear diverse, there is a common underlying thrust, namely to bring about advances that extend the reach of search (in a broad sense, including heuristic search, hillclimbing and dynamic programming). Search methods apply to almost all decision-making problems ("everything is search"). Yet, there are different communities that study search, for example, in artificial intelligence, robotics, theoretical computer science and operations research. It seems that these communities have become stuck with certain search methods and domains and are not actively following the research progress made by the other communities. We have thus helped to found the International Symposium on Combinatorial Search (SoCS) in an attempt to bring these communities together. In our own research, we are trying to bridge the gap by both making search methods more powerful and thus more useful (pushing emerging classes of search methods) and by applying them to novel domains. Some of the more unusual functionalities include fast replanning (incremental heuristic search), probabilistic planning with realistic preference models and any-angle path planning. Some of the more unusual domains include ant robotics, distributed constraint optimization and auction-based coordination systems.

Our research results are used in classes and seminars. For example, they have recently been discussed at

among others. (Sorry, I stopped updating this list but please do send me an email in case you would like to get listed.)

Our research results are cited in textbooks. For example, the standard textbook in artificial intelligence ("Artificial Intelligence: A Modern Approach" - second edition) 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)."

Our research results are used by others and resulted in a technology commercialization award from the USC Stevens Center for Innovation Technology. To give one example, our Dynamic A* Lite (= D* Lite) algorithm won a AAAI Classic Paper (= "Test of Time") Honorable Mention and has been extended at Carnegie Mellon University for use on their robots (without any involvement by us). Maxim Likhachev 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 then used Field D* on the Mars rovers "Spirit" and "Opportunity" on Mars (again without any involvement by us). A team of the University of Sherbrooke (Canada) and the Canadian Space Agency (including Khaled Belghith, Froduald Kabanza and Leo Hartman) used elements of Generalized Adaptive A* in a novel randomized path planning approach that was incorporated into a system intended to improve group support operations on the Space Station Remote Manipulator (again without any involvement by us).

International Conference on Automated Planning and Scheduling 2006

Home Page of Sven Koenig