Realtime Search for Learning Autonomous Agents

点击翻译按钮获取中文摘要

Existing search algorithms can be divided into two classes : offline search such as A^<**>, and realtime search such as Real-Time-A^<**> (RTA^<**>) and Learning Real-Time-A^<**> (LRTA^<**>). Offline search completely examines every possible path to the goal state before executing that path, while realtime search makes each decision in a constant time, and commits its decision to the physical world. The problem solver eventually reaches the goal by repeating the cycle of planning and execution. Realtime search cannot guarantee to find an optimal solution, but can interleave planning and execution.This research focuses on extending realtime search algorithms for autonomous agents and for a multiagent world. Though realtime search provides an attractive framework for resource-bounded problem solving, the behavior of the problem solver is not rational enough for autonomous agents : the problem solver tends to perform superfluous actions before attaining the goal ; and the problem solver cannot utilize and improve previous experiments. Other problems are that though the algorithms interleave planning and execution, they cannot be directly applied to a multiagent world ; the problem solver cannot adapt to the dynamically changing goals ; and the problem solver cannot cooperatively solve problems with other problem solvers. We developed a series of new algorithms including Weighted Realtime Search, Realtime Search with Upper Bounds, Moving Target Search and Realtime Bidirectional Search to overcome the above problems.