Understanding the Role of Exploration in Search and Planning

1.背景作为一名计算科学研究员，我的目标是在解决更复杂的现实世界问题方面取得进展。智能自动化决策需要对应用程序领域进行建模，并处理未来可能的备选方案的潜在巨大空间，有时是离线的，但越来越多地是在实时环境中。我和我的研究小组研究解决难题的高效搜索算法。强大的解决方案技术包括抽象、分而治之的策略，以及多种类型的系统和启发式搜索。虽然我的研究议程涉及到这些方法的许多方面的工作，但目前的提议集中在启发式搜索中的探索这一主题，这已经成为我最近许多工作的共同主题。*对于计算机程序来说，探索是一种获得对其(模拟或真实)环境的体验的方式。这种探索可以用来纠正世界模型中的错误、差距和不确定性。例子包括棋类游戏，探索未来可能的移动序列可以找到制胜策略，以及自动规划，其中探索可以用来发现有希望的动作序列。*2.拟议研究计划的目标*我的主要目标是更好地理解在启发式搜索中使用探索的问题。探索技术是大量且数量不断增加的搜索算法的重要组成部分。蒙特卡罗抽样方法在博弈和概率规划等方面的应用非常成功。然而，尽管取得了所有这些成功，但关于探索方法何时、如何以及为什么有效的许多重要问题仍然存在。3.科学方法概述为了研究启发式搜索中的探索方法，我计划继续致力于构成重大研究挑战的具体应用，如围棋、独立于领域的规划和运动规划。与我的学生和同事一起，我希望继续构建完整的高性能系统，并在标准基准测试和比赛中测试它们。*这项工作将需要从多个角度出发，从对成功部署的系统的深入分析到综合不同基于探索的算法的经验，以及导致用于控制探索的通用框架和自适应模型。对基于探索的方法的更深入的理解可能会导致算法的改进，甚至是全新的算法。它还应该导致计算机程序的显著改进，这些程序可以为困难的启发式搜索问题找到更好的解决方案，可以扩展到更大的问题，并且速度足够快，可以实时使用。

1. Background********As a researcher in Computing Science, my goal is to make progress towards solving ever more complex real-world problems. Intelligent automated decision-making requires modelling an application domain, and processing a potentially huge space of possible future alternatives, sometimes offline but more and more often in a real-time setting. With my research group I study efficient search algorithms for solving hard problems. Powerful solution techniques include abstraction, divide and conquer strategies, and many types of systematic and heuristic search. While my research agenda involves work on many aspects of these approaches, the current proposal focuses on the topic of exploration in heuristic search, which has emerged as the common theme that drives much of my recent work.******For a computer program, exploration is a way of getting experience about its (simulated or real) environment. Such exploration can be used to correct errors, gaps and uncertainty in a model of the world. Examples include board games, where exploration of possible future move sequences can find winning strategies, and automated planning, where exploration can be used to discover promising action sequences.******2. Objectives of the Proposed Research Program********My main objective is to better understand the issues of using exploration in heuristic search. Exploration techniques are vital ingredients of a large and growing number of search algorithms. Monte Carlo sampling methods have been extremely successful in applications including game-playing and probabilistic planning. Yet despite all these successes, many important questions remain about when, how, and why exploration methods work.******3. Summary of Scientific Approach*******To study exploration methods in heuristic search, I plan to continue working on concrete applications which pose significant research challenges, such as the game of Go, domain-independent planning and motion planning. With my students and colleagues, I want to continue building complete high performance systems, and test them on standard benchmarks as well as in competitions.*******This work will require many angles of attack, from in-depth analysis of successful deployed systems to synthesizing the experience from different exploration-based algorithms, and leading towards generic frameworks and adaptive models for controlling exploration. A deeper understanding of exploration-based methods will likely lead to algorithmic improvements or even brand-new algorithms. It should also lead to significantly improved computer programs, which can find better solutions to difficult heuristic search problems, can scale to larger problems, and are fast enough for real-time use.**