In his pre-dissertation work, Koenig applied Markov Decision Processes (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.

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.

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 Research 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.

PhD thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh (Pennsylvania), 1997.