Project "Agent-Centered Search"

Autonomous agents often need to operate in real-time. For example, computer-controlled agents in combat 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 (as required for real-time animation or driving), are able to handle uncertainty (such as 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 extended Learning Real-Time A* from planning in deterministic domains to worst-case planning in nondeterministic domains and analyzed the speed of convergence for both the deterministic and nondeterministic versions. Our results have recently been generalized by researchers from UCLA (Bonet) to average-case planning in nondeterministic domains. We have also studied how to speed up the convergence of Learning Real-Time A*. Our FALCONS method finds shortest paths up to sixty percent faster than LRTA* in terms of action executions and up to seventy percent faster in terms of trials. This research opens up new avenues of research for the design of novel successor-selection rules that speed up the convergence of both real-time search methods and reinforcement-learning methods. For example, researchers at Kyoto University have developed their own successor-selection rules and tested them against FALCONS as a benchmark.

The "Artificial Intelligence Topics" webpages on "Real-Time Reasoning" of the Association for the Advancement of Artificial Intelligence link to this page.

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