Project "Agent-Centered Search"
(scroll down for publications)

Autonomous agents often need to operate in real-time. For example, computer-controlled agents in video games need to move smoothly. Agent-centered search methods interleave planning and plan execution and often decrease the sum of planning and plan-execution time because gathering information early reduces the subsequent amount of planning needed. They have a solid theoretical foundation, are able to use heuristic knowledge to focus their search, can commit to actions in any given amount of time, are able to handle uncertainty (including actuator, sensor, and domain uncertainty) and can be used by single autonomous agents as well as teams of agents with various degrees of communication. They only give advice about which actions to execute and fail gracefully if their advice is ignored from time to time. This makes it easy to integrate them into complete agent architectures. Our analysis and development of agent-centered search methods combines ideas from robotics, artificial intelligence search, and theoretical aspects of graph search. We both develop agent-centered search methods and analyze when they work, why they work, and how well they work. For example, we have introduced the game time model to evaluate search methods. The game time model partitions time into uniform time intervals, an agent can execute one movement during each time interval and search and movements are done in parallel. The objective is to move the agent from its start location to its goal location in as few time intervals as possible. We have also extended Learning Real-Time A* from planning in deterministic domains to worst-case planning in nondeterministic domains, analyzed the speed of convergence of both the deterministic and nondeterministic versions, and studied how to speed up their convergence. We also demonstrated that our ideas apply to other search algorithms as well, such as TBA*.

Representative Overview Publications

Representative Publications on Deterministic Domains

Representative Publications on Nondeterministic Domains

Representative Publications on Applications

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.

Home Page of Sven Koenig