Projects of Sven Koenig

A common theme of my research projects is planning and learning despite uncertainty and incomplete information, including how to represent decision-making tasks, which preference models to use, and how to solve the resulting planning and learning problems efficiently. This includes, for example:

• different ways for dealing with uncertainty and incomplete information: One way, for example, is to model the uncertainty probabilistically using Markov decision process models, which results in probabilistic planning and reinforcement-learning problems. This is what my POMDP-based robot navigation architecture does. Another way is use greedy on-line planning methods, which interleave planning and plan execution in a way that results in deterministic planning problems. Examples of greedy on-line planning methods include agent-centered search and assumption-based planning. Agent-centered search, for example, is used by greedy mapping; and assumption-based planning is used by planning with the freespace assumption. Greedy mapping and planning with the freespace assumption are common-sense robot navigation methods whose solution quality (travel distance of the robots) has been studied by me for the first time. A third way is for robots to leave information on the ground. This is what my ant robots do.
• different preference models: Decision-support systems need to use similar preference models as the human decision makers that they support, otherwise they are of not much use. However, most artificial intelligence planners and reinforcement-learning mechanisms use simplistic preference models. For example, a lot of planning research is funded for defense applications, space applications, and environmental applications (for example, containing oil spills). Artificial intelligence planners typically maximize the probability of achieving their goals or minimize the expected plan-execution cost, even though human decision makers are risk-averse in these situations. I therefore study how to plan with more realistic preference models than is typically done.
• fast planning despite complex preference models and large numbers of contingencies: Systems that deal with uncertainty by interleaving planning and plan execution need to plan very fast since they have to plan repeatedly. To make planning fast, I study both planning methods with limited look-ahead (called agent-centered search) and planning methods that reuse information from previous searches (called re-planning methods).
• coordinating teams of agents despite uncertainty and incomplete information: Teams of agents are faster and more fault tolerant than single agents. I therefore study how agents can coordinate efficiently (both in terms of the required amount of computation and communication) under uncertainty and incomplete information, using teams of robots in unknown terrain as example. My ant robots, for example, coordinate implicitly by reading trails left by other robots. My auction robots, on the other hand, coordinate explicitly via auctions.

I am currently pursuing the following research directions:

• Fast Replanning in Symbolic Planning, Robotics and Games
• Biologically-Inspired Multi-Agent Systems (Ant Robots)
• Market Mechanisms for Agent Coordination (Auction Robots)
• Planning under Uncertainty with Realistic Preference Models
• Reinforcement Learning
• Robot Planning Tasks and Methods
• Agent Architectures for Coping with Uncertainty (POMDP-Based Robot Navigation)
• Agent-Centered Search (Real-Time Heuristic Search)
• Distributed Constraint Optimization
• Additional Projects on Heuristic Search
• Computer Games (Umbrella Project)
• Greedy On-Line Planning (Umbrella Project)

I was once pursuing the following research directions:

• Time-Delayed Teleoperation of Lunar Rovers

(You can click on the project titles for more information and publications.)

Home Page of Sven Koenig