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
- S. Koenig. Agent-Centered Search. Artificial Intelligence Magazine, 22, (4), 109-131, 2001. [downloadable]
Representative Publications on Deterministic Domains
- D. Furcy and S. Koenig. Speeding up the Convergence of Real-Time Search. In AAAI Conference on Artificial Intelligence (AAAI), 891-897, 2000. [downloadable]
- S. Koenig and B. Szymanski. Value-Update Rules for Real-Time Search. In AAAI Conference on Artificial Intelligence (AAAI), 718-724, 1999. [downloadable]
- S. Koenig and R.G. Simmons. Easy and Hard Testbeds for Real-Time Search Algorithms. In AAAI Conference on Artificial Intelligence (AAAI), 279-285, 1996. [downloadable]
- S. Koenig and R.G. Simmons. Complexity Analysis of Real-Time Reinforcement Learning. In AAAI Conference on Artificial Intelligence (AAAI), 99-105, 1993. [downloadable]
- S. Koenig and R.G. Simmons. Complexity Analysis of Real-Time Reinforcement Learning Applied to Finding Shortest Paths in Deterministic Domains. Technical Report, CMU-CS-93-106, School of Computer Science, Carnegie Mellon University, Pittsburgh (Pennsylvania), 1992. [downloadable]
Representative Publications on Nondeterministic Domains
- C. Hernandez, J. Baier, T. Uras and S. Koenig. Time-Bounded Adaptive A*. In International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 997-1006, 2012. [downloadable]
- S. Koenig and X. Sun. Comparing Real-Time and Incremental Heuristic Search for Real-Time Situated Agents. Journal of Autonomous Agents and Multi-Agent Systems, 18, (3), 313-341, 2009. [downloadable]
- S. Koenig and M. Likhachev. Real-Time Adaptive A*. In International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 281-288, 2006. [downloadable]
- S. Koenig. A Comparison of Fast Search Methods for Real-Time Situated Agents. In International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 864-871, 2004. [downloadable]
- S. Koenig. Minimax Real-Time Heuristic Search. Artificial Intelligence Journal, 129, (1-2), 165-197, 2001. [downloadable]
- S. Koenig. Exploring Unknown Environments with Real-Time Search or Reinforcement Learning. In Advances in Neural Information Processing Systems (NeurIPS), 1003-1009, 1999. [downloadable]
- S. Koenig and R.G. Simmons. Solving Robot Navigation Problems with Initial Pose Uncertainty Using Real-Time Heuristic Search. In International Conference on Artificial Intelligence Planning Systems (AIPS), 145-153, 1998. [downloadable]
- S. Koenig and R.G. Simmons. Real-Time Search in Non-Deterministic Domains. In International Joint Conference on Artificial Intelligence (IJCAI), 1660-1667, 1995. [downloadable]
Representative Publications on Applications
- D. Sigurdson, V. Bulitko, W. Yeoh, C. Hernandez and S. Koenig. Multi-Agent Pathfinding with Real-Time Heuristic Search. In IEEE Conference on Computational Intelligence and Games (CIG), 1-8, 2018. [downloadable]
- J. Svennebring and S. Koenig. Building Terrain-Covering Ant Robots. Autonomous Robots, 16, (3), 313-332, 2004. [downloadable]
- S. Koenig, B. Szymanski and Y. Liu. Efficient and Inefficient Ant Coverage Methods. Annals of Mathematics and Artificial Intelligence - Special Issue on Ant Robotics, 31, 41-76, 2001. [downloadable]
- S. Koenig and R.G. Simmons. Solving Robot Navigation Problems with Initial Pose Uncertainty Using Real-Time Heuristic Search. In International Conference on Artificial Intelligence Planning Systems (AIPS), 145-153, 1998. [downloadable]
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