Sven Koenig (computer scientist)
Encyclopedia
Sven Koenig is a full professor
in computer science
at the University of Southern California
. He received an M.S. degree in computer science from the University of California at Berkeley in 1991 and a Ph.D.
degree in computer science from Carnegie Mellon University
in 1997, advised by Reid Simmons.
and robotics
researcher
who develops techniques for planning and learning under uncertainty and time constraints, both for single agents and teams of agents. His research often combines ideas from artificial intelligence and robotics with ideas from other disciplines, such as decision theory
, theoretical computer science
, operations research
and economics
.
es (MDPs) to artificial intelligence planning. 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."
Koenig's dissertation on "Goal-Directed Acting with Incomplete Information" describes a robust robot navigation architecture based on partially observable Markov decision process
models. His papers on the subject are highly cited due to their pioneering nature and the subsequent wide adoption of probabilistic robot navigation approaches.
After his dissertation, Koenig laid a broad foundation for incremental heuristic search
in artificial intelligence with the development of search algorithms such as Lifelong Planning A* (LPA*), D* Lite, Adaptive A* (AA*) and Fringe-Saving A* (FSA*). The ideas behind his incremental heuristic search algorithm D* Lite, for example, have been incorporated by others into a variety of path planning systems in robotics, including Carnegie Mellon University's winning entry in the DARPA Urban Challenge.
Koenig is also known for his work on real-time search, ant robots, probabilistic planning with nonlinear utility functions, development and analysis of robot-navigation methods (goal-directed navigation in unknown terrain, localization, coverage and mapping), agent coordination based on cooperative auctions, and any-angle path planning.
and Americas School on Agents and Multiagent Systems, and on the steering committees of the International Conference on Automated Planning and Scheduling and the Symposium on Abstraction, Reformulation, and Approximation.
Recognition of Service Award, an NSF
CAREER award, an IBM
Faculty Partnership Award, a Charles Lee Powell Foundation Award, a Raytheon Faculty Fellowship Award, a Mellon Mentoring Award, a Fulbright Fellowship and the Tong Leong Lim Pre-Doctoral Prize from the University of California at Berkeley.
R. Simmons and S. Koenig. Probabilistic Robot Navigation in Partially Observable Environments. In Proceedings of the International Joint Conference on Artificial Intelligence, 1080–1087, 1995.
S. Koenig. Agent-Centered Search. Artificial Intelligence Magazine, 22, (4), 109-131, 2001.
S. Koenig, M. Likhachev and D. Furcy. Lifelong Planning A*. Artificial Intelligence Journal, 155, (1-2), 93-146, 2004.
S. Koenig, M. Likhachev, Y. Liu and D. Furcy. Incremental Heuristic Search in Artificial Intelligence. Artificial Intelligence Magazine, 25, (2), 99-112, 2004.
J. Svennebring and S. Koenig. Building Terrain-Covering Ant Robots. Autonomous Robots, 16, (3), 313-332, 2004.
S. Koenig and M. Likhachev. Fast Replanning for Navigation in Unknown Terrain. Transactions on Robotics, 21, (3), 354-363, 2005.
M. Lagoudakis, V. Markakis, D. Kempe, P. Keskinocak, S. Koenig, A. Kleywegt, C. Tovey, A. Meyerson and S. Jain. Auction-Based Multi-Robot Routing. In Proceedings of the International Conference on Robotics: Science and Systems, 343-350, 2005.
Y. Liu and S. Koenig. Functional Value Iteration for Decision-Theoretic Planning with General Utility Functions. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 1186–1193, 2006.
Professor
A professor is a scholarly teacher; the precise meaning of the term varies by country. Literally, professor derives from Latin as a "person who professes" being usually an expert in arts or sciences; a teacher of high rank...
in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
at the University of Southern California
University of Southern California
The University of Southern California is a private, not-for-profit, nonsectarian, research university located in Los Angeles, California, United States. USC was founded in 1880, making it California's oldest private research university...
. He received an M.S. degree in computer science from the University of California at Berkeley in 1991 and a Ph.D.
Ph.D.
A Ph.D. is a Doctor of Philosophy, an academic degree.Ph.D. may also refer to:* Ph.D. , a 1980s British group*Piled Higher and Deeper, a web comic strip*PhD: Phantasy Degree, a Korean comic series* PhD Docbook renderer, an XML renderer...
degree in computer science from Carnegie Mellon University
Carnegie Mellon University
Carnegie Mellon University is a private research university in Pittsburgh, Pennsylvania, United States....
in 1997, advised by Reid Simmons.
Research
Koenig is an artificial intelligenceArtificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
and robotics
Robotics
Robotics is the branch of technology that deals with the design, construction, operation, structural disposition, manufacture and application of robots...
researcher
Researcher
A researcher is somebody who performs research, the search for knowledge or in general any systematic investigation to establish facts. Researchers can work in academic, industrial, government, or private institutions.-Examples of research institutions:...
who develops techniques for planning and learning under uncertainty and time constraints, both for single agents and teams of agents. His research often combines ideas from artificial intelligence and robotics with ideas from other disciplines, such as decision theory
Decision theory
Decision theory in economics, psychology, philosophy, mathematics, and statistics is concerned with identifying the values, uncertainties and other issues relevant in a given decision, its rationality, and the resulting optimal decision...
, theoretical computer science
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
, operations research
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
and economics
Economics
Economics is the social science that analyzes the production, distribution, and consumption of goods and services. The term economics comes from the Ancient Greek from + , hence "rules of the house"...
.
Scientific Achievements
In his pre-dissertation work, Koenig applied Markov Decision ProcessMarkov decision process
Markov decision processes , named after Andrey Markov, provide a mathematical framework for modeling decision-making in situations where outcomes are partly random and partly under the control of a decision maker. MDPs are useful for studying a wide range of optimization problems solved via...
es (MDPs) to artificial intelligence planning. The standard textbook in artificial intelligence, Artificial Intelligence: A Modern Approach
Artificial Intelligence: A Modern Approach
Artificial Intelligence: A Modern Approach is a college textbook on Artificial Intelligence, written by Stuart J. Russell and Peter Norvig. The third edition of the book was released 11 December 2009...
(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."
Koenig's dissertation on "Goal-Directed Acting with Incomplete Information" describes a robust robot navigation architecture based on partially observable Markov decision process
Partially observable Markov decision process
A Partially Observable Markov Decision Process is a generalization of a Markov Decision Process. A POMDP models an agent decision process in which it is assumed that the system dynamics are determined by an MDP, but the agent cannot directly observe the underlying state...
models. His papers on the subject are highly cited due to their pioneering nature and the subsequent wide adoption of probabilistic robot navigation approaches.
After his dissertation, Koenig laid a broad foundation for incremental heuristic search
Incremental heuristic search
Incremental heuristic search algorithms combine both incremental and heuristic search to speed up searches of sequences of similar search problems, which is important in domains that are only incompletely known or change dynamically. Incremental search has been studied at least since the late 1960s...
in artificial intelligence with the development of search algorithms such as Lifelong Planning A* (LPA*), D* Lite, Adaptive A* (AA*) and Fringe-Saving A* (FSA*). The ideas behind his incremental heuristic search algorithm D* Lite, for example, have been incorporated by others into a variety of path planning systems in robotics, including Carnegie Mellon University's winning entry in the DARPA Urban Challenge.
Koenig is also known for his work on real-time search, ant robots, probabilistic planning with nonlinear utility functions, development and analysis of robot-navigation methods (goal-directed navigation in unknown terrain, localization, coverage and mapping), agent coordination based on cooperative auctions, and any-angle path planning.
Professional Activities
Koenig was conference co-chair of the 2004 International Conference on Automated Planning and Scheduling, program co-chair of the 2005 International Joint Conference on Autonomous Agents and Multi-Agent Systems and program co-chair of the 2007 and 2008 AAAI Nectar programs. He served or serves on the editorial boards of several artificial intelligence and robotics journals, on the board of directors of the Robotics: Science and Systems Foundation, on the advisory boards of the Journal of Artificial Intelligence ResearchJournal of Artificial Intelligence Research
The Journal of Artificial Intelligence Research is a free on-line peer-reviewed scholarly journal publishing papers in all areas of artificial intelligence. It was established in 1993, and was one of the first electronic scientific journals. It has published more than 300 papers as of 2005...
and Americas School on Agents and Multiagent Systems, and on the steering committees of the International Conference on Automated Planning and Scheduling and the Symposium on Abstraction, Reformulation, and Approximation.
Honors and awards
Koenig is the recipient of an ACMAssociation for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
Recognition of Service Award, an NSF
National Science Foundation
The National Science Foundation is a United States government agency that supports fundamental research and education in all the non-medical fields of science and engineering. Its medical counterpart is the National Institutes of Health...
CAREER award, an IBM
IBM
International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
Faculty Partnership Award, a Charles Lee Powell Foundation Award, a Raytheon Faculty Fellowship Award, a Mellon Mentoring Award, a Fulbright Fellowship and the Tong Leong Lim Pre-Doctoral Prize from the University of California at Berkeley.
Selected References
S. Koenig. Goal-Directed Acting with Incomplete Information. PhD thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh (Pennsylvania), 1997.R. Simmons and S. Koenig. Probabilistic Robot Navigation in Partially Observable Environments. In Proceedings of the International Joint Conference on Artificial Intelligence, 1080–1087, 1995.
S. Koenig. Agent-Centered Search. Artificial Intelligence Magazine, 22, (4), 109-131, 2001.
S. Koenig, M. Likhachev and D. Furcy. Lifelong Planning A*. Artificial Intelligence Journal, 155, (1-2), 93-146, 2004.
S. Koenig, M. Likhachev, Y. Liu and D. Furcy. Incremental Heuristic Search in Artificial Intelligence. Artificial Intelligence Magazine, 25, (2), 99-112, 2004.
J. Svennebring and S. Koenig. Building Terrain-Covering Ant Robots. Autonomous Robots, 16, (3), 313-332, 2004.
S. Koenig and M. Likhachev. Fast Replanning for Navigation in Unknown Terrain. Transactions on Robotics, 21, (3), 354-363, 2005.
M. Lagoudakis, V. Markakis, D. Kempe, P. Keskinocak, S. Koenig, A. Kleywegt, C. Tovey, A. Meyerson and S. Jain. Auction-Based Multi-Robot Routing. In Proceedings of the International Conference on Robotics: Science and Systems, 343-350, 2005.
Y. Liu and S. Koenig. Functional Value Iteration for Decision-Theoretic Planning with General Utility Functions. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 1186–1193, 2006.