Understanding and Improving On-Line Planning Methods

这是三年持续奖励的第一年资助。人工智能中使用了各种在线规划方法，例如实时搜索方法（如LRTA*），强化学习方法（如Q-learning）和机器人导航方法（如D*）。pi打算大幅提高这些和其他在线规划方法的性能，例如，未来的机器人导航方法将能够比现在更快地绘制未知地形，但具有与现有在线规划方法相同的优势属性。许多在线规划方法，要么总是，要么大部分时间，执行使智能体在目标感知方向上移动的动作，也就是说，移动智能体使其最大程度地减少目标距离的估计。然而，pi的初步理论结果表明，执行使代理在目标感知方向上移动的动作通常不是一个好主意。例如，在最坏的情况下，D*在未知地形中不能以最小的行进距离到达目标位置。提高这些在线计划方法的性能的关键是利用它们维持（或可以维持）的距离估计，以一种更直接地与计划或学习目标相关的方式。pi将从理论上和实验上研究在线规划方法的特性，并将开发改进的在线规划方法，这些方法与现有方法具有相同的接口，这使得这些方法的用户可以轻松地用新方法代替他们目前使用的方法。所提出的研究的附带好处包括为未知地形中机器人导航方法的实验评估开发了一个试验台，并为理解包括D*在内的未知地形中的机器人导航方法奠定了坚实的理论基础。

This is the first year funding of a three year continuing award. A variety of on-line planning methods are used in artificial intelligence including, for example, real-time search methods such as LRTA*, reinforcement-learning methods such as Q-learning, and robot-navigation methods such as D*. The PIs intend to improve the performance of these and other on-line planning methods substantially so that, for example, future robot-navigation methods will be able to map unknown terrain significantly faster than is now possible, yet have the same advantageous properties as existing on-line planning methods. Many on-line planning methods, either always or most of the time, execute actions that move the agent in the perceived direction of the goal, that is, move the agent so that it reduces the estimates of the goal distances the most. However, the PIs preliminary theoretical results show that executing actions that move the agent in the perceived direction of the goal is usually not a good idea. For example, D* does not reach a goal location in unknown terrain with a minimal travel distance in the worst case. The key to improving the performance of these on-line planning methods then is to exploit the distance estimates that they maintain (or can maintain) in a way that is more directly related to the planning or learning objective. The PIs will study the properties of on-line planning methods both theoretically and experimentally, and will develop improved on-line planning methods that have the same interface as the existing methods, which allows users of these methods to easily substitute the new methods for the ones they are currently using. Side benefits of the proposed research include developing a test-bed for the experimental evaluation of robot navigation methods in unknown terrain, and creating a solid theoretical foundation for understanding robot-navigation methods in unknown terrain, including D*.